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

1、第八節(jié) 習(xí)題一、單項(xiàng)選擇題1、將編譯程序分成若干個(gè)“遍”是為了 b 。 a提高程序的執(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)語言 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è)程序的意義。 a語義規(guī)則b詞

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

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

4、序（ 解釋不產(chǎn)生目標(biāo)程序，邊翻譯邊執(zhí)行 。2、編譯過程通?？煞譃?個(gè)階段，分別是 詞法分析 、語法分析 語義分析中間代碼生成 、代碼優(yōu)化和目標(biāo)代碼生成。3、編譯程序工作過程中，第一段輸入是 源程序 ，最后階段的輸出為 目標(biāo)程序 程序。4、編譯程序是指將 源程序 程序翻譯成 目標(biāo)程序 程序的程序。解答 是否生成目標(biāo)程序 2、詞法分析 中間代碼生成 3、源程序目標(biāo)代碼生成4、源程序 目標(biāo)語言一、單項(xiàng)選擇題1、文法G：SxSx|y所識(shí)別的語言是 c 。a. xyxb. (xyx)*c. xnyxn(n0)d. x*yx*（是指多個(gè)x）2、文法G描述的語言L(G)是指 ab 。a. L(G)=|S ,

5、 VT*b. L(G)=|S, VT*c. L(G)=|S,(VTVN*)d. L(G)=|S, (VTVN*)3、有限狀態(tài)自動(dòng)機(jī)能識(shí)別 。a. 上下文無關(guān)文法b. 上下文有關(guān)文法c.正規(guī)文法d. 短語文法4、設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對(duì)a、b有以下關(guān)系成立 。a. 若f(a)>g(b)，則a>bb.若f(a)<g(b)，則a<bc. ab都不一定成立d. ab一定成立5、如果文法G是無二義的，則它的任何句子 。a. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹必定相同b. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語法樹可能不同c. 最左推導(dǎo)和最右推導(dǎo)必定相同d. 可能存在兩個(gè)不同的最左推導(dǎo)

6、，但它們對(duì)應(yīng)的語法樹相同6、由文法的開始符經(jīng)0步或多步推導(dǎo)產(chǎn)生的文法符號(hào)序列是 。a. 短語b.句柄c. 句型d. 句子7、文法G：EE+T|TTT*P|PP(E)|I則句型P+T+i的句柄和最左素短語為 。a.P+T和ib. P和P+Tc. i和P+T+id.P和T 8、設(shè)文法為：SSA|AAa|b則對(duì)句子aba，下面 是規(guī)范推導(dǎo)。a. SÞSAÞSAAÞAAAÞaAAÞabAÞabab. SÞSAÞSAAÞAAAÞAAaÞAbaÞabac. SÞSAÞ

7、SAAÞSAaÞSbaÞAbaÞabad. SÞSAÞSaÞSAaÞSbaÞAbaÞaba9、文法G：Sb|(T)TT,S|S則FIRSTVT(T) 。a. b,(b. b,)c.b,(,，d.b,),，10、產(chǎn)生正規(guī)語言的文法為 。a. 0型b. 1型c. 2型d. 3型11、采用自上而下分析，必須 。a. 消除左遞歸b. 消除右遞歸c. 消除回溯d. 提取公共左因子12、在規(guī)范歸約中，用 來刻畫可歸約串。a. 直接短語b. 句柄c. 最左素短語d. 素短語13、有文法G：EE*T|T

8、0; TT+i|i句子1+2*8+6按該文法G歸約，其值為 。a. 23 B. 42 c. 30 d. 1714、規(guī)范歸約指 。a. 最左推導(dǎo)的逆過程b. 最右推導(dǎo)的逆過程c. 規(guī)范推導(dǎo) d. 最左歸約的逆過程解答 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。5、如果文法G無二義性，則最左推導(dǎo)是先生長(zhǎng)右邊的枝葉：對(duì)于d，如果有兩個(gè)不同的是了左推導(dǎo)，則必然有二義性。故選a。6、選c。7、由圖2-8-1的語法樹和優(yōu)先關(guān)

9、系可以看出應(yīng)選b。EE + FE + T PT iP #<·+·>+<·i·>#圖2-8-1 句型P+T+I的語法及優(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,(,，； 因此選c。 10、d 11、c 12、b 13、b 14、b二、多項(xiàng)選擇題1、下面哪些說法是錯(cuò)誤的 。a. 有向圖是一個(gè)狀態(tài)轉(zhuǎn)換圖b. 狀態(tài)轉(zhuǎn)換圖是一個(gè)有向圖c.有向圖是一個(gè)DFAd.DFA可以用狀態(tài)轉(zhuǎn)

10、換圖表示2、對(duì)無二義性文法來說，一棵語法樹往往代表了 。a. 多種推導(dǎo)過程b. 多種最左推導(dǎo)過程c.一種最左推導(dǎo)過程d.僅一種推導(dǎo)過程e.一種最左推導(dǎo)過程3、如果文法G存在一個(gè)句子，滿足下列條件 之一時(shí)，則稱該文法是二義文法。a. 該句子的最左推導(dǎo)與最右推導(dǎo)相同b. 該句子有兩個(gè)不同的最左推導(dǎo)c. 該句子有兩棵不同的最右推導(dǎo)d. 該句子有兩棵不同的語法樹 e.該句子的語法樹只有一個(gè)4、有一文法G：SAB AaAb| BcBd|它不產(chǎn)生下面 集合。a. anbmcndm|n,m0b. anbncmdm|n,m>0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbn

11、cndn|n05、自下而上的語法分析中，應(yīng)從 開始分析。a. 句型b. 句子c. 以單詞為單位的程序d. 文法的開始符e. 句柄6、對(duì)正規(guī)文法描述的語言，以下 有能力描述它。a.0型文法b.1型文法 c.上下文無關(guān)文法 d.右線性文法 e.左線性文法解答 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é)符和非終結(jié)符的交集是 。詞法分析器交給語法分析器的文法符號(hào)一定是 ，它一定只出現(xiàn)在產(chǎn)生式的 部。2、最左推導(dǎo)是指每次都對(duì)句型中的 非終結(jié)符進(jìn)行擴(kuò)展。3、在語法分析中，最常見的兩種方法一定是 分析法，另一是 分析法。4、采用

12、 語法分析時(shí)，必須消除文法的左遞歸。5、 樹代表推導(dǎo)過程， 樹代表歸約過程。6、自下而上分析法采用 、歸約、錯(cuò)誤處理、 等四種操作。 7、Chomsky把文法分為 種類型，編譯器構(gòu)造中采用 和 文法，它們分別產(chǎn)生 和 語言，并分別用 和 自動(dòng)機(jī)識(shí)別所產(chǎn)生的語言。解答 1、空集 終結(jié)符 右 2、最左 3、自上而上 自下而上 4、自上而上 5、語法 分析 6、移進(jìn) 接受 7、4 2 型 3型 上下文無關(guān)語言 正規(guī)語言 下推自動(dòng)機(jī) 有限四、判斷題1、文法 SaS|bR|描述的語言是(a|bc)* ( ) RcS2、在自下而上的語法分析中，語法樹與分析樹一定相同。 （ ）3、二義文法不是上下文無關(guān)文法

13、。 （ ）4、語法分析時(shí)必須先消除文法中的左遞歸。（ ）5、規(guī)范歸約和規(guī)范推導(dǎo)是互逆的兩個(gè)過程。（ ）6、一個(gè)文法所有句型的集合形成該文法所能接受的語言。（ ）解答 1、對(duì) 2、錯(cuò) 3、錯(cuò) 4、錯(cuò) 5、錯(cuò) 6、錯(cuò)五、簡(jiǎn)答題1、句柄2、素短語3、語法樹4、歸約5、推導(dǎo)解答 1、句柄：一個(gè)句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個(gè)終結(jié)符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面4個(gè)條件的樹稱之為文法GS的一棵語法樹。每一終結(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中

14、的一個(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)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)*。如果1Þ2ÞÞn，則我們稱這個(gè)序列是從1至2的一個(gè)推導(dǎo)。若存在一個(gè)從1n的推導(dǎo)，則稱1可推導(dǎo)出n。推導(dǎo)是歸約的逆過程。六、問答題1、給出上下文無關(guān)文法的定義。解答一個(gè)上下文

15、無關(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，(VTVN)*。開始符號(hào)S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。 2、文法GS： SaSPQ|abQ QPPQ bPbb bQbc cQcc（1）它是Chomsky哪一型文法？（2）它生成的語言是什么？解答 （1）由于產(chǎn)生式左部存在終結(jié)符號(hào)，且所有產(chǎn)生式左部符號(hào)的長(zhǎng)度均小于等于產(chǎn)生式右部的符號(hào)長(zhǎng)度，所以文法GS是Chomsky1型文法，即

16、上下文有關(guān)文法。（2）按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級(jí)由高到低（否則無法推出句子），我們可以得到： SÞabQÞabc SÞaSPQÞaabQPQÞaabPQQÞaabbQQÞaabbcQÞaabbcc SÞaSPQÞaaSPQPQÞaaabQPQPQÞaaabPQQPQÞaaabPQPQQÞaaaPPQQQÞaaabbPqqqÞaaabbQQQÞaaabbbcQQÞaaabbbccQÞaaabbbccc 于是

17、得到文法GS生成的語言L=anbncn|n13、按指定類型，給出語言的文法。L=aibj|ji1的上下文無關(guān)文法?！窘獯稹浚?）由L=aibj|ji1知，所求該語言對(duì)應(yīng)的上下文無關(guān)文法首先應(yīng)有SaSb型產(chǎn)生式，以保證b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次，還需有SSb或SbS型的產(chǎn)生式，用以保證b的個(gè)數(shù)多于a的個(gè)數(shù)；也即所求上下文無關(guān)文法GS為：GS：SaSb|Sb|b4、有文法G：SaAcB|Bd AAaB|c BbScA|b（1）試求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）寫出句子acabcbbdcc的最左推導(dǎo)過程?！窘獯稹浚?）分別畫出對(duì)應(yīng)兩句型的語法樹，如圖2

18、-8-2所示句柄:AaB Bd Sa   A   c   B  A  a  B b S c AB d cb(a)S a A c BB S c AB d  c(b)圖2-8-2 語法樹（2）句子acabcbbdcc的最左推導(dǎo)如下： SÞaAcBÞaAaBcBÞacaBcBÞacabcBÞacabcbScAÞacabcbBdcA ÞacabcbbdcAÞacabcbbdcc 5、對(duì)于文法GS： S（L）|aS|a LL, S|S（

19、1）畫出句型（S,（a）的語法樹。（2）寫出上述句型的所有短語、直接短語、句柄和素短語。S（ L ）L ， S S  ( L ) S a圖2-8-3 句型（S,（a）的語法樹【解答】（1）句型（S,（a）的語法樹如圖2-8-3所示（2）由圖2-8-3可知：短語：S、a、(a)、S,(a)、(S,(a)；直接短語：a、S；句柄：S；素短語：素短語可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即；# ·（·， ·（ ·a· ）· ）· #因此素短語為a。6、考慮文法GT：TT*F|FFF

20、P|PP（T）|i    T  T * F     F    P     P （   T    ）    T * F圖2-8-4 句型T*P（T*F）的語法樹證明T*P（T*F）是該文法的一個(gè)句型，并指出直接短語和句柄?！窘獯稹渴紫葮?gòu)造T*P（T*F）的語法樹如圖2-8-4所示。由圖2-8-4可知，T*P（T*F）是文法GT的一

21、個(gè)句型。直接短語有兩個(gè)，即P和T*F；句柄為P。一、單項(xiàng)選擇題1、詞法分析所依據(jù)的是 。a. 語義規(guī)則b. 構(gòu)詞規(guī)則c. 語法規(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í)別的語言集相等 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.

22、含奇數(shù)個(gè)0的二進(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è)過程，由語法分析器選擇使用 d. 詞法分析器并不作為一個(gè)獨(dú)立的階段解答 1、b 2、c 3、c 4、d 5、b二、多項(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(

23、a|b)解答 1、a、c、e 2、a、b、d三、填空題1、確定有限自動(dòng)機(jī)DFA是 的一個(gè)特例。2、若二個(gè)正規(guī)式所表示的 相同，則認(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、設(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

24、，都存在一個(gè)DFA M，滿足L(G)=L(M)。（ ）7、對(duì)任何正規(guī)表達(dá)式e，都存在一個(gè)NFA M，滿足L(G)=L(e)。（ ）8、對(duì)任何正規(guī)表達(dá)式e，都存在一個(gè)DFA M，滿足L(G)=L(e)。（ ）解答 1 、2、3、錯(cuò) 4、5、6、7、8、正確五、基本題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。解答：對(duì)照自動(dòng)機(jī)的定義M=(S,f,S0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，所以是一非確定有限自動(dòng)機(jī)，先畫出NFA M相應(yīng)的狀態(tài)圖

25、，如圖3-6-2所示。 a a b b b圖3-6-2 NFA MXY用子集法構(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)組1，2與非終態(tài)組0；其次，考察1,2。由于1,2a=1,2b=21,2，所以不

26、再將其劃分了，也即整個(gè)劃分只有兩組0，1,2：令狀態(tài)1代表1,2，即把原來到達(dá)2的弧都導(dǎo)向1，并刪除狀態(tài)2。最后，得到如圖3-6-6所示化簡(jiǎn)DFA M。2、對(duì)給定正規(guī)式b*（d|ad）（b|ab）+，構(gòu)造其NFA M； aadb*b*(d|ad)(b|ab)(b|ab)*XYX123YX4135Y678(d|ad)(b|ab)(b|ab)*2dbadabb|abbX4135Y2bdbbabb圖3-6-7 的NFA M解答：首先用A+=AA*改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*；其次，構(gòu)造該正規(guī)式的NFA M，如圖3-6-7所示。1、 構(gòu)造下面文法的LL（1）分析表。D TL

27、T int | realL id RR , id R | 解答： 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)#的欄目中。表4-3-1 LL（1）分析表

28、非終結(jié)符輸入符號(hào)int realid，#DDTLDTLTTintTrealLLid RRR,id RR 2、 下面文法GS是否為L(zhǎng)L（1）文法？說明理由。S  A B | P Q x A  x y B  b cP  d P | Q  a Q | 解答： 該文法不是LL（1）文法，見下面分析中的說明。分析 只有三個(gè)非終結(jié)符有兩個(gè)選擇。 1、P的兩個(gè)右部d P 和 的開始符號(hào)肯定不相交。2、Q的兩個(gè)右部a Q 和 的開始符號(hào)肯定不相交。3、對(duì)S來說，由于x FIRST(A B)，同時(shí)也有x FIRST(P Q x)（因?yàn)镻和Q都可能為空）。所以該文

29、法不是LL（1）文法。3、 設(shè)有以下文法： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| （1）求出該文法的每一個(gè)非終結(jié)符U的FOLLOW集。（2）該文法是LL（1）文法嗎？（3）構(gòu)造CS的LL（1）分析表。解答： （1）求文法的每一個(gè)非終結(jié)符U的FOLLOW集的過程如下：因?yàn)椋?S是識(shí)別符號(hào)，且有ABSD、BSAc、DSe，所以FOLLOW（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）=FI

30、RST（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不是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所示。表

31、4-3-2 GS的LL（1）分析表abcde#SaAbDedABSDBSDBSDeBSac/cDSac/DSe/Se/4、 將文法GV改造成為L(zhǎng)L(1)的。 GV：VN|NE EV|V+E Ni解答： 對(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)的FOLLOW集：FOLLOW(V)=#FIRST(B)FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLL

32、OW(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、已知文法：GA：AaAa|（1）該文法是LL（1）文法嗎？為什么？（2）若采用LL（1）方法進(jìn)行語法分析，如何得到該文法的LL（1）分析表？（3）若輸入符號(hào)串“

33、aaaa”，請(qǐng)給出語法分析過程。解答：（1）因?yàn)楫a(chǎn)生式AaAa| 有空產(chǎn)生式右部，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #Ø所以該文法不是LL（1）文法。（2）若采用LL（1）方法進(jìn)行語法分析，必須修改該文法。因該文法產(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

34、-3 文法GA的LL(1)分析表A#AAaaAA（3）若采用LL(1)方法進(jìn)行語法分析，對(duì)符號(hào)串“aaaa”的分析過程如表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#接受第七節(jié) 習(xí)題設(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）給出句型（S

35、dSdS）的短語、簡(jiǎn)單短語、句柄、素短語和最左素短語。（3）給出輸入串（adb）#的分析過程。解答： （1）先求文法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，而b

36、FIRSTVT(R)，有ab; 對(duì)PRb，而aFIRSTVT(R)，有ab。由此得到： 由S(A)得：(); 由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è)終

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

38、)#用Sb歸約#（SdS)#用AS歸約#（SdA)#用ASdA歸約#（A)#移進(jìn)#（A）#用S（A）歸約#S#分析成功第四節(jié) 習(xí)題一、單項(xiàng)選擇題1、若a為終結(jié)符，則A·a為 項(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、就文法的描述能力來說，有 。 a. SLR（1）LR（0） b. LR（1）LR（0）c. SLR（1）LR（1）d.無二義文法LR（1）4、在LR（0）的ACTION

39、子表中，如果某一行中存在標(biāo)記“rj”的欄，則 。 a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個(gè) 指明了在分析過程中的某時(shí)刻所能看到產(chǎn)生式多大一部分。 a.活前綴b.前綴c.項(xiàng)目d.項(xiàng)目集解答： 1、A·稱為歸約項(xiàng)目，對(duì)文法開始符S的歸約項(xiàng)目，如S·稱為接受項(xiàng)目，A·a（a為終結(jié)符）稱為移進(jìn)項(xiàng)目。在此選b.2、當(dāng)用產(chǎn)生式A歸約時(shí)，LR（0）無論面臨什么輸入符號(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)行歸約；因此

40、選d。3、由于LR（0）SLR（1） LR（1）無二義文法，故選c。4、選a。5、選c。二、多項(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、就文法的描述能力來說，有 。 a. SLR（1）LR（1）b. LR（1）SL

41、R（1）c. LR（0）LR（1）d. LR（1）無二義文法 e. SLR（1）無二義文法6、對(duì)LR分析器來說，存在 等分析表的構(gòu)造方法。 a.LALRb.LR（0）c.SLR（1）d.SLR（0）e.LR（1）7、自上而下的語法分析方法有 。 a.算符優(yōu)先分析法b.LL（1）分析法c.SLR（1）分析法d.LR（0）分析法e.LALR（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、e。6、選a、b、c、e。7、選a、

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

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

44、、SA·S8、A·SA12、Aa·2、列出構(gòu)成文法LR（0）項(xiàng)目集規(guī)范族。用-CLOSURE（閉包）辦法構(gòu)造文法G的LR（0）項(xiàng)目集規(guī)范族如下：I0：1、S·S I3：9、AS·AI6：12、Aa· 3、S·AS8、A·SAI7：7、Sb· 8、A·SA3、S·AS 11、A·a6、S·b 6、S·b11、A·aI1：2、SS·I4：10、ASA· 9、AS·A4、SA·S8、A·SA3、S

45、83;AS11、A·a6、S·b3、S·AS8、A·SA6、S·b 11、A·aI2：4、SA·SI5：5、SAS· 3、S·AS9、AS·A6、S·b8、A·SA 8、A·SA11、A·a 11、A·a3、S·AS6、S·b注意：I1中的SS·和A·SA是由狀態(tài)I0中的1和3讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目；，而I4中的ASA和AA·S則是由I3中的9和3讀入一個(gè)A字符后得到的下一個(gè)項(xiàng)目；I5中的SAS·和AS·A則是由I4中的4和8讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目。狀態(tài)全體構(gòu)成了文法G的LR（0）規(guī)范族。第八節(jié) 習(xí)題一、單項(xiàng)選擇題1、中間代碼生