编译原理第五章 作业参考答案.doc

编译原理习题解答 页7/7
第五章 自顶向下语法分析方法
1．对文法G[S]
Sàa|∧|(T)
TàT,S|S
(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。
(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。
(3) 经改写后的文法是否是LL(1)的？给出它的预测分析表。
(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。
解：
(1) (a,(a,a))的最左推导为Sà(T)à(T,S)à(S,S)à(a,(T))à(a,(T,S))à(a,(S,a))à(a,(a,a))
(((a,a),∧,(a)),a)的最左推导为
Sà(T)à(T,S)à(S,a)à((T),a)à((T,S),a)à((T,S,S),a)à((S,∧,(T)),a)à(((T),∧,(S)),a)
à(((T,S),∧,(a)),a)à(((S,a),∧,(a)),a)à(((a,a),∧,(a)),a)
(2)由于有TàT,S的产生式，所以消除该产生式的左递归，增中一个非终结符U有新的文法G/[S]:
Sàa|∧|(T)
TàSU
Uà，SU|ε
分析子程序的构造方法
对满足条件的文法按如下方法构造相应的语法分析子程序。
(1) 对于每个非终结号U，编写一个相应的子程序P(U)；
(2) 对于规则U::=x1|x2|..|xn,有一个关于U的子程序P(U),P(U)按如下方法构造：
IF CH IN FIRST(x1) THEN P(x1)
ELSE IF CH IN FIRST(x2) THEN P(x2)
ELSE ...
.
.
.
IF CH IN FIRST(xn) THEN P(xn)
ELSE ERROR
其中，CH存放当前的输入符号，是一个全程变量；ERROR是一段处理出错信息的程序；
P(xj)为相应的子程序。
(3) 对于符号串x=y1y2...yn;p(x)的含义为：
BEGIN
P(y1);
P(y2);
...
P(yn);
END
如果yi是非终结符，则P(yi)代表调用处理yi的子程序；
如果yi是终结符，则P(yi)为形如下述语句的一段子程序
IF CH=yi THEN READ(CH) ELSE ERROR
即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中，
否则表明出错。
(4) 如果文法中有空规则U::=EPSILON,则算法中的语句
IF CH IN FIRST(xn) THEN P(xn)
ELSE ERROR
改写为：
IF CH IN FIRST(xn) THEN P(xn)
ELSE IF CH IN FOLLOW(U) THEN RETURN
ERROR
(5) 要分析一个OrgStr,应在该串的后面加上一个串括号'#',并从子程序P(S)(S为文法的开始符号)开始，
如果中途没有产生错误，并且最后CH='#',则说明OrgStr串合法，否则该串不合法。

对每个非终结符写出不带回溯的递归子程序如下：
char CH;//存放当前的输入符号
void P_S()//非终结符S的子程序
{
if(CH==’a’) READ(CH);//产生式Sàa
else if(CH==’^’) READ(CH);//产生式Sà^
else if(CH==’(’)//产生式Sà(T)
{
READ(CH);
P_T();
IF (CH==’)’) THEN READ(CH) else ERROR
}
else ERR;
}
void P_T()//非终结符S的子程序
{
if(IsIn(CH,FIRST_SU)) //FIRST_SU为TàSU的右部的FIRST集合
{
P_S();
P_U();
}
}
void P_U()//非终结符U的子程序
{
if(CH==’,’)//产生式Uà，SU
{
READ(CH);
P_S();
P_U();
}
else//产生式Uàε
{
if(IsIn(CH,FOLLOW_U)) //FOLLOW_U为U的FOLLOW集合
return ;
else ERR;
}
}
(3)判断文法G/[S]是否为LL(1)文法。
各非终结符的FIRST集合如下：
FIRST(S)={a,∧,（}
FIRST(T)=FIRST(S)={a,∧,（}
FIRST(U)={，,ε}
各非终结符的FOLLOW集合如下：
FOLLOW(S)={#} ∪ FIRST(U) ∪ FOLLOW(T) ∪ FOLLOW(U)={#,，,)}
FOLLOW(T)={)}
FOLLOW(U)=FOLLOW(T)={)}
每个产生式的SELECT集合如下：
SELECT(Sàa)={a}
SELECT(Sà∧)={∧}
SELECT(Sà(T))={(}
SELECT(TàSU)=FIRST(S)={a,∧,（}
SELECT(Uà，SU)={，}
SELECT(Uàε)=FOLLOW(U)={)}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G/[S]是LL(1)文法。
文法G/[S]的预测分析表如下：

a
∧
(
)
，
#
S
àa
à∧
à(T)

T
àSU
àSU
àSU

U

àε
à，SU

(5) 给出输入串(a,a)#的分析过程
步骤
分析栈
剩余输入串
所用产生式
1
2
3
4
5
6
7
8
9
10
11
12
#S
#)T(
#)T
#)US
#)Ua
#)U
#)US,
#)US
#)Ua
#)U
#)
#
(a,a)#
(a,a)#
a,a)#
a,a)#
a,a)#
,a)#
,a)#
a)#
a)#
)#
)#
#
Sà(T)
( 匹配
TàSU
Sàa
a匹配
Uà，SU
,匹配
Sàa
a匹配
Uàε
)匹配
接受
2．对下面的文法G：
EàTE/
E/à+E|ε
TàFT/
T/àT|ε
FàPF/
F/à*F/|ε
Pà(E)|a|b|^
(1) 计算这个文法的每个非终结符的FIRST集和FOLLOW集。
(2) 证明这个方法是LL(1)的。
(3) 构造它的预测分析表。
(4) 构造它的递归下降分析程序。
解：
（1）计算这个文法的每个非终结符的FIRST集和FOLLOW集。
FIRST集合有：
FIRST(E)=FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(E/)={+,ε}
FIRST(T)=FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(T/)=FIRST(T)∪{ε}={(,a,b,^,ε};
FIRST(F)=FIRST(P)={(,a,b,^};
FIRST(F/)=FIRST(P)={*,ε};
FIRST(P)={(,a,b,^};
FOLLOW集合有：
FOLLOW(E)={),#};
FOLLOW(E/)=FOLLOW(E)={),#};
FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};//不包含ε
FOLLOW(T/)=FOLLOW(T)=FIRST(E/)∪FOLLOW(E)={+,),#};
FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};//不包含ε
FOLLOW(F/)=FOLLOW(F)=FIRST(T/)∪FOLLOW(T)={(,a,b,^,+,),#};
FOLLOW(P)=FIRST(F/)∪FOLLOW(F)={*,(,a,b,^,+,),#};//不包含ε
(2)证明这个方法是LL(1)的。
各产生式的SELECT集合有：
SELECT(EàTE/)=FIRST(T)={(,a,b,^};
SELECT(E/à+E)={+};
SELECT(E/àε)=FOLLOW(E/)={),#}
SELECT(TàFT/)=FIRST(F)={(,a,b,^};
SELECT(T/àT)=FIRST(T)={(,a,b,^};
SELECT(T/àε)=FOLLOW(T/)={+,),#};
SELECT(FàPF/)=FIRST(P)={(,a,b,^};
SELECT(F/à*F/)={*};
SELECT(F/àε)=FOLLOW(F/)={(,a,b,^,+,),#};
SELECT(Pà(E))={(}
SELECT(Pàa)={a}
SELECT(Pàb)={b}
SELECT(Pà^)={^}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[E]是LL(1)文法。
(3)构造它的预测分析表。
文法G[E]的预测分析表如下：

+
*
(
)
a
b
^
#
E

àTE/

àTE/
àTE/
àTE/

E/
à+E

àε

àε
T

àFT/

àFT/
àFT/
àFT/

T/
àε

àT
àε
àT
àT
àT
àε
F

àPF/

àPF/
àPF/
àPF/

F/
àε
à*F/
àε
àε
àε
àε
àε
àε
P

à(E)

àa
àb
à^

(4)构造它的递归下降分析程序。
对每个非终结符写出不带回溯的递归子程序如下：
char CH;//存放当前的输入符号
void P_E()//非终结符E的子程序
{
if(IsIn(CH,FIRST_TEP)) //FIRST_TEP为EàTE/ 的右部的FIRST集合，产生式EàTE/
{
P_T();
P_EP();
}
else ERR;
}
void P_EP()//非终结符E/的子程序
{
if(CH==’+’) //产生式E/à+E
{
READ(CH);
P_E();
}
else//产生式E/àε
{
if(IsIn(CH,FOLLOW_EP)) //FOLLOW_EP为E/的FOLLOW集合
return ;
else ERR;
}
}
void P_T()//非终结符T的子程序
{
if(IsIn(CH,FIRST_FTP)) //FIRST_ FTP为TàFT/ 的右部的FIRST集合，产生式TàFT/
{
P_F();
P_TP();
}
else ERR;
}
void P_TP()//非终结符T/的子程序
{
if(IsIn(CH,FIRST_T)) //FIRST_T为产生式T/àT 的右部的FIRST集合，产生式T/àT
{
P_T();
}
else//产生式T/àε
{
if(IsIn(CH,FOLLOW_TP)) //FOLLOW_TP为T/的FOLLOW集合
return ;
else ERR;
}
}
void P_F()//非终结符F的子程序
{
if(IsIn(CH,FIRST_PFP)) //FIRST_PFP为FàPF/ 的右部的FIRST集合，产生式FàPF/
{
P_P();
P_FP();
}
else ERR;
}
void P_FP()//非终结符F/的子程序
{
if(CH==’*’) //产生式F/à*F/
{
READ(CH);
P_FP();
}
else//产生式F/àε
{
if(IsIn(CH,FOLLOW_FP)) //FOLLOW_FP为F/的FOLLOW集合
return ;
else ERR;
}
}
void P_P()//非终结符P的子程序
{
if(CH==’(‘)
{
READ(CH);
P_E();
if(CH==’)’) READCH(CH);
else
ERR;
}
else if(CH==’a’) READ(CH);
else if(CH==’b’) READ(CH);
else if(CH==’^’) READ(CH);
else ERR;
}

3．已知文法G[S]：
SàMH|a
HàLSo|ε
KàdML|ε
LàeHf
MàK|bLM
判断G是否是LL（1）文法，如果是，构造LL（1）分析表。
解：
首先求各非终结符的FIRST集合：
FIRST(S)={a}∪FIRST(M)∪FIRST(H)={a}∪{b,d,ε}∪{e,ε}={a,b,d,e,ε};
FIRST(H)=FIRST(L)∪{ε}={e,ε};
FIRST(K)={d,ε};
FIRST(L)={e};
FIRST(M)=FIRST(K)∪{b}={b,d,ε};
然后求非终结符的FOLLOW集合：
FOLLOW(S)={o,#}
FOLLOW(H)=FOLLOW(S)∪{f}={f,o,#}
FOLLOW(K)=FOLLOW(M)=FIRST(H)∪FOLLOW(S)={e,o,#};//不包含ε
FOLLOW(L)=FIRST(S)∪{o}∪FOLLOW(K)∪FIRST(M)∪FOLLOW(M)
={a,b,d,e,o,#}∪FOLLOW(M)={a,b,d,e,o,#};//不包含ε
FOLLOW(M)=FIRST(L)∪FIRST(H)∪FOLLOW(S)={e,o,#}//不包含ε
最后求各产生式的SELECT集合：
SELECT(SàMH)=(FIRST(MH)-{ε})∪FOLLOW(S)={b,d,e}∪{o,#}={b,d,e,o,#};
SELECT(Sàa)={a}

SELECT(HàLSo)={e}
SELECT(Hàε)=FOLLOW(H)={f,o,#}

SELECT(KàdML)={d}
SELECT(Kàε)=FOLLOW(K)={e,o,#}

SELECT(LàeHf)={e}

SELECT(MàK)=(FIRST(K)-{ε})∪FOLLOW(M)={d,e,o,#}
SELECT(MàbLM)={b}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G[S]是LL(1)文法。
文法G[E]的预测分析表如下：

a
o
d
e
f
b
#
S
àa
àMH
àMH
àMH

àMH
àMH
H

àε

àLSo
àε

àε
K

àε
àdML
àε

àε
L

àeHf

M

àK
àK
àK

àbLM
àK

7．对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法？试对下面方法进行改写，并对改写后的文法进行判断。
(1) AàbaB|ε
BàAbb|a

(2) AàaABe|a
BàBb|d
解：
对于一个文法若消除了左递归，提取了左公共因子后不一定为LL(1)文法。如果新的文法中无空产生式，则一定为LL(1)文法，如果有空产生式，则需要进行LL(1)判断才能决定新方法是否一定是LL(1)文法。

(1)
由于SELECT(AàbaB)={b},SELECT(Aàε)=FOLLOW(A)={b,#},两集合有交集,所以该文法不是LL(1)方法。
该文法已经消除了左递归，与左公共因子，一般来说是不能再改写了。但根据本文法的具体情况有以下改写：
用产生式AàbaB 与Aàε分别替换产生式BàAbb有：BàbaBbb|bb，提取这两个新产生式的左公共因子有：
BàbB/,B/àaBbb|b,这样改写后文法G/[A]为：
AàbaB|ε
BàbB/|a
B/àaBbb|b
每个产生式的SELECT集合为：
SELECT(AàbaB)={b}
SELECT(Aàε)=Φ
SELECT(BàbB/)={b}
SELECT(Bàa)={a}
SELECT(B/àaBbb)={a}
SELECT(B/àb)={b}
可见，相同左部产生式的SELECT集的交集均为空，所以文法G/[A]是LL(1)文法。

(2)
显然文法的第1，2个产生式的右部具有左公共因子a,而产生工BàBb具有左递归，因此文法可改写为：
AàaA/
A/àABe|ε
BàdB/
B/àbB/|ε
由于SELECT(A/àABe)={a},SELECT(A/àε)=FOLLOW(A/)=FOLLOW(A)=FIRST(B)∪{#}={d,#},交集为空。
而SELECT(B/àbB/={b},SELECT(B/àε)=FOLLOW(B/)=FOLLOW(B)={e},交集也为空。
而非终结符A与B都只有一个产生式，不存在求SELECT的交集问题。
所以改写后的方法为LL(1)文法。