资源描述：
《第5章作业参考答案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第5章自顶向下语法分析方法1．对文法G[S]S→a
2、∧
3、(T)T→T,S
4、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,S)=>(a,(T))=>(a,(T,S))=>(a,(S,S))=>(a,(a,S))=>(a,(a
5、,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)(
6、2)改写文法为：S→a
7、∧
8、(T)T→SNN→,SN
9、ε非终结符FIRST集FOLLOW集S{a,∧,(}{#,,,)}T{a,∧,(}{)}N{,,ε}{)}对左部为S的产生式可知：Select（S→a）∩Select（S→∧）∩Select（S→(T)）={a}∩{∧}∩{(}=φ对左部为N的产生式可知：FIRST（,SN）={,}FIRST（ε）={ε}FOLLOW（N）={)}由于SELECT(N→,SN)∩SELECT(N→ε)={,}∩{)}=φ所以文法是LL(1)的。预测分析表:也可由预测分析表中无多重入口判定文法是LL(1
10、)的。(3)对输入串（a,a）#的分析过程为：可见输入串（a,a）#是文法的句子。2.对下面的文法G:E->TE’E’->+E
11、εT->FT’T’->T
12、εF->PF’F’->*F’
13、εP->(E)
14、a
15、b
16、∧（1）计算这个文法每个非终结符的FIRST和FOLLOW集。（2）证明这个文法是LL(1)文法。（3）构造它的预测分析表。答案：（1）非终结符FIRST集FOLLOW集E{(,a,b,∧}{#,)}E’{+,ε}{#,)}T{(,a,b,∧}{+,#,)}T’{(,a,b,∧,ε}{+,#,)}F{(,a,b,∧}{(,a,b,∧,
17、+,#,)}F’{*,ε}{(,a,b,∧,+,#,)}P{(,a,b,∧}{*,(,a,b,∧,+,#,)}(2)要证明这个文法是LL(1)文法，只要证明同一左部的多个产生式的select无交集。对左部为E’的产生式可知：First(+E)={+}First(ε)={ε}Follow(E’)={#,)}Select(E’->+E)∩SELECT(E’->ε)={+}∩{#,)}=φ对左部为T’的产生式可知：First(T)={(,a,b,∧}First(ε)={ε}Follow(T’)={+,#,)}Select(T’->T)∩SELE
18、CT(E’->ε)={(,a,b,∧}∩{+,#,)}=φ对左部为F’的产生式可知：First(*F’)={*}First(ε)={ε}Follow(F’)={(,a,b,∧,+,#,)}Select(F’->*F’)∩SELECT(F’->ε)={*}∩{(,a,b,∧,+,#,)}=φ所以文法是LL(1)的.(3)预测分析表 ab+*∧()#EE->TE’E->TE’ E->TE’E->TE’ E' E’->+E E’->εE’->εTT->FT’T->FT’ T->FT’T->FT’ T'T’->TT’->TT’->ε
19、 T’->TT’->TT’->εT’->εFF->PF’F->PF’ F->PF’F->PF’ F'F’->εF’->εF’->εF’->*F’F’->εF’->εF’->εF’->εPP->aP->b P->∧P->(E) 3.已知文法G[S]：S→MH
20、aH→LSo
21、εK→dML
22、εL→eHfM→K
23、bLM判断G是否是LL(1)文法，如果是，构造LL(1)分析表。答案：非终结符FIRST集FOLLOW集S{a,d,b,ε,e}{#,o}M{d,ε,b}{e,#,o}H{ε,e}{#,f,o}L{e}{a,d,b,e,o,#}K
24、{d,ε}{e,#,o}对相同左部的产生式可知：SELECT(S→MH)∩SELECT(S→a)={d,b,e，#,o}∩{a}=φSELECT(H→LSo)∩SELECT(H→ε)={e}∩
