编译原理习题课.ppt

1、编译原理习题课,中国海洋大学计算机系 葛 琳 ,第三章习题：例1,下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法 S S and S | S or S | not S | p | q | (S) 非二义文法的产生式如下： E E or T | T T T and F | F F not F | ( E) | p | q,第三章习题：例1,下面的二义文法描述命题演算公式的语法，为它写一个等价的非二义文法 S S and S | S or S | not S | p | q | (S) 非二义文法的产生式如下： E E or T | T T T and F | F F not E

2、 | ( E) | p | q not p and q有两种不同的最左推导,第三章习题：例2,文法 SaSbS | bSaS | （a）abab的两个最左推导： S lm aSbS lm abSaSbS lm abaSbS lm ababS lm abab S lm aSbS lm abS lm abaSbS lm ababS lm abab 该文法具有两个不同的最左推导，因此是二义的。 注意：不能省略步骤！,第三章习题：例2,（b）对应最右推导（这是对应第二个最左推导的最右推导） S rm aSbS rm aSbaSbS rm aSbaSb rm aSbab rmabab （c）对应分析树：

3、 注意：分析树上无箭头。 （d）该文法产生的语言：a,b个数相等的串集,第三章习题：例3,文法：R R | R | RR | R* | (R) | a | b (b) 构造等价非二义文法 分析：*优先级最高，连接次之，|最低。 E E | T | T T TF | F F F * | (E) | a | b (c)用两种文法为ab|b*a构造分析树 二义文法对应的分析树 可以画很多,第三章习题：例4,设计文法，并问哪些文法是正规的 （a）每个a后面至少有一个b跟随的所有串。 分析：该语言可以用正规式(ab | b)*表示，是正规的。对应的文法： SabS | bS | （b）a和b的个数相等的

4、串 二义文法1： S a B | b A | A a S | b A A B b S | a B B 其中 A表示 a比b多一个的串，B表示b比a多一个的串 aabbabab aabbabab,第三章习题：例4,（b）续 二义文法2： SaSbS | bSaS | aabbababaabbabab 非二义文法：S a B S | b A S | A a | b A A B b | a B B 其中 A表示 a比b多一个的串并且不含a和b个数相等的非空后缀，B表示b比a多一个的串并且不含a和b个数相等的非空后缀 aabbabab,第三章习题：例4,(c) a, b个数不相等的串。 用(b)二义文

5、法1的结论： S A | B （ a，b个数不等的串，开始符号） A A | A A （a比b多的串） B B | B B （ b 比a多的串） A a C | b A A （a比b多一个的串） B b C | a B B （ b 比a多一个的串） C a B | b A | （ a，b个数相等的串）,第三章习题：例5,文法：S (L) | a L L, S | S (a)消除该文法的左递归 分析：S是否直接（间接）左递归？L呢？ a | (a, a, (a, ),a) S (L) | a L S L L , S L | ,第三章习题：例5,(b)为(a)的文法构造预测分析器 非递归的： FI

6、RST(S) = FIRST(L) = a, ( FIRST(L)=, , FOLLOW(L) = ) FOLLOW(L) = ) FOLLOW(S)=, , ) , $,第三章习题：例5,(b)为(a)的文法构造预测分析器 递归的： void S () if (lookahead =() match(); L(); match(); else if (lookahead = a) match (a); else error(); ,第三章习题：例5,(b)为a的文法构造预测分析器 递归的： void L () if (lookahead =() | (lookahead = a) S ();

7、 Lprime (); else error(); ,第三章习题：例5,(b)为a的文法构造预测分析器 递归的： void Lprime () if (lookahead = ,) match(,); S(); Lprime(); else if (lookahead = ) return; else error(); ,第三章习题：例6,已知文法的产生式如下： XY1 Y2 Y3 Y4 Y5Y1 a | Y2 b | Y3 c | Y4 d | Y5 e | 求FIRST(X) 根据求FIRST(X)的算法，因为X*，所以 FIRST(X) 因为Y1 a ，所以X *aY2Y3Y4Y5,第三

8、章习题：例6,因为Y1 ， Y2 b，所以X *bY3Y4Y5 因为Y1 ， Y2 ， Y3 c，所以X *cY4Y5 因为Y1 ， Y2 ， Y3 ， Y4 d，所以X *dY5 因为Y1 ， Y2 ， Y3 ， Y4 ， Y5 e，所以X *e 因此，FIRST(X) = , a, b, c, d, e,第三章习题：例7,构造下面文法的LL(1)分析表 DTL Tint | real Lid R R, id R | 准备工作： FIRST(D) = FIRST(T) = int, real FIRST(L)=id FIRST(R)=, , ,第三章习题：例7,FOLLOW(D)=FOLLO

9、W(L)=$ FOLLOW(T) = id FOLLOW(R) = $ FIRST(TL) = FIRST(T) = int, real FIRSTint = int FIRSTreal = real FIRSTid R = id FIRST, id R = ,第三章习题：例7,第三章习题：例8,下面文法是否LL(1)文法？说明理由。 SA B | P Q x Ax y Bb c Pd P | Qa Q | 思路：根据LL(1)文法的定义 FIRST(AB) = FIRST(A) = x FIRST(PQx) = d, a, x FIRST(AB) FIRST(PQx) = x 该文法不是LL(1)的。,第三章习题：例9,证明下面文法不是LL(1)文法。 PP | ，其中PVN，、V*且不为空串。 思路：该题实际上是要求证明左递归文法不是LL(1)文法。从LL(1)文法定义入手。 不为空，因此FIRST(P) = FIRST() FIRST(P ) FIRST() = FIRST(P) FIRST() = FIRST() 所以该文法不是LL(1)的 注意： FIRST() ,第三章习题：例9,若该题允许为空，则还需