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

3.8（a）消除习题3.文法的左递归（b）为（a）的文法构造预测分析器答案：（a）S—(L)|aL—SL′L′—,SL′|∈(b)FIRST(S)={(,a}FIRST(L)={(,a,}FIRST(L′)={‘,’,∈}FOLLOW(S)={‘,’，﹩}FOLLOW(L)={)，﹩，‘,’}FOLLW(L′)={)，﹩，‘,’}预测分析表如下：非终结符输入符号（）a,﹩SS—(L)S—aLL—SL′L—SL′L′L′—∈L′—,SL′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））﹩L-L,S归约﹩（L，（L））﹩移进﹩（L，（L））﹩S—(L)归约﹩（L，S）﹩L-L,S归约﹩（L）﹩移进﹩（L）﹩S—(L)归约﹩S﹩Acc（c）图见下页【典型错误】：（a）中要求的是最右推导，很多人没有注意到（b）一般没有错误，但注意a归约到S后要继续归约到L（c）这题的错误主要是没有给出构造的步骤，另外题目要求的是自下而上构造分析表LS（a,(a,a)）（1）LLSS（a,(a,a)）（2）LLSSS（a,(a,a)）（3）LLLSSS（a,(a,a)）（4）SLLLSSS（a,(a,a)）(5)LSLLLSSS（a,(a,a)）(6)SLSLLLSSS（a,(a,a)）(7)