Как преобразовать регулярную грамматику в регулярное выражение?

Question

Существует ли алгоритм или инструмент для преобразования регулярной грамматики в регулярное выражение?

Answer 1

Алгоритм довольно прост, если вы можете вычислить автомат из вашего регулярного выражения.Как только у вас есть свой автомат.Например, для (aa*b|c) автоматом будет (стрелки идут вправо):

          a
         / \
      a  \ / b
-> 0 ---> 1 ---> 2 ->
    \___________/
          c

Затем просто «перечислите» свои переходы как правила.Ниже рассмотрим, что 0, 1 и 2 - нетерминальные символы, и, конечно, a, b и c - токены.

0: a1 | c2
1: a1 | b2
2: epsilon

или, если вы не хотите пустых правых частей.

0: a1 | c
1: a1 | b

И, конечно, маршрут в другом направлении предоставляет одно средство для преобразования регулярной грамматики в автомат, следовательно, рациональное выражение.

Answer 2

Ответ от Далибокай :

Моя цель - преобразовать обычный грамматик в DFA. Наконец-то я нашел отличный инструмент: JFLAP .