如何将常规语法转换为正则表达式？

Is there an algorithm or tool to convert regular grammar to regular expression?

是否有将常规语法转换为正则表达式的算法或工具？

2 个解决方案

#1

Answer from dalibocai:

来自dalibocai的回答：

My goal is to convert regular grammer to DFA. Finally, I found an excellent tool : JFLAP.

我的目标是将常规语法转换为DFA。最后，我发现了一个很好的工具：JFLAP。

#2

The algorithm is pretty straightforward if you can compute an automaton from your regular expression. Once you have your automaton. For instance for (aa*b|c), an automaton would be (arrows go to the right):

如果您可以从正则表达式计算自动机，则该算法非常简单。一旦你有自动机。例如对于（aa * b | c），自动机将是（箭头向右）：

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

Then just "enumerate" your transitions as rules. Below, consider that 0, 1, and 2 are nonterminal symbols, and of course a, b and c are the tokens.

然后只需“枚举”您的过渡作为规则。下面，考虑0,1和2是非终结符号，当然a，b和c是令牌。

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

or, if you don't want empty right-hand sides.

或者，如果你不想要空的右手边。

0: a1 | c
1: a1 | b

And of course, the route in the other direction provides one means to convert a regular grammar into an automaton, hence a rational expression.

当然，另一个方向的路径提供了一种将常规语法转换为自动机的方法，因此是一种理性的表达方式。

#1