资源描述：
《编译原理第四章-课后题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第四章1.1考虑下面文法G1S->a
2、^
3、(T)T->T,S
4、S消去G1的左递归。然后对每个非终结符，写出不带回溯的递归子程序。答:：(1)消除左递归:S->a
5、^
6、(T)T->ST’T’->,ST’
7、ε(2)first(S)={a,^,(}first(T)={a,^,(}first(T’)={,ε}First(a)={a},First(^)={^},First((T))={(}S的所有候选的首符集不相交First(,ST’)={,},First(ε)={ε},T’的所有候选的首符集不相交Follow
8、(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’
9、εT’(){if(lookahe
10、ad=’,’){advance;S();T’();}Elseif(lookahead=Follow(T’))advance;Elseerror;}3.3.下面文法是否是LL(1)文法，说明理由。S->ABBAA->a
11、εB->b
12、ε答：1.文法不含直接和间接左递归2.first(a)={a}∩first(ε)={ε}为{}first(b)={b}∩first(ε)={ε}为{}3.first(S)={a,b,ε}first(A)={a,ε}first(B)={b,ε}Follow(S)={#}foll
13、ow(A)={a,b,#}follow(B)={a,b,#}First(A)∩follow(A)不为空所以，不是LL(1)文法。4.对下面文法：Expr->-ExprExpr->(Expr)
14、VarExprTailExprTail->-Expr
15、εVar->idVarTailVarTail->(Expr)
16、ε(1)构造LL（1）分析表(2)给出句子id--id((id))的分析过程答：为书写方便，将文法写为：A->A
17、(A)
18、VBB->-A
19、εV->aDD->(A)
20、εFirst(A)={-(a}Fi
21、rst(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))#
22、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->ε
