編譯原理小題答案

1、編譯原理小題答案編譯原理常見題型一、填空題1.編譯程序的工作過程一般可以劃分為詞法分析，語法分析，中間代碼生成， 代碼優(yōu)化 ( 可省 )， 目標(biāo)代碼生成等幾個基本階段。2.若源程序是用高級語言編寫的，目標(biāo)程序是機器語言程序或匯編程序，則其翻譯程序稱為編譯程序 .3. 編譯方式與解釋方式的根本區(qū)別在于 是否生成目標(biāo)代碼 .5. 對編譯程序而言，輸入數(shù)據(jù)是 源程序，輸出結(jié)果是 目標(biāo)程序 .7. 若源程序是用高級語言編寫的， 目標(biāo)程序是機器語言程序或匯編程序 ，則其翻譯程序稱為 編譯程序。8. 一個典型的編譯程序中，不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個部分，還應(yīng)包括

2、表格處理和 出錯處理。其中，詞法分析器用于識別單詞。10. 一個上下文無關(guān)文法所含四個組成部分是一組終結(jié)符號、一組非終結(jié)符號、一個開始符號、 一組產(chǎn)生式。12. 產(chǎn)生式是用于定義 語法成分的一種書寫規(guī)則。13. 設(shè) GS 是給定文法，則由文法 G所定義的語言 L(G) 可描述為：L(G) x S=*x,x VT* 。編譯原理小題答案14. 設(shè) G是一個給定的文法， S是文法的開始符號，如果 Sx（其中 xV*），則稱 x 是文法的一個句型。15. 設(shè) G是一個給定的文法， S 是文法的開始符號，如果 Sx( 其中xVT*) ，則稱 x 是文法的一個句子。16. 掃描器的任務(wù)是從源程序中識別出一

3、個個單詞符號。17. 語法分析最常用的兩類方法是 自上而下和 自下而上分析法。18. 語法分析的任務(wù)是識別給定的 xx 串是否為給定文法的 句子 。19. 遞歸下降法不允許任一非 xx 是直接 左 遞歸的。20. 自頂向下的語法分析方法的關(guān)鍵是 如何選擇候選式的問題。21. 遞歸下降分析法是自 頂向下分析方法。22. 自頂向下的語法分析方法的基本思想是：從文法的開始符號開始，根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進行直接推導(dǎo)，試圖推導(dǎo)出文法的句子，使之與給定的輸入串匹配。23. 自底向上的語法分析方法的基本思想是： 從給定的 xx 串開始，根據(jù)文法的規(guī)則一步一步的向上進行直接歸約，試

4、圖歸約到文法的開始符號。編譯原理小題答案24. 自底向上的語法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進行直接歸約，力求歸約到文法的開始符號。26. 在 LR（0）分析法的名稱中， L 的含義是 自 xx 的掃描輸入串， R的含義是 最左歸約，0 的含義是向貌似句柄的符號串后查看0 個輸入符號。31.xx 只有綜合屬性，它們由詞法分析器提供。32. 在使用高級語言編程時，首先可通過編譯程序發(fā)現(xiàn)源程序的全部A（語法）錯誤和 B （語義）部分錯誤 .34一個句型中的最左簡單短語稱為該句型的_句柄_。36從功能上說，程序語言的語句大體可分為_執(zhí)行性 _語句和說明性 _語句兩

5、大類。37語法分析是依據(jù)語言的 _語法 _規(guī)則進行的，中間代碼產(chǎn)生是依據(jù)語言的 _語義 _規(guī)進行的。38語法分析器的輸入是 _單詞符號 _，其輸出是 _語法單位_。40逆 xx 式 ab+c+ d*e-所表達的表達式為 _(a+b+c)*d-c_。41計算機執(zhí)行用高級語言編寫的程序主要有兩種途徑： _解釋_和_編譯 _。42自上而下分析法采用 _移進 _、歸約、錯誤處理、接受_等四種操作。編譯原理小題答案43一個 LR分析器包括兩部分：一個總控程序和 _一張分析表 _。44后綴式 abc-/ 所代表的表達式是a/(b-c)_ 。46語法分析基于 _上下文無關(guān) _文法進行，即識別的是該類文法的句

6、子。語法分析的有效工具是_語法樹 _。48語義分析階段所生成的與源程序等價的中間表示形式可以有_逆xx_、四元式表示 _與_三元式表示 _等。51. 自頂向下語法分析會遇到的主要問題有左遞歸和 回溯。52. 已知文法 GE ：ET|E+T; T F|T*F; F (E)|i 該文法的開始符號是，終結(jié)符號集合 VT是，非終結(jié)符號結(jié)合 VN是。二、單選題1一個編譯程序中，不僅包含詞法分析， ( A) ，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分。A語法分析B文法分析C語言分析D解釋分析2語法分析器則可以發(fā)現(xiàn)源程序中的(D ) 。A語義錯誤 B語法和語義錯誤C錯誤并校正 D語法錯誤3解釋程序處理

7、語言時,大多數(shù)采用的是 (B)B 方法。A源程序命令被逐個直接解釋執(zhí)行編譯原理小題答案B先將源程序轉(zhuǎn)化為中間代碼,再解釋執(zhí)行C先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,再執(zhí)行D以上方法都可以4編譯程序是一種 (B) 。A匯編程序B翻譯程序C解釋程序 D目標(biāo)程序5通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個部分，還應(yīng)包括(C) 。A模擬執(zhí)行器 B解釋器 C表格處理和出錯處理D符號執(zhí)行器6一個句型中的最左 (B) 稱為該句型的句柄。A短語 B簡單短語 C素短語 D終結(jié)符號7文法 GE：ETE TTFT FFa(E)該文法句型 E F(ET) 的簡單短語是下列符號串

8、中的(B) 。 （ET）ETF F (ET)A和B和C和D8詞法分析器用于識別 (C) 。編譯原理小題答案A句子 B句型 C單詞 D產(chǎn)生式9在自底向上的語法分析方法中，分析的關(guān)鍵是(D) 。A尋找句柄 B尋找句型 C消除遞歸 D選擇候選式10文法 G 產(chǎn)生的 ( D) 的全體是該文法描述的語言。A句型 Bxx 集C非 xx 集D句子11若文法 G 定義的語言是無限集，則文法必然是(A) 。A遞歸的 B前后文無關(guān)的 C二義性的12四種形式語言文法中， 1 型文法又稱為A短語結(jié)構(gòu)文法 B前后文無關(guān)文法D無二義性的(C)C 文法。C前后文有關(guān)文法D正規(guī)文法13一個文法所描述的語言是(A) 。A唯一的

9、 B不唯一的C可能唯一， 好可能不唯一 D都不對14(B) 和代碼優(yōu)化部分不是每個編譯程序都必需的。A語法分析 B中間代碼生成C詞法分析 D目標(biāo)代碼生成15(B) 是兩類程序語言處理程序。A高級語言程序和低級語言程序B解釋程序和編譯程序C編譯程序和操作系統(tǒng)D系統(tǒng)程序和應(yīng)用程序16. 一個上下文無關(guān)文法 G包括四個組成部分， 它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 (D) 。A句子 B句型C單詞D產(chǎn)生式編譯原理小題答案17 文法分為四種類型，即0 型、 1 型、 2 型、3 型。其中 2 型文法是 (D) 。A短語文法 B正則文法 C上下文有關(guān)文法D上下文無關(guān)文法18文法

10、G 所描述的語言是 (C) 的集合。A文法 G的字母表 Vxx 所有符號組成的符號串B文法 G 的字母表 V 的閉包 V*中的所有符號串C由文法的開始符號推出的所有xx 串D由文法的開始符號推出的所有符號串19文法分為四種類型，即0 型、 1 型、 2 型、 3 型。其中 0 型文法是 (A) 。A短語文法 B正則文法 C上下文有關(guān)文法D上下文無關(guān)文法20(A 是一種典型的解釋型語言。ABASICBCCFORTRANDPASCAL21與編譯系統(tǒng)相比，解釋系統(tǒng)(D) 。A比較簡單 ,可移植性好 ,執(zhí)行速度快B比較復(fù)雜 ,可移植性好 ,執(zhí)行速度快C比較簡單 ,可移植性差 ,執(zhí)行速度慢D比較簡單 ,

11、可移植性好 ,執(zhí)行速度慢22用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B) 。編譯原理小題答案A源程序 B目標(biāo)程序 C連接程序D解釋程序23編寫一個計算機高級語言的源程序后，到正式上機運行之前，一般要經(jīng)過 (B) 這幾步 :(1) 編輯(2)編譯(3)連接(4) 運行A(1)(2)(3)(4)B(1)(2)(3)C(1)(3)D (1)(4)24把匯編語言程序翻譯成機器可執(zhí)行的目標(biāo)程序的工作是由(B)完成的。A編譯器 B匯編器 C解釋器 D預(yù)處理器25詞法分析器的輸出結(jié)果是(C) 。A單詞的種別編碼B單詞在符號表中的位置C單詞的種別編碼和自身值D單詞自身值26 正規(guī)式 M1和 M2 等價是指(

12、C)。AM1和 M2的狀態(tài)數(shù)相等 BM1和 M2的有向邊條數(shù)相等CM1和 M2所識別的語言集相等DM1和 M2狀態(tài)數(shù)和有向邊條數(shù)相等27 文法 G：SxSx|y 所識別的語言是 (C) 。AxyxB(xyx)*C Dx*yx*28如果文法 G是無二義的，則它的任何句子 (A)。A最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C最左推導(dǎo)和最右推導(dǎo)必定相同D可能存在兩個不同的最左推導(dǎo)，但它們對應(yīng)的語法樹相同編譯原理小題答案29構(gòu)造編譯程序應(yīng)掌握 (D) 。A源程序 B目標(biāo)語言C編譯方法 D以上三項都是30四元式之間的聯(lián)系是通過(B) 實現(xiàn)的。A指示器 B臨時變量C符

13、號表 D程序變量31表達式 ( AB)(CD)的逆 xx 表示為 (B) 。A AB CDBABCD CAB CD DAB CD33 編譯程序是對 (D) 。A匯編程序的翻譯B高級語言程序的解釋執(zhí)行C機器語言的執(zhí)行D高級語言的翻譯34 采用自上而下分析，必須(C) 。A消除左遞歸 B消除右遞歸C消除回溯D提取公共左因子35在規(guī)范歸約中，用 ()B 來刻畫可歸約串。A直接短語 B句柄C最左素短語 D素短語36間接三元式表示法的優(yōu)點為(A) 。A采用間接碼表，便于優(yōu)化處理B節(jié)省存儲空間， 不便于表的修改C便于優(yōu)化處理，節(jié)省存儲空間D節(jié)省存儲空間，不便于優(yōu)化處理37在目標(biāo)代碼生成階段，符號表用(D)

14、 。編譯原理小題答案A目標(biāo)代碼生成B語義檢查C語法檢查D地址分配38下面關(guān)于解釋程序的描述正確的是B .(1) 解釋程序的特點是處理程序時不產(chǎn)生目標(biāo)代碼(2) 解釋程序適用于 COBOL和 FORTRAN語言(3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的A. (1)(2)B. (1)C. (1)(2)(3)D.(2)(3)39. 解釋程序處理語言時，大多數(shù)采用的是B 方法 .A. 源程序命令被逐個直接解釋執(zhí)行B. 先將源程序轉(zhuǎn)化為中間代碼，再解釋執(zhí)行C.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，在執(zhí)行D.以上方法都可以40. 用不同語言編寫的程序產(chǎn)生后，可用連接在一起生成機器可執(zhí)行的程序 . 在機器中

15、真正執(zhí)行的是 .上面三空格對應(yīng)的選項是：Aa.源程序 b.目標(biāo)程序c.函數(shù) d.過程e. 機器指令代碼 f. 模塊 g. 連接程序 h. 程序庫A. b 、g、eB. b 、c、eC. e 、g、fD. e 、c、f41. 由于受到具體機器主存容量的限制，編譯程序幾個不同階段的工作往往被組合成，諸階段的工作往往是進行的 . 上面兩空格對應(yīng)的選項是： Aa.過程b.程序c.批量d. 遍e.順序f.并行g(shù).成批h. 穿插編譯原理小題答案A. d 和 hB. d 和 eC. a 和 hD. a 和 e42. 編譯過程中，語法分析器的任務(wù)就是 B .(1) 分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如

16、何構(gòu)成語句和說明的(3)分析語句和說明是如何構(gòu)成程序的(4)分析程序的結(jié)構(gòu)A. (2)(3)B. (2)(3)(4)C. (1)(2)(3)D.(1)(2)(3)(4)43.編譯程序必須完成的工作有 A .(1) 詞法分析 (2) 語法分析 (3) 語義分析(4) 代碼生成 (5) 中間代碼生成 (6) 代碼優(yōu)化A. (1)(2)(3)(4)B. (1)(2)(3)(4)(5)C. (1)(2)(3)(4)(5)(6)D. (1)(2)(3)(4)(6)44按邏輯上劃分，編譯程序第二步工作是C。A. 語義分析 B. 詞法分析 C. 語法分析 D. 代碼優(yōu)化45已知語言 L= xnyyn | n

17、=1，則下述文法中，D可以產(chǎn)生語言 L。A 1.Z xZy|xAy|yB 1.A xAy2. A xAy|x2.A xC1.Z AyBD1.Z xAy2.AxA|x2.A xAy|y編譯原理小題答案3.ByB|y46喬姆斯基（Chomsky）把文法分為四種類型， 即 0 型、1 型、2 型、3 型。其中 3 型文法是 B。A. 短語文法 B. 正則文法 C.上下文有關(guān)文法D.上下文無關(guān)文法48設(shè) G是一個給定的文法， S是文法的開始符號，如果 Sx( 其中 xV*) ，則稱 x 是文法 G的一個 B 。A. 候選式 B. 句型 C. 單詞 D. 產(chǎn)生式49若一個文法是遞歸的，則它所產(chǎn)生的語言的

18、句子A 。A. 是無窮多個B.是有窮多個C. 是可枚舉的 D.個數(shù)是常量50文法的二義性和語言的二義性是兩個A的概念。A不同B相同C無法判斷 D不存在51. 在語法分析處理中， FIRST 集合、 FOLLOW集合、 SELECT集合均是 B。A. 非 xx 集 B.xx 集 C. 字母表 D. 狀態(tài)集52. 編譯程序中語法分析器接收以A為單位的輸入。A. 單詞 B. 表達式 C. 產(chǎn)生式 D. 句子編譯原理小題答案53.在 LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型C的 DFA狀態(tài)。A. 句柄 B. 前綴 C. 活前綴 D. LR(0) 項目三、是非題( 下列各題，你認為正確的，請在題干

19、的括號內(nèi)打“”，錯的打“”。 )1計算機高級語言翻譯成低級語言只有解釋一種方式。（X）2在編譯中進行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤。（ X）3甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。（X）4“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運行”這種說法。（X）5正則文法其產(chǎn)生式為Aa，ABb， A ，BVN，a、bVT。 （V）6產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。(X)7解釋程序適用于COBOL 和 FORTRAN語言。 (X)8正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。(V)編譯原理小題答案9如果一個文法存在某個句子

20、對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。(V)10編譯程序是對高級語言程序的解釋執(zhí)行。(X)11一個有限狀態(tài)自動機中，有且僅有一個唯一的終態(tài)。(X)12語法分析時必須先消除文法中的左遞歸。(X)13兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。(V )14設(shè) r 和 s 分別是正規(guī)式，則有L(r|s)=L(r)L(s)。(X)15確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。(V)16詞法分析作為單獨的一遍來處理較好。(X)17構(gòu)造 LR分析器的任務(wù)就是產(chǎn)生LR 分析表。 (V)18編譯程序與具體的機器有關(guān)，與具體的語言無關(guān)。(X)19每個文法都能改寫為LL(1) 文法。（ X）2

21、0遞歸下降法允許任一非xx 是直接左遞歸的。（ V）21遞歸下降分析法是自頂向下分析方法。(V)22一個 LL(l)文法一定是無二義的。 (V)23算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)。（X）24自底而上語法分析方法的主要問題是候選式的選擇。（X）25LR分析方法是自頂向下語法分析方法。（X）26簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部。（X）編譯原理小題答案27若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（ X）28一個句型的句柄一定是文法某產(chǎn)生式的右部。（V）29在 SLR(1) 分析法的名稱中， S 的含義是簡單的。 (V)30綜合屬性是用于“ 自上而下” 傳遞信息

22、。 (X)31一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。(V)32LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。(V)33規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。(V)34LR分析技術(shù)無法適用二義文法。(X)35逆 xx 表示法表示表達式時無須使用括號。(V)36逆 xx 法表示的表達式亦稱后綴式。(V)38在程序中標(biāo)識符的出現(xiàn)僅為使用性的。（X）39. 設(shè)為 a ，b ，則 a，ba， ， 都是上的正規(guī)式。（ X）40. 對于上下文無關(guān)文法 GS ，若 S AB 則 A 一定是一條產(chǎn)生式規(guī)則，其中 , , （ VTVN） * 。（ X）41. 對于逆 xx 后綴式

23、，無論從哪頭開始分析均可得到唯一正確的分解。（V）42. LR（0）分析法是一種規(guī)范歸約法。（V）編譯原理小題答案43. 算符優(yōu)先分析法只能用來分析算符優(yōu)先文法。（V）44. 解釋程序和編譯程序一樣，生成目標(biāo)代碼。（X）45. 編譯程序生成的目標(biāo)代碼只能是機器語言。（X）46. 等價文法是指兩個文法完全相同。（ X）47. 對于字母表 上的任一 NFA M，必存在 上與 NFA M 等價的DFA M。（ V）48. 每個文法都能改寫為 LL(1) 文法。 （X）49. 不存在正規(guī)文法能產(chǎn)生語言： L=anbn|n=1 （V）四、簡答題1、什么是句子？什么是語言 ?答：設(shè) G是一個給定的文法，

24、S 是文法的開始符號，如果S=*x（其中xVt* ），則稱 x 是文法的一個句子。設(shè) GS 是給定文法，則由文法 G所定義的語言 L(G) 可描述為 L(G) x S=*x,x VT*編譯原理小題答案2、已知文法 GE 為：ET|E+T|E -TTF|T*F|T/FF（ E）|i 該文法的開始符號（識別符號）是什么？請給出該文法的終結(jié)符號集合 VT和非終結(jié)符號集合 VN。 找出句型 T+T*F+i 的所有短語、簡單短語和句柄。答：該文法的開始符號（識別符號）是E。該文法的終結(jié)符號集合VT=+、- 、* 、/ 、（、）、 i 。非終結(jié)符號集合VN=E、T、F 。句型 T+T*F+I 的句柄為第一

25、個T。3、已知文法 GS 為：SdABAaA|aBBb| 編譯原理小題答案 GS 產(chǎn)生的語言是什么？ GS 能否改寫為等價的正規(guī)文法？答：GS 產(chǎn)生的語言是 L(GS)=danbm n1,m0 。 GS 能改寫為等價的正規(guī)文法 , 其改寫后的等價的正規(guī)文法 GS 為：S dAA aA|aB|aB bB|b5、證明下面文法GN是二義性文法。GN ： N SEES SDDE 0210D 0127、簡述 DFA與 NFA有何區(qū)別 ?答：編譯原理小題答案主要區(qū)別在于， 1.DFA 沒有 轉(zhuǎn)換；2.DFA 的狀態(tài)轉(zhuǎn)換函數(shù)是單值映射，即當(dāng)前狀態(tài)輸入一個字符后轉(zhuǎn)換到下一個狀態(tài)， 而 NFA的狀態(tài)轉(zhuǎn)換函數(shù)是非單值映射