《龙书 第四章课后作业答案》由会员分享，可在线阅读，更多相关《龙书 第四章课后作业答案（13页珍藏版）》请在金锄头文库上搜索。
1、龙书 第四章课后作业答案 P1774.14 为练习4.3的文法构造一个预测语法分析器 bexprbexpr or bterm|bterm btermbterm and bfactor | bfactor bfactornot bfactor|(bexpr)|true |false 解1 非递归方法 1)消除左递归 bexprbterm A Aor bterm A A btermbfactor B Band bfactor B B bfactornot bfactor bfactor(bexpr) bfactortrue bfactorfalse 2)求first集与follow集 针对以同一非
2、总结符开头的产生式右部求first集如果该非终结符能产生则需要求其follow集 bexprbterm A first(bterm A)= not,(,true,false Aor bterm A first(or bterm A)=or Afollow(A）=follow(bexpr)= $, ) btermbfactor B first(bfactor B)=not,(,true,false Band bfactor B first(and bfactor B)=and Bfollow(B）=follow(bterm)=first(A) 因为first(A)= or , 包含 所以foll
3、ow(B）=follow(bterm) =first(A)follow(A）-=or, $, ) bfactornot bfactor first(not bfactor)=not bfactor(bexpr)first(bexpr)=( bfactortrue first(true)=true bfactorfalse first(false)=false 表中空白处填error，表示调用错误处理程序 4)根据步骤3）编写预测分析程序 下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。 repeat X=当前栈顶符号;a=当前输入符号； if XT# then if X=a t
4、hen if X# then 将X弹出,且前移输入指针 else error else if MX,a=Y1Y2Y k then 将X弹出;依次将Y kY2Y1压入栈； 输出产生式XY1Y2Y k else error until X=# 注： 如果考虑错误恢复，上面的预测分析表还显得简单，应该将每个非总结符的follow集作为同步(sync)记号，便于错误恢复。具体留给感兴趣的同学深入研究 解2：递归下降方法 消除给定文法中的左递归，并提取公因子： bexprbterm or bterm btermbfactor and bfactor bfactornot bfactor | (bexpr
5、) | true |false 用类Pascal语言写出其递归预测分析器 PROCEDURE bexpr; BEGIN Bterm WHILE (lookahead =or) BEGIN match (or); bterm; END; END; PROCEDURE bterm; BEGIN bfactor; WHILE (lookahead =and); BEGIN match (and); bfactor; END; END; PROCEDURE bfactor; BEGIN if (llokahead=not) then BEGIN match (not); bfactor; END el
6、se if (lookahead=() then BEGIN match (); bexpr; match(); END else if (lookahead =true) then match (true) else if (lookahead=false) then match (false); else error; END; P1784.24 图4-60给出了练习4.1中文法的算符优先关系，利用这些优先关系分析练习4.1(b)的句子。 S(L)|a LL,S|S 解： 对每个终结符或建立符号f与g，把f (和g ) 分成一组。根据文法的算符优先关系表，画出如下的有向图。 优先函数如下：
7、 用算符优先分析法分析句子(a,(a,a) 另外2个句子的分析略。 (也可不必如上面先构造优先矩阵在分析，亦可直接分析) P1794.35 考虑下面文法 EE+T|T TTF|F FF*|a|b a）试为该文法构造SLR语法分析表 解： 该文法的拓广文法G为 (0) E E (1) E E+T (2) E T (3) T TF (4) T F (5) F F* (6) F a (7) F b 其LR(0)项目集规范族和goto函数(识别活前缀的DFA)如下: = EE, EE+T, ET, TTF, TF, FF*,Fa, Fb I =EE, EE+T I 1 =ET, TTF, FF*, F
8、a, Fb I 2 =TF, FF* I 3 =Fa I 4 =Fb I 5 =EE+T, TTF, TF, FF*, Fa, Fb I 6 =TTF, FF* I 7 =FF* I 8 =EE+T, TTF, FF*, Fa, Fb I 9 求FOLLOW集： FOLLOW(E)=, FOLLOW(T)=, , a, b FOLLOW(F)=, , a, b, * 构造的SLR分析表如下： 显然，此分析表无多重定义入口，所以此文法是SLR文法。 P1794.37 a）证明下面的文法是LL(1)文法，但不是SLR(1)文法 SAaAb|BbBa A B 解： 对于产生式SAaAb|BbBa 来
9、说 FIRST(AaAb)FIRST(BbBa)=ab= 仅有一条候选式。 而A，BV N 因此，这个文法是LL(1)的。 下面构造这个文法的识别活前缀的DFA。 = SS, SAaAb, SBbBa, A, B I I = SS 1 = SAaAb I 2 I = SBbBa 3 = SAaAb, A I 4 I = SBbBa, B 5 = SAaAb I 6 I = SBbBa 7 I = SAaAb 8 I = SBbBa 9 由于FOLLOW(A)=FOLLOW(B)=a, b 因此项目集I 0中存在归约归约冲突。在I 状态下，当输入符号是a或是b时， 不知用A还是B进行归约。故此文
10、法不是SLR(1)的。但是，此文法时LR(1)的。 P1794.40证明下面的文法是LR(1)文法 SAa| bAc| Bc| bBa Ad Bd 解 拓广文法为： G : (0) SS (1) SAa (2) SbAc (3) SBc (4) SbAa (5) Ad (6) Bd 有效项目集族为： I0: S?S ，# S?Aa ，# S?bAc，# S?Bc ，# S?bBa，# A?d ，a B?d ，c I1: goto(I0 ,S) SS?, # I2: goto (I0 ,A) S A?a ，# I3: goto (I0 ,b) S b?Ac，# S b?Ba，# A?d ，c B?d ，a I5: goto (I0 ,d) A d ?，a B d ?，c I7: goto (I3 ,A) S bA?c，# I11: goto (I7 ,c) S bAc ?，# I12: goto (I8 ,a) S bBa ?，# I9: goto (I3 ,d)
