編譯原理小題答案解析

./《編譯原理》常見(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)包括表格處理和出錯(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è)G[S]是給定文法,則由文法G所定義的語(yǔ)言L<G>可描述為：L<G>＝{x│S=>*x,x∈VT*}。14.設(shè)G是一個(gè)給定的文法,S是文法的開(kāi)始符號(hào),如果Sx〔其中x∈V*,則稱(chēng)x是文法的一個(gè)句型。15.設(shè)G是一個(gè)給定的文法,S是文法的開(kāi)始符號(hào),如果Sx<其中x∈VT*>,則稱(chēng)x是文法的一個(gè)句子。16.掃描器的任務(wù)是從源程序中識(shí)別出一個(gè)個(gè)單詞符號(hào)。17.語(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)始符號(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ǔ)言的__語(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à)的中間表示形式可以有_逆波蘭__、四元式表示___與_三元式表示____等。51.自頂向下語(yǔ)法分析會(huì)遇到的主要問(wèn)題有左遞歸和回溯。52.已知文法G[E]：E→T|E+T;T→F|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．源程序命令被逐個(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>稱(chēng)為該句型的句柄。A．短語(yǔ)

B．簡(jiǎn)單短語(yǔ)

C．素短語(yǔ)

D．終結(jié)符號(hào)7．文法G[E]：

E→T∣E＋T

T→F∣T﹡F

F→a∣<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型文法又稱(chēng)為<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>是兩類(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)型,即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是一種典型的解釋型語(yǔ)言。A．BASICB．CC．FORTRAN

D．PASCAL21．與編譯系統(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ǔ)言的源程序后,到正式上機(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ī)式M1和M2等價(jià)是指<C>。A．M1和M2的狀態(tài)數(shù)相等 B．M1和M2的有向邊條數(shù)相等C．M1和M2所識(shí)別的語(yǔ)言集相等 D．M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等27．文法G：S→xSx|y所識(shí)別的語(yǔ)言是<C>。A．xyx

B．<xyx>*C．

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>。A．┐AB∨∧CD∨B．A┐B∨CD∨∧

C．AB∨┐CD∨∧

D．A┐B∨∧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)刻畫(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.<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ě)的程序產(chǎn)生后,可用連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是.上面三空格對(duì)應(yīng)的選項(xiàng)是：Aa.源程序

b.目標(biāo)程序

c.函數(shù)

d.過(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.<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)化45．已知語(yǔ)言L={xnyyn|n>=1},則下述文法中,D可以產(chǎn)生語(yǔ)言L。A1.Z→xZy|xAy|yB1.A→xAy2.A→xAy|x2.A→xC1.Z→AyBD1.Z→xAy2.A→xA|x2.A→xAy|y3.B→yB|y46．喬姆斯基〔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<其中x∈V*>,則稱(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ǔ)法分析處理中,FIRST集合、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ǔ)言只有解釋一種方式?！瞂2．在編譯中進(jìn)行語(yǔ)法檢查的目的是為了發(fā)現(xiàn)程序中所有錯(cuò)誤。〔X3．甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同。〔X4．"用高級(jí)語(yǔ)言書(shū)寫(xiě)的源程序都必須通過(guò)編譯,產(chǎn)生目標(biāo)代碼后才能投入運(yùn)行"這種說(shuō)法?！瞂5．正則文法其產(chǎn)生式為Aa,ABb,A,B∈VN,a、b∈VT?！睼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>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>文法?！瞂20．遞歸下降法允許任一非終結(jié)符是直接左遞歸的?！睼21．遞歸下降分析法是自頂向下分析方法。<V>22．一個(gè)LL<l>文法一定是無(wú)二義的。<V>23．算符優(yōu)先關(guān)系表不一定存在對(duì)應(yīng)的優(yōu)先函數(shù)?！瞂24．自底而上語(yǔ)法分析方法的主要問(wèn)題是候選式的選擇?！瞂25．LR分析方法是自頂向下語(yǔ)法分析方法。〔X26．簡(jiǎn)單優(yōu)先文法允許任意兩個(gè)產(chǎn)生式具有相同右部?！瞂27．若一個(gè)句型中出現(xiàn)了某產(chǎn)生式的右部,則此右部一定是該句型的句柄。〔X28．一個(gè)句型的句柄一定是文法某產(chǎn)生式的右部。〔V29．在SLR<1>分析法的名稱(chēng)中,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è)過(guò)程。<V>34．LR分析技術(shù)無(wú)法適用二義文法。<X>35．逆波蘭表示法表示表達(dá)式時(shí)無(wú)須使用括號(hào)。<V>36．逆波蘭法表示的表達(dá)式亦稱(chēng)后綴式。<V>38．在程序中標(biāo)識(shí)符的出現(xiàn)僅為使用性的。〔X設(shè)∑為{a,b},則a,ba,{∑},Φ都是∑上的正規(guī)式。〔X對(duì)于上下文無(wú)關(guān)文法G[S],若SαABαβγ則A→γ一定是一條產(chǎn)生式規(guī)則,其中α,β,γ∈〔VT∨VN* 。 〔X對(duì)于逆波蘭后綴式,無(wú)論從哪頭開(kāi)始分析均可得到唯一正確的分解?！睼LR〔0分析法是一種規(guī)范歸約法。 〔V算符優(yōu)先分析法只能用來(lái)分析算符優(yōu)先文法?！睼解釋程序和編譯程序一樣,生成目標(biāo)代碼?！瞂編譯程序生成的目標(biāo)代碼只能是機(jī)器語(yǔ)言?！瞂等價(jià)文法是指兩個(gè)文法完全相同?！瞂對(duì)于字母表Σ上的任一NFAM',必存在Σ上與NFAM'等價(jià)的DFAM?！睼每個(gè)文法都能改寫(xiě)為L(zhǎng)L<1>文法?！瞂不存在正規(guī)文法能產(chǎn)生語(yǔ)言：L={anbn|n>=1}〔V四、簡(jiǎn)答題什么是句子？什么是語(yǔ)言?答：設(shè)G是一個(gè)給定的文法,S是文法的開(kāi)始符號(hào),如果S=>*x〔其中x∈Vt*,則稱(chēng)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-TT→F|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、已知文法G[S]為：S→dABA→aA|aB→Bb|ε①G[S]產(chǎn)生的語(yǔ)言是什么？②G[S]能否改寫(xiě)為等價(jià)的正規(guī)文法？答：①

G[S]產(chǎn)生的語(yǔ)言是L<G[S]>={da^nb^m│n≥1,m≥0}。②

G[S]能改寫(xiě)為等價(jià)的正規(guī)文法,其改寫(xiě)后的等價(jià)的正規(guī)文法G[Sˊ]為：Sˊ→dAA

→aA|aB|aB

→bB|b5、證明下面文法G[N]是二義性文法。G[N]：N→SE∣ES→SD∣DE→0∣2∣10D