2023年編譯原理期末復習題（含答案）

第編譯原理期末復習題（含答案）

第八節(jié)習題一、單項選擇題

1、將編譯程序分成若干個遍是為了。a．提高程序的執(zhí)行效率b．使程序的結構更加清晰

c．利用有限的機器內存并提高機器的執(zhí)行效率d．利用有限的機器內存但降低了機器的執(zhí)行效率2、構造編譯程序應掌握。a．源程序b．目標語言c．編譯方法d．以上三項都是3、變量應當。a．持有左值b．持有右值

c．既持有左值又持有右值d．既不持有左值也不持有右值4、編譯程序絕大多數(shù)時間花在上。a．出錯處理b．詞法分析c．目標代碼生成d．管理表格5、不可能是目標代碼。a．匯編指令代碼b．可重定位指令代碼c．絕對指令代碼d．中間代碼6、使用可以定義一個程序的意義。a．語義規(guī)則b．詞法規(guī)則c．產生規(guī)則d．詞法規(guī)則7、詞法分析器的輸入是。a．單詞符號串b．源程序c．語法單位d．目標程序8、中間代碼生成時所遵循的是-。a．語法規(guī)則b．詞法規(guī)則c．語義規(guī)則d．等價變換規(guī)則9、編譯程序是對。a．匯編程序的翻譯b．高級語言程序的解釋執(zhí)行c．機器語言的執(zhí)行d．高級語言的翻譯10、語法分析應遵循。a．語義規(guī)則b．語法規(guī)則c．構詞規(guī)則d．等價變換規(guī)則解答

1、將編譯程序分成若干個遍是為了使編譯程序的結構更加清晰，故選b。2、構造編譯程序應掌握源程序、目標語言及編譯方法等三方面的知識，故選d。3、對編譯而言，變量既持有左值又持有右值，故選c。4、編譯程序打交道最多的就是各種表格，因此選d。

5、目標代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是目標代碼的只能選d。

6、詞法分析遵循的是構詞規(guī)則，語法分析遵循的是語法規(guī)則，中間代碼生成遵循的是語義規(guī)則，并且語義規(guī)則可以定義一個程序的意義。因此選a。7、b8、c9、d10、c二、多項選擇題

1、編譯程序各階段的工作都涉及到。a．語法分析b．表格管理c．出錯處理d．語義分析e．詞法分析

2、編譯程序工作時，通常有階段。a．詞法分析b．語法分析c．中間代碼生成d．語義檢查e．目標代碼生成解答

1．b、c2.a、b、c、e三、填空題

1、解釋程序和編譯程序的區(qū)別在于。

2、編譯過程通?？煞譃?個階段，分別是、語法分析、代碼優(yōu)化和目標代碼生成。3、編譯程序工作過程中，第一段輸入是，最后階段的輸出為程序。

4、編譯程序是指將程序翻譯成程序的程序。解答

是否生成目標程序2、詞法分析中間代碼生成3、源程序目標代碼生成4、源程序目

標語言

一、單項選擇題

1、文法G：Srarr;xSx|y所識別的語言是。

nna.xyxb.(xyx)xc.xyx(nge;0)d.xxyxx2、文法G描述的語言L(G)是指。

+alpha;,alpha;isin;Vx}xalpha;,alpha;isin;Vx}a.L(G)={alpha;|S?b.L(G)={alpha;|S?TTx+c.L(G)={alpha;|S?alpha;,alpha;isin;(VTcup;VNx)}d.L(G)={alpha;|S?alpha;,alpha;isin;(VTcup;VNx)}

3、有限狀態(tài)自動機能識別。a.上下文無關文法b.上下文有關文法

c.正規(guī)文法d.短語文法

4、設G為算符優(yōu)先文法，G的任意終結符對a、b有以下關系成立。a.若f(a)g(b)，則abb.若f(a)

c.a~b都不一定成立d.a~b一定成立

5、如果文法G是無二義的，則它的任何句子alpha;。a.最左推導和最右推導對應的語法樹必定相同

b.最左推導和最右推導對應的語法樹可能不同c.最左推導和最右推導必定相同

d.可能存在兩個不同的最左推導，但它們對應的語法樹相同

6、由文法的開始符經0步或多步推導產生的文法符號序列是。a.短語b.句柄c.句型d.句子7、文法G：Erarr;E+T|T

Trarr;TxP|PPrarr;(E)|I

則句型P+T+i的句柄和最左素短語為。a.P+T和ib.P和P+Tc.i和P+T+id.P和T8、設文法為：Srarr;SA|A

Ararr;a|b

則對句子aba，下面是規(guī)范推導。a.S?SA?SAA?AAA?aAA?abA?aba

b.S?SA?SAA?AAA?AAa?Aba?abac.S?SA?SAA?SAa?Sba?Aba?abad.S?SA?Sa?SAa?Sba?Aba?aba9、文法G：Srarr;b|and;(T)Trarr;T,S|S

則FIRSTVT(T)。a.{b,and;,(}b.{b,and;,)}

10、產生正規(guī)語言的文法為。

c.{b,and;,(,，}d.{b,and;,),，}

a.0型b.1型c.2型d.3型11、采用自上而下分析，必須。a.消除左遞歸b.消除右遞歸c.消除回溯d.提取公共左因子12、在規(guī)范歸約中，用來刻畫可歸約串。a.直接短語b.句柄c.最左素短語d.素短語13、有文法G：Erarr;ExT|T

Trarr;T+i|i

句子1+2x8+6按該文法G歸約，其值為。

a.23B.42c.30d.1714、規(guī)范歸約指。a.最左推導的逆過程b.最右推導的逆過程c.規(guī)范推導d.最左歸約的逆過程[解答]

1、選c。

2、選a。3、選c。4、雖然a與b沒有優(yōu)先關系，但構造優(yōu)先函數(shù)后，a與b就一定存在優(yōu)先關系了。所以，由f(a)g)(b)或f(a)

5、如果文法G無二義性，則最左推導是先生長右邊的枝葉：對于d，如果有兩個不同的是了左推導，則必然有二義性。故選a。

6、選c。

7、由圖2-8-1的語法樹和優(yōu)先關系可以看出應選b。

E

E+F

E+TP

Ti

P

#++i#圖2-8-1句型P+T+I的語法及優(yōu)先關系

8、規(guī)范推導是最左推導，故選d。

9、由Trarr;T,?和Trarr;(?得FIRSTVT(T))={(,，)}；

由Trarr;S得FIRSTVT(S)?FIRSTVT(T)，而FIRSTVT(S)={b,and;,(}；即FIRSTVT(T)={b,and;,(,，}；因此選c。10、d11、c12、b13、b14、b二、多項選擇題

1、下面哪些說法是錯誤的。a.有向圖是一個狀態(tài)轉換圖b.狀態(tài)轉換圖是一個有向圖

c.有向圖是一個DFAd.DFA可以用狀態(tài)轉換圖表示2、對無二義性文法來說，一棵語法樹往往代表了。

a.多種推導過程b.多種最左推導過程c.一種最左推導過程d.僅一種推導過程e.一種最左推導過程

3、如果文法G存在一個句子，滿足下列條件之一時，則稱該文法是二義文法。a.該句子的最左推導與最右推導相同

b.該句子有兩個不同的最左推導c.該句子有兩棵不同的最右推導d.該句子有兩棵不同的語法樹

e.該句子的語法樹只有一個4、有一文法G：Srarr;ABArarr;aAb|epsilon;Brarr;cBd|epsilon;它不產生下面集合。

a.{anbmcndm|n,mge;0}b.{anbncmdm|n,m0}c.{anbmcmdn|n,mge;0}d.{anbncmdm|n,mge;0}e.{anbncndn|nge;0}

5、自下而上的語法分析中，應從開始分析。a.句型b.句子c.以單詞為單位的程序d.文法的開始符e.句柄

6、對正規(guī)文法描述的語言，以下有能力描述它。

a.0型文法b.1型文法c.上下文無關文法d.右線性文法e.左線性文法

解答1、e、a、c2、a、c、e3、b、c、d4、a、c5、b、c6、a、b、c、d、e三、填空題

1、文法中的終結符和非終結符的交集是。詞法分析器交給語法分析器的文法符號一定是，它一定只出現(xiàn)在產生式的部。

2、最左推導是指每次都對句型中的非終結符進行擴展。

3、在語法分析中，最常見的兩種方法一定是分析法，另一是分析法。4、采用語法分析時，必須消除文法的左遞歸。5、樹代表推導過程，樹代表歸約過程。

6、自下而上分析法采用、歸約、錯誤處理、等四種操作。

7、Chomsky把文法分為種類型，編譯器構造中采用和文法，它們分別產生和語言，并分別用和自動機識別所產生的語言。解答1、空集終結符右2、最左

3、自上而上自下而上4、自上而上

5、語法分析6、移進接受

7、42型3型上下文無關語言正規(guī)語言下推自動機有限四、判斷題

1、文法Srarr;aS|bR|epsilon;描述的語言是(a|bc)x()Rrarr;cS

2、在自下而上的語法分析中，語法樹與分析樹一定相同。（）3、二義文法不是上下文無關文法。（）4、語法分析時必須先消除文法中的左遞歸。（）5、規(guī)范歸約和規(guī)范推導是互逆的兩個過程。（）6、一個文法所有句型的集合形成該文法所能接受的語言。（）解答1、對2、錯3、錯4、錯5、錯6、錯五、簡答題

1、句柄2、素短語3、語法樹4、歸約5、推導[解答]

1、句柄：一個句型的最左直接短語稱為該句型的句柄。

2、素短語：至少含有一個終結符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面4個條件的樹稱之為文法G[S]的一棵語法樹。①每一終結均有一標記，此標記為VNcup;VT中的一個符號；

②樹的根結點以文法G[S]的開始符S標記；

③若一結點至少有一個直接后繼，則此結點上的標記為VN中的一個符號；④若一個以A為標記的結點有K個直接后繼，且按從左至右的順序，這些結點的標記分別為x1,x2,?,xK，則Ararr;x1,x2,?,xK，必然是G的一個產生式。4、歸約：我們稱alpha;gamma;beta;直接歸約出alpha;Abeta;，僅當Ararr;gamma;是一個產生式，且alpha;、beta;isin;(VNcup;VT)x。歸約過程就是從輸入串開始，反復用產生式右部的符號替換成產生式左部符號，直至文法開始符。

5、推導：我們稱alpha;Abeta;直接推出alpha;gamma;beta;，即alpha;Abeta;?alpha;gamma;beta;，僅當Ararr;gamma;是一個產生式，且alpha;、beta;isin;(VNcup;VT)x。如果alpha;1?alpha;2???alpha;n，則我們稱這個序列是從alpha;1至alpha;2的一個推導。若存在一個從alpha;1alpha;n的推導，則稱alpha;1可推導出alpha;n。推導是歸約的逆過程。

六、問答題

1、給出上下文無關文法的定義。[解答]

一個上下文無關文法G是一個四元式（VT,VN,S,P），其中：●VT是一個非空有限集，它的每個元素稱為終結符號；

●VN是一個非空有限集，它的每個元素稱為非終結符號，VTcap;VN=Phi;；●S是一個非終結符號，稱為開始符號；●P是一個產生式集合（有限），每個產生式的形式是Prarr;alpha;，其中，Pisin;VN，alpha;isin;(VTcup;VN)x。開始符號S至少必須在某個產生式的左部出現(xiàn)一次。2、文法G[S]：

Srarr;aSPQ|abQQPrarr;PQbPrarr;bbbQrarr;bccQrarr;cc

（1）它是Chomsky哪一型文法？（2）它生成的語言是什么？[解答]（1）由于產生式左部存在終結符號，且所有產生式左部符號的長度均小于等于產生式右部的符號長度，所以文法G[S]是Chomsky1型文法，即上下文有關文法。

（2）按產生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低（否則無法推出句子），我們可以得到：S?abQ?abc

S?aSPQ?aabQPQ?aabPQQ?aabbQQ?aabbcQ?aabbcc

S?aSPQ?aaSPQPQ?aaabQPQPQ?aaabPQQPQ?aaabPQPQQ?aaaPPQQ