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

更新时间：2023-11-20 02:31:01 阅读量：教育文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

编译原理第五章课后题答案推荐度：
相关推荐

编译原理习题解答页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; }

编译原理习题解答页6/6

}

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 H ?ε ?LSo ?ε K ?ε ?dML ?ε # ?MH ?ε ?ε 编译原理习题解答页7/7 L M ?K ?K ?eHf ?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}