編譯原理小題答案

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

2、，還應(yīng)包括 表格處理 和 出錯(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,x VT* 。 *?是文x（其中xV是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S），則稱x14.設(shè)G 。 法的一個(gè) 句型 *?是文法x其中xV)，則稱15.設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果Sx(T 。的一個(gè) 句子 掃描器的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè) 單詞

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

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

5、_語(yǔ)句兩大類。 37語(yǔ)法分析是依據(jù)語(yǔ)言的_語(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í)別的是該類文法的句子。語(yǔ)法分析的有效工具是_語(yǔ)法樹(shù)

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

7、用的是(B)B方法。 A源程序命令被逐個(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解釋器 C表格處理和出錯(cuò)處理 D符號(hào)執(zhí)行器 6一個(gè)句型中的最左(B)稱為該句型的句柄。 A短語(yǔ) B簡(jiǎn)單短語(yǔ) C素短語(yǔ) D終結(jié)符號(hào) 7文法 GE ： ETET TFTF Fa(E) 該文法句型 EF(ET)的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的(B

8、)。 （ET） ET F F(ET) A 和 B 和 C 和 D 8詞法分析器用于識(shí)別(C)。 A句子 B句型 C單詞 D產(chǎn)生式 9在自底向上的語(yǔ)法分析方法中，分析的關(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型文法又稱為(C)C文法。 A短語(yǔ)結(jié)構(gòu)文法 B前后文無(wú)關(guān)文法 C前后文有關(guān)文法 D正規(guī)文法 13一個(gè)文法所描述的語(yǔ)言是(A)。 都不對(duì)

9、D 可能唯一，好可能不唯一C 不唯一的B 唯一的A 14(B)和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。 A語(yǔ)法分析 B中間代碼生成 C詞法分析 D目標(biāo)代碼生成 15(B)是兩類程序語(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 文法分為四種類型，即0型、1型、2型、3型。其中2型文法是(D)。 A短語(yǔ)文法 B正則文法 C上下文有關(guān)文法 D上下文無(wú)關(guān)文法 18文法 G 所描述的語(yǔ)

10、言是(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文法分為四種類型，即0型、1型、2型、3型。其中0型文法是(A)。 A短語(yǔ)文法 B正則文法 C上下文有關(guān)文法 D上下文無(wú)關(guān)文法 20(A是一種典型的解釋型語(yǔ)言。 ABASIC BC CFORTRAN DPASCAL 21與編譯系統(tǒng)相比，解釋系統(tǒng)(D)。 A比較簡(jiǎn)單 , 可移植性好 , 執(zhí)行速度快 B比較復(fù)雜 , 可移植性好 , 執(zhí)行速度快 C比較簡(jiǎn)單 , 可移植性差 , 執(zhí)行速度慢 D比較簡(jiǎn)單 , 可

11、移植性好 , 執(zhí)行速度慢 22用高級(jí)語(yǔ)言編寫(xiě)的程序經(jīng)編譯后產(chǎn)生的程序叫(B)。 A源程序 B目標(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編譯器 B匯編器 C解釋器 D預(yù)處理器 25詞法分析器的輸出結(jié)果是(C)。 A單詞的種別編碼 B單詞在符號(hào)表中的位置 C單詞的種別編碼和自身值 D單詞自身值 26 正規(guī)式M 1和M

12、 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)。 nn)n?0xyx( x*yx* (xyx)* C Bxyx A D 。)A (是無(wú)二義的，則它的任何句子G如果文法28 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

13、)實(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ǔ)言程序的解釋執(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)

14、化處理 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. (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.用不同語(yǔ)言編寫(xiě)的

15、程序產(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ù) A. b、g、e B. b、c、e C. e、g、f D. e、c、f 41.由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工作往往被組合成 ， 諸階段的工作往往是 進(jìn)行的. 上面兩空格對(duì)應(yīng)的選項(xiàng)是： A a. 過(guò)程 b. 程序 c. 批量 d.遍 e. 順序 f. 并行 g. 成批 h.穿插 e和h D. a和e C. a和h B. d和A. d42.編譯過(guò)程中，語(yǔ)

16、法分析器的任務(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) 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)(3)(4)(6) 44按邏輯上劃分，編譯程序第二步工

17、作是 C 。 A. 語(yǔ)義分析 B. 詞法分析 C. 語(yǔ)法分析 D. 代碼優(yōu)化 nn45已知語(yǔ)言L= xyy | n=1，則下述文法中， D 可以產(chǎn)生語(yǔ)言L。 A xZy|xAy|y B xAy 2. AxAy|x x C AyB D xAy xA|x xAy|y yB|y 46喬姆斯基（Chomsky）把文法分為四種類型，即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)，則稱x是文法G的一個(gè) B 。 A. 候選式 B. 句型 C. 單詞 D. 產(chǎn)生式 49若

18、一個(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分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型 C 的DFA狀態(tài)。 A.句柄 B. 前綴 C. 活前綴 D. LR(0)項(xiàng)目

19、 三、是非題 )(下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“ ”，錯(cuò)的打“”。 ）計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。 （X1 ）在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。 （X2 甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相3 ）同。 （X產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說(shuō)法?！坝酶呒?jí)語(yǔ)言書(shū)寫(xiě)的源程序都必須通過(guò)編譯，4 ）（XABb， A，BV，a、bV。 5正則文法其產(chǎn)生式為（Aa，V） TN6產(chǎn)生式是用于定義詞法成分的一種書(shū)寫(xiě)規(guī)則。 (X) 7解釋程序適用于 COBOL 和 FORTRAN 語(yǔ)言。 (X) 8正規(guī)文法產(chǎn)生的語(yǔ)言都可以

20、用上下文無(wú)關(guān)文法來(lái)描述。 (V) 9如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹(shù)，則稱這個(gè)文法是二義的。 (V) 10編譯程序是對(duì)高級(jí)語(yǔ)言程序的解釋執(zhí)行。 (X) 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編譯程序與具體的

21、機(jī)器有關(guān)，與具體的語(yǔ)言無(wú)關(guān)。 (X) 19每個(gè)文法都能改寫(xiě)為L(zhǎng)L(1)文法。 （X） 20遞歸下降法允許任一非終結(jié)符是直接左遞歸的。 （V） 21遞歸下降分析法是自頂向下分析方法。 (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在 S

22、LR(1)分析法的名稱中，S的含義是簡(jiǎn)單的。 (V) 30綜合屬性是用于 “ 自上而下 ” 傳遞信息。 (X) 31一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。 (V) 32LR分析法在自左至右掃描輸入串時(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á)式亦稱后綴式 。 (V) ）X（ 在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。3839. 設(shè)為a，b，則a，ba，都是上的正規(guī)式。（X） ?則A S一定是一條產(chǎn)生式規(guī)則，AB 40.

23、 對(duì)于上下文無(wú)關(guān)文法GS，若* （X） V） 。 ,其中,（VNT41. 對(duì)于逆波蘭后綴式，無(wú)論從哪頭開(kāi)始分析均可得到唯一正確的分解。（V） 42. LR（0）分析法是一種規(guī)范歸約法。 （V） 43. 算符優(yōu)先分析法只能用來(lái)分析算符優(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） nn （b不存在正規(guī)文法能產(chǎn)生語(yǔ)言：49. L=a

24、|n=1V） 四、簡(jiǎn)答題1、什么是句子？ 什么是語(yǔ)言? 答： 設(shè)G是一個(gè)給定的文法，S是文法的開(kāi)始符號(hào)，如果S=*x（其中xVt*），則稱x是文法的一個(gè)句子。 設(shè)GS是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為L(zhǎng)(G)xS=*x,x VT* 、已知文法GE為：2 ET|E+T|E-T TF|T*F|T/F ）|iF（E 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是什么？ V。請(qǐng)給出該文法的終結(jié)符號(hào)集合V和非終結(jié)符號(hào)集合NT 的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。 找出句型T+T*F+i 。答： 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是E /、（、）、i。 、 該文法的終結(jié)符號(hào)集合VT=+-、*、 。 、T、FVN=E 非終結(jié)符號(hào)集合 T。句型T+T*F+I的句柄為第一個(gè) 為：3、已知文法GS SdAB AaA|a BBb| GS產(chǎn)生的語(yǔ)言是什么？ GS能否改寫(xiě)為等價(jià)的正規(guī)文法？ 。 GS產(chǎn)生的語(yǔ)言是L(GS)=danbmn1,m0答： 其改寫(xiě)后的等價(jià)的能改寫(xiě)為等價(jià)的正規(guī)文法,GS 正規(guī)文法GS為： SdA A aA|aB|a B bB|b GN、證明下面文法是二義性文法。 5 GN：N SEE S SDD E 0210 D 0127、簡(jiǎn)述DFA與NFA有何區(qū)別 ? 答： 主要區(qū)別在于，沒(méi)有轉(zhuǎn)換；的狀態(tài)轉(zhuǎn)換函數(shù)是單值映射，即當(dāng)前狀態(tài)輸入一個(gè)字符后轉(zhuǎn)換到下