Построение детерменированного конечного автомата по регулярному выражению на Python

August 19, 2018 19:02

Конечный автомат - это абстрактная модель, которая содержит в себе конечное число состояний чего-либо. Он используется для управления потоком или выполнения каких-либо команд. Конечный автомат хорошо подойдет для использования в играх, например в качестве искусственного интеллекта, таким образом будет получено удобное решение с минимальным количеством кода.

#!/bin/python
# Пример реализации программы, выполняющей построение 
# детерменированного конечного автомата по регулярному выражению

operators = set('.*|')
brackets = set('()')

class Node:
    """ Класс, представляющий бинарное дерево"""

    def __init__(self):
        self.left, self.right, self.root, self.value = None, None, None, None

    def new_left(self):
        self.left = Node()
        self.left.root = self
        return self.left

    def new_right(self):
        self.right = Node()
        self.right.root = self
        return self.right

    def new_right_root(self):
        self.root = Node()
        self.root.left = self
        return self.root

    def __repr__(self):
        return self.value 

def get_T(regexp):
    """ Возвращает алфавит Т регулярного выражения """

    return set(filter(lambda item: not item in operators | brackets, regexp))

def get_pos(regexp):
    """ Возвращает список позиций рег. без операторов и скобок """
    
    return list(filter(lambda item: not item in operators | brackets, regexp))

def get_pos_count(regexp):
    """ Возвращает количество позиций в рег. выражении """
    
    return len(get_pos(regexp))


def get_filled_concat_symbols_regexp(regexp):
    """ Возвращает рег. выражение, заполненое символами конкатенации '.' """

    T = get_T(regexp)
    filed_regexp = str()

    for i, item in enumerate(regexp):
        filed_regexp += item
        if i + 1 < len(regexp) and regexp[i] in T | set('*)') and regexp[i + 1] in T | set('('):
            filed_regexp += '.'
   
    return filed_regexp

def build_tree(regexp):
    """ Строит синтаксическое дерево выражения, возвращает корень """

    root = Node()
    current = root.new_left()

    T = get_T(regexp)
    filled_regexp = get_filled_concat_symbols_regexp(regexp)

    for token in filled_regexp:

        if token == '(':
            current = current.new_left()
            continue

        if token == ')':
            current = current.root or current.new_right_root()
            continue

        if token in T:
            current.value = token
            current = current.root or current.new_right_root()

            continue

        if token in set('.|'):
            if current.value:
                current = current.new_right_root()
            current.value = token
            current = current.new_right()

            continue

        if token == '*':
            if current.value:
                current = current.new_right_root()
            current.value = token
    
    return current

def nullable(node):
    """ Проверяет могут ли поддеревья породить пустое слово """

    if node is None:
        return True

    if node.value == '|':
        return nullable(node.left) or nullable(node.right)

    if node.value == '.':   
        return nullable(node.left) and nullable(node.right)

    if node.value == '*':
        return True

    return False

i = 1

def fill_tree_pos(root): 
    """ Вычисляет firstpos, lastpos """

    global i

    if root is None:
        return

    fill_tree_pos(root.left)
    fill_tree_pos(root.right)

    root.firstpos = set()
    root.lastpos = set()

    if root.value in operators:

        if root.value == '|':
            root.firstpos |= root.left.firstpos | root.right.firstpos
            root.lastpos |= root.left.lastpos | root.right.lastpos

        if root.value == '.':
            if nullable(root.left):
                root.firstpos |= root.left.firstpos | root.right.firstpos
            else:
                root.firstpos |= root.left.firstpos

            if nullable(root.right):
                root.lastpos |= root.left.lastpos | root.right.lastpos
            else:
                root.lastpos |= root.right.lastpos

        if root.value == '*':
            root.firstpos |= root.left.firstpos
            root.lastpos |= root.left.lastpos
    else:
        root.firstpos.add(i)
        root.lastpos.add(i)

        i += 1

    print(f'{root} = {root.firstpos}, {root.lastpos}')


def fill_followpos(root, followpos):
    """ Вычисляет followpos """

    if root is None:
        return

    fill_followpos(root.left, followpos)
    fill_followpos(root.right, followpos)

    # 1. Пусть n — внутренний узел с операцией «.» (конкатенация); a, b — его потомки. Тогда для каждой позиции i, входящей
    # в lastpos(a), добавляем к множеству значений followpos(i) множество firstpos(b).

    # 2. Пусть n — внутренний узел с операцией «*» (итерация), a — его потомок. Тогда для каждой позиции i, входящей в
    # lastpos(a), добавляем к множеству значений followpos(i) множество firstpos(а). 
    
    if root.value == '.':
        for i in root.left.lastpos:
            followpos[i - 1] |= root.right.firstpos

    if root.value == '*':
        for i in root.left.lastpos:
            followpos[i - 1] |= root.left.firstpos


def build_dka(q0, regexp, followpos):
    positions = get_pos(regexp)

    F = list()
    Q = set()
    
    unhandled = set()

    unhandled.add(tuple(q0))

    while unhandled:
        current = unhandled.pop()
        if not current in Q:
            for i in current:
                next_state = followpos[i - 1]
                F.append((current, positions[i - 1], tuple(next_state)))

                unhandled.add(tuple(next_state))
        Q.add(current)

    return Q, F

if __name__ == '__main__':
    
    regexp = input('regexp: ').strip()
    
    # regexp = '(a|b)*abb' +
    # regexp = '(a(b|c))*c' +
    # regexp = '(ab*a|b)*' -
    regexp += '#'

    root = build_tree(regexp)        
    fill_tree_pos(root)
    followpos = [set() for i in range(get_pos_count(regexp))]
    fill_followpos(root, followpos)
    
    Q, F = build_dka(root.firstpos, regexp, followpos)

    print('followpos:',', '.join(map(str, followpos)))
    print(f'Q = {Q}')
    print(f'q0 = {root.firstpos}')
    print('F = ', '\n'.join(list(map(str, F))))