編譯原理小題答案

1、.編譯原理常見(jiàn)題型一、填空題1.編譯程序的工作過(guò)程一般可以劃分為詞法分析，語(yǔ)法分析， 中間代碼生成， 代碼優(yōu)化 (可省 )， 目標(biāo)代碼生成等幾個(gè)基本階段。2.若源程序是用高級(jí)語(yǔ)言編寫的，目標(biāo)程序是機(jī)器語(yǔ)言程序或匯編程序，則其翻譯程序稱為編譯程序 .3.編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼.5.對(duì)編譯程序而言，輸入數(shù)據(jù)是源程序，輸出結(jié)果是目標(biāo)程序.7.若源程序是用高級(jí)語(yǔ)言編寫的，目標(biāo)程序是機(jī)器語(yǔ)言程序或匯編程序，則其翻譯程序稱為 編譯程序。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ǔ)法成分的一種書寫規(guī)則。13.設(shè) GS 是給定文法，則由文法G 所定義的語(yǔ)言 L(G) 可描述為：L(G) x S=>*x,x VT*。*14.設(shè) G 是一個(gè)給定的文法，S 是文法的開(kāi)始符號(hào)，如果Sx（其中 xV * ），則稱 x 是文法的一個(gè)句型。*15.設(shè) G 是一個(gè)給定的文法，S 是文法的開(kāi)始符號(hào)，如果Sx( 其中 x VT * )，則稱 x 是文法的一個(gè)句子。16.掃描器的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè)單詞符號(hào)。17.語(yǔ)法分析最常用的兩類方法

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）分析法的名稱中， L 的含義是自左向右的掃描輸入串，R 的含義是最左歸約， 0 的含義是 向貌似句柄的符號(hào)串后查看0 個(gè)輸入符號(hào)。31.終結(jié)符只有綜合屬性，它們由詞法分析器提供。1/12.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ō)明性 _語(yǔ)句兩大類。37語(yǔ)法分析是依據(jù)語(yǔ)言的_語(yǔ)法 _規(guī)則進(jìn)行的，中間代碼產(chǎn)生是依據(jù)語(yǔ)言的_語(yǔ)義

5、_規(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ǔ)言編寫的程序主要有兩種途徑：_解釋 _和 _編譯 _。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ù) _。48語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有_逆波蘭

6、_、四元式表示 _與 _三元式表示 _等。51. 自頂向下語(yǔ)法分析會(huì)遇到的主要問(wèn)題有左遞歸和 回溯。52. 已知文法GE ： E T|E+T; T F|T*F;F (E)|i該文法的開(kāi)始符號(hào)是，終結(jié)符號(hào)集合 VT 是，非終結(jié)符號(hào)結(jié)合VN是。2/12.二、單選題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 源程序命令被逐個(gè)直接解釋執(zhí)行B 先將源程序轉(zhuǎn)化為

7、中間代碼, 再解釋執(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：ET E TTF TFFa(E)該文法句型E F (E T)的簡(jiǎn)單短語(yǔ)是下列符號(hào)串中的(B)。 （ ET） ETF F (ET)A和B和C和D8詞法分析器用于識(shí)別(C)。A 句子B

8、句型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)。A 唯一的B不唯一的C可能唯一，好可能不唯一D都不對(duì)14 (B )和代碼優(yōu)化部分不是每個(gè)編譯程序都必需的。A 語(yǔ)法分析B中間代碼生成C

9、詞法分析D 目標(biāo)代碼生成15 (B )是兩類程序語(yǔ)言處理程序。A 高級(jí)語(yǔ)言程序和低級(jí)語(yǔ)言程序B解釋程序和編譯程序3/12.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ǔ)言是(C)的集合。A 文法 G 的字母表V 中所有符號(hào)組成的符號(hào)串B 文法G 的字母表V 的閉包V*中的所有符號(hào)串C由文法

10、的開(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ǔ)言。A BASICB CC FORTRAND PASCAL21與編譯系統(tǒng)相比，解釋系統(tǒng)(D )。A 比較簡(jiǎn)單, 可移植性好, 執(zhí)行速度快B 比較復(fù)雜, 可移植性好, 執(zhí)行速度快C比較簡(jiǎn)單, 可移植性差, 執(zhí)行速度慢D 比較簡(jiǎn)單, 可移植性好, 執(zhí)行速度慢22用高級(jí)語(yǔ)言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫(B)。A 源程序B 目標(biāo)程序C連接程序D解釋程序23編寫一

11、個(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 2 等價(jià)是指 (C)。A M1 和 M2 的狀態(tài)數(shù)相等B M1 和 M2 的有向邊條數(shù)相等C M1 和 M2 所識(shí)別的語(yǔ)言集相等D M1 和

12、M2 狀態(tài)數(shù)和有向邊條數(shù)相等27 文法 G： S xSx|y 所識(shí)別的語(yǔ)言是(C)。A xyxB (xyx)*C x n yxn (n0)D x*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臨時(shí)變量C符號(hào)表D 程序變量31表達(dá)式 ( A B) (C D) 的逆波蘭表示為(B )。4/12

13、.A AB CD B AB CD CAB CDD AB CD 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)刻畫可歸約串。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)于解釋

14、程序的描述正確的是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ǔ)言編寫的程序產(chǎn)生后，可用連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是. 上面三空格對(duì)應(yīng)的選項(xiàng)是：Aa. 源程序b. 目標(biāo)程序c. 函數(shù)d.

15、 過(guò)程e. 機(jī)器指令代碼f. 模塊g. 連接程序h.程序庫(kù)A. b 、 g、 eB. b、 c、 eC. e、g、 fD. e、 c、f41. 由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工作往往被組合成，諸階段的工作往往是進(jìn)行的 . 上面兩空格對(duì)應(yīng)的選項(xiàng)是：Aa. 過(guò)程b. 程序c. 批量d.遍e. 順序f. 并行g(shù). 成批h.穿插A. d 和 hB. d 和 eC. a 和 hD. 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.

16、 (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按邏輯上劃分，編譯程序第二步工作是C 。A. 語(yǔ)義分析B. 詞法分析C. 語(yǔ)法分析D. 代碼優(yōu)化5/12.45已知語(yǔ)言 L= x nyy n | n>=1 ，則下述文法中， D可以產(chǎn)生語(yǔ)言 L。A1.Z xZy|xAy|yB1.A xAy

17、2. A xAy|x2.A xC1.Z AyBD1.Z xAy2.A xA|x2.A xAy|y3.B yB|y46喬姆斯基（ 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(其中 x V * ) ，則稱 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的概念

18、。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)目6/12.三、是非題(下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打“”，錯(cuò)的打 “×”。)1計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。（ X ）2在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程

19、序中所有錯(cuò)誤。（ X ）3甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。（X ）4 “用高級(jí)語(yǔ)言書寫的源程序都必須通過(guò)編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行 ”這種說(shuō)法。（X ）5正則文法其產(chǎn)生式為A a，ABb ， A ，B V N ，a、 b V T。（ V ）6產(chǎn)生式是用于定義詞法成分的一種書寫規(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ù)，則稱這個(gè)文法是二義的。(V)10編譯程序是對(duì)高級(jí)語(yǔ)言程序的解釋執(zhí)行。(X)11一個(gè)有限狀態(tài)自動(dòng)

20、機(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è)文法都能改寫為L(zhǎng)L(1) 文法。（ X ）20遞歸下降法允許任一非終結(jié)符是直接左遞歸的。（ V ）21遞歸下降分析法是自頂向下分析方法。(V)22一個(gè) LL

21、(l) 文法一定是無(wú)二義的。(V)23算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。（ X ）24自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇。（ X ）25 LR 分析方法是自頂向下語(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) 分析法的名稱中， S 的含義是簡(jiǎn)單的。(V)30綜合屬性是用于“ 自上而下” 傳遞信息。(X)31一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。(V)32 LR 分析法在自左至右掃描輸入串時(shí)

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

23、3.算符優(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è)文法都能改寫為 LL(1) 文法。 （ X）49. 不存在正規(guī)文法能產(chǎn)生語(yǔ)言： L=a nbn|n>=1 （ V）8/12.四、簡(jiǎn)答題1、什么是句子？什么是語(yǔ)言 ?答：設(shè) G 是一個(gè)給定的文法，S 是文法的開(kāi)始符號(hào)，如果S=>*x （其中 x Vt* ），則稱

24、 x 是文法的一個(gè)句子。設(shè) GS 是給定文法，則由文法G 所定義的語(yǔ)言L(G) 可描述為L(zhǎng)(G) x S=>*x,x VT*2、已知文法GE 為：E T|E+T|E -TT F|T*F|T/FF （ E） |i 該文法的開(kāi)始符號(hào)（識(shí)別符號(hào)）是什么？請(qǐng)給出該文法的終結(jié)符號(hào)集合V T 和非終結(jié)符號(hào)集合V N。 找出句型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 為：S dABA aA|aB Bb| GS 產(chǎn)生的語(yǔ)言是什么？ GS 能否改寫為等價(jià)的正規(guī)文法？答： GS 產(chǎn)生的語(yǔ)言是L(GS)=danbm n 1,m 0 。 GS 能改寫為等價(jià)的正規(guī)文法 ,其改寫后的等價(jià)的正規(guī)文法 GS 為：S dAA aA|aB|a B bB|b5、證明下面文法GN 是二義性文法。GN ： N SEES SDDE 0 2 10 D 0 129/12.7、簡(jiǎn)述 DFA 與 NFA 有何區(qū)別?答：主要區(qū)別在于，1.DFA 沒(méi)有轉(zhuǎn)換； 2.DFA 的狀態(tài)轉(zhuǎn)換函數(shù)是單值映射，即當(dāng)前狀態(tài)輸入一個(gè)字符后轉(zhuǎn)換到下一個(gè)狀態(tài)，而NFA 的狀態(tài)轉(zhuǎn)換函數(shù)是非單值映射，也就是說(shuō)當(dāng)前狀態(tài)輸入一個(gè)字符