1、第八節 習題一、單項選擇題1、將編譯程序分成若干個“遍”是為了 。 a提高程序的執行效率 b使程序的結構更加清晰 c利用有限的機器內存并提高機器的執行效率 d利用有限的機器內存但降低了機器的執行效率2、構造編譯程序應掌握 。 a源程序b目標語言 c編譯方法d以上三項都是3、變量應當 。 a持有左值b持有右值 c既持有左值又持有右值d既不持有左值也不持有右值 4、編譯程序絕大多數時間花在 上。 a出錯處理b詞法分析 c目標代碼生成d管理表格5、 不可能是目標代碼。 a匯編指令代碼b可重定位指令代碼 c絕對指令代碼d中間代碼6、使用 可以定義一個程序的意義。 a語義規則b詞法規則 c產生規則d詞法

2、規則7、詞法分析器的輸入是 。 a單詞符號串b源程序 c語法單位d目標程序8、中間代碼生成時所遵循的是- 。 a語法規則b詞法規則 c語義規則d等價變換規則9、編譯程序是對 。 a匯編程序的翻譯b高級語言程序的解釋執行 c機器語言的執行d高級語言的翻譯10、語法分析應遵循 。 a語義規則b語法規則 c構詞規則d等價變換規則解答1、將編譯程序分成若干個“遍”是為了使編譯程序的結構更加清晰，故選b。2、構造編譯程序應掌握源程序、目標語言及編譯方法等三方面的知識，故選d。3、對編譯而言，變量既持有左值又持有右值，故選c。4、編譯程序打交道最多的就是各種表格，因此選d。5、目標代碼包括匯編指令代碼、可

3、重定位指令代碼和絕對指令代碼3種，因此不是目標代碼的只能選d。6、詞法分析遵循的是構詞規則，語法分析遵循的是語法規則，中間代碼生成遵循的是語義規則，并且語義規則可以定義一個程序的意義。因此選a。 7、b 8、c 9、d 10、c二、多項選擇題1、編譯程序各階段的工作都涉及到 。 a語法分析b表格管理c出錯處理 d語義分析e詞法分析2、編譯程序工作時，通常有 階段。 a詞法分析b語法分析c中間代碼生成 d語義檢查e目標代碼生成解答1b、c 2. a、b、c、e三、填空題 1、解釋程序和編譯程序的區別在于 。2、編譯過程通常可分為5個階段，分別是 、語法分析 、代碼優化和目標代碼生成。3、編譯程序

4、工作過程中，第一段輸入是 ，最后階段的輸出為 程序。4、編譯程序是指將 程序翻譯成 程序的程序。解答 是否生成目標程序 2、詞法分析 中間代碼生成 3、源程序目標代碼生成4、源程序 目標語言一、單項選擇題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、有限狀態自動機能識別 。a. 上下文無關文法b. 上下文有關文法c.正規文法d. 短語文法4、設g為算符優先

5、文法，g的任意終結符對a、b有以下關系成立 。a. 若f(a)g(b)，則abb.若f(a)g(b)，則ag)(b)或f(a)g(b)并不能判定原來的a與b之間是否存在優先關系：故選c。5、如果文法g無二義性，則最左推導是先生長右邊的枝葉：對于d，如果有兩個不同的是了左推導，則必然有二義性。故選a。6、選c。7、由圖2-8-1的語法樹和優先關系可以看出應選b。ee + fe + t pt ip #+#圖2-8-1 句型p+t+i的語法及優先關系8、規范推導是最左推導，故選d。9、由tt,和t( 得firstvt(t)=(,，)； 由ts得firstvt(s)firstvt(t)，而firstv

6、t(s)=b,(；即 firstvt(t)=b,(,，； 因此選c。 10、d 11、c 12、b 13、b 14、b二、多項選擇題1、下面哪些說法是錯誤的 。a. 有向圖是一個狀態轉換圖b. 狀態轉換圖是一個有向圖c.有向圖是一個dfad.dfa可以用狀態轉換圖表示2、對無二義性文法來說，一棵語法樹往往代表了 。a. 多種推導過程b. 多種最左推導過程c.一種最左推導過程d.僅一種推導過程e.一種最左推導過程3、如果文法g存在一個句子，滿足下列條件 之一時，則稱該文法是二義文法。a. 該句子的最左推導與最右推導相同b. 該句子有兩個不同的最左推導c. 該句子有兩棵不同的最右推導d. 該句子有

7、兩棵不同的語法樹 e.該句子的語法樹只有一個4、有一文法g：sab aaab| bcbd|它不產生下面 集合。a. anbmcndm|n,m0b. anbncmdm|n,m0c. anbmcmdn|n,m0d. anbncmdm|n,m0e. anbncndn|n05、自下而上的語法分析中，應從 開始分析。a. 句型b. 句子c. 以單詞為單位的程序d. 文法的開始符e. 句柄6、對正規文法描述的語言，以下 有能力描述它。a.0型文法b.1型文法 c.上下文無關文法 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、

8、e 三、填空題1、文法中的終結符和非終結符的交集是 。詞法分析器交給語法分析器的文法符號一定是 ，它一定只出現在產生式的 部。2、最左推導是指每次都對句型中的 非終結符進行擴展。3、在語法分析中，最常見的兩種方法一定是 分析法，另一是 分析法。4、采用 語法分析時，必須消除文法的左遞歸。5、 樹代表推導過程， 樹代表歸約過程。6、自下而上分析法采用 、歸約、錯誤處理、 等四種操作。 7、chomsky把文法分為 種類型，編譯器構造中采用 和 文法，它們分別產生 和 語言，并分別用 和 自動機識別所產生的語言。解答 1、空集 終結符 右 2、最左 3、自上而上 自下而上 4、自上而上 5、語法

9、分析 6、移進 接受 7、4 2 型 3型 上下文無關語言 正規語言 下推自動機 有限四、判斷題1、文法 sas|br|描述的語言是(a|bc)* ( ) rcs2、在自下而上的語法分析中，語法樹與分析樹一定相同。 （ ）3、二義文法不是上下文無關文法。 （ ）4、語法分析時必須先消除文法中的左遞歸。（ ）5、規范歸約和規范推導是互逆的兩個過程。（ ）6、一個文法所有句型的集合形成該文法所能接受的語言。（ ）解答 1、對 2、錯 3、錯 4、錯 5、錯 6、錯五、簡答題1、句柄2、素短語3、語法樹4、歸約5、推導解答 1、句柄：一個句型的最左直接短語稱為該句型的句柄。2、素短語：至少含有一個終

10、結符的素短語，并且除它自身之外不再含任何更小的素短語。3、語法樹：滿足下面4個條件的樹稱之為文法gs的一棵語法樹。每一終結均有一標記，此標記為vnvt中的一個符號；樹的根結點以文法gs的開始符s標記；若一結點至少有一個直接后繼，則此結點上的標記為vn中的一個符號；若一個以a為標記的結點有k個直接后繼，且按從左至右的順序，這些結點的標記分別為x1,x2,xk，則ax1,x2,xk，必然是g的一個產生式。4、歸約：我們稱直接歸約出a，僅當a 是一個產生式，且、(vnvt)*。歸約過程就是從輸入串開始，反復用產生式右部的符號替換成產生式左部符號，直至文法開始符。5、推導：我們稱a直接推出，即a，僅當

11、a 是一個產生式，且、(vnvt)*。如果12n，則我們稱這個序列是從1至2的一個推導。若存在一個從1n的推導，則稱1可推導出n。推導是歸約的逆過程。六、問答題1、給出上下文無關文法的定義。解答一個上下文無關文法g是一個四元式（vt,vn,s, p），其中：vt是一個非空有限集，它的每個元素稱為終結符號；vn是一個非空有限集，它的每個元素稱為非終結符號，vtvn=；s是一個非終結符號，稱為開始符號；p是一個產生式集合（有限），每個產生式的形式是p，其中，pvn，(vtvn)*。開始符號s至少必須在某個產生式的左部出現一次。 2、文法gs： saspq|abq qppq bpbb bqbc cq

12、cc（1）它是chomsky哪一型文法？（2）它生成的語言是什么？解答 （1）由于產生式左部存在終結符號，且所有產生式左部符號的長度均小于等于產生式右部的符號長度，所以文法gs是chomsky1型文法，即上下文有關文法。（2）按產生式出現的順序規定優先級由高到低（否則無法推出句子），我們可以得到： sabqabc saspqaabqpqaabpqqaabbqqaabbcqaabbcc saspqaaspqpqaaabqpqpqaaabpqqpqaaabpqpqqaaappqqqaaabbpqqqaaabbqqqaaabbbcqqaaabbbccqaaabbbccc 于是得到文法gs生成的語言l

13、=anbncn|n13、按指定類型，給出語言的文法。l=aibj|ji1的上下文無關文法。【解答】（1）由l=aibj|ji1知，所求該語言對應的上下文無關文法首先應有sasb型產生式，以保證b的個數不少于a的個數；其次，還需有ssb或sbs型的產生式，用以保證b的個數多于a的個數；也即所求上下文無關文法gs為：gs：sasb|sb|b4、有文法g：saacb|bdaaab|cbbsca|b（1）試求句型aaabcbbdcc和aacbbdcc的句柄；（2）寫出句子acabcbbdcc的最左推導過程。【解答】（1）分別畫出對應兩句型的語法樹，如圖2-8-2所示句柄:aab bd sa a c b

14、 aab b s c ab d cb(a)s a a c bb s c ab d c(b)圖2-8-2 語法樹（2）句子acabcbbdcc的最左推導如下： saacbaaabcbacabcbacabcbacabcbscaacabcbbdca acabcbbdcaacabcbbdcc 5、對于文法gs： s（l）|as|a ll, s|s（1）畫出句型（s,（a）的語法樹。（2）寫出上述句型的所有短語、直接短語、句柄和素短語。s（ l ）l ， ss ( l ) s a圖2-8-3 句型（s,（a）的語法樹【解答】（1）句型（s,（a）的語法樹如圖2-8-3所示（2）由圖2-8-3可知：短語：

15、s、a、(a)、s,(a)、(s,(a)；直接短語：a、s；句柄：s；素短語：素短語可由圖2-8-3中相鄰終結符之間的優先關系求得，即；# （，（a ） ） #因此素短語為a。6、考慮文法gt：tt*f|fffp|pp（t）|itt * ff pp （ t ）t * f圖2-8-4 句型t*p（t*f）的語法樹證明t*p（t*f）是該文法的一個句型，并指出直接短語和句柄。【解答】首先構造t*p（t*f）的語法樹如圖2-8-4所示。由圖2-8-4可知，t*p（t*f）是文法gt的一個句型。直接短語有兩個，即p和t*f；句柄為p。一、單項選擇題1、詞法分析所依據的是 。a. 語義規則b. 構詞規則

16、c. 語法規則d. 等價變換規則2、詞法分析器的輸出結果是 。a. 單詞的種別編碼b. 單詞在符號表中的位置c. 單詞的種別編碼和自身值d. 單詞自身值3、正規式m1和m2等價是指 。a. m1和m2的狀態數相等b. m1和m2的有向弧條數相等c. m1和m2所識別的語言集相等 d. m1和m2狀態數和有向弧條數相等4、狀態轉換圖（見圖3-6-1）接受的字集為 。 0 1 0圖3-6-1yxa. 以 0開頭的二進制數組成的集合 b. 以0結尾的二進制數組成的集合c. 含奇數個0的二進制數組成的集合 d. 含偶數個0的二進制數組成的集合5、詞法分析器作為獨立的階段使整個編譯程序結構更加簡潔、明確

17、，因此， 。a. 詞法分析器應作為獨立的一遍 b. 詞法分析器作為子程序較好c. 詞法分析器分解為多個過程，由語法分析器選擇使用 d. 詞法分析器并不作為一個獨立的階段解答 1、b 2、c 3、c 4、d 5、b二、多項選擇題1、在詞法分析中，能識別出 。a. 基本字b. 四元式c. 運算符d. 逆波蘭式e. 常數2、令=a,b，則上所有以b開頭，后跟若干個ab的字的全體對應的正規式為 。a. b(ab)*b. b(ab)+c.(ba)*bd. (ba)+be. b(a|b)解答 1、a、c、e 2、a、b、d三、填空題1、確定有限自動機dfa是 的一個特例。2、若二個正規式所表示的 相同，則

18、認為二者是等價的。3、一個字集是正規的，當且僅當它可由 所 。解答 1、nfa 2、正規集 3、dfa（nfa）所識別四、判斷題1、一個有限狀態自動機中，有且僅有一個唯一終態。（ ）2、設r和s分別是正規式，則有l（r|s）=l(r)|l(s)。（ ）3、自動機m和m的狀態數不同，則二者必不等價。（ ）4、確定的自動機以及不確定的自動機都能正確地識別正規集。（ ）5、對任意一個右線性文法g，都存在一個nfa m，滿足l(g)=l(m)。（ ）6、對任意一個右線性文法g，都存在一個dfa m，滿足l(g)=l(m)。（ ）7、對任何正規表達式e，都存在一個nfa m，滿足l(g)=l(e)。（

19、）8、對任何正規表達式e，都存在一個dfa m，滿足l(g)=l(e)。（ ）解答 1 、2、3、錯 4、5、6、7、8、正確五、基本題1、設m（x,y, a,b, f,x,y）為一非確定的有限自動機，其中f定義如下：f（x,a）x,y f（x,b）yf（y,a） f（y,b）x,y 試構造相應的確定有限自動機m。解答：對照自動機的定義m=(s,f,s0,z)，由f的定義可知f(x,a)、f(y,b)均為多值函數，所以是一非確定有限自動機，先畫出nfa m相應的狀態圖，如圖3-6-2所示。 a a b b b圖3-6-2 nfa mxy用子集法構造狀態轉換矩陣表3-6-3所示。iiaibxx,

20、yyyx,yx,yx,yx,y將轉換矩陣中的所有子集重新命名而形成表3-6-4所示的狀態轉換矩陣。表3-6-4 狀態轉換矩陣ab02112222 a a,b b b圖3-6-5 dfa m021即得到m=（0,1,2, a,b, f,0, 1,2），其狀態轉換圖如圖3-6-5所示。 a a,b b圖3-6-6 化簡后的dfa m01將圖3-6-5的dfa m最小化。首先，將m的狀態分成終態組1，2與非終態組0；其次，考察1,2。由于1,2a=1,2b=21,2，所以不再將其劃分了，也即整個劃分只有兩組0，1,2：令狀態1代表1,2，即把原來到達2的弧都導向1，并刪除狀態2。最后，得到如圖3-6

21、-6所示化簡dfa m。2、對給定正規式b*（d|ad）（b|ab）+，構造其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*改造正規式得：b*(d|ad)(b|ab)(b|ab)*；其次，構造該正規式的nfa m，如圖3-6-7所示。1、 構造下面文法的ll（1）分析表。d tlt int | reall id rr , id r | 解答： ll（1）分析表見表4-3-1分析 雖然這個文法很簡單，我們還

22、是從求開始符號集合和后繼符號集合開始。 first（d）=first（t）=int, real follow（d）=follow（l）=#first（l）=id follow（t）=idfirst（r）=，, follow（r）=#有了上面每個非終結符的first集合，填分析表時要計算一個產生式右部的first（）就不是件難事了。填表時唯一要小心的時，是產生式r右部的一個開始符號，而#在follow（r）中，所以r填在輸入符號#的欄目中。表4-3-1 ll（1）分析表非終結符輸入符號int realid，#ddtldtlttinttrealllid rrr,id rr 2、 下面文法gs是否為

23、ll（1）文法？說明理由。s a b | p q x a x y b b cp d p | q a q | 解答： 該文法不是ll（1）文法，見下面分析中的說明。分析 只有三個非終結符有兩個選擇。 1、p的兩個右部d p 和 的開始符號肯定不相交。2、q的兩個右部a q 和 的開始符號肯定不相交。3、對s來說，由于x first(a b)，同時也有x first(p q x)（因為p和q都可能為空）。所以該文法不是ll（1）文法。3、 設有以下文法： gs：saabde|d absd|e bsac| cd| dse| （1）求出該文法的每一個非終結符u的follow集。（2）該文法是ll（1）

24、文法嗎？（3）構造cs的ll（1）分析表。解答： （1）求文法的每一個非終結符u的follow集的過程如下：因為： s是識別符號，且有absd、bsac、dse，所以follow（s）應包含first(d)first(ac) first(e) #=a,da,d,c,ee#=a,c,d,e# 又因為absd和d，所以follow中還包含follow(a)。因為saabde和bsac,所以follow（a）=first（bde）first（c）=b,c綜合、得follow（s）=a,d,c,e,#a,b,c,d,e,#因為absd，所以 follow（b）=first（sd）=a,d 因為saab

25、de | 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）文法。因為產生式bsac|cd| 中 first（sac）follow（b）=a,d（3）構造gs的ll（1）分析表。按照ll（1）分析表的構造算法構造方法gs的ll（1）分析表如表4-3-2所示。表4-3-2 gs的ll（1）分析表abcde#saabdedabsdbsdbsdebsac/cdsac/dse/se/4、 將文法gv改造成為ll(1)的。 gv：vn|ne ev|v+e ni解答： 對文法gv

26、提取公共左因子后得到文法： gv：vnaa|eevbb|+eni求出文法gv中每一個非終結符號的first集： first(v)=ifirst(a)=, first(e)=ifirst(b)=+, first(n)=i求出文法gv中每一個非終結符號的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)=,+,#可以看到，對文法g

27、v的產生式a|e，有first(e)follow(a)=+,#= 對產生式b|+e，有first(+e)follow(b)=+= 而文法的其他產生式都只有一個不為的右部，所以文法gv是ll(1)文法。5、已知文法：ga：aaaa|（1）該文法是ll（1）文法嗎？為什么？（2）若采用ll（1）方法進行語法分析，如何得到該文法的ll（1）分析表？（3）若輸入符號串“aaaa”，請給出語法分析過程。解答：（1）因為產生式aaaa| 有空產生式右部，而 follow(a)=#first(a)=a, #造成 first(a)follow(a)=a, a, #所以該文法不是ll（1）文法。（2）若采用ll

28、（1）方法進行語法分析，必須修改該文法。因該文法產生偶數（可以為0）個a，所以得到文法ga：aaaa|此時對產生式aaaa|， 有 follow(a)=#follow(a)=#，因而first(a)follow(a)=a, #=所以文法ga是ll（1）文法，按ll（1）分析表構造算法構造該文法的ll（1）分析表如表4-3-3所示。表4-3-3 文法ga的ll(1)分析表a#aaaaaa（3）若采用ll(1)方法進行語法分析，對符號串“aaaa”的分析過程如表4-3-4所示。 表4-3-4對符號串“aaaa”的分析過程步驟分析棧輸入串產生式/動作1#aa a a a #aaaa2#a a aa

29、a a a #匹配3#a aa a a #匹配4#aa a #aaaa5#a a aa a #匹配6#a aa#匹配7#a#a8#接受第七節 習題設有文法gs為：sa|b|(a)asda|s（1） 完成下列算符優先關系表，見表5-7-1，并判斷gs是否為算符優先文法。表5-7-1 算符優先關系表ab()d#ab()d# （2）給出句型（sdsds）的短語、簡單短語、句柄、素短語和最左素短語。（3）給出輸入串（adb）#的分析過程。解答： （1）先求文法gs的firstvt集和lastvt集：由sa|b|(a)得：firstvt(s)=a,b,( );由asd得：firstvt(a)=d;又由a

30、s得：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,)。構造優先關系表方法如下： 對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)得，last

31、vt(a)，即：d),a),b),);由asd得：lastvt(s)d，即：ad,bd,)d;此外，由#s#得：#；由#firstvt(s)得：#a,#b,#(；脂由lastvt(s)#得：d#,a#,b#,)#。最后得到算符優先關系表，見表5-7-2。表5-7-2 算符優先關系表ab()d#ab()d#由表5-7-2可以看出，任何兩個終結符之間至少只滿足、三種優先關系之一，故gs為算符優先文法。sasasd（）asd圖5-7-3 句型（sdsds）的語法樹（2）為求出句型（sdsds）的短語、簡單短語、句柄，我們先畫出該句型對應的語法樹，如圖5-7-3所示。由圖5-7-3得到：短語：s，sd

32、s，sdsds，（sdsds）簡單短語（即直接短語）：s句柄（即最左直接短語）：s素短語：sds，它同時也是該句型的最左素短語。（3）輸入串（adb）#的分析過程見表5-7-4表5-7-4 輸入串（adb）#的分析過程符號棧輸入串說明#(adb)#移進#（adb)#移進#（adb)#用sa歸約#（sdb)#移進#（sdb)#移進#（sdb)#用sb歸約#（sds)#用as歸約#（sda)#用asda歸約#（a)#移進#（a）#用s（a）歸約#s#分析成功第四節 習題一、單項選擇題1、若a為終結符，則aa為 項目 a.歸約b.移進c.接受d.待約2、若項目集ik含有a，則在狀態k時，僅當面臨的輸

33、入符號afollow(a)時，才采取“a”動作的一定是 。 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子表中，如果某一行中存在標記“rj”的欄，則 。 a.該行必定填滿rjb.該行未填滿rjc.其他行也有rjd.goto子表中也有rj5、一個 指明了在分析過程中的某時刻所能看到產生式多大一部分。 a.活前綴b.前綴c.項目d.項目集解答： 1、a稱為歸約項目，對文法開始符s的歸約項目，如s稱為接

34、受項目，aa（a為終結符）稱為移進項目。在此選b.2、當用產生式a歸約時，lr（0）無論面臨什么輸入符號都進行歸約；slr（1）則僅當面臨的輸入符號afollow(a)時進行歸約；lr（1）則當在把歸約為a的規范句型的前綴aa前提下，當后跟終結符a時，才進行歸約；因此選d。3、由于lr（0）slr（1） lr（1）無二義文法，故選c。4、選a。5、選c。二、多項選擇題1、一個lr分析器包括 。 a.一個總控程序b.一個項目集c.一個活前綴d.一張分析表e.一個分析棧2、lr分析器核心部分是一張分析表，該表包括 等子表。 a.ll(1)分析b.優先關系c.goto d.lre.action3、每

35、一項actions，a所規定的動作包括 。a.移進b.比較c.接受d.歸約e.報錯4、對lr分析表的構造，有可能存在 動作沖突。a.移進b.歸約c.移進/歸約d.移進/移進e.歸約/歸約5、就文法的描述能力來說，有 。 a. slr（1）lr（1）b. lr（1）slr（1）c. lr（0）lr（1）d. lr（1）無二義文法 e. slr（1）無二義文法6、對lr分析器來說，存在 等分析表的構造方法。 a.lalrb.lr（0）c.slr（1）d.slr（0）e.lr（1）7、自上而下的語法分析方法有 。 a.算符優先分析法b.ll（1）分析法c.slr（1）分析法d.lr（0）分析法e.l

36、alr（1）分析法解答： 1、一個lr分析器包括一個總控程序和一張分析表，選a、d。2、選c、e。3、選a、c、d、e。4、在lr分析表的構造中有可能存在“移進”/“歸約”和“歸約”/“歸約”沖突；故選c、e。5、選a、b、c、d、e。6、選a、b、c、e。7、選a、c、d、e。三、填空題1、對于一個文法，如果能夠構造 。使得它的 均是唯一確定的，則稱該文法為lr文法。2、字的前綴是指該字的 。3、活前綴是指 的一個前綴，這種前綴不含 之后的任何符號。4、在lr分析過程中，只要 的已掃描部分保持可歸約成一個 ，則掃描過的部分正確。5、將識別 的nfa確定化，使其成為以 為狀態的dfa，這個df

37、a就是建立 的基礎。6、a稱為 項目；對文法開始符s為 項目；若a為終結符，則稱aa為 項目；若b為非終結符，則稱aa為 項目。 7、lr（0）分析法的名字中“l”表示 ，“r”表示 ，“0”表示 。解答： 1、一張分析表 每個入口2、任意首部3、規范句型 句柄4、輸入串 活前綴5、活前綴 項目集合 lr分析算法6、歸約 接受 移進 待約7、自左至右分析 采用最右推導的逆過程即最左歸約 向右查看0個字符四、綜合題1、對于文法gs： sas|b asa|a （1）列出所有lr（0）項目（2）列出構成文法lr（0）項目集規范族。解答：首先將文法g拓廣為gs：sssas|basa|a（1）文法gs的

38、lr（0）項目是： 1、ss5、sas9、asa 2、ss6、sb10、asa 3、sas7、sb11、aa 4、sas8、asa12、aa2、列出構成文法lr（0）項目集規范族。用-closure（閉包）辦法構造文法g的lr（0）項目集規范族如下：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、asa4、sas8、asa3、sas11、aa6、sb3、sas8、asa6、sb 11、aai2：4、sasi5：5、sas 3、sas9、asa6、sb8、asa

39、 8、asa11、aa 11、aa3、sas6、sb注意：i1中的ss和asa是由狀態i0中的1和3讀入一個s字符后得到的下一個項目；，而i4中的asa和aas則是由i3中的9和3讀入一個a字符后得到的下一個項目；i5中的sas和asa則是由i4中的4和8讀入一個s字符后得到的下一個項目。狀態全體構成了文法g的lr（0）規范族。第八節 習題一、單項選擇題1、中間代碼生成所依據的是 。a.語法規則b.詞法規則c.語義規則d.等價變換規則2、四元式之間的聯系是通過 實現的。 a.指示器b.臨時變量c.符號表d.程序變量3、后綴式ab+cd+/可用表達式 來表示。a.a+b/c+db.(a+b)/(c+d)c.a+b/(c+d)d.a+b+c/d4、表達式（ab）（cd）的逆波蘭表示為 。 a. abcdb. abcdc. abcdd. abcd5、中間代碼的樹型表示+abcd+ 所對應的表達式為 。 a.a+b+c+db.a+(b+c)+dc.