资源描述：
《编译原理第二版张素琴著第五章习题参考答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第五章习题参考答案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
2、) (((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)
3、,Ù,(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)S→a
4、 1)S→∧ 2)S→(T) 3)T→SN 4)N→,SN 5)N→ε入口入口入口S:T:N:，YNNSNYaRead(w)Y^NNS出口N出口Y(出错Read(w)TN)Read(w)出口(3)非终结符FIRST集FOLLOW集S{a,∧,(}{#,,,)}T{a,∧,(}{)}....N{,,ε}.{)}....对左部为N的产生式可知： SELECT(S→a)∩SELECT(S→∧)∩SELECT(S→(T))= SELECT(N→,SN)∩SELECT(N→ε)={，}∩{)}= 所以文法是LL(1)的。预测分析表 a∧()
5、,#S→a→∧→(T) T→SN→SN→SN N →ε→,SN 也可由预测分析表中无多重入口判定文法是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).T→SNS→a.
6、N→,SN.S→a.N→ε可见输入串（a,a）#是文法的句子。6.(2)不是LL(1)文法以A的产生式代入S，以D的产生式代入B中，提取左公共因子并删除多余产生式得文法：S→BCC→aB
7、εB→dF
8、FF→b
9、ε分析表为abd#SBCBCBCBCBFFdFFCaBεFεbε结论：经改写之后的文法Ｇ是ＬＬ（１）文法。递归下降分析器如同题1，从略6.(4)消除左递归为：S→iS→(E)E→SFF→+SFF→-SFF→ε分析表为：+-i()﹟ESFSFF+SF-SFεSi(E)结论：经改写之后的文法Ｇ是ＬＬ（１）文法。递归下降分析器如同题1，从略7.(
10、1)文法不存在左递归第一种改法：以A的产生式替入B产生式中B→baBbbB→bbB→a消除左公共因子：B→bCC→aBbbC→bB→a改写之后的文法的分析表：ab#BabCCaBbbb改写之后的文法是LL(1)文法第二种改法：以B的产生式替入A产生式中A→baAbbA→baaA→ε消除左公共因子后为A→εA→baCC→AbbC→aSELECT(A→baC)∩SELECT(A→ε)={b}∩{#,b}≠所以，改写之后的文法不是LL(1)文法7.(3)第1种改写：用A的产生式右部代替S的产生式右部的A得： S→SBa
11、b B→ab 消除左递归后
12、文法变为： 0)S→bN 1)N→BaN 2)N→ε 3)B→ab非终结符FIRST集FOLLOW集S{b}...{#}B{a}
