编译原理习题解答 页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,^,ε};
//
编译原理习题解答 页4/4
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]的预测分析表如下：
E E T T F F P
(4)构造它的递归下降分析程序。
对每个非终结符写出不带回溯的递归子程序如下： char CH;//存放当前的输入符号 void P_E()//非终结符E的子程序 {
/ /
if(IsIn(CH,FIRST_TEP)) //FIRST_TEP为E?TE的右部的FIRST集合，产生式E?TE { P_T(); P_EP(); }
////
/
/
//
/
/
/
/
/
/
/
/
/
/
/
/
/
/
/
//
+ ?+E ?ε ?ε * ?*F /( ?TE ?FT ?T ?PF ?ε ?(E) ///) ?ε ?ε ?ε a ?TE ?FT ?T ?PF ?ε ?a ///b ?TE ?FT ?T ?PF ?ε ?b ///^ ?TE ?FT ?T ?PF ?ε ?^ ///# ?ε ?ε ?ε 编译原理习题解答 页5/5
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; }
(完整版)编译原理第五章作业参考答案
