編譯原理習(xí)題集與答案解析整理后

1、第一章1、將編譯程序分成若干個“遍”是為了 。a .提高程序的執(zhí)行效率b 使程序的結(jié)構(gòu)更加清晰c .利用有限的機器內(nèi)存并提高機器的執(zhí)行效率d 利用有限的機器內(nèi)存但降低了機器的執(zhí)行效率2、 構(gòu)造編譯程序應(yīng)掌握。a 源程序c .編譯方法3、 變量應(yīng)當(dāng)。a .持有左值c .既持有左值又持有右值4、編譯程序絕大多數(shù)時間花在a .出錯處理c 目標(biāo)代碼生成5、 不可能是目標(biāo)代碼。a 匯編指令代碼c 絕對指令代碼b. 目標(biāo)語言d.以上三項都是b. 持有右值d.既不持有左值也不持有右值上。b.詞法分析d.管理表格b.可重定位指令代碼d.中間代碼6、使用可以定義一個程序的意義。a.語義規(guī)則b.語法規(guī)則c.產(chǎn)生規(guī)

2、則d.詞法規(guī)則7、 詞法分析器的輸入是 。a.單詞符號串b.源程序c.語法單位d.目標(biāo)程序8、 中間代碼生成時所遵循的是-。a .語法規(guī)則c .語義規(guī)則b.詞法規(guī)則d.等價變換規(guī)則9、 編譯程序是對。a 匯編程序的翻譯c .機器語言的執(zhí)行10、語法分析應(yīng)遵循a 語義規(guī)則c 構(gòu)詞規(guī)則b.高級語言程序的解釋執(zhí)行d.高級語言的翻譯b.語法規(guī)則d.等價變換規(guī)則則，并且語義規(guī)則可以定義一個程序的意義。因此選a。二、多項選擇題1、 編譯程序各階段的工作都涉及到 。a .語法分析b.表格管理c.出錯處理d .語義分析e .詞法分析2、編譯程序工作時，通常有 階段。a .詞法分析b.語法分析c.中間代碼生成d

3、 .語義檢查e .目標(biāo)代碼生成三、填空題1 、解釋程序和編譯程序的區(qū)別在于 。2、 編譯過程通?？煞譃?5個階段，分別是、語法分析、代碼優(yōu)化和目標(biāo)代碼生成。3、 編譯程序工作過程中，第一段輸入是 ，最后階段的輸出為 程序。4、 編譯程序是指將 程序翻譯成 程序的程序。單選解答1、 將編譯程序分成若干個“遍”是為了使編譯程序的結(jié)構(gòu)更加清晰，故選b。2、 構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語言及編譯方法等三方面的知識，故選d。3、 對編譯而言，變量既持有左值又持有右值，故選c。4、 編譯程序打交道最多的就是各種表格，因此選do5、 目標(biāo)代碼包括匯編指令代碼、可重定位指令代碼和絕對指令代碼3種，因此不是

4、目標(biāo)代碼 的只能選do6、詞法分析遵循的是構(gòu)詞規(guī)則，語法分析遵循的是語法規(guī)則，中間代碼生成遵循的是語義規(guī)7、b 8c 9、 d 10 、 c多選解答1. b、c 2. a 、b、c、e填空解答4、源程序 目是否生成目標(biāo)程序2、詞法分析中間代碼生成3、源程序 目標(biāo)代碼生成標(biāo)語言第二章、單項選擇題1、文法 G StxSx|y所識別的語言是a. xyxb. (xyx)*c. xn n,yx (n > 0)d. x*yx*2、文法G描述的語言L(G)是指a. L(G)= a |S? a c. L(G)= a |S?* a ,a Vt*a (VtU Vn*)b. L(G)= a |S ?d. L(

5、G)= a |S?a , a Vt*a , a (VtU Vn*)3、有限狀態(tài)自動機能識別a. 上下文無關(guān)文法b.上下文有關(guān)文法c.正規(guī)文法d.短語文法4、設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對a、b有以下關(guān)系成立a.若 f(a)>g(b)，則a>bb.若 f(a)<g(b)，貝U a<bc. ab都不一定成立d. ab 一定成立5、如果文法 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)的語法樹相同6、 由文法的開始符經(jīng)

6、0步或多步推導(dǎo)產(chǎn)生的文法符號序列是 a.短語 b.句柄c. 句型 d.句子7、文法 G Et E+T|TTt T*P|PPt (E)|I則句型P+T+i的句柄和最左素短語為 。+T 和 i b. P 和 P+T c. i 和 P+T+i 和 T8 、設(shè)文法為：St SA|A9、文法GStb| A (T)Tt T,S|SAt a|b則對句子aba,卜面是規(guī)范推導(dǎo)。a.sSAsaaAAAaAAabAabab.ssasaaAAAAAaAbaabac.ssasaaSAaSbaAbaabad.ssaSaSAaSbaAbaaba則 FIRSTVT(T)10、a. 011、a. b, A ,(b. b, A

7、 ,)產(chǎn)生正規(guī)語言的文法為b. 1型采用自上而下分析，必須a.消除左遞歸b.消除右遞歸c.b, A ,(, , c. 2型c.消除回溯d.b,12、在規(guī)范歸約中，用來刻畫可歸約串。a.直接短語b.句柄c.最左素短語A ,), , .3型.提取公共左因子.素短語13、有文法 G: Et E*T|TTt T+i|i句子1+2*8+6按該文法 G歸約，其值為a. 23 B. 42 c. 30d. 1714、規(guī)范歸約指a.最左推導(dǎo)的逆過程b.最右推導(dǎo)的逆過程c.規(guī)范推導(dǎo)d.最左歸約的逆過程二、多項選擇題1、下面哪些說法是錯誤的a.有向圖是一個狀態(tài)轉(zhuǎn)換圖b.狀態(tài)轉(zhuǎn)換圖是一個有向圖c.有向圖是一個DFA可

8、以用狀態(tài)轉(zhuǎn)換圖表示2、對無二義性文法來說，一棵語法樹往往代表了 a.多種推導(dǎo)過程b.多種最左推導(dǎo)過程c. 一種最左推導(dǎo)過程FHcS3、如果文法G存在一個句子，滿足下列條件 之一時，則稱該文法是二義文法。a. 該句子的最左推導(dǎo)與最右推導(dǎo)相同b. 該句子有兩個不同的最左推導(dǎo)c. 該句子有兩棵不同的最右推導(dǎo)d. 該句子有兩棵不同的語法樹e. 該句子的語法樹只有一個4、有一文法G: St ABA t aAb| e它不產(chǎn)生下面集合。a.d.a. ac. ae. anbmcndmn,m >0 n m m .n,b c d |n,m >0nbncndn|n >0自下而上的語法分析中,句型b

9、.b. ad. a應(yīng)從句子文法的開始符e.句柄6、對正規(guī)文法描述的語言,以下型文法型文法 c.上下文無關(guān)文法nbncmdm| n,m>0nbncmdnjn,m > 0開始分析。c.以單詞為單位的程序有能力描述它。d.右線性文法e.左線性文法三、填空題1、文法中的終結(jié)符和非終結(jié)符的交集是。詞法分析器交給語法分析器的文法符號一定，它一定只出現(xiàn)在產(chǎn)生式的部。2、最左推導(dǎo)是指每次都對句型中的非終結(jié)符進(jìn)行擴(kuò)展。3、在語法分析中，最常見的兩種方法一定是分析法，另一是分析法。4、 采用 語法分析時，必須消除文法的左遞歸。5、 樹代表推導(dǎo)過程， 樹代表歸約過程。6、 自下而上分析法采用 、歸約、錯

10、誤處理、 等四種操作。7、 Chomsky把文法分為 種類型，編譯器構(gòu)造中采用 和文法，它們分別產(chǎn)生和語言，并分別用 和自動機識別所產(chǎn)生的語言。四、判斷題1、文法StaS|bR| e描述的語言是 （a|bc）*2、在自下而上的語法分析中，語法樹與分析樹一定相同。（）3、二義文法不是上下文無關(guān)文法。（）4、語法分析時必須先消除文法中的左遞歸。（）5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個過程。（）6、一個文法所有句型的集合形成該文法所能接受的語言。（）五、簡答題1、句柄2、素短語3、語法樹4、歸約5、推導(dǎo) 六、問答題1、給出上下文無關(guān)文法的定義。2、文法 GS ：S t aSPQ|abQQi PQbPt

11、bbbQ tbccQtcc（1）它是Chomsky哪一型文法（ 2）它生成的語言是什么3、按指定類型，給出語言的文法。L=aibj |j > i > 1的上下文無關(guān)文法。4、有文法 G： St aAcB|BdAt AaB|cBtbScA|b（ 1）試求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄；（ 2）寫出句子 acabcbbdcc 的最左推導(dǎo)過程。5、對于文法 GS ：S t（ l） |aS|a L t l, S|S（1）畫出句型（S, （a）的語法樹。（2）寫出上述句型的所有短語、直接短語、句柄和素短語。6、考慮文法 GT ：TtT*F|FFt Ff P|PPt（

12、 T）|i證明T*P f( T*F)是該文法的一個句型，并指出直接短語和句柄。單選解答1 、選 c。2、選 a。3、選 c。4、雖然a與b沒有優(yōu)先關(guān)系，但構(gòu)造優(yōu)先函數(shù)后，a與b就一定存在優(yōu)先關(guān)系了。所以，由f(a)>g)(b) 或f(a)<g(b)并不能判定原來的a與b之間是否存在優(yōu)先關(guān)系：故選c。d，如果有兩個不同的是了左推導(dǎo)，則必然有二義性。故選a。6、選 c。7、 由圖2-8-1的語法樹和優(yōu)先關(guān)系可以看出應(yīng)選bo5、如果文法G無二義性，則最左推導(dǎo)是先生長右邊的枝葉：對于E/|E + F/匕IE + T PIT iP#< + >+< i >#8、 規(guī)范推

13、導(dǎo)是最左推導(dǎo)，故選d。9、由 TtT,和 ( 得 FIRSTVT(T)=(, , );由 Tt S 得 FIRSTVT(S)? FIRSTVT(T)，而 FIRSTVT(S)=b, A ,(;即10、dFIRSTVT(T)=b, A ,(,;因此選c。13 、b 14 、b11、c12、b多選解答1 、 e、 a、c 2、a、c、e 3、b、c、d 4 、a、c5 、b、c 6、a、b、c、d、e填空解答1、空集終結(jié)符右2 、最左3、自上而上自下而上4、自上而上5、語法分析6 、移進(jìn)接受7、4 2 型3型上下文無關(guān)語言正規(guī)語言下推自動機有限判斷解答1、對 2、錯 3、錯 4、錯 5、錯 6、錯

14、簡答解答1 、句柄：一個句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個終結(jié)符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面 4個條件的樹稱之為文法 GS的一棵語法樹。 每一終結(jié)均有一標(biāo)記，此標(biāo)記為VnU Vt中的一個符號； 樹的根結(jié)點以文法 GS的開始符S標(biāo)記； 若一結(jié)點至少有一個直接后繼，則此結(jié)點上的標(biāo)記為M中的一個符號； 若一個以A為標(biāo)記的結(jié)點有 K個直接后繼，且按從左至右的順序，這些結(jié)點的標(biāo)記分別 為X,X2,Xk,貝U AXi,X2,Xk,必然是 G的一個產(chǎn)生式。4、 歸約：我們稱仏丫直接歸約出a AB,僅當(dāng)Ay 是一個產(chǎn)生式，且a、B(VnU V

15、t)* 歸約過程就是從輸入串開始，反復(fù)用產(chǎn)生式右部的符號替換成產(chǎn)生式左部符號，直至文法開始符。5、 推導(dǎo)：我們稱a A B直接推出ayB, 即a A B ayB,僅當(dāng)丫是一個產(chǎn)生式，且a、(VnU Vt)*。如果a 1 a 2 a n,則我們稱這個序列是從a1至a 2的一個推導(dǎo)。若存在一個從a ia n的推導(dǎo)，則稱a 1可推導(dǎo)出a n。推導(dǎo)是歸約的逆過程。問答1解答一個上下文無關(guān)文法 G是一個四元式(Vt,Vn,S, P )，其中： Vt是一個非空有限集，它的每個元素稱為終結(jié)符號； Vn是一個非空有限集，它的每個元素稱為非終結(jié)符號，VtA Vn=； S是一個非終結(jié)符號，稱為開始符號； P是一個

16、產(chǎn)生式集合(有限)，每個產(chǎn)生式的形式是 Pa,其中，P Vn, a (VtU Vn)*。開始符號S至少必須在某個產(chǎn)生式的左部出現(xiàn)一次。2解答(1) 由于產(chǎn)生式左部存在終結(jié)符號，且所有產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式右部的符 號長度，所以文法 GS是Chomsky1型文法，即上下文有關(guān)文法。(2) 按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低(否則無法推出句子)，我們可以得到：S abQ abcS aSPQ aabQPQ aabPQQ aabbQQ aabbcQ aabbccS aSPQ aaSPQPQ aaabQPQPQ aaabPQQPQ aaabPQPQQ aaaPPQQQaaabbPqqq

17、aaabbQQQ aaabbbcQQ aaabbbccQ aaabbbccc于是得到文法 GS生成的語言L=anbncn|n >13【解答】(1)由L=ai bj |j > i > 1知，所求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有St aSb型產(chǎn)生式，以保證b的個數(shù)不少于a的個數(shù)；其次，還需有 St Sb或StbS型的產(chǎn)生式，用以保證 b的個數(shù)多 于a的個數(shù)；也即所求上下文無關(guān)文法GS為：GS : St aSb|Sb|b4【解答】(1 )分別畫出對應(yīng)兩句型的語法樹，如圖2-8-2所示(1)句型(S,(a)的語法樹如圖2-8-3 所示(2)由圖2-8-3可知:(L)L，SIS (

18、L )IS短語:S、a、(a)、S,(a)、 直接短語：a、S； 句柄：S； 素短語：素短語可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即;#<( <(<$) #因此素短語為a。6【解答】/1句柄：AaB Bda /I A zVW/ IA a B b S cAB d c圖2-8-2 語法樹(2) 句子acabcbbdcc的最左推導(dǎo)如下：S aAcB aAaBcB acaBcB acabcB acabcbScA acabcbBdcAacabcbbdcA acabcbbdcc5【解答】/1首先構(gòu)造T*P f( T*F)的語法樹如圖2-8-4所示。由圖2-8-4可知，T*Pf(

19、 T*F)是文法GT的一個句型。直接短語有兩個，即 P和T*F ;句柄為P。第三章單項選擇題1、 詞法分析所依據(jù)的是_。a. 語義規(guī)則b.構(gòu)詞規(guī)則2、 詞法分析器的輸出結(jié)果是_。a.單詞的種別編碼c.單詞的種別編碼和自身值3、 正規(guī)式M和M等價是指 。a. M i和M2的狀態(tài)數(shù)相等c. M i和M所識別的語言集相等c.語法規(guī)則d.等價變換規(guī)則b. 單詞在符號表中的位置d.單詞自身值b. M i和M的有向弧條數(shù)相等d. M i和M狀態(tài)數(shù)和有向弧條數(shù)相等4、狀態(tài)轉(zhuǎn)換圖(見圖 3-6-1 )接受的字集為1a.以0開頭的二進(jìn)制數(shù)組成的集合b. 以0結(jié)尾的二進(jìn)制數(shù)組成的集合c. 含奇數(shù)個0的二進(jìn)制數(shù)組成

20、的集合d. 含偶數(shù)個0的二進(jìn)制數(shù)組成的集合5、詞法分析器作為獨立的階段使整個編譯程序結(jié)構(gòu)更加簡潔、明確，因此，_。a.c.詞法分析器應(yīng)作為獨立的一遍b.詞法分析器作為子程序較好詞法分析器分解為多個過程，由語法分析器選擇使用d.詞法分析器并不作為一個獨立的階段多項選擇題1、 在詞法分析中，能識別出 。a.基本字b.四元式c.運算符d.逆波蘭式e.常數(shù)2、 令刀=a,b,則刀上所有以b開頭，后跟若干個ab的字的全體對應(yīng)的正規(guī)式為 。a. b(ab)*b. b(ab) +c.(ba)*bd. (ba) be. b(a|b)三、填空題1、 確定有限自動機 DFA是的一個特例。2、 若二個正規(guī)式所表示的

21、 相同，則認(rèn)為二者是等價的。3、 一個字集是正規(guī)的，當(dāng)且僅當(dāng)它可由 所。四、判斷題1、 一個有限狀態(tài)自動機中，有且僅有一個唯一終態(tài)。()2、 設(shè)r和s分別是正規(guī)式，則有 L( r|s )=L(r)|L(s)。()3、 自動機M和M'的狀態(tài)數(shù)不同，則二者必不等價。()4、 確定的自動機以及不確定的自動機都能正確地識別正規(guī)集。()5、 對任意一個右線性文法G,都存在一個NFA M滿足L(G)=L(M)。()6、 對任意一個右線性文法G,都存在一個 DFA M滿足L(G)=L(M)。()7、對任何正規(guī)表達(dá)式e,都存在一個NFAM,滿足L(G)=L(e)。()8、對任何正規(guī)表達(dá)式e，都存在一個

22、DFAM,滿足L(G)=L(e)。()五、基本題1、設(shè)M=( x,y, a,b, f,x,y)為一非確定的有限自動機，其中f定義如下：f (x,a )= x,yf (x,b ) = yf (y,a )=0f (y,b ) = x,y試構(gòu)造相應(yīng)的確定有限自動機M 。2、對給定正規(guī)式 b* (d|ad ) (b|ab ) +，構(gòu)造其 NFA M;單選解答1、b 2、c 3、c4、d 5、b多選解答 1、a、c、e 2、a、b、d填空解答1、NFA2、正規(guī)集3、DFA (NFA)所識別判斷解答1、2、3、錯4、5、6、7、8正確基本1解答：對照自動機的定義M=S,工,f,S 0,Z)，由f的定義可知

23、1：(x,a)、f(y,b)均為多值函數(shù)，所以是一非確定有限自動機，先畫出NFA M相應(yīng)的狀態(tài)圖，如圖3-6-2所示。.用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示。匚IIabI bbxx,yyy一x,yx,yx,yx,y將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。21考察1,2。由于1,2a=1,2b=2? 1,2，所以不再將其劃分了，也即整個劃分只有兩組0，1,2:令狀態(tài)1代表1,2所示化簡DFA M'。，即把原來到達(dá).2的弧都導(dǎo)向1，并刪除狀態(tài)2。最后，得到如圖3-6-6a,b2解答：首先用3-6-7所示。A+=aA改造正規(guī)式得：b (d|ad)(b|ab)(

24、b|ab) ;其次，構(gòu)造該正規(guī)式的NFAM如圖b*(d|ad)(b|ab)(b|23Yadab12££bbaa-a d仟g K Y”廠J£ 4£表3-6-4狀態(tài)轉(zhuǎn)換矩陣ab0211一2222即得到 M =(0,1,2,a,b,f,0,1,2)，其狀態(tài)轉(zhuǎn)換圖如圖3-6-5所示。將圖3-6-5的DFA M最小化。首先，將M'的狀態(tài)分成終態(tài)組1 , 2與非終態(tài)組0;其次,圖 3-6-7 的 NFA M第四章1、構(gòu)造下面文法的 LL( 1)分析表?！?TLTt int | realLt i d RRt , id R |£2、下面文法GS是否為L

25、L (1 )文法說明理由。S t A B | P Q xA t x y B t b cP t d P | eQ t a Q | e3、設(shè)有以下文法：GS：StaAbDe|dA tBSD|eB tSAc| cD| eD tSe| e(1) 求出該文法的每一個非終結(jié)符U的FOLLOW集。(2) 該文法是LL( 1)文法嗎(3) 構(gòu)造CS的LL( 1 )分析表。4、將文法GV改造成為LL(1)的。GV：VtN|NEEtV|V+ENti5、已知文法：GA:At aAa| &(1 )該文法是LL (1)文法嗎為什么(2) 若采用LL (1)方法進(jìn)行語法分析，如何得到該文法的LL (1)分析表(3

26、) 若輸入符號串“ aaaa”，請給出語法分析過程。1解答：LL (1)分析表見表4-3-1分析 雖然這個文法很簡單，我們還是從求開始符號集合和后繼符號集合開始。FOLLOW D =FOLLOV( L) =#FIRST ( D) =FIRST (T) =int, realFIRST ( L) =idFOLLOW T) =idFIRST ( R) = , , £ FOLLOW/ R) =#有了上面每個非終結(jié)符的FIRST集合，填分析表時要計算一個產(chǎn)生式右部a的FIRST (a )就不是件難事了。填表時唯一要小心的時，&是產(chǎn)生式FHs右部的一個開始符號，而 #在 FOLLO( R

27、)中，所 以FTs填在輸入符號#的欄目中。表4-3-1 LL (1)分析表非終結(jié)符輸入符號intrealid#Ddt tldt tlTTt intTt realLLt id RRRt ,id RRt&2解答： 該文法不是LL (1)文法，見下面分析中的說明。分析只有三個非終結(jié)符有兩個選擇。1、P的兩個右部d P和&的開始符號肯定不相交。2、Q的兩個右部a Q和&的開始符號肯定不相交。3、對S來說，由于 x FIRST(A B)，同時也有 x FIRST(P Q x)(因為P和Q都可能為空) 所以該文法不是 LL (1)文法。3解答： (1)求文法的每一個非終結(jié)符U的FO

28、LLOW的過程如下：因為： S是識別符號，且有 2 BSDSAc、Se,所以FOLLOW/ S)應(yīng)包含F(xiàn)IRST(D) U FIRST(Ac) U FIRST(e) U #=a,d U a,d,c,e U e U #=a,c,d,e# 又因為At BSD和D£,所以 FOLLOV中還包含 FOLLOW(A) 因為St aAbDe和Bt SAc,所以FOLLOW A) =FIRST (bDe)U FIRST ( c) =b,c綜合、得 FOLLO(S) =a,d,c,e,# U a,b,c,d,e,#因為 At BSD 所以 FOLLOW ( B) =FIRST (SD) =a,d因為

29、 St aAbDe | d、At BSD| e 和 Bt SAc | cD，所以FOLLOW D) =FIRST (e)U FOLLO( A)U FOLLOV/ B)=e U b,c U a,d=a,b,c,d,e(2) GS不是 LL ( 1)文法。因為產(chǎn)生式Bt SAc|cD| £中FIRST(SAc)n FOLLO( B) =a,d工?(3) 構(gòu)造GS的LL (1)分析表。按照LL (1)分析表的構(gòu)造算法構(gòu)造方法GS的LL (1)分析表如表4-3-2所示。表4-3-2 GS 的LL (1)分析表abcde#saAbDedABSDBSDBSDeBSac/ ecDSac/ eDSe

30、/ eeeSe/ ee4解答： 對文法GV提取公共左因子后得到文法:V : Vt NAAf |Ei VBBf |+ENR i求出文法G V中每一個非終結(jié)符號的FIRST集：FIRST(V)=iFIRST(A)=,£ FIRST(E)=iFIRST(B)=+,£ FIRST(N)=i求出文法G V中每一個非終結(jié)符號的FOLLOWI:FOLLOW(V)=# U FIRST(B) £ U FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST() £ U FOLLOW(B)= FIRST() £

31、U FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A) £ U FOLLOW(V)=,+,#可以看到，對文法 G V的產(chǎn)生式Ar£ |E，有FIRST(E) A FOLLOW(A)= n +,#=?對產(chǎn)生式Br£ |+e，有FIRST(+E) n FOLLOW(B)=+n =?而文法的其他產(chǎn)生式都只有一個不為&的右部，所以文法G V是LL(1)文法。5解答：(1)因為產(chǎn)生式 Ar aAa| £有空產(chǎn)生式右部，而FOLLOW(A)=# U FIRST(a)=a, #造成 FIRST(A) A FO

32、LLOW(A)=A, £ A a, #工?所以該文法不是 LL( 1 )文法。(2)若采用LL (1)方法進(jìn)行語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)(可以為0 )個a，所以得到文法G A :Ar aaA| £此時對產(chǎn)生式 Ar aaA| £, 有 FOLLOW(A)=# U FOLLOW(A)=#，因而FIRST(A) n FOLLOW(A)=a, £ n #= ?所以文法G' A是LL (1)文法，按LL (1)分析表構(gòu)造算法構(gòu)造該文法的LL (1)分析表如表4-3-3所示。表4-3-3文法G' A的LL(1)分析表A#AAt aa

33、AAt£(3)若采用LL(1)方法進(jìn)行語法分析，對符號串“aaaa”的分析過程如表 4-3-4所示。表4-3-4對符號串“ aaaa”的分析過程步驟分析棧輸入串產(chǎn)生式/動作1#Aa a a a #At aaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #At aaA5#A a aa a #匹配6#A aa#匹配7#A#At£8#接受第五章1. 設(shè)有文法GS為：St a|b|(A)A SdA|S5-7-1 ,并判斷GS是否為算符優(yōu)先文法。算符優(yōu)先關(guān)系表(1) 完成下列算符優(yōu)先關(guān)系表，見表表 5-7-1ab()d#a?b?(?)?d#?(2)

34、給出句型(SdSdS的短語、簡單短語、句柄、素短語和最左素短語。(3) 給出輸入串(adb) #的分析過程。解答：(1)先求文法 GS的FIRSTVT集和LASTVT集：由 Sta|b|(A)得：FIRSTVT(S)=a,b,();由 At Sd 得：FIRSTVT(A)=d;又由 At S 得：FIRSTVT(S) ? FIRSTVT(A),即 FIRSTVT(A)=d,a,b,(;由 St a|b|(A)得；LASTVT(S)=a,b,;由 A t dA 得：LASTVT(A)=d,又由 A t S 得：LASTVT(S) ? LASTVT(A),即 LASTVT(A)=d,a,b,)。構(gòu)

35、造優(yōu)先關(guān)系表方法如下： 對Ptab，或PtaQb，有a? b; 對 PtaR，而 b FIRSTVT(R)，有 a? b; 對 PtRb，而 a FIRSTVT(R)，有 a? b。由此得到： 由 St (A)得：(？); 由 St(A得：(? FIRSTVT(A)，即:(? d,( ? a ,( ? b,( ?(;由 AtdA得：d? FIRSTVT(A), 即：d? d,d ? a,d ? b,d ?(; 由 St A)得，LASTVT(A)?)，即：d? ),a ? ),b ? ),) ?);由 At Sd 得：LASTVT(S)? d，即：a ? d,b ? d,) ? d;此外，由#

36、S#得：#? # ；由#? FIRSTVT(S)得：#? a,# ? b,# ?(;脂由 LASTVT(S)? #得：d? #,a ? #,b ? #,) ? #。最后得到算符優(yōu)先關(guān)系表，見表5-7-2。表5-7-2算符優(yōu)先關(guān)系表ab()d#a?b?(?)?d?#?由表5-7-2為算符優(yōu)先文法。（2）為求出句型（可以看出，任何兩個終結(jié)符之間至少只滿足？、？、？三種優(yōu)先關(guān)系之一，故GS圖5-7-3 句型（SdSdS的語法樹SdSdS的短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹，如圖5-7-3所示。由圖5-7-3得到：短語：S, SdS, SdSdS（ SdSdS）簡單短語（即直接短語）：

37、S句柄（即最左直接短語）：S素短語：SdS,它同時也是該句型的最左素短語。（3）輸入串（adb） #的分析過程見表 5-7-4表5-7-4 輸入串（adb）#的分析過程符號棧輸入串說明#(adb)#移進(jìn)#（adb)#移進(jìn)#( adb)#用Sa歸約#( Sdb)#移進(jìn)#( Sdb)#移進(jìn)#( Sdb)#用Sb歸約#( SdS)#用At S歸約#( SdA)#用At SdA歸約# (A)#移進(jìn)# (A)#用Sf( A)歸約#S#分析成功第六章一、單項選擇題1、若a為終結(jié)符，則Aaa 3為項目a. 歸約b.移進(jìn)c.接受d.待約2、 若項目集Ik含有Aa，則在狀態(tài)k時，僅當(dāng)面臨的輸入符號a FOLLO

38、W(A時，才采取“ Afa ”動作的一定是。文法(0)文法 (1)文法 (1)文法3、 就文法的描述能力來說，有_。a. SLR( 1) ? LR( 0) b. LR (1) ? LR (0) c. SLR (1) ? LR ( 1) d.無二義文法？ LR ( 1)4、 在LR (0)的ACTION子表中，如果某一行中存在標(biāo)記“j 的欄，貝U 。a. 該行必定填滿rjb.該行未填滿rjc.其他行也有rj子表中也有rj5、 一個 指明了在分析過程中的某時刻所能看到產(chǎn)生式多大一部分。a.活前綴b.前綴c.項目d.項目集、多項選擇題1、一個LR分析器包括。a.一個總控程序b. 一個項目集c. 一個

39、活前綴d. 一張分析表e. 一個分析棧2、LR分析器核心部分是一張分析表，該表包括 等子表。(1)分析b.優(yōu)先關(guān)系3、每一項ACTIONS, a所規(guī)定的動作包括a.移進(jìn)b. 比較c. 接受d. 歸約e.報錯4、對LR分析表的構(gòu)造，有可能存在動作沖突。a.移進(jìn)b.歸約c.移進(jìn)/歸約d.移進(jìn)/移進(jìn)e.歸約/歸約d. LR (1) ?無二義文法e. SLR (1) ?無二義文法5、就文法的描述能力來說，有a. SLR (1) ? LR (1)b. LR ( 1) ? SLR( 1)c. LR ( 0) ? LR (1)6、對LR分析器來說，存在 _等分析表的構(gòu)造方法。(0)(1) ( 0)(1)7、

40、 自上而下的語法分析方法有 。a.算符優(yōu)先分析法(1)分析法(1)分析法(0)分析法(1)分析法三、填空題1、 對于一個文法，如果能夠構(gòu)造 _。使得它的 _均是唯一確定的，則稱該文法為LR文法。2、 字的前綴是指該字的 。3、 活前綴是指 的一個前綴，這種前綴不含 之后的任何符號。4、 在LR分析過程中，只要 的已掃描部分保持可歸約成一個 ，則掃描過的部分正確。5、 將識別 的NFA確定化，使其成為以 為狀態(tài)的DFA這個DFA就是建立 的基礎(chǔ)。6、 Aa稱為項目；對文法開始符 S'fa為項目；若a為終結(jié)符，則稱Aaa B為項目；若B為非終結(jié)符，則稱 Aaa 3為項目。7、LR ( 0)

41、分析法的名字中“ L”表示, “ R”表示, “ 0”表示。四、綜合題1、對于文法 GS : S t AS|bAt SA|a(1) 列出所有LR ( 0)項目(2) 列出構(gòu)成文法 LR ( 0)項目集規(guī)范族。單項解答：1 、At%稱為歸約項目，對文法開始符 S'的歸約項目，如S't%稱為接受項目，ATaa3 (a為終結(jié)符)稱為移進(jìn)項目。在此選b.2、 當(dāng)用產(chǎn)生式 ATa歸約時，LR ( 0 )無論面臨什么輸入符號都進(jìn)行歸約；SLR( 1)則僅當(dāng)面 臨的輸入符號a FOLLOW(A時進(jìn)行歸約；LR ( 1)則當(dāng)在把 a歸約為A的規(guī)范句型的前綴 3 Aa前 提下，當(dāng)a后跟終結(jié)符a時

42、，才進(jìn)行歸約；因此選 d。3、由于 LR (0) ? SLR (1) ? LR (1) ?無二義文法，故選 c。4、選 a。5、選 c。多選解答：1 、一個LR分析器包括一個總控程序和一張分析表，選a、d。2、選 c、e。3、選 a、c、d、e。4、 在LR分析表的構(gòu)造中有可能存在“移進(jìn)”/ “歸約”和“歸約” / “歸約”沖突；故選 c、e。5、選 a、b、c、d、e。6、選 a、b、c、e。7、選 a、 c、d、e。填空解答：1 、一張分析表 每個入口2、任意首部3、規(guī)范句型句柄4、輸入串活前綴5、活前綴項目集合 LR 分析算法6、歸約接受 移進(jìn) 待約7、自左至右分析采用最右推導(dǎo)的逆過程即

43、最左歸約 向右查看 0 個字符綜合解答：首先將文法G拓廣為GS':S't SSt AS|b3 SA|a(1)文法GS'的LR (0)項目是:1、s5、St AS *9、At s A2、S't S 6、St. b10、At SA-3、AS7、St b 11、At. a4、St A S8、At. SA12、At a 2、列出構(gòu)成文法 LR( 0)項目集規(guī)范族。用&-CLOSURE閉包)辦法構(gòu)造文法G'的 LR (0)項目集規(guī)范族如下:I 0:1、S't. sI 3 :9、At S AI 6: 12、 At a3、St as8、At. SA17

44、: 7、St b 8、At SA3、St. AS11 、a6、St. b6、St b11、Ar aI 1:2、S't S-I 4 :10、At SA-9、At S A4、St A S8、At SA3、St. as11、At. a6、St. b3、St. AS8、At. SA6、St. b11、Ar aI 2:4、St A SI 5 :5、St AS 3、St as9、At S A8 、SA11、a11 、a3、AS6、S» b注意：I1中的S't S和AtSA是由狀態(tài)Io中的1和3讀入一個S字符后得到的下一個項目；， 而丨4中的At SA和At A- S則是由I 3中

45、的9和3讀入一個A字符后得到的下一個項目；丨5中的 AS -和At S- A 則是由I 4中的4和8讀入一個S字符后得到的下一個項目。狀態(tài)全體構(gòu)成了文法 G的LR (0)規(guī)范族。第七章、單項選擇題1、中間代碼生成所依據(jù)的是 _c.語義規(guī)則d.等價變換規(guī)則a. 語法規(guī)則b.詞法規(guī)則2、 四元式之間的聯(lián)系是通過_實現(xiàn)的。a.指示器b.臨時變量c.符號表d.程序變量3、后綴式ab+cd+/可用表達(dá)式 來表示。+b/c+db.(a+b)/(c+d)+b/(c+d)+b+c/d4、 表達(dá)式鬥 AV B)A( CV D)的逆波蘭表示為 。a. n ABVA CDVb. A n BV CDVAc. AB V

46、n CDVAd. A n BVA CDV4+1皂一f5、 中間代碼的樹型表示A B C D 所對應(yīng)的表達(dá)式為。7、終結(jié)符具有屬性。a.傳遞b.繼承、多頂選擇題1、中間代碼主要有。a.四兀式b .二兀式+B+C+D +(B+C)+D6、四元式表示法的優(yōu)點為a.不便于優(yōu)化處理，但便于表的更動c.便于優(yōu)化處理，也便于表的更動c.(A+B)+C+Dd. (A+B)+(C+D)b. 不便于優(yōu)化處理，但節(jié)省存儲空間d.便于表的更動，也節(jié)省存儲空間c. 抽象d.綜合c 三元式d 后綴式e 間接三元式2、下面中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b+c的有a. ab+c+b. abc+c.+ c+d 八a

47、7e . a+b+c3、 在下面的 語法制導(dǎo)翻譯中，采用拉鏈 -回填技術(shù)。a.賦值語句b. goto語句c .條件語句d.循環(huán)語句4、 下列中間代碼形式有益于優(yōu)化處理。a.三元式 b.四元式c.間接三元式d.逆波蘭表示法e .樹形表示法5、 在編譯程序中安排中間代碼生成的目的是 。a.便于進(jìn)行存儲空間的組織b.利于目標(biāo)代碼的優(yōu)化c.利于編譯程序的移植d.利于目標(biāo)代碼的移植e.利于提高目標(biāo)代碼的質(zhì)量6、下面的中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b*c。題)*/+a.ab+c*b. abc*+c.a+b*c + c(d.a e7、三地址代碼語句具體實現(xiàn)通常有 表示方法。a.逆波蘭表示b .三元

48、式c.間接三元式d .樹形表示e .四元式三、填空題1、 中間代碼有 等形式，生成中間代碼主要是為了使。2、 語法制導(dǎo)翻譯既可以用來產(chǎn)生 代碼，也可以用來產(chǎn)生 指令，甚至可用來對輸入串進(jìn)行。3、 當(dāng)源程序中的標(biāo)號出現(xiàn)“先引用后定義”時，中間代碼的轉(zhuǎn)移地址須持時才能確定,因而要進(jìn)行。4、 文法符號的屬性有兩種，一種稱為 ，另一種稱為 。5、 后綴式abc-/所代表的表達(dá)式是 ，表達(dá)式(a-b)*c 可用后綴式 表示。6、 用一張 輔以的辦法來表示中間代碼，這種表示法稱為間接三元式。四、綜合題1、 給出下列表達(dá)式的逆波蘭表示(后綴式)： a*(-b+c) (A V B) A (C DA E)2、 寫出算術(shù)表達(dá)式：A+B*(C-D)+E/(C-D) f N的四元式序列；三元式序列；間接三元式序列 單選解答1 、選 c 。2、四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的，故選b。3、選 b。4、選 b。5、選 d。6、四元式表示法的優(yōu)點與間接三元式相同，故選c。7、選 d。多選解答1、選a、c、d、e。2、b、d的中間代碼不能正確表示a+b+c,而e不是中間代碼：故選 a、c。3、凡涉及到跳轉(zhuǎn)的語句都需要采用拉鏈回填技術(shù)