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

Question

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

Answer 1

Ответ от dalibocai:

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

Answer 2

Алгоритм довольно прост, если вы можете вычислить автомат из своего обычного выражения. Как только у вас будет свой автомат. Например, для (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 

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