編譯原理復(fù)習(xí)題2

ET*F二、觀點題1、設(shè)有文法：P→P+Q|QQ→Q*R|RR→(P)|i1）證明Q*R+Q+Q是它的一個句型。（3分)2）給出Q*R+Q+Q的全部短語，直接短語和句柄。(4分)3）給出句子ｉ+ｉ*ｉ的最右推導(dǎo)。(4分)4）給出句子ｉ+ｉ*ｉ的最左推導(dǎo)。(4分)2、設(shè)有文法：E→E+T|TT→T*F|FF→(E)|i（1）證明E+T*F是它的一個句型。（3分)答案：EET（2）給出E+T*F的全部短語，直接短語和句柄。(4分)短語:E+T*F,T*F,直接短語:T*F句柄:T*F（3）給出句子ｉ+ｉ*ｉ的最右推導(dǎo)。(4分)3、寫出表達式a+b*(c-d)對應(yīng)的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+)三元式序列:OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)三、詞法剖析題給出下邊語言的相應(yīng)文法L1={anbnambm|n,m≥0}答案：S→AB|A|B|∑A→aAb|abB→aBb|ab給出下邊語言的相應(yīng)文法L2={anbnci|n≥1,i≥0}答案：S→AB|BA→a|aAB→bBc|bc給出下邊語言的相應(yīng)文法L3={anbncm|m,n≥1，n為奇數(shù)，m為偶數(shù)}。答案：文法G(S):S→ACA→aaAbb/abC→ccCcc/cc四、詞法剖析題1、結(jié)構(gòu)下邊正規(guī)式相應(yīng)的DFA((0|1)*|(11)*)*（要求：先將正規(guī)式轉(zhuǎn)變?yōu)镹FA，再將NFA確立化，最小化）2、結(jié)構(gòu)下邊正規(guī)式相應(yīng)的DFA1(0|1)*101答案：II0I1{X}Ф{A,B,C}{A,B,C}{B,C}{B,C,D}{B,C}{B,C}{B,C,D}{B,C,D}{B,C,E}{B,C,D}{B,C,E}{B,C}{B,C,D,y}{B,C,D,y}{B,C,E}{B,C,D}3、結(jié)構(gòu)一個DFA，它接受={a，b}上全部包括ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)變?yōu)镹FA，再將NFA確立化，最小化）答案：(一)相應(yīng)的正規(guī)式為(a|b)*ab(a|b)*(二)①與此正規(guī)式對應(yīng)的NFA為②狀態(tài)變換矩陣為：③最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}baaab013b④所以此等價的DFA為：開始狀態(tài)為0，終態(tài)集為{3}，狀態(tài)集為{0,1,3}，輸入字母表是{a,b}狀態(tài)變換圖如上。4、結(jié)構(gòu)與正規(guī)式b(a|b)*ba等價的DFA五、語法剖析題1、對下邊的文法G:Expr→-ExprExpr→(Expr)|VarExprTailExprTail→-Expr|εVar→idVarTailVarTail→(Expr)|ε1）結(jié)構(gòu)LL(1)剖析表。（12分）答案：（1）FIRST(Expr)={_,(,id}FIRST(ExprTail)={_,ε}FIRST(Var)={id}FIRST(VarTail)={(ε,}FOLLOW(Expr)={#,)}FOLLOW(ExprTail)={#,)}FOLLOW(Var)={_,#,)}FOLLOW(VarTail)={_,#,)}（2）給出對句子id—id((id))的剖析過程。（8分）步驟符號棧輸入串所用產(chǎn)生式0＃Exprid__id((id))＃1#ExprTailVarid__id((id))＃Expr→VarExprTail2#ExprTailVarTailidid__id((id))＃Var→idVarTail3#ExprTailVarTail__id((id))＃4#ExprTail__id((id))＃VarTail→ε5#Expr___id((id))＃ExprTail→_Expr6#Expr_id((id))＃7#Expr__id((id))＃Expr→_Expr8#Exprid((id))＃9#ExprTailVarid((id))＃Expr→VarExprTail10#ExprTailVarTailidid((id))＃Var→idVarTail11#ExprTailVarTail((id))＃12#ExprTail)Expr(((id))＃VarTail→(Expr)13#ExprTail)Expr(id))＃14#ExprTail))Expr((id))＃Expr→(Expr)15#ExprTail))Exprid))＃16#ExprTail))ExprTailVarid))＃Exp→VarExprTail17#ExprTail))ExprTailVarTailidid))＃Var→idVarTail18#ExprTail))ExprTailVarTail))＃19#ExprTail))ExprTail))＃VarTail→ε20#ExprTail))))＃ExprTail→ε21#ExprTail))＃22#ExprTail#ExprTail→ε23##剖析成功2、對下邊的文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧（1）計算這個文法的每個非終結(jié)符的FIRST和FOLLOW。（8分）答案：FIRST(E)={(,a,b,^}FIRST(E')={+,ε}FIRST(T)={(,a,b,^}FIRST(T')={(,a,b,^,ε}FIRST(F)={(,a,b,^}FIRST(F')={*,ε}FIRST(P)={(,a,b,^}FOLLOW(E)={#,)}FOLLOW(E')={#,)}FOLLOW(T)={+,),#}FOLLOW(T')={+,),#}FOLLOW(F)={(,a,b,^,+,),#}FOLLOW(F')={(,a,b,^,+,),#}FOLLOW(P)={*,(,a,b,^,+,),#}（2）證明這個文法是LL(1)的。（6分）答案：考慮以下產(chǎn)生式:EE|TT|F*F|P(E)|^|a|bFIRST(+E)∩FIRST(ε)={+}∩{ε}=φFIRST(+E)∩FOLLOW(E')={+}∩{#,)}=φFIRST(T)∩FIRST(ε)={(,a,b,^}∩{ε}=φFIRST(T)∩FOLLOW(T')={(,a,b,^}∩{+,),#}=φFIRST(*F')∩FIRST(ε)={*}∩{ε}=φFIRST(*F')∩FOLLOW(F')={*}∩{(,a,b,^,+,),#}=φFIRST((E))∩FIRST(a)∩FIRST(b)∩FIRST(^)=φ所以,該文法式LL(1)文法.（3）結(jié)構(gòu)它的展望剖析表。（6分）3、已知文法G[S]為：S->a|(T)T->T,S|S①除去文法G[S]中的左遞歸，得文法G′[S]。②文法G′[S]能否為LL(1)的假如，給出它的展望剖析表。4、對下邊的文法G:SSaT|aT|aTTaT|a除去該文法的左遞歸和提取左公因子；結(jié)構(gòu)各非終結(jié)符的FIRST和FOLLOW會合；結(jié)構(gòu)該文法的LL(1)剖析表，并判斷該文法是不是LL(1)的。答案：5、文法G(S)及其LR剖析表以下，請給出串baba#的剖析過程。(1)S→DbB(2)D→d(3)D→ε(4)B→a(5)B→Bba(6)B→εLR剖析表ACTIONGOTObDa#SBD0r3s3121accs4r24r6S5r665r4r46s7r17S88r5r5答案：步驟狀態(tài)符號輸入串00#baba#102#Dbaba#2024#Dbaba#30245#Dbaba#40246#DbBba#502467#DbBba#6024678#DbBba#70246#DbB#801#S#acc六、語法剖析題考慮文法:S→AS|bA→SA|a1）列出這個文法的全部LR(0)項目。（5分）答案0.SS1.SS2.SAS3.SAS4.SAS5.Sb6.Sb

7.ASA8.ASA9.ASA10.Aa11.Aa2）給出辨別文法全部活前綴的DFA。（5分）3）求全部非終結(jié)符的FOLLOW集。（5分）4）文法是SLR文法嗎假如，結(jié)構(gòu)出它的SLR剖析表,不然說明原因。5分）不是SLR文法狀態(tài)3，6，7有移進歸約矛盾狀態(tài)3：FOLLOW(S’)={#}不包括a,b狀態(tài)6：FOLLOW(S)={#,a,b}包括a,b,；移進歸約矛盾沒法消解狀態(tài)7：FOLLOW(A)={a,b}包括a,b；移進歸約矛盾消解所以不是SLR文法。七、證明題1、證明下邊文法是LL(1)的但不是SLR(1)的。S→AaAb|BbBaA→εB→ε第一該文法無左遞歸存在,沒有公共左因子。其次:關(guān)于S→AaAb|BbBaFIRST(AaAb)={a}FIRST(BbBa)=FIRST(AaAb)∩FIRST(BbBa)=Φ所以該文法是LL(1)文法。(2)證明該文法不是SLR的。文法的LR(0)項目集規(guī)范族為:I0={S’→.SS→.AaAbS→.BbBaA→.B→.}I1={S’→S.}I2={S→}I3={S→}I4={S→A→.}I5={S→B→.}I6={S→}I7={S→}I8={S→AaAb.}I9={S→BbBa.}觀察I0:FOLLOW(A)={a,b}FOLLOW(B)={a,b}FOLLOW(A)∩FOLLOW(B)={a,b}產(chǎn)生規(guī)約-規(guī)約矛盾。所以該文法不是SLR(1)文法。2、證明下邊文法是SLR(1)但不是LR(0)的。S→AA→Ab|bBaB→aAc|a|aAb解：文法G[S]：0：S→A1：A→Ab2：A→bBa3：B→aAc4：B→a5：B→aAb結(jié)構(gòu)LR(0)項目集規(guī)范族：狀態(tài)項目集變換函數(shù)0S→·AGO[0，A]＝1A→·AbGO[0，A]＝1A→·bBaGO[0，b]＝21S→A·ACCEPTA→A·bGO[1，b]＝32A→b·BaGO[2，B]＝4B→·aAcGO[2，a]＝5B→·aGO[2，a]＝5B→·aAbGO[2，a]＝53A→Ab·R14A→bB·aGO[4，a]＝65→a·Ac，A]＝7BGO[5B→a·R4B→a·AbGO[5，A]＝7A→·AbGO[5，A]＝7A→·bBaGO[5，b]＝26A→bBa·R27B→aA·cGO[7，c]＝8B→aA·bGO[7，b]＝9A→A·bGO[7，b]＝98B→aAc·R39→·R5BaAbA→Ab·R1狀態(tài)5存在“歸約－移進”矛盾，狀態(tài)9存在“歸約－歸約”矛盾，所以該文法不是LR(0)文法。狀態(tài)5：FOLLOW(B)＝｛a｝，所以，F(xiàn)OLLOW(B)∩｛b｝＝Φ狀態(tài)9：FOLLOW(B)＝｛a｝，F(xiàn)OLLOW(A)＝｛#，b，c｝，所以FOLLOW(B)∩FOLLOW(A)＝Φ狀態(tài)5和狀態(tài)9的矛盾均可用SLR(1)方法解決，結(jié)構(gòu)SLR(1)剖析表如下：ACTIONGOTO狀態(tài)abc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1該SLR(1)剖析表無重定義，所以該文法是SLR(1)文法，不是LR(0)文法。八、語義剖析題1、將語句if((A<0)(B>0))thenwhile(C>0)doC:=C-D翻譯成四元式答案：100(j<，A，0，104)101(j，-，-，102)102(j>，B，0，104)103(j，-，-，109)104(j>，C