編譯原理作業(yè)標準答案.

1、編譯原理 作業(yè)標準答案第一章 引 言一、解釋下列各詞源語言:編寫源程序的語言（基本符號，關鍵字），各種程序設計語言都可以作為源語言。源程序: 用接近自然語言（數(shù)學語言）的源語言（基本符號，關鍵字）編寫的程序，它是翻譯程序處理的對象。目標程序: 目標程序是源程序經(jīng)過翻譯程序加工最后得到的程序。目標程序（結(jié)果程序）一般可由計算機直接執(zhí)行。低級語言：機器語言和匯編語言。高級語言：是人們根據(jù)描述實際問題的需要而設計的一個記號系統(tǒng)。如同自然語言（接近數(shù)學語言和工程語言）一樣，語言的基本單位是語句，由符號組和一組用來組織它們成為有確定意義的組合規(guī)則。翻譯程序: 能夠把某一種語言程序（源語言程序）改變成另一

2、種語言程序（目標語言程序），后者與前者在邏輯上是等價的。其中包括：編譯程序，解釋程序，匯編程序。編譯程序: 把輸入的源程序翻譯成等價的目標程序（匯編語言或機器語言），然后再執(zhí)行目標程序（先編譯后執(zhí)行），執(zhí)行翻譯工作的程序稱為編譯程序。解釋程序: 以該語言寫的源程序作為輸入，但不產(chǎn)生目標程序。按源程序中語句動態(tài)順序逐句的邊解釋邊執(zhí)行的過程，完成翻譯工作的程序稱為解釋程序。二、什么叫“遍”？指對源程序或源程序的中間形式（如單詞，中間代碼）從頭到尾掃描一次，并作相應的加工處理，稱為一遍。三、簡述編譯程序的基本過程的任務。編譯程序的工作是指從輸入源程序開始到輸出目標程序為止的整個過程，整個過程可以劃分

3、5個階段。詞法分析：輸入源程序，進行詞法分析，輸出單詞符號。語法分析：在詞法分析的基礎上，根據(jù)語言的語法規(guī)則把單詞符號串分解成各類語法單位，并判斷輸入串是否構(gòu)成語法正確的“程序”。中間代碼生成：按照語義規(guī)則把語法分析器歸約（或推導）出的語法單位翻譯成一定形式的中間代碼。優(yōu)化：對中間代碼進行優(yōu)化處理。目標代碼生成：把中間代碼翻譯成目標語言程序。四、編譯程序與解釋程序的區(qū)別？編譯程序生成目標程序后，再執(zhí)行目標程序；然而解釋程序不生成目標程序，邊解釋邊執(zhí)行。五、有人認為編譯程序的五個組成部分缺一不可，這種看法正確嗎？編譯程序的5個階段中，詞法分析，語法分析，語義分析和代碼生成生成是必須完成的。而中間

4、代碼生成和代碼優(yōu)化并不是必不可少的。優(yōu)化的目的是為了提高目標程序的質(zhì)量，沒有這一部分工作，仍然能夠得到目標代碼、六、編譯程序的分類 目前基本分為：診斷編譯程序，優(yōu)化編譯程序，交叉編譯程序，可變目標編譯程序。 第二章 高級語言及其語法描述一、P36 6、令文法為N ® D½NDD ® 0½1½2½¼½9 文法描述的語言L（G）是什么？ 給出句子34，568的最左推導和最右推導。解： L（G）=a½a為可帶前導0的正整數(shù)或L（G）=（0½1½2½¼½9）+ 或

5、 L（G）=a½a為數(shù)字串 最左推導：NÞNDÞDDÞ3DÞ34NÞNDÞNDDÞDDDÞ5DDÞ56DÞ568最右推導：NÞNDÞN4ÞD4Þ34NÞNDÞN8ÞND8ÞN68ÞD68Þ5687、寫出一個文法，使其語言是奇數(shù)集，且每個奇數(shù)是不以0開頭。解：N ® C½AC½ABCC ® 1½3½5½7½9A

6、 ® 1½2½¼½9B ® B½BBB ® 0½A8、令文法為 E ® T½E+T½E-TT ® F½T*F½T/FF ® （E）½i 給出i+i*i，i*（i+i）的最左推導和最右推導。給出i+i+i，i+i*i的語法樹。解：最左推導EÞE+TÞT+TÞF+TÞi+TÞi+T*FÞi+F*FÞi+i*FÞi+i*iEÞTÞT*

7、FÞF*FÞi*FÞi*(E)Þi*(E+T)Þi*(T+T)Þi*(F+T)Þi*(i+T)Þi*(i+F)Þi*(i+i)最右推導EÞE+TÞE+T*FÞE+T*iÞE+F*iÞE+i*iÞT+i*iÞF+i*iÞi+i*iEÞTÞT*FÞT*(E)ÞT*(E+T)ÞT*(E+F)ÞT*(E+i)ÞT*(T+i)ÞT*(F+i)ÞT*

8、(i+i)ÞF*(i+i)Þi*(i+i) 構(gòu)造語法樹 E 最左推導構(gòu)造語法樹 E + T E + T i T i i10、把下列文法改寫為無二義的：S ® SS½（S）½（）解：改寫后的文法S ® SA½（S）½（）A ® （S）½（） 第三章 詞法分析一、P647、構(gòu)造下列正規(guī)式相應的DFA M構(gòu)造相應的NFA MYX 1（0½1）*101 Y5431X 1 （0½1）* 1 0 1 Y3221X45 1 e e 1 0 1 0½1 0 Y54321X 1 e

9、e 1 0 1 1構(gòu)造轉(zhuǎn)換矩陣表（用子集法） I I0 I1 S 0 1X 1,2,3 0 11,2,3 2,3 2,3,4 1 2 32,3 2,3 2,3,4 2 2 32,3,4 2,3,5 2,3,4 3 4 32,3,5 2,3 2,3,4,Y 4 2 52,3,4,Y 2,3,5 2,3,4 5 4 3由轉(zhuǎn)換矩陣構(gòu)造DFA M25 001 0 0 1 1 1 034 1 1 0 1 將DFA M最小化 將DFA M的狀態(tài)劃分為非終態(tài)集0,1,2,3,4和終態(tài)集5p=0，1，2，3，4，5對每一個子集及每一個aÎS進行考察；0，1，2，3，41=1，3，3，3，5Ë

10、;0，1，2，3，4對于輸入1是可區(qū)別的，將0，1，2，3，4分為 0,1,2，3 和 4。pnew = 0,1,2，3，4，5對pnew 進行考察；0，1，2，30=-，2，2，4Ë0，1，2，3由于0結(jié)點不能接受輸入的數(shù)字“0”，并不屬于任何狀態(tài)集，所以先將0結(jié)點區(qū)別出來,又由于3結(jié)點輸入的數(shù)字“0”到達4結(jié)點，所以將3結(jié)點也區(qū)別出來3。將0，1,2，3 分為 0 ，1，2和 3pnew = 0，1,2，3，4，5對pnew 進行考察；1,20=2Ì1，2，1,21=3Í3則1，2不可劃分合為一個狀態(tài)，最終的結(jié)果是；pnew = 0，1,2，3，4，5。根據(jù)最

11、小化的結(jié)果構(gòu)造矩陣表 舊名 0 1，2 3 4 5 新名 0 1 2 3 4 S 0 1 0 1 1 1 2 2 3 2 3 1 4 4 3 2 構(gòu)造最小化的DFA M 0 1 143210 1 1 0 1 0 012將下圖的有限自動機確定化和最小化 a a,b 01 a 該有限自動機輸入同一字符a時到達兩個不同的結(jié)點,所以是NFA。構(gòu)造轉(zhuǎn)換矩陣表（用子集法） I Ia Ib S a b 0 0，1 1 0 1 2 0，1 0，1 1 1 1 2 1 0 2 0 由轉(zhuǎn)換矩陣構(gòu)造DFA M1 a a0 b a2 b將DFA M最小化將DFA M的狀態(tài)劃分為非終態(tài)集2和終態(tài)集0，1p=2，0，1對

12、每一個子集及每一個aÎS進行考察；0，1A=1Ì0，10，1b=2，2Í2對于輸入a和b均是不可區(qū)別的，所以pnew = 0,1，2根據(jù)最小化的結(jié)果構(gòu)造矩陣表 舊名 0，1 2 S a b 新名 0 1 0 0 1 1 0 構(gòu)造最小化的DFA M a 01 b a 二、P6514、構(gòu)造一個DFA M，它接受å=0，1上所有滿足如下條件的字符串：每個1都有0直接跟在右邊。 寫出正規(guī)集的正規(guī)式的表示形式 （0½10）* 構(gòu)造相應的NFA MYX （0½10）* 1YX e e 0½10 0Y1X e e 1 0 2 構(gòu)造轉(zhuǎn)換矩陣

13、表（用子集法） I I0 I1 S 0 1 X，1，Y ！，Y 2 0 1 2 1，Y 1，Y 2 1 1 2 2 1，Y 2 1 由轉(zhuǎn)換矩陣構(gòu)造DFA M 1 021 0 1 0 0 將DFA M最小化 將DFA M的狀態(tài)劃分為非終態(tài)集2和終態(tài)集0，1p=2，0，1對每一個子集及每一個0，1ÎS進行考察；0，10=1Ì0，10，11=2，2Í2對于輸入a和b均是不可區(qū)別的，所以pnew = 0,1，2根據(jù)最小化的結(jié)果構(gòu)造矩陣表 舊名 0，1 2 S 0 1 新名 0 1 0 0 1 1 0 構(gòu)造最小化的DFA M 0 10 1 0 第四章 語法分析-自上而下一、

14、用P76的文法寫出表達式 (i+i)*i 的預測分析過程。 步驟 符號棧 輸入串 所用的產(chǎn)生式 0 #E （i+i）*i# 1 #ET （i+i）*i# E®TE 2 #ETF （i+i）*i# T®FT 3 #ET）E（ （i+i）*i# F®（E） 4 #ET）E i+i）*i# 5 #ET）ET i+i）*i# E®TE 6 #ET）ETF i+i）*i# T®FT 7 #ET）ETi i+i）*i# F®i 8 #ET）ET +i）*i# 9 #ET）E +i）*i# T®e 10 #ET）ET+ +i）*i# E&

15、#174;+TE 11 #ET）ET i）*i# 12 #ET）ETF i）*i# T®FT 13 #ET）ETi i）*i# F®i 14 #ET）ET ）*i# 15 #ET）E ）*i# T®e 16 #ET） ）*i# E®e 18 #ET *i# 19 #ETF* *i# T®*FT 20 #ETF i# 21 #ETi i# F®i 22 #ET # 23 #E # T®e 24 # # E®e二、P811、 考慮下面文法GS® a½½（T） T®T，S½

16、;S消除文法的左遞歸。經(jīng)改寫后的文法是否是LL（1）的？給出它的預測分析表。解：經(jīng)考察該文法S® a½½（T）的各侯選式的首字符都是終結(jié)符號，所以只有T®T，S½S是直接左遞歸。根據(jù)改寫算法，改寫后的文法是：S® a½½（T） T®STT®，ST½e 證明改寫后的文法是否是LL（1）的.證明S® a½½（T）各侯選式的FIRST是否兩兩相交。 FIRST（a）ÇFIRST（）=fFIRST（a）ÇFIRST（）=fFIRST（）

17、9;FIRST（）=f證明T®，ST½e的FIRST（T）和FOLLOW（T）是否相交。 求FIRST（T）=，e FOLLOW（T）= ) FIRST（T）Ç FOLLOW（T）=，eÇ ) =f該文法是LL（1）的。構(gòu)造預測分析表 a ， （ ） # S S® a S® S®（T） T T®ST T®ST T®ST T T®，ST T®e 2、下面的文法GE® TE E®+E½e T®FTT®T½eF®

18、PF F®*F½eP®（E）½½a½b計算這個文法的每個非終結(jié)符的FIRST和FOLLOW。證明這個文法是LL（1）的構(gòu)造它的預測分析表。解：求非終結(jié)符的FIRST和FOLLOW。求非終結(jié)符的FIRST：因為E®+E½e，所以FIRST（E）=+， e因為F®*F½e，所以FIRST（F）=*， e因為P®（E）½½a½b，所以FIRST（P）=（， ， a， b 因為F®PF，所以FIRST（F）= FIRST（P）因為T®FT，所以

19、FIRST（T）=FIRST（F）因為E® TE，所以FIRST（E）= FIRST（T）因為T®T½e，所以FIRST（T）= FIRST（T）È e =（， ， a， b ，e求非終結(jié)符的FOLLOW：因為E® TE的E是文法的開始符號，F(xiàn)OLLOW（E）=#，又因為P®（E），所以FOLLOW（E）=#ÈFIRST（）e=#，)因為E® TE，所以FOLLOW（E）=FOLLOW（E）因為E® TE，并且Ee，所以FOLLOW（T）=FIRST（E）e,又因為E®e,所以FOLLOW（T）

20、=+È FOLLOW（E）=+È #,=+，#,) .因為T®FT，所以FOLLOW（T）=FOLLOW（T）=+，#,) .因為T® FT，并且Te，所以FOLLOW（F）=FIRST（T）e,又因為T®e,所以FOLLOW（F）=（，a，b È FOLLOW（T）=（，a，b È+，#,) =（，a，b ,+，#,) 因為F®PF，所以FOLLOW（F）=FOLLOW（F）=（，a，b ,+，#,) .因為F®PF，并且Fe，所以FOLLOW（P）=FIRST（F）e,又因為F®e,所以FO

21、LLOW（P）=*È FOLLOW（F）=*È（，a，b,+,）,# =*,（，a，b ,+，),# .證明這個文法是LL（1）的證明P®(E)½½a½b各侯選式的FIRST是否兩兩相交。 FIRST（(E)）ÇFIRST（）=fFIRST（(E)）ÇFIRST（a）=fFIRST（(E)）ÇFIRST（b）=f FIRST（）ÇFIRST（a）=fFIRST（）ÇFIRST（b）=fFIRST（a）ÇFIRST（b）=f證明E®+E½e,T®T

22、½e,F®*F½e非終結(jié)符號的FIRST和FOLLOW是否相交。FIRST（E）Ç FOLLOW（E）=+，eÇ#, ) =fFIRST（T）Ç FOLLOW（T）=（， ， a， b ，eÇ+，#,) =f FIRST（F）Ç FOLLOW（F）=*，eÇ（，a，b ,+，#,) =f該文法是LL（1）的。構(gòu)造預測分析表 + * ( ) a b # E TE TE TE TE E +E e e T FT FT FT FT T e T e T T T e F PF PF PF PF F e *F e e

23、e e e e P (E) a b 第五章 語法分析-自上而下分析一、寫出表達式（i+i）*i的LR分析過程（P101 LR分析表）。步驟 狀態(tài) 符號 輸入串 下一狀態(tài) 1 0 # (i+i)*i# 4 2 04 #( i+i)*i# 5 3 045 #(i +i)*i# goto(4,F)=3 4 043 #(F +i)*i# goto(4,T)=2 5 042 #(T +i)*i# goto(4,E)=8 6 048 #(E +i)*i# 6 7 0486 #(E+ i)*i# 5 8 04865 #(E+i )*i# goto(6,F)=3 9 04863 #(E+F )*i# goto

24、(6,T)=9 10 04 #(E+T )*i# goto(4,E)=8 11 048 #(E )*i# 11 12 04811 #(E) *i# goto(0,F)=3 13 03 #F *i# goto(0,T)=2 14 02 #T *i# 7 15 027 #T* i# 5 16 0275 #T*i # goto(7,F)=10 17 02710 #T*F # goto(0,T)=2 18 02 #T # goto(0,E)=1 19 01 #E # 二、P133 1、 令文法為EE+T½T TT*F½F F（E）½i證明E+T*F是它的一個句型，指出這個

25、句型的所有短語，直接短語和句柄。證明輸入串E+T*F是文法的一個句型，建立一個最右推導:EÞE+TÞE+T*F，E+T*F是該文法的句型。EE 且 EE+T*F所以，E+T*F是句型E+T*F+i對于E的一個短語。因為 EE+T 且 TÞT*F所以，T*F是句型E+T*F對于T®T*F的一個直接短語。句型E+T*F的短語為E+T*F，直接短語為T*F，由于直接短語是唯一的，因此T*F為句柄。三、P1345考慮文法SAS½b ASA½a 列出這個文法的所有LR（0）項目。構(gòu)造這個文法的LR（0）項目規(guī)范族及識別活前綴的DFA。這個文法是

26、SLR（1）的嗎？若是，構(gòu)造出它的SLR分析表。解：構(gòu)造拓廣文法，并列出文法的所有項目SS S·S SS· SAS S·AS SA·S SAS·Sb S·b Sb· ASA A·SA AS·A ASA·Aa A·a Aa·構(gòu)造這個文法的LR（0）項目規(guī)范族及識別活前綴的DFA。 A 0 2 5 4 A S A S b A S a a b b a a b b a a S S ASA·SS·ASS·bA·SAA·aS·S

27、S·ASS·bA·SAA·aSAS·AS·AA·SAA·aS·ASS·bASA·SA·SS·ASS·bA·SAA·aSS·AS·AA·SAA·aS·ASS·bAS·AA·SAA·aS·ASS·bS·bA·aS·ASS·bAa· 證明文法是SLR（1）的嗎？為了驗證這個文法是否是S

28、LR(1)文法，必須對LR(0)項目規(guī)范族的各個項目集I，驗證其是否存在“移進歸約”、“歸約歸約”沖突。該項目規(guī)范族中的I1,I4,I5存在“移進歸約”，只需證明存在集合的í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ý&#

29、237;ýÇía,býf，所以不存在“移進歸約”沖突。對狀態(tài)I4有FOLLOW(S)ía,bý；A·a；S·b。因此FOLLOW(A)Çía,bý=ía,býÇía,bý¹f，所以存在“移進歸約”沖突。對狀態(tài)I5也同樣存在這種沖突，即FOLLOW(S)Çía,bý=í,a,býÇía,bý¹f，因此，該文法不是SLR(1)文法。四、P13

30、5 7、證明下面文法是SLR（1）擔不是LR（0）的SA AAb½bBa BaAc½a½aAb證明：因為項目AAb·和BaAb·出現(xiàn)在一個項目集中，造成“歸約-歸”約沖突，所以不是LR（0）文法。又因為FOLLOW（A）=b，c，#，F(xiàn)OLLOW（B）=a使得FOLLOW（A）FOLLOW（B）=，構(gòu)造SLR（1）分析表時不會出現(xiàn)沖突，所以該文法是SLR（1）的。五、對給定文法G，構(gòu)造分析表，并利用此分析表判定符號串a(chǎn)ccd是否文法的句子？ (0)SE E aA E bB A cA Ad B cB B d解：該文法在P110，分析表在P109，

31、構(gòu)造LR（0）的項目在P105（略）。構(gòu)造LR（0）識別活前綴的DFA在P106（略）構(gòu)造LR（0）分析表在P109（略）。利用LR（0）分析表判定符號串a(chǎn)ccd的分析過程： 狀態(tài)棧 符號棧 輸入串 動作 0 # accd# 開始 02 #a ccd# 移進 024 #ac cd# 移進0244 #acc d# 移進024410 #accd # 移進02448 #accA # 用Ad歸約0248 #acA # 用AcA歸約026 #aA # 用AcA歸約01 #E # 用EaA歸約第六章 屬性文法和語法制導翻譯思考題P164 1 第七章 語義分析和中間代碼產(chǎn)生一、 P2185、把下列賦值語句翻

32、譯為三地址代碼序列,語義規(guī)則在P181： Ai，j:=Bi，j+CAK，i+Di+j解：求Ai，jLid (i) L.place:=id.place; L.offset:=null EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place := L.placeL.offset) end ElistidE (i) Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.placeLid (j) L.place:=id.place; L.o

33、ffset:=null EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place:=L.placeL.offset) end ElistElist,E (j) t:=newtemp; m:=Elist.ndim+1; emit(t := Elist.place * limit(Elist1.array,m) emit(t := t + E.place) Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;LElist L.p

34、lace:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emit(L.offset := w *Elist.place)求Bi,j的處理同Ai,j(省略中間過成) ElistidE (i) Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place ElistElist,E (j) t:=newtemp; m:=Elist.ndim+1; emit(t := Elist.place * limit(Elist1.array,m) emit(t := t + E.pl

35、ace) Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;LElist L.place:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emit(L.offset := w *Elist.place) EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place:=L.placeL.offset) end求AK，iElistidE (k) Elist.pl

36、ace:=E.place; Elist.ndim:=1; Elist.array:=id.place ElistElist,E (i) t:=newtemp; m:=Elist.ndim+1; emit(t := Elist.place * limit(Elist1.array,m) emit(t := t + E.place) Elist.array:=Elist1.array; Elist.place:=t; Elist.ndim:=m;LElist L.place:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emi

37、t(L.offset := w *Elist.place)EL if L.offset=null then E.place:=L.place else begin E.place:=newtemp; emit(E.place:=L.placeL.offset) end求Di+jEE+E E.place:=newtemp; emit(E.place := E1.place + E2.place)ElistidE (i+j) Elist.place:=E.place; Elist.ndim:=1; Elist.array:=id.place LElist L.place:=newtemp;emit(L.place := Elist.arry - c )L.offset:=newtemp;emit(L.offset := w *Elist.place)EL if L.offset=null then E.place:=L.