編譯原理小題答案

1、編譯原理常見(jiàn)題型一、填空題1.編譯程序的工作過(guò)程一般可以劃分為 詞法分析 ， 語(yǔ)法分析 ， 中間代碼生成 ， 代碼優(yōu)化 (可省) ， 目標(biāo)代碼生成 等幾個(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)包括 表格處

2、理 和 出錯(cuò)處理 。其中，詞法分析器用于識(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)xS=>*x,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.

3、語(yǔ)法分析最常用的兩類(lèi)方法是 自上而下 和 自下而上 分析法。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)

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

5、言的_語(yǔ)法_規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的_語(yǔ)義_規(guī)進(jìn)行的。38語(yǔ)法分析器的輸入是_單詞符號(hào)_，其輸出是_語(yǔ)法單位_。40逆波蘭式 ab+c+ d*e- 所表達(dá)的表達(dá)式為_(kāi)(a+b+c)*d-c_ 。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à)的中間表

6、示形式可以有_逆波蘭_、四元式表示_與_三元式表示_等。51.自頂向下語(yǔ)法分析會(huì)遇到的主要問(wèn)題有 左遞歸 和 回溯 。52.已知文法GE：ET|E+T; TF|T*F; F(E)|i該文法的開(kāi)始符號(hào)是 ，終結(jié)符號(hào)集合VT是 ，非終結(jié)符號(hào)結(jié)合VN是 。二、單選題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)B方法。A源程序命令被逐

7、個(gè)直接解釋執(zhí)行B先將源程序轉(zhuǎn)化為中間代碼 , 再解釋執(zhí)行C先將源程序解釋轉(zhuǎn)化為目標(biāo)程序 , 再執(zhí)行D以上方法都可以4編譯程序是一種(B)。A匯編程序 B翻譯程序C解釋程序         D目標(biāo)程序5通常一個(gè)編譯程序中，不僅包含詞法分析，語(yǔ)法分析，中間代碼生成，代碼優(yōu)化，目標(biāo)代碼生成等五個(gè)部分，還應(yīng)包括(C)。A模擬執(zhí)行器             B解釋器     &

8、#160;C表格處理和出錯(cuò)處理     D符號(hào)執(zhí)行器6一個(gè)句型中的最左(B)稱(chēng)為該句型的句柄。A短語(yǔ)         B簡(jiǎn)單短語(yǔ)       C素短語(yǔ)          D終結(jié)符號(hào) 7文法 GE ：      ETET      TFTF  

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

10、中，分析的關(guān)鍵是(D)。A尋找句柄         B尋找句型       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)C文法。A短語(yǔ)結(jié)構(gòu)文法   

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

12、括四個(gè)組成部分，它們是：一組非終結(jié)符號(hào)，一組終結(jié)符號(hào)，一個(gè)開(kāi)始符號(hào)，以及一組(D)。 A句子 B句型C單詞 D產(chǎn)生式17 文法分為四種類(lèi)型，即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

13、短語(yǔ)文法    B正則文法     C上下文有關(guān)文法 D上下文無(wú)關(guān)文法20(A是一種典型的解釋型語(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目

14、標(biāo)程序      C連接程序 D解釋程序23編寫(xiě)一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后，到正式上機(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編譯器  

15、60;         B匯編器           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ù)相等C

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

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

18、序的解釋執(zhí)行C機(jī)器語(yǔ)言的執(zhí)行 D高級(jí)語(yǔ)言的翻譯 34 采用自上而下分析，必須(C)。A消除左遞歸  B消除右遞歸C消除回溯  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)代碼(

19、2) 解釋程序適用于COBOL 和 FORTRAN 語(yǔ)言(3) 解釋程序是為打開(kāi)編譯程序技術(shù)的僵局而開(kāi)發(fā)的   A. (1)(2)       B. (1)      C. (1)(2)(3)      D.(2)(3)39.解釋程序處理語(yǔ)言時(shí)，大多數(shù)采用的是 B 方法.A.源程序命令被逐個(gè)直接解釋執(zhí)行 B.先將源程序轉(zhuǎn)化為中間代碼，再解釋執(zhí)行 C.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序，在執(zhí)行 D.以上方法都可以40.用不同

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

21、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. 并行  g. 成批  h.穿插A. d和h B. d和e C. a和h D. a和e42.編譯過(guò)程中，語(yǔ)法分析器的任務(wù)就是 B . (1)分析單詞是怎樣構(gòu)成的        

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

24、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是文法的開(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 的概念

25、。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分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型 C 的DFA狀態(tài)。A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目三、是非題(下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“ ”，錯(cuò)的打“×”。)1計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。 （X）2在編譯中進(jìn)行語(yǔ)法檢查的目的是為

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

27、11一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一的終態(tài)。 (X)12語(yǔ)法分析時(shí)必須先消除文法中的左遞歸 。 (X)13兩個(gè)正規(guī)集相等的必要條件是他們對(duì)應(yīng)的正規(guī)式等價(jià)。 (V )14設(shè)r和s分別是正規(guī)式，則有L(r|s)=L(r)L(s)。 (X)15確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。 (V)16詞法分析作為單獨(dú)的一遍來(lái)處理較好。 (X)17構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。 (V)18編譯程序與具體的機(jī)器有關(guān)，與具體的語(yǔ)言無(wú)關(guān)。 (X)19每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法。 （X）20遞歸下降法允許任一非終結(jié)符是直接左遞歸的。 （V）21遞歸下降分析法是自頂向下分析方法。 (

28、V)22一個(gè) LL(l)文法一定是無(wú)二義的。 (V)23算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。 （X）24自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇。 （X）25LR分析方法是自頂向下語(yǔ)法分析方法。 （X）26簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部。 （X）27若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部，則此右部一定是該句型的句柄。（X）28一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。 （V）29在 SLR(1)分析法的名稱(chēng)中，S的含義是簡(jiǎn)單的。 (V)30綜合屬性是用于 “ 自上而下 ” 傳遞信息。 (X)31一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 (V)32LR分析法在自左至右掃描輸入

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

30、優(yōu)先文法。 （V）44. 解釋程序和編譯程序一樣，生成目標(biāo)代碼。 （X）45. 編譯程序生成的目標(biāo)代碼只能是機(jī)器語(yǔ)言。 （X）46. 等價(jià)文法是指兩個(gè)文法完全相同。 （X）47. 對(duì)于字母表上的任一NFA M'，必存在上與NFA M' 等價(jià)的DFA M。（V）48. 每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法。 （X）49. 不存在正規(guī)文法能產(chǎn)生語(yǔ)言：L=anbn|n>=1（V）四、簡(jiǎn)答題1、 什么是句子？ 什么是語(yǔ)言?答：設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S=>*x（其中xVt*），則稱(chēng)x是文法的一個(gè)句子。 設(shè)GS是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述

31、為 L(G)xS=>*x,xVT*2、已知文法GE為：ET|E+T|E-TTF|T*F|T/FF（E）|i 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是什么？請(qǐng)給出該文法的終結(jié)符號(hào)集合VT和非終結(jié)符號(hào)集合VN。 找出句型T+T*F+i的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。答： 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是E。 該文法的終結(jié)符號(hào)集合VT=+、-、*、/、（、）、i。  非終結(jié)符號(hào)集合VN=E、T、F。  句型T+T*F+I的句柄為第一個(gè)T。3、已知文法GS為：SdABAaA|aBBb| GS產(chǎn)生的語(yǔ)言是什么？ GS能否改寫(xiě)為等價(jià)的正規(guī)文法？答： GS產(chǎn)生的語(yǔ)言是L(GS)=danbmn1,m0。  GS能改寫(xiě)為等價(jià)的正規(guī)文法,其改寫(xiě)后的等價(jià)的 正規(guī)文法GS為：     SdA     A aA|aB|a     B bB|b5、證明下面文法GN是二義性文法。 GN： N SEE S SDD E