編譯原理小題答案

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)xS=>*x,xVT*  。14.設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx（其中xV*），則稱x是文法的一個 句型 。15.設(shè)G是一個給定的文法，S是文法的開始符號，如果Sx(其中xVT*)，則稱x是文法的一個 句子 。16.掃描器的任務(wù)是從源程序中識別出一個個 單詞符號 。17.

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

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

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

6、示形式可以有_逆波蘭_、四元式表示_與_三元式表示_等。51.自頂向下語法分析會遇到的主要問題有 左遞歸 和 回溯 。52.已知文法GE：ET|E+T; TF|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解釋程序處理語言時 , 大多數(shù)采用的是(B)B方法。A源程序命令被逐

7、個直接解釋執(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解釋器     &

8、#160;C表格處理和出錯處理     D符號執(zhí)行器6一個句型中的最左(B)稱為該句型的句柄。A短語         B簡單短語       C素短語          D終結(jié)符號 7文法 GE ：      ETET      TFTF  

9、0;   Fa(E)該文法句型 EF(ET)的簡單短語是下列符號串中的(B)。 （ET）   ET      F    F(ET) A 和 B 和 C 和 D 8詞法分析器用于識別(C)。A句子      B句型         C單詞         D產(chǎn)生式 9在自底向上的語法分析方法

10、中，分析的關(guān)鍵是(D)。A尋找句柄         B尋找句型       C消除遞歸       D選擇候選式 10文法 G 產(chǎn)生的( D)的全體是該文法描述的語言。A句型 B終結(jié)符集 C非終結(jié)符集 D句子11若文法 G 定義的語言是無限集，則文法必然是(A)。  A遞歸的   B前后文無關(guān)的C二義性的 D無二義性的12四種形式語言文法中，1型文法又稱為(C)C文法。A短語結(jié)構(gòu)文法   

11、;    B前后文無關(guān)文法 C前后文有關(guān)文法     D正規(guī)文法 13一個文法所描述的語言是(A)。A唯一的   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包

12、括四個組成部分，它們是：一組非終結(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文法 G 所描述的語言是(C)的集合。 A文法G的字母表V中所有符號組成的符號串B文法 G 的字母表 V 的閉包 V* 中的所有符號串C由文法的開始符號推出的所有終結(jié)符串D由文法的開始符號推出的所有符號串19文法分為四種類型，即0型、1型、2型、3型。其中0型文法是(A)。A

13、短語文法    B正則文法     C上下文有關(guān)文法 D上下文無關(guān)文法20(A是一種典型的解釋型語言。  ABASIC BC CFORTRAN  DPASCAL21與編譯系統(tǒng)相比，解釋系統(tǒng)(D)。A比較簡單 , 可移植性好 , 執(zhí)行速度快 B比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快C比較簡單 , 可移植性差 , 執(zhí)行速度慢 D比較簡單 , 可移植性好 , 執(zhí)行速度慢 22用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)。 A源程序       B目

14、標(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編譯器  

15、60;         B匯編器           C解釋器            D預(yù)處理器25詞法分析器的輸出結(jié)果是(C)。A單詞的種別編碼 B單詞在符號表中的位置C單詞的種別編碼和自身值 D單詞自身值26 正規(guī)式M 1和M 2 等價是指(C)。  AM1和M2的狀態(tài)數(shù)相等BM1和M2的有向邊條數(shù)相等C

16、M1和M2所識別的語言集相等DM1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 27 文法G：SxSx|y所識別的語言是(C)。Axyx  B(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

17、四元式之間的聯(lián)系是通過(B)實現(xiàn)的。 A指示器         B臨時變量C符號表             D程序變量 31表達(dá)式(AB)(CD)的逆波蘭表示為(B)。AABCD BABCD      CABCD      DABCD 33 編譯程序是對(D)。  A匯編程序的翻譯   B高級語言程

18、序的解釋執(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)。A目標(biāo)代碼生成 B語義檢查C語法檢查 D地址分配38下面關(guān)于解釋程序的描述正確的是 B .(1) 解釋程序的特點是處理程序時不產(chǎn)生目標(biāo)代碼(

19、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.用不同

20、語言編寫的程序產(chǎn)生 后，可用 連接在一起生成機器可執(zhí)行的程序.在機器中真正執(zhí)行的是 . 上面三空格對應(yīng)的選項是：A a. 源程序          b. 目標(biāo)程序   c. 函數(shù)        d. 過程  e. 機器指令代碼    f. 模塊       g. 連接程序    h.程序庫

21、A. b、g、e B. b、c、e C. e、g、f D. e、c、f41.由于受到具體機器主存容量的限制，編譯程序幾個不同階段的工作往往被組合成 ，諸階段的工作往往是 進(jìn)行的. 上面兩空格對應(yīng)的選項是： A a. 過程  b. 程序  c. 批量  d.遍 e. 順序  f. 并行  g. 成批  h.穿插A. d和h B. d和e C. a和h D. a和e42.編譯過程中，語法分析器的任務(wù)就是 B . (1)分析單詞是怎樣構(gòu)成的        

22、60;  (2) 分析單詞串是如何構(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

23、) 中間代碼生成    (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>=1，則下述文法中， D 可以產(chǎn)生語言L。A 1.ZxZy|xAy|y B 1.

24、AxAy 2. AxAy|x 2.AxC 1.ZAyB D 1.ZxAy 2.AxA|x 2.AxAy|y 3.ByB|y 46喬姆斯基（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)生的語言的句子 A 。A.是無窮多個 B.是有窮多個 C.是可枚舉的 D.個數(shù)是常量50文法的二義性和語言的二義性是兩個 A 的概念

25、。A 不同 B 相同 C 無法判斷 D 不存在51.在語法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是 B 。A. 非終結(jié)符集 B.終結(jié)符集 C. 字母表 D. 狀態(tài)集52.編譯程序中語法分析器接收以 A 為單位的輸入。A. 單詞 B. 表達(dá)式 C. 產(chǎn)生式 D. 句子53. 在LR分析法中，分析棧中存放的狀態(tài)是識別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項目三、是非題(下列各題，你認(rèn)為正確的，請在題干的括號內(nèi)打“ ”，錯的打“×”。)1計算機高級語言翻譯成低級語言只有解釋一種方式。 （X）2在編譯中進(jìn)行語法檢查的目的是為

26、了發(fā)現(xiàn)程序中所有錯誤。 （X）3甲機上的某編譯程序在乙機上能直接使用的必要條件是甲機和乙機的操作系統(tǒng)功能完全相 同。 （X）4“用高級語言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運行”這種說法。（X）5正則文法其產(chǎn)生式為Aàa，AàBb， A，BVN，a、bVT。 （V）6產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。 (X)7解釋程序適用于 COBOL 和 FORTRAN 語言。 (X)8正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。 (V)9如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹，則稱這個文法是二義的。 (V)10編譯程序是對高級語言程序的解釋執(zhí)行。 (X)

27、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）20遞歸下降法允許任一非終結(jié)符是直接左遞歸的。 （V）21遞歸下降分析法是自頂向下分析方法。 (

28、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綜合屬性是用于 “ 自上而下 ” 傳遞信息。 (X)31一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。 (V)32LR分析法在自左至右掃描輸入

29、串時就能發(fā)現(xiàn)錯誤，但不能準(zhǔn)確地指出出錯地點。 (V)33規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。 (V)34LR分析技術(shù)無法適用二義文法。 (X)35逆波蘭表示法表示表達(dá)式時無須使用括號。 (V)36逆波蘭法表示的表達(dá)式亦稱后綴式 。 (V)38在程序中標(biāo)識符的出現(xiàn)僅為使用性的。 （X）39. 設(shè)為a，b，則a，ba，都是上的正規(guī)式。（X）40. 對于上下文無關(guān)文法GS，若 SAB 則A 一定是一條產(chǎn)生式規(guī)則，其中,（VTVN）*。 （X）41. 對于逆波蘭后綴式，無論從哪頭開始分析均可得到唯一正確的分解。（V）42. LR（0）分析法是一種規(guī)范歸約法。（V）43. 算符優(yōu)先分析法只能用來分析算符

30、優(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是一個給定的文法，S是文法的開始符號，如果S=>*x（其中xVt*），則稱x是文法的一個句子。 設(shè)GS是給定文法，則由文法G所定義的語言L(G)可描述

31、為 L(G)xS=>*x,xVT*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的句柄為第一個T。3、已知文法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|b5、證明下面文法GN是二義性文法。 GN： N SEE S SDD E