編譯原理期末總復(fù)習(xí)題

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

2、序的意義。b.詞法規(guī)則d.詞法規(guī)則a oa .語(yǔ)義規(guī)則c .產(chǎn)生規(guī)則7、詞法分析器的輸入是a .單詞符號(hào)串c .語(yǔ)法單位8、中間代碼生成時(shí)所遵循的是a .語(yǔ)法規(guī)則c.語(yǔ)義規(guī)則9、編譯程序是對(duì) d。a .匯編程序的翻譯c .機(jī)器語(yǔ)言的執(zhí)行10、語(yǔ)法分析應(yīng)遵循 ba .語(yǔ)義規(guī)則c.構(gòu)詞規(guī)則解答b.源程序d.目標(biāo)程序-d。b.詞法規(guī)則d.等價(jià)變換規(guī)則b.高級(jí)語(yǔ)言程序的解釋執(zhí)行d.高級(jí)語(yǔ)言的翻譯b.語(yǔ)法規(guī)則d.等價(jià)變換規(guī)則1、將編譯程序分成若干個(gè)“遍”是為了使編譯程序的結(jié)構(gòu)更加清晰，故選bo2、構(gòu)造編譯程序應(yīng)掌握源程序、目標(biāo)語(yǔ)言及編譯方法等三方面的知識(shí)，故選do3、對(duì)編譯而言，變量既持有左值又持有右值

3、，故選c。4、編譯程序打交道最多的就是各種表格，因此選do3種，因此不是目標(biāo)代碼5、目標(biāo)代碼包括匯編指令代碼、可重定位指令代碼和絕對(duì)指令代碼 的只能選doa。6、詞法分析遵循的是構(gòu)詞規(guī)則，語(yǔ)法分析遵循的是語(yǔ)法規(guī)則，中間代碼生成遵循的是語(yǔ)義規(guī) 則，并且語(yǔ)義規(guī)則可以定義一個(gè)程序的意義。因此選7 、b 8 、c 9 、d 10 、c、多項(xiàng)選擇題1、編譯程序各階段的工作都涉及到bca .語(yǔ)法分析b.表格管理d .語(yǔ)義分析e.詞法分析2、編譯程序工作時(shí)，通常有 abcec.出錯(cuò)處理d解答1. b、c.詞法分析.語(yǔ)義檢查2. a 、b、c、階段。b.語(yǔ)法分析語(yǔ)義分析？ c.中間代碼生成e.目標(biāo)代碼生成中間

4、代碼優(yōu)化三、填空題解釋不產(chǎn)生目標(biāo)程序，邊翻譯邊執(zhí)1 、解釋程序和編譯程序的區(qū)別在于是否生成目標(biāo)程序( 行。、語(yǔ)法分析語(yǔ)義分析中間代碼生2、編譯過(guò)程通?？煞譃?5個(gè)階段，分別是 詞法分析、代碼優(yōu)化和目標(biāo)代碼生成。3、編譯程序工作過(guò)程中，第一段輸入是源程序,最后階段的輸出為目標(biāo)程序 程序。4、編譯程序是指將 解答 是否生成目標(biāo)程序2、源程序詞法分析程序翻譯成目標(biāo)程序程序的程序。中間代碼生成3、源程序標(biāo)語(yǔ)言目標(biāo)代碼生成4、源程序、單項(xiàng)選擇題1、文法G: SH>xSx|y所識(shí)別的語(yǔ)言是a. xyxb. (xyx)*c. xOyx n(n > 0)d. x*yx*(是指多個(gè)x)2、文法G描述

5、的語(yǔ)言L(fǎng)(G)是指aba. L(G)= a|S?c. L(G)= a |S?3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別a. 上下文無(wú)關(guān)文法c.正規(guī)文法4、設(shè)G為算符優(yōu)先文法，a.若 f(a)>g(b),則c. ab都不一定成立a £ Vt*a 6 (VtU Vn*)_ _ _ * b. L(G)= a |S ? d. L(G)= a |S +V* (VtU Vn*)Ob.上下文有關(guān)文法d.短語(yǔ)文法G的任意終結(jié)符對(duì)a、b有以下關(guān)系成立a>b b.若 f(a)<g(b),貝U a<bd. ab 一定成立5、如果文法 G是無(wú)二義的，則它的任何句子aa.b.c.d.最左推導(dǎo)和最右推導(dǎo)對(duì)

6、應(yīng)的語(yǔ)法樹(shù)必定相同最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同最左推導(dǎo)和最右推導(dǎo)必定相同可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同6、由文法的開(kāi)始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是a.短語(yǔ)b.句柄c.句型d.句子7、文法 G:E+T|T T- T*P|P A (E)|I則句型P+T+i的句柄和最左素短語(yǔ)為+T 和 i b. P 和 P+T c. i 和 P+T+i8 、設(shè)文法為:S- SA|Aaba, a. S卜囹SA是規(guī)范推導(dǎo)。abaSAA AAAaAA abAb. SSASAA AAAAAa Abaabac. SSASAA SAaSba Abaabad. SSASa SAaSba A

7、baabaAf a|b則對(duì)句子9、文法G:Sf b| A (T) T一 T,S|S貝U FIRSTVT(T)a. b, A,( b. b, A ,)c.b, A,(, , d.b, A ,), , 10、產(chǎn)生正規(guī)語(yǔ)言的文法為a. 0型b.1型11、采用自上而下分析，必須 。a.消除左遞歸b.消除布1歸12、在規(guī)范歸約中，用 來(lái)刻畫(huà)可歸約串。a.直接短語(yǔ)b.句柄13、有文法 G: E- E*T|TT- T+i|i句子1+2*8+6按該文法 G歸約，其值為 。a. 23 B. 42 c. 30 d. 1714、規(guī)范歸約指。a.最左推導(dǎo)的逆過(guò)可c.規(guī)范推導(dǎo)d.c. 2型c.消除回溯c.最左素短語(yǔ)d.

8、 3型d.提取公共左因子d.素短語(yǔ)b.最右推導(dǎo)的逆過(guò)程最左歸約的逆過(guò)程解答1 、選 c。2、選 a。3、選 Co4、雖然a與b沒(méi)有優(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。5、如果文法G無(wú)二義性，則最左推導(dǎo)是先生長(zhǎng)右邊的枝葉：對(duì)于 d,如果有兩個(gè)不同的是了左 推導(dǎo)，則必然有二義性。故選 a。6、選 Co7、由圖2-8-1的語(yǔ)法樹(shù)和優(yōu)先關(guān)系可以看出應(yīng)選boE + F/Tx iE + T PIIT iIP#<- + - >+< i >#圖2-8-

9、1句型P+T+I的語(yǔ)法及優(yōu)先關(guān)系8、規(guī)范推導(dǎo)是最左推導(dǎo)，故選 do9、由 T-T,和 T一( 得 FIRSTVT(T)=(, , );由 T一 S 得 FIRSTVT(S)? FIRSTVT(T),而 FIRSTVT(S)=b, A ,(;即因此選c。14 、bb.狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖 可以用狀態(tài)轉(zhuǎn)換圖表示FIRSTVT(T尸b, A ,(, , ;10、d 11、c 12 、b 13 、b二、多項(xiàng)選擇題1、下面哪些說(shuō)法是錯(cuò)誤的 。 a.有向圖是一個(gè)狀態(tài)轉(zhuǎn)換圖 c.有向圖是一個(gè) DFA2、對(duì)無(wú)二義性文法來(lái)說(shuō)，一棵語(yǔ)法樹(shù)往往代表了 。a.多種推導(dǎo)過(guò)程b.多種最左推導(dǎo)過(guò)程c. 一種最左推導(dǎo)過(guò)程d

10、.僅一種推導(dǎo)過(guò)程e. 一種最左推導(dǎo)過(guò)程3、如果文法G存在一個(gè)句子，滿(mǎn)足下列條件 之一時(shí)，則稱(chēng)該文法是二義文法。a.該句子的最左推導(dǎo)與最右推導(dǎo)相同b.該句子有兩個(gè)不同的最左推導(dǎo) c.該句子有兩棵不同的最右推導(dǎo) d.該句子有兩棵不同的語(yǔ)法樹(shù) e.該句子的語(yǔ)法樹(shù)只有一個(gè)4、有一文法G: SfABA 一aAb| £Bf cBd| £它不產(chǎn)生下面 集合。a. a nbmcndm|n,m >0b. ac. a nbmcmdn|n,m >0d. ae. a nbncndnln >05、自下而上的語(yǔ)法分析中，應(yīng)從 nbncmdmjn,m>0nbncmdmn,m>

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

12、約過(guò)程。6、自下而上分析法采用 、歸約、錯(cuò)誤處理、 等四種操作。7、Chomsky把文法分為 種類(lèi)型，編譯器構(gòu)造中采用 和 文法，它們分別產(chǎn)一答 生解.語(yǔ)言，并分別用 和 自動(dòng)機(jī)識(shí)別所產(chǎn)生的語(yǔ)言。1IHX42終結(jié)符 右自下而上分析接受型3型上下文無(wú)關(guān)語(yǔ)言正規(guī)語(yǔ)言下推自動(dòng)機(jī)有限四、判斷題1、文法SfaS|bR| e描述的語(yǔ)言是 （a|bc）*（）RH c S2、在自下而上的語(yǔ)法分析中，語(yǔ)法樹(shù)與分析樹(shù)一定相同。（）3、二義文法不是上下文無(wú)關(guān)文法。（）4、語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。（）5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過(guò)程。（）6、一個(gè)文法所有句型的集合形成該文法所能接受的語(yǔ)言。（）解答1

13、 、對(duì) 2 、錯(cuò) 3 、錯(cuò) 4 、錯(cuò) 5 、錯(cuò) 6 、錯(cuò)五、簡(jiǎn)答題1、句柄2、素短語(yǔ)3、語(yǔ)法樹(shù)4、歸約5、推導(dǎo) 解答1 、句柄：一個(gè)句型的最左直接短語(yǔ)稱(chēng)為該句型的句柄。2、素短語(yǔ)：至少含有一個(gè)終結(jié)符的素短語(yǔ)，并且除它自身之外不再含任何更小的素短語(yǔ)。3、語(yǔ)法樹(shù)：滿(mǎn)足下面 4個(gè)條件的樹(shù)稱(chēng)之為文法 GS的一棵語(yǔ)法樹(shù)。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VnU Vt中的一個(gè)符號(hào)；樹(shù)的根結(jié)點(diǎn)以文法 GS的開(kāi)始符S標(biāo)記；若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為中的一個(gè)符號(hào)；若一個(gè)以A為標(biāo)記的結(jié)點(diǎn)有 K個(gè)直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為K,X2，,Xk,則 ZX1,X2，,Xk,必然是 G的

14、一個(gè)產(chǎn)生式。4、歸約：我們稱(chēng)“ 丫 3直接歸約出aA3,僅當(dāng)A-丫 是一個(gè)產(chǎn)生式，且a、3 C （VnU Vt）*歸約過(guò)程就是從輸入串開(kāi)始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開(kāi)始符。5、推導(dǎo)：我們稱(chēng)a A 3直接推出“丫3, 即aAB 口丫3,僅當(dāng)A一 丫是一個(gè)產(chǎn)生式，且a、 3 C (VnU Vt)*。如果a i “2 an,則我們稱(chēng)這個(gè)序列是從a1至a 2的一個(gè)推導(dǎo)。若存在一個(gè)從a ian的推導(dǎo)，則稱(chēng)a 1可推導(dǎo)出a n。推導(dǎo)是歸約的逆過(guò)程。六、問(wèn)答題1、給出上下文無(wú)關(guān)文法的定義。解答一個(gè)上下文無(wú)關(guān)文法 G是一個(gè)四元式(Vt,Vn,S, P ),其中： VT是一個(gè)非空有限

15、集，它的每個(gè)元素稱(chēng)為終結(jié)符號(hào)； VN是一個(gè)非空有限集，它的每個(gè)元素稱(chēng)為非終結(jié)符號(hào)，VtAVn=； S是一個(gè)非終結(jié)符號(hào)，稱(chēng)為開(kāi)始符號(hào)； P是一個(gè)產(chǎn)生式集合(有限)，每個(gè)產(chǎn)生式的形式是 P-a ,其中，PC X, a C (VtU Vn)*。開(kāi)始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2、文法 GS:S 一 aSPQ|abQQA PQ bP- bb bQ 一 bc cCH cc(1)它是Chomsky哪一型文法？(2)它生成的語(yǔ)言是什么？解答(1)由于產(chǎn)生式左部存在終結(jié)符號(hào)，且所有產(chǎn)生式左部符號(hào)的長(zhǎng)度均小于等于產(chǎn)生式右部的符號(hào)長(zhǎng)度，所以文法 GS是Chomsky1型文法，即上下文有關(guān)文法。(2)

16、按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低(否則無(wú)法推出句子)，我們可以得到：S abQ abcS aSPQ aabQPQ aabPQQ aabbQQ aabbcQ aabbccS aSPQ aaSPQPQ aaabQPQPQ aaabPQQPQ aaabPQPQQ aaaPPQQQ aaabbPqqq aaabbQQQ aaabbbcQQ aaabbbccQ aaabbbccc于是得到文法 GS生成的語(yǔ)言L(fǎng)=anbncn|n >13、按指定類(lèi)型，給出語(yǔ)言的文法。L=a1 bj |j > i > 1的上下文無(wú)關(guān)文法。【解答】(1)由L=aibj|j >i>1知，所求該語(yǔ)

17、言對(duì)應(yīng)的上下文無(wú)關(guān)文法首先應(yīng)有S 一 aSb型產(chǎn)生式，以保證b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次，還需有S-Sb或S-bS型的產(chǎn)生式，用以保證b的個(gè)數(shù)多于a的個(gè)數(shù)；也即所求上下文無(wú)關(guān)文法GS為：GS : Sf aSb|Sb|b4、有文法 G: SfaAcB|BdZ AaB|cBf bScA|b(1)試求句型 aAaBcbbdcc和aAcbBdcc的句柄；(2)寫(xiě)出句子 acabcbbdcc的最左推導(dǎo)過(guò)程?！窘獯稹?1)分別畫(huà)出對(duì)應(yīng)兩句型的語(yǔ)法樹(shù)，如圖 2-8-2所示句柄：AaB BdSA c BA/八 /7(b)圖2-8-2 語(yǔ)法樹(shù)(2)句子acabcbbdcc的最左推導(dǎo)如下：S aAcB aAaBc

18、B acaBcB acabcB acabcbScA acabcbBdcAacabcbbdcA5、對(duì)于文法GS:acabcbbdccS(1) 語(yǔ)?！窘獯稹?1)一 (L) |aS|a畫(huà)出句型(S,句型(S, (a)(2)L, S|S(a)的語(yǔ)法樹(shù)。(2)寫(xiě)出上述句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短的語(yǔ)法樹(shù)如圖由圖2-8-3可知:S2-8-3 所示 /|(L )/ 短語(yǔ)：S、a、(a)、S,(a)、(S,(a);直接短語(yǔ)：a、S;句柄：S;a圖2-8-3 句型(S, (a)的語(yǔ)法樹(shù)素短語(yǔ)：素短語(yǔ)可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即;# <(<； < (< a&

19、gt; )> ) A #因此素短語(yǔ)為a。6、考慮文法GT:T-T*F|F FfFT P|P P-( T) |i證明t*pT(t*f)是該文法的一個(gè)句型，并指出直接短 【解答】語(yǔ)和句柄。首先構(gòu)造T*PT (T*F)的語(yǔ)法樹(shù)如圖2-8-4所示。由圖2-8-4 可知，T*PT (T*F)是文法 GT直接短語(yǔ)有兩個(gè)，即 P和T*F;句柄為P。的一個(gè)句型。I /l P )P2-8-4句型T*P T (T*F)的語(yǔ)法樹(shù)、單項(xiàng)選擇題1、詞法分析所依據(jù)的是 a.語(yǔ)義規(guī)則b.構(gòu)詞規(guī)則c.語(yǔ)法規(guī)則d.等價(jià)變換規(guī)則2、詞法分析器的輸出結(jié)果是 a.單詞的種別編碼c.單詞的種別編碼和自身值 3、正規(guī)式M1和M等價(jià)

20、是指b.單詞在符號(hào)表中的位置 d.單詞自身值a. M 1和M2的狀態(tài)數(shù)相等c. M 1和M2所識(shí)別的語(yǔ)言集相等b. M 1和M的有向弧條數(shù)相等d. M 1和M狀態(tài)數(shù)和有向弧條數(shù)相等Oa.以0開(kāi)頭的二進(jìn)制數(shù)組成的集合c.含奇數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合b.d.以0結(jié)尾的二進(jìn)制數(shù)組成的集合 含偶數(shù)個(gè)0的二進(jìn)制數(shù)組成的集合5、詞法分析器作為獨(dú)立的階段使整個(gè)編譯程序結(jié)構(gòu)更加簡(jiǎn)潔、a.詞法分析器應(yīng)作為獨(dú)立的一遍b.明確，因此，詞法分析器作為子程序較好c.詞法分析器分解為多個(gè)過(guò)程，由語(yǔ)法分析器選擇使用d.詞法分析器并不作為一個(gè)獨(dú)立的階段4、狀態(tài)轉(zhuǎn)換圖(見(jiàn)圖 3-6-1 )接受的字集為用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣

21、表3-6-3所示。解答 1 、 b 2 、 c二、多項(xiàng)選擇題1、 a. d.2、在詞法分析中, 基本字 逆波蘭式 令匯=a,b,能識(shí)別出b.e.四元式 常數(shù)c.運(yùn)算符則匯上所有以b開(kāi)頭，后跟若干個(gè)a. b(ab)*d. (ba) +bb. b(ab)e. b(a|b)ab的字的全體對(duì)應(yīng)的正規(guī)式為 c.(ba)*b解答1、 a、c、e 2a、b、d、填空題1、確定有限自動(dòng)機(jī)DFA是2、若二個(gè)正規(guī)式所表示的_的一個(gè)特例。相同，則認(rèn)為二者是等價(jià)的。3、一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由解答1 四、判斷題、NFA 2、正規(guī)集 3、DFA (NFA)所識(shí)別1、一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一終態(tài)。2

22、、設(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è)右線(xiàn)性文法6、對(duì)任意一個(gè)右線(xiàn)性文法7、對(duì)任何正規(guī)表達(dá)式8、對(duì)任何正規(guī)表達(dá)式e,e,解答1、2、3、錯(cuò)4五、基本題G,都存在一個(gè) NFA M,滿(mǎn)足L(G尸L(M)。G,都存在一個(gè) DFA M 滿(mǎn)足L(G尸L(M)。 都存在一個(gè) NFA M滿(mǎn)足L(G)=L(e)。 都存在一個(gè) DFA M滿(mǎn)足L(G)=L(e)。、5、6、7、8、正確() ( ) ) ) )1、設(shè) M= (x,y, a,b, f,x,y f

23、(x,a ) f (y,a )為一非確定的有限自動(dòng)機(jī)，其中定義如下:=x,y=4f (x,b) =yf (y,b ) = x,y試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)解答：對(duì)照自動(dòng)機(jī)的定義M=(S, N,f,S o,Z),由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，所以是一非確定有限自動(dòng)機(jī)，先畫(huà)出NFA M相應(yīng)的狀態(tài)圖，如圖 3-6-2所示。II aI bxx,yyy一x,yx,yx,yx,y將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態(tài)轉(zhuǎn)換矩陣。表3-6-4 狀態(tài)轉(zhuǎn)換矩陣ab0211一2222即得到M, *,10, 如f,0, 1，2),其狀態(tài)轉(zhuǎn)換圖如圖3-6-5所示。1,2:令狀

24、態(tài)1代表1,2,即把原來(lái)到達(dá)2的弧都導(dǎo)向 所示化簡(jiǎn)DFA M'。ab圖3-6-6 化簡(jiǎn)后的DFA M'2、對(duì)給定正規(guī)式 b* (d|ad ) ( b|ab ) +,構(gòu)造其 NFA M; 解答：首先用 A+=AA改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab) 3-6-7所示。 *b(d|ad)(b|ab)(baqb* C)(d|ad.1 2)(b|ab.( 甘d 口 hwQt：4c1XI£j； adab& MEL aMfe1,并刪除狀態(tài)2。最后，得到如圖3-6-6;其次，構(gòu)造該正規(guī)式的 NFA M,如圖01-b二 M d X 0a將圖3-6-5的DFA

25、M最小化。首先，將M'的狀態(tài)分成終態(tài)組1 , 2與非終態(tài)組0;其次，考察1,2。由于1,2a=1,2b=2? 1,2,所以不再將其劃分了，也即整個(gè)劃分只有兩組0,圖 3-6-7 的 NFA M1、構(gòu)造下面文法的LL (1)分析表。A TLT一 int | realL 一 id RRH , id R |£解答：LL (1)分析表見(jiàn)表4-3-1分析 雖然這個(gè)文法很簡(jiǎn)單，我們還是從求開(kāi)始符號(hào)集合和后繼符號(hào)集合開(kāi)始。FIRST (D) =FIRST (T) =int, real FOLLOW D =FOLLOW L) =#FIRST (L) =idFOLLOW T =idFIRST

26、( R = , , s FOLLOW R) =#有了上面每個(gè)非終結(jié)符的FIRST集合，填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部”的FIRST (a)就不是件難事了。填表時(shí)唯一要小心的時(shí)，£ 是產(chǎn)生式 Ae右部的一個(gè)開(kāi)始符號(hào)，而 # FOLLOW R)中，所 以 -e填在輸入符號(hào)#的欄目中。表4-3-1 LL (1)分析表非終結(jié)符輸入符號(hào)intrealid#DA TLA TLTT- intT一 realLLfid RRRf ,id RR- £2、 下面文法GS是否為L(zhǎng)L (1)文法？說(shuō)明理由。S 一 A B | P Q xA 一 x y B 一 b cP 一 d P | eQ 一 a

27、Q | e解答：該文法不是LL (1)文法，見(jiàn)下面分析中的說(shuō)明。分析只有三個(gè)非終結(jié)符有兩個(gè)選擇。1 、P的兩個(gè)右部d P和e的開(kāi)始符號(hào)肯定不相交。2、Q的兩個(gè)右部a Q和e的開(kāi)始符號(hào)肯定不相交。3、對(duì)S來(lái)說(shuō)，由于 x C FIRST(A B),同時(shí)也有 x C FIRST(P Q x)(因?yàn)镻和Q都可能為空) 所以該文法不是 LL (1)文法。3、 設(shè)有以下文法：GS : Sf aAbDe|dA 一 BSD|e B f SAc| cD| £ D 一 Se| e(1)求出該文法的每一個(gè)非終結(jié)符U的FOLLOW!。(2)該文法是 LL(1)文法嗎？(3)構(gòu)造CS的LL (1)分析表。解答

28、： (1)求文法的每一個(gè)非終結(jié)符U的FOLLOW!的過(guò)程如下：因?yàn)椋篠是識(shí)別符號(hào)，且有 Z BSD BfSAc、Df Se,所以FOLLOW S)應(yīng)包含 FIRST(D) U FIRST(Ac) U FIRST(e) U # =a,d Ua,d,c,e U e U # =a,c,d,e#又因?yàn)锳-BSD和 Ae,所以 FOLLOW還包含 FOLLOW(A) 因?yàn)镾- aAbDe和B-SAc,所以 FOLLOW A) =FIRST (bDe) U FIRST ( c) =b,c綜合、得 FOLLOWS) =a,d,c,e,# U a,b,c,d,e,# 因?yàn)?A- BSQ 所以 FOLLOW (

29、 B) =FIRST (SD)=a,d 因?yàn)?S- aAbDe | d、A- BSD| e 和 B- SAc | cD ,所以FOLLOW D) =FIRST (e) U FOLLOW A) U FOLLOWS B)=e U b,c U a,d=a,b,c,d,e(2) GS不是 LL (1)文法。因?yàn)楫a(chǎn)生式Bf SAc|cD| £中FIRST(SAc) n FOLLOWS B) =a,d w?(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#SaAbDedABS

30、DBSDBSDeBSac/ ecDSac/ eDSe/ e££Se/ e£4、 將文法GV改造成為L(zhǎng)L(1)的。GV : " N|NEE一 V|V+EN一 i解答： 對(duì)文法GV提取公共左因子后得到文法：G ' V ： V- NA2 £ |EVBBf s |+ENR i求出文法 G V中每一個(gè)非終結(jié)符號(hào)的FIRST集：FIRST(V)=iFIRST(A)=,£ FIRST(E)=iFIRST(B尸+,£ FIRST(N)=i求出文法G V中每一個(gè)非終結(jié)符號(hào)的FOLLOW!:FOLLOW(V)=# U FIRST(B)

31、£ U FOLLOW(E尸#,+,FOLLOW(A)= FOLLOW(V尸+,#FOLLOW(E尸 FIRST() £ U FOLLOW(B)= FIRST() £ U FOLLOW(E)=FOLLOW(B)= FOLLOW(E尸 FOLLOW(N)= FIRST(A) £ U FOLLOW(V尸,+,#可以看到，對(duì)文法 G' V的產(chǎn)生式A- s |E,有 FIRST(E) A FOLLOW(A)= n +,#=?對(duì)產(chǎn)生式B- e |+E ,有FIRST(+E) A FOLLOW(B尸+ A = ?而文法的其他產(chǎn)生式都只有一個(gè)不為£的右

32、部，所以文法G' V是LL(1)文法。5、已知文法：GA :A- aAa| £(1)該文法是LL (1)文法嗎？為什么？(2)若采用LL (1)方法進(jìn)行語(yǔ)法分析，如何得到該文法的LL (1)分析表？(3)若輸入符號(hào)串“ aaaa”，請(qǐng)給出語(yǔ)法分析過(guò)程。解答：(1)因?yàn)楫a(chǎn)生式 A- aAa| £有空產(chǎn)生式右部，而 FOLLOW(A)=# U FIRST(a尸a, #造成 FIRST(A) n FOLLOW(A尸A,£ n a, # w?所以該文法不是 LL (1)文法。(2)若采用LL (1)方法進(jìn)行語(yǔ)法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)(可以為0)個(gè)a

33、,所以得到文法G A :Z aaA| £此時(shí)對(duì)產(chǎn)生式 A- aaA| s , 有 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#AA一 aaAA- £(3)若采用LL(1)方法進(jìn)行語(yǔ)法分析，對(duì)符號(hào)串“aaaa”的分析過(guò)程如表 4-3-4所示。表4-3-4對(duì)符號(hào)串“ aaaa”的分析過(guò)程步驟分析棧輸入串產(chǎn)生式/動(dòng)作1#Aa a a a #Z a

34、aA2#A a aa a a a #匹配3#A aa a a #匹配4#Aa a #Z aaA5#A a aa a #匹配6#A aa#匹配7#A#Ar> £8#接受第七節(jié)習(xí)題設(shè)有義法GS為:Sf a|b|(A)ab()d#a?b?(?)?d#?5-7-1 ,并判斷GS是否為算符優(yōu)先文法。算符優(yōu)先關(guān)系表2 SdA|S完成下列算符優(yōu)先關(guān)系表，見(jiàn)表表 5-7-1(2)給出句型(SdSdS)的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)。(3)給出輸入串(adb) #的分析過(guò)程。(1)解答：(1)先求文法 G網(wǎng)的FIRSTVT集和LASTVT集：由 S-a|b|(A)得：FIRSTVT(

35、S尸a,b,();由 A一 Sd 得：FIRSTVT(A)=d;又由 A一 S 得：FIRSTVT(S) ? FIRSTVT(A),即 FIRSTVT(A尸d,a,b,(;由 S-a|b|(A)得；LASTVT(S)=a,b,;由 A 一 dA 得：LASTVT(A)=d,又由 A - S 得：LASTVT(S) ? LASTVT(A),即 LASTVT(A)=d,a,b,)。構(gòu)造優(yōu)先關(guān)系表方法如下：對(duì)ab，或4aQb，有a? b;對(duì)aR,而 bC FIRSTVT(R),有 a? b;對(duì)Rt> -,而 aC FIRSTVT(R),有 a? b。由此得到：由 S一 (A)得：(？); 由

36、S一(A得：(？ FIRSTVT(A),即：(？ d,( ? a ,( ? b,( ?(;由 A一dA得：d? FIRSTVT(A), 即：d? d,d ? a,d ? b,d ?(; 由 Sf A)得，LASTVT(A)?),即：d? ),a ? ),b ? ),) ?);由 A-Sd得：LASTVT(S)? d,即：a ? d,b ? d,) ? d;此外，由 #S#W： #? #；由#? FIRSTVT(S)得：#? a,# ? b,# ?(;脂由 LASTVT(S)? #得：d? #,a ? #,b ? #,) ? #。最后得到算符優(yōu)先關(guān)系表，見(jiàn)表5-7-2 。表5-7-2算符優(yōu)先關(guān)系

37、表ab()d#a?b?(?)?d?#?由表5-7-2可以看出，任何兩個(gè)終結(jié)符之間至少只滿(mǎn)足？、？、？三種優(yōu)先關(guān)系之一，故 GS為算符優(yōu)先文法。（2）為求出句型（SdSdS）的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄，我們先畫(huà)出該句型對(duì)應(yīng)的語(yǔ)法樹(shù)，如圖 5-7-3所示。由圖5-7-3得到：短語(yǔ)：S, SdS, SdSdS （SdSdS）簡(jiǎn)單短語(yǔ)（即直接短語(yǔ)）：S句柄（即最左直接短語(yǔ)）：S素短語(yǔ)：SdS,它同時(shí)也是該句型的最左素短語(yǔ)。(3)輸入串(adb) #的分析過(guò)程見(jiàn)表 5-7-4表5-7-4 輸入串(adb) #的分析過(guò)程符號(hào)棧輸入串說(shuō)明#(adb)#移進(jìn)# (adb)#移進(jìn)# (adb)#用Sfa歸約# (S

38、db)#移進(jìn)# (Sdb)#移進(jìn)# (Sdb)#用Sfb歸約# (SdS)#用A-S歸約# (SdA)#用SdA歸約# (A)#移進(jìn)# (A)#用S-( A)歸約#S#分析成功第四節(jié) 習(xí)題一、單項(xiàng)選擇題1、若a為終結(jié)符，則A-“ ap為 項(xiàng)目a. 歸約b.移進(jìn)c.接受d.待約2、若項(xiàng)目集Ik含有A-a ,則在狀態(tài)k時(shí)，僅當(dāng)面臨的輸入符號(hào) aCFOLLOW(A時(shí)，才采取“A 一 a ”動(dòng)作的一定是。文法 (0)文法 (1)文法 (1)文法3、就文法的描述能力來(lái)說(shuō)，有 一。a. SLR (1) ? LR (0) b. LR (1) ? LR (0) c. SLR (1) ? LR (1) d.無(wú)二

39、義文法？ LR ( 1)4、在LR (0)的ACTION子表中，如果某一行中存在標(biāo)記“ 門(mén)”的欄，則 。a.該行必定填滿(mǎn)口b.該行未填滿(mǎn)rjc.其他行也有口子表中也有rj5、一個(gè) 指明了在分析過(guò)程中的某時(shí)刻所能看到產(chǎn)生式多大一部分。a.活前綴b.前綴c.項(xiàng)目d.項(xiàng)目集解答：1 、Aa 稱(chēng)為歸約項(xiàng)目，對(duì)文法開(kāi)始符 S'的歸約項(xiàng)目，如S' a 稱(chēng)為接受項(xiàng)目，A- a a 3(a為終結(jié)符)稱(chēng)為移進(jìn)項(xiàng)目。在此選 b.2、當(dāng)用產(chǎn)生式 A-a歸約時(shí)，LR (0)無(wú)論面臨什么輸入符號(hào)都進(jìn)行歸約；SLR (1)則僅當(dāng)面臨的輸入符號(hào)aCFOLLOW(A時(shí)進(jìn)行歸約；LR (1)則當(dāng)在把 “歸約為A

40、的規(guī)范句型的前綴 3 Aa前 提下，當(dāng)“后跟終結(jié)符a時(shí)，才進(jìn)行歸約；因此選 do3、由于 LR (0) ? SLR (1) ? LR (1) ?無(wú)二義文法，故選 c。4、選 a。5、選 Co 二、多項(xiàng)選擇題1、一個(gè)LR分析器包括。a. 一個(gè)總控程序 b. 一個(gè)項(xiàng)目集c. 一個(gè)活前綴d. 一張分析表 e. 一個(gè)分析棧2、LR分析器核心部分是一張分析表，該表包括等子表。分析 b.優(yōu)先關(guān)系3、每一項(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、就文法的描

41、述能力來(lái)說(shuō)，有 。a. SLR (1) ? LR (1) b. LR (1) ? SLR (1)c. LR (0) ? LR (1)d. LR (1) ?無(wú)二義文法 e. SLR (1) ?無(wú)二義文法6、對(duì)LR分析器來(lái)說(shuō)，存在 等分析表的構(gòu)造方法。(0)(1)(0)(1)7、自上而下的語(yǔ)法分析方法有 。a.算符優(yōu)先分析法(1)分析法(1)分析法(0)分析法(1)分析法解答：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、

42、e。6、選 a、b、c、e。7、選 a、c、d、e。三、填空題1、對(duì)于一個(gè)文法，如果能夠構(gòu)造。使得它的均是唯一確定的，則稱(chēng)該文法為L(zhǎng)R文法。2、字的前綴是指該字的 。3、活前綴是指 的一個(gè)前綴，這種前綴不含 之后的任何符號(hào)。4、在LR分析過(guò)程中，只要 的已掃描部分保持可歸約成一個(gè) ,則掃描過(guò)的部分正確。5、將識(shí)別 的NFA確定化，使其成為以 為狀態(tài)的DFA這個(gè)DFA就是建立 的基礎(chǔ)。6、A-> a ,稱(chēng)為項(xiàng)目；對(duì)文法開(kāi)始符 S' -> a 為項(xiàng)目；若a為終結(jié)符，則稱(chēng)A- a , a 3為 項(xiàng)目；若B為誣結(jié)符，則稱(chēng) A-a ap為 而：7 、LR (0)分析法的名字中“ L”

43、表示, "R'表示, “0”表示 解答：1 、一張分析表每個(gè)入口2、任意首部3、規(guī)范句型句柄4、輸入串 活前綴5、活前綴 項(xiàng)目集合LR分析算法6、歸約接受移進(jìn)待約7、自左至右分析采用最右推導(dǎo)的逆過(guò)程即最左歸約向右查看0個(gè)字符四、綜合題1、對(duì)于文法 GS : SfAS|bAf SA|a(1)列出所有LR (0)項(xiàng)目(2)列出構(gòu)成文法 LR (0)項(xiàng)目集規(guī)范族。解答：首先將文法G拓廣為GS':S' 一 S項(xiàng)目是：5、S一 AS ,6、Sf b9、2 S - A10、A-SA-Sf AS|b Z SA|a (1)文法 GS'的 LR (0)1、S'

44、一 - S2、S' 一 S 3、S一 , AS7、S一 b ,11、Af a8、Af SA2、列出構(gòu)成文法 LR (0)項(xiàng)目集規(guī)范族。用e -CLOSURE閉包)辦法構(gòu)造文法 G'白L LR (0)項(xiàng)目集規(guī)范族如下:0:1、S' 一 - SI 3： 9、Af S - A16： 12、Aa3、Sf AS8、Af SA17： 7、Sf b -8、Af SA3、Sf AS11、A一 a6、S 一 - b6、Sf , b11、2 . a1:2、S' -S-I 4： 10、ZSA-9、Af S - A4、SfA - S8、Z - SA3、Sf - AS11、A一 a6、S

45、 一 - b3、Sf AS8、Af SA6、Sf b11、Z . a2：4、Sf A- SI 5 :5、S-AS-3、Sf AS9、Af S - A6、Sf b8、Af SA8、Af SA11、Z . a11 、A一 a3、Sf - AS6、S 一 , b注意：Il中的S' -S 和A一 SA是由狀態(tài)I。中的1和3讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目；， 而I4中的A- SA和A- A- S則是由I3中的9和3讀入一個(gè)A字符后得到的下一個(gè)項(xiàng)目；、中的S 一AS和A- S- A 則是由I4中的4和8讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目。狀態(tài)全體構(gòu)成了文法 G'白L LR (0)規(guī)范族。第

46、八節(jié) 習(xí)題、單項(xiàng)選擇題d.等價(jià)變換規(guī)則d.程序變量+b+c/d1、中間代碼生成所依據(jù)的是。a.語(yǔ)法規(guī)則b.詞法規(guī)則c.語(yǔ)義規(guī)則2、四元式之間的聯(lián)系是通過(guò) 實(shí)現(xiàn)的。a.指示器b.臨時(shí)變量c.符號(hào)表3、后綴式ab+cd+/可用表達(dá)式 來(lái)表示。+b/c+db.(a+b)/(c+d)+b/(c+d)4、表達(dá)式 3 AV B) A ( CV D)的逆波蘭表示為 。a. r ABV A CDMb. A n BV CDV Ac. AB Vr CDV Ad. A r BV A CDV5、中間代碼的樹(shù)型表示A B C D所對(duì)應(yīng)的表達(dá)式為+B+C+D +(B+C)+Dc.(A+B)+C+Dd.(A+B)+(C+D

47、)6、四元式表示法的優(yōu)點(diǎn)為 。a.不便于優(yōu)化處理，但便于表的更動(dòng)c.便于優(yōu)化處理，也便于表的更動(dòng)7、終結(jié)符具有 屬性。a.傳遞b.繼承解答1 、選 c。b.不便于優(yōu)化處理，但節(jié)省存儲(chǔ)空間 d.便于表的更動(dòng)，也節(jié)省存儲(chǔ)空間c.抽象d.綜合2、四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的，故選bo3、選 bo4、選 bo5、選d6、四元式表示法的優(yōu)點(diǎn)與間接三元式相同，故選c。7、選 do、多頂選擇題1、中間代碼主要有a.四元式d.后綴式e.間接三元式2、下面中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b+c的有a. ab+c+b. abc+ c.+/ + c / a b+a + /.a+b+c3、在下面的a.

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

49、正確表示 a+b+c,而e不是中間代碼：故選 a、c。3、凡涉及到跳轉(zhuǎn)的語(yǔ)句都需要采用拉鏈一一回填技術(shù)，故選 b、c、do4、選 b、c5、選 b、do6、選 b、 e。7、選 b、c、e。三、填空題1、中間代碼有 等形式，生成中間代碼主要是為了使 。2、語(yǔ)法制導(dǎo)翻譯既可以用來(lái)產(chǎn)生 代碼，也可以用來(lái)產(chǎn)生 指令，甚至可用來(lái)對(duì)輸 入串進(jìn)行。3、當(dāng)源程序中的標(biāo)號(hào)出現(xiàn)“先引用后定義”時(shí)，中間代碼的轉(zhuǎn)移地址須持 時(shí)才能確定, 因而要進(jìn)行。4、文法符號(hào)的屬性有兩種，一種稱(chēng)為 ,另一種稱(chēng)為 。5、后綴式abc-/所代表的表達(dá)式是 ,表達(dá)式(a-b)*c 可用后綴式 表示。6、用一張 輔以 的辦法來(lái)表示中間代

50、碼，這種表示法稱(chēng)為間接三元式。解答1、逆波蘭記號(hào)、樹(shù)形表示、三元式、四元式目標(biāo)代碼的優(yōu)化容易實(shí)現(xiàn)2、中間3、標(biāo)號(hào)定義4、繼承屬性5、a/(b-c)6、間接碼表 四、綜合題目標(biāo)解釋執(zhí)行回填綜合屬性ab-c*三兀式表1、給出下列表達(dá)式的逆波蘭表示(后綴式) a*(-b+c)(A V B) A (CVrDA E)2、寫(xiě)出算術(shù)表達(dá)式： A+B*(C-D)+E/(C-D) TN的四元式序列；三元式序列；間接三元式序列 解答1、 abc+*; AB V CD EA V A2、表達(dá)式的四元式序列：(1) (-,C,D,T i) (*,B,T i,T2) (3) (+,A,T 2,T3) (4) (-,C,D,T 4) (5) ( T ,T4,N,T 5)(/，E，(4)(6) (/,E,T5,T6)(+,(3),(5)第三節(jié)一、單項(xiàng)選擇題1、編譯程序使用