第四章课后作业答案

P1774.14 为练习4.3的文法构造一个预测语法分析器 bexpr→bexpr or bterm|bterm bterm→bterm and bfactor | bfactor bfactor→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→false 2) 求first集 与 follow集 针对以同一非 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 符开头的产生式右部求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} 3) 根据步骤2）画预测分析 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf   or and not ( ) true false $ bexpr         A           bterm         B         bfactor                           表中空白处填error，表示调用错误处理程序 4) 根据步骤3）编写预测分析程序 下面给出通用的预测分析算法，具体程序留给同学们根据算法自己完善。 repeat X=当前栈顶符号;a=当前输入符号； if X∈ＶT∪{#} then if X=a then if X≠# then {将X弹出,且前移输入指针} else error else if M[X,a]=Y1Y2…Yk then {将X弹出;依次将Yk…Y2Y1压入栈； 输出产生式X→Y1Y2…Yk } else error until X=# 注： 如果考虑错误恢复，上面的预测分析表还显得简单，应该将每个非总结符的follow集作为同步(sync)记号，便于错误恢复。具体留给感兴趣的同学深入研究 解2：递归下降方法 ①消除给定文法中的左递归，并提取公因子： bexpr→bterm {or bterm } bterm→bfactor {and bfactor} bfactor→not bfactor | (bexpr) | 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 else 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 L→L,S|S 解： 对每个终结符或＄建立符号f与g，把f(和g) 分成一组。根据文法的算符优先关系表，画出如下的有向图。 优先函数如下： 用算符优先分析法分析句子(a,(a,a))  另外2个句子的分析略。 (也可不必如上面先构造优先矩阵在分析，亦可直接分析) P1794.35 考虑下面文法 E→E+T|T T→TF|F F→F*|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)项目集 规范 编程规范下载gsp规范下载钢格栅规范下载警徽规范下载建设厅规范下载 族和goto函数(识别活前缀的DFA)如下: I0 = {E'→·E, E→·E+T, E→·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I1 ={E'→E·, E→E·+T} I2 ={E→T·, T→T·F, F→·F*, F→·a, F→·b} I3 ={T→F·, F→F·*} I4 ={F→a·} I5 ={F→b·} I6 ={E→E+·T, T→·TF, T→·F, F→·F*, F→·a, F→·b} I7 ={T→TF·, F→F·*} I8 ={F→F*·} I9 ={E→E+T·, T→T·F, F→·F*, F→·a, F→·b} 求FOLLOW集： FOLLOW(E)={＋, ＄} FOLLOW(T)={＋, ＄, a, b} FOLLOW(F)={＋, ＄, a, b, *} 构造的SLR分析表如下： 显然，此分析表无多重定义入口，所以此文法是SLR文法。 P1794.37 a）证明下面的文法是LL(1)文法，但不是SLR(1)文法 S→AaAb|BbBa A→ε B→ε 解： 对于产生式S→AaAb|BbBa 来说 FIRST(AaAb)∩FIRST(BbBa)={a}∩{b}=Φ 而A，B∈VN仅有一条候选式。 因此，这个文法是LL(1)的。 下面构造这个文法的识别活前缀的DFA。 I0 = {S'→·S, S→·AaAb, S→·BbBa, A→·, B→·} I1 = {S'→S·} I2 = {S→A·aAb} I3 = {S→B·bBa} I4 = {S→Aa·Ab, A→·} I5 = {S→Bb·Ba, B→·} I6 = {S→AaA·b} I7 = {S→BbB·a} I8 = {S→AaAb·} I9 = {S→BbBa·} 由于FOLLOW(A)=FOLLOW(B)={a, b} 因此项目集I0中存在归约－归约冲突。在I0状态下，当输入符号是a或是b时，不知用A→ε还是B→ε进行归约。故此文法不是SLR(1)的。但是，此文法时LR(1)的。 P1794.40证明下面的文法是LR(1)文法 S→Aa| bAc| Bc| bBa A→d B→d 解 拓广文法为： G' : (0) S'→S (1) S→Aa (2) S→bAc (3) S→Bc (4) S→bAa (5) A→d (6) B→d 有效项目集族为： LR(1)项目集不存在冲突 该文法是LR(1)文法 LR(1)项目集不存在冲突 该文法是LR(1)文法