整理完編譯原理網(wǎng)上作業(yè)題參考答案

1、編譯原理作業(yè)題參考答案第一章 編譯概述多項(xiàng)選擇題：1.編譯程序各階段的工作都涉及到（BC）。（）2.編譯程序工作時(shí)，通常有（ABCE）階段。 （）填空題：1解釋程序和編譯程序的區(qū)別在于（是否生成目標(biāo)程序）。（）2編譯過程通?？煞譃?個(gè)階段，分別是（詞法分析）、（語法分析）、（中間代碼生成）、（代碼優(yōu)化）和（目標(biāo)代碼）生成。（）3編譯程序工作過程中，第一段輸入是（源程序），最后階段的輸出為（目標(biāo)代碼生成）程序。（）4編譯程序是指將（高級語言編寫的）程序翻譯成（目標(biāo)語言）程序的程序。（）綜合題：1.畫出編譯程序的總體結(jié)構(gòu)圖，簡述各部分的主要功能。（）解答：編譯程序的總體結(jié)構(gòu)如下圖所示：詞

2、法分析程序：輸入源程序，進(jìn)行詞法分析，輸出單詞符號。語法分析程序：在詞法分析的基礎(chǔ)上，根據(jù)語言的語法規(guī)則（方法規(guī)則）把單詞符號串分解成各類語法單位，并判斷輸入串是否構(gòu)成語法上正確的“程序”。中間代碼生成程序：按照語義規(guī)則把語法分析程序歸約（或推導(dǎo)）出的語法單位翻譯成一定形式的中間代碼，比如說四元式。優(yōu)化程序：對中間代碼進(jìn)行優(yōu)化處理。目標(biāo)代碼生成程序：把中間代碼翻譯成目標(biāo)語言程序。表格管理模塊保存一系列的表格，登記源程序的各類信息和編譯各階段的進(jìn)展情況。編譯程序各階段所產(chǎn)生的中間結(jié)果都記錄在表格中，所需信息多數(shù)都需從表格中獲取，整個(gè)編譯過程中都在不斷地和表格打交道。出錯(cuò)處理程序?qū)Τ霈F(xiàn)在源程序中的

3、錯(cuò)誤進(jìn)行處理。此外，編譯的各個(gè)階段都可能出現(xiàn)錯(cuò)誤。出錯(cuò)處理程序?qū)Πl(fā)現(xiàn)的錯(cuò)誤都及時(shí)進(jìn)行處理。 第二章 文法和語言的基本知識(shí)多項(xiàng)選擇題：1.ABC2.ACE3.BCD4.AC5.BC 填空題：1文法中的終結(jié)符和非終結(jié)符的交集是（空集）。詞法分析器交給語法分析器的文法符號一定是（終結(jié)符），它一定只出現(xiàn)在產(chǎn)生式的（右）部。（）2最左推導(dǎo)是指每次都對句型中的（最左）非終結(jié)符進(jìn)行擴(kuò)展。（）3在語法分析中，最常見的兩種方法一定是（自上而上）分析法，另一是（自下而上）分析法。（）4采用（自上而下）語法分析時(shí)，必須消除文法的左遞歸。（）5（語法）樹代表推導(dǎo)過程，（分析）樹代表歸約過程。（）6自下而上分

4、析法采用（移進(jìn)）、歸約、錯(cuò)誤處理、（接受）等四種操作。（）7Chomsky把文法分為（4）種類型，編譯器構(gòu)造中采用 （2型） 和（3型）文法，它們分別產(chǎn)生（上下文無關(guān)語言）和（正規(guī)語言）語言，并分別用（下推自動(dòng)機(jī)）和（有限）自動(dòng)機(jī)識(shí)別所產(chǎn)生的語言。（）判斷題： 1正確2錯(cuò)誤3錯(cuò)誤4錯(cuò)誤5錯(cuò)誤6錯(cuò)誤7正確8正確9錯(cuò)誤簡答題1句柄：（）解答：一個(gè)句型的最左直接短語稱為該句型的句柄。2素短語：（）解答：至少含有一個(gè)終結(jié)符的素短語， 并且除它自身之外不再含任何更小的素短語。3語法樹：（）解答：滿足下面4個(gè)條件的樹稱之為文法GS的一棵語法樹。每一終結(jié)均有一標(biāo)記，此標(biāo)記為VNVT中的一個(gè)符號；樹

5、的根結(jié)點(diǎn)以文法GS的開始符S標(biāo)記；若一結(jié)點(diǎn)至少有一個(gè)直接后繼，則此結(jié)點(diǎn)上的標(biāo)記為VN中的一個(gè)符號；若一個(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)生式右部的符號替換成產(chǎn)生式左部符號，直至文法開始符。5推導(dǎo)：（）解答：我們稱A直接推出，即AT，僅當(dāng)A 是一個(gè)產(chǎn)生式，且、(VNVT)*。如果12n，則我們稱這個(gè)序列是從1至2的一個(gè)推導(dǎo)。若存在一個(gè)從1n的推導(dǎo)，則稱1可推導(dǎo)出n。推導(dǎo)是歸約的逆

6、過程。問答題1給出上下文無關(guān)文法的定義。（）解答：一個(gè)上下文無關(guān)文法G是一個(gè)四元式（VT,VN,S, P），其中：VT是一個(gè)非空有限集，它的每個(gè)元素稱為終結(jié)符號；VN是一個(gè)非空有限集，它的每個(gè)元素稱為非終結(jié)符號，VTVN=；S是一個(gè)非終結(jié)符號，稱為開始符號；P是一個(gè)產(chǎn)生式集合（有限），每個(gè)產(chǎn)生式的形式是P，其中，PVN，(VTVN)*。開始符號S至少必須在某個(gè)產(chǎn)生式的左部出現(xiàn)一次。 2.文法GS：SaSPQ|abQQPPQbPbbbQbccQcc（1）它是Chomsky哪一型文法？（2）它生成的語言是什么？（）解答： （1）由于產(chǎn)生式左部存在終結(jié)符號，且所有產(chǎn)生式左部符號的長度均小于等于產(chǎn)生式

7、右部的符號長度，所以文法GS是Chomsky1型文法，即上下文有關(guān)文法。（2）按產(chǎn)生式出現(xiàn)的順序規(guī)定優(yōu)先級由高到低（否則無法推出句子），我們可以得到：SabQabcSaSPQaabQPQaabPQQaabbQQaabbcQ aabbccSaSPQaaSPQPQaaabQPQPQaaabPQQPQaaabPQPQQaaaPPQQQaaabbPqqqaaabbQQQaaabbbcQQaaabbbccQaaabbbccc于是得到文法GS生成的語言L=anbncn|n13按指定類型，給出語言的文法。 L=aibj|ji1的上下文無關(guān)文法。（）解答： 由L=aibj|ji1知，所求該語言對應(yīng)的上下文無關(guān)

8、文法首先應(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|BdAAaB|cBbScA|b（1）試求句型aAaBcbbdcc和aAcbBdcc的句柄；（2）寫出句子acabcbbdcc的最左推導(dǎo)過程。（）解答：（1）分別畫出對應(yīng)兩句型的語法樹，如下圖所示句柄:AaBBd 圖語法樹（2）句子acabcbbdcc的最左推導(dǎo)如下：STaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcAacabcbbdcAacabcbbdcc5

9、對于文法GS：S（L）|aS|a LL, S|S（1）畫出句型（S,（a）的語法樹。（2）寫出上述句型的所有短語、直接短語、句柄和素短語。（）解答：（1）句型（S,（a）的語法樹如下圖所示。圖句型（S,（a）的語法樹（2）由上圖可知：短語：S、a、(a)、S,(a)、(S,(a)；直接短語：a、S；句柄：S；素短語：素短語可由圖2-8-3中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即； 因此素短語為a。6. 考慮文法GS,其產(chǎn)生式如下: S(L)|a LL，S|S (a)試指出此文法的終結(jié)符號、非終結(jié)符號。(b)給出句子(a,(a，a)的分析樹。(c)構(gòu)造句子(a,(a，a)的一個(gè)最左推導(dǎo)。(d)構(gòu)造句子

10、(a,(a，a)的一個(gè)最右推導(dǎo)。(e)這個(gè)文法生成的語言是什么？（）解答：(a) 終結(jié)符號為：(,),a,    非終結(jié)符號為：S,L    開始符號為：S(b)分析樹（c）    S (L) (L,S) (S,S) (a,S) (a,(L) (a,(L,S)      (a,(S,S) (a,(a,S) (a,(a,a)(d) S (L) (L,S) (L,(L) (L,(L,S) (L,(L,a)      (L,(S,a

11、) (L,(a,a) (S,(a,a) (a,(a,a)(e) L(GS) = (1,2,.,n)或a    其中i(1in)是L(GS)。即L(GS)產(chǎn)生一個(gè)以a為原子的純表，但不包括空表。7考慮文法GT：TT*F|FFFP|PP（T）|i證明T*P（T*F）是該文法的一個(gè)句型，并指出直接短語和句柄。（）解答：首先構(gòu)造T*P（T*F）的語法樹如下圖所示。圖句型T*P（T*F）的語法樹由上圖可知，T*P（T*F）是文法GT的一個(gè)句型。直接短語有兩個(gè)，即P和T*F；句柄為P。8試描述下列文法產(chǎn)生的語言L（GS）（）S10S0|aAAbA|a解答：L(G)=(10)i

12、abna0i n0 i09已知語言L(G)=abnc|n1 試對該語言構(gòu)造相應(yīng)文法。（）解答：GZ:ZaBCBBb|b10證明下列文法的二義性 （）1GZ 2GS ZaZbZ|aZ|aSAB AbB|bC|ba BSb|ba|a CBb|b解答：（1）對于句子aaaba，畫出二棵不同的語法樹，因而是二義的。（2）GS對于句子baba，畫出二棵不同的語法樹，因而是二義的。11有文法GS：SiSeS|iS|i 該文法是否是二義的。試證明之。（）解答：對于句子iiiei，有兩棵不同的語法樹，故文法是二義的。12文法GT：TaR，RTb|d生成的語言是什么？GT是否為3型文法？（）解答：不是3型文法。

13、13.試寫出能夠描述下列電話號碼格式的文法。（）67391742解答： 文法產(chǎn)生式規(guī)則如下：<電話號碼> <局代碼> <本機(jī)碼><電話號碼> <區(qū)前綴> <局代碼> <本機(jī)碼><區(qū)前綴> <地區(qū)碼> -<區(qū)前綴> ( <地區(qū)碼> )<地區(qū)碼> DIG DIG<地區(qū)碼> DIG DIG DIG<局代碼> DIG DIG DIG DIG<本機(jī)碼> DIG DIG DIG DIG14. 試構(gòu)造生成語言的上下文無關(guān)文法。（）

14、(1) anbnci | n1,i0 (2) w | wa,b+，且w中a的個(gè)數(shù)恰好比b多1 解答：(1)把a(bǔ)nbnci分成anbn和ci兩部分，分別由兩個(gè)非終結(jié)符號生成，因此，生成此文法的產(chǎn)生式為：S ABA aAb|abB cB|(2)令S為開始符號，產(chǎn)生的w中a的個(gè)數(shù)恰好比b多一個(gè)，令E為一個(gè)非終結(jié)符號，產(chǎn)生含相同個(gè)數(shù)的a和b的所有串，則產(chǎn)生式如下： S aE|Ea|bSS|SbS|SSbE aEbE|bEaE|15. 下面的二義性文法描述命題演算公式，為它寫一個(gè)等價(jià)的非二義性文法。GS:S -> S AND S | S OR S | NOT S | p | q | (S)（）解答

15、：GS:S -> S AND A | AA -> A OR B | BB -> NOT B |p | q | (S)16. 對于下列語言分別寫出它們的正規(guī)表達(dá)式。（）(1) 英文字母組成的所有符號串，要求符號串中順序包含五個(gè)元音。(2) 英文字母組成的所有符號串，要求符號串中的字母依照詞典順序排列。解答：(1) 令Letter表示除這五個(gè)元音外的其它字母。(letter)*A(letter)*E(letter)*I(letter)*O(letter)*U(letter)*(2) A*B*.Z*第三章 詞法分析與有窮自動(dòng)機(jī)多項(xiàng)選擇題：1.

16、ACE2.ABD填空題：1確定有限自動(dòng)機(jī)DFA是（ NFA ）的一個(gè)特例。（）2若二個(gè)正規(guī)式所表示的（ 正規(guī)集 ）相同，則認(rèn)為二者是等價(jià)的。（）3一個(gè)字集是正規(guī)的，當(dāng)且僅當(dāng)它可由（ DFA/NFA）所 （識(shí)別） 。（）判斷題：1錯(cuò)誤2錯(cuò)誤3錯(cuò)誤4正確5正確6正確7正確8正確9錯(cuò)誤10正確綜合題：1設(shè)M（x,y, a,b, f,x,y）為一非確定的有限自動(dòng)機(jī)，其中f定義如下：f（x,a）x,yf（a,b）yf（y,a） f（y,b）x,y 試構(gòu)造相應(yīng)的確定有限自動(dòng)機(jī)M。（）解答：對照自動(dòng)機(jī)的定義M=(S,f,S0,Z)， 由f的定義可知f(x,a)、f(y,b)均為多值函數(shù)，所以是一非確定有限自

17、動(dòng)機(jī)，先畫出NFAM相應(yīng)的狀態(tài)圖，如圖下所示。圖NFAM用子集法構(gòu)造狀態(tài)轉(zhuǎn)換矩陣下表所示。 將轉(zhuǎn)換矩陣中的所有子集重新命名而形成下表所示的狀態(tài)轉(zhuǎn)換矩陣。表狀態(tài)轉(zhuǎn)換矩陣即得到M（0,1,2, a,b, f,0, 1,2），其狀態(tài)轉(zhuǎn)換圖如下圖所示。將上圖的DFAM 最小化。首先，將M的狀態(tài)分成終態(tài)組1，2與非終態(tài)組0；其次，考察1,2。由于1,2a=1,2b=21,2， 所以不再將其劃分了，也即整個(gè)劃分只有兩組0，1,2：令狀態(tài)1代表1,2，即把原來到達(dá)2的弧都導(dǎo)向1，并刪除狀態(tài)2。 最后，得到如下圖所示化簡DFAM。 圖化簡后的DFAM2對給定正規(guī)式b*（d|ad）（b|ab）+，構(gòu)造其NFAM

18、。（）解答：首先用A+=AA*改造正規(guī)式得：b*(d|ad)(b|ab)(b|ab)*； 其次，構(gòu)造該正規(guī)式的NFAM，如下圖所示。圖NFAM3字母表a，b上的正規(guī)式R=（ba|a）*，構(gòu)造R的相應(yīng)DFA。（）解答：IIaIbx1y1y21y1y221y IIaIb12322332 4請寫出在=（a,b）上，不是a開頭的，但以aa結(jié)尾的字符串集合的正規(guī)表達(dá)式，并構(gòu)造與之等價(jià)狀態(tài)最少的DFA。（）解答：根據(jù)題意，不以a開頭就意味著以b開頭，且以aa結(jié)尾的正規(guī)式為：b(a|b)* aa根將圖1所示的NFA確定化，如圖2所示。NFA將圖1所示的NFA確定化，如圖從圖2可知已為最簡

19、狀態(tài)，由于開始狀態(tài)0只能輸入字符b而不能與狀態(tài)1合并，而狀態(tài)2和狀態(tài)3面對輸入符號的下一狀態(tài)相同，但兩者一為非終態(tài)、一為終態(tài)，故也不有合并，故圖2所示的狀態(tài)轉(zhuǎn)換矩陣已是最簡的DFA，如圖3所示據(jù)正規(guī)式畫出NFA，如圖1所示。 圖2狀態(tài)轉(zhuǎn)換矩陣圖3最簡DFA5. 人運(yùn)狼、羊、菜過河，一次運(yùn)一件，不讓羊吃掉菜，也不讓狼吃掉羊，畫出渡河的狀態(tài)轉(zhuǎn)換圖?？煞駥⑵涑橄鬄橐粋€(gè)有限自動(dòng)機(jī)。（）解答：先寫出渡河的方法，串中對象順序?yàn)槿藖砘囟珊訒r(shí)所運(yùn)的貨物的順序：羊空菜羊狼空羊羊空狼羊菜空羊現(xiàn)給出一個(gè)NFA:M=(,Q,0,9,)其中=羊，空，菜，狼Q=0,1,2,3,4,5,6,7,8,9轉(zhuǎn)形函數(shù)(0,羊)=1

20、,  (1,空)=2,  (2,菜)=3,  (2,狼)=5(3,羊)=4,  (5,羊)=6,  (4,狼)=7,  (6,菜)=7(7,空)=8,  (8,羊)=96對于正規(guī)表達(dá)式 (a|b)*a(a|b) 構(gòu)造最小狀態(tài)的DFA。（）解答：NFA M:DFA M:化簡:   中的DFA M中沒有等價(jià)狀態(tài)，因此為最小化的DFA M。第四章 語法分析多項(xiàng)選擇題：1.AD2.CE3.ACDE4.CE5.ABCE6.ACDE填空題：1對于一

21、個(gè)文法，如果能夠構(gòu)造 （LR(0)文法） 。使得它的 （每個(gè)入口） 均是唯一確定的，則稱該文法為LR文法。（）2字的前綴是指該字的 （任意首部） 。（）3活前綴是指（規(guī)范句型）的一個(gè)前綴，這種前綴不含（句柄）之后的任何符號。（）4在LR分析過程中，只要 （輸入串） 的已掃描部分保持可歸約成一個(gè) （活前綴） ，則掃描過的部分正確。（）5將識(shí)別 （活前綴） 的NFA確定化，使其成為以 （項(xiàng)目集合） 為狀態(tài)的DFA，這個(gè)DFA就是建立 （LR分析算法） 的基礎(chǔ)。（）6A·稱為 （歸約） 項(xiàng)目；對文法開始符S·為 （接受） 項(xiàng)目；若a為終結(jié)符，則稱A·a為 （移進(jìn)） 項(xiàng)目

22、；若B為非終結(jié)符，則稱A·a為 （待約） 項(xiàng)目。（）7LR（0）分析法的名字中“L”表示 （自左至右分析） ，“R”表示 （采用最右推導(dǎo)的逆過程即最左歸約） ，“0”表示 （向右查看0個(gè)字符） 。（）判斷題：1正確簡答題：綜合題：1構(gòu)造下面文法的LL（1）分析表。（）DTLTint | realLid RR, id R | 解答：LL（1）分析表見下表。分析雖然這個(gè)文法很簡單，我們還是從求開始符號集合和后繼符號集合開始。FIRST（D）=FIRST（T）=int, realFOLLOW（D）=FOLLOW（L）=#FIRST（L）=idFOLLOW（T）=idFIRST（R）=，,

23、FOLLOW（R）=#有了上面每個(gè)非終結(jié)符的FIRST集合，填分析表時(shí)要計(jì)算一個(gè)產(chǎn)生式右部的FIRST（）就不是件難事了。填表時(shí)唯一要小心的時(shí)，是產(chǎn)生式R右部的一個(gè)開始符號，而#在FOLLOW（R）中，所以R填在輸入符號#的欄目中。表LL（1）分析表2下面文法GS是否為LL（1）文法？說明理由。（） SAB|PQxAxyBbc PdP| QaQ|解答：該文法不是LL（1）文法，見下面分析中的說明。分析只有三個(gè)非終結(jié)符有兩個(gè)選擇。（1）P的兩個(gè)右部dP和的開始符號肯定不相交。（2）Q的兩個(gè)右部aQ和的開始符號肯定不相交。（3）對S來說，由于xFIRST(AB)，同時(shí)也有xFIRST(PQx)（因

24、為P和Q都可能為空）。所以該文法不是LL（1）文法。3設(shè)有以下文法：（）GS：SaAbDe|dABSD|eBSAc|cD|DSe|（1）求出該文法的每一個(gè)非終結(jié)符U的FOLLOW集。（2）該文法是LL（1）文法嗎？（3）構(gòu)造CS的LL（1）分析表。解答：（1）求文法的每一個(gè)非終結(jié)符U的FOLLOW集的過程如下：因?yàn)椋篠是識(shí)別符號，且有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

25、（A）=FIRST（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）分析表如下表所示。表GS的LL（1）分析表4

26、將文法GV改造成為LL(1)的。（）GV：VN|NEEV|V+ENi解答：對文法GV提取公共左因子后得到文法：GV：VNAA|EEVBB|+ENi求出文法GV中每一個(gè)非終結(jié)符號的FIRST集：FIRST(V)=iFIRST(A)=,FIRST(E)=iFIRST(B)=+,FIRST(N)=i求出文法GV中每一個(gè)非終結(jié)符號的FOLLOW集：FOLLOW(V)=#FIRST(B)FOLLOW(E)=#,+,FOLLOW(A)= FOLLOW(V)=+,#FOLLOW(E)= FIRST()FOLLOW(B)= FIRST()FOLLOW(E)=FOLLOW(B)= FOLLOW(E)= FOLL

27、OW(N)= FIRST(A)FOLLOW(V)=,+,#可以看到，對文法GV的產(chǎn)生式A|E，有FIRST(E)FOLLOW(A)=+,#=對產(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）若輸入符號串“aaaa”，請給出語法分析過程。解答：（1）因?yàn)楫a(chǎn)生式AaAa|有空產(chǎn)生式右部，而FOLLOW(A)=#FIRST(a)=a, #造成FIRST(A)FOLL

28、OW(A)=A,a, #所以該文法不是LL（1）文法。（2）若采用LL（1）方法進(jìn)行語法分析，必須修改該文法。因該文法產(chǎn)生偶數(shù)（可以為0）個(gè)a，所以得到文法GA：AaaA|此時(shí)對產(chǎn)生式AaaA|，有FOLLOW(A)=#FOLLOW(A)=#，因而FIRST(A)FOLLOW(A)=a,#=所以文法GA是LL（1）文法， 按LL（1）分析表構(gòu)造算法構(gòu)造該文法的LL（1）分析表如下表所示。表文法GA的LL(1)分析表 （3）若采用LL(1)方法進(jìn)行語法分析， 對符號串“aaaa”的分析過程如下表所示。表對符號串“aaaa”的分析過程6設(shè)有文法GS為：（）Sa|b|(A)ASdA|S（1）完成下列

29、算符優(yōu)先關(guān)系表，見下表，并判斷GS是否為算符優(yōu)先文法。表算符優(yōu)先關(guān)系表（2）給出句型（SdSdS）的短語、簡單短語、句柄、素短語和最左素短語。（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,

30、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)系表，見下表。表算符優(yōu)先關(guān)系表由上表可

31、以看出，任何兩個(gè)終結(jié)符之間至少只滿足、三種優(yōu)先關(guān)系之一，故GS為算符優(yōu)先文法。（2）為求出句型（SdSdS）的短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹，如下圖所示。由圖得到：短語：S，SdS，SdSdS，（SdSdS）簡單短語（即直接短語）：S句柄（即最左直接短語）：S素短語：SdS，它同時(shí)也是該句型的最左素短語。圖句型（SdSdS）的語法樹（3）輸入串（adb）#的分析過程見下表。表輸入串（adb）#的分析過程7設(shè)有文法GS為：（）Sa|b|(A)ASdA|S（1）完成下列算符優(yōu)先關(guān)系表，見下表，并判斷GS是否為算符優(yōu)先文法。表算符優(yōu)先關(guān)系表（2）給出句型（SdSdS）的短語、簡單

32、短語、句柄、素短語和最左素短語。（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)系表方法如下：對Pab，或PaQb，有ab；對PaR，而bFIRSTVT(R)，有ab；

33、對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)系表，見下表。表算符優(yōu)先關(guān)系表由上表可以看出，任何兩個(gè)終結(jié)符之間至少只滿足、三種優(yōu)先關(guān)系之一，故GS為算符優(yōu)先文法。（2）為求出句型（SdSdS）的

34、短語、簡單短語、句柄，我們先畫出該句型對應(yīng)的語法樹，如下圖所示。由圖得到：短語：S，SdS，SdSdS，（SdSdS）簡單短語（即直接短語）：S句柄（即最左直接短語）：S素短語：SdS，它同時(shí)也是該句型的最左素短語。圖句型（SdSdS）的語法樹（3）輸入串（adb）#的分析過程見下表。表輸入串（adb）#的分析過程8對于文法GS： SAS|bASA|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)目是：1S·S5SAS· 9AS·A 2SS·

35、6S·b10ASA·3S·AS 7Sb· 11A·a4SA·S 8A·SA 12Aa·（2）用-CLOSURE（閉包）辦法構(gòu)造文法G的LR（0）項(xiàng)目集規(guī)范族如下： I0：1S·S I3：9AS·A I6：12Aa·3S·AS 8A·SA I7： 7Sb·8A·SA 3S·AS 11A·a 6S·b6S·b 11A·aI1：2SS· I4：10.ASA·9AS·A 4.

36、SA·S 8A·SA 3.S·AS 11A·a 6.S·b3.S·AS 8.A·SA 6.S·b 11.A·aI2：4SA·SI5： 5SAS·3S·AS 9AS·A 6S·b 8A·SA 8A·SA 11A·a 11A·a 3S·AS 6S·b注意：I1中的SS·和A·SA是由狀態(tài)I0中的1和3讀入一個(gè)S字符后得到的下一個(gè)項(xiàng)目；，而I4中的ASA和AA·S則是由I3

37、中的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ī)范族。9有文法GS Sa|（T） TT，S|S 該文法是否是LL（1）文法，若不是，請進(jìn)行改寫。并給出它的分析表。（）解答：不是。TST'T'T，S|SFIRST(S)=FIRST(T)=a,（FIRST(T')=，, FOLLOW(S)=#,，)FOLLOW(T')=FOLLOW(T)= ）分析表如下：10有文法GS（1）SA（2）SB（3）AaAb（4）Ac（5）BaBb（6）Bd

38、試構(gòu)造相應(yīng)的LR（0）項(xiàng)目集規(guī)范族及相應(yīng)的分析表。（）解答：11. 已知文法GS，其產(chǎn)生式如下：        S(L)|a    L L，S|S     從GS中消除左遞歸，并為之構(gòu)造一個(gè)非遞歸預(yù)測分析器LL(1)分析表。請說明在句子(a，(a，a)上的分析器的動(dòng)作。 （）答：將所給文法消除左遞歸得G'：        S (L)|a   

39、;      L SL'         L' ，SL' | 實(shí)現(xiàn)預(yù)測分析器的不含遞歸調(diào)用的一種有效方法是使用一張分析表和一個(gè)棧進(jìn)行聯(lián)合控制，下面構(gòu)造預(yù)測分析表：根據(jù)文法G'有FIRST(s) = ( , a )FOLLOW(S) = ) , ', ' , $ FIRST(L) = ( , a )FOLLOW(L) = ) FIRST(L) = ', ' FOLLOW(L) = ) 按以上結(jié)果

40、，構(gòu)造預(yù)測分析表M如下：文法G是LL(1)的，因?yàn)樗腖L(1)分析表不含多重定義入口。預(yù)測分析器對輸入符號串(a, (a, a)做出的分析動(dòng)作如下：12. 證明下面文法是SLR(1)文法，并構(gòu)造其SLR分析表。     EE+T|T          TTF|F          FF*|a|b （）答：該文法的拓廣文法G'為 (0) E' E(1) E E+T(2)

41、E T(3) T TF(4) T F(5) F F*(6) F a(7) F b其LR(0)項(xiàng)目集規(guī)范族和goto函數(shù)(識(shí)別活前綴的DFA)如下:I0 = E'·E, E·E+T, E·T, T·TF, T·F, F·F*,        F·a, F·bI1 = E'E·, EE·+TI2 = ET·, TT·F, F·F*, F·a, F·bI3

42、= TF·, FF·*I4 = Fa·I5 = Fb·I6 = EE+·T, T·TF, T·F, F·F*, F·a, F·bI7 = TTF·, FF·*I8 = FF*·I9 = EE+T·, TT·F, F·F*, F·a, F·b求FOLLOW集：    FOLLOW(E)=,     FOLLOW(T)=, , a, b

43、60;   FOLLOW(F)=, , a, b, *構(gòu)造的SLR分析表如下： 顯然，此分析表無多重定義入口，所以此文法是SLR文法第五章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成多項(xiàng)選擇題：1.ACDE2.BCD3.BC 4.BD5.BCE填空題：1中間代碼有 （逆波蘭記號）、（樹形表示）、（三元式）、（四元式） 等形式，生成中間代碼主要是為了使 （目標(biāo)代碼的優(yōu)化容易實(shí)現(xiàn)） 。（）2語法制導(dǎo)翻譯既可以用來產(chǎn)生 （中間） 代碼，也可以用來產(chǎn)生 （目標(biāo)） 指令，甚至可用來對輸入串進(jìn)行 （解釋執(zhí)行） 。（）3當(dāng)源程序中的標(biāo)號出現(xiàn)“先引用后定義”時(shí)，中間代碼的轉(zhuǎn)移地址須持 （標(biāo)號定義） 時(shí)才能確定，因而要進(jìn)行 （回填） 。（）4文法符號的屬性有兩種，一種稱為 （繼承屬性） ，另一種稱為 （綜合屬性） 。（）5后綴式abc-/所代表的表達(dá)式是（ a/(b-c) ），表達(dá)式(a-b)*c可用后綴式（ ab-c* ）表示。（）6用一張 （間接碼表） 輔以 （三元式表） 的辦法來表示中間代碼，這種表示法稱為間接三元式。（）問答題：1給出下列表達(dá)式的逆波蘭表示（后綴式）：（）a*(-b+c)(AB)(CDE)解答：abc+*;ABCDE2寫出算術(shù)表達(dá)式：A+B*(C-D)+E/(C-D)N的：（）四元式序列；三元式序列；間接三元式序列解答：3寫出