編譯原理作業(yè)標(biāo)準(zhǔn)答案.

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

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

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

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

5、 L（G）=a½a為數(shù)字串 最左推導(dǎo)：NÞNDÞDDÞ3DÞ34NÞNDÞNDDÞDDDÞ5DDÞ56DÞ568最右推導(dǎo)：NÞNDÞN4ÞD4Þ34NÞNDÞN8ÞND8ÞN68ÞD68Þ5687、寫出一個(gè)文法，使其語言是奇數(shù)集，且每個(gè)奇數(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）的最左推導(dǎo)和最右推導(dǎo)。給出i+i+i，i+i*i的語法樹。解：最左推導(dǎo)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)最右推導(dǎo)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 最左推導(dǎo)構(gòu)造語法樹 E + T E + T i T i i10、把下列文法改寫為無二義的：S ® SS½（S）½（）解：改寫后的文法S ® SA½（S）½（）A ® （S）½（） 第三章 詞法分析一、P647、構(gòu)造下列正規(guī)式相應(yīng)的DFA M構(gòu)造相應(yīng)的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對(duì)每一個(gè)子集及每一個(gè)aÎS進(jìn)行考察；0，1，2，3，41=1，3，3，3，5Ë

10、;0，1，2，3，4對(duì)于輸入1是可區(qū)別的，將0，1，2，3，4分為 0,1,2，3 和 4。pnew = 0,1,2，3，4，5對(duì)pnew 進(jìn)行考察；0，1，2，30=-，2，2，4Ë0，1，2，3由于0結(jié)點(diǎn)不能接受輸入的數(shù)字“0”，并不屬于任何狀態(tài)集，所以先將0結(jié)點(diǎn)區(qū)別出來,又由于3結(jié)點(diǎn)輸入的數(shù)字“0”到達(dá)4結(jié)點(diǎn)，所以將3結(jié)點(diǎn)也區(qū)別出來3。將0，1,2，3 分為 0 ，1，2和 3pnew = 0，1,2，3，4，5對(duì)pnew 進(jìn)行考察；1,20=2Ì1，2，1,21=3Í3則1，2不可劃分合為一個(gè)狀態(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將下圖的有限自動(dòng)機(jī)確定化和最小化 a a,b 01 a 該有限自動(dòng)機(jī)輸入同一字符a時(shí)到達(dá)兩個(gè)不同的結(jié)點(diǎn),所以是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對(duì)

12、每一個(gè)子集及每一個(gè)aÎS進(jìn)行考察；0，1A=1Ì0，10，1b=2，2Í2對(duì)于輸入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)造一個(gè)DFA M，它接受å=0，1上所有滿足如下條件的字符串：每個(gè)1都有0直接跟在右邊。 寫出正規(guī)集的正規(guī)式的表示形式 （0½10）* 構(gòu)造相應(yīng)的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對(duì)每一個(gè)子集及每一個(gè)0，1ÎS進(jìn)行考察；0，10=1Ì0，10，11=2，2Í2對(duì)于輸入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的文法寫出表達(dá)式 (i+i)*i 的預(yù)測分析過程。 步驟 符號(hào)棧 輸入串 所用的產(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）的？給出它的預(yù)測分析表。解：經(jīng)考察該文法S® a½½（T）的各侯選式的首字符都是終結(jié)符號(hào)，所以只有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)造預(yù)測分析表 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計(jì)算這個(gè)文法的每個(gè)非終結(jié)符的FIRST和FOLLOW。證明這個(gè)文法是LL（1）的構(gòu)造它的預(yù)測分析表。解：求非終結(jié)符的FIRST和FOLLOW。求非終結(jié)符的FIRST：因?yàn)镋®+E½e，所以FIRST（E）=+， e因?yàn)镕®*F½e，所以FIRST（F）=*， e因?yàn)镻®（E）½½a½b，所以FIRST（P）=（， ， a， b 因?yàn)镕®PF，所以FIRST（F）= FIRST（P）因?yàn)門®FT，所以

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

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

21、LLOW（P）=*È FOLLOW（F）=*È（，a，b,+,）,# =*,（，a，b ,+，),# .證明這個(gè)文法是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é)符號(hào)的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)造預(yù)測分析表 + * ( ) 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 第五章 語法分析-自上而下分析一、寫出表達(dá)式（i+i）*i的LR分析過程（P101 LR分析表）。步驟 狀態(tài) 符號(hào) 輸入串 下一狀態(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是它的一個(gè)句型，指出這個(gè)

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

26、SLR（1）的嗎？若是，構(gòu)造出它的SLR分析表。解：構(gòu)造拓廣文法，并列出文法的所有項(xiàng)目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)造這個(gè)文法的LR（0）項(xiàng)目規(guī)范族及識(shí)別活前綴的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）的嗎？為了驗(yàn)證這個(gè)文法是否是S

28、LR(1)文法，必須對(duì)LR(0)項(xiàng)目規(guī)范族的各個(gè)項(xiàng)目集I，驗(yàn)證其是否存在“移進(jìn)歸約”、“歸約歸約”沖突。該項(xiàng)目規(guī)范族中的I1,I4,I5存在“移進(jìn)歸約”，只需證明存在集合的ía,bý，F(xiàn)OLLOW(S)，F(xiàn)OLLOW(S)，F(xiàn)OLLOW(A)兩兩不相交。對(duì)此求出FOLLOW(S)íý，F(xiàn)OLLOW(S)í#,a,bý，F(xiàn)OLLOW(A)ía,bý。驗(yàn)證如下：對(duì)狀態(tài)I1有FOLLOW(S)íý；A·a；S·b。因此FOLLOW(S)Çía,bý&#

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

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

31、構(gòu)造LR（0）的項(xiàng)目在P105（略）。構(gòu)造LR（0）識(shí)別活前綴的DFA在P106（略）構(gòu)造LR（0）分析表在P109（略）。利用LR（0）分析表判定符號(hào)串a(chǎn)ccd的分析過程： 狀態(tài)棧 符號(hào)棧 輸入串 動(dòng)作 0 # accd# 開始 02 #a ccd# 移進(jìn) 024 #ac cd# 移進(jìn)0244 #acc d# 移進(jìn)024410 #accd # 移進(jìn)02448 #accA # 用Ad歸約0248 #acA # 用AcA歸約026 #aA # 用AcA歸約01 #E # 用EaA歸約第六章 屬性文法和語法制導(dǎo)翻譯思考題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.