P1774.14 为练习4.3的文法构造一个预测语法分析器bexpr→bexpr or bterm|btermbterm→bterm and bfactor | bfactorbfactor→not bfactor|(bexpr)|true |false解1 非递归方法1)消除左递归①bexpr→bterm A②A→or bterm A③A→ε④bterm→bfactor B⑤B→and bfactor B⑥B→ε⑦bfactor→not bfactor⑧bfactor→(bexpr)⑨bfactor→true⑩bfactor→false2)求first集与follow集针对以同一非总结符开头的产生式右部求first集如果该非终结符能产生ε则需要求其follow集①bexpr→bterm A first(bterm A)= {not,(,true,false}②A→or bterm A first(or bterm A)={or}③A→εfollow(A）=follow(bexpr)= {$, )}④bterm→bfactor B first(bfactor B)={not,(,true,false}⑤B→and bfactor B first(and bfactor B)={and}⑥B→εfollow(B）=follow(bterm)=first(A)因为first(A)= {or , ε} 包含ε所以follow(B）=follow(bterm)=first(A)∪follow(A）-{ε}={or, $, )}⑦bfactor→not bfactor first(not bfactor)={not}⑧bfactor→(bexpr)first((bexpr))={(}⑨bfactor→true first(true)={true}⑩bfactor→false first(false)={false}表中空白处填error，表示调用错误处理程序4)根据步骤3）编写预测分析程序下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。
repeatX=当前栈顶符号;a=当前输入符号；if X∈ＶT∪{#} thenif X=a thenif X≠# then {将X弹出,且前移输入指针}else errorelseif M[X,a]=Y1Y2…Y k then{将X弹出;依次将Y k…Y2Y1压入栈；输出产生式X→Y1Y2…Y k }else erroruntil X=#注：如果考虑错误恢复，上面的预测分析表还显得简单，应该将每个非总结符的follow集作为同步(sync)记号，便于错误恢复。
具体留给感兴趣的同学深入研究解2：递归下降方法①消除给定文法中的左递归，并提取公因子：bexpr→bterm {or bterm }bterm→bfactor {and bfactor}bfactor→not bfactor | (bexpr) | true |false②用类Pascal语言写出其递归预测分析器PROCEDURE bexpr;BEGINBtermWHILE (lookahead =='or')BEGINmatch ('or');bterm;END;END;PROCEDURE bterm;BEGINbfactor;WHILE (lookahead =='and');BEGINmatch ('and');bfactor;END;END;PROCEDURE bfactor;BEGINif (llokahead=='not')then BEGINmatch ('not');bfactor;ENDelse if (lookahead=='(')then BEGINmatch ('(');bexpr;match(')');ENDelse 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)|aL→L,S|S解：对每个终结符或＄建立符号f与g，把f(和g)分成一组。
根据文法的算符优先关系表，画出如下的有向图。
优先函数如下：用算符优先分析法分析句子(a,(a,a)) 另外2个句子的分析略。
(也可不必如上面先构造优先矩阵在分析，亦可直接分析)P1794.35 考虑下面文法E→E+T|TT→TF|FF→F*|a|ba）试为该文法构造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)如下:= {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*,F→·a, F→·b} I={E'→E·, E→E·+T}I1={E→T·, T→T·F, F→·F*, F→·a, F→·b}I2={T→F·, F→F·*}I3={F→a·}I4={F→b·}I5={E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b}I6={T→TF·, F→F·*}I7={F→F*·}I8={E→E+T·, T→T·F, F→·F*, F→·a, F→·b}I9求FOLLOW集：FOLLOW(E)={＋, ＄}FOLLOW(T)={＋, ＄, a, b}FOLLOW(F)={＋, ＄, a, b, *}构造的SLR分析表如下：显然，此分析表无多重定义入口，所以此文法是SLR文法。
P1794.37 a）证明下面的文法是LL(1)文法，但不是SLR(1)文法S→AaAb|BbBaA→εB→ε解：对于产生式S→AaAb|BbBa 来说FIRST(AaAb)∩FIRST(BbBa)={a}∩{b}=Φ仅有一条候选式。
而A，B∈VN因此，这个文法是LL(1)的。
下面构造这个文法的识别活前缀的DFA。
= {S'→·S, S→·AaAb, S→·BbBa, A→·, B→·} II= {S'→S·}1= {S→A·aAb}I2I= {S→B·bBa}3= {S→Aa·Ab, A→·}I4I= {S→Bb·Ba, B→·}5= {S→AaA·b}I6I= {S→BbB·a}7I= {S→AaAb·}8I= {S→BbBa·}9由于FOLLOW(A)=FOLLOW(B)={a, b}因此项目集I0中存在归约－归约冲突。
在I状态下，当输入符号是a或是b时，不知用A→ε还是B→ε进行归约。
故此文法不是SLR(1)的。
但是，此文法时LR(1)的。
P1794.40证明下面的文法是LR(1)文法S→Aa| bAc| Bc| bBaA→dB→d解拓广文法为：G' : (0) S'→S(1) S→Aa(2) S→bAc(3) S→Bc(4) S→bAa(5) A→d(6) B→d有效项目集族为：I0:S`→•S ，#S→•Aa ，#S→•bAc，#S→•Bc ，#S→•bBa，#A→•d ，aB→•d ，c I1: goto(I0 ,S)S`→S•, #I2: goto (I0 ,A)S→ A•a ，# I3: goto (I0 ,b)S→ b•Ac，#S→ b•Ba，#A→•d ，cB→•d ，a I5: goto (I0 ,d)A→ d •，aB→ d •，cI7: goto (I3 ,A)S→ bA•c，#I11: goto (I7 ,c)S→ bAc •，#I12: goto (I8 ,a)S→ bBa •，# I9: goto (I3 ,d)A→d •，cB→d •，aLR(1)项目集不存在冲突该文法是LR(1)文法。