编译原理习题解答 页1/1
第五章 自顶向下语法分析方法
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)为相应的子程序。
BEGIN END
P(y1); P(y2); ... P(yn);
(3) 对于符号串x=y1y2...yn;p(x)的含义为：
如果yi是非终结符，则P(yi)代表调用处理yi的子程序； 如果yi是终结符，则P(yi)为形如下述语句的一段子程序
IF CH=yi THEN READ(CH) ELSE ERROR
即如果当前文法中的符号与输入符号匹配，则继续读入下一个待输入符号到CH中， 否则表明出错。
IF CH IN FIRST(xn) THEN P(xn)
(4) 如果文法中有空规则U::=EPSILON,则算法中的语句
编译原理习题解答 页2/2
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集合如下：
编译原理习题解答 页3/3
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]的预测分析表如下：
S T U
(5) 给出输入串(a,a)#的分析过程
步骤 1 2 3 4 5 6 7 8 9 10 11 12 2．对下面的文法G：
E?TE
/
/ /
/
a ?a ?SU ∧ ?∧ ?SU ( ?(T) ?SU ) ?ε ， ?，SU # 分析栈 #S #)T( #)T #)US #)Ua #)U #)US, #)US #)Ua #)U #) # 剩余输入串 所用产生式 (a,a)# S?(T) (a,a)# ( 匹配 a,a)# T?SU a,a)# S?a a,a)# a匹配 ,a)# U?，SU ,a)# ,匹配 a)# S?a a)# a匹配 )# U?ε )# )匹配 # 接受 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,^,ε};
//