regex - 将正则表达式转换为CFG

Question

如何将某种常规语言转换为其等效的上下文无关语法？
是否有必要构造与该正则表达式相对应的DFA，或者是否存在用于此类转换的规则？

例如，考虑以下正则表达式

01+10(11)^*

如何描述上述RE对应的语法？

Answer 1

将A + B更改为语法

G -> A
G -> B

将A *更改为

G -> (empty)
G -> A G

将AB更改为

G -> AB

并以递归方式继续处理A和B。基本情况是空的语言(无结果)和单个符号。

在你的情况下

 A -> 01
 A -> 10B
 B -> (empty)
 B -> 11B

如果语言是通过有限自动机描述的:

使用状态作为非终结符

使用语言作为终端符号集

在原始自动机中的字母a上为任何过渡p-> q添加过渡p-> aq

在语法

中使用初始状态作为初始符号