編譯原理復習題答案

編譯原理復習題答案編譯原理復習題答案編譯原理復習題答案資料僅供參考文件編號：2022年4月編譯原理復習題答案版本號：A修改號：1頁次：1.0審核：批準:發(fā)布日期：二、概念題1、設有文法：P→P+Q|QQ→Q*R|RR→(P)|i（1）證明Q*R+Q+Q是它的一個句型。（3分)（2）給出Q*R+Q+Q的所有短語，直接短語和句柄。(4分)（3）給出句子ｉ+ｉ*ｉ的最右推導。(4分)（4）給出句子ｉ+ｉ*ｉ的最左推導。(4分)2、設有文法：E→E+T|TT→T*F|FF→(E)|i（1）證明E+T*F是它的一個句型。（3分)答案：（2）給出E+T*F的所有短語，直接短語和句柄。(4分)短語:E+T*F,T*F,直接短語:T*F句柄:T*F（3）給出句子ｉ+ｉ*ｉ的最右推導。(4分)3、寫出表達式a+b*(c-d)對應的逆波蘭式和三元式序列。答案：逆波蘭式：(abcd-*+)三元式序列:OPARG1ARG2(1)-cd(2)*b(1)(3)+a(2)三、詞法分析題給出下面語言的相應文法L1={anbnambm|n,m≥0}答案：

S→AB|A|B|∑

A→

aAb|ab

B→

aBb|ab給出下面語言的相應文法L2={anbnci|n≥1,i≥0}答案：

S→

AB|B

A→

a|aA

B→

bBc|bc給出下面語言的相應文法L3={anbncm|m,n≥1，n為奇數，m為偶數}。答案：文法G(S):S→ACA→aaAbb/abC→ccCcc/cc四、詞法分析題1、構造下面正規(guī)式相應的DFA((0|1)*|(11)*)*（要求：先將正規(guī)式轉化為NFA，再將NFA確定化，最小化）2、構造下面正規(guī)式相應的DFA1(0|1)*101答案：I

I0

I1

{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、構造一個DFA，它接受={a，b}上所有包含ab的字符串。（要求：先將正規(guī)式轉化為NFA，再將NFA確定化，最小化）答案：(一)相應的正規(guī)式為(a|b)*ab(a|b)*(二)①與此正規(guī)式對應的NFA為②狀態(tài)轉換矩陣為：③最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}bbaa01b3ba④所以此等價的DFA為：開始狀態(tài)為0，終態(tài)集為{3}，狀態(tài)集為{0,1,3}，輸入字母表是{a,b}狀態(tài)轉換圖如上。4、構造與正規(guī)式b(a|b)*ba等價的DFA五、語法分析題1、對下面的文法G:Expr→-ExprExpr→(Expr)|VarExprTailExprTail→-Expr|εVar→idVarTailVarTail→(Expr)|ε構造LL(1)分析表。（12分）答案：（1）FIRST(Expr)={_,(,id}FIRST(ExprTail)={_,ε}FIRST(Var)={id}FIRST(VarTail)={(,ε}FOLLOW(Expr)={#,)}FOLLOW(ExprTail)={#,)}FOLLOW(Var)={_,#,)}FOLLOW(VarTail)={_,#,)}給出對句子id—id((id))的分析過程。（8分）步驟 符號棧 輸入串 所用產生式0 ＃Expr id__id((id))＃ 1 #ExprTailVar id__id((id))＃ Expr→VarExprTail2 #ExprTailVarTailid id__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 #Expr id((id))＃9 #ExprTailVar id((id))＃ Expr→VarExprTail10 #ExprTailVarTailid id((id))＃ Var→idVarTail11 #ExprTailVarTail ((id))＃12 #ExprTail)Expr( ((id))＃ VarTail→(Expr)13 #ExprTail)Expr (id))＃14 #ExprTail))Expr( (id))＃ Expr→(Expr)15 #ExprTail))Expr id))＃#ExprTail)) ExprTailVar id))＃ Exp→VarExprTail17 #ExprTail))ExprTailVarTailid id))＃ 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|∧計算這個文法的每個非終結符的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,^,+,),#}證明這個文法是LL(1)的。（6分）答案：考慮下列產生式:FIRST(+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)文法.構造它的預測分析表。（6分）3、已知文法G[S]為：S->a|(T)T->T,S|S=1\*GB3①消除文法G[S]中的左遞歸，得文法G′[S]。=2\*GB3②文法G′[S]是否為LL(1)的若是，給出它的預測分析表。4、對下面的文法G:SSaT|aT|aTTaT|a(1)消除該文法的左遞歸和提取左公因子；(2)構造各非終結符的FIRST和FOLLOW集合；(3)構造該文法的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#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案：步驟 狀態(tài) 符號 輸入串0 0 # baba#1 02 #D baba#2 024 #Db aba#3 0245 #Dba ba#4 0246 #DbB ba#5 02467 #DbBb a#6 024678 #DbBba #7 0246 #DbB #8 01 #S # acc六、語法分析題考慮文法:S→AS|bA→SA|a列出這個文法的所有LR(0)項目。（5分）答案0. 1. 2. 3.4. 5. 6. 7.8. 9. 10. 11.（2）給出識別文法所有活前綴的DFA。（5分）（3）求所有非終結符的FOLLOW集。（5分）（4）文法是SLR文法嗎若是，構造出它的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→ε首先該文法無左遞歸存在,沒有公共左因子。其次:對于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}產生規(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構造LR(0)項目集規(guī)范族：狀態(tài)項目集轉換函數0S→·AA→·AbA→·bBaGO[0，A]＝1GO[0，A]＝1GO[0，b]＝21S→A·A→A·bACCEPTGO[1，b]＝32A→b·BaB→·aAcB→·aB→·aAbGO[2，B]＝4GO[2，a]＝5GO[2，a]＝5GO[2，a]＝53A→Ab·R14A→bB·aGO[4，a]＝65B→a·AcB→a·B→a·AbA→·AbA→·bBaGO[5，A]＝7R4GO[5，A]＝7GO[5，A]＝7GO[5，b]＝26A→bBa·R27B→aA·cB→aA·bA→A·bGO[7，c]＝8GO[7，b]＝9GO[7，b]＝98B→aAc·R39B→aAb·A→Ab·R5R1狀態(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)方法解決，構造SLR(1)分析表如下：狀態(tài)ACTIONGOTOabc#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，-，-，1