編譯原理復(fù)習(xí)題-給學(xué)生(2014)

1、編譯原理復(fù)習(xí)題一、單項(xiàng)選擇題概述部分1構(gòu)造編譯程序應(yīng)掌握 。D A. 源程序 B. 目標(biāo)語(yǔ)言 C. 編譯方法 D. 以上三項(xiàng)都是2編譯程序絕大多數(shù)時(shí)間花在 上。DA. 出錯(cuò)處理 B. 詞法分析 C. 目標(biāo)代碼生成 D. 表格管理3編譯程序是對(duì) 。DA. 匯編程序的翻譯 B. 高級(jí)語(yǔ)言程序的解釋執(zhí)行C. 機(jī)器語(yǔ)言的執(zhí)行 D. 高級(jí)語(yǔ)言的翻譯4. 將編譯程序分成若干“遍”，是為了 。BA. 提高程序的執(zhí)行效率 B. 使程序的結(jié)構(gòu)更為清晰C 利用有限的機(jī)器內(nèi)存并提高機(jī)器的執(zhí)行效率D. 利用有限的機(jī)器內(nèi)存但降低了機(jī)器的執(zhí)行效率詞法分析部分1DFA M(見(jiàn)圖1-1)接受的字集為 。D 圖1-1XY001

2、1A. 以0開(kāi)頭的二進(jìn)制數(shù)組成的集合 B. 以0結(jié)尾的二進(jìn)制數(shù)組成的集合 C. 含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合 D. 含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合 2詞法分析器的輸出結(jié)果是 。CA. 單詞的種別編碼 B. 單詞在符號(hào)表中的位置C. 單詞的種別編碼和自身值 D. 單詞自身值3正規(guī)式M1和M2等價(jià)是指 。CA. M1和M2的狀態(tài)數(shù)相等 B. M1和M2的有向邊條數(shù)相等C. M1和M2所識(shí)別的語(yǔ)言集相等 D. M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等4詞法分析器的加工對(duì)象是 。 C A中間代碼 B單詞 C源程序 D元程序5同正規(guī)式（a|b）*等價(jià)的正規(guī)式為 。D A(a|b)+ Ba*|b* C(ab)*

3、 D(a*|b*)+6. 兩個(gè)DFA等價(jià)是指： 。 DA. 這兩個(gè)DFA的狀態(tài)數(shù)相同B. 這兩個(gè)DFA的狀態(tài)數(shù)和有向弧條數(shù)都相等C. 這兩個(gè)DFA的有向弧條數(shù)相等D. 這兩個(gè)DFA接受的語(yǔ)言相同7. 下列符號(hào)串不可以由符號(hào)集Sa,b上的正閉包運(yùn)算產(chǎn)生的是：（A）A. B.a C.aa D.ab8稱有限自動(dòng)機(jī)A1和A2等價(jià)是指_。DAA1和A2都是定義在一個(gè)字母表上的有限自動(dòng)機(jī)BA1和A2狀態(tài)數(shù)和有向邊數(shù)相等CA1和A2狀態(tài)數(shù)或有向邊數(shù)相等DA1和A2所能識(shí)別的字符串集合相等9同正規(guī)式（a|b）+等價(jià)的正規(guī)式是_。BA（a|b）* B（a|b）（a|b）* C（ab）*（ab） D（a|b）|（

4、a|b）*語(yǔ)法分析1在規(guī)范歸約中，用 來(lái)刻畫(huà)可歸約串。 BA. 直接短語(yǔ) B. 句柄 C. 最左素短語(yǔ) D. 素短語(yǔ)2若B為非終結(jié)符，則A·B為 項(xiàng)目。DA. 歸約 B. 移進(jìn) C. 接受 D. 待約3如果文法G是無(wú)二義的，則它的任何句子 。 AA. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同B. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同C. 最左推導(dǎo)和最右推導(dǎo)必定相同D. 可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同4下列動(dòng)作中，不是自下而上分析動(dòng)作的是： 。BA. 移進(jìn) B. 展開(kāi)C. 接受 D. 報(bào)錯(cuò)6若a為終結(jié)符，則A·a為 項(xiàng)目。BA. 歸約 B. 移進(jìn) C. 接

5、受 D. 待約7語(yǔ)法分析時(shí)所依據(jù)的是 。AA. 語(yǔ)法規(guī)則 B. 詞法規(guī)則 C. 語(yǔ)義規(guī)則 D. 等價(jià)變換規(guī)則8文法G：SxSx|y所識(shí)別的語(yǔ)言是 。C A. xyx B. (xyx)* C. xnyxn (n0) D. x*yx*9下列動(dòng)作中，不是自上而下分析動(dòng)作的是： 。CA. 匹配 B. 展開(kāi)C. 移進(jìn) D. 報(bào)錯(cuò)10若A為非終結(jié)符，則A· 為 項(xiàng)目。AA. 歸約 B. 移進(jìn) C. 接受 D. 待約11文法G：SxSx| xS|y所識(shí)別的語(yǔ)言是 。 A A. xmyxn(mn0) B. (xyx)* C. xnyxn(n0) D. x*yx*13由文法的開(kāi)始符號(hào)出發(fā)經(jīng)過(guò)若干步（包

6、括0步）推導(dǎo)產(chǎn)生的文法符號(hào)序列稱為_(kāi)。BA語(yǔ)言 B句型 C句子 D句柄14在自上而下的語(yǔ)法分析中，應(yīng)從 開(kāi)始分析。CA句型 B句子 C文法開(kāi)始符號(hào)D句柄15一個(gè)文法G，若_，則稱它是LL（1）文法。CAG中不含左遞歸 BG無(wú)二義性 CG的LL（1）分析表中不含多重定義的條目 DG中產(chǎn)生式不含左公因子16項(xiàng)目SS. 為 。DA.歸約項(xiàng)目 B.移進(jìn)項(xiàng)目C.待約項(xiàng)目 D.接受項(xiàng)目17. 語(yǔ)法分析器的輸入是： 。AA. Token序列 B. 源程序C. 目標(biāo)程序 D. 符號(hào)表18. 在LR（0）的Action表中，如果某行中存在標(biāo)記為“rj”的欄，則： 。 AA. 該行必定填滿“rj” B. 該行未必

7、填滿“rj”C. 其他行可能也有“rj” D. goto表中也可能有“rj”19. LR分析過(guò)程中棧內(nèi)存儲(chǔ)的是 。 AA. 活前綴 B. 前綴C. 歸約活前綴 D. 項(xiàng)目20.文法G：S x xS | y 所識(shí)別的語(yǔ)言是 。 DAxxyn B(xxy) n Cxxnyx D(xx)ny21.若狀態(tài)k含有項(xiàng)目“A.”，對(duì)任意非終結(jié)符a，都用規(guī)則“A ”歸約的語(yǔ)法分析方法是 。BALALR分析法 BLR(0)分析法 CLR(1)分析法 DSLR(1)分析法22. 在SLR（1）的Action表中，如果某行中存在標(biāo)記為“rj”的欄，則： 。BA. 該行必定填滿“rj” B. 該行未必填滿“rj”C.

8、 其他行可能也有“rj” D. goto表中也可能有“rj”23. 一個(gè) 指明了在LR分析過(guò)程中的某個(gè)時(shí)刻所能看到產(chǎn)生式多大一部分。DA. 活前綴 B. 前綴C. 歸約活前綴 D. 項(xiàng)目24.若狀態(tài)k含有項(xiàng)目“A.”，且僅當(dāng)輸入符號(hào)aFOLLOW(A)時(shí)，才用規(guī)則“A ”歸約的語(yǔ)法分析方法是 。DALALR分析法 BLR(0)分析法 CLR(1)分析法 DSLR(1)分析法25設(shè)有文法GT:TT*F|FFFP|PP(T)|a該文法句型T*P(T*F)的句柄是下列符號(hào)串 。C A.（T*F） B. T*F C. P D. P(T*F)26LR分析表中的轉(zhuǎn)移表（goto）是以 作為列標(biāo)題的。BA終

9、結(jié)符 B非終結(jié)符 C終結(jié)符或非終結(jié)符 D表示狀態(tài)的整形數(shù)27編譯程序的語(yǔ)法分析器必須輸出的信息是 。 A A語(yǔ)法錯(cuò)誤信息 B語(yǔ)法規(guī)則信息C語(yǔ)法分析過(guò)程 D語(yǔ)句序列28下列項(xiàng)目中為可移進(jìn)項(xiàng)目的是 。C AEE . BL. CL.-L DFL*F.29LR分析表中的動(dòng)作表（action）是以 作為列標(biāo)題的。DA終結(jié)符 B非終結(jié)符C終結(jié)符或非終結(jié)符 D終結(jié)符和結(jié)束符#30下列項(xiàng)目中為可歸約項(xiàng)目的是 。BAE.E BL. CL-.L DFL*.F33LR分析器的核心部分是一張分析表，該表由_組成。DAACTION表 BGOTO表C預(yù)測(cè)分析表 DACTION表和GOTO表 34在遞歸下降子程序方法中，若

10、文法存在左遞歸，則會(huì)使分析過(guò)程產(chǎn)生_ _。DA回溯 B非法調(diào)用 C有限次調(diào)用 D無(wú)限循環(huán) 35最左簡(jiǎn)單子樹(shù)的葉結(jié)點(diǎn)，自左至右排列組成句型的_。CA短語(yǔ) B句型 C句柄 D間接短語(yǔ)36由文法的開(kāi)始符號(hào)出發(fā)經(jīng)過(guò)若干步（包括0步）推導(dǎo)產(chǎn)生的文法符號(hào)序列中，如果只含有終結(jié)符，則文法符號(hào)序列稱為_(kāi)。CA語(yǔ)言 B句型 C句子 D句柄37LL（1）分析法中“1”的含義是在輸入串中查看一個(gè)輸入符號(hào)，其目的是_。CA確定最左推導(dǎo) B確定句柄 C確定使用哪一個(gè)產(chǎn)生式進(jìn)行展開(kāi) D確定是否推導(dǎo)語(yǔ)義分析1.表達(dá)式（ab）（ef）的逆波蘭表示為 。BAabef BabefCabef Dabef2中間代碼生成時(shí)所依據(jù)的是

11、。CA詞法規(guī)則 B語(yǔ)法規(guī)則 C語(yǔ)義規(guī)則 D等價(jià)變換規(guī)則3 -a-(b*c/(c-d)+(-b)*a)的逆波蘭表示是 。(代表后綴式中的求負(fù)運(yùn)算符) CA. abc*cd-ba*+/- B. abc*cd-ba*+/-C. abc*cd-/ba*+- D. abc*/cd-ba*+-4有文法G及其語(yǔ)法制導(dǎo)翻譯如下所示（語(yǔ)義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符）： EE(1) T E.val = E(1).val * T.val ET E.val = T.val TT(1)# n T.val = T(1).val + n.val T n T.val = n.val則分析句子1 2 3 # 4

12、其值為 。 C A. 10 B. 34 C. 14 D.545有文法G及其語(yǔ)法制導(dǎo)翻譯如下所示（語(yǔ)義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符）： EE(1) T E.val = E(1).val * T.val ET E.val = T.val TT(1)# n T.val = T(1).val + n.val T n T.val = n.val 則分析句子2 3 # 4其值為 。 C A. 10 B. 21 C. 14 D. 246間接三元式表示法的優(yōu)點(diǎn)為 。 AA. 采用間接碼表，便于優(yōu)化處理 B. 節(jié)省存儲(chǔ)空間，不便于表的修改C. 便于優(yōu)化處理，節(jié)省存儲(chǔ)空間 D. 節(jié)省存儲(chǔ)空間，不便于

13、優(yōu)化處理7文法GS及其語(yǔ)法制導(dǎo)翻譯定義如下： 產(chǎn)生式語(yǔ)義動(dòng)作 S Sprint(S.num) S (L)S.num = L.num +1S aS.num = 0 L L(1), SL.num = L(1).num + S.numL S L.num = S.num若輸入為(a,(a)，且采用自底向上的分析方法，則輸出為 。CA0B1C2D48四元式之間的聯(lián)系是通過(guò) _實(shí)現(xiàn)的。BA指示器 B臨時(shí)變量 C符號(hào)表 D程序變量9表達(dá)式（ab）（cd）的逆波蘭表示為 。BAabcd BabcdCabcd Dabcd10表達(dá)式a+b+c+d的逆波蘭表示為 。BAa+bc+d+ Bab+c+d+Cab+cd+

14、 Dabc+d+11.有文法G及其語(yǔ)法制導(dǎo)翻譯如下所示（語(yǔ)義規(guī)則中的*和+分別是常規(guī)意義下的算術(shù)運(yùn)算符）： EE(1) T E.val = E(1).val * T.val ET E.val = T.val TT(1)# n T.val = T(1).val + n.val T n T.val = n.val則分析句子3 3 # 4其值為 。B A. 10 B. 21 C. 14 D. 2412表達(dá)式a+b+c的逆波蘭表示為 。BAa+bc+ Bab+c+C+abc+ Dabc+13. 文法GS及其語(yǔ)法制導(dǎo)翻譯定義如下： 產(chǎn)生式語(yǔ)義動(dòng)作 S Sprint(S.num) S (L)S.num =

15、 L.num +1S a S.num = 0 L L(1), SL.num = L(1).num + S.numL S L.num = S.num若輸入為(a, a)，且采用自底向上的分析方法，則輸出為 。BA0 B1C2 D414有一語(yǔ)法制導(dǎo)翻譯定義如下：SbAb print “1”A（B print “2”Aa print “3”BaA) print “4”若輸入序列為b（a（a（aa）b，且采用自底向上的分析方法，則輸出序列為 。BA32224441 B34242421C12424243 D3444221215賦值語(yǔ)句X:=-(a+b)/(c-d)-(a+b*c)的逆波蘭表示是 。CA.

16、 Xab+cd-/-bc*a+-:=B. Xab+/cd-bc*a+-:=C. Xab+-cd-/ a bc* +-:=D. Xab+cd-/abc* +-:=16有一語(yǔ)法制導(dǎo)翻譯定義如下，其中+表示符號(hào)連接運(yùn)算：SB print B.versBa B.vers=aBb B.vers=bBBa B.vers=a+B.versBBb B.vers=b+B.vers若輸入序列為abab，且采用自底向上的分析方法，則輸出序列為 。DAaabb Babab Cbbaa Dbaba17編譯程序不能檢查、處理的錯(cuò)誤是程序中的_。BA靜態(tài)語(yǔ)義檢查 B動(dòng)態(tài)語(yǔ)義檢查 C語(yǔ)法錯(cuò)誤 D詞法錯(cuò)誤（優(yōu)化、存儲(chǔ)、錯(cuò)誤管理

17、）1.在編譯過(guò)程中，如果遇到錯(cuò)誤應(yīng)該 。CA. 把錯(cuò)誤理解成局部的錯(cuò)誤 B. 對(duì)錯(cuò)誤在局部范圍內(nèi)進(jìn)行糾正，繼續(xù)向下分析C. 當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)，跳過(guò)錯(cuò)誤所在的語(yǔ)法單位繼續(xù)分析下去D. 當(dāng)發(fā)現(xiàn)錯(cuò)誤時(shí)立即停止編譯，待用戶改正錯(cuò)誤后再繼續(xù)編譯二、填空題概述部分：1編譯程序的開(kāi)發(fā)常常采用自編譯、 交叉編譯 、 自展 和移植等技術(shù)實(shí)現(xiàn)。2解釋程序和編譯程序的區(qū)別在于 是否生成目標(biāo)程序 。3如果編譯程序生成的目標(biāo)程序是匯編語(yǔ)言程序，則源程序的執(zhí)行分為3個(gè)階段： 編譯階段 、 匯編階段 和 運(yùn)行階段 。4編譯程序工作過(guò)程中，第一階段輸入是 源程序 ，最后階段的輸出為 目標(biāo)程序 。5編譯過(guò)程通?？煞譃?個(gè)階段 詞法

18、分析階段 、 語(yǔ)法分析階段 、 語(yǔ)義分析和中間代碼生成階段 、優(yōu)化階段和目標(biāo)代碼生成階段。6如果編譯階段生成的目標(biāo)程序是某特定計(jì)算機(jī)系統(tǒng)的機(jī)器代碼程序，則源程序的執(zhí)行分為兩大階段： 編譯階段 和 運(yùn)行階段 。7對(duì)編譯程序而言，輸入數(shù)據(jù)是 源程序 ，輸出結(jié)果是 目標(biāo)程序 。8貫穿于編譯程始終的工作有 符號(hào)表處理 和出錯(cuò)處理。詞法分析部分：1詞法分析的工作是將源程序中的 字符串 變換成 單詞符號(hào)流 的過(guò)程，所遵循的是語(yǔ)言的 構(gòu)詞規(guī)則 。2若兩個(gè)正規(guī)式所表示的 正規(guī)集 相同，則認(rèn)為二者是等價(jià)的。3若兩個(gè)正規(guī)式所表示的正規(guī)集相同，則認(rèn)為二者是 等價(jià) 的。4正規(guī)式R1和R2等價(jià)是指_表示相同的正規(guī)集 。

19、5詞法分析器的輸入是源程序字符串，輸出結(jié)構(gòu)是 二元式（單詞種別， 單詞自身的值） 。詞法分析所遵循的是語(yǔ)言的 構(gòu)詞 規(guī)則。6確定的有限自動(dòng)機(jī)是一個(gè)五元組，包含的五個(gè)元分別是：狀態(tài)集合、 字母表、初態(tài)、終態(tài)集、狀態(tài)轉(zhuǎn)換函數(shù)集合 。7有限自動(dòng)機(jī)是更一般化的狀態(tài)轉(zhuǎn)換圖，它分為 確定的有限自動(dòng)機(jī)DFA 和 非確定的有限自動(dòng)機(jī)NFA 兩種。8NFA和DFA的區(qū)別主要有兩點(diǎn)：其一是 NFA可以有若干個(gè)初始狀態(tài)，而DFA僅有一個(gè)初始狀態(tài) ；其二是 NFA的狀態(tài)轉(zhuǎn)換函數(shù)f不是單值函數(shù)，而是一個(gè)多值函數(shù) 。語(yǔ)法分析部分：（基本概念、LL（1）、LR（0）、SLR（1）、遞歸下降子程序）1 語(yǔ)法分析的方法通常分為

20、兩類(lèi)： 自上而下分析方法 和 自下而上分析方法 。2文法中的終結(jié)符集和非終結(jié)符集的交集是 空集 。3一個(gè)句型的最左直接短語(yǔ)稱為該句型的_句柄_。4規(guī)范歸約是 最右推導(dǎo) 的逆過(guò)程。5自下而上語(yǔ)法分析中分析器的動(dòng)作有_移進(jìn) 、_歸約 、_接受_ 、_報(bào)錯(cuò) _。6自上而下語(yǔ)法分析中分析器的動(dòng)作有_匹配終結(jié)符_、_展開(kāi)非終結(jié)符_、_分析成功、報(bào)錯(cuò)_。7常用的自上而下語(yǔ)法分析方法有遞歸下降子程序方法和預(yù)測(cè)分析表方法（LL（1）方法）。8常用的自下而上語(yǔ)法分析方法有算符優(yōu)先分析法和LR分析法。9一個(gè)LL(1)分析器由 一張LL(1)分析表（預(yù)測(cè)分析表） 、 一個(gè)先進(jìn)后出分析棧 和一個(gè) 控制程序（表驅(qū)動(dòng)程序

21、）組成。10一個(gè)LR分析器由 分析棧 、 分析表 和總控程序三個(gè)部分組成。11LR(0)分析法的名字中，“L”表示 自左至右分析輸入串 ，“R”表示 采用最右推導(dǎo)的逆過(guò)程即最左歸約 ?！?”表示 向右查看0個(gè)字符 。12LL(1)分析法中，第一個(gè)L的含義是 從左到右掃描輸入串 ；第二個(gè)L的含義是 分析過(guò)程中采用最左推導(dǎo) ；“1”的含義是 只需向右查看一個(gè)符號(hào)就可以決定如何推導(dǎo) 。13LR(1)文法的含義是：L表明_自左至右掃描輸入串_，R表明_采用最右推導(dǎo)的逆過(guò)程（最左歸約）方法進(jìn)行分析_。14一個(gè)上下文無(wú)關(guān)文法是LL(1)文法的充分必要條件是：對(duì)每一個(gè)非終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A|，有下

22、面的條件成立：（1） FIRST()FIRST() = Ø ；（2）假若，則有 FIRST() FOLLOW(A) = Ø 。15對(duì)于LL（1）文法中的任何產(chǎn)生式A|，則需要滿足_First(_)First()= 、_若_=>*,則_ First(_) _Follow(A)=_ _。16LR分析器的核心部分是一張分析表，該表包括 動(dòng)作（ACTION）表 和 狀態(tài)轉(zhuǎn)換（GOTO）表 等兩個(gè)子表。17關(guān)于非終結(jié)符A的直接左遞歸產(chǎn)生式：AA|，其中、是任意的符號(hào)串且不以A開(kāi)頭，則可以將A的產(chǎn)生式改寫(xiě)為右遞歸的形式為： AA , AA| 。18在消除回溯，提取公共左因子時(shí)，關(guān)

23、于A的產(chǎn)生式A 1 | 2 | | i | i+1 | | j，可以改寫(xiě)為： A A | i+1 | | j ， A 1 | |i 。19設(shè)GS 是一文法，如果符號(hào)串x是從識(shí)別符號(hào)推導(dǎo)出來(lái)的，即有x，則稱x是文法GS的_句型_，若x僅由終結(jié)符號(hào)組成，即，則稱x為文法GS的_句子 。20已知文法GS:SeT|RT TDR| RdR| Da|bd求FIRST(S)=e，d，a，b，_；FOLLOW(D)=_d，# 。語(yǔ)義處理部分：1文法符號(hào)的屬性有兩種，一種稱為 繼承屬性 ，另一種稱為 綜合屬性 。2編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有 逆波蘭表示法 、 抽象語(yǔ)法樹(shù) 、 三元式 、 四元式 。3語(yǔ)法制

24、導(dǎo)翻譯的方法就是為每個(gè)產(chǎn)生式配上一個(gè) 翻譯子程序（語(yǔ)義動(dòng)作或語(yǔ)義子程序） ，并在語(yǔ)法分析的同時(shí)執(zhí)行它們。4編譯過(guò)程中，常見(jiàn)的中間語(yǔ)言形式有 逆波蘭表示法 、 抽象語(yǔ)法樹(shù) 、 三元式 、 四元式 。6文法符號(hào)的屬性有兩種，一種稱為 繼承屬性 ，另一種稱為 綜合屬性 。7四元式之間的聯(lián)系是通過(guò) 臨時(shí)變量 實(shí)現(xiàn)的。8在屬性文法中，終結(jié)符只有_綜合 屬性。10語(yǔ)法制導(dǎo)翻譯的方法就是為每個(gè)產(chǎn)生式配上一個(gè) 翻譯子程序（語(yǔ)義動(dòng)作或語(yǔ)義子程序） ，并在語(yǔ)法分析的同時(shí)執(zhí)行它們。11目前較常見(jiàn)的語(yǔ)言語(yǔ)義的描述形式是_屬性文法_，并使用_語(yǔ)法制導(dǎo)翻譯 方法完成對(duì)語(yǔ)法成分的翻譯。（優(yōu)化、存儲(chǔ)、錯(cuò)誤管理）1.代碼優(yōu)化的

25、含義是：對(duì)代碼進(jìn)行 等價(jià)變換 ，使得變換后的代碼具有更高的 時(shí)間效率 和 空間效率。2.按照優(yōu)化對(duì)象所涉及的程序范圍，優(yōu)化分為 局部?jī)?yōu)化 、 循環(huán)優(yōu)化 和 全局優(yōu)化 。3.基本塊，是指程序中 順序執(zhí)行的語(yǔ)句序列 ，其中只有一個(gè) 入口 和一個(gè) 出口 。4.從編譯角度看，分配目標(biāo)程序數(shù)據(jù)空間的基本策略有： 靜態(tài)分配策略 、 棧式動(dòng)態(tài)分配策略 和堆式動(dòng)態(tài)分配策略 。三、判斷題1設(shè)r和s分別為正規(guī)式，則有L(r|s) = L(r) | L(s).。( × )2一個(gè)文法的所有句型的集合形成該文法所能接受的語(yǔ)言。( × )3語(yǔ)法分析之所以采用上下文無(wú)關(guān)文法是因?yàn)樗拿枋瞿芰ψ顝?qiáng)。( &

26、#215; )4由于LR(0)分析表構(gòu)造簡(jiǎn)單，所以它的描述能力強(qiáng)，適用面寬；LR(1)分析表因構(gòu)造復(fù)雜而描述能力弱，適用面窄。( × )5逆波蘭表示法表示表達(dá)式時(shí)無(wú)需使用括號(hào)。( )6自動(dòng)機(jī)M和M的狀態(tài)個(gè)數(shù)不同，則二者必不等價(jià)。( × )7LL(1)文法一定不含左遞歸和二義性。( )8所有LR分析器的總控程序都是一樣的，只是分析表各有不同。( )9無(wú)論是三元式表示還是間接三元式表示的中間代碼，其三元式在三元式表中的位置一旦確定就很難改變。( )10三地址語(yǔ)句類(lèi)似于匯編語(yǔ)言代碼，可以看成中間代碼的一種抽象形式。( )11最左推導(dǎo)也被稱為規(guī)范推導(dǎo)。（× ）12運(yùn)算對(duì)象

27、排列的先后順序在后綴式和中綴式中不同。（ × ）13出現(xiàn)在移進(jìn)-歸約分析器棧中的內(nèi)容被稱為文法G的活前綴。（ ）14LR方法可以分析含有左遞歸的文法。（ ）15三元式的編號(hào)具有雙重含義，既代表此三元式，又代表三元式存放的結(jié)果。（ ）16語(yǔ)義規(guī)則中的屬性有兩種：綜合屬性與繼承屬性。（ ）17移進(jìn)-歸約分析器的格局中棧的內(nèi)容一般是文法符號(hào)與狀態(tài)。（ ）18由于遞歸下降子程序方法較LL（1）方法簡(jiǎn)單，因此它要求文法不必是LL（1）文法。（ × ）19四元式的編號(hào)具有雙重含義，既代表此四元式，又代表四元式存放的結(jié)果。（ × ）20用高級(jí)語(yǔ)言編寫(xiě)的源程序必須經(jīng)過(guò)編譯，產(chǎn)生目

28、標(biāo)程序后才能運(yùn)行。（ × ）21源程序到目標(biāo)程序的變換是等價(jià)變換，即兩者結(jié)構(gòu)不同，但語(yǔ)義是一致的。（ ）22對(duì)于任何一個(gè)正規(guī)式e，都存在一個(gè)DFA A，使得L（e）=L（A）。（ ）23最小化的DFA，它的狀態(tài)數(shù)最小。（ ）24NFA的確定化算法具有消除邊的功能。（ ）25每個(gè)非終結(jié)符產(chǎn)生的終結(jié)符號(hào)串都是該語(yǔ)言的子集。（ × ）26一個(gè)語(yǔ)言的文法是不唯一的。（ ）27語(yǔ)法錯(cuò)誤校正的目的是為了把錯(cuò)誤改正過(guò)來(lái)。（ × ）28源程序和目標(biāo)程序是等價(jià)關(guān)系。（ ）29編譯程序中錯(cuò)誤處理的任務(wù)是對(duì)檢查出的錯(cuò)誤進(jìn)行修改。（ × ）30使用有限自動(dòng)機(jī)可以實(shí)現(xiàn)單詞的識(shí)別。

29、（ ）31一個(gè)非確定的有限自動(dòng)機(jī)NFA可以通過(guò)多條路徑識(shí)別同一個(gè)符號(hào)串。（ ）32最小化的DFA所識(shí)別接受的正規(guī)集最小。（ × ）33一個(gè)語(yǔ)言（如C語(yǔ)言）的句子是有窮的。（ × ）34LL（1）方法又稱為預(yù)測(cè)分析方法。（ ）35一個(gè)LL（1）文法是無(wú)二義和無(wú)回溯方法。（ ）36語(yǔ)法分析器可以檢查出程序中的所有錯(cuò)誤。（ × ）37LR分析法是自上而下的語(yǔ)法分析方法。（ × ）三、多項(xiàng)選擇題1. 編譯器的各個(gè)階段的工作都涉及到（AE）A. 表格處理 B. 詞法分析C. 語(yǔ)法分析 D. 語(yǔ)義分析 E. 出錯(cuò)處理2. 令Sa,b，則S上的符號(hào)串的全體可用下面的正

30、規(guī)式表示。（ABE）A. (a|b)* B. (a*|b*)*C. (a|b)+ D. (ab)* E. (a*b*)*3. 自上而下的分析方法有：（AD）A. 遞歸下降分析法 B. LR（0）分析法C. LALR（1）分析法 D. LL（1）分析法E. SLR（1）分析法4.文法G：GS：SCDAbbA CaCABaaB CbCBBbbB ADaDC BDbDD AabD是（A）。A. 0型文法 B. 1型文法C. 2型文法 D. 3型文法 E. 上下文有關(guān)文法5. 對(duì)LR分析表的構(gòu)造，有可能存在的動(dòng)作沖突有：（AD）A. 移進(jìn)/歸約沖突 B. 移進(jìn)/移進(jìn)沖突C. 歸約沖突 D. 歸約/歸約

31、沖突E. 移進(jìn)沖突6. 一個(gè)編譯器可能有的階段為（ABCDE）A. 詞法分析 B. 語(yǔ)法分析C. 語(yǔ)義分析 D. 中間代碼生成E. 目標(biāo)代碼生成7 令Sa,b，則S上的所有以b開(kāi)頭，后跟若干個(gè)（可為0個(gè)）ab的符號(hào)串的全體可用下面的正規(guī)式表示。（AB）A.b (ab)* B. (ba)*b C. b(a|b)+ D. (ba)+b E. b (a|b)*8. 自下而上的分析方法有：（BCE）A. 遞歸下降分析法 B. LR（0）分析法C. LALR（1）分析法 D. LL（1）分析法E. SLR（1）分析法9. 一般來(lái)說(shuō)，編譯器可分為前端和后端，下列編譯階段可被劃分為編譯的前端的有：（ABCD

32、E）A. 詞法分析 B. 語(yǔ)法分析C. 語(yǔ)義分析 D. 中間代碼生成 E. 中間代碼優(yōu)化10令Sa,b，則S上的符號(hào)串的全體可用下面的正規(guī)式表示。（ABE）A. (a|b)* B. (a*|b*)*C. (a|b)+ D. (ab)* E. (a*b*)*11下列符號(hào)串是符號(hào)集Sa,b上的正規(guī)式的有：（ABCDE）A. B.a C.ab D.(aba) (aba)E.abab12正規(guī)式服從的代數(shù)規(guī)律有：（ABDE）A. “或”運(yùn)算服從交換律 B. “或”運(yùn)算服從結(jié)合律C. “連接”運(yùn)算服從交換律 D. “連接”運(yùn)算服從結(jié)合律E. “連接”運(yùn)算可對(duì)“或”運(yùn)算進(jìn)行分配13 令Sa,b，則S上的所有

33、以b開(kāi)頭，后跟若干個(gè)（可為0個(gè)）ab的符號(hào)串的全體可用下面的正規(guī)式表示。（AB）A.b (ab)* B. (ba)*b C. b(a|b)+D. (ba)+b E. b (a|b)*14 一個(gè)LR分析器包括：（ADE）A. 一個(gè)總控程序 B.一個(gè)項(xiàng)目集C.一個(gè)活前綴 D.一個(gè)分析棧E.一張分析表15 LR分析器的核心部分是一張分析表，該表包括（DE）等子表。A. LL（1）分析表 B. LR（1）分析表C. SLR（1）分析表 D. Action表E. goto表16 Action表中的每一項(xiàng)ActionS,a所表示的動(dòng)作可能為：（ABCD）A. 移進(jìn) B. 接受 C. 歸約D. 出錯(cuò) E.

34、待約五簡(jiǎn)答題1構(gòu)造正規(guī)表達(dá)式(a|b)*|aa)*b的NFA。解：2設(shè)M=(x,y, a,b, f, x, y)為一非確定的有限自動(dòng)機(jī)，其中f定義如下： f(x,a)=x,y fx,b=y f(y,a)= fy,b=x,y試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M。解：對(duì)照自動(dòng)機(jī)的定義M=(S,f,So,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，因此M是一非確定有限自動(dòng)機(jī)。先畫(huà)出NFA M相應(yīng)的狀態(tài)圖，如下圖所示。用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣，如下表所示。 將轉(zhuǎn)換矩陣中的所有子集重新命名，形成下表所示的狀態(tài)轉(zhuǎn)換矩陣，即得到M=(0,1,2,a,b,f,0,1,2)，M狀態(tài)轉(zhuǎn)換圖如下圖所示。（注

35、意：本題由于集合的命名和先后順序不同，可能最終結(jié)果不同。）3畫(huà)出編譯程序的總體結(jié)構(gòu)圖，簡(jiǎn)述各部分的主要功能。解：編譯程序的總體框圖如下所示： （1）詞法分析器，又稱掃描器，它接受輸入的源程序，對(duì)源程序進(jìn)行詞法分析，識(shí)別出一個(gè)個(gè)單詞符號(hào)，其輸出結(jié)果是二元式(單詞種別，單詞自身的值)流。（2）語(yǔ)法分析器，對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析（根據(jù)語(yǔ)法規(guī)則進(jìn)行推導(dǎo)或歸約），識(shí)別出程序中的各類(lèi)語(yǔ)法單位，最終判斷輸入串是否構(gòu)成語(yǔ)法上正確的句子。（3）語(yǔ)義分析及中間代碼生成器，按照語(yǔ)義規(guī)則對(duì)語(yǔ)法分析器歸約出（或推導(dǎo)出）的語(yǔ)法單位進(jìn)行語(yǔ)義分析并把它們翻譯成一定形式的中間代碼。編譯程序可以根據(jù)不同的需要選擇不同的中間代碼

36、形式，有的編譯程序甚至沒(méi)有中間代碼形式，而直接生成目標(biāo)代碼。（4）優(yōu)化器對(duì)中間代碼進(jìn)行優(yōu)化處理。一般最初生成的中間代碼執(zhí)行效率都比較低，因此要做中間代碼的優(yōu)化，其過(guò)程實(shí)際上是對(duì)中間代碼進(jìn)行等價(jià)替換，使程序在執(zhí)行時(shí)能更快，并占用更小的空間。（5）目標(biāo)代碼生成器，把中間代碼翻譯成目標(biāo)程序。中間代碼一般是一種與機(jī)器無(wú)關(guān)的表示形式，只有把它再翻譯成與機(jī)器硬件直接相關(guān)的機(jī)器能識(shí)別的語(yǔ)言，即目標(biāo)程序，才能在機(jī)器上運(yùn)行。（6）表格管理模塊保持一系列的表格，登記源程序的各類(lèi)信息和編譯各階段的進(jìn)展?fàn)顩r。編譯程序各個(gè)階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需要的信息也大多從表格中獲取，整個(gè)編譯過(guò)程都在不斷和表格打交

37、道。（7）出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的錯(cuò)誤進(jìn)行處理。如果源程序有錯(cuò)誤，編譯程序應(yīng)設(shè)法發(fā)現(xiàn)錯(cuò)誤，把有關(guān)錯(cuò)誤信息報(bào)告給用戶。編譯程序的各個(gè)階段都有可能發(fā)現(xiàn)錯(cuò)誤，出錯(cuò)處理程序要對(duì)發(fā)現(xiàn)的錯(cuò)誤進(jìn)行處理、記錄，并反映給用戶。4構(gòu)造一個(gè)DFA，它接受 = 0, 1上所有滿足如下條件的字符串：每個(gè)1后面都有0直接跟在右邊。解：（1）0*(0|10)*0* 或者 (0|10)* （2）NFA （2分）X0Y01020103子集法確定化 II0I1X, 0, 1, 3, Y0, 1, 3, Y20, 1, 3, Y0, 1, 3, Y221, 3, Y-1, 3, Y1, 3, Y2重新命名狀態(tài)，即得：S011

38、2322334-443 最小化 首先分為終態(tài)集和非終態(tài)集 3 1, 2, 4 因?yàn)?0 = 2 20 = 2 40 = 4 狀態(tài)均屬于集合1, 2, 4，所以對(duì)于輸入符號(hào)0不能區(qū)分開(kāi)1，2，4三個(gè)狀態(tài)；11 = 3 21 = 3 41 = 3狀態(tài)均屬于集合3，所以對(duì)于輸入符號(hào)1也不能區(qū)分開(kāi)1，2，4三個(gè)狀態(tài)；因此最終的狀態(tài)劃分即為: 3 1, 2, 4，其對(duì)應(yīng)的DFA如下圖所示：001105寫(xiě)出C語(yǔ)言標(biāo)識(shí)符集（字母或下劃線開(kāi)頭的由字母、數(shù)字、下劃線構(gòu)成的串）的正規(guī)式。解答：用D表示數(shù)字0-9，用L表示字母a-z|A-Z，則C語(yǔ)言標(biāo)識(shí)符的正規(guī)式為： （L|_）（L|D|_）*語(yǔ)法分析部分：6構(gòu)造

39、一文法，使其描述的語(yǔ)言L = | (a, b)*，且中含有相同個(gè)數(shù)的a和b。解：S | aA|bBA b| bS| aAAB a| aS| bBB7對(duì)于文法G(S)：S (L) | aS | aL L, S | S(1) 畫(huà)出句型(S, (a)的語(yǔ)法樹(shù)。(2) 寫(xiě)出上述句型的所有短語(yǔ)、直接短語(yǔ)和句柄。解：(1) 句型(S, (a)的語(yǔ)法樹(shù)如下圖所示： (2) 從語(yǔ)法樹(shù)中可以找到（3分）短語(yǔ)：a; (a); S; S,(a); (S, (a)直接短語(yǔ)： a; S 句柄： S8令文法GN為 GN: ND|ND D0|1|2|3|4|5|6|7|8|9給出句子568的最左、最右推導(dǎo)。解：最左推導(dǎo)：N

40、 ND NDD DDD 5DD 56D 568最右推導(dǎo)：N ND N8 ND8 N68 D68 5688已知文法GA: AaABl|aBBb|d試給出與GA等價(jià)的LL(1)文法GA；解：GA：AaAAABl | BdBBbB| 9試構(gòu)造下述文法的SLR(1)分析表。GA: AaABl|aBBb|d解：拓廣文法 （0）SA（1）AaABl（2）Aa（3）BBb（4）BdFirst（A）=afollow（A）=#，dFirst（B）=dfollow（B）=lSLR（1）分析表如下：abdl#AB0S211ACC2S2R2R233S454R45S7S66R1R17R310. 試構(gòu)造下述文法的LL(1

41、)分析表。GS: S（L）|aLL，S|S解：消除左遞歸：G(S): S à (L) | aL à SLL à , SL| 構(gòu)造FIRST集，如下：（1）FIRST(S) = (, a（2）FIRST(L) = (, a（3）FIRST(L) = , 構(gòu)造FOLLOW集如下：（1）FOLLOW(S) = #, , )（2）FOLLOW(L) = )（3）FOLLOW(L) = )LL(1)分析表()a,#SS à (L)S à aLL à SLL à SLLL à L à ,SL11已知文法GS: SaS

42、bS|bSaS|試證明GS是二義文法證明： 該文法產(chǎn)生的語(yǔ)言是a的個(gè)數(shù)和b的個(gè)數(shù)相等的串的集合。該文法二義，例如句子abab有兩種不同的最左推導(dǎo)。 SaSbSabSabaSbSababSabab SaSbSabSaSbSabaSbSababSabab12已知文法： S ( L | a L S , L | )判斷是不是LL（1）文法，如果是請(qǐng)構(gòu)造文法 的預(yù)測(cè)分析表，如果不是請(qǐng)說(shuō)明理由?！窘狻?1）求各非終結(jié)符的 FISRT 集和 FOLLOW 集：First（S）= (, a FIRST(L) = ） È FIRST(S) = (, ), a FOLLOW(S) = , # FOLLOW(L) = FOLLOW(S) = , # FIR