编译原理第二版张素琴著第五章习题参考答案.doc

第五章 习题参考答案1、(1) 对(a,(a,a)的最左推导为：S(T) (T,S) (S,S) (a,S) (a,(T) (a,(T,S) (a,(S,S)(a,(a,S)(a,(a,a) 对(a,a),(a),a) 的最左推导为：S(T) (T,S)(S,S) (T),S)(T,S),S) (T,S,S),S)(S,S,S),S) (T),S,S),S)(T,S),S,S),S)(S,S),S,S),S)(a,S),S,S),S) (a,a),S,S),S) (a,a),S),S) (a,a),(T),S) (a,a),(S),S) (a,a),(a),S) (a,a),(a),a)对( a, a ), , ( a ), a )的最左推导为：S ( T ) ( T, S ) ( S, S ) ( T ), S ) ( T, S ), S ) ( T, S, S ), S ) ( S, S, S ), S ) ( T ), S, S ), S ) ( T, S ), S, S ), S ) ( S, S ), S, S ), S ) ( a, S ), S, S ), S ) ( a, a ), S, S ), S ) ( a, a ), , S ), S ) ( a, a ), , ( T ), S ) ( a, a ), , ( S ), S ) ( a, a ), , ( a ), S ) ( a, a ), , ( a ), a )对( a, a ), , ( a ), a )的最左推导为：S ( T ) ( T, S ) ( T, a ) ( S, a ) ( T ), a ) ( T, S ), a ) ( T, ( T ), a ) ( T, ( S ), a ) ( T, ( a ), a ) ( T, S, ( a ), a ) ( T, , ( a ), a ) ( S, , ( a ), a ) ( T ), , ( a ), a ) ( T, S ), , ( a ), a ) ( T, a ), , ( a ), a ) ( S, a ), , ( a ), a ) ( a, a ), , ( a ), a ) (2) 改写文法为： 0) Sa 1) S 2) S( T ) 3) TS N4) N, S N5) N 入口入口入口S: T:N: ，YNNSNYaRead(w)YNNS出口N出口Y(出错Read(w)TN)Read(w)出口(3)非终结符FIRST集FOLLOW集Sa,(#,)Ta,().N,.).对左部为N的产生式可知：SELECT(Sa)SELECT(S) SELECT(S( T )=SELECT(N , S N)SELECT(N ) =， )=所以文法是LL(1)的。 预测分析表a(),#Sa(T)TS NS NS NN, S N也可由预测分析表中无多重入口判定文法是LL(1)的。(4) 对输入串（a,a）#的分析过程为：栈（STACK）当前输入符（CUR_CHAR）剩余输入符（INOUT_STRING）所用产生式（OPERATION）#S #)T(#)T #)NS #)Na#)N#)NS,#)NS #)Na#)N#)#(aaa,aa)#a,a)#.a,a)#.,a)#.,a)#.,a)#.a)#.a)#.)#.)#.#.#.S(T).TSNSa.N,SN.Sa.N可见输入串（a,a）#是文法的句子。6.(2) 不是LL(1)文法以A的产生式代入S，以D的产生式代入B中，提取左公共因子并删除多余产生式得文法：SBCCaB|BdF|FFb|分析表为abd#SBCBCBCBCBFFdFFCaBFb结论：经改写之后的文法是（）文法。递归下降分析器如同题1，从略6.(4)消除左递归为：SiS(E)ESFF+SFF-SFF分析表为：+-i()ESFSFF+SF-SFSi(E)结论：经改写之后的文法是（）文法。递归下降分析器如同题1，从略7.(1)文法不存在左递归第一种改法：以A的产生式替入B 产生式中BbaBbbBbbBa消除左公共因子：BbCCaBbbCbBa改写之后的文法的分析表：ab#BabCCaBbbb改写之后的文法是LL(1)文法第二种改法：以B的产生式替入A产生式中AbaAbbAbaaA消除左公共因子后为AAbaCCAbbCaSELECT(AbaC) SELECT(A) = b # ,b 所以，改写之后的文法不是LL(1)文法7.(3)第1种改写：用A的产生式右部代替S的产生式右部的A得： SSBa|bBab消除左递归后文法变为： 0) Sb N1) NB a N2) N3) Ba b 非终结符FIRST集FOLLOW集Sb.#Ba.aN,a#SELECT(NB a N)SELECT(N) = a # =所以文法是LL(1)的。预测分析表ab#Sb NBa bNB a N第2种改写：用S的产生式右部代替A的产生式右部的S得： SAa|bAAaB|bBBab 消除左递归后文法变为： 0) SA a 1) Sb 2) Ab B N3) Na B N4) N 5) Ba b非终结符FIRST集FOLLOW集Sb.#Ab.aBa.aNa,aSELECT(SA a)SELECT(Sb) = b b = b SELECT(Na B N)SELECT(N) = a a = a 所以文法不是LL(1)的。7.(5)以A、B的产生式代入S的产生式中的A、B，得新文法：SaCCAb|b|aAaA|a以A的产生式代入C中提取左公共因子得：SaCCaD|bDAb|b|AaA|a以A的产生式代入