(a)消除习题3文法的左递归.pdf

3.8 （a ）消除习题3.文法的左递归 （b ）为（a ）的文法构造预测分析器 答案：（a ）S — (L) | a L —SL′ L′— ,S L′|∈ (b) FIRST(S)={(,a} FIRST(L)={(,a,} FIRST(L′)={‘,’, ∈} FOLLOW(S)={ ‘,’，﹩} FOLLOW(L)={ ) ，﹩，‘,’} FOLLW(L′)={ ) ，﹩，‘,’} 预测分析表如下： 非终结符 输入符号 （ ） a , ﹩ S S — (L) S — a L L —SL′ L —SL′ L′ L′— ∈ L′— ,S L′ L′— ∈ 【典型错误】 ：消除左递归请参考书上介绍的方法，有些人引入了两个非终结符， 但不是最简的情况。另外很多人没有构造 FIRST 和 FOLLOW 表，本题需要注意的是当 FIRST 集合中有∈预测分析表的构造方法。 3.15（a）用习题 3.1 的文法构造（a，（a，a））的最右推导，说出每个右句型的句柄。 （b）给出对应（a）的最右推导的移进-归约分析器的步骤。 （c）对照（b）的移进-规约，给出自下而上构造分析树的步骤。 答案：(a) S = (L) = (L,S) =(L,(L)) = (L,(L,S)) = (L,(L,a)) =(L,(S,a)) =(L,(a,a)) =(S,(a,a)) =(a,(a,a)) (b) 栈 输入 动作 ﹩ （a，（a，a））﹩ 移进 ﹩（ a，（a，a））﹩ 移进 ﹩（a ，（a，a））﹩ S-a 归约 ﹩（S ，（a，a））﹩ L-S 归约 ﹩（L ，（a，a））﹩ 移进 ﹩（L， （a，a））﹩ 移进 ﹩（L，（ a，a））﹩ 移进 ﹩（L，（a ，a））﹩ S-a 归约 ﹩（L，（S ，a））﹩ L-S 归约 ﹩（L，（L ，a））﹩ 移进 ﹩（L，（L， a））﹩ 移进 ﹩（L，（L，a ））﹩ S-a 归约 ﹩（L，（L，S ）