文法等价变换 文法的等价 对文法G1和G2，若有：L(G1)=L(G2)，则称文法G1和G2等价, 记作:G1=G2. 文法等价变换

Presentation on theme: "文法等价变换 文法的等价 对文法G1和G2，若有：L(G1)=L(G2)，则称文法G1和G2等价, 记作:G1=G2. 文法等价变换"— Presentation transcript:

1 文法等价变换 文法的等价 对文法G1和G2，若有：L(G1)=L(G2)，则称文法G1和G2等价, 记作:G1=G2. 文法等价变换
有些语法分析方法要求被分析的文法满足一定的约束条件，当被分析的文法不满足这些条件是，常常要进行文法变换。

2 重要的文法等价变换 增补产生式 消除空产生式 消除不可达产生式 消除特型产生式 消除公共前缀 消除左递归

3 1.增补产生式 何时需要增补：在自底向上语法分析中需要。
定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2的开始符唯一且不出现于任何产生式的右部。 证明：假设S是G1的开始符，则只要在G1中扩充一条新产生式ZS即可，其中Z是新的开始符。另这样扩充后的文法为G2，则它显然满足定理的要求。 3

4 G2[Z]: 　 Z →S 　　 S → abSA |a 　　 A →b 例: G1[S]: S → abSA | a 　　A → b

5 2.消除空产生式 空产生式: A 定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式A 。
void printStar( ); <函数声明语句>  <类型> id(<形参表>); <形参表>  <形参表> , <形参表> | <类型> id |  定理：对任一文法G1，可构造文法G2，使得L(G1)=L(G2)，且G2中无空产生式A 。

6 2.消除空产生式 证明：根据G1，构造G2的方法如下： 令={A | A}，={A | A + , +}；
对于文法中任意产生式 AX1X2…Xi-1XiXi+1…Xn,若Xi，补充规则 A X1X2…Xi-1Xi+1…Xn； 重复以上过程，直到不出现新的产生式。

7 例 ：设有如下文法 A  aBcD B  b |  D  BB | d 消除该文法中的空产生式. 解： (1) ={B}
A  acD (3) A  aBcD A  ac A  aBc D  BB D  B 得到新的文法如下: A  aBcD | acD | aBc | ac B  b DBB | B | d

8 3.消除不可达产生式 定理：对任一文法G1都可以构造文法G2，使得L(G1)=L(G2)，且G2中的每个非终极符必出现在它的某个句型中。
令={S | S是文法的开始符}。 递归扩充 ={B | AxByG1, BVN, A}。 若A，则删除以A为左部的所有产生式。

9 例子： ZaB|bc BbC|a AaB|a Cc DAB|a 1.={Z} 2.={Z,B} 2.={Z,B,C} A,D无用 3.ZaB|bc BbC|a Cc

10 4：消除特型产生式 特型产生式 若文法中的产生式具有形式AB（B为非终极符），则称该产生式为特型产生式.
特型产生式的缺点是在语法分析中会降低分析的速度，因此应该消除这样的产生式.

11 定理 对任一文法G1，可以构造文法G2，使得L(G1)=L(G2)，并且在G2中没有特型产生式.
(1) 对文法G1中每个非终极符A，求集合: A={B | A=>+B, BVN}. (2) 若BA，且B是文法G中的一个非特型产生式，则补充如下规则： A (3) 去掉文法G1中的所有的特型产生式. (4) 去掉新的文法中的无用产生式.

12 例 设有如下文法 AB | D | aB BC | b Cc DB | d 消除该文法中的特型产生式. 解：A={B, D, C} B={C} C={ } D={B, C} 根据算法第2步在文法中补充如下规则 Ab | d | c Bc Db | c 去掉文法中的特型产生式，得到如下文法 A  aB | b | d | c B  b | c D b | c | d 其中关于C和D的产生式是无用产生式，应去掉.

13 5：消除公共前缀 公共前缀: A→，A→ 这种情形不满足自顶向下的语法分析条件. 消除方法：可用提取左因子的方法.
假定关于Ａ的规则是： A1 | 2 |…| n | 1| 2 |…| γm 则将这些规则写成： AA’ | 1 |γ2|…|γm A’1 | 2 |…|n

14 例子： AaB|aC|aD BbB|bD|c Dd 提取公共前缀 AaA' A'B|C|D BbB'|c B'B|D Dd

15 6.消除左递归 一个文法含有下列形式的产生式时 （1） AAa |b ，称为直接左递归 其中AVN；a, (VNVT)*
（2） AB| BA| 其中A,B VN； a,,, (VNVT)* 称为间接左递归 文法中只要有A+A…，则称文法为左递归的。

16 对于不含回路或空产生式，消除左递归方法为：
（1）对直接左递归形如： AA| 消除左递归得： AA AA| 直接左递归的一般情形： AA1 | A2 |…| Am | 1 | 2| …| n A ( 1 | 2 |…| n ) A’ A’(1 | 2 |…| m) A’ | 

17 （2）间接左递归形如： AB| BA| 转为直接左递归形式： AA|| （或者 BB||） 按照直接左递归方式消除。 A A | A A A |  最后去掉多余的产生式。

18 例： E  T E’ E’  + T E’ |  E  T | E + T T  F | T * F F  i d| ( E )  T  F T’ T’  * F T’ |  F  id | ( E )

19 重要的文法等价变换 增加拓广产生式 消除空产生式 消除不可达产生式 消除特型产生式 消除公共前缀 消除左递归

20 练习： 1.设有如下文法，画出句型（adSdS）的语法树并写出其短语、简单短语和句柄。 S a | b | ( A )
A S d A | S 2、通过文法等价变换消除以下文法G[S]的左递归； G[S]: S->Aa|b A->SB B->ab 3、已知文法G[Z]，说明文法G[Z]为二义性的。   G[Z]: Z→WV  W→aB | aW | a    B→b | bB  V→bV | dD  D→d | dD