編譯原理期末復(fù)習(xí)題含答案

1、WORD格式專業(yè)資料整理第八節(jié) 習(xí)題一、單項(xiàng)選擇題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源程序c編譯方法3、變量應(yīng)當(dāng)。a持有左值c既持有左值又持有右值4、編譯程序絕大多數(shù)時(shí)間花在 a出錯(cuò)處理 c目標(biāo)代碼生 成5、不可能是目標(biāo)代碼a匯編指令代 碼c絕對(duì)指令代碼b目標(biāo)語(yǔ)言d以上三項(xiàng)都是b持有右值 d既不持有左值也不持有右 值上。b詞法分析d管理表格b可重定位指令代碼d中間代碼6、使用可以定義一個(gè)程序的意義。a語(yǔ)義規(guī)則b詞法規(guī)則c產(chǎn)生規(guī)則d詞法規(guī)則

2、7、詞法分析器的輸入是a單詞符號(hào)串c語(yǔ)法單位8、中間代碼生成時(shí)所遵循的是a語(yǔ)法規(guī)則c語(yǔ)義規(guī)則9、編譯程序是對(duì)。a匯編程序的翻譯c機(jī)器語(yǔ)言的執(zhí)行10、語(yǔ)法分析應(yīng)遵循a語(yǔ)義規(guī)則c構(gòu)詞規(guī)則解答b源程序d目標(biāo)程序。b詞法規(guī)則d等價(jià)變換規(guī)則b高級(jí)語(yǔ)言程序的解釋執(zhí)行d高級(jí)語(yǔ)言的翻譯b語(yǔ)法規(guī)則d等價(jià)變換規(guī)則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 種

3、，因此不是目標(biāo)代碼的只能選 d。6、詞法分析遵循的是構(gòu)詞規(guī)則，語(yǔ)法分析遵循的是語(yǔ)法規(guī)則，中間代碼生成遵循的是語(yǔ)義規(guī) 則，并且語(yǔ)義規(guī)則可以定義一個(gè)程序的意義。因此選a。7、b8、 c9、 d10、c、多項(xiàng)選擇題到a語(yǔ)法分析d語(yǔ)義分析2、編譯程序工作時(shí)，通常 有a詞法分析d語(yǔ)義檢查解答解答是否生成目標(biāo)程序2、詞法分析中間代碼生成3、源程序目標(biāo)代碼生成4、源程序目1、編譯程序各階段的工作都涉及b表格管理c出錯(cuò)處理e詞法分析階段。b語(yǔ)法分析c中間代碼生成e目標(biāo)代碼生成1b、c2.a 、b、 c、e 三、填空題1、解釋程序和編譯程序的區(qū)別在 于。、語(yǔ)法分 、代碼優(yōu)化和目標(biāo)代碼2、編譯過(guò)程通?？煞譃? 個(gè)

4、階段，分別是析 生3、編譯程序工作過(guò)程中，第一段輸入 成。 是 ，最后階段的輸出為 程序。4、編譯程序是指將程序翻譯成 程序的程序。標(biāo)語(yǔ)言、單項(xiàng)選擇題1、文法 G： S xSx|y 所識(shí)別的語(yǔ)言是 。a.xyx b.(xyx)*c.x nyx n(n 0)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? , (VT VN*)3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別a. 上下文無(wú)關(guān)文法c. 正規(guī)文法4、設(shè) G 為算符優(yōu)先文法，b. 上下文有關(guān)文法d. 短語(yǔ)文法G的任

5、意終結(jié)符對(duì) a、b 有以下關(guān)系成立a. 若 f(a)>g(b) ，則 a>b b. 若 f(a)<g(b) ，則 a<bc. ab 都不一定成立 d.ab 一定成立5、如果文法 G 是無(wú)二義的，則它的任何句子 。a. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)必定相同b. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹(shù)可能不同c. 最左推導(dǎo)和最右推導(dǎo)必定相同d. 可能存在兩個(gè)不同的最左推導(dǎo)，但它們對(duì)應(yīng)的語(yǔ)法樹(shù)相同6、由文法的開(kāi)始符0 步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列經(jīng)是7、a. 短語(yǔ) 文法 G： EE+T|Tb. 句柄c. 句型 d. 句子則句型TT*P|PP(E)|P+T+i 的句柄和最左素短語(yǔ)為

6、a.P+T 和 ib.P 和 P+Tc.i 和 P+T+id.P 和 T8、設(shè)文法為： S SA|AAa|b 則對(duì)句子 aba，下面是規(guī)范推導(dǎo)。a.SSASAAAAAaAAabAabab.SSASAAAAAAAaAbaabac.SSASAASAaSbaAbaabad. S SA Sa SAaSba Abaaba9、文法 G： Sb| (T)T T,S|Sd.b, ,),c.b, ,(, ，則 FIRSTVT(T) 。a.b, ,( b.b, ,)10、產(chǎn)生正規(guī)語(yǔ)言的文法為a.0 型b.1 型c.2型d.3 型11、采用自上而下分析，必須。a. 消除左遞歸b. 消除右遞歸12、在規(guī)范歸約中，用來(lái)

7、刻畫可歸約串。a. 直接短語(yǔ)b. 句柄13、有文法 G： EE*T|TTT+i|i句 1+2*8+6 按該文法 G 歸約，其值為 子c. 消除回溯 c.d. 提取公共左因子最左素短語(yǔ)d. 素短語(yǔ)a. 23 B.4214、規(guī)范歸約指a. 最左推導(dǎo)的逆過(guò)程c. 規(guī)范推導(dǎo) 解答 1、2、3、4、 f(a)>g)(b)或 f(a)<g(b) 并不能判定原來(lái)的 a 與 b 之間是否存在優(yōu)先關(guān)系：故選 c 。 如果文法 G 無(wú)二義性，則最左推導(dǎo)是先生長(zhǎng)右邊的枝葉：對(duì)于 則必然有二義性。故選a。選由c. 30d.17b. 最右推導(dǎo)的逆過(guò)程d. 最左歸約的逆過(guò)程c。a。c。選選選雖然 a與 b沒(méi)有

8、優(yōu)先關(guān)系，但構(gòu)造優(yōu)先函數(shù)后， a與 b就一定存在優(yōu)先關(guān)系了。所以，由5、 左推導(dǎo)，6、7、 圖d，如果有兩個(gè)不同的是了c。2-8-1選的語(yǔ)法樹(shù)和優(yōu)先關(guān)系可以看出應(yīng)b。#<· +·>+<· i ·># 圖 2-8-1 句型 P+T+I 的語(yǔ)法及優(yōu)先關(guān)系8、規(guī)范推導(dǎo)是最左推導(dǎo)，故選d。9、由 TT,和 T(, 得 FIRSTVT(T)=(, ，) ；由 TS 得 FIRSTVT(S) ?FIRSTVT(T) ，而 FIRSTVT(S)=b, ,( ；即FIRSTVT(T)=b, ,(, ， ； 10、d11、c12、 b 13、b二、

9、多項(xiàng)選擇題1、下面哪些說(shuō)法是錯(cuò)誤的。a. 有向圖是一個(gè)狀態(tài)轉(zhuǎn)換圖 c. 有向圖是一個(gè) DFA因此選 c14、bb. 狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖d.DFA 可以用狀態(tài)轉(zhuǎn)換圖表示2、對(duì)無(wú)二義性文法來(lái)說(shuō)，一棵語(yǔ)法樹(shù)往往代表了a. 多種推導(dǎo)過(guò)程b. 多種最左推導(dǎo)過(guò)程d. 僅一種推導(dǎo)過(guò)程e. 一種最左推導(dǎo)過(guò)程3、如果文法 G 存在一個(gè)句子，滿足下列條件c. 一種最左推導(dǎo)過(guò)程之一時(shí)，則稱該文法是二義文法a. 該句子的最左推導(dǎo)與最右推導(dǎo)相同b. 該句子有兩個(gè)不同的最左推導(dǎo)c. 該句子有兩棵不同的最右推導(dǎo)d. 該句子有兩棵不同的語(yǔ)法樹(shù)e. 該句子的語(yǔ)法樹(shù)只有一個(gè)4、有一文法 G： SABA aAb| B cBd|

10、 它不產(chǎn)生下面 集合。a.anbmcndm|n,m 0n m m n c.abcd|n,m 0 e.anbncndn|n 0b.anbncmdm|n,m >0nnmmd.abcd|n,m 05、自下而上的語(yǔ)法分析中，應(yīng)從開(kāi)始分析。a. 句型b. 句子d. 文法的開(kāi)始符e. 句柄c. 以單詞為單位的程序6、對(duì)正規(guī)文法描述的語(yǔ)言，以下有能力描述它a.0 型文法 b.1 型文法c. 上下文無(wú)關(guān)文法1、e、 a、c 2、 a、c、 e 3、b、c、d4、a、c5、三、填空題d. 右線性文法 e. 左線性文法b、c6、a、 b、c、 d、e1、文法中的終結(jié)符和非終結(jié)符的交集是是 ，它一定只出現(xiàn)在產(chǎn)

11、生式的 部詞法分析器交給語(yǔ)法分析器的文法符號(hào)一定2、最左推導(dǎo)是指每次都對(duì)句型中的 非終結(jié)符進(jìn)行擴(kuò)展。3 、在語(yǔ)法分析中，最常見(jiàn)的兩種方法一定是 分析法，另一是 分析法。4、采用 語(yǔ)法分析時(shí)，必須消除文法的左遞歸。5、 樹(shù)代表推導(dǎo)過(guò)程， 樹(shù)代表歸約過(guò)程。6、自下而上分析法采用 、歸約、錯(cuò)誤處理、等四種操作。7、Chomsky把文法分為種類型，編譯器構(gòu)造中采用 和 文法，它們分別產(chǎn)和 語(yǔ)言，并分別用 和 自動(dòng)機(jī)識(shí)別所產(chǎn)生的語(yǔ)言。1、空集終結(jié)符 右2、最左3、自上而上自下而上4、自上而上5、語(yǔ)法分析6、移進(jìn)接受7、42型3 型 上下文無(wú)關(guān)語(yǔ)言 正規(guī)語(yǔ)言下推自動(dòng)機(jī) 限四、判斷題1、文法 S aS|bR

12、| 描述的語(yǔ)言是 （a|bc）* （ ）RcS2、在自下而上的語(yǔ)法分析中，語(yǔ)法樹(shù)與分析樹(shù)一定相同。（）3、二義文法不是上下文無(wú)關(guān)文法。（）4、語(yǔ)法分析時(shí)必須先消除文法中的左遞歸。（）5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過(guò)程。（）6、一個(gè)文法所有句型的集合形成該文法所能接受的語(yǔ)言。（）解答 1、對(duì) 錯(cuò)2、錯(cuò)3、錯(cuò)4、錯(cuò)5、錯(cuò)6、五、簡(jiǎn)答題5、推導(dǎo)1、句柄2、素短語(yǔ)3、語(yǔ)法樹(shù)4、歸約 解答 1、句柄：一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄。2、素短語(yǔ)：至少含有一個(gè)終結(jié)符的素短語(yǔ)，并且除它自身之外不再含任何更小的素短語(yǔ)。 3、語(yǔ)法樹(shù)：滿足下面4個(gè)條件的樹(shù)稱之為文法GS 的一棵語(yǔ)法樹(shù)。每一終結(jié)均有一標(biāo)記

13、，此標(biāo)記為VN VT中的一個(gè)符號(hào)；樹(shù)的根結(jié)點(diǎn)以文法 GS 的開(kāi)始符 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, , ,X K，必然是 G的一個(gè)產(chǎn)生式。4、歸約：我們稱 直接歸約出 A，僅當(dāng) A是一個(gè)產(chǎn)生式，且 、 （VNVT）歸約過(guò)程就是從輸入串開(kāi)始，反復(fù)用產(chǎn)生式右部的符號(hào)替換成產(chǎn)生式左部符號(hào)，直至文法開(kāi) 始符。5、推導(dǎo)：我們稱 A 直接推出 ，即 A，僅當(dāng) A 是一個(gè)產(chǎn)生式，且 、 (VNVT)*。如果 12, n，則我們稱這個(gè)序列是

14、從 1至 2的一個(gè)推導(dǎo)。若存在一個(gè)從 1n 的推導(dǎo)，則稱 1可推導(dǎo)出 n。推導(dǎo)是歸約的逆過(guò)程。六、問(wèn)答題1、給出上下文無(wú)關(guān)文法的定義。 解答 一個(gè)上下文無(wú)關(guān)文法 G是一個(gè)四元式（ VT,V N,S,P ），其中： VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號(hào)；VN 是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號(hào)，VTVN=；S 是一個(gè)非終結(jié)符號(hào)，稱為開(kāi)始符號(hào)；P 是一個(gè)產(chǎn)生式集合（有限） ，每個(gè)產(chǎn)生式的形式是P，其中， PVN， （VTVN）*。開(kāi)始符號(hào) S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。2、文法 GS ：S aSPQ|abQQPPQ bPbb bQbc cQcc（ 1）它是 Chomsk

15、y 哪一型文法？ （ 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）按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低（否則無(wú)法推出句子），我們可以得到：S abQ abcS aSPQ aabQPQaabPQQaabbQQaabbcQaabbccS aSPQ aaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQ aaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc于是得到文法 GS 生成的

16、語(yǔ)言 L=a b c |n 13、按指定類型，給出語(yǔ)言的文法。L=a i bj |j >i 1 的上下文無(wú)關(guān)文法。解答】SaSb 型產(chǎn)生式， （1）由 L=aibj|j >i 1知，所求該語(yǔ)言對(duì)應(yīng)的上下文無(wú)關(guān)文法首先應(yīng)有以保證 b 的個(gè)數(shù)不少于 a 的個(gè)數(shù)；其次，還需有 SSb或 S bS型的產(chǎn)生式，用以保證b 的個(gè)數(shù)多于a 的個(gè)數(shù)；也即所求上下文無(wú)關(guān)文法 GS 為：GS：SaSb|Sb|b4、有文法 G： SaAcB|BdAAaB|cBbScA|b1）試求句型 aAaBcbbdcc 和 aAcbBdcc 的句柄； 2）寫出句子 acabcbbdcc 的最左推導(dǎo)過(guò)程?！窘獯稹浚?圖

17、 句柄 :AaB1）分別畫出對(duì)應(yīng)兩句型的語(yǔ)法樹(shù)，如a A c B2-8-2 所示B S c AAaB b S c Ab(a)(b)圖 2-8-2 語(yǔ)法樹(shù)2）句子 acabcbbdcc 的最左推導(dǎo)如下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcA acabcbbdcc5、對(duì)于文法 GS ：（1） 語(yǔ)。解答】S（ L）|aS|aL L,S|S畫出句型（ S, （a）的語(yǔ)法樹(shù)。（ 2）寫出上述句型的所有短語(yǔ)、直接短語(yǔ)、句柄和素短1）S 句型（ S, （a）的語(yǔ)法樹(shù)如圖 2-8-3 所示（ L ）L ， SS （L）（ 2）由圖 2-8-3

18、可知：短語(yǔ)： S、a、 （a） 、S,（a） 、（S,（a） ；直接短語(yǔ)： a、 S；圖 2-83 句柄： S；Sa句型（ S,（a）的語(yǔ)法樹(shù)素短語(yǔ)：素短語(yǔ)可由圖 2-8-3 中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即；#·（·，·（·a·）·）·#因此素短語(yǔ)為 a6、考慮文法 GT ：T T*F|FFFP|PP（ T）|i證明 T*P（ T*F）是該文法的一個(gè)句型，并指出直接短語(yǔ)和句柄解答】首先構(gòu)造 T*P（ T*F）的語(yǔ)法樹(shù)如圖 2-8-4 所示。由圖 2-8-4 可知， T*P（ T*F）是文法 GT 的一個(gè)句型。 直接短語(yǔ)有

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

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

21、) 2、a、b、dc.(ba)*bd.(ba) +b 解答 1、a、 c、e 三、填空題 確定有限自動(dòng)機(jī) DFA是 若二個(gè)正規(guī)式所表示的1、2、3、 由 解答 四、判斷題 一個(gè)有限狀態(tài)自動(dòng)機(jī)中，有且僅有一個(gè)唯一終態(tài)。 設(shè) r 和 s分別是正規(guī)式，則的一個(gè)特例。相同，則認(rèn)為二者是等價(jià)的。一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可1、NFA2、正規(guī)集所。3、DFA(NFA)所識(shí)別1、2、有3、4、5、6、7、式8、式解答1、 2、3、錯(cuò)五、基本題 1、設(shè) M( x,y,a,b,f,x,y f ( x,a )L( r|s ) =L(r)|L(s) 。 自動(dòng)機(jī) M和 M的狀態(tài)數(shù)不同，則二者必不等價(jià)。 確定的自動(dòng)機(jī)

22、以及不確定的自動(dòng)機(jī)都能正確地識(shí)別正規(guī)集。 對(duì)任意一個(gè)右線性文法 對(duì)任意一個(gè)右線性文法 對(duì)任何正規(guī)表達(dá)G，都存在一個(gè)G，都存在一個(gè)NFAM，滿足 L(G)=L(M)DFAM，滿足 L(G)=L(M)對(duì)任何正規(guī)表達(dá)都存NFAM，e，DFA5、6、)=L(e) 。e，都存4、滿足 L(G)=L(e) 。)f ( y,a )f (y,b ) x,y試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī) ,Mf,S 。0,Z) ，由f 的定義可知 f(x,a) 、 f(y,b) 均為多值函數(shù)，解答：對(duì)照自動(dòng)機(jī)的定義 M=(S,0以,Z是)一，非由a所確定有限自動(dòng)機(jī)，先畫出 NFAM)為一非確定的有限自動(dòng)機(jī)，其中 f 定義如下： x

23、,yf(x,b )yab X b Y b圖 3-6- NFAM2用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣3-6- 所示。表3IIIbaxx,yyyx,y,bx,y x,y x,y將轉(zhuǎn)換矩陣中的所有子集重新命名而形成表 3-6-4 所示的狀態(tài)轉(zhuǎn)換矩陣 表 3-6-4 狀態(tài)轉(zhuǎn)換矩陣ab02112即得到 M =( 0,1,2,a,b,f,0,1,2)，其狀態(tài)轉(zhuǎn)換圖如圖 3-6-5 所示令狀態(tài) 1 代表 1,2DFAM。2。最后，得到如圖將圖 3-6-5 的 DFAM最小化。首先，將M的狀態(tài)分成終態(tài)組 1 ，2 與非終態(tài)組 0 ；其次，考察 1,2 。由于 1,2a=1,2b=2?1,2 ，所以不再將其劃分了，也即整

24、個(gè)劃分只有兩 0 ，組 1,2 ： 3-6-6 所示化bb* ( d|ad )( b|ab )+，構(gòu)造其 NFA M；2、對(duì)給定正規(guī)式 + * * 解答：首先用 A+=AA* 改造正規(guī)式得： b*(d|ad)(b|ab)3-6-7 所示。構(gòu)造該正規(guī)式的NFAM，如圖(d|ad)(b|ab)b|a1 2 3 5圖 3-6-6 化簡(jiǎn)后的 DFAMa b a a6 d 7 b 8圖 3-6-7 的 NFAM1、構(gòu)造下面文法的LL（ 1）分析表DTLT int|realL idRR ,idR|解答： LL（ 1）分析表見(jiàn)表 4-3-1分析 雖然這個(gè)文法很簡(jiǎn)單，我們還是從求開(kāi)始符號(hào)集合和后繼符號(hào)集合開(kāi)始

25、。FIRSTFIRSTFIRSTD）=FIRST（T）L）=idR）=，, =int,realFOLLOWFO（ D） =FOLLOWLLOWFOLL（ T ） =id （ R） =#OWL）=#有了上面每個(gè)非終結(jié)符的 部不是件難事了。FIRST集合，填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右 的 FIRST（）就以 R 填在輸入符號(hào) #的欄目中。表 4-3-1LL（1）分析表非終結(jié)符輸入符號(hào)intid#lDDTLDTLFOLLOW（ R）中，所T realTintTLidRL是產(chǎn)生式填表時(shí)唯一要小心的時(shí)，R,idRR2、下面文法 GS 是否 為SAB|PQxLL（ 1）文法？說(shuō)明理由A xyB bcQ a

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

27、個(gè)非終結(jié)符U 的 FOLLOW 集的過(guò)程如下：因?yàn)椋?S 是識(shí)別符號(hào)，且有ABSD、BSAc、DSe，所以FOLLOW （S）應(yīng)包含F(xiàn)IRST(D) FIRST(Ac)FIRST(e) #=a,d a,d,c,e e #=a,c,d,e# 又因?yàn)?A BSD和 D，所以 FOLLOW 中還包含 FOLLOW(A) 。 因?yàn)?S aAbDe和 BSAc, 所以FOLLOW( A) =FIRST( bDe) FIRST( c ) =b,c 綜合、得 FOLLOW( S) =a,d,c,e,# a,b,c,d,e,#因?yàn)?ABSD，所以 FOLLOW(B) =FIRST(SD)=a,d 因?yàn)镾aAb

28、De|d、A BSD|e和 BSAc|cD，所以FOLLOW(D)=FIRST(e) FOLLOW( A) FOLLOW(B)=e b,c a,d=a,b,c,d,e( 2) GS 不是 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-2GS 的 LL（ 1）分析表abcde#SaAbDedABSDBSDBSDeBSac/ cDSac/ DSe/ Se/ 4、 將文法 GV 改造成為 LL(1) 的。GV ：

29、 VN|NEEV|V+ENi解答： 對(duì)文法 GV 提取公共左因子后得到文法：GV ：VNAA | EEVBB | +ENi求出文法 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)=# FIRST(B) FOLLOW(E)=#,+,FOLLOW(A)=FOLLOW(V)=+,#FOLLOW(E)=FIRST() FOLLOW(B)=FIRST() FOLLOW(E)=FOLLOW(B)=FOLLOW(E)=FOLLOW(N)

30、=FIRST(A) FOLLOW(V)=,+,#可以看到，對(duì)文法 G V 的產(chǎn)生式 A| E ，有FIRST(E) FOLLOW(A)= +,#=?對(duì)產(chǎn)生式 B| +E，有G V 是 LL(1) 文法FIRST（+E） FOLLOW（B）=+ =? 而文法的其他產(chǎn)生式都只有一個(gè)不為 的右部，所以文法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）

31、=#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#AA aaAAaaaa”的分析過(guò)程如表 4-3

32、-4 所示方法進(jìn)行語(yǔ)法分析，對(duì)符號(hào)串3）若采用 LL（1） “表 4-3-4 對(duì)符號(hào)串“ aaaa ”的分析過(guò)程步驟分析棧輸入串產(chǎn)生式 / 動(dòng)作1#Aaaaa#AaaA2#Aaaaaaa#匹配3#Aaaaa#匹配4#Aaa#AaaA5#Aaaaa#匹配6#Aaa#匹配7#A#A8#接受第七節(jié) 習(xí)題設(shè)有文法 GS 為：Sa|b|（A）ASdA|S1 ）完成下列算符優(yōu)先關(guān)系表，見(jiàn)表 5-7-1 ，并判斷 GS 是否為算符優(yōu)先文法。表 5-7-1 算符優(yōu)先關(guān)系表WORD格式ab()d#a?b?(?)?d#?（ 2 ）給出句型（ SdSdS）的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄、素短語(yǔ)和最左素短語(yǔ)。（ 3）給出輸入

33、串（ adb） #的分析過(guò)程。解答：(1)先求文法 GS 的 FIRSTVT集和 LASTVT集：由 S a|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,;由 A, dA得： LASTVT(A)=d, 又由 AS得： LASTVT(S)?構(gòu)造優(yōu)先關(guān)系表方法如下： 對(duì) P,ab, ，或 對(duì) P,aR, ，而 對(duì) P,Rb, ，而 由此得到：由 S（A） 得： （?）;P,aQb

34、, ，有 a?b; b FIRSTVT(R) ，有 a?b; a FIRSTVT(R) ，有 a?bLASTVT(A)，即LASTVT(A)=d,a,b,)專業(yè)資料整理由 S(A ,得：( ?FIRSTVT(A) ，即： (?d,( ?a,( ?b,( ?(; 由 A,dA得： d?FIRSTVT(A) 即： d?d,d ?a,d ?b,d ?(;由 SA)得， LASTVT(A)?) ，即： d?),a ?),b ?),) ?); 由 ASd,得： LASTVT(S)?d，即： a?d,b ?d,) ?d; 此外，由 #S#得： #?#；由#?FIRSTVT(S)得： #?a,# ?b,#

35、?(；脂由 LASTVT(S)?#得： d?#,a ?#,b ?#, ) ?#。最后得到算符優(yōu)先關(guān)系表，見(jiàn)表 5-7-2表 5-7-2算 算符符優(yōu)先關(guān)系表ab()d#?b?b(?() d?#?、?、?三種優(yōu)先關(guān)系之一，故GS為由表 5-7-2 可以看出，任何兩個(gè)終結(jié)符之間至少只滿 足 算符優(yōu)先文法。2）為求出句型（ SdSdS）的短語(yǔ)、簡(jiǎn)單短語(yǔ)、句柄，我們先畫出該句型對(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ǔ)WORD格

36、式專業(yè)資料整理3）輸入串（ adb） #的分析過(guò)程見(jiàn)表5-7-4表 5-74 輸入串（ adb） #的分析過(guò)程符號(hào)棧輸入串說(shuō)明#(adb)#移進(jìn)#（adb)#移進(jìn)#(adb)#用 S a 歸約#(Sdb)#移進(jìn)#(Sdb)#移進(jìn)#(Sdb)#用 S b 歸約#(SdS)#用 A S 歸約(#( SdA)#用 A S 歸約 用 A SdA歸約#(A)#用 歸約 移進(jìn)（#（A）)#移進(jìn)用 S（ A）歸約#(A)#S#用 S（ A）歸約分析成功第四節(jié) 習(xí)題、單項(xiàng)選擇題1、若 a 為終結(jié)符，則 A· a 為 項(xiàng)目a. 歸約 b. 移進(jìn)2、若項(xiàng)目集I k 含有 A·，則在狀態(tài)A

37、83;”動(dòng)作的一定是。c. 接受 d. 待約k 時(shí)，僅當(dāng)面臨的輸入符號(hào) a FOLLOW（A）時(shí)，才采取a. LALR 文法b.LR （0）文法3、就文法的描述能力來(lái)說(shuō)， 有。c.LR （1）文法d.SLR（1）文法a. SLR(1)?LR(0)b.LR4、在 LR( 0)的 ACTION1）?LR（0）c.SLR（1）?LR（1）子表中，如果某一行中存在標(biāo)記d.無(wú)二義文法 ?LR（1） r j ”的欄，則。a. 該行必定填滿rj b. 該行未填滿 rjc. 其他行也有 rj d.goto 子表中也有 rj5、一個(gè) 指明了在分析過(guò)程中的某時(shí)刻所能看到產(chǎn)生式多大一部分。a. 活前綴 b. 前綴

38、c. 項(xiàng)目 d. 項(xiàng)目集解答：1 、 A·稱為歸約項(xiàng)目，對(duì)文法開(kāi)始符 S的歸約項(xiàng)目，如 S·稱為接受項(xiàng)目， A· a （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)面臨的輸入符號(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 。 、多項(xiàng)選擇題1、一個(gè) LR 分析器包括a. 一個(gè)總控程序d

39、. 一張分析表b. 一個(gè)項(xiàng)目集 c. 一個(gè)活前綴e. 一個(gè)分析棧2、LR 分析器核心部分是一張分析表，該表包括等子表a.LL(1) 分析d.LRb. 優(yōu)先關(guān)系 c.GOTO e.ACTION3、每一項(xiàng) ACTIONS，a 所規(guī)定的動(dòng)作包括 c. 接 a. 移進(jìn) b. 比較 受4、對(duì) LR 分析表的構(gòu)造，有可能存在a. 移進(jìn) b. 歸約5、就文法的描述能力來(lái)說(shuō)，有a.SLR（1）?LR（1）d. LR（1）?無(wú)二義文法6、對(duì) LR 分析器來(lái)說(shuō)，存在a.LALRb.LR （0）7、自上而下的語(yǔ)法分析方法有a. 算符優(yōu)先分析法d. 歸約 動(dòng)作沖突。c. 移進(jìn) / 歸約 d. 移進(jìn) / 移進(jìn) 。b.

40、LR（1）?SLR（1）e. SLR（1）?無(wú)二義文法等分析表的構(gòu)造方法。c. SLR（ 1） d.SLR（0）。b. LL （ 1）分析法e. 報(bào)錯(cuò)e. 歸約 / 歸約c.LR（0）?LR（1）e.LR （ 1）c.SLR（1）分析法d. LR （0）分析法e. LALR（1）分析法解答：2、選c、e。3、選a、c、d、e。4、在LR分析表的構(gòu)造中有可能存在“移進(jìn)”5、選a、b、c、d、e。6、選a、b、c、e。7、選a、c、d、e。三、填空題1、一個(gè) LR 分析器包括一個(gè)總控程序和一張分析表，選a、 d。/ “歸約”和“歸約” / “歸約”沖突；故選 c、 e。使得它1、對(duì)于一個(gè)文法，如果

41、能夠構(gòu)造的 均是唯一確定的，則稱該文法為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·稱為項(xiàng)目；對(duì)文法開(kāi)始符 S·為項(xiàng)目；若 a 為終結(jié)符，則稱A·a為 項(xiàng)目；若 B 為非終結(jié)符，則稱A· a 為項(xiàng)目。、LR（0）分析法的名字中7 “L”表示，“ R”表示，“ 0 ”表示。解答：1、一張分析表每個(gè)入口2、任意首部3、規(guī)范句型句柄4、輸入串

42、活前綴5、活前綴 項(xiàng)目集合 LR 分析算法6、歸約 接受 移進(jìn) 待約7、自左至右分析采用最右推導(dǎo)的逆過(guò)程即最左歸約向右查看0 個(gè)字符四、綜合題1、對(duì)于文法GS ：S AS|bA SA|a（ 1）列出所有 LR（0）項(xiàng)目（ 2）列出構(gòu)成文法 LR（ 0）項(xiàng)目集規(guī)范族。 解答：首先將文法 G拓廣為 GS ：S SSAS|bASA|a（1）文法 GS 的 LR（0）項(xiàng)目是：1、S· S5、SAS·9、AS·A2、S S·6、S· b10、ASA·3、S· AS7、Sb·11、 A· a4、SA·S8、

43、A· SA12、Aa·2、列出構(gòu)成文法 LR（0）項(xiàng)目集規(guī)范族。用 -CLOSURE（閉包）辦法構(gòu)造文法I 0：1、S· SI 3：3、S· ASG的 LR 9、AS·A 8、A· SA 3、S· AS項(xiàng)目集規(guī)范族如下：I 6：12、 Aa·I 7： 7、S b·8、A· SA11、 A· a6、S·b6、S·b11、 A· a2、 S S·I 4 ： 10、ASA·9、AS·A4、SA·S8、A· SA3

44、、S· AS11、 A· a6、S·b3、S· AS8、A· SA6、S·b11、 A· a4、SA·SI 5： 5、SAS·3、S· AS9、AS·A6、S·b8、A· SA8、A· SA11、 A· a11、 A· a3、S· AS6、S· b注意： I1中的 S S·和 A· SA是由狀態(tài) I 0中的 1和 3讀入一個(gè) S字符后得到的下一個(gè)項(xiàng)目；，而I 4中的 ASA和AA·S則是

45、由 I3中的 9和 3讀入一個(gè) A字符后得到的下一個(gè)項(xiàng)目； I5中的 S AS·和 A S· A 則是由 I 4 中的 4 和 8 讀入一個(gè) S 字符后得到的下一個(gè)項(xiàng)目。狀態(tài) 全體構(gòu)成了文法 G的 LR( 0)規(guī)范族。第八節(jié) 習(xí)題、單項(xiàng)選擇題1、中間代碼生成所依據(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)表示。a.a+b/c+d4、表達(dá)式( A B) a. AB CD c.AB CDb.(a+b)/(c+d c.a+b/(c+d )( CD)的逆波蘭表示為b

46、.A BCD+ +d.A B CDd. 等價(jià)變換規(guī) 則d. 程序變量d.a+b+c/d5、中間代碼的樹(shù)型表A BC示a.A+B+C+D b.A+(B+C)+D6、四元式表示法的優(yōu)點(diǎn)為。a. 不便于優(yōu)化處理，但便于表的更 動(dòng)c. 便于優(yōu)化處理，也便于表的更動(dòng)7、終結(jié)符具有屬性。a. 傳遞b. 繼承解答1、選 c 。D 所對(duì)應(yīng)的表達(dá)式為 。d.(A+B)+(C+Dc. (A+B)+C+D )b. 不便于優(yōu)化處理，但節(jié)省存儲(chǔ)空 間d. 便于表的更動(dòng)，也節(jié)省存儲(chǔ)空 間c. 抽象d. 綜合2、四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的，故選b3 、選 b。4 、選 b。5、選 d。6、四元式表示法的優(yōu)點(diǎn)與間接三元式相同，故選c7、選 d。、多頂選擇題e間接三元式1、中間代碼主要有。a四元式b二元式c 三元式d后綴式2、下面中間代碼形式中，能正確表示算術(shù)表達(dá)式a+b+c 的有a ab+c+e a+b+c