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

时间：2026-01-20

第五章自顶向下语法分析方法

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,则算法中的语句

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]的预测分析表如下：

(5) 给出输入串(a,a)#的分析过程

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]的预测分析表如下：

(4)构造它的递归下降分析程序。

对每个非终结符写出不带回溯的递归子程序如下： char CH;//存放当前的输入符号 void P_E()//非终结符E的子程序 {

/ /

if(IsIn(CH,FIRST_TEP)) //FIRST_TEP为E TE的右部的FIRST集合，产生式E TE { P_T(); P_EP(); }