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

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

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

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

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

例：web

设有正则文法G：
$Z \to 0A$正则表达式

$A \to 0A | 0B$app

$B\to 1A|\epsilon$svg

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

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

$Z \to 0A$
2.
$A \to 0A + 0B$
3.
$B\to 1A+\epsilon$code

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

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

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

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

字母表 $\sum$上的正则表达式到正则文法 $G=(V_N, V_T,P,S)$的转换方法以下:

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

例如：

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

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

根据第三条规则变换为：

$A \to (a|b)B$

$B \to (aa)^*(a|b)$

根据第四条规则变换为：
$A \to aB|bB$

$B \to aaB|a|b$

根据第五条规则变换为：
$A \to aB|bB$

$B \to aC|a|b$

$C\to aB$