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

转换公式如下：

① 对形如 A-> α|β的正则表达式，转换为

A->α

A->β

② 对形如 A->αβ 的正则表达式，转换为

A->αB

B->β

③ 对形如 A->α*β的正则表达式，转换为

A->αB

A->β

B->αB

B->β

例题1：将正则表达式 r = a(a|d)* 转化为相应的正则文法G【S】。

设开始符号为S，则有 S -> a(a|d)*。

把a看作α，(a|d)*看作β，即S -> αβ。带入公式②得到：

S -> aA     ...........    线性文法，符合正则文法 （结果1）

A -> (a|d)*

继续对 A -> (a|d)* 进行分析。

把 A -> (a|d)* 变成  A -> (a|d)*ε 

把 (a|d)*看作α*，把ε 看作β，即A->α*β。带入公式③得到：

A -> (a|d)B

A -> ε

B -> (a|d)B

B -> ε

把所有带“|”的产生式写开，用公式①。

A -> aB     ...........    线性文法，符合正则文法 （结果2）

A -> dB     ...........    线性文法，符合正则文法 （结果3）

A -> ε         ...........    线性文法，符合正则文法 （结果4）

B -> aB     ...........    线性文法，符合正则文法 （结果5）

B -> dB     ...........    线性文法，符合正则文法 （结果6）

B -> ε        ...........    线性文法，符合正则文法 （结果7）

最终的正则文法G【S】结果如下：

S -> aA   

A -> aB    

A -> dB     

A -> ε        

B -> aB    

B -> dB    

B -> ε