編譯原理期末練習題匯總

1、“編譯原理”練習題一、 選擇題1、匯編程序是將 a 翻譯成 b ,編譯程序是將 c 翻譯成 d .a.匯編語言程序 b.機器語言程序 c.高級語言程序d. a 或者 b e. a 或者 c f. b 或者 c2、下面關(guān)于解釋程序的描述正確的是 b . (1) 解釋程序的特點是處理程序時不產(chǎn)生目標代碼 (2) 解釋程序適用于COBOL 和 FORTRAN 語言 (3) 解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的 a. (1)(2) b. (1) c. (1)(2)(3) d.(2)(3)3、高級語言的語言處理程序分為解釋程序和編譯程序兩種.編譯程序有五個階段，而解釋程序通常缺少 (1)e 和 (

2、1)b .其中， (1)e 的目的是使最后階段產(chǎn)生的目標代碼更為高效. 與編譯系統(tǒng)相比，解釋系統(tǒng) (2)d .解釋程序處理語言時,大多數(shù)采用的是 (3)b 方法. (4)a 就是一種典型的解釋型語言. (1): a. 中間代碼生成 b.目標代碼生成 c.詞法分析 d.語法分析 e.代碼優(yōu)化 (2): a.比較簡單,可移植性好,執(zhí)行速度快 b.比較復雜,可移植性好,執(zhí)行速度快 c.比較簡單,可移植性差,執(zhí)行速度慢 d.比較簡單,可移植性好,執(zhí)行速度慢 (3): a.源程序命令被逐個直接解釋執(zhí)行 b.先將源程序轉(zhuǎn)化為之間代碼,再解釋執(zhí)行c.先將源程序解釋轉(zhuǎn)化為目標程序,在執(zhí)行 d.以上方法都可以

3、(4) : a. BASIC b. C c. FORTRAN d. PASCAL4、用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫 b .用不同語言編寫的程序產(chǎn)生 b 后,可用 g 連接在一起生成機器可執(zhí)行的程序.在機器中真正執(zhí)行的是 e .a. 源程序 b. 目標程序 c. 函數(shù) d. 過程 e. 機器指令代碼 f. 模塊 g. 連接程序 h.程序庫5、要在某一臺機器上為某種語言構(gòu)造一個編譯程序,必須掌握下述三方面的內(nèi)容: c , d , f .a. 匯編語言 b. 高級語言 c. 源語言 d. 目標語言e. 程序設計方法 f. 編譯方法 g. 測試方法 h. 機器語言6、由于受到具體機器主存容量

4、的限制,編譯程序幾個不同階段的工作往往被組合成 (1)d ,諸階段的工作往往是 (2)d 進行的. (1) a. 過程 b. 程序 c. 批量 d.遍 (2) a. 順序 b. 并行 c. 成批 d.穿插7、編譯過程中,語法分析器的任務就是 b . (1) 分析單詞是怎樣構(gòu)成的 (2) 分析單詞串是如何構(gòu)成語句和說明的 (3) 分析語句和說明是如何構(gòu)成程序的 (4) 分析程序的結(jié)構(gòu)8、編寫一個計算機高級語言的源程序后,到正式上機運行之前，一般要經(jīng)過 b 這幾步. (1) 編輯 (2) 編譯 (3) 連接 (4) 運行9、編譯程序必須完成的工作有 a . (1) 詞法分析 (2) 語法分析 (3

5、) 語義分析 (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) e. (1)(2)(3)(5)(6)10、編譯程序是一種 B 。A. 匯編程序 B. 翻譯程序 C. 解釋程序 D. 目標程序11、按邏輯上劃分，編譯程序第二步工作是 C 。A. 語義分析 B. 詞法分析 C. 語法分析 D. 代碼優(yōu)化12、通常一個編譯程序中，不僅包含詞法分析，語法分析，中間代碼生成，代碼優(yōu)化，目標代碼生成等五個部分，還應包括 C 。A.模擬執(zhí)行器 B.解釋

6、器 C.表格處理和出錯處理 D.符號執(zhí)行器13、文法G所描述的語言是 C 的集合。A.文法G的字母表V中所有符號組成的符號串B.文法G的字母表V的閉包V*中的所有符號串C.由文法的開始符號推出的所有終極符串D.由文法的開始符號推出的所有符號串14、喬姆斯基（Chomsky）把文法分為四種類型，即0型、1型、2型、3型。其中3型文法是 B 。A.短語文法 B.正則文法 C.上下文有關(guān)文法 D.上下文無關(guān)文法15、文法GN=（b，N，B，N，NbbB，BbN），該文法所描述的語言是 C 。A. L(GN)=bii0 B. L(GN)=b2ii0C. L(GN)=b2i+1i0 D. L(GN)=b

7、2i+1i116、一個句型中的最左 B 稱為該句型的句柄。可選項有：A. 短語 B. 簡單短語 C. 素短語 D. 終結(jié)符號17、設G是一個給定的文法，S是文法的開始符號，如果Sx(其中xV*),則稱x是文法G的一個 B 。A. 候選式 B. 句型 C. 單詞 D. 產(chǎn)生式18、一個上下文無關(guān)文法G包括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 D 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式19、文法GE：ETETTFTF Fa（E）該文法句型EF(ET)的簡單短語是下列符號串中的 B 。（ET） ET F F(ET)可選項有：A) 和 B) 和 C)

8、和 D) 20、若一個文法是遞歸的，則它所產(chǎn)生的語言的句子 A 。A.是無窮多個 B.是有窮多個 C.是可枚舉的 D.個數(shù)是常量21、詞法分析器用于識別 C 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式22、在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是 B 。A. 非終極符集 B.終極符集 C. 字母表 D. 狀態(tài)集23、編譯程序中語法分析器接收以 A 為單位的輸入。A. 單詞 B. 表達式 C. 產(chǎn)生式 D. 句子24、在自底向上的語法分析方法中，分析的關(guān)鍵是 A 。A. 尋找句柄 B. 尋找句型 C. 消除遞歸 D. 選擇候選式25、在LR分析法中，分析棧

9、中存放的狀態(tài)是識別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項目26、詞法分析的任務是（A）A識別單詞B.分析句子的含義C.識別句子D.生成目代碼27、代碼優(yōu)分的目的是（C）A.節(jié)省時間B.節(jié)省空間C.節(jié)省時間和空間D.把編譯程序進行等價交換28、代碼生成階段的主要任務是（C）A.把高級語言翻譯成匯編語言B.把高級語言翻譯成機器語言C.把中間代碼變換成依賴具體機器的目標代碼D.把匯編語言翻譯成機器語言29、在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項目30、一個上下文無關(guān)文法G包

10、括四個組成部分，它們是：一組非終結(jié)符號，一組終結(jié)符號，一個開始符號，以及一組 D 。A. 句子 B. 句型 C. 單詞 D. 產(chǎn)生式二、 是非判斷題1、正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 （）2、如果一個文法是遞歸的，則其產(chǎn)生的語言的句子是無窮個。 （）3、文法的二義性和語言的二義性是兩個不同的概念。 （）4、一個LL( l)文法一定是無二義的。 （）5、在規(guī)范規(guī)約中用最左素短語來刻劃可歸約串。 （）6、目標代碼生成時，應考慮如何充分利用計算機的寄存器的問題。 （）7、編譯程序是對匯編程序的翻譯。 （）8、計算機高級語言翻譯成低級語言只有解釋一種方式。 （）9、在編譯中進行語法檢

11、查的目的是為了發(fā)現(xiàn)程序中所有錯誤。 （）10、甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相同。 （）11、正則文法其產(chǎn)生式為Aa，ABb, A,BVN，a、bVT。 （）12、每個文法都能改寫為LL(1)文法。 （）13、遞歸下降法允許任一非終極符是直接左遞歸的。 （）14、算符優(yōu)先關(guān)系表不一定存在對應的優(yōu)先函數(shù)。 （）15、自底而上語法分析方法的主要問題是候選式的選擇。 （）16、LR法是自頂向下語法分析方法。 （）18、若一個句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。 （）19、一個句型的句柄一定是文法某產(chǎn)生式的右部。 （）20、在程序中標識

12、符的出現(xiàn)僅為使用性的。 （）21、在程序中標識符的出現(xiàn)僅為使用性的。 （）三、 名詞解釋題1、掃描遍：指編譯程序?qū)υ闯绦蚧蛑虚g代碼程序從頭到尾掃描一次。2、短語：設GZ是給定文法, w=xuyV+，為該文法的句型,如果滿足下面兩個條件: Z xUy； U u； 則稱句型xuy 中的子串u是句型xuy的短語。3、簡單短語：設GZ是給定文法, w=xuyV+，為該文法的句型,如果滿足下面兩個條件: Z xUy； U u； 則稱句型xuy 中的子串u是句型xuy的簡單短語（或直接短語）。4、句柄：一個句型中的最左簡單短語稱為該句型的句柄。5、語法分析：按文法的產(chǎn)生式識別輸入的符號串是否為一個句子的分

13、析過程。RR6、活前綴：若S A 是文法G中的一個規(guī)范推導，G是G的拓廣文法，符號串是的前綴，則稱是G的，也是G的一個活前綴。其中 S為文法開始符號。或：可歸前綴的任意首部。7、可歸前綴：是指規(guī)范句型的一個前綴，這種前綴不含句柄之后的任何符號。8、LR(0)項目：把產(chǎn)生式右部某位置上標有圓點的產(chǎn)生式稱為相應文法的一個LR(0)項目。9、語義規(guī)則：對于文法的每個產(chǎn)生式都配備了一組屬性的計算規(guī)則，稱為語義規(guī)則。10、翻譯方案：將屬性文法中的語義規(guī)則用花括號 括起來，插在產(chǎn)生式右部的合適地方，指明語義規(guī)則的計算次序，陳述一些細節(jié)，得到一種語義動作與語法分析交錯的表示方法，以表述語義動作在語法分析過程

14、中的執(zhí)行時刻，稱之為翻譯方案。11、后綴式： 一種把運算量（操作數(shù)）寫在前面把算符寫在后面（后綴）的表示法。即 一個表達式E的后綴形式可以如下定義：(1) 如果E是一個變量或常量，則E的后綴式是E自身。(2) 如果E是E1 op E2形式的表達式，這里op是任何二元操作符，則E的后綴式為E1 E2op，這里E1和E2分別為E1和E2的后綴式。(3) 如果E是（E1）形式的表達式，則E1的后綴式就是E的后綴式。12、過程活動：一個過程的活動指的是該過程的一次執(zhí)行。就是說，每次執(zhí)行一個過程體，產(chǎn)生該過程體的一個活動。13、活動記錄：為了管理過程在一次執(zhí)行中所需要的信息，使用一個連續(xù)的存儲塊，這樣一

15、個連續(xù)的存儲塊稱為活動記錄。14、活動的生存期：指的是從執(zhí)行某過程體第一步操作到最后一步操作之間的操作序，包括執(zhí)行過程時調(diào)用其它過程花費的時間。15、 基本塊的DAG：一個基本塊的DAG是一種其結(jié)點帶有下述標記或附加信息的DAG。 (1)圖的葉結(jié)點（沒有后繼的結(jié)點）以一標識符（變量名）或常數(shù)作為標記，表示該結(jié)點代表該變量或常數(shù)的值。如果葉結(jié)點用來代表某變量A的地址，則用addr（A）作為該結(jié)點的標記。通常把葉結(jié)點上作為標記的標識符加上下標0，以表示它是該變量的初值。 (2)圖的內(nèi)部結(jié)點（有后繼的結(jié)點）以一運算符作為標記，表示該結(jié)點代表應用該運算符對其后繼結(jié)點所代表的值進行運算的結(jié)果。 (3)圖

16、中各個結(jié)點上可能附加一個或多個標識符，表示這些變量具有該結(jié)點所代表的值。16、S-屬性文法：？什么是L-屬性文法？它們之間有什么關(guān)系？S-屬性文法是只含有綜合屬性的屬性文法。 17、L-屬性文法：L-屬性文法要求對于每個產(chǎn)生式AX1X2Xn，其每個語義規(guī)則中的每個屬性或者是綜合屬性，或者是Xj的一個繼承屬性，且該屬性僅依賴于：（1） 產(chǎn)生式Xj的左邊符號X1,X2Xj-1的屬性；（2） A的繼承屬性。 18、語法制導翻譯：語法制導翻譯是對前后文無關(guān)文法的擴充，即對文法中的每個產(chǎn)生式都附加一個語義動作或語義子程序，且在語法分析過程中，每當需要使用一個產(chǎn)生式進行推導或歸約時，語法分析程序除執(zhí)行相應

17、的語法分析動作外，還要執(zhí)行相應的語義動作或調(diào)用相應的語義子程序，完成相應的語義分析和翻譯工作。19、詞法分析詞法分析的主要任務是從左向右掃描每行源程序的符號，按照記法規(guī)則從構(gòu)成源程序的字符串中識別出一個個具有獨立意義的最小語法單位，并轉(zhuǎn)換成統(tǒng)一的內(nèi)部表示，送給語法分析程序。四、 簡答計算題1、已知文法GE為：ET|E+T|E-TTF|T*F|T/FF（E）|i 該文法的開始符號（識別符號）是什么？請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。 找出句型T+T*F+i的所有短語、簡單短語和句柄。答： 該文法的開始符號（識別符號）是E。該文法的終結(jié)符號集合VT=+、-、*、/、（、）、i。非

18、終結(jié)符號集合VN=E、T、F。句型T+T*F+I的短語為i、T*F、第一個T、T+T*F+i;簡單短語為i、T*F、第一個T;句柄為第一個T。2、已知文法GS為：SdABAaA|aBBb| GS產(chǎn)生的語言是什么？ GS能否改寫為等價的正規(guī)文法？答： GS產(chǎn)生的語言是L(GS)=danbmn1,m0。 GS能改寫為等價的正規(guī)文法,其改寫后的等價的正規(guī)文法GS為： SdA A aA|aB|a B bB|b3、簡述DFA與NFA有何區(qū)別 答：DFA與NFA的區(qū)別表現(xiàn)為兩個方面:一是NFA可以若干個開始狀態(tài)，而DFA僅只一個開始狀態(tài)。另一方面，DFA的映象M是從K到K，而NFA的映象M是從K到K的子集

19、，即映象M將產(chǎn)生一個狀態(tài)集合（可能為空集），而不是單個狀態(tài)。4、試給出非確定自動機的定義。答：一個非確定的有窮自動機（NFA）M是一個五元組：M=（K，S，P ）。其中:1. K是一個有窮集，它的每個元素稱為一個狀態(tài)；2. 是一個有窮字母表，它的每個元素稱為一個輸入符號，所以也稱為輸入符號表；3. SK是一個非空初態(tài)集； 4. P是狀態(tài)轉(zhuǎn)換函數(shù)，是在K*K的子集的映射，即，P: K*2K ；表明在某狀態(tài)下對于某輸入符號可能有多個后繼狀態(tài)。5、為正規(guī)式（a|b）*a(a|b) 構(gòu)造一個等價的確定的有限自動機。答：a,baab0126、給定下列自動機，將其轉(zhuǎn)換為確定的自動機。dddddddstar

20、tdSADBCEGH注：帶號的結(jié)點為初始狀態(tài)； 帶號的結(jié)點為終止狀態(tài)ddddddddddddSADBCEGH注：帶號的結(jié)點為初始狀態(tài)； 帶號的結(jié)點為終止狀態(tài)答：(1)消除邊，得到NFA：(2)確定化，得到DFA：ddSABCDEGHAABCEBCEBCDEHHGDG+SAABCEGDGHDHAABCEBCEBCEHDHHDHGGDGdddddddSAAAHBCEADGADHA注：帶號的結(jié)點為初始狀態(tài)； 帶號的結(jié)點為終止狀態(tài)G7、 給定下列自動機：其中：開始狀態(tài)：0 終止狀態(tài)：2aaa0bbb12(1)把此自動機轉(zhuǎn)換為確定自動機DFA。 (2)給出此DFA的正則表達式。答：（1）： 有狀態(tài)矩陣如

21、圖： a b0 01 201 01 22 1 2 1 2a b 0 0,1 2 1 2 2 1 2-02aaba101bbb極小化后：02babb1a從而可得DFA如圖：（2）此DFA的正則表達式為： (aa*bb)(bab)* 或 a*b（bab）*。4-13.消除下列文法GE的左遞歸。EE-TTTT/FFF( E )i答：消除文法GE的左遞歸后得到：ETEE -TETFTT/FTF( E )i8、在LL(1)分析法中,LL分別代表什么含義?答:第一個L代表從左到右的掃描，第二個L代表每次進行最左推導。9、自頂向下分析思想是什么？答：從開始符出發(fā)導出句型并一個符號一個符號地與給定終結(jié)符串進行

22、匹配。如果全部匹配成功，則表示開始符號可推導出給定的終結(jié)符串。因此判定給定終結(jié)符號串是正確句子。10、自頂向下的缺點是什么？答：在推導過程中，如果對文法不做限制。那么產(chǎn)生式的選擇成為無根據(jù)的，只好一一去試所有可能的產(chǎn)生式，直至成功為止。這種方法的致命弱點是不斷地回溯，大大影響速度。11、LL（1）文法的定義是什么？答：一個上下文無關(guān)文法是LL(1)文法的充分必要條件是每個非終結(jié)符A的兩個不同產(chǎn)生式，A,A；滿足SELECT(A )SELECT(A )=。其中，、不能同時。12、什么是文法的左遞歸？答：一個文法含有下列形式的產(chǎn)生式之一時：1)AA，AVN，V*2)AB，BA，A、BVN，、V*

23、則稱該文法是左遞歸的。13、遞歸下降法的主要思想是什么？答：對每個非終結(jié)符按其產(chǎn)生式結(jié)構(gòu)寫出相應語法分析子程序。因為文法遞歸相應子程序也遞歸，子程序的結(jié)構(gòu)與產(chǎn)生式結(jié)構(gòu)幾乎一致。所以稱此種方法稱為遞歸子程序法或遞歸下降法。14、自底向上分析法的原理是什么？答：在采用自左向右掃描，自底向上分析的前提下，該類分析方法是從輸入符號串入手，通過反復查找當前句型的句柄（最左簡單短語），并使用文法的產(chǎn)生式把句柄歸約成相應的非終極符來一步步地進行分析的。最終把輸入串歸約成文法的開始符號，表明分析成功。1 ZC S2 Cif E then3 SAE4 EEA5 EA6 Ai其中：Z、C、S、A、EVN ； if

24、、then、iVT15、給定文法GZ：a) 構(gòu)造此文法的LR(0)項目集規(guī)范族，并給出識別活前綴的DFA。b) 構(gòu)造其SLR（1）分析表。答：1.首先拓廣文法：在G中加入產(chǎn)生式0ZZ，然后得到新的文法G，再求G的識別全部活前綴的DFA：I0：Z.ZZ.C SC.if E thenI1：ZZ.I2：ZC .SS.AEA.iI3：Cif .E thenE.EAE.AA.iI4：ZC S.I5：SA.EI6：Ai.I7：Cif E .thenEE.AI9：SA.EE.EAE.AA.iI10：Cif E then.I11：EE.AA.iI12：SAE.EE.AI13：EEA.CSiAiiEAZI0I1

25、I6I5I2I3I7I9I12I13I11I10I8I4AtheniifEA2 Follow(Z)#Follow(C)iFollow(S)#Follow(E)#,thenFollow(A),# ,then 則可構(gòu)造SLR（1）分析表為：ACTIONGOTO0iftheni#ZCSEA0S3121OK2S6453S6784r15S96r6r6r6r67S10S118r5r5r59S612810r211S61312S11r313r4r4r416、 設有文法GS：SaAAAbAbI1:SS.I0:S.S S.aAI2:Sa.AA.AbA.baI3:SaA.AA.bAI4:AAb.Ab.bbS 求識別

26、該文法所有活前綴的DFA。答：(1).首先拓廣文法： 在G中加入產(chǎn)生式0.SS，然后得到新的文法G: 0.SS 1.SaA2.AAb3.Ab(2).再求G的識別全部活前綴的DFA：17、語法制導翻譯方法的基本思想是什么?答：在語法分析過程中，每當使用一條產(chǎn)生式進行推導或歸約時，就執(zhí)行該產(chǎn)生式所對應的語義動作進行屬性計算，完成對輸入符號串的翻譯。18、在一個屬性文法中，對應于每個產(chǎn)生式Aa都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為b：f（c1,c2，ck），其中對于b的要求是什么？答：語義規(guī)則中的左部屬性變量b被規(guī)定為只能是下述兩種變量： 對應產(chǎn)生式左部符號的綜合屬性變量； 對應產(chǎn)生式右部符

27、號的繼承屬性變量。19、對于文法G(E):ET|E+TTF|T*FF(E)|i1） 寫出句型(T*F+i)的最右推導并畫出語法樹。ETF(E)E+TFiTT*F2） 寫出上述句型的短語，直接短語和句柄。答：1.）ETF(E) (E+T) (E+F) (E+i) (T+i) (T*F+i) 2） 短語：(T*F+i), T*F+i, T*F, i直接短語：T*F, i句柄：T*F20、構(gòu)造下面文法的LL(1)分析表。S a B S | b A S | eA b A A | aB a B B | b 答： 開始符號集合和后繼符號集合LL(1)分析表FirstFollowSa, b, e$Aa, ba, b, $Ba, ba, b, $ab$SS a B SS b A SS eAA aA b A ABB a B BB b五、 綜合題1、通過構(gòu)造識別活前綴的DFA和構(gòu)造分析表，來證明文法E E + id | id是SLR(1)文法。答：先給出接受該文法活前綴的DFA如下：E EE E + idE idI0E EE E+ idI1E idI2Eid+E E +idI3E E + idI4id再構(gòu)造SLR分析表如下：狀態(tài) 動作轉(zhuǎn)移 id + $ E 0 s2 1 1 s3 acc 2 r2 r2 3 s4 4 r1 r1 表中沒有多重定義的條目，因此該