《編譯原理》課后習題答案第5章

《編譯原理》課后習題答案第5章《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdf51題對文法G[S]S→a|∧|(T)T→T,S|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,a))對(((a,a),∧,(a)),aS(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)《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdf(((a,a),∧,(a)),S)(((a,a),∧,(a)),a)(2)改寫文法為：0)S→a1)S→∧2)S→(T)3)T→SN4)N→,SNN→ε非終結(jié)符FIRST集FOLLOW集S{a,∧,(}{#,,,)}T{a,∧,(}{)}N{,,ε}{)}NFIRST（SN）={，F(xiàn)IRST（→ε）={ε}FOLLOW（N）={)}由于SELECT(N→,SN)∩SELECT(N→ε)={，}∩{)}=所以文法是LL(1)的。預測分析表（PredictingAnalysisTable）STNa→a→SN∧(),#→∧→SN→(T)→SN→ε→,SN也可由預測分析表中無多重入口判定文法是LL(1)的。(3)對輸入串（a,a）#當前輸入符（CUR_CHAR）((aaa,,剩余輸入符（INOUT_STRING）a,a)#a,a)#,a)#,a)#,a)#a)#a)#棧（STACK）#S#)TT#)NS#)Na#)N#)NS,所用產(chǎn)生式（ON）S→(T)T→SNS→aN→,SN《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdfa)#S→aa)#)#N→ε)##是文法的句子。#)NS#)Na#)N#)#可見輸入串（a,a）#《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdf3題已知文法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLMGLL(1)LL(1)分析表。答案：0）S→MH1）S→a2）H→LSo3）H→ε4）K→dML5）K→ε6）L→eHf7）M→K8）M→bLM非終結(jié)符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{d,ε}{e,#,o}對相同左部的產(chǎn)生式可知：SELECT(S→MH)∩SELECT(S→a)={d,b,e，#,o}∩{a}=SELECT(H→LSo)∩SELECT(H→ε)={e}∩{#,f,o}=SELECT(K→dML)∩SELECT(K→ε)=2iaas6k∩{e,#,o}=SELECT(M→K)∩SELECT(M→bLM)={d，e,#,o}∩=所以文法是LL(1)的?！毒幾g原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdf預測分析表：Sa→ao→MHd→MHfb#→MH→MH→MHM→K→K→K→bLM→KH→ε→LSo→ε→εL→eHfK→ε→dML→ε→ε由預測分析表中無多重入口也可判定文法是LL(1)的?！毒幾g原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdf7題對于一個文法若消除了左遞歸，提取了左公共因子后是否一定為LL(1)文法?試對下面文法進行改寫，并對改寫后的文法進行判斷。(１)A→baB|εB→Abb|a(2)A→aABe|aB→Bb|d(3)S→Aa|bA→SBB→ab答案：(１)先改寫文法為：A→baB1A→ε2B→baBbb3B→bb4B→a0)A→baB1)A→ε2)B→bN3)B→a4)N→aBbb5)N→b預測分析表：→baB→εB→a→N→aBbb→由預測分析表中無多重入口判定文法是LL(1)的。（2）文法：A→aABe|aB→Bb|d提取左公共因子和消除左遞歸后文法變?yōu)椋?)A→aNN→ABe2)N→ε《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdf3)B→dN14)N1→bN15)N1→εFIRSTFOLLOWA{a{#,dB{d{e}N{a,ε}{#,d}N1{b,ε}{e}對相同左部的產(chǎn)生式可知：SELECT(N→ABe)∩SELECT(N→ε)={a}∩{#,d}=SELECT(N1→bN1)∩SELECT(N1→ε)=∩{e}=所以文法是LL(1)的。預測分析表（PredictingAnalysisTable）ABNa→aNeb→bN1d→dN1#→εN1→ε也可由預測分析表中無多重入口判定文法是LL(1)的。（3）文法：S→Aa|bA→SBB→ab1種改寫：ASAS→SBa|bB→ab0S→bN1N→BaN2N→ε3B→abFIRSTFOLLOW集《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdfS{#}B{a}{a}N{ε,a}{#}對相同左部的產(chǎn)生式可知：SELECT(N→BaN)∩SELECT(N→ε)={a}∩{#}=所以文法是LL(1)的。預測分析表（PredictingAnalysisTable）BNa→ab→BaNb→b#→εS也可由預測分析表中無多重入口判定文法是LL(1)2種改寫：SASS→Aa|bA→AaB|bBB→ab消除左遞歸后文法變?yōu)椋?)S→Aa1)S→b2)A→bBN3)N→aBN4)N→ε5)B→ab非終結(jié)符FIRST集FOLLOW集S{#}A{a}B{a}{a}N{a,ε}{a}對相同左部的產(chǎn)生式可知：SELECT(S→Aa)∩SELECT(S→b)=∩=≠SELECT(N→aBN)∩SELECT(N→ε)={a}∩{a}={a}≠所以文法不是LL(1)的?！毒幾g原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdf預測分析表：BNa→ab→aBN→εb→Aa→b→bB#SALL(15《編譯原理》課后習題答案第5章.pdf附加題CPASCAL語言寫出其遞歸下降子G[A]:A→[BB→X]{A}X→(a|b){a|b}答案：不妨約定:在進入一個非終結(jié)符號相應的子程序前，已讀到一個單詞.word：存放當前讀到的單詞，Getsym()為一子程序，每調(diào)用一次，完成讀取一單詞的工作。AFIRSTCvoidA()B()voidX(){{X();{ifword=='['word==']'if(word=='a'||word=='b'){{{Getsym();Getsym();Getsym();while(word=='a'||word=='b')FIRST(A))}Getsym();elseerror();A();}}}elseerror();elseerror();}}問題2：設(shè)有文法G[A]的產(chǎn)生式集為:A→BaC|CbBB→Ac|cC→Bb|b試消除G[A]的左遞歸。答案：A、、C排序.ABBA、BC中。再消除C:G[A]:A→BaC|CbBB→CbBcB'|cB'B'→aCcB'|εC→cB'bC'|bC'C'→bBcB'bC'|ε《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdf問題3：G[E]LL(1)文法E[FEEEεFaFFεE,F,E’,F’各非終結(jié)符的FIRST集和FOLLOW集如下：FIRST（E）={[}FOLLOW（E）={＃}FIRST（E′）={[，ε}FOLLOW（E′）={＃}FIRST（F）={a}FOLLOW（F）={]}FIRST（F′）={a，ε}FOLLOW（F′）={]}EEε，F(xiàn)IRST(E)FIRST(ε)φFIRST(EFOLLOW（E’）φFaFε，F(xiàn)IRST(aF’)FIRST(ε)φFIRST（aF’）∩FOLLOW（F’）φ所以,G[E]LL（1）4：G[E]LL(1)文法E[FEEEεFaFFaFε其中E,F,E’,F’為非終結(jié)符。對文法G[E]構(gòu)造遞歸下降分析程序。答案：/*用類C語言寫出G[E]的遞歸子程序，其中yylex()為取下一單詞過程，變量lookahead存放當前單詞。*/intlookahead;《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdfvoidParseE(){MatchToken(′[′);ParseF();MatchToken(′]′);ParseE’();}voidParseE’(){switch(lookahead){case′[′:ParseE();break;case′#′:break;default:printf(“syntaxerror\n")exit(0);}}voidParseF(){MatchToken(′a′);ParseF’();}voidParseF’(){switch(lookahead){case′a′:MatchToken(′a′);ParseF’();break;case′]′:break;default:printf("syntaxerror\n")exit(0);}}《編譯原理》課后習題答案第5章.pdf《編譯原理》課后習題答案第5章.pdfvoidMatchToken(intexpected){if(lookahead!=expected)//判別當前單詞是否與期望的終結(jié)符匹配{printf("syntaxerror\n");exit(0);}else//若匹配,消費掉當前單詞并讀入下一個調(diào)用詞法分析程序lookaheadyylex();}5：文法G[E]是LL(1)文法:E→[F]E′E’→EεF→aF’F’→aF’ε其中E,F,E’,F’G[E]LL(1)分析表。答案：aEE’FF’[E-[F]E’E’-E]#E’-εF-aF’F’-aF’-ε5章.pdf5章.pdf問題6：試消除下面文法G[A]中的左遞歸和左公因子，并判斷改寫后的文法是否為LL(1)文法?G[A]：A→aABeaB→Bbd答案：提取左公共因子和消除左遞歸后，G［A］變換為等價的G′［A］如下：A→aA′A′→ABe|