编译原理第四章-课后题.pdf

第四章
1.1考虑下面文法G1
S->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->ABBA
A->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->-Expr
Expr->(Expr)|VarExprTail
ExprTail->-Expr|ε
Var->idVarTail
VarTail->(Expr)|ε
(1)构造LL（1）分析表
(2)给出句子id--id((id))的分析过程
答：为书写方便，将文法写为：
A->A|(A)|VB
B->-A|ε
V->aD
D->(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->VB
BB->-AB->εB->ε
VV->aD
DD->ε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->ε