編譯原理作業(yè)參考答案

第1章引言1、解釋下列各詞源語言:編寫源程序的語言（基本符號，關鍵字），各種程序設計語言都可以作為源語言。源程序:用接近自然語言（數(shù)學語言）的源語言（基本符號，關鍵字）編寫的程序，它是翻譯程序處理的對象。目標程序:目標程序是源程序經(jīng)過翻譯程序加工最后得到的程序。目標程序（結果程序）一般可由計算機直接執(zhí)行。低級語言：機器語言和匯編語言。高級語言：是人們根據(jù)描述實際問題的需要而設計的一個記號系統(tǒng)。如同自然語言（接近數(shù)學語言和工程語言）一樣，語言的基本單位是語句，由符號組和一組用來組織它們成為有確定意義的組合規(guī)則。翻譯程序:能夠把某一種語言程序（源語言程序）改變成另一種語言程序（目標語言程序），后者與前者在邏輯上是等價的。其中包括：編譯程序，解釋程序，匯編程序。編譯程序:把輸入的源程序翻譯成等價的目標程序（匯編語言或機器語言），然后再執(zhí)行目標程序（先編譯后執(zhí)行），執(zhí)行翻譯工作的程序稱為編譯程序。解釋程序:以該語言寫的源程序作為輸入，但不產(chǎn)生目標程序。按源程序中語句動態(tài)順序逐句的邊解釋邊執(zhí)行的過程，完成翻譯工作的程序稱為解釋程序。2、什么叫“遍”？指對源程序或源程序的中間形式（如單詞，中間代碼）從頭到尾掃描一次，并作相應的加工處理，稱為一遍。3、簡述編譯程序的基本過程的任務。編譯程序的工作是指從輸入源程序開始到輸出目標程序為止的整個過程，整個過程可以劃分5個階段。詞法分析：輸入源程序，進行詞法分析，輸出單詞符號。語法分析：在詞法分析的基礎上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單位，并判斷輸入串是否構成語法正確的“程序”。中間代碼生成：按照語義規(guī)則把語法分析器歸約（或推導）出的語法單位翻譯成一定形式的中間代碼。優(yōu)化：對中間代碼進行優(yōu)化處理。目標代碼生成：把中間代碼翻譯成目標語言程序。4、編譯程序與解釋程序的區(qū)別？編譯程序生成目標程序后，再執(zhí)行目標程序；然而解釋程序不生成目標程序，邊解釋邊執(zhí)行。5、有人認為編譯程序的五個組成部分缺一不可，這種看法正確嗎？編譯程序的5個階段中，詞法分析，語法分析，語義分析和代碼生成生成是必須完成的。而中間代碼生成和代碼優(yōu)化并不是必不可少的。優(yōu)化的目的是為了提高目標程序的質(zhì)量，沒有這一部分工作，仍然能夠得到目標代碼。6、編譯程序的分類目前基本分為：診斷編譯程序，優(yōu)化編譯程序，交叉編譯程序，可變目標編譯程序。第2章高級語言及其語法描述1（P36）令文法為NDNDD0129（1）文法描述的語言L（G）是什么？（2）給出句子34，568的最左推導和最右推導。答：（1）L（G）={為可帶前導0的正整數(shù)}或L（G）={（0129）+}或L（G）={為數(shù)字串}（2）最左推導：NNDDD3D34NNDNDDDDD5DD56D568最右推導：NNDN4D434NNDN8ND8N68D685682*．寫出一個文法，使其語言是奇數(shù)集，且每個奇數(shù)是不以0開頭。答： SCAB|B（考慮了正負號） A1|2|3|4|5|6|7|8|9|AA|A0| B1|3|5|7|9 C+|-|或：（未考慮正負號） SB|AB B1|3|5|7|9 AAD|N N2|4|6|8|B D0|N或：（未考慮正負號）SC|ABC C1|3|5|7|9 A1|2|3|4|5|6|7|8|9 BBA|B0|2.（P36,8）令文法為ETE+TE-TTFT*FT/FF（E）i（1）給出該文法的VN、VT和S。（2）給出i+i*i，i*（i+i）的最左推導和最右推導。（3）給出i+i+i，i+i*i的語法樹。答：（1）VN={E,T,F}VT={+,-,*,/,(,),i}S=E（2）最左推導EE+TT+TF+Ti+Ti+T*Fi+F*Fi+i*Fi+i*iETT*FF*Fi*Fi*(E)i*(E+T)i*(T+T)i*(F+T)i*(i+T)i*(i+F)i*(i+i)最右推導EE+TE+T*FE+T*iE+F*iE+i*iT+i*iF+i*ii+i*iETT*FT*(E)T*(E+T)T*(E+F)T*(E+i)T*(T+i)T*(F+i)T*(i+i)F*(i+i)i*(i+i)=2\*GB2⑵構造語法樹E最左推導構造語法樹E+TE+TiTii3.（P36,9）證明下面的文法是二義的： SiSeS|iSi答：對于句子iiiei有兩棵不同的語法樹。因此該文法是二義的。SiSeSiiSeSiiieSiiieiSiSiiSeSiiieSiiiei第3章詞法分析1．設M=（{x，y}，{a，b}，，x，{y}）為一個非確定有限自動機NFAM，其中定義如下：（x，a）={x，y}（x，b）={y}（y，a）=（y，b）={x，y}試構造其相應的最小化的確定有限自動機DFAM’。答：由定義可知（x，a），（y，b）均為多值函數(shù)，所以是一個非確定有限自動機。（1）根據(jù)函數(shù)值，先構造NFAM（2）確定化：①構造DFAM’的轉換矩陣:IIaIb{x}①{x，y}②{y}③{x，y}②{x，y}②{x，y}②{y}③{x，y}②②確定DFAM’的初始狀態(tài)和終態(tài)：（a）轉換矩陣中I列的第一個狀態(tài)①為DFAM’的初始狀態(tài)結點。（b）含有y狀態(tài)的子集均為DFAM’的終態(tài)結點(②、③為終態(tài)結點)。③根據(jù)DFAM’的轉換矩陣畫出對應的狀態(tài)轉換圖：（3）最小化：①首先將其劃分成終態(tài)集{2，3}和非終態(tài)集{1}②{2，3}a=｛2｝{2，3}，{2，3}b=｛2｝{2，3}因此{2，3}已是不可再區(qū)分的,所以該DFAM’已是最小化的。2.（P64，7(1)）構造正規(guī)式1(01)*101相應的DFAM。答：（1）構造NFAM。XY1（01）*XYX3514Y1X3514YX32X321542Y01X1X12345Y11011（2）構造轉換矩陣II0I1{X}①{1,2,3}②{1,2,3}②{2,3}③{2,3,4}④{2,3}③{2,3}③{2,3,4}④{2,3,4}④{2,3,5}⑤{2,3,4}④{2,3,5}⑤{2,3}③{2,3,4,Y}⑥{2,3,4,Y}⑥{2,3,5}⑤{2,3,4}④（3）由轉換矩陣構造DFAM3．（P64，12(a)）將下圖所示的NFAM轉換為等價的DFAM’，并將該DFA’最小化。答：該有限自動機狀態(tài)0輸入同一字符a時到達兩個不同的結點,所以是NFA。（1）構造轉換矩陣IIaIb{0}①{0，1}②{1}③{0，1}②{0，1}②{1}③{1}③{0}①（2）由轉換矩陣構造DFAM12123abab（3）將DFAM最小化=1\*GB3①將DFAM的狀態(tài)劃分為非終態(tài)集{3}和終態(tài)集{1，2}=2\*GB3②對每一個子集及每一個a進行考察；{1，2}a={2}{1，2}{1，2}b={3}{3}因此{1，2}是不可區(qū)分的，所以最終狀態(tài)為：{1，2}，{3}構造最小化的DFAM：12，312，3ba4.（P64，12（b））將下圖所示的NFAM轉換為等價的DFAM’，并進行最小化。答：從圖上可知該圖已經(jīng)是DFAM，先只需將其最小化。首先劃分為兩個集合：{0,1}和{2,3,4,5}{2,3,4,5}a={1,3,0,5}，劃分為：{2,4}和｛3,5｝{2,4}a={1,0}，{2,4}b={3,5}，無需劃分{3,5}a={3,5}，{3,5}b={2,4}，無需劃分{0,1}a={1}，{0,1}b={2,4}，無需劃分因此，最終的劃分為：{0,1}、{2,4}和｛3,5｝，化簡后的結果：5．（P65，14）構造一個DFAM，它接受={0，1}上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。答：（1）根據(jù)題意，得到正規(guī)式：(0|10)*（2）構造對應的NFAM：（3）將NFAM確定化為DFAM。相應的DFAM的狀態(tài)轉換矩陣如下：II0I1{X,1,Y}①{1;Y}②{2}③{1,Y}②{1;Y}②{2}③{2}③{1;Y}②DFAM轉換圖：（4）將DFAM最小化：①將DFAM的狀態(tài)劃分為非終態(tài)集{3}和終態(tài)集{1,2}②對每一個子集進行考察；{1,2}0={2}{1,2}{1,2}1={3，3}{3}因此{0,1}是不可劃分的。因此最終劃分結果為：{1,2}和{3}最小化后的DFAM：第4章語法分析-自上而下1.（P81，1）考慮下面文法GSa^(T)TT,SS（1）消除文法的左遞歸。（2）經(jīng)改寫后的文法是否是LL(1)的？給出它的預測分析表。答：消除左遞歸：Sa^(T)TST’T’,ST’|證明改寫后的文法是否是LL(1)的。FIRST(S)={a,^,(} FOLLOW(S)={，,),#}FIRST(T)={a,^,(} FOLLOW(T)={)}FIRST(T’)={，,} FOLLOW(T’)={)}=1\*GB3①證明Sa^（T）各侯選式的FIRST是否兩兩相交。FIRST（a）FIRST（^）=FIRST（a）FIRST（（）=FIRST（^）FIRST（（）==2\*GB3②證明T’，ST’的FIRST（T’）和FOLLOW（T’）是否相交。FIRST（T’）FOLLOW（T’）={，，}{}=∴該文法是LL（1）的。所以，改造后的文法是LL(1)文法③預測分析表：a^()，#SSaS^S(T)TTSTTT’ST’ST’T’T’T’,ST’2.利用P76表4.1的LL(1)分析表寫出表達式(i+i)*i的預測分析過程。步驟符號棧輸入串所用的產(chǎn)生式0#E（i+i）*i#1#E’T（i+i）*i#ETE’2#E’T’F（i+i）*i#TFT’3#E’T’）E（（i+i）*i#F（E）4#E’T’）Ei+i）*i#5#E’T’）E`Ti+i）*i#ETE’6#E’T’）E’T’Fi+i）*i#TFT’7#E’T’）E’T’ii+i）*i#Fi8#E’T’）E’T’+i）*i#9#E’T’）E’+i）*i#T’10#E’T’）E’T++i）*i#E’+TE’11#E’T’）E’Ti）*i#12#E’T’）E’T’Fi）*i#TFT’13#E’T’）E’T’ii）*i#Fi14#E’T’）E’T’）*i#15#E’T’）E’）*i#T’16#E’T’））*i#E’18#E’T’*i#19#E’T’F**i#T’*FT’20#E’T’Fi#21#E’T’ii#Fi22#E’T’#23#E’#T’24##E’3.（P81，2）對下面的文法GETE’E’+ETFT’T’TFPF’F’*F’P(E)^ab（1）計算這個文法的每個非終結符的FIRST和FOLLOW。（2）證明這個文法是LL(1)的。（3）構造它的預測分析表。答：（1）計算每個非終結符的FIRST和FOLLOW。 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,^,),#}（求解過程：因為E`+E，所以FIRST（E`）={+，}因為F`*F`，所以FIRST（F`）={*，}因為P（E）^ab，所以FIRST（P）={（，^，a，b因為FPF`，所以FIRST（F）=FIRST（P）因為TFT`，所以FIRST（T）={FIRST（F）因為ETE`，所以FIRST（E）=FIRST（T）因為T`T，所以FIRST（T`）=FIRST（T）{}={（，^，a，b，求非終結符的FOLLOW：因為ETE`的E是文法的開始符號，F(xiàn)OLLOW（E）={#}，又因為P（E），所以FOLLOW（E）={#}FIRST（））\{}={#，)}因為ETE`，所以FOLLOW（E`）=FOLLOW（E）因為ETE`，并且E`≠，所以FOLLOW（T）=FIRST（E`）\{},又因為E`,所以FOLLOW（T）={+}FOLLOW（E）={+}{#,}}={+，#,}.因為TFT`，所以FOLLOW（T`）=FOLLOW（T）={+，#,}.因為TFT`，并且T`≠，所以FOLLOW（F）=FIRST（T`）\{},又因為T`,所以FOLLOW（F）={（，^，a，bFOLLOW（T）={（，^，a，b{+，#,}={（，^，a，b,+，#,因為FPF`，所以FOLLOW（F`）=FOLLOW（F）={（，^，a，b,+，#,.因為FPF`，并且F`≠，所以FOLLOW（P）=FIRST（F`）\{},又因為F`,所以FOLLOW（P）={*FOLLOW（F）={*}{（，^，a，b,+,）,#={*,（，^，a，b,+，,#）（2）證明這個文法是LL(1)的該文法沒有左遞歸，只需考察：E’+ET’TF’*F’P(E)^ab由于：E’+E：FIRST(E’)={+,}∩FOLLOW(E’)={#,}}=ФT’T：FIRST(T’)={(,a,b,^,}∩FOLLOW(T’)={+,),#}=ФF’*F’：FIRST(F’)={*,}∩FOLLOW(F’)={+,(,a,b,^,),#}=ФP(E)^ab：候選式終結符首字符集兩兩不相交所以該文法為LL(1)文法。（3）LL(1)分析表+*()ab^#EETETETETE’E’E’E’E’E’+EE’E’TTFT’TFT’TFT’TFT’T’T’T’TT’T’TT’TT’TT’FFPFFPFFPFFPF’’’’F’F’F’*F’F’F’F’F’F’F’PP(E)PaPbP^第5章語法分析-自上而下分析1．（P133，1）令文法G1為:E→E+T|TT→T*F|FF→(E)|i證明E+T*F是它的一個句型，指出這個句型的所有短語，直接短語和句柄。答：因為有：EE+TE+T*F，所以E+T*F是文法的一個句型。短語：E+T*F,T*F直接短語：T*F句柄：T*F2.（P133，3）考慮文法G2S→a∧|(T)T→T；SS計算文法G2每個非終結符的FIRSTVT和LASTVT。構造文法G2的優(yōu)先關系表，該文法是算符優(yōu)先文法嗎？給出輸入串(a；(a；a))的算符優(yōu)先分析過程。解：FIRSTVT和LASTVTFIRSTVT(S)={a,∧,(}FIRSTVT(T)={；，a,∧,(}LASTVT(S)={a,∧,)}LASTVG(T)={；，a,∧,)}優(yōu)先關系表a∧()；#a∧()；#是算符優(yōu)先分析文法，因為優(yōu)先關系表中沒有沖突的關系。（3）(a,(a,a))的分析過程步驟棧余留符號串棧頂關系下一步動作0#(a；(a；a))##<.((進棧1#(A；(a；a))#(<.aa進棧2#(a；(a；a))#a.>；用S→a歸約3#(S；(a；a))#(<.；;進棧4#(S;(a；a))#;<.((進棧5#(S;(a；a))#(<.aa進棧6#(S;(a；a))#a.>；用S→a歸約7#(S;(S；a))#(<.；;進棧8#(S;(S;a))#;<.aa進棧9#(S;(S;a))#a.>)用S→a歸約10#(S;(S;S))#;.>)用T→T;S歸約11#(S;(T))#())進棧12#(S;(T))#).>)用S→(T)歸約13#(S;S)#;.>)用T→T;S歸約14#(T)#())進棧15#(T)#).>#用S→(T)歸約16#S###結束3.（P134，5）考慮文法S→ASbA→SAa（1）構造這個文法的LR(0)項目規(guī)范族及識別活前綴的DFA。（2）這個文法是SLR（1）的嗎？若是，構造出它的SLR分析表。解：構造拓廣文法：(0)S’→S (1)S→AS (2)S→b (3)A→SA (4)A→a（1）構造這個文法的LR(0)項目規(guī)范族及識別活前綴的DFA。（2）證明文法是否是SLR(1)文法？為了驗證這個文法是否是SLR(1)文法，必須對LR(0)項目集規(guī)范族的各個項目集I，驗證其是否存在“移進－歸約”、“歸約－歸約”沖突。該項目規(guī)范族中的I1,I5,I7存在“移進－歸約”，只需證明存在集合的a,b，F(xiàn)OLLOW(S’)，F(xiàn)OLLOW(S)，F(xiàn)OLLOW(A)兩兩不相交。對此求出FOLLOW(S’)＝＃，F(xiàn)OLLOW(S)＝#,a,b，F(xiàn)OLLOW(A)＝a,b。驗證如下：對狀態(tài)I1有 FOLLOW(S’)=＃；A→·a；S→·b。因此FOLLOW(S’)a,b=＃a,b=，所以不存在“移進－歸約”沖突。對狀態(tài)I5有FOLLOW(A)=a,b；A→·a；S→·b。因此FOLLOW(A)a,b=a,ba,b，所以存在“移進－歸約”沖突。對狀態(tài)I7也同樣存在這種沖突，即:FOLLOW(S)a,b=＃,a,ba,b因此，該文法不是SLR(1)文法。4．（P1357）證明下面文法是SLR(1)文法，但不是LR(0)文法.S→AA→Ab|bBaB→aAc|a|aAb證明：該文法的項目集規(guī)范族有： I0={S→?A，A→?Ab，A→?bBa} I1=GO(I0,A)={S→A?，A→A?b} I2=GO(I0,b)={A→b?Ba，B→?aAc，B→?a，B→?aAb} I3=GO(I1,b)={A→Ab?} I4=GO(I2,B)={A→bB?a} I5=GO(I2,a)={B→a?Ac，B→a?，B→a?Ab，A→?Ab，A→?bBa} I6=GO(I4,a)={A→bBa?} I7=GO(I5,A)={B→aA?c，B→aA?b，A→A?b} I8=GO(I5,b)=I2 I9=GO(I7,b)={B→aAb?，A→Ab?}因為項目集I9中有A→Ab?和B→aAb?，存在“歸約-歸約”沖突，所以不是LR（0）文法。又因為FOLLOW(A)={b，c，#}，F(xiàn)OLLOW(B)={a}使得FOLLOW(A)∩FOLLOW(B)=φ，因此構造SLR(1)分析表時不會出現(xiàn)沖突，所以該文法是SLR(1)的。5．有文法：0．S’→E1．E→aA2．E→bB3．A→cA4．A→d5．B→cB6．B→d根據(jù)下列給出的該文法的LR(0)分析表，寫出分析符號串“accd”的分析過程。狀態(tài)ACTIONGOTOabcd#EAB0S2S311acc2S6S543S8S974r1r1r1r1r15r4r4r4r4r46S6S5107r2r2r2r2r28S8S9119r6r6r6r6r610r3r3r3r3r311r5r5r5r5r5答：步驟狀態(tài)棧符號棧輸入串動作00#accd#S2，移進102#accd#S6，移進2026#accd#S6，移進30266#accd#S5，移進402665#accd#用r4（A→d）歸約5026610#accA#用r3（A→cA）歸約602610#acA#用r3（A→cA）歸約7024#aA#用r1（E→aA）歸約801#E#acc第6章語義分析和中間代碼生成1．根據(jù)給出的語義規(guī)則，寫出下列布爾表達式的翻譯過程(假設第1條四元式地址為100)及最終產(chǎn)生的四元式序列：A<10or（Bandnot（CorD））解：語法樹：翻譯過程：（1）E1→id1relopid2 （A<10）E1.truelist:=makelist(nextquad)=100E1.falselist:=makelist(nextquad+1)=101100(j<,A,10,0)101(j,_,_,0)(j,_,_,102)步驟13回填結果(2)M1→ε:M1.quad:=102(3)E4→id(B)E4.truelist:=makelist(nextquad)=102E4.falselist:=makelist(nextquad+1)=103102(jnz,B,_,0)(jnz,B,_,104)步驟11回填結果103(j,_,_,0)(4)M2→ε:M2.quad:=104(5)E8→id(C)E8.truelist:=makelist(nextquad)=104E8.falselist:=makelist(nextquad+1)=105104(jnz,C,_,0)105(j,_,_,0)(j,_,_,106)步驟8回填結果(6)M3→ε:M3.quad:=106(7)E9→id(D)E9.truelist:=makelist(nextquad)=106E9.falselist:=makelist(nextquad+1)=107106(jnz,D,_,0)(jnz,D,_,104)步驟8的拉鏈(jnz,D,_,103)步驟11的拉鏈107(j,_,_,0)(j,_,_,100)步驟13的拉鏈(8)E7→E8orM3E9backpatch(E8.falselist,M3.quad)=(105,106)E7.truelist:=merge(E8.truelist,E9.truelist)=merge(104,106)=106E7.falselist:=E9.falselist=107(9)E6→(E7)E6.truelist:=E7.truelist=106E6.falselist:=E7.falselist=107(10)E5→notE6E5.truelist:=E6.falselist=107E5.falselist:=E6.truelist=106(11)E3→E4andM2E5backpatch(E4.truelist,M2.quad)=(102,104)E3.falselist:=merge(E4.falselist,E5.falselist)=merge(103,106)=106E3.truelist:=E5.truelist=107(12)E2→(E3)E2.truelist:=E3.truelist=107E2.falselist:=E3.falselist=106（13）E→E1orM1E2backpatch(E1.falselist,M1.quad)=(101,102)E.truelist:=merge(E1.truelist,E2.truelist)=merge(100,107)=107E.falselist:=E2.falselist=106最終結果：A<10or（Bandnot（CorD））100(j<,A,10,0)101(j,_,_,102)無條件轉102(jnz,B,_,104)條件轉103(j,_,_,0)104(jnz,C,_,0)105(j,_,_,106)無條件轉106(jnz,D,_,103)106和103是一條鏈107(j,_,_,100)107和100是一條鏈2.根據(jù)給出的語義規(guī)則，把下面的語句翻譯成四元式序列(設第1條四元式地址為100)：Whilea<candb<ddoifa=1thenc:=c*2elsea:=a+x；解:語法樹：（1）M1→M1.quad:=nextquad=100（2）E1→E1reLopE2(a<c)E1.trulist:=makelist(nextquad)=100E1.falelist:=makelist(nextquad+1)=101100(j<,a,c,0)(j<,a,c,102)，步驟（5）回填101(j,_,_,0)（3）M3→M2.quad:=nextquad=102（4）E2→E1reLopE2(b<d){E2.trulist:=makelist(nextquad)=102E2.falelist:=makelist(nextquad+1)=103102(j<,b,d,0)(j<,b,d,104)，步驟18回填103(j,_,_,0)(j,_,_,101)，步驟（5）拉鏈（5）EandM3backpatch(truelist,M3.quad)=backpatch(100,102)，用102回填100E.truelist:=E2.truelist=102E.falselist:=merge(E1.falselist,E2.falselist)=merge(101,103)=103，103指向101（6）M2→M2.quad:=nextquad=104（7）E3→E1reLopE2(a=1)E3.trulist:=makelist(nextquad)=104E3.falelist:=makelist(nextquad+1)=105104(j=,a,1,0)(j=,a,1,106)，步驟17回填105(j,_,_,0)(j,_,_,109)，步驟17回填（8）M4→M4.quad:=nextquad=106（9）E4→E1*E2(c*2)E4.place:=newtemp=T1106(*，c，2，T1)（10）A1→id:=E(c=c*2)107(:=,T1,_,c)（11）S2→A1S2.nex