资源描述：
《习题与答案-5-语法分析-自上而下.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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=>(T)=>(T,S)=>(S,S)S(T)Sa=>((T),S
5、)=>((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,(T,S))=>(((a,a),^,(S)),S)=>(a,(S,S))T,S=>(((a,a),^,(a)),S)=>(a,(
6、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=’^’thenelsegetsymerror;elseifsym=’(‘end;begingetsym;proceduceT’;T;beginIfsym=’)’thenifsym=’,’thenGetsym
10、;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',εFOLLOW(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' →ε→,
11、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)#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#)
12、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’#出错^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^2.G:E→TE'E'→+E
13、εT→FT'T'→T
14、εF→PF'F'→*F'
15、εP→(E)
16、a
17、b
18、∧2.[解答]可推出εFIRST集FIRST集ENFIRST(T)(ab∧E'Y+ε+εTNFIRST(F)(ab∧T'YFIRST(T)∪{ε}(ab∧εFNFIRST(P)(ab
19、∧F'Y*ε*εPN(ab∧(ab∧FOLLOW集FOLLOW集E{#}∪FOLLOW(E')∪{)}#)E'FOLLOW(E)#)TFIRST(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'FIRST(F)(ab
