編譯原理小題答案解析

./《編譯原理》常見題型一、填空題1.編譯程序的工作過程一般可以劃分為詞法分析,語法分析,中間代碼生成,代碼優(yōu)化<可省>,目標(biāo)代碼生成等幾個基本階段。2.若源程序是用高級語言編寫的,目標(biāo)程序是機(jī)器語言程序或匯編程序,則其翻譯程序稱為編譯程序.3.編譯方式與解釋方式的根本區(qū)別在于是否生成目標(biāo)代碼.5.對編譯程序而言,輸入數(shù)據(jù)是源程序,輸出結(jié)果是目標(biāo)程序.7.若源程序是用高級語言編寫的,目標(biāo)程序是機(jī)器語言程序或匯編程序,則其翻譯程序稱為編譯程序。8.一個典型的編譯程序中,不僅包括詞法分析、語法分析、中間代碼生成、代碼優(yōu)化、目標(biāo)代碼生成等五個部分,還應(yīng)包括表格處理和出錯處理。其中,詞法分析器用于識別單詞。10.一個上下文無關(guān)文法所含四個組成部分是一組終結(jié)符號、一組非終結(jié)符號、一個開始符號、一組產(chǎn)生式。12.產(chǎn)生式是用于定義語法成分的一種書寫規(guī)則。13.設(shè)G[S]是給定文法,則由文法G所定義的語言L<G>可描述為：L<G>＝{x│S=>*x,x∈VT*}。14.設(shè)G是一個給定的文法,S是文法的開始符號,如果Sx〔其中x∈V*,則稱x是文法的一個句型。15.設(shè)G是一個給定的文法,S是文法的開始符號,如果Sx<其中x∈VT*>,則稱x是文法的一個句子。16.掃描器的任務(wù)是從源程序中識別出一個個單詞符號。17.語法分析最常用的兩類方法是自上而下和自下而上分析法。18.語法分析的任務(wù)是識別給定的終結(jié)符串是否為給定文法的句子。19.遞歸下降法不允許任一非終結(jié)符是直接左遞歸的。20.自頂向下的語法分析方法的關(guān)鍵是如何選擇候選式的問題。21.遞歸下降分析法是自頂向下分析方法。22.自頂向下的語法分析方法的基本思想是：從文法的開始符號開始,根據(jù)給定的輸入串并按照文法的產(chǎn)生式一步一步的向下進(jìn)行直接推導(dǎo),試圖推導(dǎo)出文法的句子,使之與給定的輸入串匹配。23.自底向上的語法分析方法的基本思想是：從給定的終結(jié)符串開始,根據(jù)文法的規(guī)則一步一步的向上進(jìn)行直接歸約,試圖歸約到文法的開始符號。24.自底向上的語法分析方法的基本思想是：從輸入串入手,利用文法的產(chǎn)生式一步一步地向上進(jìn)行直接歸約,力求歸約到文法的開始符號。26.在LR〔0分析法的名稱中,L的含義是自左向右的掃描輸入串,R的含義是最左歸約,0的含義是向貌似句柄的符號串后查看0個輸入符號。31.終結(jié)符只有綜合屬性,它們由詞法分析器提供。32.在使用高級語言編程時,首先可通過編譯程序發(fā)現(xiàn)源程序的全部A〔語法錯誤和B〔語義部分錯誤.34．一個句型中的最左簡單短語稱為該句型的__句柄___。36．從功能上說,程序語言的語句大體可分為_執(zhí)行性____語句和說明性____語句兩大類。37．語法分析是依據(jù)語言的__語法_規(guī)則進(jìn)行的,中間代碼產(chǎn)生是依據(jù)語言的_語義___規(guī)進(jìn)行的。38．語法分析器的輸入是_單詞符號____,其輸出是_語法單位____。40．逆波蘭式ab+c+d*e-所表達(dá)的表達(dá)式為__<a+b+c>*d-c__。41．計算機(jī)執(zhí)行用高級語言編寫的程序主要有兩種途徑：_解釋__和_編譯__。42．自上而下分析法采用___移進(jìn)_、歸約、錯誤處理、接受__等四種操作。43．一個LR分析器包括兩部分：一個總控程序和_一張分析表___。44．后綴式abc-/所代表的表達(dá)式是a/<b-c>____。46．語法分析基于_上下文無關(guān)___文法進(jìn)行,即識別的是該類文法的句子。語法分析的有效工具是_語法樹___。48．語義分析階段所生成的與源程序等價的中間表示形式可以有_逆波蘭__、四元式表示___與_三元式表示____等。51.自頂向下語法分析會遇到的主要問題有左遞歸和回溯。52.已知文法G[E]：E→T|E+T;T→F|T*F;F→<E>|i該文法的開始符號是,終結(jié)符號集合VT是,非終結(jié)符號結(jié)合VN是。二、單選題1．一個編譯程序中,不僅包含詞法分析,<A>,中間代碼生成,代碼優(yōu)化,目標(biāo)代碼生成等五個部分。A．語法分析B．文法分析C．語言分析D．解釋分析2．語法分析器則可以發(fā)現(xiàn)源程序中的<D>。A．語義錯誤

B．語法和語義錯誤 C．錯誤并校正

D．語法錯誤3．解釋程序處理語言時,大多數(shù)采用的是<B>B方法。A．源程序命令被逐個直接解釋執(zhí)行B．先將源程序轉(zhuǎn)化為中間代碼,再解釋執(zhí)行C．先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,再執(zhí)行D．以上方法都可以4．編譯程序是一種<B>。A．匯編程序B．翻譯程序 C．解釋程序

D．目標(biāo)程序5．通常一個編譯程序中,不僅包含詞法分析,語法分析,中間代碼生成,代碼優(yōu)化,目標(biāo)代碼生成等五個部分,還應(yīng)包括<C>。A．模擬執(zhí)行器

B．解釋器

C．表格處理和出錯處理

D．符號執(zhí)行器6．一個句型中的最左<B>稱為該句型的句柄。A．短語

B．簡單短語

C．素短語

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

E→T∣E＋T

T→F∣T﹡F

F→a∣<E>該文法句型E＋F﹡<E＋T>的簡單短語是下列符號串中的<B>。①〔E＋T

②E＋T

③F

④F﹡<E＋T>A．①和③B．②和③C．③和④D．③8．詞法分析器用于識別<C>。A．句子

B．句型

C．單詞

D．產(chǎn)生式9．在自底向上的語法分析方法中,分析的關(guān)鍵是<D>。A．尋找句柄

B．尋找句型

C．消除遞歸

D．選擇候選式10．文法G產(chǎn)生的<D>的全體是該文法描述的語言。A．句型B．終結(jié)符集C．非終結(jié)符集D．句子11．若文法G定義的語言是無限集,則文法必然是<A>。A．遞歸的

B．前后文無關(guān)的 C．二義性的D．無二義性的12．四種形式語言文法中,1型文法又稱為<C>C文法。A．短語結(jié)構(gòu)文法

B．前后文無關(guān)文法C．前后文有關(guān)文法

D．正規(guī)文法13．一個文法所描述的語言是<A>。A．唯一的

B．不唯一的 C．可能唯一,好可能不唯一

D．都不對14．<B>和代碼優(yōu)化部分不是每個編譯程序都必需的。A．語法分析

B．中間代碼生成 C．詞法分析

D．目標(biāo)代碼生成15．<B>是兩類程序語言處理程序。A．高級語言程序和低級語言程序 B．解釋程序和編譯程序C．編譯程序和操作系統(tǒng) D．系統(tǒng)程序和應(yīng)用程序16.一個上下文無關(guān)文法G包括四個組成部分,它們是：一組非終結(jié)符號,一組終結(jié)符號,一個開始符號,以及一組<D>。A．句子B．句型 C．單詞D．產(chǎn)生式17．文法分為四種類型,即0型、1型、2型、3型。其中2型文法是<D>。A．短語文法

B．正則文法

C．上下文有關(guān)文法D．上下文無關(guān)文法18．文法G所描述的語言是<C>的集合。A．文法G的字母表V中所有符號組成的符號串B．文法G的字母表V的閉包V*中的所有符號串C．由文法的開始符號推出的所有終結(jié)符串D．由文法的開始符號推出的所有符號串19．文法分為四種類型,即0型、1型、2型、3型。其中0型文法是<A>。A．短語文法

B．正則文法

C．上下文有關(guān)文法D．上下文無關(guān)文法20．<A是一種典型的解釋型語言。A．BASICB．CC．FORTRAN

D．PASCAL21．與編譯系統(tǒng)相比,解釋系統(tǒng)<D>。A．比較簡單,可移植性好,執(zhí)行速度快B．比較復(fù)雜,可移植性好,執(zhí)行速度快C．比較簡單,可移植性差,執(zhí)行速度慢D．比較簡單,可移植性好,執(zhí)行速度慢22．用高級語言編寫的程序經(jīng)編譯后產(chǎn)生的程序叫<B>。A．源程序

B．目標(biāo)程序

C．連接程序D．解釋程序23．編寫一個計算機(jī)高級語言的源程序后,到正式上機(jī)運行之前,一般要經(jīng)過<B>這幾步:<1>編輯

<2>編譯

<3>連接

<4>運行A．<1><2><3><4>

B．<1><2><3>

C．<1><3>

D．<1><4>24．把匯編語言程序翻譯成機(jī)器可執(zhí)行的目標(biāo)程序的工作是由<B>完成的。A．編譯器

B．匯編器

C．解釋器

D．預(yù)處理器25．詞法分析器的輸出結(jié)果是<C>。A．單詞的種別編碼B．單詞在符號表中的位置C．單詞的種別編碼和自身值D．單詞自身值26．正規(guī)式M1和M2等價是指<C>。A．M1和M2的狀態(tài)數(shù)相等 B．M1和M2的有向邊條數(shù)相等C．M1和M2所識別的語言集相等 D．M1和M2狀態(tài)數(shù)和有向邊條數(shù)相等27．文法G：S→xSx|y所識別的語言是<C>。A．xyx

B．<xyx>*C．

D．x*yx*28．如果文法G是無二義的,則它的任何句子α<A>。A．最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹必定相同B．最左推導(dǎo)和最右推導(dǎo)對應(yīng)的語法樹可能不同C．最左推導(dǎo)和最右推導(dǎo)必定相同D．可能存在兩個不同的最左推導(dǎo),但它們對應(yīng)的語法樹相同29．構(gòu)造編譯程序應(yīng)掌握<D>。A．源程序

B．目標(biāo)語言 C．編譯方法

D．以上三項都是30．四元式之間的聯(lián)系是通過<B>實現(xiàn)的。A．指示器

B．臨時變量 C．符號表

D．程序變量31．表達(dá)式<┐A∨B>∧<C∨D>的逆波蘭表示為<B>。A．┐AB∨∧CD∨B．A┐B∨CD∨∧

C．AB∨┐CD∨∧

D．A┐B∨∧CD∨33．編譯程序是對<D>。A．匯編程序的翻譯

B．高級語言程序的解釋執(zhí)行C．機(jī)器語言的執(zhí)行D．高級語言的翻譯34．采用自上而下分析,必須<C>。A．消除左遞歸

B．消除右遞歸 C．消除回溯

D．提取公共左因子35．在規(guī)范歸約中,用<>B來刻畫可歸約串。A．直接短語B．句柄 C．最左素短語

D．素短語36．間接三元式表示法的優(yōu)點為<A>。A．采用間接碼表,便于優(yōu)化處理 B．節(jié)省存儲空間,不便于表的修改C．便于優(yōu)化處理,節(jié)省存儲空間 D．節(jié)省存儲空間,不便于優(yōu)化處理37．在目標(biāo)代碼生成階段,符號表用<D>。A．目標(biāo)代碼生成B．語義檢查 C．語法檢查D．地址分配38．下面關(guān)于解釋程序的描述正確的是B.<1>解釋程序的特點是處理程序時不產(chǎn)生目標(biāo)代碼<2>解釋程序適用于COBOL和FORTRAN語言<3>解釋程序是為打開編譯程序技術(shù)的僵局而開發(fā)的A.<1><2>

B.<1>

C.<1><2><3>

D.<2><3>39.解釋程序處理語言時,大多數(shù)采用的是B方法.A.源程序命令被逐個直接解釋執(zhí)行B.先將源程序轉(zhuǎn)化為中間代碼,再解釋執(zhí)行C.先將源程序解釋轉(zhuǎn)化為目標(biāo)程序,在執(zhí)行D.以上方法都可以40.用不同語言編寫的程序產(chǎn)生后,可用連接在一起生成機(jī)器可執(zhí)行的程序.在機(jī)器中真正執(zhí)行的是.上面三空格對應(yīng)的選項是：Aa.源程序

b.目標(biāo)程序

c.函數(shù)

d.過程e.機(jī)器指令代碼

f.模塊

g.連接程序

h.程序庫A.b、g、eB.b、c、eC.e、g、fD.e、c、f41.由于受到具體機(jī)器主存容量的限制,編譯程序幾個不同階段的工作往往被組合成,諸階段的工作往往是進(jìn)行的.上面兩空格對應(yīng)的選項是：Aa.過程

b.程序

c.批量

d.遍e.順序f.并行g(shù).成批h.穿插A.d和hB.d和eC.a和hD.a和e42.編譯過程中,語法分析器的任務(wù)就是B.<1>分析單詞是怎樣構(gòu)成的

<2>

分析單詞串是如何構(gòu)成語句和說明的<3>分析語句和說明是如何構(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>語法分析

<3>語義分析<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.語義分析B.詞法分析C.語法分析D.代碼優(yōu)化45．已知語言L={xnyyn|n>=1},則下述文法中,D可以產(chǎn)生語言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把文法分為四種類型,即0型、1型、2型、3型。其中3型文法是B。A.短語文法B.正則文法C.上下文有關(guān)文法D.上下文無關(guān)文法48．設(shè)G是一個給定的文法,S是文法的開始符號,如果Sx<其中x∈V*>,則稱x是文法G的一個B。A.候選式B.句型C.單詞D.產(chǎn)生式49．若一個文法是遞歸的,則它所產(chǎn)生的語言的句子A。A.是無窮多個B.是有窮多個C.是可枚舉的D.個數(shù)是常量50．文法的二義性和語言的二義性是兩個A的概念。A不同B相同C無法判斷D不存在51.在語法分析處理中,FIRST集合、FOLLOW集合、SELECT集合均是B。A.非終結(jié)符集B.終結(jié)符集C.字母表D.狀態(tài)集52.編譯程序中語法分析器接收以A為單位的輸入。A.單詞B.表達(dá)式C.產(chǎn)生式D.句子53.在LR分析法中,分析棧中存放的狀態(tài)是識別規(guī)范句型C的DFA狀態(tài)。A.句柄B.前綴C.活前綴D.LR<0>項目三、是非題<下列各題,你認(rèn)為正確的,請在題干的括號內(nèi)打"√",錯的打"×"。>1．計算機(jī)高級語言翻譯成低級語言只有解釋一種方式?！瞂2．在編譯中進(jìn)行語法檢查的目的是為了發(fā)現(xiàn)程序中所有錯誤?！瞂3．甲機(jī)上的某編譯程序在乙機(jī)上能直接使用的必要條件是甲機(jī)和乙機(jī)的操作系統(tǒng)功能完全相同?！瞂4．"用高級語言書寫的源程序都必須通過編譯,產(chǎn)生目標(biāo)代碼后才能投入運行"這種說法。〔X5．正則文法其產(chǎn)生式為Aa,ABb,A,B∈VN,a、b∈VT。〔V6．產(chǎn)生式是用于定義詞法成分的一種書寫規(guī)則。<X>7．解釋程序適用于COBOL和FORTRAN語言。<X>8．正規(guī)文法產(chǎn)生的語言都可以用上下文無關(guān)文法來描述。<V>9．如果一個文法存在某個句子對應(yīng)兩棵不同的語法樹,則稱這個文法是二義的。<V>10．編譯程序是對高級語言程序的解釋執(zhí)行。<X>11．一個有限狀態(tài)自動機(jī)中,有且僅有一個唯一的終態(tài)。<X>12．語法分析時必須先消除文法中的左遞歸。<X>13．兩個正規(guī)集相等的必要條件是他們對應(yīng)的正規(guī)式等價。<V>14．設(shè)r和s分別是正規(guī)式,則有L<r|s>=L<r>L<s>。<X>15．確定的自動機(jī)以及不確定的自動機(jī)都能正確地識別正規(guī)集。<V>16．詞法分析作為單獨的一遍來處理較好。<X>17．構(gòu)造LR分析器的任務(wù)就是產(chǎn)生LR分析表。<V>18．編譯程序與具體的機(jī)器有關(guān),與具體的語言無關(guān)。<X>19．每個文法都能改寫為LL<1>文法?！瞂20．遞歸下降法允許任一非終結(jié)符是直接左遞歸的?！睼21．遞歸下降分析法是自頂向下分析方法。<V>22．一個LL<l>文法一定是無二義的。<V>23．算符優(yōu)先關(guān)系表不一定存在對應(yīng)的優(yōu)先函數(shù)?！瞂24．自底而上語法分析方法的主要問題是候選式的選擇?！瞂25．LR分析方法是自頂向下語法分析方法。〔X26．簡單優(yōu)先文法允許任意兩個產(chǎn)生式具有相同右部?！瞂27．若一個句型中出現(xiàn)了某產(chǎn)生式的右部,則此右部一定是該句型的句柄。〔X28．一個句型的句柄一定是文法某產(chǎn)生式的右部。〔V29．在SLR<1>分析法的名稱中,S的含義是簡單的。<V>30．綜合屬性是用于"自上而下"傳遞信息。<X>31．一個算符優(yōu)先文法可能不存在算符優(yōu)先函數(shù)與之對應(yīng)。<V>32．LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)錯誤,但不能準(zhǔn)確地指出出錯地點。<V>33．規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。<V>34．LR分析技術(shù)無法適用二義文法。<X>35．逆波蘭表示法表示表達(dá)式時無須使用括號。<V>36．逆波蘭法表示的表達(dá)式亦稱后綴式。<V>38．在程序中標(biāo)識符的出現(xiàn)僅為使用性的。〔X設(shè)∑為{a,b},則a,ba,{∑},Φ都是∑上的正規(guī)式?！瞂對于上下文無關(guān)文法G[S],若SαABαβγ則A→γ一定是一條產(chǎn)生式規(guī)則,其中α,β,γ∈〔VT∨VN* 。 〔X對于逆波蘭后綴式,無論從哪頭開始分析均可得到唯一正確的分解?！睼LR〔0分析法是一種規(guī)范歸約法。 〔V算符優(yōu)先分析法只能用來分析算符優(yōu)先文法?！睼解釋程序和編譯程序一樣,生成目標(biāo)代碼?！瞂編譯程序生成的目標(biāo)代碼只能是機(jī)器語言?！瞂等價文法是指兩個文法完全相同?！瞂對于字母表Σ上的任一NFAM',必存在Σ上與NFAM'等價的DFAM?！睼每個文法都能改寫為LL<1>文法?！瞂不存在正規(guī)文法能產(chǎn)生語言：L={anbn|n>=1}〔V四、簡答題什么是句子？什么是語言?答：設(shè)G是一個給定的文法,S是文法的開始符號,如果S=>*x〔其中x∈Vt*,則稱x是文法的一個句子。設(shè)G[S]是給定文法,則由文法G所定義的語言L<G>可描述為L<G>＝{x│S=>*x,x∈VT*}2、已知文法G[E]為：E→T|E+T|E-TT→F|T*F|T/FF→〔E|i①該文法的開始符號〔識別符號是什么？②請給出該文法的終結(jié)符號集合VT和非終結(jié)符號集合VN。③找出句型T+T*F+i的所有短語、簡單短語和句柄。答：①

該文法的開始符號〔識別符號是E。②該文法的終結(jié)符號集合VT={+、-、*、/、〔、、i}。非終結(jié)符號集合VN={E、T、F}。③句型T+T*F+I的句柄為第一個T。3、已知文法G[S]為：S→dABA→aA|aB→Bb|ε①G[S]產(chǎn)生的語言是什么？②G[S]能否改寫為等價的正規(guī)文法？答：①

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

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

→aA|aB|aB

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