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

1、第一章1、將編譯程序分成假設(shè)干個“遍是為了 。 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)語言 c編譯方法d以上三項都是3、變量應(yīng)當(dāng) 。 a持有左值b持有右值 c既持有左值又持有右值d既不持有左值也不持有右值 4、編譯程序絕大多數(shù)時間花在 上。 a出錯處理b詞法分析 c目標(biāo)代碼生成d管理表格5、 不可能是目標(biāo)代碼。 a匯編指令代碼b可重定位指令代碼 c絕對指令代碼d中間代碼6、使用 可以定義一個程序的意義。 a語義規(guī)那么b語法規(guī)那么 c產(chǎn)生規(guī)那么d詞法規(guī)那么7、詞法

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

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

4、并且語義規(guī)那么可以定義一個程序的意義。因此選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)語言第二章一、單項選擇題1、文法G：SxSx|y所識別的語言是 。a. xyxb. (xyx)*c. xnyxn(n0)d. x*yx*2、文法G描述的語言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)自動機(jī)能識別 。a. 上下文無關(guān)文法b. 上下文有關(guān)文法c.正

5、規(guī)文法d. 短語文法4、設(shè)G為算符優(yōu)先文法，G的任意終結(jié)符對a、b有以下關(guān)系成立 。a. 假設(shè)f(a)>g(b)，那么a>bb.假設(shè)f(a)<g(b)，那么a<bc. ab都不一定成立d. ab一定成立5、如果文法G是無二義的，那么它的任何句子 。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)0步或多步推導(dǎo)產(chǎn)生的文法符號序列是 。a. 短語b.句柄c. 句型d. 句子7、文法G：EE+T|TTT*P|PP(E)|I那么句型

6、P+T+i的句柄和最左素短語為 。a.P+T和ib. P和P+Tc. i和P+T+id.P和T 8、設(shè)文法為：SSA|AAa|b那么對句子aba，下面 是標(biāo)準(zhǔn)推導(dǎo)。a. SÞSAÞSAAÞAAAÞaAAÞabAÞabab. SÞSAÞSAAÞAAAÞAAaÞAbaÞabac. SÞSAÞSAAÞSAaÞSbaÞAbaÞabad. SÞSAÞSaÞSAaÞSbaÞAba

7、Þ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、在標(biāo)準(zhǔn)歸約中，用 來刻畫可歸約串。a. 直接短語b. 句柄c. 最左素短語d. 素短語13、有文法G：EE*T|T  TT+i|i句子1+2*8+6按該文法G歸約，其值為 。a. 23 B. 42 c. 30 d. 1714、標(biāo)準(zhǔn)歸約指 。a. 最左推導(dǎo)的逆過程b. 最右

8、推導(dǎo)的逆過程c. 標(biāo)準(zhǔn)推導(dǎo) d. 最左歸約的逆過程二、多項選擇題1、下面哪些說法是錯誤的 。a. 有向圖是一個狀態(tài)轉(zhuǎn)換圖b. 狀態(tài)轉(zhuǎn)換圖是一個有向圖c.有向圖是一個DFAd.DFA可以用狀態(tài)轉(zhuǎn)換圖表示2、對無二義性文法來說，一棵語法樹往往代表了 。a. 多種推導(dǎo)過程b. 多種最左推導(dǎo)過程c.一種最左推導(dǎo)過程d.僅一種推導(dǎo)過程e.一種最左推導(dǎo)過程3、如果文法G存在一個句子，滿足以下條件 之一時，那么稱該文法是二義文法。a. 該句子的最左推導(dǎo)與最右推導(dǎo)相同b. 該句子有兩個不同的最左推導(dǎo)c. 該句子有兩棵不同的最右推導(dǎo)d. 該句子有兩棵不同的語法樹 e.該句子的語法樹只有一個4、有一文法G：SAB

9、 AaAb| BcBd|它不產(chǎn)生下面 集合。a. anbmcndm|n,m0b. anbncmdm|n,m>0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbncndn|n05、自下而上的語法分析中，應(yīng)從 開始分析。a. 句型b. 句子c. 以單詞為單位的程序d. 文法的開始符e. 句柄6、對正規(guī)文法描述的語言，以下 有能力描述它。a.0型文法b.1型文法 c.上下文無關(guān)文法 d.右線性文法 e.左線性文法 三、填空題1、文法中的終結(jié)符和非終結(jié)符的交集是 。詞法分析器交給語法分析器的文法符號一定是 ，它一定只出現(xiàn)在產(chǎn)生式的 部。2、最左推導(dǎo)是指每次都對句型中的

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

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

12、語法樹。2寫出上述句型的所有短語、直接短語、句柄和素短語。6、考慮文法GT：TT*F|FFFP|PPT|i證明T*PT*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)系：應(yīng)選c。EE + FE + T PT iP #<·+·>+<·i·>#圖2-8-1 句型P+T+I的語法及優(yōu)先關(guān)系5、如果文法G無二義性，那么最左推導(dǎo)

13、是先生長右邊的枝葉：對于d，如果有兩個不同的是了左推導(dǎo)，那么必然有二義性。應(yīng)選a。6、選c。7、由圖2-8-1的語法樹和優(yōu)先關(guān)系可以看出應(yīng)選b。8、標(biāo)準(zhǔn)推導(dǎo)是最左推導(dǎo)，應(yīng)選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、自上而上

14、 5、語法 分析 6、移進(jìn) 接受 7、4 2 型 3型 上下文無關(guān)語言 正規(guī)語言 下推自動機(jī) 有限判斷解答 1、對 2、錯 3、錯 4、錯 5、錯 6、錯 簡答解答 1、句柄：一個句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個終結(jié)符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面4個條件的樹稱之為文法GS的一棵語法樹。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VNVT中的一個符號；樹的根結(jié)點(diǎn)以文法GS的開始符S標(biāo)記；假設(shè)一結(jié)點(diǎn)至少有一個直接后繼，那么此結(jié)點(diǎn)上的標(biāo)記為VN中的一個符號；假設(shè)一個以A為標(biāo)記的結(jié)點(diǎn)有K個直接后繼，且按從左至右的順序，這些結(jié)點(diǎn)的標(biāo)記分別為X1,X2

15、,XK，那么AX1,X2,XK，必然是G的一個產(chǎn)生式。4、歸約：我們稱直接歸約出A，僅當(dāng)A 是一個產(chǎn)生式，且、(VNVT)*。歸約過程就是從輸入串開始，反復(fù)用產(chǎn)生式右部的符號替換成產(chǎn)生式左部符號，直至文法開始符。5、推導(dǎo)：我們稱A直接推出，即AÞ，僅當(dāng)A 是一個產(chǎn)生式，且、(VNVT)*。如果1Þ2ÞÞn，那么我們稱這個序列是從1至2的一個推導(dǎo)。假設(shè)存在一個從1n的推導(dǎo)，那么稱1可推導(dǎo)出n。推導(dǎo)是歸約的逆過程。 問答1解答一個上下文無關(guān)文法G是一個四元式VT,VN,S, P，其中：VT是一個非空有限集，它的每個元素稱為終結(jié)符號；VN是一個非空有限集，它的

16、每個元素稱為非終結(jié)符號，VTVN=；S是一個非終結(jié)符號，稱為開始符號；P是一個產(chǎn)生式集合有限，每個產(chǎn)生式的形式是P，其中，PVN，(VTVN)*。開始符號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Þabc SÞaSPQÞaabQPQÞaabPQQÞaabbQQÞaabbcQÞaabbc

17、c SÞaSPQÞaaSPQPQÞaaabQPQPQÞaaabPQQPQÞaaabPQPQQÞaaaPPQQQÞaaabbPqqqÞaaabbQQQÞaaabbbcQQÞaaabbbccQÞaaabbbccc 于是得到文法GS生成的語言L=anbncn|n13【解答】1由L=aibj|ji1知，所求該語言對應(yīng)的上下文無關(guān)文法首先應(yīng)有SaSb型產(chǎn)生式，以保證b的個數(shù)不少于a的個數(shù)；其次，還需有SSb或SbS型的產(chǎn)生式，用以保證b的個數(shù)多于a的個數(shù)；也即所求上下文無關(guān)文法GS為：GS：Sa

18、Sb|Sb|b4【解答】1分別畫出對應(yīng)兩句型的語法樹，如圖2-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

19、S L L ， S S  ( L ) S a圖2-8-3 句型S,a的語法樹5【解答】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。    T  T * F     F &#

20、160;  P     P   T        T * F圖2-8-4 句型T*PT*F的語法樹6【解答】首先構(gòu)造T*PT*F的語法樹如圖2-8-4所示。由圖2-8-4可知，T*PT*F是文法GT的一個句型。直接短語有兩個，即P和T*F；句柄為P。第三章一、單項選擇題1、詞法分析所依據(jù)的是 。a. 語義規(guī)那么b. 構(gòu)詞規(guī)那么c. 語法規(guī)那么d. 等價變換規(guī)那么2、詞法分析器的輸出結(jié)果是 。a. 單詞的種別編碼b. 單詞在符號表中的位置c. 單詞

21、的種別編碼和自身值d. 單詞自身值3、正規(guī)式M1和M2等價是指 。a. M1和M2的狀態(tài)數(shù)相等b. M1和M2的有向弧條數(shù)相等c. M1和M2所識別的語言集相等 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ù)個0的二進(jìn)制數(shù)組成的集合 d. 含偶數(shù)個0的二進(jìn)制數(shù)組成的集合5、詞法分析器作為獨(dú)立的階段使整個編譯程序結(jié)構(gòu)更加簡潔、明確，因此， 。a. 詞法分析器應(yīng)作為獨(dú)立的一遍 b. 詞法分析器作為子程序較好c. 詞法分析器分解為多個過程，由

22、語法分析器選擇使用 d. 詞法分析器并不作為一個獨(dú)立的階段二、多項選擇題1、在詞法分析中，能識別出 。a. 根本字b. 四元式c. 運(yùn)算符d. 逆波蘭式e. 常數(shù)2、令=a,b，那么上所有以b開頭，后跟假設(shè)干個ab的字的全體對應(yīng)的正規(guī)式為 。a. b(ab)*b. b(ab)+c.(ba)*bd. (ba)+be. b(a|b)三、填空題1、確定有限自動機(jī)DFA是 的一個特例。2、假設(shè)二個正規(guī)式所表示的 相同，那么認(rèn)為二者是等價的。3、一個字集是正規(guī)的，當(dāng)且僅當(dāng)它可由 所 。四、判斷題1、一個有限狀態(tài)自動機(jī)中，有且僅有一個唯一終態(tài)。 2、設(shè)r和s分別是正規(guī)式，那么有Lr|s=L(r)|L(s)

23、。 3、自動機(jī)M和M的狀態(tài)數(shù)不同，那么二者必不等價。 4、確定的自動機(jī)以及不確定的自動機(jī)都能正確地識別正規(guī)集。 5、對任意一個右線性文法G，都存在一個NFA M，滿足L(G)=L(M)。 6、對任意一個右線性文法G，都存在一個DFA M，滿足L(G)=L(M)。 7、對任何正規(guī)表達(dá)式e，都存在一個NFA M，滿足L(G)=L(e)。 8、對任何正規(guī)表達(dá)式e，都存在一個DFA M，滿足L(G)=L(e)。 五、基此題1、設(shè)Mx,y, a,b, f,x,y為一非確定的有限自動機(jī)，其中f定義如下：fx,ax,y fx,byfy,a fy,bx,y 試構(gòu)造相應(yīng)確實定有限自動機(jī)M。2、對給定正規(guī)式b*d

24、|adb|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、DFANFA所識別判斷解答 1 、2、3、錯 4、5、6、7、8、正確 a a b b b圖3-6-2 NFA MXY根本1解答：對照自動機(jī)的定義M=(S,f,S0,Z)，由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，所以是一非確定有限自動機(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)換矩陣中的所有子集重新命名而形成表

25、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 化簡后的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，所以不再將其劃分了，也即整個劃分只有兩組0，1,2：令狀態(tài)1代表1,2，即把原來到達(dá)2的弧都導(dǎo)向1，并刪除狀態(tài)2。最后，得到如圖3-6-6所示化簡DFA M。aadb*b*(d|ad)(b|ab)(b|ab

26、)*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)造下面文法的LL1分析表。D TLT int | realL id RR , id R | 2、 下面文法GS是否為LL1文法？說明理由。S  A B | P Q x A  x y B  b cP  d P | Q  a Q | 3、 設(shè)有以下文法

27、： GS：SaAbDe|d ABSD|e BSAc| cD| DSe| 1求出該文法的每一個非終結(jié)符U的FOLLOW集。2該文法是LL1文法嗎？3構(gòu)造CS的LL1分析表。4、 將文法GV改造成為LL(1)的。 GV：VN|NE EV|V+E Ni5、文法：GA：AaAa|1該文法是LL1文法嗎？為什么？2假設(shè)采用LL1方法進(jìn)行語法分析，如何得到該文法的LL1分析表？3假設(shè)輸入符號串“aaaa，請給出語法分析過程。1解答： LL1分析表見表4-3-1分析 雖然這個文法很簡單，我們還是從求開始符號集合和后繼符號集合開始。 FIRSTD=FIRSTT=int, real FOLLOWD=FOLLOW

28、L=#FIRSTL=id FOLLOWT=idFIRSTR=，, FOLLOWR=#有了上面每個非終結(jié)符的FIRST集合，填分析表時要計算一個產(chǎn)生式右部的FIRST就不是件難事了。填表時唯一要小心的時，是產(chǎn)生式R右部的一個開始符號，而#在FOLLOWR中，所以R填在輸入符號#的欄目中。表4-3-1 LL1分析表非終結(jié)符輸入符號int realid，#DDTLDTLTTintTrealLLid RRR,id RR 2解答： 該文法不是LL1文法，見下面分析中的說明。分析 只有三個非終結(jié)符有兩個選擇。 1、P的兩個右部d P 和 的開始符號肯定不相交。2、Q的兩個右部a Q 和 的開始符號肯定不相

29、交。3、對S來說，由于x FIRST(A B)，同時也有x FIRST(P Q x)因為P和Q都可能為空。所以該文法不是LL1文法。3解答： 1求文法的每一個非終結(jié)符U的FOLLOW集的過程如下：因為： S是識別符號，且有ABSD、BSAc、DSe，所以FOLLOWS應(yīng)包含F(xiàn)IRST(D)FIRST(Ac) FIRST(e) #=a,da,d,c,ee#=a,c,d,e# 又因為ABSD和D，所以FOLLOW中還包含F(xiàn)OLLOW(A)。因為SaAbDe和BSAc,所以FOLLOWA=FIRSTbDeFIRSTc=b,c綜合、得FOLLOWS=a,d,c,e,#a,b,c,d,e,#因為ABSD

30、，所以 FOLLOWB=FIRSTSD=a,d 因為SaAbDe | d、ABSD| e和BSAc | cD，所以FOLLOWD=FIRSTeFOLLOWAFOLLOWB  =eb,ca,d=a,b,c,d,e2GS不是LL1文法。因為產(chǎn)生式BSAc|cD| 中 FIRSTSAcFOLLOWB=a,dØ3構(gòu)造GS的LL1分析表。按照LL1分析表的構(gòu)造算法構(gòu)造方法GS的LL1分析表如表4-3-2所示。表4-3-2 GS的LL1分析表abcde#SaAbDedABSDBSDBSDeBSac/cDSac/DSe/Se/4解答： 對文法GV提取公共左因子后得到文法： GV：VNAA

31、|EEVBB|+ENi求出文法GV中每一個非終結(jié)符號的FIRST集： FIRST(V)=iFIRST(A)=, FIRST(E)=iFIRST(B)=+, FIRST(N)=i求出文法GV中每一個非終結(jié)符號的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)=,+,#可以看到，對文法GV的產(chǎn)生式A|E，有FIRST(E)FOL

32、LOW(A)=+,#= Ø對產(chǎn)生式B|+E，有FIRST(+E)FOLLOW(B)=+= Ø而文法的其他產(chǎn)生式都只有一個不為的右部，所以文法GV是LL(1)文法。5解答：1因為產(chǎn)生式AaAa| 有空產(chǎn)生式右部，而 FOLLOW(A)=#FIRST(a)=a, #造成 FIRST(A)FOLLOW(A)=A, a, #Ø所以該文法不是LL1文法。2假設(shè)采用LL1方法進(jìn)行語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)可以為0個a，所以得到文法GA：AaaA|此時對產(chǎn)生式AaaA|， 有 FOLLOW(A)=#FOLLOW(A)=#，因而FIRST(A)FOLLOW(A)=

33、a, #=Ø所以文法GA是LL1文法，按LL1分析表構(gòu)造算法構(gòu)造該文法的LL1分析表如表4-3-3所示。表4-3-3 文法GA的LL(1)分析表A#AAaaAA3假設(shè)采用LL(1)方法進(jìn)行語法分析，對符號串“aaaa的分析過程如表4-3-4所示。 表4-3-4對符號串“aaaa的分析過程步驟分析棧輸入串產(chǎn)生式/動作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)系表，見表

34、5-7-1，并判斷GS是否為算符優(yōu)先文法。表5-7-1 算符優(yōu)先關(guān)系表ab()d#ab()d# 2給出句型SdSdS的短語、簡單短語、句柄、素短語和最左素短語。3給出輸入串a(chǎn)db#的分析過程。解答： 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(

35、A)=d,a,b,)。構(gòu)造優(yōu)先關(guān)系表方法如下： 對Pab，或PaQb，有ab; 對PaR，而bFIRSTVT(R)，有ab; 對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-

36、7-2。表5-7-2 算符優(yōu)先關(guān)系表ab()d#ab()d#由表5-7-2可以看出，任何兩個終結(jié)符之間至少只滿足、三種優(yōu)先關(guān)系之一，故GS為算符優(yōu)先文法。SASASdASd圖5-7-3 句型SdSdS的語法樹2為求出句型SdSdS的短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹，如圖5-7-3所示。由圖5-7-3得到：短語：S，SdS，SdSdS，SdSdS簡單短語即直接短語：S句柄即最左直接短語：S素短語：SdS，它同時也是該句型的最左素短語。3輸入串a(chǎn)db#的分析過程見表5-7-4表5-7-4 輸入串a(chǎn)db#的分析過程符號棧輸入串說明#(adb)#移進(jìn)#adb)#移進(jìn)#adb)#用Sa

37、歸約#Sdb)#移進(jìn)#Sdb)#移進(jìn)#Sdb)#用Sb歸約#SdS)#用AS歸約#SdA)#用ASdA歸約#A)#移進(jìn)#A#用SA歸約#S#分析成功第六章一、單項選擇題1、假設(shè)a為終結(jié)符，那么A·a為 工程 a.歸約b.移進(jìn)c.接受d.待約2、假設(shè)工程集Ik含有A·，那么在狀態(tài)k時，僅當(dāng)面臨的輸入符號aFOLLOW(A)時，才采取“A·動作的一定是 。 a.LALR文法b.LR0文法c.LR1文法d.SLR1文法3、就文法的描述能力來說，有 。 a. SLR1LR0 b. LR1LR0c. SLR1LR1d.無二義文法LR14、在LR0的ACTION子表中，如果某

38、一行中存在標(biāo)記“rj的欄，那么 。 a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個 指明了在分析過程中的某時刻所能看到產(chǎn)生式多大一局部。 a.活前綴b.前綴c.工程d.工程集二、多項選擇題1、一個LR分析器包括 。 a.一個總控程序b.一個工程集c.一個活前綴d.一張分析表e.一個分析棧2、LR分析器核心局部是一張分析表，該表包括 等子表。 a.LL(1)分析b.優(yōu)先關(guān)系c.GOTO d.LRe.ACTION3、每一項ACTIONS，a所規(guī)定的動作包括 。a.移進(jìn)b.比擬c.接受d.歸約e.報錯4、對LR分析表的構(gòu)造，有可能存在 動作沖突。a.移進(jìn)b

39、.歸約c.移進(jìn)/歸約d.移進(jìn)/移進(jìn)e.歸約/歸約5、就文法的描述能力來說，有 。 a. SLR1LR1b. LR1SLR1c. LR0LR1d. LR1無二義文法 e. SLR1無二義文法6、對LR分析器來說，存在 等分析表的構(gòu)造方法。 a.LALRb.LR0c.SLR1d.SLR0e.LR17、自上而下的語法分析方法有 。 a.算符優(yōu)先分析法b.LL1分析法c.SLR1分析法d.LR0分析法e.LALR1分析法三、填空題1、對于一個文法，如果能夠構(gòu)造 。使得它的 均是唯一確定的，那么稱該文法為LR文法。2、字的前綴是指該字的 。3、活前綴是指 的一個前綴，這種前綴不含 之后的任何符號。4、在

40、LR分析過程中，只要 的已掃描局部保持可歸約成一個 ，那么掃描過的局部正確。5、將識別 的NFA確定化，使其成為以 為狀態(tài)的DFA，這個DFA就是建立 的根底。6、A·稱為 工程；對文法開始符S·為 工程；假設(shè)a為終結(jié)符，那么稱A·a為 工程；假設(shè)B為非終結(jié)符，那么稱A·a為 工程。 7、LR0分析法的名字中“L表示 ，“R表示 ，“0表示 。四、綜合題1、對于文法GS： SAS|b ASA|a 1列出所有LR0工程2列出構(gòu)成文法LR0工程集標(biāo)準(zhǔn)族。單項解答： 1、A·稱為歸約工程，對文法開始符S的歸約工程，如S·稱為接受工程，A&#

41、183;aa為終結(jié)符稱為移進(jìn)工程。在此選b.2、當(dāng)用產(chǎn)生式A歸約時，LR0無論面臨什么輸入符號都進(jìn)行歸約；SLR1那么僅當(dāng)面臨的輸入符號aFOLLOW(A)時進(jìn)行歸約；LR1那么當(dāng)在把歸約為A的標(biāo)準(zhǔn)句型的前綴Aa前提下，當(dāng)后跟終結(jié)符a時，才進(jìn)行歸約；因此選d。3、由于LR0SLR1 LR1無二義文法，應(yīng)選c。4、選a。5、選c。多項選擇解答： 1、一個LR分析器包括一個總控程序和一張分析表，選a、d。2、選c、e。3、選a、c、d、e。4、在LR分析表的構(gòu)造中有可能存在“移進(jìn)/“歸約和“歸約/“歸約沖突；應(yīng)選c、e。5、選a、b、c、d、e。6、選a、b、c、e。7、選a、c、d、e。填空解答

42、： 1、一張分析表 每個入口2、任意首部3、標(biāo)準(zhǔn)句型 句柄4、輸入串 活前綴5、活前綴 工程集合 LR分析算法6、歸約 接受 移進(jìn) 待約7、自左至右分析 采用最右推導(dǎo)的逆過程即最左歸約 向右查看0個字符綜合解答：首先將文法G拓廣為GS：SSSAS|bASA|a1文法GS的LR0工程是： 1、S·S5、SAS·9、AS·A 2、SS·6、S·b10、ASA· 3、S·AS7、Sb·11、A·a 4、SA·S8、A·SA12、Aa·2、列出構(gòu)成文法LR0工程集標(biāo)準(zhǔn)族。用-CLOS

43、URE閉包方法構(gòu)造文法G的LR0工程集標(biāo)準(zhǔn)族如下：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·AS11、A·a6、S·b3、S·AS8、A·SA6、S·b 11、

44、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讀入一個S字符后得到的下一個工程；，而I4中的ASA和AA·S那么是由I3中的9和3讀入一個A字符后得到的下一個工程；I5中的SAS·和AS·A那么是由I4中的4和8讀入一個S字符后得到的下一個工程。狀態(tài)全體構(gòu)成了文法G的LR0標(biāo)準(zhǔn)族。第七章一、單項選擇題1、中間代碼生成所依據(jù)的是 。a.語法規(guī)那么