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

Question

有没有算法或工具可以将正则语法转换为正则表达式？

Answer 1

dalibocai 的回答：

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

此处提供了教程：https://www2.cs.duke。 edu/csed/jflap/tutorial/framebody.html

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

当然，另一个方向的路线提供了一种将正则语法转换为自动机（即有理表达式）的方法。

Answer 3

从理论角度来看，解决此问题的算法的工作原理是根据语法中的每个规则创建正则表达式，并求解初始符号的所得方程组。

例如，对于正则语法 ({S,A},{a,b,c},P,S)：

P:
   S -> aA | cS | a  | c
   A -> aA | a  | bS

1. 采用每个非项式符号并从右手生成正则表达式：

   <前><代码>S = aA + cS + a + c
   A = aA + bS + c

2. 求解初始符号S的方程组：

   A = a(aA + bS + c) + bS + c
   A = a⁺bS + a⁺c + bS + c  
   
   S = aA + c(aA + cS + a + c)
   S = aA + c⁺aA + c⁺a + c⁺
   
   S = a(a⁺bS + a⁺c + bS + c) + c⁺a(a⁺bS + a⁺c + bS + c) + c⁺a + c⁺
   S = a⁺bS + a⁺c + c⁺a⁺bS + c⁺a⁺c + c⁺a + c⁺
   
   S = (c⁺ + ε)a⁺bS + a⁺c + c⁺(a⁺c + a + ε)
   
   替换： x = (c⁺ + ε)a⁺b
   
   S = x(xS + a⁺c + c⁺(a⁺c + a + ε)) + a⁺c + c⁺(a⁺c + a + ε)
   S = x⁺a⁺c + x⁺c⁺(a⁺c + a + ε) + a⁺c + c⁺(a⁺c + a + ε)
   S = x*(a⁺c + c⁺(a⁺c + a + ε))
   
   S = ((c⁺ + ε)a⁺b)*(⁺a⁺c + c⁺(a⁺c + a + ε)) 
   

因为所有修改都是等价的，((c⁺ + ε)a⁺b)*(⁺a⁺c + c⁺(a⁺c + a) + ε)) 是一个正则表达式，相当于可以从初始符号生成的所有单词。因此，这个表达式的值必须等于由初始符号为 S 的语法生成的语言。

它并不漂亮，但我故意选择了一个包含循环的语法来描述算法的工作方式。最难的部分是认识到 S = xS | x 相当于 S = x⁺，然后只需进行替换即可。

Answer 4

我将把这个作为这个老问题的答案，以防有人发现它有用：

我最近发布了一个正是用于此目的的库：

https://github.com/rindPHI/grammar2regex

您可以精确地转换正则语法，还可以计算更通用的上下文无关语法的近似正则表达式。输出格式可以配置为自定义 ADT 类型或 z3 SMT 求解器的正则表达式格式 (z3.ReRef)。

在内部，该工具将语法转换为有限自动机。如果您对自动机本身感兴趣，可以调用方法right_linear_grammar_to_nfa。