编译原理--正则文法与正则表达式

冷不防 2022-02-25 06:10 283阅读 0赞

*  对任何正则文法`G`，存在定义同一语言的正则表达式`r`
 *  对任何正则表达式`r`，存在生成同一语言的正则文法`G`

## 正则文法到正则表达式的转换 ##

1.  将正则文法中的每个非终结符表示成关于它的一个正则表达式方程，获得一个联立方程组
2.  依照求解规则：
    
     *  若 x = α x ∣ β x=\\alpha x | \\beta x=αx∣β（若 x = α x + β x=\\alpha x + \\beta x=αx\+β），则解为： x = α ∗ β x=\\alpha^\*\\beta x=α∗β
     *  若 x = x α ∣ β x=x\\alpha | \\beta x=xα∣β（若 x = x α + β x=x\\alpha + \\beta x=xα\+β），则解为 x = β x ∗ x=\\beta x^\* x=βx∗

以及正则表达式的代数定理，求文法开始符号的正规式方程组的解。这个解释关于该文法开始符号`S`的一个正规式。

例：

设有正则文法G：  
 Z → 0 A Z \\to 0A Z→0A

A → 0 A ∣ 0 B A \\to 0A | 0B A→0A∣0B

B → 1 A ∣ ϵ B\\to 1A|\\epsilon B→1A∣ϵ

试给出该文法生成语言的正则表达式

*  首先给出相应正则表达式方程组（即用`+`代替正则表达式`|`）

Z → 0 A Z \\to 0A Z→0A  
2.  
 A → 0 A + 0 B A \\to 0A + 0B A→0A\+0B  
3.  
 B → 1 A + ϵ B\\to 1A+\\epsilon B→1A\+ϵ

将3式代入2式中得，  
4.  
 A = 0 A + 01 A + 0 A = 0A + 01A + 0 A=0A\+01A\+0  
对4式利用分配率：  
5.  
 A = ( 0 + 01 ) A + 0 A = (0+01)A + 0 A=(0\+01)A\+0

对5式使用**求解规则**：  
6.  
 A = ( 0 + 01 ) ∗ 0 A=(0+01)^\*0 A=(0\+01)∗0

将式6代入式1中的A得：  
 Z = 0 ( 0 + 01 ) ∗ 0 Z=0(0+01)^\*0 Z=0(0\+01)∗0

## 正则表达式到正则文法的转换 ##

字母表 ∑ \\sum ∑上的正则表达式到正则文法 G = ( V N , V T , P , S ) G=(V\_N, V\_T,P,S) G=(VN,VT,P,S)的转换方法如下:

*  令 V T = ∑ V\_T=\\sum VT=∑
 *  对任意正则表达式`R`选择一个非终结符`Z`生成规则 Z → R Z \\to R Z→R，并令 S = Z S=Z S=Z
 *  若 a a a和 b b b都是正则表达式，对形如 A → a b A\\to ab A→ab的规则转换成 A → a B A \\to aB A→aB和 B → b B\\to b B→b两规则，其中`B`是新增的非终结符
 *  在已转换的文法中，将形如 A → a ∗ b A \\to a^\*b A→a∗b的规则进一步转换成 A → a A ∣ b A \\to aA | b A→aA∣b
 *  不断利用第三和第四条规则进行变换，**直到每条规则最多含有一个终结符**。

例如：

将 R = ( a ∣ b ) ( a a ) ∗ ( a ∣ b ) R=(a|b)(aa)^\*(a|b) R=(a∣b)(aa)∗(a∣b)转换成相应的正则文法

令 A A A是文法开始符号，根据第二条规则可变换为：  
 A → ( a ∣ b ) ( a a ) ∗ ( a ∣ b ) A \\to (a|b)(aa)^\*(a|b) A→(a∣b)(aa)∗(a∣b)

根据第三条规则变换为：

A → ( a ∣ b ) B A \\to (a|b)B A→(a∣b)B

B → ( a a ) ∗ ( a ∣ b ) B \\to (aa)^\*(a|b) B→(aa)∗(a∣b)

根据第四条规则变换为：  
 A → a B ∣ b B A \\to aB|bB A→aB∣bB

B → a a B ∣ a ∣ b B \\to aaB|a|b B→aaB∣a∣b

根据第五条规则变换为：  
 A → a B ∣ b B A \\to aB|bB A→aB∣bB

B → a C ∣ a ∣ b B \\to aC|a|b B→aC∣a∣b

C → a B C\\to aB C→aB