编译原理第四章-课后题

第四章1.1考虑下面文法G1S-a|^|(T)T-T,S|S消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。答:：(1)消除左递归:S-a|^|(T)T-ST’T’-,ST’|ε(2)first(S)={a,^,(}first(T)={a,^,(}first(T’)={,ε}First(a)={a},First(^)={^},First((T))={(}S的所有候选的首符集不相交First(,ST’)={,},First(ε)={ε},T’的所有候选的首符集不相交Follow(T’)=Follow(T)={)}first(T’)∩Follow(T’)={}所以改造后的文法为LL(1)文法。不带回溯的递归子程序如下：S(){if(lookahead=’a’)advance;Elseif(lookahead=’^’)advance;Elseif(lookahead=’(’){advance;T();if(lookahead=’)’)advance;elseerror();}Elseerror();}T(){S();T’():}T’-,ST’|εT’(){if(lookahead=’,’){advance;S();T’();}Elseif(lookahead=Follow(T’))advance;Elseerror;}3.3.下面文法是否是LL(1)文法，说明理由。S-ABBAA-a|εB-b|ε答：1.文法不含直接和间接左递归2.first(a)={a}∩first(ε)={ε}为{}first(b)={b}∩first(ε)={ε}为{}3.first(S)={a,b,ε}first(A)={a,ε}first(B)={b,ε}Follow(S)={#}follow(A)={a,b,#}follow(B)={a,b,#}First(A)∩follow(A)不为空所以，不是LL(1)文法。4.对下面文法：Expr--ExprExpr-(Expr)|VarExprTailExprTail--Expr|εVar-idVarTailVarTail-(Expr)|ε(1)构造LL（1）分析表(2)给出句子id--id((id))的分析过程答：为书写方便，将文法写为：A-A|(A)|VBB--A|εV-aDD-(A)|εFirst(A)={-(a}First(B)={-ε}first(V)={a}first(D)={(ε}Follow(A)={#)}follow(B)={#)}follow(V)={#)-}follow(D)={#-)}LL（1）分析表如下：-(a)#AA--AA-(A)A-VBBB--AB-εB-εVV-aDDD-εD-(A)D-εD-ε句子id--id((id))即a--a((a))的分析过程如下：符号栈输入串所用产生式#Aa--a((a))##BVa--a((a))#A-VB#BDaa--a((a))#V-aD#BD--a((a))##B--a((a))#D-ε#A---a((a))#B--A#A-a((a))##A--a((a))#A--A#Aa((a))##BVa((a))#A-VB#BDaa((a))#V-aD#BD((a))##B)A(((a))#D-(A)#B)A(a))##B))A((a))#A-(A)#B))Aa))##B))BVa))#A-VB#B))BDaa))#a))##B))BD))##B))B))#D-ε#B))))#B-ε#B))##B###B-ε