资源描述:
《习题与答案-5-语法分析-自上而下》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、第五章^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^1.对文法G[S]G: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.[解答](1)①S②S(T)(T)T,ST,S②S
5、=>(T)=>(T,S)=>(S,S)S(T)Sa=>((T),S)=>((T,S),S)aT,S(T)=>((T,S,S),S)=>((S,S,S),S)SaT,S=>(((T),S,S),S)=>(((T,S),S,S),S)aT,S(T)=>(((S,S),S,S),S)=>(((a,S),S,S),S)①S=>(T)=>(T,S)S^S=>(((a,a),S,S),S)=>(S,S)=>(a,S)=>(((a,a),^,S),S)=>(a,(T))(T)a=>(((a,a),^,(T)),S)=>(a,(
6、T,S))=>(((a,a),^,(S)),S)=>(a,(S,S))T,S=>(((a,a),^,(a)),S)=>(a,(a,S))=>(((a,a),^,(a)),a)=>(a,(a,a))Saa(2)消除左递归G':S→a
7、∧
8、(T)T→ST'T'→,ST'
9、ε递归子程序:programparserproceduceT;beginbegingetsym;ifsymin[a,^,()thenSbeginend;S;第五章proceduceS;T;beginend;ifsym=’a’orsym=’^’then
10、elsegetsymerror;elseifsym=’(‘end;begingetsym;proceduceT’;T;beginIfsym=’)’thenifsym=’,’thenGetsym;beginElsegetsym;Error;S;End;T;Elseend;Error;elseEnd;ifsym=’)’thenelseerror;end;(3)FIRST集FOLLOW集Sa∧({#}∪FIRST(T')/{ε}∪FOLLOW(T)∪FOLLOW(T')#,)TFIRST(S)a∧())T',εFOLL
11、OW(T)∪FOLLOW(T'))FIRST集FOLLOW集Sa∧(#,)Ta∧()T',ε)SELECT集合S→aaS→∧∧S→(T)(T→ST'a∧(T'→,ST',T'→ε) a∧(),#S→a→∧→(T)T→ST'→ST'→ST'T' →ε→,ST' 预测分析表不含多重定义入口,所以该文法是LL(1)文法!(4)分析栈余留串所用产生式或动作第五章1#S(a,a)#S—>(T)2#)T((a,a)#(匹配3#)Ta,a)#T—>ST’4#)T’Sa,a)#S—>a5#)T’aa,a)#a匹配6#)T’,a)
12、#T’—>,ST’7#)T’S,,a)#,匹配8#)T’Sa)#S—>a9#)T’aa)#a匹配10#)T’)#T’—>ε11#))#)匹配12##接受因为(a,a)#分析成功所以(a,a)为文法的句子步骤分析栈余留串所用产生式或动作1#S(a,a#S→(T)2#)T((a,a#(匹配3#)Ta,a#T→ST’4#)T’Sa,a#S→a5#)T’aa,a#a匹配6#)T’,a#T’→,ST’7#)T’S,,a#,匹配8#)T’Sa#S→a9#)T’aa#a匹配10#)T’#出错第五章^^^^^^^^^^^^^^^
13、^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2.G:E→TE'E'→+E
14、εT→FT'T'→T
15、εF→PF'F'→*F'
16、εP→(E)
17、a
18、b
19、∧2.[解答]可推出εFIRST集FIRST集ENFIRST(T)(ab∧E'Y+ε+εTNFIRST(F)(ab∧T'YFIRST(T)∪{ε}(ab∧εFNFIRST(P)(ab∧F'Y*ε*εPN(ab∧(ab∧FOLLOW集FOLLOW集E{#}∪FOLLOW(E')∪{)}#)E'FOLLOW(E)#)T
20、FIRST(E')/{ε}∪FOLOW(E)∪FOLOW(T')+#)T'FOLLOW(T)+#)FFIRST(T')/{ε}∪FOLOW(T)(ab∧+#)F'FOLLOW(F)(ab∧+#)PFIRST(F')/{ε}∪FOLOW(F)*(ab∧+#) SELECT集SELECT集E→TE'FIRST(T)(ab∧E'→+E++E'→εFOLLOW(E')#)T→FT