整理完編譯原理網(wǎng)上作業(yè)題

1、東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院編譯原理網(wǎng)上作業(yè)題第一章 編譯概述一、多項(xiàng)選擇題：1. 編譯程序各階段的工作都涉及到（）。（*）A. 語法分析 B. 表格管理 C. 出錯(cuò)處理 D. 語義分析 E. 詞法分析2. 編譯程序工作時(shí)，通常有（）階段。 （*）A. 詞法分析 B. 語法分析 C. 中間代碼生成 D. 語義檢查 E. 目標(biāo)代碼生成二、填空題：1解釋程序和編譯程序的區(qū)別在于（）。（*）2編譯過程通?？煞譃?5 個(gè)階段，分別是（）、（）、（）、（）和（ ）生成。（*）3編譯程序工作過程中，第一段輸入是（），最后階段的輸出為（）程序。（*）4編譯程序是指將（）程序翻譯成（）程序的程序。（*）三、綜合題

2、：1. 畫出編譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。（*）第二章 文法和語言的基本知識、多項(xiàng)選擇題：1.下面哪些說法是錯(cuò)誤的（）。（*）A. 有向圖是一個(gè)狀態(tài)轉(zhuǎn)換圖B. 狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖C. 有向圖是一個(gè) DFAD.DFA 可以用狀態(tài)轉(zhuǎn)換圖表示2. 對無二義性文法來說，一棵語法樹往往代表了（）。（*）A. 多種推導(dǎo)過程B.多種最左推導(dǎo)過程C. 一種最左推導(dǎo)過程D.僅一種推導(dǎo)過程E. 一種最左推導(dǎo)過程3. 如果文法 G 存在一個(gè)句子，滿足下列條件（）之一時(shí)，則稱該文法是二義文法。A. 該句子的最左推導(dǎo)與最右推導(dǎo)相同B. 該句子有兩個(gè)不同的最左推導(dǎo)C. 該句子有兩棵不同的最右推導(dǎo) D.

3、該句子有兩棵不同的語法樹E. 該句子的語法樹只有一個(gè)4. 有一文法G: St ABAt aAb| ecBd| e它不產(chǎn)生下面（）集合 （*）A.a nbmcsup >ndm|n,m0B.a nbn csup>mdm |n,m >0C.anbmcsup>mdn|n,m> 0D.anbncsup>mdm|n,m> 0E.anbncsup>ndm|n,n > 05. 自下而上的語法分析中，應(yīng)從（）開始分析。 （*）A. 句型 B. 句子 C. 以單詞為單位的程序 D. 文法的開始符 E. 句柄6. 對正規(guī)文法描述的語言，以下（）有能力描述它。 （

4、*）A.0 型文法 B.1 型文法 C. 上下文無關(guān)文法 D. 右線性文法 E. 左線性文法二、填空題：1文法中的終結(jié)符和非終結(jié)符的交集是（）。詞法分析器交給語法分析器的文法符號一定是（），它一定只出現(xiàn)在產(chǎn)生式的（）部。（*）2最左推導(dǎo)是指每次都對句型中的（）非終結(jié)符進(jìn)行擴(kuò)展。（*）3在語法分析中，最常見的兩種方法一定是（）分析法，另一是（）分析法。（*）4采用（）語法分析時(shí)，必須消除文法的左遞歸。（*）5（）樹代表推導(dǎo)過程，（ ）樹代表歸約過程。（*）6自下而上分析法采用（）、歸約、錯(cuò)誤處理、（）等四種操作。（*）7. Chomsky把文法分為（）種類型，編譯器構(gòu)造中采用（）和（ ）文法，它

5、們分別產(chǎn)生（）和（ ）語言，并分別用（）和（ ）自動(dòng)機(jī)識別所產(chǎn)生的語言。（*）三、判斷題：1 文法 StaS|bR| eFTcS。描述的語言是（a|bc） * （*）2. 在自下而上的語法分析中，語法樹與分析樹一定相同。（*）3. 二義文法不是上下文無關(guān)文法。（*）4. 語法分析時(shí)必須先消除文法中的左遞歸。（*）5. 規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（*）6. 一個(gè)文法所有句型的集合形成該文法所能接受的語言。（*）7. 有窮自動(dòng)機(jī)接受的語言是正則語言。（*）&若r1和r2是上的正規(guī)式，則 r1|r2也是。（*）9. 令2 = a,b，則工上所有以b為首的字構(gòu)成的正規(guī)集的正規(guī)式為b*

6、（a|b）* 。（*）四、簡答題1 . 句柄:（*）2. 素短語：（*）3. 語法樹：（*）4. 歸約：（*）5. 推導(dǎo)：（*）五、問答題1. 給出上下文無關(guān)文法的定義。（*）2. 文法 GS ：St aSPQ|abQQi PQbPtbbbQtbccQtcc（1）它是Chomsky哪一型文法？（ 2）它生成的語言是什么？（*）3. 按指定類型，給出語言的文法。L=aibj|j >i > 1的上下文無關(guān)文法。（*）4. 有文法 G： St aAcB |BdAtAaB|cBtbScA|b( 1)試求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄；( 2)寫出句子 acabcb

7、bdcc 的最左推導(dǎo)過程。(*)5. 對于文法 GS ：St（ l） |aS|aLtL, S|S（1）畫出句型（S, （a）的語法樹。（ 2）寫出上述句型的所有短語、直接短語、句柄和素短語。（*）6. 考慮文法 GS, 其產(chǎn)生式如下 :S(L)|aLtL, S|S(a) 試指出此文法的終結(jié)符號、非終結(jié)符號。(b) 給出句子(a,(a，a)的分析樹。(c) 構(gòu)造句子(a,(a，a)的一個(gè)最左推導(dǎo)。(d) 構(gòu)造句子(a,(a，a)的一個(gè)最右推導(dǎo)。(e) 這個(gè)文法生成的語言是什么？ (*)7考慮文法 GT ：TtT*F|FFtFf P|PPt( T) |i證明T*Pf( T*F)是該文法的一個(gè)句型，

8、并指出直接短語和句柄。(*)8試描述下列文法產(chǎn)生的語言L(GS)(*)St10S0|aA AtbA|a9.已知語言L(G)=ab nc |n > 1試對該語言構(gòu)造相應(yīng)文法。(*)10證明下列文法的二義性(*)1 . GZ2. GSZtaZbZ|aZ|aStABAtbB|bC|baBtSb|ba|aCtBb|b11 .有文法 GS : StiSeS|iS|i該文法是否是二義的。試證明之。（*）12. 文法 GT : Tt aR FH Tb|d 生成的語言是什么？GT是否為3型文法？ （*）13. 試寫出能夠描述下列電話號碼格式的文法。 （*）6739174201

9、0)6739174214. 試構(gòu)造生成語言的上下文無關(guān)文法。 （*）（1） a nbnci | n > 1,i > 0 （2） w | w a,b且w中a的個(gè)數(shù)恰好比 b多1 GS:S -> S AND S | S OR15. 下面的二義性文法描述命題演算公式，為它寫一個(gè)等價(jià)的非二義性文法。S | NOT S | p | q | (S)(*)16. 對于下列語言分別寫出它們的正規(guī)表達(dá)式。（*）（1）英文字母組成的所有符號串，要求符號串中順序包含五個(gè)元音。（2）英文字母組成的所有符號串，要求符號串中的字母依照詞典順序排列。第三章一、多項(xiàng)選擇題：詞法分析與有窮自動(dòng)機(jī)1. 在詞法分

10、析中，能識別出（）。（*）A.基本字 B.四元式C.運(yùn)算符D.逆波蘭式 E.常數(shù)2. 令刀=a,b,則刀上所有以 b開頭，后跟若干個(gè) ab的字的全體對應(yīng)的正規(guī)式為(* + * +A.b(ab) * B.b(ab) + C.(ba) *b D.(ba) +bE.b(a|b)、填空題：1確定有限自動(dòng)機(jī) DFA是(2若二個(gè)正規(guī)式所表示的()的一個(gè)特例。(*)相同，則認(rèn)為二者是等價(jià)的。(*)3一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由()所 ()。(*)三、判斷題：1一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)惟一終態(tài)。()2設(shè) r 和 s 分別是正規(guī)式，則有 L( r|s ) =L(r)|L(s)。()3. 自動(dòng)機(jī)M和

11、M的狀態(tài)數(shù)不同，則二者必不等價(jià)。()4確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識別正規(guī)集。()5. 對任意一個(gè)右線性文法G,都存在一個(gè) NFA M滿足L(G)=L(M)。()6. 對任意一個(gè)右線性文法G,都存在一個(gè) DFA M滿足L(G)=L(M)。()7. 對任何正規(guī)表達(dá)式 e,都存在一個(gè) NFA M滿足L(G)=L(e)。() &對任何正規(guī)表達(dá)式 e,都存在一個(gè) DFA M滿足L(G)=L(e)。()9. 設(shè)M是一個(gè)NFA并且L(M) =x,y,z，則M的狀態(tài)數(shù)至少為 4個(gè)。()10. 對任何一個(gè) NFA M 都存在一個(gè) DFA M'，使得L(M')=L(M)。()

12、四、綜合題：1. 設(shè)M=( x,y, a,b, f,x,y)為一非確定的有限自動(dòng)機(jī)，其中 f定義如下:f (x,a ) = x,y f (a,b ) = yf (y,a )=0 f (y,b ) = x,y試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M。(*)2. 對給定正規(guī)式 b* (d|ad ) ( b|ab ) +，構(gòu)造其 NFAMI (*)3. 字母表a , b上的正規(guī)式 R= ( ba|a ) *，構(gòu)造R的相應(yīng)DFA (*)4. 請寫出在刀=(a,b )上，不是a開頭的，但以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式，并構(gòu)造與之等價(jià)狀 態(tài)最少的 DFAI(*)5. 人運(yùn)狼、羊、菜過河，一次運(yùn)一件，不讓羊吃掉菜，

13、也不讓狼吃掉羊，畫出渡河的狀態(tài)轉(zhuǎn)換圖?？煞駥⑵涑橄鬄橐粋€(gè)有限自動(dòng)機(jī)。（*）6. 對于正規(guī)表達(dá)式b） a（a|b）構(gòu)造最小狀態(tài)的 DFA （*）第四章語法分析一、多項(xiàng)選擇題：1. 一個(gè)LR分析器包括（）。(*)A. 一個(gè)總控程序B. 一個(gè)項(xiàng)目集C. 一個(gè)活前綴D. 一張分析表 E. 一個(gè)分析棧2.LR分析器核心部分是一張分析表，該表包括（）等子表。（*）A.LL（1）分析 B.優(yōu)先關(guān)系 C.GOTO D.LR E.ACTION3. 每一項(xiàng)ACTIONS a所規(guī)定的動(dòng)作包括（）。（*）A.移進(jìn) B.比較 C.接受 D.歸約 E.報(bào)錯(cuò)4. 對LR分析表的構(gòu)造，有可能存在（）動(dòng)作沖突。（*）A.移進(jìn)

14、B.歸約 C.移進(jìn)/歸約D.移進(jìn)/移進(jìn)E.歸約/歸約5. 對LR分析器來說，存在（）等分析表的構(gòu)造方法。（*）A.LALR B.LR (0)C.SLR (1) D.SLR (0)E.LR (1)6. 自上而下的語法分析方法有（）。（*）A.算符優(yōu)先分析法B.LL (1)分析法 C.SLR (1)分析法D丄R ( 0)分析法 E.LALR (1)分析法、填空題:1.對于一個(gè)文法，如果能夠構(gòu)造文法。（*）（）。使得它的）均是唯一確定的，則稱該文法為LR2. 字的前綴是指該字的（）。（*）3. 活前綴是指 （）的一個(gè)前綴，這種前綴不含（）之后的任何符號。（*）4. 在LR分析過程中，只要（）的已掃描

15、部分保持可歸約成一個(gè)（），則掃描過的部分正確。5. 將識別（）的NFA確定化，使其成為以 （）為狀態(tài)的DFA這個(gè)DFA就是建立 （）的基礎(chǔ)。（*）6. Aa稱為（）項(xiàng)目；對文法開始符 S'fa為（）項(xiàng)目；若a為終結(jié)符，則稱Aaa 3為（）項(xiàng)目；若B為非終結(jié)符，則稱 Aaa3為（）項(xiàng)目。（*）7. LR（ 0）分析法的名字中“ L”表示 （），“ R'表示 （），“ 0”表示 （）。三、判斷題：1對一個(gè)右線性文法 G,必存在一個(gè)左線性文法 G'，使得L（G）=L（G'），反之亦然。（*）四、綜合題：1. 構(gòu)造下面文法的 LL( 1)分析表。 (*)D TLTt i

16、nt | realLt id RFT, id R |&2. 下面文法 GS 是否為 LL( 1)文法？說明理由。(*)STAB|PQxATxyBTbcPTdP| &QTaQ|&3. 設(shè)有以下文法： （*）GS ：STaAbDe|dATBSD|eBTSAc|cD| &DT Se| &（1 ）求出該文法的每一個(gè)非終結(jié)符U的FOLLO噪。（ 2）該文法是 LL（ 1）文法嗎？（3）構(gòu)造 CS 的 LL（ 1）分析表。4. 將文法 GV 改造成為 LL（1） 的。（*）GV ：VTN|NEETV|V+ENRi5. 已知文法：（*）GA ： AaAa| &

17、（ 1）該文法是 LL（ 1）文法嗎？為什么？（ 2）若采用 LL（ 1）方法進(jìn)行語法分析，如何得到該文法的LL （ 1）分析表？（3）若輸入符號串“ aaaa”，請給出語法分析過程。6. 設(shè)有文法 GS 為：（*）St a|b|（A）At SdA|S（ 1）完成下列算符優(yōu)先關(guān)系表，見下表，并判斷GS 是否為算符優(yōu)先文法。表 算符優(yōu)先關(guān)系表（2）給出句型（SdSdS的短語、簡單短語、句柄、素短語和最左素短語。（3）給出輸入串（adb） #的分析過程。7. 設(shè)有文法 GS 為：（*）Sta|b|（A）AtSdA|S（ 1）完成下列算符優(yōu)先關(guān)系表，見下表，并判斷GS 是否為算符優(yōu)先文法。表 算符優(yōu)

18、先關(guān)系表(2) 給出句型(SdSdS的短語、簡單短語、句柄、素短語和最左素短語。(3) 給出輸入串( adb) #的分析過程。&對于文法GS : StAS|bA SA|a(1) 列出所有 LR (0)項(xiàng)目；(2) 列出構(gòu)成文法LR (0)項(xiàng)目集規(guī)范族。(*)9有文法 GSSta| A | ( T)TtT, S|S該文法是否是 LL (1)文法，若不是，請進(jìn)行改寫。并給出它的分析表。(*)10有文法 GS( 1 )StA( 2)StB( 3)At aAb( 4 ) Atc( 5)Bt aBb( 6)Btd試構(gòu)造相應(yīng)的 LR( 0)項(xiàng)目集規(guī)范族及相應(yīng)的分析表。(*)11. 已知文法 GS

19、，其產(chǎn)生式如下：St （L）|aLt L , S|S從GS中消除左遞歸，并為之構(gòu)造一個(gè)非遞歸預(yù)測分析器LL（1）分析表。請說明在句子（a , （a ,a）上的分析器的動(dòng)作。（*）12. 證明下面文法是 SLR（1）文法，并構(gòu)造其 SLR分析表。Et E+T |TTt TF|FFt F*|a|b第五章一、多項(xiàng)選擇題：語法制導(dǎo)翻譯技術(shù)和中間代碼生成1. 中間代碼主要有（）。（*）A. 四元式 B. 二元式 C. 三元式 D. 后綴式 E. 間接三元式2. 在下面的（）語法制導(dǎo)翻譯中，采用拉鏈 - 回填技術(shù)。（*）A.賦值語句B.goto 語句C.條件語句D.循環(huán)語句3. 下列（ ）中間代碼形式有益

20、于優(yōu)化處理。（*）A.三元式 B.四元式C.間接三元式D.逆波蘭表示法E.樹形表示法4. 在編譯程序中安排中間代碼生成的目的是（）。（*）A.便于進(jìn)行存儲空間的組織B.利于目標(biāo)代碼的優(yōu)化C.利于編譯程序的移植D.利于目標(biāo)代碼的移植E.利于提高目標(biāo)代碼的質(zhì)量5. 三地址代碼語句具體實(shí)現(xiàn)通常有（）表示方法。（*）A.逆波蘭表示B.三元式C.間接三元式D.樹形表示 E.四元式填空題：1中間代碼有 （）、（）、（）、（） 等形式， 生成中間代碼主要是為了使 （）( ) 時(shí)才能確定，因而) 。(*)串進(jìn)行 ()。(*)3當(dāng)源程序中的標(biāo)號出現(xiàn)“先引用后定義”時(shí)，中間代碼的轉(zhuǎn)移地址須持 要進(jìn)行 ()。(*)

21、4文法符號的屬性有兩種，一種稱為( ) ，另一種稱為 (5后綴式 abc-/ 所代表的表達(dá)式是()，表達(dá)式 (a-b)*c 可用后綴式()表示。(*)6用一張 () 輔以 () 的辦法來表示中間代碼，這種表示法稱為間接三元式。(*)三、問答題：1給出下列表達(dá)式的逆波蘭表示(后綴式)：(*) a*(-b+c) (A V B) A (C DA E)2 寫出算術(shù)表達(dá)式：A+B*(C-D)+E/(C- D)f N 的：(*) 四元式序列； 三元式序列； 間接三元式序列3. 寫出下面算術(shù)表達(dá)式E值的語義描述：(*)12(1) EE +E(2) 0(3) 14. 給出下列表達(dá)式的逆波蘭表式。(*)(1)

22、aw b+cA a> d V a+be( 2) a=cA b=d( 3)( a*b-c ) *n+b* ( a+d/e )5. 分別寫出語句 a:=b*-c+b*-c 的四元式、三元式和間接三元式的表示。 (*)6. 文法及其翻譯方案為：P:=bQb print:”1” Q:=cR print:”2”Q:=a print:” 3” R:=Qad print:”4”當(dāng)輸入串為bccaadadb時(shí)，該翻譯方案的輸出是什么？ （*）7. 給定文法 GE :E:=T+E | T T:=F*T | F F:=i | (E)則求 i+i+(i*i)*i 的逆波蘭表示。 (*)第六章 符號表的組織和管

23、理一、多項(xiàng)選擇題：1. 符號表的每一項(xiàng)均包含（ ）。（*）A. 名字欄B. 類型欄C.信息欄D.值欄 E.ad均包含2. 對編譯程序所用到的符號表，涉及的操作有（A. 填寫或更新信息欄內(nèi)容D. 雜湊技術(shù)E.B. 填入新名C.給定名字，訪問它的有關(guān)信息線性表和排序二叉樹3. 源程序中的錯(cuò)誤一般有（）。（*）A. 詞法錯(cuò)誤 B .語法錯(cuò)誤C .語義錯(cuò)誤D. 編譯錯(cuò)誤E .違反環(huán)境限制的錯(cuò)誤、填空題：1符號表中名字欄內(nèi)容有兩種填寫方式，它們是） 填寫和 （）填寫。（*） 的辦法糾正錯(cuò)誤。（*）2詞法分析階段的錯(cuò)誤主要是（） ，可通過 （）和（）過程中陸續(xù)填入。（*）3符號表中名字的有關(guān)信息在4在目標(biāo)

24、代碼生成階段，符號表是（ ） 的依據(jù)。（*）三、簡答題：1在編譯過程中為什么要建立符號表？（*）2. 一個(gè)過程的活動(dòng)記錄中一般包含那些數(shù)據(jù)。 （*）第七章一、多項(xiàng)選擇題：運(yùn)行時(shí)的存儲組織與管理1. 下面（ ）需要在運(yùn)行階段分配存儲空間。（*）A.數(shù)組 B.指針變量C.動(dòng)態(tài)數(shù)組D.靜態(tài)變量E.動(dòng)態(tài)變量2. 棧式動(dòng)態(tài)分配允許（）。（*）A.遞歸過程B.分程序結(jié)構(gòu)C.動(dòng)態(tài)變量D.動(dòng)態(tài)數(shù)組 E.靜態(tài)數(shù)組3. 動(dòng)態(tài)存儲分配可采用的分配方案有（）。（*）A.隊(duì)式存儲分配B.棧式存儲分配C.鏈?zhǔn)酱鎯Ψ峙銬.堆式存儲分配E.線性存儲分配4. 棧式動(dòng)態(tài)分配與管理因調(diào)用而進(jìn)入過程之后，要做的工作是（）。（*）A.

25、 定義新的活動(dòng)記錄的 SP B. 保護(hù)返回地址C. 傳遞參數(shù)值D.建立DISPLAY表E.定義新的活動(dòng)記錄的 TOP5. 靜態(tài)分配不允許程序出現(xiàn)（）。（*）A.遞歸過程B.靜態(tài)數(shù)組C.可變體積的數(shù)據(jù)項(xiàng)目D.待定性質(zhì)的名字E.靜態(tài)變量6. 活動(dòng)記錄包括（ ）。（*）A.局部變量B.連接數(shù)據(jù)C.形式單元D.局部數(shù)組的內(nèi)情變量E.臨時(shí)工作單元第八章 目標(biāo)代碼生成一、多項(xiàng)選擇題：1. 根據(jù)優(yōu)化所涉及的范圍，可將優(yōu)化分為（）。（*）A.局部優(yōu)化B.過程優(yōu)化C.全局優(yōu)化 D.循環(huán)優(yōu)化 E.四元式優(yōu)化2. 下列優(yōu)化中，屬于循環(huán)優(yōu)化的有（）。（*）E.代碼外提A.強(qiáng)度削弱B.合并已知量C.刪除無用賦值D.刪除

26、歸納變量3. 如果ab是程序流圖中的一條邊，則由這條回邊構(gòu)成的循環(huán)由（）結(jié)點(diǎn)組成。（*）A.a B.bC.有通路到達(dá)b的結(jié)點(diǎn)D. 有通路到達(dá)a且該通路上不經(jīng)過 b的結(jié)點(diǎn)E.有通路到達(dá)b且該通路上不經(jīng)過 a的結(jié)點(diǎn)4.采用無環(huán)有向圖（DAG，可以實(shí)現(xiàn)的優(yōu)化有（）。（*）A.合并已知量B.刪除公共子表達(dá)式C.強(qiáng)度削弱D.刪除無用賦值 E.刪除歸納變量5.編譯程序的輸出結(jié)果可以是（）。（*）A.目標(biāo)代碼B.匯編語言代碼C.中間代碼D.優(yōu)化后的中間代碼E.可重定位代碼二、填空題:1.局部優(yōu)化是（范圍內(nèi)進(jìn)行的一種優(yōu)化。（*）2 在一個(gè)基本塊內(nèi)，可實(shí)行3種優(yōu)化方法，即合并已知量、)° (*)3 優(yōu)

27、化就是對程序進(jìn)行各種（）變換，使之能生成更有效的*)4.在優(yōu)化中，可把循環(huán)中的）提到循環(huán)外面去，這種方法稱為)° (*)東北農(nóng)業(yè)大學(xué)網(wǎng)絡(luò)教育學(xué)院編譯原理作業(yè)題參考答案第一章 編譯概述多項(xiàng)選擇題：1. 編譯程序各階段的工作都涉及到（BC）。（*）A.語法分析B.表格管理C.出錯(cuò)處理 D.語義分析E.詞法分析2. 編譯程序工作時(shí)，通常有（ ABCE階段。 （*）A.詞法分析B.語法分析C.中間代碼生成 D.語義檢查E.目標(biāo)代碼生成填空題:1 解釋程序和編譯程序的區(qū)別在于（是否生成目標(biāo)程序）。（*）2 編譯過程通?？煞譃?5個(gè)階段，分別是（詞法分析）、（語法分析）、（中間代碼生成）、（代碼

28、優(yōu) 化）和（目標(biāo)代碼）生成。（*）3編譯程序工作過程中，第一段輸入是（源程序），最后階段的輸出為（目標(biāo)代碼生成）程序。（*）4編譯程序是指將（高級語言編寫的）程序翻譯成（目標(biāo)語言）程序的程序。（*）綜合題:1. 畫出編譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。（*） 解答：編譯程序的總體結(jié)構(gòu)如下圖所示：詞法分析程序：輸入源程序，進(jìn)行詞法分析，輸出單詞符號。語法分析程序：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則（方法規(guī)則）把單詞符號串分解成各類語 法單位，并判斷輸入串是否構(gòu)成語法上正確的“程序”。中間代碼生成程序：按照語義規(guī)則把語法分析程序歸約（或推導(dǎo)）出的語法單位翻譯成一定形式的中 間代碼，比如

29、說四元式。優(yōu)化程序：對中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成程序：把中間代碼翻譯成目標(biāo)語言程序。表格管理模塊保存一系列的表格，登記源程序的各類信息和編譯各階段的進(jìn)展情況。編譯程序各階段 所產(chǎn)生的中間結(jié)果都記錄在表格中，所需信息多數(shù)都需從表格中獲取，整個(gè)編譯過程中都在不斷地和表格 打交道。出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。此外，編譯的各個(gè)階段都可能出現(xiàn)錯(cuò)誤。出錯(cuò)處理 程序?qū)Πl(fā)現(xiàn)的錯(cuò)誤都及時(shí)進(jìn)行處理。第二章文法和語言的基本知識多項(xiàng)選擇題：1. ABC 2. ACE 3. BCD 4. AC 5. BC填空題:1文法中的終結(jié)符和非終結(jié)符的交集是（空集）。詞法分析器交給語法分析器的文法符號一定是

30、（終結(jié)符），它一定只出現(xiàn)在產(chǎn)生式的（右）部。（*）2最左推導(dǎo)是指每次都對句型中的（最左）非終結(jié)符進(jìn)行擴(kuò)展。（*）3在語法分析中，最常見的兩種方法一定是（自上而上）分析法，另一是（自下而上）分析法。（*）4采用（自上而下）語法分析時(shí)，必須消除文法的左遞歸。（*）5. （語法）樹代表推導(dǎo)過程，（分析）樹代表歸約過程。（*）6自下而上分析法采用（移進(jìn)）、歸約、錯(cuò)誤處理、（接受）等四種操作。（*）7. Chomsky把文法分為（4）種類型，編譯器構(gòu)造中采用（2型）和（3型）文法，它們分別產(chǎn)生（上下文無關(guān)語言）和（正規(guī)語言）語言，并分別用（下推自動(dòng)機(jī)）和（有限）自動(dòng)機(jī)識別所產(chǎn)生的語言。（*）判斷題：1正

31、確 2 .錯(cuò)誤 3 .錯(cuò)誤 4 .錯(cuò)誤 5 .錯(cuò)誤6. 錯(cuò)誤7 .正確 8 .正確 9 .錯(cuò)誤簡答題1句柄：（*） 解答：一個(gè)句型的最左直接短語稱為該句型的句柄。2. 素短語：（*）解答：至少含有一個(gè)終結(jié)符的素短語， 并且除它自身之外不再含任何更小的素短語。3. 語法樹：（*）解答：滿足下面 4 個(gè)條件的樹稱之為文法 GS 的一棵語法樹。 每一終結(jié)均有一標(biāo)記，此標(biāo)記為VNU Vt中的一個(gè)符號； 樹的根結(jié)點(diǎn)以文法 GS的開始符S標(biāo)記； 若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為Vn中的一個(gè)符號； 若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有 K個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為X,X2,Xk,

32、貝U AX1,X2,Xk, 必然是G的一個(gè)產(chǎn)生式。4. 歸約：（*）解答：我們稱 仏丫直接歸約出a AB,僅當(dāng)Ay是一個(gè)產(chǎn)生式，且a、B （VnU Vt） *。歸約過程就是從輸入串開始，反復(fù)用產(chǎn)生式右部的符號替換成產(chǎn)生式左部符號，直至文法開始符。5. 推導(dǎo)：（*）解答：我們稱 a A3直接推出aY3, 即卩a A3 TayB，僅當(dāng)丫是一個(gè)產(chǎn)生式，且 a、B (VnUVt)。如果a 1二：a 2二二：an,則我們稱這個(gè)序列是從 a 1至a 2的一個(gè)推導(dǎo)。若存在一個(gè)從 a 1 a n的 推導(dǎo)，則稱a 1可推導(dǎo)出a n。推導(dǎo)是歸約的逆過程。問答題1 .給出上下文無關(guān)文法的定義。(*)解答：一個(gè)上下文

33、無關(guān)文法 G是一個(gè)四元式(Vt,Vn,S, P )，其中： Vt是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號； Vn是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號，VtQVn=； S是一個(gè)非終結(jié)符號，稱為開始符號； P是一個(gè)產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式的形式是ia,其中，PV N,a (VtUVn)*。開始符號S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2. 文法 GS:St aSPQ|abQQP PQbPr bbbCH bc cCH cc(1) 它是Chomsky哪一型文法？(2) 它生成的語言是什么？ (*)解答：(1)由于產(chǎn)生式左部存在終結(jié)符號，且所有產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式右部的符

34、號長 度，所以文法GS是Chomsky1型文法，即上下文有關(guān)文法。(2)按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低(否則無法推出句子)，我們可以得到：S abQ abcS 二；aSPQ二 aabQPg aabPQG； aabbQ沖：aabbcQ 二 aabbccS 二：aSPQ二 aaSPQP中 aaabQPQP生 aaabPQQPA aaabPQPQQ' aaaPPQQQ aaabbPqqq= aaabbQQF aaabbbcQQ二 aaabbbccQ 二 aaabbbccc于是得到文法 GS生成的語言L=a nbncn|n > 13. 按指定類型，給出語言的文法。L=aibj|j

35、>i > 1的上下文無關(guān)文法。(*)解答:由L=ai bj |j >i > 1知，所求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有StaSb型產(chǎn)生式，以保證 b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次，還需有 St Sb或St bS型的產(chǎn)生式，用以保證 b的個(gè)數(shù)多于a的個(gè)數(shù)；也即 所求上下文無關(guān)文法 GS為：GS : StaSb|Sb|b4. 有文法 G: St aAcB|BdAt AaB|c Bt bScA|b(1) 試求句型 aAaBcbbdcc和aAcbBdcc的句柄；(2) 寫出句子 acabcbbdcc的最左推導(dǎo)過程。(*) 解答：(1 )分別畫出對應(yīng)兩句型的語法樹，如下圖所示句柄:

36、AaB BdS(2)句子acabcbbdcc的最左推導(dǎo)如下:ST 二 aAcB= aAaBcB 二 acaBcB 二 acabcB = acabcbScA 二 acabcbBdcA= acabcbbdcA 二 acabcbbdcc5. 對于文法GS:St( L) |aS|aLt L, S|S(1) 畫出句型(S, (a)的語法樹。(2) 寫出上述句型的所有短語、直接短語、句柄和素短語。(*)解答：(1)句型(S, ( a)的語法樹如下圖所示。(L )a圖句型(S, (a)的語法樹(2)由上圖可知: 短語：S、a、(a)、S,(a)、(S,(a); 直接短語：a、S; 句柄：S; 素短語：素短語

37、可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即;a) A#因此素短語為a。6. 考慮文法GS,其產(chǎn)生式如下：St (L)|aLtL, S|S(a) 試指出此文法的終結(jié)符號、非終結(jié)符號。(b) 給出句子(a,(a , a)的分析樹。(c) 構(gòu)造句子(a,(a , a)的一個(gè)最左推導(dǎo)。(d) 構(gòu)造句子(a,(a , a)的一個(gè)最右推導(dǎo)。(e) 這個(gè)文法生成的語言是什么？ (*)解答：(a)終結(jié)符號為：(,),a,',非終結(jié)符號為：S,L開始符號為：S(b)分析樹(L)Sa(S'E)(s's)(a,(L)(a,(L,S)(a,(S,S)(a,(a,S)(d)(a,(a,a

38、)(L)(L,S)(L,(L)(L,(L,S)(L,(L,a)(L,(S,a)(L,(a,a)(S,(a,a)(a,(a,a)(e) L(GS) = ( a i, a 2, a n)或 a其中a i(1 w i w n)是L(GS)。即L(GS)產(chǎn)生一個(gè)以a為原子的純表，但不包括空表。 7考慮文法 GT ：TF *F|FFtFf P|PP( T) |i證明T*Pf( T*F)是該文法的一個(gè)句型，并指出直接短語和句柄。(*)解答：首先構(gòu)造T*Pf( T*F)的語法樹如下圖所示。TF圖句型T*Pf( T*F)的語法樹由上圖可知，T*Pf( T*F)是文法GT的一個(gè)句型。直接短語有兩個(gè)，即P和T*F

39、 ;句柄為P。&試描述下列文法產(chǎn)生的語言L( GS)(*)St 10S0|aAAt bA|a解答：L(G)=(10) iabna0in0 i > 09.已知語言L(G)=ab nc |n > 1試對該語言構(gòu)造相應(yīng)文法。(*)解答：GZ:Zt aBCBt Bb|b10.證明下列文法的二義性(*)1. GZ2. GSZt aZbZ|aZ|aSt ABat bB|bC|baBt Sb|ba|aCt Bb|b解答：(1)對于句子aaaba,畫出二棵不同的語法樹，因而是二義的。（2）GS對于句子baba,畫出二棵不同的語法樹，因而是二義的。11 .有文法 GS : StiSeS|iS

40、|i該文法是否是二義的。試證明之。（*）解答:對于句子 iiiei ，有兩棵不同的語法樹，故文法是二義的。12. 文法 GT :aR FH Tb|d 生成的語言是什么？GT是否為3型文法？ （*）解答：不是 3 型文法。13. 試寫出能夠描述下列電話號碼格式的文法。(*)67391742010-67391742(010)67391742解答： 文法產(chǎn)生式規(guī)則如下：<電話號碼 > t <局代碼 > <本機(jī)碼 ><電話號碼 >t <區(qū)前綴 > <局代碼> < 本機(jī)碼 ><區(qū)前綴 >t< 地區(qū)碼 &

41、gt;<區(qū)前綴 >t('< 地區(qū)碼 >)'<地區(qū)碼 >tDIGDIG<地區(qū)碼 >tDIGDIGDIG<局代碼 >tDIGDIGDIG DIG<本機(jī)碼 >tDIGDIGDIGDIG16. 試構(gòu)造生成語言的上下文無關(guān)文法。 (*)(1) a nbnci | n > 1,i > 0 (2) w | w a,b +,且w中a的個(gè)數(shù)恰好比 b多1 解答：(1)把a(bǔ)nbnci分成anbn和c，兩部分，分別由兩個(gè)非終結(jié)符號生成，因此，生成此文法的產(chǎn)生式為:S t ABA t aAb|abB t cB| e（2

42、）令S為開始符號，產(chǎn)生的 w中a的個(gè)數(shù)恰好比b多一個(gè)，令E為一個(gè)非終結(jié)符號，產(chǎn)生含相同個(gè) 數(shù)的a和b的所有串，則產(chǎn)生式如下：S t aE|Ea|bSS|SbS|SSbE t aEbE|bEaE| £GS:S -> S AND S | S OR17. 下面的二義性文法描述命題演算公式，為它寫一個(gè)等價(jià)的非二義性文法。S | NOT S |p | q | （S）（*）解答：GS:S -> S AND A | AA -> A OR B | BB -> NOT B |p | q | （S）16.對于下列語言分別寫出它們的正規(guī)表達(dá)式。（*）（1）英文字母組成的所有符號串，

43、要求符號串中順序包含五個(gè)元音。（2）英文字母組成的所有符號串，要求符號串中的字母依照詞典順序排列。解答：（1） 令Letter表示除這五個(gè)元音外的其它字母。(letter)*A(letter)*E(letter)*l(letter)*O(letter)*U(letter)*(2)A*B*.Z*第三章詞法分析與有窮自動(dòng)機(jī)多項(xiàng)選擇題：1. ACE 2. ABD填空題：1.確定有限自動(dòng)機(jī) DFA是（NFA ）的一個(gè)特例。（*）2 若二個(gè)正規(guī)式所表示的（正規(guī)集）相同，則認(rèn)為二者是等價(jià)的。（*）3.個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由（DFA/NFA）所 （識別）。（*）判斷題：1.錯(cuò)誤2 .錯(cuò)誤3 .錯(cuò)誤4

44、 .正確5 .正確6.正確 7 .正確 8 .正確 9 .錯(cuò)誤 10 .正確綜合題：)為一非確定的有限自動(dòng)機(jī)，其中 f 定義如下：1 設(shè) M=( x,y, a,b, f,x,yf ( x,a )= x,y f( a,b )= yf (y,a )=0 f (y,b ) = x,y試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M。(*)解答：對照自動(dòng)機(jī)的定義 M=(S,X ,f,S o,Z),由f的定義可知f(x,a) 、f(y,b)均為多值函數(shù)，所以是一非 確定有限自動(dòng)機(jī)，先畫出NFAM相應(yīng)的狀態(tài)圖，如圖下所示。圖 NFAM用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣下表所示。將轉(zhuǎn)換矩陣中的所有子集重新命名而形成下表所示的狀態(tài)轉(zhuǎn)換矩陣

45、。表狀態(tài)轉(zhuǎn)換矩陣即得到M），其狀態(tài)轉(zhuǎn)換圖如下圖所示。=(0,1,2, a,b, f,0, 1,2將上圖的DFAM最小化。首先，將 M的狀態(tài)分成終態(tài)組1 , 2與非終態(tài)組0;其次，考察1,2由于 1,2a=1,2b=2 即整個(gè)劃分只有兩組 0 后，得到如下圖所示化簡1,2 ， 所以不再將其劃分了，也1,2 ：令狀態(tài) 1 代表1,2 ，即把原來到達(dá) 2 的弧都導(dǎo)向 1，并刪除狀態(tài) 2。 最DFAM?；喓蟮腄FAM2. 對給定正規(guī)式 b* (d|ad ) ( b|ab ) +，構(gòu)造其 NFAMI (*)解答：首先用a=aA改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*;其次，構(gòu)造該正規(guī)式

46、的NFAM如下圖所示。圖 NFAM3. 字母表a , b上的正規(guī)式 R= ( ba|a ) *，構(gòu)造R的相應(yīng)DFA (*)解答：II aI bx1yiy2lyiy22iyIIaI b123223324. 請寫出在刀=(a,b )上，不是a開頭的，但以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式，并構(gòu)造與之等價(jià)狀 態(tài)最少的DFA (*)解答：根據(jù)題意，不以a開頭就意味著以b開頭，且以aa結(jié)尾的正規(guī)式為：b(a|b)* aa根將圖1所示的NFA確定化，如圖2所示。NFA將圖1所示的NFA確定化，如圖從圖2可知已為最簡狀態(tài)，由于開始狀態(tài)0只能輸入字符b而不能與狀態(tài)1合并，而狀態(tài)2和狀態(tài)32所示的狀態(tài)轉(zhuǎn)換矩面對輸

47、入符號的下一狀態(tài)相同，但兩者一為非終態(tài)、一為終態(tài)，故也不有合并，故圖 陣已是最簡的 DFA如圖3所示據(jù)正規(guī)式畫出 NFA如圖1所示。圖 2 狀態(tài)轉(zhuǎn)換矩陣圖 3 最簡 DFA6. 人運(yùn)狼、羊、菜過河，一次運(yùn)一件，不讓羊吃掉菜，也不讓狼吃掉羊，畫出渡河的狀態(tài)轉(zhuǎn)換圖。可否將其抽象為一個(gè)有限自動(dòng)機(jī)。(*)解答：先寫出渡河的方法，串中對象順序?yàn)槿藖砘囟珊訒r(shí)所運(yùn)的貨物的順序： 羊空菜羊狼空羊 羊空狼羊菜空羊現(xiàn)給出一個(gè) NFA:M=(S ,Q,0,9, S )其中=羊，空，菜，狼Q=0,1,2,3,4,5,6,7,8,9轉(zhuǎn)形函數(shù)S （0,羊）=1,S （1,空）=2,S （2,菜）=3,S （2,狼）=5S

48、 （3,羊）=4,S （5,羊）=6,S （4,狼）=7,S （6,菜）=7S （7,空）=8, S （8,羊）=96.對于正規(guī)表達(dá)式 （a|b） *a（a|b） 構(gòu)造最小狀態(tài)的 DFA （*）解答：NFA M: DFA M: 化簡： 中的DFA M中沒有等價(jià)狀態(tài)，因此為最小化的DFA M第四章語法分析多項(xiàng)選擇題：1. AD 2. CE 3. ACDE 4. CE 5. ABCE 6. ACDE填空題：1對于一個(gè)文法，如果能夠構(gòu)造（LR（0）文法）。使得它的（每個(gè)入口）均是唯一確定的，則稱該文法為LR文法。（*）2. 字的前綴是指該字的（任意首部）。（*）3. 活前綴是指（規(guī)范句型）的一個(gè)前綴

49、，這種前綴不含（句柄） 之后的任何符號。（*）4. 在LR分析過程中，只要（輸入串） 的已掃描部分保持可歸約成一個(gè)（活前綴），則掃描過的部分正確。（*）5. 將識別（活前綴）的NFA確定化，使其成為以（項(xiàng)目集合）為狀態(tài)的DFA這個(gè)DFA就是建立 （LR分析算法）的基礎(chǔ)。（*）6. Aa稱為（歸約）項(xiàng)目；對文法開始符S'fa為（接受）項(xiàng)目；若a為終結(jié)符，則稱Aaa 3 為（移進(jìn)） 項(xiàng)目；若B為非終結(jié)符，則稱 Aaa 3為（待約） 項(xiàng)目。（*）7. LR ( 0)分析法的名字中“ L”表示(自左至右分析)R'表示(采用最右推導(dǎo)的逆過程即最左歸約) ，“ 0”表示 (向右查看 0 個(gè)

50、字符) 。(*)判斷題：1. 正確簡答題：綜合題：1構(gòu)造下面文法的 LL (1 )分析表。(*)“ TLTt int | realLt id RFT, id R |&解答： LL( 1)分析表見下表。分析 雖然這個(gè)文法很簡單，我們還是從求開始符號集合和后繼符號集合開始。FIRST( D) =FIRST( T) =int, realFOLLOW( D) =FOLLOW( L)=#FIRST( L) =idFOLLOW( T) =idFIRST( R) = ，,&FOLLOW( R) =#有了上面每個(gè)非終結(jié)符的FIRST集合，填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部a的FIRST(a)就不是

51、件難事了。填表時(shí)唯一要小心的時(shí)，&是產(chǎn)生式RT&右部的一個(gè)開始符號，而 #在 FOLLO( R)中，所以RT&填在輸入符號 #的欄目中。表 LL( 1)分析表2. 下面文法 GS是否為LL ( 1)文法？說明理由。(*)St AB|PQxxybePdP| eQaQ| e解答：該文法不是 LL (1)文法，見下面分析中的說明。分析 只有三個(gè)非終結(jié)符有兩個(gè)選擇。( 1 ) P 的兩個(gè)右部 dP 和 e 的開始符號肯定不相交。(2) Q的兩個(gè)右部aQ和e的開始符號肯定不相交。(3) 對S來說，由于x FIRST(AB)，同時(shí)也有x FIRST(PQx)(因?yàn)镻和Q都可能為空)。所以該文 法不是 LL( 1 )文