編譯原理復(fù)習(xí)題

1、編譯原理復(fù)習(xí)題一、填空題1.編譯程序的工作過(guò)程一般可以劃分為 詞法分析， 語(yǔ)法分析， 語(yǔ)義分析， 中間代碼優(yōu)化 ， 代碼優(yōu)化 等幾個(gè)基本階段。2.若源程序是用高級(jí)語(yǔ)言編寫(xiě)的，目標(biāo)程序是 匯編程序或機(jī)器語(yǔ)言程序 ，則其翻譯程序稱(chēng)為編譯程序.3.編譯方式與解釋方式的根本區(qū)別在于 是否生成目標(biāo)代碼 .5.對(duì)編譯程序而言，輸入數(shù)據(jù)是 源程序 ，輸出結(jié)果是 目標(biāo)程序 .7.若源程序是用高級(jí)語(yǔ)言編寫(xiě)的，目標(biāo)程序是機(jī)器語(yǔ)言程序或匯編程序 ，則其翻譯程序稱(chēng)為 編譯程序 。8.一個(gè)典型的編譯程序中，不僅包括詞法分析、語(yǔ)法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括 表格管理 和 出錯(cuò)處理 。其

2、中，詞法分析器用于識(shí)別 單詞 。10.一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成部分是 一組終結(jié)符號(hào)、 一組非終結(jié)符號(hào) 、 一個(gè)開(kāi)始符號(hào) 、 一組產(chǎn)生式 。12.產(chǎn)生式是用于定義 語(yǔ)法成分 的一種書(shū)寫(xiě)規(guī)則。13.設(shè)GS是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為： L(G)=x|Sx，xVT* 。14.設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果Sx（其中xV*），則稱(chēng)x是文法的一個(gè) 句型 。15.設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果Sx(其中xVT*)，則稱(chēng)x是文法的一個(gè) 句子 。16.掃描器的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè) 單詞符號(hào) 。17.語(yǔ)法分析最常用的兩類(lèi)方法是 自頂向下 和 自

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

4、思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地向上進(jìn)行 直接歸約 ，力求 歸約 到文法的 開(kāi)始符號(hào) 。26.在LR（0）分析法的名稱(chēng)中，L的含義是 自左向右的掃描輸入串 ，R的含義是 最左歸約，0 的含義是 向右查看輸入串符號(hào)的個(gè)數(shù)為0 。 31.終結(jié)符只有 ，它們由詞法分析器提供。32.在使用高級(jí)語(yǔ)言編程時(shí)，首先可通過(guò)編譯程序發(fā)現(xiàn)源程序的全部 語(yǔ)法 錯(cuò)誤和 語(yǔ)義 部分錯(cuò)誤.34一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱(chēng)為該句型的句柄。36從功能上說(shuō)，程序語(yǔ)言的語(yǔ)句大體可分為執(zhí)行性語(yǔ)句和說(shuō)明性語(yǔ)句兩大類(lèi)。37語(yǔ)法分析是依據(jù)語(yǔ)言的語(yǔ)法規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的語(yǔ)義規(guī)進(jìn)行的。38語(yǔ)法分析器的輸入是單詞

5、符號(hào)串，其輸出是語(yǔ)法單位。40逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為（a+b+c）*d-e 。41計(jì)算機(jī)執(zhí)行用高級(jí)語(yǔ)言編寫(xiě)的程序主要有兩種途徑：解釋和編譯。42自上而下分析法采用移進(jìn)、歸約、錯(cuò)誤處理、接收等四種操作。43一個(gè)LR分析器包括兩部分：一個(gè)總控程序和一張分析表。44后綴式abc-/所代表的表達(dá)式是a/(b-c)。 46語(yǔ)法分析基于上下文無(wú)關(guān)文法進(jìn)行，即識(shí)別的是該類(lèi)文法的句子。語(yǔ)法分析的有效工具是語(yǔ)法樹(shù)。48語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有逆波蘭、四元式與三元式等。51.自頂向下語(yǔ)法分析會(huì)遇到的主要問(wèn)題有回溯和左遞歸。52.已知文法GE：ET|E+T; T

6、F|T*F; F(E)|i該文法的開(kāi)始符號(hào)是E，終結(jié)符號(hào)集合VT是+,*,(,),，非終結(jié)符號(hào)結(jié)合VN是E,T,F。二、單選題1一個(gè)編譯程序中，不僅包含詞法分析，( A)，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分。A語(yǔ)法分析 B文法分析C語(yǔ)言分析D解釋分析2語(yǔ)法分析器則可以發(fā)現(xiàn)源程序中的(D )。A語(yǔ)義錯(cuò)誤   B語(yǔ)法和語(yǔ)義錯(cuò)誤C錯(cuò)誤并校正    D語(yǔ)法錯(cuò)誤3解釋程序處理語(yǔ)言時(shí) , 大多數(shù)采用的是(B)方法。A源程序命令被逐個(gè)直接解釋執(zhí)行B先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行C先將源程序解釋轉(zhuǎn)化為目標(biāo)程序 , 再執(zhí)行D以上方法都可以4編譯程序是一種(B)

7、。A匯編程序 B翻譯程序C解釋程序         D目標(biāo)程序5通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括(C)。A模擬執(zhí)行器             B解釋器      C表格處理和出錯(cuò)處理     D符號(hào)執(zhí)行器6一個(gè)句型中的最左(B)稱(chēng)為該句型的句柄。A短語(yǔ) &#

8、160;       B簡(jiǎn)單短語(yǔ)       C素短語(yǔ)          D終結(jié)符號(hào) 7文法 GE ：      ETET      TFTF      Fa(E)該文法句型 EF(ET)的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的(B)。 （ET）   E

9、T      F    F(ET) A 和 B 和 C 和 D 8詞法分析器用于識(shí)別(C)。A句子      B句型         C單詞         D產(chǎn)生式 9在自底向上的語(yǔ)法分析方法中，分析的關(guān)鍵是(A)。A尋找句柄         B尋找句型 &

10、#160;     C消除遞歸       D選擇候選式 10文法 G 產(chǎn)生的(D)的全體是該文法描述的語(yǔ)言。A句型 B終結(jié)符集 C非終結(jié)符集 D句子11若文法 G 定義的語(yǔ)言是無(wú)限集，則文法必然是(A)。  A遞歸的   B前后文無(wú)關(guān)的C二義性的 D無(wú)二義性的12四種形式語(yǔ)言文法中，1型文法又稱(chēng)為(C)文法。A短語(yǔ)結(jié)構(gòu)文法       B前后文無(wú)關(guān)文法 C前后文有關(guān)文法     D正規(guī)文法 13一個(gè)文法所

11、描述的語(yǔ)言是(A)。A唯一的   B不唯一的C可能唯一，好可能不唯一   D都不對(duì)14(B)和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A語(yǔ)法分析   B中間代碼生成C詞法分析       D目標(biāo)代碼生成 15(B)是兩類(lèi)程序語(yǔ)言處理程序。 A高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序B解釋程序和編譯程序 C編譯程序和操作系統(tǒng)D系統(tǒng)程序和應(yīng)用程序 16. 一個(gè)上下文無(wú)關(guān)文法G包括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組(D)。 A句子 B句型C單詞 D產(chǎn)生式17 文法分為四種類(lèi)型，

12、即0型、1型、2型、3型。其中2型文法是(D)。A短語(yǔ)文法    B正則文法     C上下文有關(guān)文法 D上下文無(wú)關(guān)文法18文法 G 所描述的語(yǔ)言是(C)的集合。 A文法G的字母表V中所有符號(hào)組成的符號(hào)串B文法 G 的字母表 V 的閉包 V* 中的所有符號(hào)串C由文法的開(kāi)始符號(hào)推出的所有終結(jié)符串D由文法的開(kāi)始符號(hào)推出的所有符號(hào)串19文法分為四種類(lèi)型，即0型、1型、2型、3型。其中0型文法是(A)。A短語(yǔ)文法    B正則文法     C上下文有關(guān)文法 D上下文無(wú)關(guān)文法20(A)

13、是一種典型的解釋型語(yǔ)言。  ABASIC BC CFORTRAN  DPASCAL21與編譯系統(tǒng)相比，解釋系統(tǒng)(D)。A比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度快 B比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快C比較簡(jiǎn)單 , 可移植性差 , 執(zhí)行速度慢 D比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度慢 22用高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序叫(B)。 A源程序       B目標(biāo)程序      C連接程序 D解釋程序23編寫(xiě)一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后，

14、到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(guò)(B)這幾步: (1) 編輯   (2) 編譯   (3) 連接   (4) 運(yùn)行 A(1)(2)(3)(4)     B(1)(2)(3)    C(1)(3)     D(1)(4)24把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由(B)完成的。A編譯器            B匯編器   

15、        C解釋器            D預(yù)處理器25詞法分析器的輸出結(jié)果是(C)。A單詞的種別編碼 B單詞在符號(hào)表中的位置C單詞的種別編碼和自身值 D單詞自身值26 正規(guī)式M 1和M 2 等價(jià)是指(C)。  AM1和M2的狀態(tài)數(shù)相等BM1和M2的有向邊條數(shù)相等CM1和M2所識(shí)別的語(yǔ)言集相等DM1和M2狀態(tài)數(shù)和有向邊條數(shù)相等 27 文法G：SxSx|y所識(shí)別的語(yǔ)言是(C)。Axyx  B(

16、xyx)* C     Dx*yx* 28如果文法G是無(wú)二義的，則它的任何句子 (A)。A最左推導(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ù)相同 29構(gòu)造編譯程序應(yīng)掌握(D)。A源程序   B目標(biāo)語(yǔ)言C編譯方法      D以上三項(xiàng)都是30四元式之間的聯(lián)系是通過(guò)(B)實(shí)現(xiàn)的。 A指示器         B臨

17、時(shí)變量C符號(hào)表             D程序變量 31表達(dá)式(AB)(CD)的逆波蘭表示為(B)。AABCD BABCD      CABCD      DABCD 33 編譯程序是對(duì)(D)。  A匯編程序的翻譯   B高級(jí)語(yǔ)言程序的解釋執(zhí)行C機(jī)器語(yǔ)言的執(zhí)行 D高級(jí)語(yǔ)言的翻譯 34 采用自上而下分析，必須(C)。A消除左遞歸  B消除右遞歸C消除回溯 &#

18、160;D提取公共左因子 35在規(guī)范歸約中，用(B)來(lái)刻畫(huà)可歸約串。A直接短語(yǔ) B句柄C最左素短語(yǔ)   D素短語(yǔ) 36間接三元式表示法的優(yōu)點(diǎn)為(A)。 A采用間接碼表，便于優(yōu)化處理B節(jié)省存儲(chǔ)空間，不便于表的修改C便于優(yōu)化處理，節(jié)省存儲(chǔ)空間 D節(jié)省存儲(chǔ)空間，不便于優(yōu)化處理 37在目標(biāo)代碼生成階段，符號(hào)表用(D)。A目標(biāo)代碼生成 B語(yǔ)義檢查C語(yǔ)法檢查 D地址分配38下面關(guān)于解釋程序的描述正確的是 B .(1) 解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼(2) 解釋程序適用于COBOL 和 FORTRAN 語(yǔ)言(3) 解釋程序是為打開(kāi)編譯程序技術(shù)的僵局而開(kāi)發(fā)的   A.

19、(1)(2)       B. (1)      C. (1)(2)(3)      D.(2)(3)40.用不同語(yǔ)言編寫(xiě)的程序產(chǎn)生 后，可用 連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是 . 上面三空格對(duì)應(yīng)的選項(xiàng)是： A a. 源程序          b. 目標(biāo)程序   c. 函數(shù)   

20、     d. 過(guò)程  e. 機(jī)器指令代碼    f. 模塊       g. 連接程序    h.程序庫(kù)A. b、g、e B. b、c、e C. e、g、f D. e、c、f41.由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工作往往被組合成 ，諸階段的工作往往是 進(jìn)行的. 上面兩空格對(duì)應(yīng)的選項(xiàng)是： A a. 過(guò)程  b. 程序  c. 批量  d.遍 e. 順序  f. 并行

21、  g. 成批  h.穿插A. d和h B. d和e C. a和h D. a和e42.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)就是 B . (1)分析單詞是怎樣構(gòu)成的           (2) 分析單詞串是如何構(gòu)成語(yǔ)句和說(shuō)明的 (3)分析語(yǔ)句和說(shuō)明是如何構(gòu)成程序的  (4) 分析程序的結(jié)構(gòu)A. (2)(3)     B. (2)(3)(4)     C. (1)(2)(3) &

22、#160;  D.(1)(2)(3)(4)43.編譯程序必須完成的工作有 A . (1) 詞法分析  (2) 語(yǔ)法分析        (3) 語(yǔ)義分析 (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)

23、(3)(4)(6)   44按邏輯上劃分，編譯程序第二步工作是 C 。A. 語(yǔ)義分析 B. 詞法分析 C. 語(yǔ)法分析 D. 代碼優(yōu)化45已知語(yǔ)言L= xnyyn | n>=1，則下述文法中， D 可以產(chǎn)生語(yǔ)言L。A 1.ZxZy|xAy|y B 1.AxAy 2. AxAy|x 2.AxC 1.ZAyB D 1.ZxAy 2.AxA|x 2.AxAy|y 3.ByB|y 46喬姆斯基（Chomsky）把文法分為四種類(lèi)型，即0型、1型、2型、3型。其中3型文法是 B 。A.短語(yǔ)文法 B.正則文法 C.上下文有關(guān)文法 D.上下文無(wú)關(guān)文法48設(shè)G是一個(gè)給定的文法，S是文法的

24、開(kāi)始符號(hào)，如果Sx(其中xV*)，則稱(chēng)x是文法G的一個(gè) B 。A. 候選式 B. 句型 C. 單詞 D. 產(chǎn)生式49若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子 A 。A.是無(wú)窮多個(gè) B.是有窮多個(gè) C.是可枚舉的 D.個(gè)數(shù)是常量50文法的二義性和語(yǔ)言的二義性是兩個(gè) A 的概念。A 不同 B 相同 C 無(wú)法判斷 D 不存在51.在語(yǔ)法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是 B 。A. 非終結(jié)符集 B.終結(jié)符集 C. 字母表 D. 狀態(tài)集52.編譯程序中語(yǔ)法分析器接收以 A 為單位的輸入。A. 單詞 B. 表達(dá)式 C. 產(chǎn)生式 D. 句子53. 在LR分析法中，分析棧中

25、存放的狀態(tài)是識(shí)別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目三、判斷題1計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。 （×）2在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。 （×）3甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相 同。 （×）4“用高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序都必須通過(guò)編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”說(shuō)法。（×）5正則文法其產(chǎn)生式為Aàa，AàBb， A，BVN，a、bVT。 （）6產(chǎn)生式是用于定義詞法成分的一種書(shū)寫(xiě)規(guī)則。 (×)7解釋

26、程序適用于 COBOL 和 FORTRAN 語(yǔ)言。 (×)8正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來(lái)描述。 ()9如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱(chēng)這個(gè)文法是二義的。 ()10編譯程序是對(duì)高級(jí)語(yǔ)言程序的解釋執(zhí)行。 (×)11一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。 (×)12語(yǔ)法分析時(shí)必須先消除文法中的左遞歸 。 (×)13兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 ( )14設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。 (×)15確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。 ()16詞法分析

27、作為單獨(dú)的一遍來(lái)處理較好。 (×)17構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。 ()18編譯程序與具體的機(jī)器有關(guān)，與具體的語(yǔ)言無(wú)關(guān)。 (×)19每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法。 （×）20遞歸下降法允許任一非終結(jié)符是直接左遞歸的。 （×）21遞歸下降分析法是自頂向下分析方法。 ()22一個(gè) LL(l)文法一定是無(wú)二義的。 ()23算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 （）24自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇。 （×）25LR分析方法是自頂向下語(yǔ)法分析方法。 （×）26簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。 （&

28、#215;）27若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（×）28一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 （）29在 SLR(1)分析法的名稱(chēng)中，S的含義是簡(jiǎn)單的。 ()30綜合屬性是用于 “ 自上而下 ” 傳遞信息。 (×)31一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 ()32LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。 ()33規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過(guò)程。 ()34LR分析技術(shù)無(wú)法適用二義文法。 (×)35逆波蘭表示法表示表達(dá)式時(shí)無(wú)須使用括號(hào)。 ()36逆波蘭法表示的表達(dá)式亦稱(chēng)后綴式 。 ()

29、38在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。 （×）39. 設(shè)為a，b，則a，ba，都是上的正規(guī)式。（×）40. 對(duì)于上下文無(wú)關(guān)文法GS，若 SAB 則A 一定是一條產(chǎn)生式規(guī)則，其中,（VTVN）*。 （×）41. 對(duì)于逆波蘭后綴式，無(wú)論從哪頭開(kāi)始分析均可得到唯一正確的分解。（）42. LR（0）分析法是一種規(guī)范歸約法。（）43. 算符優(yōu)先分析法只能用來(lái)分析算符優(yōu)先文法。 （）44. 解釋程序和編譯程序一樣，生成目標(biāo)代碼。 （×）45. 編譯程序生成的目標(biāo)代碼只能是機(jī)器語(yǔ)言。 （×）46. 等價(jià)文法是指兩個(gè)文法完全相同。 （×）47. 對(duì)于

30、字母表上的任一NFA M'，必存在上與NFA M' 等價(jià)的DFA M。（）48. 不存在正規(guī)文法能產(chǎn)生語(yǔ)言：L=anbn|n>=1（×）四、簡(jiǎn)答題1、什么是句子？ 什么是語(yǔ)言?句子：設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果Sx（其中xVT*），則稱(chēng)x是文法的一個(gè)句子。語(yǔ)言：句子的集合。設(shè)GS是給定文法，則由文法G所定義的語(yǔ)言L（G）可描述為：2、已知文法GE為：ET|E+T|E-TTF|T*F|T/FF（E）|i 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是什么？E請(qǐng)給出該文法的終結(jié)符號(hào)集合VT和非終結(jié)符號(hào)集合VN。答：VN=E,T,FVT=i,+,-,*,(,), 找

31、出句型T+T*F+i的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。答：短語(yǔ)T，T*F，i，T+T*F+i簡(jiǎn)單短語(yǔ)：T，T*F句柄：T3、已知文法GS為：SdABAaA|aBBb| GS產(chǎn)生的語(yǔ)言是什么？答：L(GS)=danbn|n1,m0 GS能否改寫(xiě)為等價(jià)的正規(guī)文法？答：能， GS，S，dABAaA|aB|aBbB|b5、證明下面文法GN是二義性文法。 GN： N SEE S SDD E 0210D 012證明：左推導(dǎo)1：N=>SE=>DE=>D0=>10 左推導(dǎo)2：N=>E=>107、 簡(jiǎn)述DFA與NFA有何區(qū)別 ? 答：DFA與NFA的區(qū)別：NFA可以有若干個(gè)開(kāi)始狀態(tài)

32、，而DFA僅只有一個(gè)開(kāi)始狀態(tài)；DFA的映象M是從K×到K，而NFA的映象M是從K×到K的子集，即映象M將產(chǎn)生一個(gè)狀態(tài)集合（可能為空集），而不是單個(gè)狀態(tài)。8、 試給出非確定自動(dòng)機(jī)的定義。答：一個(gè)NFA（M）是一個(gè)五元組：M=(K，f，S，Z)。(K是一個(gè)有窮集，它的每個(gè)元素稱(chēng)為一個(gè)狀態(tài)；(是一個(gè)有窮字母表，它的每個(gè)元素成為一個(gè)輸入符號(hào)，所以也稱(chēng)為輸入符號(hào)表；(f是狀態(tài)轉(zhuǎn)換函數(shù)，是在K×*K的子集的映射，即f：K×*ZK；表明在某狀態(tài)下對(duì)于某輸入符號(hào)可能有多個(gè)后繼狀態(tài)；SCK是一個(gè)非空初態(tài)集；ZCK是一個(gè)終態(tài)集（可空）。9、為正規(guī)式（a|b）*a(a|b)

33、構(gòu)造一個(gè)等價(jià)的確定的有限自動(dòng)機(jī)。10、構(gòu)造正規(guī)式相應(yīng)的 NFA : 1(0|1)*101 13、 編譯過(guò)程一般分為幾個(gè)階段？各階段的輸入輸出分別為什么？15、 在LL(1)分析法中，LL分別代表什么含義?答：第一個(gè)L表明自頂向下分析是從左向右掃描輸入串，第二個(gè)L表明分析過(guò)程中將用最左推導(dǎo)。16、文法G為： SaAB Aa B |則判斷G為L(zhǎng)L（1）文法的條件是：答：Sclect(SaAB)=aSclect(Aa)=aSclect(B|/y)=，y=17、文法G=(A, B, S, a, b, c, P, S) 其中P為： SAc|aB Aab Bbc 該文法是二義的嗎？說(shuō)明理由。答：是有二義性

34、的，因?yàn)榫渥觓bc 有兩棵語(yǔ)法樹(shù)(或稱(chēng)有兩個(gè)最左推導(dǎo)或有兩個(gè)最右推導(dǎo))最左推導(dǎo)1：S Ac abc最左推導(dǎo)2：S aB abc18、文法G=(E, +, *, i, (, ), P, E)其中P為： Ei EE+E EE*E E(E)該文法是二義的嗎？說(shuō)明理由。答： 是有二義性的，因?yàn)榫渥觟*i+i 有兩個(gè)最左推導(dǎo)最左推導(dǎo)1：EE+E E*E+E i*E+E i*i+E i*i+i最左推導(dǎo)2：EE*E i*E i*E+E i*i+E i*i+i19、 自頂向下分析思想是什么？答：從開(kāi)始符出發(fā)導(dǎo)出句型并一個(gè)符號(hào)一個(gè)符號(hào)地與給定終結(jié)符串進(jìn)行匹配。如果全部匹配成功，則表示開(kāi)始符號(hào)可推導(dǎo)出給定的終結(jié)符

35、串。因此判定給定終結(jié)符號(hào)串是正確句子。25、 簡(jiǎn)單優(yōu)先方法基本思想是什么？答：簡(jiǎn)單優(yōu)先方法基本思想是首先規(guī)定文法符號(hào)之間的優(yōu)先關(guān)系和結(jié)合性質(zhì)，然后再利用這種關(guān)系，通過(guò)比較兩個(gè)相鄰的符號(hào)之間的優(yōu)先順序來(lái)確定句型的“句柄”并進(jìn)行歸約。28、 語(yǔ)法制導(dǎo)翻譯方法的基本思想是什么?答：在語(yǔ)法分析過(guò)程中，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行該產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義動(dòng)作進(jìn)行屬性計(jì)算，完成對(duì)輸入符號(hào)串的翻譯。33、給定下列中綴式，分別寫(xiě)出等價(jià)的后綴式和四元式(運(yùn)算符優(yōu)先級(jí)按常規(guī)理解)。(1)(ab*c)/(ab)d答：后綴式：abc*+ab+/d-四元式：（*，b，c，t1） （+，a，t1，t2） （+，

36、a，b，t3） （/，t2,t3,t4） (-,t4,d,t5)一、最左、最右推導(dǎo)及語(yǔ)法樹(shù)1、令文法為 E®T|E+T|E-T T®F|T*F|T/F F®（E）|i1） 給出i+i*i的最左推導(dǎo)和最右推導(dǎo)；2） 給出i+i*i的最左推導(dǎo)語(yǔ)法樹(shù)。3、下面的文法生成的是以x和y為操作數(shù)、二元運(yùn)算符+、*和-為運(yùn)算符的前綴表達(dá)式： E®+EE|*EE|-EE|x|y1）給出串+*-xyxy的最左推導(dǎo)和最右推導(dǎo)；2）給出+*-xyxy的語(yǔ)法樹(shù)。4、一個(gè)上下文無(wú)關(guān)文法生成句子abbaa的推導(dǎo)樹(shù)如下：1） 給出該句子相應(yīng)的最左推導(dǎo)，最右推導(dǎo)。2） 該文法的產(chǎn)生式集

37、合P可能有哪些元素？二、自動(dòng)機(jī)的確定化和最小化1、將下圖中的自動(dòng)機(jī)確定化并最小化。3、試構(gòu)造正規(guī)式(0|1)*1(0|1)相應(yīng)的自動(dòng)機(jī)，并將其確定化4、試構(gòu)造正規(guī)式(a|b)*ab(a|b)*相應(yīng)的自動(dòng)機(jī)，并將其確定化和最小化。 三、FIRST和FOLLOW集合1、考慮下面文法G1： Sa|(T)TT，S|S1） 消去G1的左遞歸；2） 經(jīng)改寫(xiě)后的文法是否是LL(1)的？給出它的預(yù)測(cè)分析表(要求寫(xiě)出詳細(xì)過(guò)程，應(yīng)先求出每個(gè)非終結(jié)符的FIRST和FOLLOW集合)。2、判斷下面文法是否為L(zhǎng)L(1)文法，若是，請(qǐng)構(gòu)造相應(yīng)的預(yù)測(cè)分析表。SaD DSTe|TbH|HHd|3、對(duì)文法G(S)：S 

38、4; S Ú a T | a T | Ú a TT ® Ù a T | Ù a1）消除該文法的左遞歸和提取左公因子；2）構(gòu)造各非終結(jié)符的FIRST和FOLLOW集合；3）構(gòu)造該文法的LL(1)分析表，并判斷該文法是否是LL(1)的。四、短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)1、對(duì)于文法G（S）：S(L)|aS|aLL,S|S1）畫(huà)出句型(S,(a)的語(yǔ)法樹(shù)。2）寫(xiě)出上述句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)。2、文法GS為：SV VT | ViTTF| T+FF)V* |(1）畫(huà)出句型ViFi(的語(yǔ)法樹(shù)。2）寫(xiě)出上述句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)。3、對(duì)于文法G(E):E®T|E+TT®F|T*FF®(E)|i1） 畫(huà)出句型T*F+i1*i2的語(yǔ)法樹(shù)。2）寫(xiě)出上述句型的短語(yǔ)，直接短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)。答：短語(yǔ)：T*F +i1*i2, T*F, i1*i2 , i1, i2直接短語(yǔ)：T*F, i1, i2句柄：T*F素短語(yǔ)：T*F, i1, i2 最左素短語(yǔ)：T*F五、FIRSTVT集合和LASTVT集合，構(gòu)造優(yōu)先關(guān)系表1、設(shè)