編譯原理小題答案

《編譯原理》常見題型

一、填空題

1.編譯程序的工作過程一般可以劃分為母法殳近，語(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ò)處理。其中，詞法分析器用于識(shí)別單詞。

10.一個(gè)上下文無(wú)關(guān)文法所含四個(gè)組成部分是一組終結(jié)符號(hào)、一組非終結(jié)符號(hào)、一個(gè)開始符

號(hào)、一組產(chǎn)生式。

12.產(chǎn)生式是用于定義語(yǔ)法成分的一種書寫規(guī)則。

13.設(shè)G［S］是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為：L(G)={xIS=>*x,x￡

VT*］。

14.設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果sgx(其中x￡V?),則稱x是

文法的一個(gè)句型。

15.設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果Snx(其中x￡V/),則稱x是文

法的一個(gè)句子。

16.掃描器的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè)單詞符號(hào)。

17.語(yǔ)法分析最常用的兩類方法是自上而下和自下而上分析法。

18.語(yǔ)法分析的任務(wù)是識(shí)別給定的終結(jié)符串是否為給定文法的近。

19.遞歸下降法不允許任一非終結(jié)符是直接左遞歸的。

20.自頂向下的語(yǔ)法分析方法的關(guān)鍵是如何選擇候選式的問題。

21.遞歸下降分析法是自頂向下分析方法。

22.自頂向下的語(yǔ)法分析方法的基本思想是：從文法的開始符號(hào)開始,根據(jù)給定的輸入串并

按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo)，試圖推導(dǎo)出文法的包壬，使之與給定的

輸入串匹配。

23.自底向上的語(yǔ)法分析方法的基本思想是：從給定的終結(jié)符串開始，根據(jù)文法的規(guī)則一步

一步的向上進(jìn)行直接歸約,試圖歸約到文法的開始符號(hào)。

24.自底向上的語(yǔ)法分析方法的基本思想是：從輸入串入手，利用文法的產(chǎn)生式一步一步地

向上進(jìn)行直接歸約，力求歸約到文法的開始符號(hào)。

26.在LR(0)分析法的名稱中，L的含義是自左向右的掃描輸入串,R的含義是最左歸約,

0的含義是向貌似句柄的符號(hào)串后查看0個(gè)輸入符號(hào)。

31.終結(jié)符只有綜合屬性，它們由詞法分析器提供。

32.在使用高級(jí)語(yǔ)言編程時(shí)，首先可通過編譯程序發(fā)現(xiàn)源程序的全部A(語(yǔ)法)錯(cuò)誤和B(語(yǔ)

義)部分錯(cuò)誤.

34.一個(gè)句型中的最左簡(jiǎn)單短語(yǔ)稱為該句型的一句柄一。

36.從功能上說，程序語(yǔ)言的語(yǔ)句大體可分為_執(zhí)行性—語(yǔ)句和說明性一語(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á)式為_(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ǔ)法樹O

48.語(yǔ)義分析階段所生成的與源程序等價(jià)的中間表示形式可以有一逆波蘭一、四元式表示_

與一三元式表示一等。

51.自頂向下語(yǔ)法分析會(huì)遇到的主要問題有左遞歸和［可溯。

52.已知文法G［E］：E-T|E+T;T-F|T*F;F-(E)|i該文法的開始符號(hào)是，終結(jié)符號(hào)集

合片是，非終結(jié)符號(hào)結(jié)合VN是。

二、單選題

I.一個(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)化為中間代碼，再解釋執(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.文法G［E］：

E->TIE+T

T—FIT*F

F-aI(E)

該文法句型E+F?(E+T)的簡(jiǎn)及短語(yǔ)是下列符號(hào)串中的(B)。

①(E+T)②E+T③F④F*(E+T)

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),

A.唯一的B.不唯的C.可能唯一，好可能不唯一D.都不對(duì)

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è)開始符號(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.由文法的開始符號(hào)推出的所有終結(jié)符串

D.由文法的開始符號(hào)推出的所有符號(hào)串

19.文法分為四種類型，即。型、1型、2型、3型。其中0型文法是(A)。

A.短語(yǔ)文法B.正則文法C.上下文有關(guān)文法D.上下文無(wú)關(guān)文法

20.(A是一種典型的解釋型語(yǔ)言.

A.BASICB.CC.FORTRAND.PASCAL

21.與編譯系統(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.編寫一個(gè)計(jì)算機(jī)高級(jí)語(yǔ)言的源程序后，到正式上機(jī)運(yùn)行之前，一般要經(jīng)過(B)這幾步：

(1)編輯(2)編譯(3)連接(4)運(yùn)行

A.(D(2)(3)(4)B.(1)(2)(3)C.(1)(3)D.⑴(4)

24.把匯編語(yǔ)言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由(B)完成的。

A.編譯器B.匯編器C.解釋器D.預(yù)處理器

25.詞法分析器的輸出結(jié)果是(C)。

A.單詞的種別編碼B.單詞在符號(hào)表中的位置

C.單詞的種別編碼和自身值D.單詞自身值

26.正規(guī)式M1和M2等價(jià)是指(C)。

A.Ml和M2的狀態(tài)數(shù)相等B.Ml和M2的有向邊條數(shù)相等

C.Ml和M2所識(shí)別的語(yǔ)言集相等D.Ml和M2狀態(tài)數(shù)和有向邊條數(shù)相等

27.文法G：S—xSx卜所識(shí)別的語(yǔ)言是(C)。

A.xyxB.(xyx)*C.xnyxn(n>0)D.x*yx*

28.如果文法G是無(wú)二義的，則它的任何句子a(A)o

A.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同

B.最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能不同

C.最左推導(dǎo)和最右推導(dǎo)必定相同

D.可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹相同

29.構(gòu)造編譯程序應(yīng)掌握(D)。

A.源程序B.目標(biāo)語(yǔ)言C.編譯方法D.以上三項(xiàng)都是

30.四元式之間的聯(lián)系是通過(B)實(shí)現(xiàn)的。

A.指示器B.臨時(shí)變量C.符號(hào)表D.程序變量

31.表達(dá)式(1AVB)八(CVD)的逆波蘭表示為(B)。

A.1ABVACDVB.A-|BVCDVAC.ABV-|CDVAD.AqBVACDV

33.編譯程序是對(duì)(D)。

A.匯編程序的翻譯B.高級(jí)語(yǔ)言程序的解釋執(zhí)行

C.機(jī)器語(yǔ)言的執(zhí)行D.高級(jí)語(yǔ)言的翻譯

34.采用自上而下分析，必須(C).

A.消除左遞歸B.消除右遞歸C.消除回溯D.提取公共左因子

35.在規(guī)范歸約中，用()B來刻畫可歸約串。

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)于解釋程序的描述正確的是旦.

(I)解釋程序的特點(diǎn)是處理程序時(shí)不產(chǎn)生目標(biāo)代碼

(2)解釋程序適用于COBOL和FORTRAN語(yǔ)言

(3)解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的

A.⑴⑵B.⑴C.⑴⑵⑶D.(2)(3)

39.解釋程序處理語(yǔ)言時(shí)，大多數(shù)采用的是支方法.

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)是：A

a.源程序b.目標(biāo)程序c.函數(shù)d.過程

e.機(jī)器指令代碼f.模塊g.連接程序h.程序庫(kù)

A.b、g、eB.b、c、eC.e、g、fD.e、c、f

41.由于受到具體機(jī)器主存容量的限制，編譯程序幾個(gè)不同階段的工伍往往被組合成，諸階

段的工作往往是進(jìn)行的.上面兩空格對(duì)應(yīng)的選項(xiàng)是：A

a.過程b.程序c.批量d.遍

e.順序f.并行g(shù).成批h.穿插

A.d和hB.d和eC.a和hD.a和e

42.編譯過程中，語(yǔ)法分析器的任務(wù)就是R.

(1)分析單詞是怎樣構(gòu)成的⑵分析單詞吊是如何構(gòu)成語(yǔ)句和說明的

(3)分析語(yǔ)句和說明是如何構(gòu)成程序的(4)分析程序的結(jié)構(gòu)

A.⑵(3)B.⑵(3)(4)C.⑴⑵⑶D.⑴⑵(3)(4)

43.編譯程序必須完成的工作有A.

(1)詞法分析(2)語(yǔ)法分析(3)語(yǔ)義分析

(4)代碼生成(5)中間代碼生成(6)代碼優(yōu)化

A.⑴⑵(3)(4)B.⑴⑵(3)(4)⑸

C.⑴⑵⑶(4)⑸⑹D.⑴⑵⑶(4)(6)

44.按邏輯上劃分，編譯程序第二步工作是

A.語(yǔ)義分析B.詞法分析C.語(yǔ)法分析D.代碼優(yōu)化

45.已知語(yǔ)言L={xnyyTn>=l},則下述文法中，D_可以產(chǎn)生語(yǔ)言L。

A1.Z—>xZy|xAy|yB1.A—>xAy

2.A—*xAy|x2.A-x

CLZ—AyBDLZ-xAy

2.A—>xA|x2.A—>xAy|y

3.B->yB|y

46.喬姆斯基(Chomsky)把文法分為四種類型，即。型、1型、2型、3型。其中3型文

法是旦。

A.短語(yǔ)文法B.正則文法C.上下文有關(guān)文法D.上下文無(wú)關(guān)文法

48.設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S當(dāng)x(其中x￡V"),則稱x是文法

G的一個(gè)

A.候選式B.句型C.單詞D.產(chǎn)生式

49.若一個(gè)文法是遞歸的，則它所產(chǎn)生的語(yǔ)言的句子A。

A.是無(wú)窮多個(gè)B.是有窮多個(gè)C.是可枚舉的D.個(gè)數(shù)是常量

50.文法的二義性和語(yǔ)言的二義性是兩個(gè)區(qū)的概念。

A不同B相同C無(wú)法判斷D不存在

51.在語(yǔ)法分析處理中，F(xiàn)IRST集合、FOLLOW集合、SELECT集合均是旦。

A.非終結(jié)符集B.終結(jié)符集C.字母表D.狀態(tài)集

52.編譯程序中語(yǔ)法分析器接收以區(qū)為單位的輸入。

A.單詞B.表達(dá)式C.產(chǎn)生式D.句子

53.在LR分析法中，分析棧中存放的狀態(tài)是識(shí)別規(guī)范句型Q的DFA狀態(tài)。

A.句柄B.前綴C.活前綴D.LR(O)項(xiàng)目

三、是非題

（下列各題，你認(rèn)為正確的，請(qǐng)?jiān)陬}干的括號(hào)內(nèi)打錯(cuò)的打％）

I.計(jì)算機(jī)高級(jí)語(yǔ)言翻譯成低級(jí)語(yǔ)言只有解釋一種方式。（X）

2.在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。（X）

3.甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相

同。（X）

4.“用高級(jí)語(yǔ)言書寫的源程序都必須通過編譯，產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行”這種說法。

（X）

5.正則文法其產(chǎn)生式為Ala,A->Bb,A,BGVN,a、beVTo（V）

6.產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。（X）

7.解釋程序適用于COBOL和FORTRAN語(yǔ)言。（X）

8.正規(guī)文法產(chǎn)生的語(yǔ)言都可以用上下文無(wú)關(guān)文法來描述。（V）

9.如果一個(gè)文法存在某個(gè)句子對(duì)應(yīng)兩棵不同的語(yǔ)法樹，則稱這個(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è)1?和s分別是正規(guī)式，則有L（hs尸L（r）L（s）。（X）

15.確定的自動(dòng)機(jī)以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。（V）

16.詞法分析作為單獨(dú)的一遍來處理較好。（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⑴文法一定是無(wú)二義的。（V）

23.算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)。（X）

24.自底而上語(yǔ)法分析方法的主要問題是候選式的選擇。（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（l）分析法的名稱中，S的含義是簡(jiǎn)單的。（V）

30.綜合屬性是用于“自上而下”傳遞信息。（X）

31.一個(gè)算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對(duì)應(yīng)。（V）

32.LR分析法在自左至右掃描輸入串時(shí)就能發(fā)現(xiàn)錯(cuò)誤，但不能準(zhǔn)確地指出出錯(cuò)地點(diǎn)。（V）

33.規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（V）

34.LR分析技術(shù)無(wú)法適用二義文法。（X）

35.逆波蘭表示法表示表達(dá)式時(shí)無(wú)須使用括號(hào)。（V）

36.逆波蘭法表示的表達(dá)式亦稱后綴式。（V）

38.在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。（X）

39.設(shè)E為{a,b},則a,ba,{￡},中都是E上的正規(guī)式。（X）

40.對(duì)于上下文無(wú)關(guān)文法G[S],若S=aAB=。BY則A-Y一定是一條產(chǎn)生式規(guī)則,

其中。，B,Yf(VrVVO\〔X)

41.對(duì)于逆波蘭后綴式，無(wú)論從哪頭開始分析均可得到唯一正確的分解。(V)

42.LR(0)分析法是一種規(guī)范歸約法。(V)

43.算符優(yōu)先分析法只能用來分析算符優(yōu)先文法。(V)

44.解釋程序和編譯程序一樣，生成目標(biāo)代碼。(X)

45.編譯程序生成的目標(biāo)代碼只能是機(jī)器語(yǔ)言。(X)

46.等價(jià)文法是指兩個(gè)文法完全相同。(X)

47.對(duì)于字母表Z上的任一NFAH',必存在S上與NFAM'等價(jià)的并AMo(V)

48.每個(gè)文法都能改寫為L(zhǎng)L(1)文法。(X)

49.不存在正規(guī)文法能產(chǎn)生語(yǔ)言：L={aV|n>=l)(V)

四、簡(jiǎn)答題

1、什么是句子？什么是語(yǔ)言？

答：

設(shè)G是一個(gè)給定的文法，S是文法的開始符號(hào)，如果S=>*x(其中xWVt*),則稱x是

文法的一個(gè)句子。

設(shè)G[S]是給定文法，則由文法G所定義的語(yǔ)言L(G)可描述為L(zhǎng)(G)=[x|S=>*x,x￡VT*}

2、已知文法G[E]為：

E->T|E+T|E-T

T->F|T*F|T/F

F一(E)|i

①該文法的開始符號(hào)(識(shí)別符號(hào))是什么？

②請(qǐng)給出該文法的終結(jié)符號(hào)集合VT和非終結(jié)符號(hào)集合VNo

③找出句型T+T*F+i的所有短語(yǔ)、簡(jiǎn)單短語(yǔ)和句柄。

答：①該文法的開始符號(hào)(識(shí)別符號(hào))是E。

②該文法的終結(jié)符號(hào)集合VT={+、-、*、/、(、)、i}。

非終結(jié)符號(hào)集合VN={E、T、F}。

③句型T+T*F+I的句柄為第一個(gè)To

3、已知文法G[S]為：

S->dAB

A—>aA|a

B—B*

①G[S]產(chǎn)生的語(yǔ)言是什么？

②G[S]能否改寫為等價(jià)的正規(guī)文法？

答：①G[S]產(chǎn)生的語(yǔ)言是L(G[S])={daAnbAm|nel,m20}。

②G[S]能改寫為等價(jià)的正規(guī)文法，其改寫后的等價(jià)的

正規(guī)文法G[S']為：

S'fdA

A-*aA|aB|a

B-bB|b

5、證明下面文法G[N]是二義性文法。

G[N]：N