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

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

S→AB|A|B|∑

A→

aAb|ab

B→

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

S→

AB|B

A→

a|aA

B→

bBc|bc給出下面語(yǔ)言的相應(yīng)文法L3={anbncm|m,n≥1，n為奇數(shù)，m為偶數(shù)}。答案：文法G(S):S→ACA→aaAbb/abC→ccCcc/cc四、詞法分析題1、構(gòu)造下面正規(guī)式相應(yīng)的DFA((0|1)*|(11)*)*（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）2、構(gòu)造下面正規(guī)式相應(yīng)的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、構(gòu)造一個(gè)DFA，它接受={a，b}上所有包含ab的字符串。（要求：先將正規(guī)式轉(zhuǎn)化為NFA，再將NFA確定化，最小化）答案：(一)相應(yīng)的正規(guī)式為(a|b)*ab(a|b)*(二)①與此正規(guī)式對(duì)應(yīng)的NFA為②狀態(tài)轉(zhuǎn)換矩陣為：③最小化：{0，1，2}{3，4，5}{0，2}，1，{3，4，5}bbaa01b3ba④所以此等價(jià)的DFA為：開(kāi)始狀態(tài)為0，終態(tài)集為{3}，狀態(tài)集為{0,1,3}，輸入字母表是{a,b}狀態(tài)轉(zhuǎn)換圖如上。4、構(gòu)造與正規(guī)式b(a|b)*ba等價(jià)的DFA五、語(yǔ)法分析題1、對(duì)下面的文法G:Expr→-ExprExpr→(Expr)|VarExprTailExprTail→-Expr|εVar→idVarTailVarTail→(Expr)|ε構(gòu)造LL(1)分析表。（12分）答案：（1）FIRST(Expr)={_,(,id}FIRST(ExprTail)={_,ε}FIRST(Var)={id}FIRST(VarTail)={(,ε}FOLLOW(Expr)={#,)}FOLLOW(ExprTail)={#,)}FOLLOW(Var)={_,#,)}FOLLOW(VarTail)={_,#,)}給出對(duì)句子id—id((id))的分析過(guò)程。（8分）步驟 符號(hào)棧 輸入串 所用產(chǎn)生式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、對(duì)下面的文法G:E→TE’E’→+E|εT→FT’T’→T|εF→PF’F’→*F’|εP→(E)|a|b|∧計(jì)算這個(gè)文法的每個(gè)非終結(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,^,+,),#}證明這個(gè)文法是LL(1)的。（6分）答案：考慮下列產(chǎn)生式: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)文法.構(gòu)造它的預(yù)測(cè)分析表。（6分）3、已知文法G[S]為：S->a|(T)T->T,S|S=1\*GB3①消除文法G[S]中的左遞歸，得文法G′[S]。=2\*GB3②文法G′[S]是否為L(zhǎng)L(1)的若是，給出它的預(yù)測(cè)分析表。4、對(duì)下面的文法G:SSaT|aT|aTTaT|a(1)消除該文法的左遞歸和提取左公因子；(2)構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；(3)構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。答案：5、文法G(S)及其LR分析表如下，請(qǐng)給出串baba#的分析過(guò)程。(1)S→DbB (2)D→d (3)D→ε(4)B→a (5)B→Bba (6)B→εLR分析表ACTIONGOTObDa#SBD0r3s3121acc2s43r24r6S5r665r4r46s7r17S88r5r5答案：步驟 狀態(tài) 符號(hào) 輸入串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六、語(yǔ)法分析題考慮文法:S→AS|bA→SA|a列出這個(gè)文法的所有LR(0)項(xiàng)目。（5分）答案0. 1. 2. 3.4. 5. 6. 7.8. 9. 10. 11.（2）給出識(shí)別文法所有活前綴的DFA。（5分）（3）求所有非終結(jié)符的FOLLOW集。（5分）（4）文法是SLR文法嗎若是，構(gòu)造出它的SLR分析表,否則說(shuō)明理由。（5分）不是SLR文法狀態(tài)3，6，7有移進(jìn)歸約沖突狀態(tài)3：FOLLOW(S’)={#}不包含a,b狀態(tài)6：FOLLOW(S)={#,a,b}包含a,b,；移進(jìn)歸約沖突無(wú)法消解狀態(tài)7：FOLLOW(A)={a,b}包含a,b；移進(jìn)歸約沖突消解所以不是SLR文法。七、證明題1、證明下面文法是LL(1)的但不是SLR(1)的。S→AaAb|BbBaA→εB→ε首先該文法無(wú)左遞歸存在,沒(méi)有公共左因子。其次:對(duì)于S→AaAb|BbBaFIRST(AaAb)={a}FIRST(BbBa)=FIRST(AaAb)∩FIRST(BbBa)=Φ所以該文法是LL(1)文法。(2)證明該文法不是SLR的。文法的LR(0)項(xiàng)目集規(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構(gòu)造LR(0)項(xiàng)目集規(guī)范族：狀態(tài)項(xiàng)目集轉(zhuǎn)換函數(shù)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存在“歸約－移進(jìn)”沖突，狀態(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)方法解決，構(gòu)造SLR(1)分析表如下：狀態(tài)ACTIONGOTOabc#AB0S211S3ACCEPT2S543R1R1R14S65R4S276R2R2R27S9S88R39R5R1R1R1該SLR(1)分析表無(wú)重定義，因此該文法是SLR(1)文法，不是LR(0)文法。八、語(yǔ)義分析題1、將語(yǔ)句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