編譯原理習(xí)題及答案(整理后)

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

2、輸入是 。 a單詞符號(hào)串b源程序 c語(yǔ)法單位d目標(biāo)程序8、中間代碼生成時(shí)所遵循的是- 。 a語(yǔ)法規(guī)則b詞法規(guī)則 c語(yǔ)義規(guī)則d等價(jià)變換規(guī)則9、編譯程序是對(duì) 。 a匯編程序的翻譯b高級(jí)語(yǔ)言程序的解釋執(zhí)行 c機(jī)器語(yǔ)言的執(zhí)行d高級(jí)語(yǔ)言的翻譯10、語(yǔ)法分析應(yīng)遵循 。 a語(yǔ)義規(guī)則b語(yǔ)法規(guī)則 c構(gòu)詞規(guī)則d等價(jià)變換規(guī)則二、多項(xiàng)選擇題1、編譯程序各階段的工作都涉及到 。 a語(yǔ)法分析b表格管理c出錯(cuò)處理 d語(yǔ)義分析e詞法分析2、編譯程序工作時(shí)，通常有 階段。 a詞法分析b語(yǔ)法分析c中間代碼生成 d語(yǔ)義檢查e目標(biāo)代碼生成三、填空題 1、解釋程序和編譯程序的區(qū)別在于 。2、編譯過程通?？煞譃?個(gè)階段，分別是 、語(yǔ)法分

3、析 、代碼優(yōu)化和目標(biāo)代碼生成。3、編譯程序工作過程中，第一段輸入是 ，最后階段的輸出為 程序。4、編譯程序是指將 程序翻譯成 程序的程序。單選解答1、將編譯程序分成若干個(gè)“遍”是為了使編譯程序的結(jié)構(gòu)更加清晰，故選b。2、構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語(yǔ)言及編譯方法等三方面的知識(shí)，故選d。3、對(duì)編譯而言，變量既持有左值又持有右值，故選c。4、編譯程序打交道最多的就是各種表格，因此選d。5、目標(biāo)代碼包括匯編指令代碼、可重定位指令代碼和絕對(duì)指令代碼3種，因此不是目標(biāo)代碼的只能選d。6、詞法分析遵循的是構(gòu)詞規(guī)則，語(yǔ)法分析遵循的是語(yǔ)法規(guī)則，中間代碼生成遵循的是語(yǔ)義規(guī)則，并且語(yǔ)義規(guī)則可以定義一個(gè)程序的意義

4、。因此選a。 7、b 8、c 9、d 10、c多選解答1b、c 2. a、b、c、e填空解答 是否生成目標(biāo)程序 2、詞法分析 中間代碼生成 3、源程序目標(biāo)代碼生成4、源程序 目標(biāo)語(yǔ)言第二章一、單項(xiàng)選擇題1、文法G：SxSx|y所識(shí)別的語(yǔ)言是 。a. xyxb. (xyx)*c. xnyxn(n0)d. x*yx*2、文法G描述的語(yǔ)言L(G)是指 。a. L(G)=|S , VT*b. L(G)=|S, VT*c. L(G)=|S,(VTVN*)d. L(G)=|S, (VTVN*)3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別 。a. 上下文無(wú)關(guān)文法b. 上下文有關(guān)文法c.正規(guī)文法d. 短語(yǔ)文法4、設(shè)G為算符優(yōu)先文

5、法，G的任意終結(jié)符對(duì)a、b有以下關(guān)系成立 。a. 若f(a)g(b)，則abb.若f(a)g(b)，則a0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbncndn|n05、自下而上的語(yǔ)法分析中，應(yīng)從 開始分析。a. 句型b. 句子c. 以單詞為單位的程序d. 文法的開始符e. 句柄6、對(duì)正規(guī)文法描述的語(yǔ)言，以下 有能力描述它。a.0型文法b.1型文法 c.上下文無(wú)關(guān)文法 d.右線性文法 e.左線性文法 三、填空題1、文法中的終結(jié)符和非終結(jié)符的交集是 。詞法分析器交給語(yǔ)法分析器的文法符號(hào)一定是 ，它一定只出現(xiàn)在產(chǎn)生式的 部。2、最左推導(dǎo)是指每次都對(duì)句型中的 非終結(jié)符

6、進(jìn)行擴(kuò)展。3、在語(yǔ)法分析中，最常見的兩種方法一定是 分析法，另一是 分析法。4、采用 語(yǔ)法分析時(shí)，必須消除文法的左遞歸。5、 樹代表推導(dǎo)過程， 樹代表歸約過程。6、自下而上分析法采用 、歸約、錯(cuò)誤處理、 等四種操作。 7、Chomsky把文法分為 種類型，編譯器構(gòu)造中采用 和 文法，它們分別產(chǎn)生 和 語(yǔ)言，并分別用 和 自動(dòng)機(jī)識(shí)別所產(chǎn)生的語(yǔ)言。四、判斷題1、文法 SaS|bR|描述的語(yǔ)言是(a|bc)* ( ) RcS2、在自下而上的語(yǔ)法分析中，語(yǔ)法樹與分析樹一定相同。 （ ）3、二義文法不是上下文無(wú)關(guān)文法。 （ ）4、語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。（ ）5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩

7、個(gè)過程。（ ）6、一個(gè)文法所有句型的集合形成該文法所能接受的語(yǔ)言。（ ）五、簡(jiǎn)答題1、句柄2、素短語(yǔ)3、語(yǔ)法樹4、歸約5、推導(dǎo)六、問答題1、給出上下文無(wú)關(guān)文法的定義。2、文法GS： SaSPQ|abQ QPPQ bPbb bQbc cQcc（1）它是Chomsky哪一型文法？（2）它生成的語(yǔ)言是什么？3、按指定類型，給出語(yǔ)言的文法。L=aibj|ji1的上下文無(wú)關(guān)文法。4、有文法G：SaAcB|BdAAaB|cBbScA|b（1）試求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）寫出句子acabcbbdcc的最左推導(dǎo)過程。5、對(duì)于文法GS： S（L）|aS|a LL, S|S（1）畫

8、出句型（S,（a）的語(yǔ)法樹。（2）寫出上述句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短語(yǔ)。6、考慮文法GT：TT*F|FFFP|PP（T）|i證明T*P（T*F）是該文法的一個(gè)句型，并指出直接短語(yǔ)和句柄。單選解答 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)并不能判定原來(lái)的a與b之間是否存在優(yōu)先關(guān)系：故選c。EE + FE + T PT iP #+#圖2-8-1 句型P+T+I的語(yǔ)法及優(yōu)先關(guān)系5、如果文法G無(wú)二義性，則最左推導(dǎo)是先生長(zhǎng)右邊的枝葉：對(duì)于d，如果有兩個(gè)不同的是了左推導(dǎo)，則必然有二義性。故

9、選a。6、選c。7、由圖2-8-1的語(yǔ)法樹和優(yōu)先關(guān)系可以看出應(yīng)選b。8、規(guī)范推導(dǎo)是最左推導(dǎo)，故選d。9、由TT,和T( 得FIRSTVT(T)=(,，)； 由TS得FIRSTVT(S)FIRSTVT(T)，而FIRSTVT(S)=b,(；即 FIRSTVT(T)=b,(,，； 因此選c。 10、d 11、c 12、b 13、b 14、b多選解答 1、e、a、c 2、a、c、e 3、b、c、d 4、a、c 5、b、c 6、a、b、c、d、e填空解答 1、空集 終結(jié)符 右 2、最左 3、自上而上 自下而上 4、自上而上 5、語(yǔ)法 分析 6、移進(jìn) 接受 7、4 2 型 3型 上下文無(wú)關(guān)語(yǔ)言 正規(guī)語(yǔ)言

10、 下推自動(dòng)機(jī) 有限判斷解答 1、對(duì) 2、錯(cuò) 3、錯(cuò) 4、錯(cuò) 5、錯(cuò) 6、錯(cuò) 簡(jiǎn)答解答 1、句柄：一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。2、素短語(yǔ)：至少含有一個(gè)終結(jié)符的素短語(yǔ)，并且除它自身之外不再含任何更小的素短語(yǔ)。3、語(yǔ)法樹：滿足下面4個(gè)條件的樹稱之為文法GS的一棵語(yǔ)法樹。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VNVT中的一個(gè)符號(hào)；樹的根結(jié)點(diǎn)以文法GS的開始符S標(biāo)記；若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為VN中的一個(gè)符號(hào)；若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有K個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為X1,X2,XK，則AX1,X2,XK，必然是G的一個(gè)產(chǎn)生式。4、歸約：我們稱直接歸約出A，僅當(dāng)

11、A 是一個(gè)產(chǎn)生式，且、(VNVT)*。歸約過程就是從輸入串開始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開始符。5、推導(dǎo)：我們稱A直接推出，即A，僅當(dāng)A 是一個(gè)產(chǎn)生式，且、(VNVT)*。如果12n，則我們稱這個(gè)序列是從1至2的一個(gè)推導(dǎo)。若存在一個(gè)從1n的推導(dǎo)，則稱1可推導(dǎo)出n。推導(dǎo)是歸約的逆過程。 問答1解答一個(gè)上下文無(wú)關(guān)文法G是一個(gè)四元式（VT,VN,S, P），其中：VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)；VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VTVN=；S是一個(gè)非終結(jié)符號(hào)，稱為開始符號(hào)；P是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是P，其中，PVN，(V

12、TVN)*。開始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。 2解答 （1）由于產(chǎn)生式左部存在終結(jié)符號(hào)，且所有產(chǎn)生式左部符號(hào)的長(zhǎng)度均小于等于產(chǎn)生式右部的符號(hào)長(zhǎng)度，所以文法GS是Chomsky1型文法，即上下文有關(guān)文法。（2）按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低（否則無(wú)法推出句子），我們可以得到： SabQabc SaSPQaabQPQaabPQQaabbQQaabbcQaabbcc SaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc 于是得到文法GS生成的語(yǔ)言L=a

13、nbncn|n13【解答】（1）由L=aibj|ji1知，所求該語(yǔ)言對(duì)應(yīng)的上下文無(wú)關(guān)文法首先應(yīng)有SaSb型產(chǎn)生式，以保證b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次，還需有SSb或SbS型的產(chǎn)生式，用以保證b的個(gè)數(shù)多于a的個(gè)數(shù)；也即所求上下文無(wú)關(guān)文法GS為：GS：SaSb|Sb|b4【解答】（1）分別畫出對(duì)應(yīng)兩句型的語(yǔ)法樹，如圖2-8-2所示句柄:AaB Bd Sa A c B AaB b S c AB d cb(a)S a A c BB S c AB d c(b)圖2-8-2 語(yǔ)法樹（2）句子acabcbbdcc的最左推導(dǎo)如下： SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbB

14、dcA acabcbbdcAacabcbbdcc S（ L ）L ， SS ( L ) S a圖2-8-3 句型（S,（a）的語(yǔ)法樹5【解答】（1）句型（S,（a）的語(yǔ)法樹如圖2-8-3所示（2）由圖2-8-3可知：短語(yǔ)：S、a、(a)、S,(a)、(S,(a)；直接短語(yǔ)：a、S；句柄：S；素短語(yǔ)：素短語(yǔ)可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即；# （，（a ） ） #因此素短語(yǔ)為a。TT * FF PP （ T ）T * F圖2-8-4 句型T*P（T*F）的語(yǔ)法樹6【解答】首先構(gòu)造T*P（T*F）的語(yǔ)法樹如圖2-8-4所示。由圖2-8-4可知，T*P（T*F）是文法GT的一個(gè)句型

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

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

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

18、式e，都存在一個(gè)DFA M，滿足L(G)=L(e)。（ ）五、基本題1、設(shè)M（x,y, a,b, f,x,y）為一非確定的有限自動(dòng)機(jī)，其中f定義如下：f（x,a）x,y f（x,b）yf（y,a） f（y,b）x,y 試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M。2、對(duì)給定正規(guī)式b*（d|ad）（b|ab）+，構(gòu)造其NFA M； 單選解答 1、b 2、c 3、c 4、d 5、b多選解答 1、a、c、e 2、a、b、d填空解答 1、NFA 2、正規(guī)集 3、DFA（NFA）所識(shí)別判斷解答 1 、2、3、錯(cuò) 4、5、6、7、8、正確 a a b b b圖3-6-2 NFA MXY基本1解答：對(duì)照自動(dòng)機(jī)的定義M=(S

19、,f,S0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，所以是一非確定有限自動(dòng)機(jī)，先畫出NFA M相應(yīng)的狀態(tài)圖，如圖3-6-2所示。用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣表3-6-3所示。IIaIbxx,yyyx,yx,yx,yx,y將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。表3-6-4 狀態(tài)轉(zhuǎn)換矩陣ab02112222 a a,b b b圖3-6-5 DFA M021即得到M=（0,1,2, a,b, f,0, 1,2），其狀態(tài)轉(zhuǎn)換圖如圖3-6-5所示。 a a,b b圖3-6-6 化簡(jiǎn)后的DFA M01將圖3-6-5的DFA M最小化。首先，將M的狀態(tài)分成終態(tài)組

20、1，2與非終態(tài)組0；其次，考察1,2。由于1,2a=1,2b=21,2，所以不再將其劃分了，也即整個(gè)劃分只有兩組0，1,2：令狀態(tài)1代表1,2，即把原來(lái)到達(dá)2的弧都導(dǎo)向1，并刪除狀態(tài)2。最后，得到如圖3-6-6所示化簡(jiǎn)DFA M。aadb*b*(d|ad)(b|ab)(b|ab)*XYX123YX4135Y678(d|ad)(b|ab)(b|ab)*2dbadabb|abbX4135Y2bdbbabb圖3-6-7 的NFA M2解答：首先用A+=AA*改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*；其次，構(gòu)造該正規(guī)式的NFA M，如圖3-6-7所示。第四章1、 構(gòu)造下面文法的LL（1

21、）分析表。D TLT int | realL id RR , id R | 2、 下面文法GS是否為L(zhǎng)L（1）文法？說(shuō)明理由。S A B | P Q x A x y B b cP d P | Q a Q | 3、 設(shè)有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| （1）求出該文法的每一個(gè)非終結(jié)符U的FOLLOW集。（2）該文法是LL（1）文法嗎？（3）構(gòu)造CS的LL（1）分析表。4、 將文法GV改造成為L(zhǎng)L(1)的。 GV：VN|NE EV|V+E Ni5、已知文法：GA：AaAa|（1）該文法是LL（1）文法嗎？為什么？（2）若采用LL（1）方法進(jìn)行語(yǔ)法分析

22、，如何得到該文法的LL（1）分析表？（3）若輸入符號(hào)串“aaaa”，請(qǐng)給出語(yǔ)法分析過程。1解答： LL（1）分析表見表4-3-1分析 雖然這個(gè)文法很簡(jiǎn)單，我們還是從求開始符號(hào)集合和后繼符號(hào)集合開始。 FIRST（D）=FIRST（T）=int, real FOLLOW（D）=FOLLOW（L）=#FIRST（L）=id FOLLOW（T）=idFIRST（R）=，, FOLLOW（R）=#有了上面每個(gè)非終結(jié)符的FIRST集合，填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部的FIRST（）就不是件難事了。填表時(shí)唯一要小心的時(shí)，是產(chǎn)生式R右部的一個(gè)開始符號(hào)，而#在FOLLOW（R）中，所以R填在輸入符號(hào)#的欄目中

23、。表4-3-1 LL（1）分析表非終結(jié)符輸入符號(hào)int realid，#DDTLDTLTTintTrealLLid RRR,id RR 2解答： 該文法不是LL（1）文法，見下面分析中的說(shuō)明。分析 只有三個(gè)非終結(jié)符有兩個(gè)選擇。 1、P的兩個(gè)右部d P 和 的開始符號(hào)肯定不相交。2、Q的兩個(gè)右部a Q 和 的開始符號(hào)肯定不相交。3、對(duì)S來(lái)說(shuō)，由于x FIRST(A B)，同時(shí)也有x FIRST(P Q x)（因?yàn)镻和Q都可能為空）。所以該文法不是LL（1）文法。3解答： （1）求文法的每一個(gè)非終結(jié)符U的FOLLOW集的過程如下：因?yàn)椋?S是識(shí)別符號(hào)，且有ABSD、BSAc、DSe，所以FOLLO

24、W（S）應(yīng)包含F(xiàn)IRST(D)FIRST(Ac) FIRST(e) #=a,da,d,c,ee#=a,c,d,e# 又因?yàn)锳BSD和D，所以FOLLOW中還包含F(xiàn)OLLOW(A)。因?yàn)镾aAbDe和BSAc,所以FOLLOW（A）=FIRST（bDe）FIRST（c）=b,c綜合、得FOLLOW（S）=a,d,c,e,#a,b,c,d,e,#因?yàn)锳BSD，所以 FOLLOW（B）=FIRST（SD）=a,d 因?yàn)镾aAbDe | d、ABSD| e和BSAc | cD，所以FOLLOW（D）=FIRST（e）FOLLOW（A）FOLLOW（B） =eb,ca,d=a,b,c,d,e（2）GS不

25、是LL（1）文法。因?yàn)楫a(chǎn)生式BSAc|cD| 中 FIRST（SAc）FOLLOW（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/cDSac/DSe/Se/4解答： 對(duì)文法GV提取公共左因子后得到文法： GV：VNAA|EEVBB|+ENi求出文法GV中每一個(gè)非終結(jié)符號(hào)的FIRST集： FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一個(gè)非終結(jié)符號(hào)的

26、FOLLOW集：FOLLOW(V)=#FIRST(B)FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST()FOLLOW(B)= FIRST()FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLLOW(N)= FIRST(A)FOLLOW(V)=,+,#可以看到，對(duì)文法GV的產(chǎn)生式A|E，有FIRST(E)FOLLOW(A)=+,#= 對(duì)產(chǎn)生式B|+E，有FIRST(+E)FOLLOW(B)=+= 而文法的其他產(chǎn)生式都只有一個(gè)不為的右部，所以文法GV是LL(1)文法。5解答：（1）因?yàn)楫a(chǎn)生式AaAa| 有空產(chǎn)生式右部

27、，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #所以該文法不是LL（1）文法。（2）若采用LL（1）方法進(jìn)行語(yǔ)法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)（可以為0）個(gè)a，所以得到文法GA：AaaA|此時(shí)對(duì)產(chǎn)生式AaaA|， 有 FOLLOW(A)=#FOLLOW(A)=#，因而FIRST(A)FOLLOW(A)=a, #=所以文法GA是LL（1）文法，按LL（1）分析表構(gòu)造算法構(gòu)造該文法的LL（1）分析表如表4-3-3所示。表4-3-3 文法GA的LL(1)分析表A#AAaaAA（3）若采用LL(1)方法進(jìn)行語(yǔ)法分析，對(duì)符號(hào)串“aaa

28、a”的分析過程如表4-3-4所示。 表4-3-4對(duì)符號(hào)串“aaaa”的分析過程步驟分析棧輸入串產(chǎn)生式/動(dòng)作1#Aa a a a #AaaA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #AaaA5#A a aa a #匹配6#A aa#匹配7#A#A8#接受第五章1.設(shè)有文法GS為：Sa|b|(A)ASdA|S（1） 完成下列算符優(yōu)先關(guān)系表，見表5-7-1，并判斷GS是否為算符優(yōu)先文法。表5-7-1 算符優(yōu)先關(guān)系表ab()d#ab()d# （2）給出句型（SdSdS）的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)。（3）給出輸入串（adb）#的分析過程。解答： （1

29、）先求文法GS的FIRSTVT集和LASTVT集：由Sa|b|(A)得：FIRSTVT(S)=a,b,( );由ASd得：FIRSTVT(A)=d;又由AS得：FIRSTVT(S) FIRSTVT(A)，即FIRSTVT(A)=d,a,b,(;由Sa|b|(A)得；LASTVT(S)=a,b,;由AdA得：LASTVT(A)=d,又由AS得：LASTVT(S) LASTVT(A)，即LASTVT(A)=d,a,b,)。構(gòu)造優(yōu)先關(guān)系表方法如下： 對(duì)Pab，或PaQb，有ab; 對(duì)PaR，而bFIRSTVT(R)，有ab; 對(duì)PRb，而aFIRSTVT(R)，有ab。由此得到： 由S(A)得：()

30、; 由S(A得：(FIRSTVT(A)，即：(d,(a ,(b,(;由AdA得：dFIRSTVT(A)，即：dd,da,db,d(; 由SA)得，LASTVT(A)，即：d),a),b),);由ASd得：LASTVT(S)d，即：ad,bd,)d;此外，由#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#ab()d#由表5-7-2可以看出，任何兩個(gè)終結(jié)符之間至少只滿足、三種優(yōu)先關(guān)系之一，故GS為算符優(yōu)先文法。SASASd（）ASd圖5-7-3 句型（Sd

31、SdS）的語(yǔ)法樹（2）為求出句型（SdSdS）的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄，我們先畫出該句型對(duì)應(yīng)的語(yǔ)法樹，如圖5-7-3所示。由圖5-7-3得到：短語(yǔ)：S，SdS，SdSdS，（SdSdS）簡(jiǎn)單短語(yǔ)（即直接短語(yǔ)）：S句柄（即最左直接短語(yǔ)）：S素短語(yǔ)：SdS，它同時(shí)也是該句型的最左素短語(yǔ)。（3）輸入串（adb）#的分析過程見表5-7-4表5-7-4 輸入串（adb）#的分析過程符號(hào)棧輸入串說(shuō)明#(adb)#移進(jìn)#（adb)#移進(jìn)#（adb)#用Sa歸約#（Sdb)#移進(jìn)#（Sdb)#移進(jìn)#（Sdb)#用Sb歸約#（SdS)#用AS歸約#（SdA)#用ASdA歸約#（A)#移進(jìn)#（A）#用S（A）歸約#

32、S#分析成功第六章一、單項(xiàng)選擇題1、若a為終結(jié)符，則Aa為 項(xiàng)目 a.歸約b.移進(jìn)c.接受d.待約2、若項(xiàng)目集Ik含有A，則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào)aFOLLOW(A)時(shí)，才采取“A”動(dòng)作的一定是 。 a.LALR文法b.LR（0）文法c.LR（1）文法d.SLR（1）文法3、就文法的描述能力來(lái)說(shuō)，有 。 a. SLR（1）LR（0） b. LR（1）LR（0）c. SLR（1）LR（1）d.無(wú)二義文法LR（1）4、在LR（0）的ACTION子表中，如果某一行中存在標(biāo)記“rj”的欄，則 。 a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個(gè) 指明了

33、在分析過程中的某時(shí)刻所能看到產(chǎn)生式多大一部分。 a.活前綴b.前綴c.項(xiàng)目d.項(xiàng)目集二、多項(xiàng)選擇題1、一個(gè)LR分析器包括 。 a.一個(gè)總控程序b.一個(gè)項(xiàng)目集c.一個(gè)活前綴d.一張分析表e.一個(gè)分析棧2、LR分析器核心部分是一張分析表，該表包括 等子表。 a.LL(1)分析b.優(yōu)先關(guān)系c.GOTO d.LRe.ACTION3、每一項(xiàng)ACTIONS，a所規(guī)定的動(dòng)作包括 。a.移進(jìn)b.比較c.接受d.歸約e.報(bào)錯(cuò)4、對(duì)LR分析表的構(gòu)造，有可能存在 動(dòng)作沖突。a.移進(jìn)b.歸約c.移進(jìn)/歸約d.移進(jìn)/移進(jìn)e.歸約/歸約5、就文法的描述能力來(lái)說(shuō)，有 。 a. SLR（1）LR（1）b. LR（1）SLR（

34、1）c. LR（0）LR（1）d. LR（1）無(wú)二義文法 e. SLR（1）無(wú)二義文法6、對(duì)LR分析器來(lái)說(shuō)，存在 等分析表的構(gòu)造方法。 a.LALRb.LR（0）c.SLR（1）d.SLR（0）e.LR（1）7、自上而下的語(yǔ)法分析方法有 。 a.算符優(yōu)先分析法b.LL（1）分析法c.SLR（1）分析法d.LR（0）分析法e.LALR（1）分析法三、填空題1、對(duì)于一個(gè)文法，如果能夠構(gòu)造 。使得它的 均是唯一確定的，則稱該文法為L(zhǎng)R文法。2、字的前綴是指該字的 。3、活前綴是指 的一個(gè)前綴，這種前綴不含 之后的任何符號(hào)。4、在LR分析過程中，只要 的已掃描部分保持可歸約成一個(gè) ，則掃描過的部分正確

35、。5、將識(shí)別 的NFA確定化，使其成為以 為狀態(tài)的DFA，這個(gè)DFA就是建立 的基礎(chǔ)。6、A稱為 項(xiàng)目；對(duì)文法開始符S為 項(xiàng)目；若a為終結(jié)符，則稱Aa為 項(xiàng)目；若B為非終結(jié)符，則稱Aa為 項(xiàng)目。 7、LR（0）分析法的名字中“L”表示 ，“R”表示 ，“0”表示 。四、綜合題1、對(duì)于文法GS： SAS|b ASA|a （1）列出所有LR（0）項(xiàng)目（2）列出構(gòu)成文法LR（0）項(xiàng)目集規(guī)范族。單項(xiàng)解答： 1、A稱為歸約項(xiàng)目，對(duì)文法開始符S的歸約項(xiàng)目，如S稱為接受項(xiàng)目，Aa（a為終結(jié)符）稱為移進(jìn)項(xiàng)目。在此選b.2、當(dāng)用產(chǎn)生式A歸約時(shí)，LR（0）無(wú)論面臨什么輸入符號(hào)都進(jìn)行歸約；SLR（1）則僅當(dāng)面臨的輸

36、入符號(hào)aFOLLOW(A)時(shí)進(jìn)行歸約；LR（1）則當(dāng)在把歸約為A的規(guī)范句型的前綴Aa前提下，當(dāng)后跟終結(jié)符a時(shí)，才進(jìn)行歸約；因此選d。3、由于LR（0）SLR（1） LR（1）無(wú)二義文法，故選c。4、選a。5、選c。多選解答： 1、一個(gè)LR分析器包括一個(gè)總控程序和一張分析表，選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、一張分析表 每個(gè)入口2、任意首部3、規(guī)范句型 句柄4、輸入串 活前綴5、活前綴 項(xiàng)目集合 LR分析算法6

37、、歸約 接受 移進(jìn) 待約7、自左至右分析 采用最右推導(dǎo)的逆過程即最左歸約 向右查看0個(gè)字符綜合解答：首先將文法G拓廣為GS：SSSAS|bASA|a（1）文法GS的LR（0）項(xiàng)目是： 1、SS5、SAS9、ASA 2、SS6、Sb10、ASA 3、SAS7、Sb11、Aa 4、SAS8、ASA12、Aa2、列出構(gòu)成文法LR（0）項(xiàng)目集規(guī)范族。用-CLOSURE（閉包）辦法構(gòu)造文法G的LR（0）項(xiàng)目集規(guī)范族如下：I0：1、SS I3：9、ASAI6：12、Aa 3、SAS8、ASAI7：7、Sb 8、ASA3、SAS 11、Aa6、Sb 6、Sb11、AaI1：2、SSI4：10、ASA 9、A

38、SA4、SAS8、ASA3、SAS11、Aa6、Sb3、SAS8、ASA6、Sb 11、AaI2：4、SASI5：5、SAS 3、SAS9、ASA6、Sb8、ASA 8、ASA11、Aa 11、Aa3、SAS6、Sb注意：I1中的SS和ASA是由狀態(tài)I0中的1和3讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目；，而I4中的ASA和AAS則是由I3中的9和3讀入一個(gè)A字符后得到的下一個(gè)項(xiàng)目；I5中的SAS和ASA則是由I4中的4和8讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目。狀態(tài)全體構(gòu)成了文法G的LR（0）規(guī)范族。第七章一、單項(xiàng)選擇題1、中間代碼生成所依據(jù)的是 。a.語(yǔ)法規(guī)則b.詞法規(guī)則c.語(yǔ)義規(guī)則d.等價(jià)變換規(guī)則2、四元式之間的聯(lián)系是通過 實(shí)現(xiàn)的。 a.指示器b.臨時(shí)變量c.符號(hào)表d.程序變量3、后綴式ab+cd+/可用表達(dá)式 來(lái)表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d4、表達(dá)式（AB）（CD）的逆波蘭表示為 。 a. ABCDb. ABCDc. ABCDd. ABCD5、中間代碼的樹型表示+ABCD+ 所對(duì)應(yīng)的表達(dá)式為 。 a.A+B+C+Db.A+(B+C)+Dc.(A+B)+C+Dd.(A+B)+(