編譯原理教程課后習(xí)題答案——第三章

1、精選優(yōu)質(zhì)文檔-傾情為你奉上第三章 語法分析 3.1 完成下列選擇題： (1) 文法G：SxSx|y所識(shí)別的語言是 。 a. xyx b. (xyx)* c. xnyxn(n0) d. x*yx*(2) 如果文法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)，但它們對(duì)應(yīng)的語法樹相同(3) 采用自上而下分析，必須 。a. 消除左遞a. 必有ac歸 b. 消除右遞歸c. 消除回溯 d. 提取公共左因子(4) 設(shè)a、b、c是文法的終結(jié)符，且滿足優(yōu)先關(guān)系ab和bc，

2、則 。b. 必有cac. 必有ba d. ac都不一定成立(5) 在規(guī)范歸約中，用 來刻畫可歸約串。 a. 直接短語 b. 句柄 c. 最左素短語 d. 素短語(6) 若a為終結(jié)符，則A·a為 項(xiàng)目。 a. 歸約 b. 移進(jìn) c. 接受 d. 待約(7) 若項(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)文法(8) 同心集合并有可能產(chǎn)生新的 沖突。a. 歸約 b. “移進(jìn)”/“移進(jìn)” c.“移進(jìn)”/“歸約” d. “歸約

3、”/“歸約”【解答】 (1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d3.2 令文法GN為 GN: ND|ND D0|1|2|3|4|5|6|7|8|9(1) GN的語言L(GN)是什么? (2) 給出句子0127、34和568的最左推導(dǎo)和最右推導(dǎo)?！窘獯稹?(1) GN的語言L(GN)是非負(fù)整數(shù)。(2) 最左推導(dǎo)：NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568最右推導(dǎo)：NNDN7ND7N27ND27N127D NNDN4D434 NNDN8ND8N68D685683.3 已知

4、文法GS為SaSb|Sb|b，試證明文法GS為二義文法?！窘獯稹?由文法GS：SaSb|Sb|b，對(duì)句子aabbbb可對(duì)應(yīng)如圖3-1所示的兩棵語法樹。圖3-1 句子aabbbb對(duì)應(yīng)的兩棵不同語法樹 因此，文法GS為二義文法(對(duì)句子abbb也可畫出兩棵不同語法樹)。3.4 已知文法GS為SSaS|，試證明文法GS為二義文法。【解答】 由文法GS：SSaS|，句子aa的語法樹如圖3-2所示。 圖3-2 句子aa對(duì)應(yīng)的兩棵不同的語法樹 由圖3-2可知，文法GS為二義文法。3.5 按指定類型，給出語言的文法。 (1) L=aibj|ji0的上下文無關(guān)文法；(2) 字母表=a,b上的同時(shí)只有奇數(shù)個(gè)a和奇

5、數(shù)個(gè)b的所有串的集合的正規(guī)文法；(3) 由相同個(gè)數(shù)a和b組成句子的無二義文法?！窘獯稹?(1) 由L=aibj|ji0知，所求該語言對(duì)應(yīng)的上下文無關(guān)文法首先應(yīng)有SaSb型產(chǎn)生式，以保證b的個(gè)數(shù)不少于a的個(gè)數(shù)；其次，還需有SSb或Sb型的產(chǎn)生式，用以保證b的個(gè)數(shù)多于a的個(gè)數(shù)。因此，所求上下文無關(guān)文法GS為GS：SaSb|Sb|b(2) 為了構(gòu)造字母表=a,b上同時(shí)只有奇數(shù)個(gè)a和奇數(shù)個(gè)b的所有串集合的正規(guī)式，我們畫出如圖3-3所示的DFA，即由開始符S出發(fā)，經(jīng)過奇數(shù)個(gè)a到達(dá)狀態(tài)A，或經(jīng)過奇數(shù)個(gè)b到達(dá)狀態(tài)B；而由狀態(tài)A出發(fā)，經(jīng)過奇數(shù)個(gè)b到達(dá)狀態(tài)C(終態(tài))；同樣，由狀態(tài)B出發(fā)經(jīng)過奇數(shù)個(gè)a到達(dá)終態(tài)C。由

6、圖3-3可直接得到正規(guī)文法GS如下： GS：SaA|bB AaS|bC|b BbS|aC|a CbA|aB|圖3-3 習(xí)題3.5的DFA(3) 我們用一個(gè)非終結(jié)符A代表一個(gè)a(即有Aa)，用一個(gè)非終結(jié)符B代表一個(gè)b(即有Bb)；為了保證a和b的個(gè)數(shù)相同，則在出現(xiàn)一個(gè)a時(shí)應(yīng)相應(yīng)地出現(xiàn)一個(gè)B，出現(xiàn)一個(gè)b時(shí)則相應(yīng)出現(xiàn)一個(gè)A。假定已推導(dǎo)出bA，如果下一步要推導(dǎo)出連續(xù)兩個(gè)b時(shí)，則應(yīng)有bAbbAA。也即為了保證b和A的個(gè)數(shù)一致，應(yīng)有AbAA；同理有BaBB。此外，為了保證遞歸地推出所要求的ab串，應(yīng)有SaBS和SbAS。由此得到無二義文法GS為 GS：SaBS|bAS| AbAA|a BaBB|b3.6

7、有文法GS: SaAcB|BdAAaB|cBbScA|b(1) 試求句型aAaBcbbdcc和aAcbBdcc的句柄；(2) 寫出句子acabcbbdcc的最左推導(dǎo)過程?！窘獯稹?(1) 分別畫出對(duì)應(yīng)句型aAaBcbbdcc和aAcbBdcc的語法樹如圖3-4的(a)、(b)所示。圖3-4 習(xí)題3.6的語法樹 (a) aAaBcbbdcc; (b) aAcbBdcc 對(duì)樹(a)，直接短語有3個(gè)：AaB、b和c，而AaB為最左直接短語(即為句柄)。對(duì)樹(b)，直接短語有兩個(gè)：Bd和c，而Bd為最左直接短語。能否不畫出語法樹，而直接由定義(即在句型中)尋找滿足某個(gè)產(chǎn)生式的候選式這樣一個(gè)最左子串(即

8、句柄)呢？例如，對(duì)句型aAaBcbbdcc，我們可以由左至右掃描找到第一個(gè)子串AaB，它恰好是滿足AAaB右部的子串；與樹(a)對(duì)照，AaB的確是該句型的句柄。是否這一方法始終正確呢？我們繼續(xù)檢查句型aAcbBdcc，由左至右找到第一個(gè)子串c，這是滿足AC右部的子串，但由樹(b)可知，c不是該句型的句柄。由此可知，畫出對(duì)應(yīng)句型的語法樹然后尋找最左直接短語是確定句柄的好方法。(2) 句子acabcbbdcc的最左推導(dǎo)如下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc3.7 對(duì)于文法GS: S(L)|aS|aLL,S

9、|S(1) 畫出句型(S,(a)的語法樹；(2) 寫出上述句型的所有短語、直接短語、句柄、素短語和最左素短語?！窘獯稹?(1) 句型(S, (a)的語法樹如圖3-5所示。圖3-5 句型(S,(a)的語法樹 (2) 由圖3-5可知：短語：S、a、(a)、S,(a)、(S,(a)；直接短語：a、S；句柄：S；素短語：素短語可由圖3-5中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得，即： # (， (a)#因此，素短語為a。3.8 下述文法描述了C語言整數(shù)變量的聲明語句：GD: DTLTint|long|shortLid|L,id(1) 改造上述文法，使其接受相同的輸入序列，但文法是右遞歸的；(2) 分別用上述文法

10、GD和改造后的文法GD為輸入序列int a,b,c構(gòu)造分析樹?！窘獯稹?(1) 消除左遞歸后，文法GD如下：DTLTint|long|shortLidL圖3-6 兩種文法為int a,b,c構(gòu)造的分析樹 (a) 文法G(D)； (b) 文法G(D)3.9 考慮文法GS: S(T) | a+S | aTT,S | S消除文法的左遞歸及提取公共左因子，然后對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序?！窘獯稹?消除文法GS的左遞歸：S(T) | a+S | aTSTT,ST| 提取公共左因子：S(T) | aSS+S | TSTT,ST| 改造后的文法已經(jīng)是LL(1)文法，不帶回溯的遞歸子程序如下：vo

11、id match (token t) if ( lookahead=t)lookahead=nexttoken; else error ( );void S ( ) if ( lookahead=a)match (a);else if ( lookahead=()match ();T ( );void S( ) if ( lookahead=+)match (+);S ( );void T ( ) S ( );T( );void T ( ) if ( lookahead=, )match (, );S ( );T ( );3.10 已知文法GA: AaABl|aBBb|d(1) 試給出與GA等

12、價(jià)的LL(1)文法GA；(2) 構(gòu)造GA的LL(1)分析表；(3) 給出輸入串a(chǎn)adl#的分析過程。【解答】 (1) 文法GA存在左遞歸和回溯，故其不是LL(1)文法。要將GA改造為LL(1)文法，首先要消除文法的左遞歸，即將形如PP | 的產(chǎn)生式改造為PPPP| 來消除左遞歸。由此，將產(chǎn)生式BBb|d改造為BdBBbB| 其次，應(yīng)通過提取公共左因子的方法來消除GA中的回溯，即將產(chǎn)生式AaABl|a改造為AaAAABl | 最后得到改造后的文法為GA：AaAAABl | BdBBbB| 求得： FIRST(A)=a FIRST(A)=a, FIRST(B)=d FIRST(B)=b, 對(duì)文法開

13、始符號(hào)A，有FOLLOW(A)=#。由AABl得FIRST(B) ÌFOLLOW(A)，即FOLLOW(A)=#,d； 由AABl得FIRST(l) ÌFOLLOW(B)，即FOLLOW(B)=l；由AaA得FOLLOW(A) ÌFOLLOW(A)，即FOLLOW(A)=#,d；由BdB得FOLLOW(B) ÌFOLLOW(B)，即FOLLOW(B)=l。 對(duì)AABl來說，F(xiàn)IRST(A)FOLLOW(A)=a#,d=，所以文法GA為所求等價(jià)的LL(1)文法。(2) 構(gòu)造預(yù)測分析表的方法如下： 對(duì)文法GA的每個(gè)產(chǎn)生式A執(zhí)行、步。 對(duì)每個(gè)終結(jié)符aFIRST

14、(A)，把A加入到MA,a中，其中為含有首字符a的候選式或?yàn)槲ㄒ坏暮蜻x式。 若FIRST(A)，則對(duì)任何屬于FOLLOW(A)的終結(jié)符b，將A加入到MA,b中。把所有無定義的MA,a標(biāo)記上“出錯(cuò)”。由此得到GA的預(yù)測分析表，見表3-1。表3-1 預(yù)測分析表 (3) 輸入串a(chǎn)adl的分析過程見表3-2。 表3-2 輸入串a(chǎn)adl的分析過程 3.11 將下述文法改造為LL(1)文法： GV: VN | NEEV | V+ENi【解答】 LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子)，而文法GV中含有回溯，所以先消除回溯，得到文法GV： G V：VNVV | EEVEE | +ENi一個(gè)L

15、L(1)文法的充要條件是：對(duì)每一個(gè)終結(jié)符A的任何兩個(gè)不同產(chǎn)生式A|有下面的條件成立：(1) FIRST()FIRST()=； (2) 假若，則有FIRST()FOLLOW(A)= 。即求出GV的FIRSTVT和LASTVT集如下：FIRST(N)=FIRST(V)=FIRST(E)=iFIRST(V)=, FIRST(E)=+, FOLLOW(V)=#由VE得FIRST() ÌFOLLOW(E)，即FOLLOW(E)= ；由VNV得FIRST(V) Ì FOLLOW(N)，即FOLLOW(N)= ；由EVE得FIRST(E) ÌFOLLOW(V)，即FOLLOW(

16、V)=#,+；由VNV得FOLLOW(V) ÌFOLLOW(V)，即FOLLOW(V)=#,+；由VNV，且V得FOLLOW(V) ÌFOLLOW(N)，即FOLLOW(N)=,#,+；由EVE得FOLLOW(E) ÌFOLLOW(E)，即FOLLOW(E)= ；則，對(duì)V |E有：FIRST()FIRST(= ；對(duì)E | +E有：FIRST()FIRST(+)= ；對(duì)V | E有：FIRST()FOLLOW(V)=#,+=；對(duì)E | +E有：FIRST(+)FOLLOW(E)=+=。故文法GV為LL(1)文法。3.12 對(duì)文法GE: EE+T|T TT*P|P P

17、i (1) 構(gòu)造該文法的優(yōu)先關(guān)系表(不考慮語句括號(hào)#)，并指出此文法是否為算符優(yōu)先文法；(2) 構(gòu)造文法G的優(yōu)先函數(shù)。【解答】 FIRSTVT集構(gòu)造方法： 由Pa或PQa，則aFIRSTVT(P)。 若aFIRSTVT(Q)，且PQ，則aFIRSTVT(P)，也即FIRSTVT(Q)ÌFIRSTVT(P)。由得：由EE+得FIRSTVT(E)=+； 由TT*得FIRSTVT(T)=*； 由Pi得FIRSTVT(P)=i。由得：由TP得FIRSTVT(P)ÌFIRSTVT(T)，即FIRSTVT(T)=*，i； 由ET得FIRSTVT(T)ÌFIRSTVT(E)，即

18、FIRSTVT(T)=+，*，i。LASTVT集構(gòu)造方法： 由Pa或PaQ, 則aLASTVT(P)。 若aLASTVT(Q)，且PQ，則aLASTVT(P)，也即LASTVT(Q)ÌLASTVT(P)。由得：E+T，得LASTVT(E)=+； T*P，得LASTVT(T)=*； Pi，得LASTVT(P)=i。由得：由TP得LASTVT(P)ÌLASTVT(T)，即LASTVT(T)=*，i； 由ET得LASTVT(T)ÌLASTVT(E)，即LASTVT(E)=+，*，i。優(yōu)先關(guān)系表構(gòu)造方法： 對(duì)Pab或PaQb，有ab； 對(duì)PaR而bFIRSTVT(R)，有

19、ab； 對(duì)PRb而aLASTVT(R)，有ab。解之無。由得：E+T，即+FIRSTVT(T)，有+*，+i； T*P，即*FIRSTVT(P)，有*i。由得：EE+，即LASTVT(E)+，有+，*+，i+； TT*，即LASTVT(T)*，有*，i*。得到優(yōu)先關(guān)系表見表3-3。由于該文法的任何產(chǎn)生式的右部都不含兩個(gè)相繼并列的非終結(jié)符，故屬算符文法，且該文法中的任何終結(jié)符對(duì)(見優(yōu)先關(guān)系表)至多滿足、和三種關(guān)系之一，因而是算符優(yōu)先文法。表3-3 習(xí)題3.12的優(yōu)先關(guān)系表 用關(guān)系圖構(gòu)造優(yōu)先函數(shù)的方法是：對(duì)所有終結(jié)符a用有下腳標(biāo)的fa、ga為結(jié)點(diǎn)名畫出全部終結(jié)符所對(duì)應(yīng)的結(jié)點(diǎn)。若存在優(yōu)先關(guān)系ab或a

20、b，則畫一條從fa到ga的有向??；若ab或ab，則畫一條從g b到f a的有向弧。最后，對(duì)每個(gè)結(jié)點(diǎn)都賦一個(gè)數(shù)，此數(shù)等于從該結(jié)點(diǎn)出發(fā)所能到達(dá)的結(jié)點(diǎn)(包括出發(fā)結(jié)點(diǎn))的個(gè)數(shù)，賦給fa的數(shù)作為f(a)，賦給gb的數(shù)作為g(b)。用關(guān)系圖法構(gòu)造本題的優(yōu)先函數(shù)，如圖3-7所示。得到優(yōu)先函數(shù)見表3-4。 表3-4 習(xí)題3.12的優(yōu)先函數(shù)表 圖3-7 習(xí)題3.12關(guān)系圖構(gòu)造該優(yōu)先函數(shù)表經(jīng)檢查與優(yōu)先關(guān)系表沒有矛盾，故為所求優(yōu)先函數(shù)。也可由定義直接構(gòu)造優(yōu)先函數(shù)，其方法是：對(duì)每個(gè)終結(jié)符a，令f(a)=g(a)=1；如果ab，而f(a)g(b)，則令f(a)=g(b)+1；如果ab，而f(a)g(b)，則令g(b)=

21、f(a)+1；如果ab，而f(a)g(b)，則令minf(a),g(b)=maxf(a),g(b)。重復(fù)上述過程，直到每個(gè)終結(jié)符的函數(shù)值不再變化為止。如果有一個(gè)函數(shù)值大于2n(n為終結(jié)符個(gè)數(shù))，則不存在優(yōu)先函數(shù)。優(yōu)先函數(shù)的計(jì)算過程如表3-5所示。 表3-5 優(yōu)先函數(shù)的計(jì)算過程表計(jì)算最終收斂，并且計(jì)算得出的優(yōu)先函數(shù)與關(guān)系圖構(gòu)造得出的優(yōu)先函數(shù)是一樣的。3.13 設(shè)有文法GS: Sa|b|(A)ASdA|S(1) 構(gòu)造算符優(yōu)先關(guān)系表；(2) 給出句型(SdSdS)的短語、簡單短語、句柄、素短語和最左素短語；(3) 給出輸入串(adb)#的分析過程。【解答】(1) 先求文法GS的FIRSTVT集和LA

22、STVT集：由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而bFIRSTVT(R)，有ab； 對(duì)PRb而aFIRSTVT(R)，有ab。由此得到： 由S(A)得()； 由S(A得(FIRSTVT

23、(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)#得a#, b#, )#。最后得到算符優(yōu)先關(guān)系表，見表3-6。表3-6 習(xí)題3.13的算符優(yōu)先關(guān)系表 由表3-6可以看出，任何兩個(gè)終結(jié)符之間至多只滿足、三種優(yōu)先關(guān)系之一，故GS為算符優(yōu)先文法。(2) 為求出句型(SdSdS)的短語、簡單短語、句柄，我們先畫出該句型對(duì)應(yīng)的語法樹，如圖3-8所示。圖3-8

24、句型(SdSdS)的語法樹 由圖3-8得到：短語：S，SdS，SdSdS，(SdSdS) 注意，句型中的素短語具有如下形式： aj-1ajaj+1aiai+1 而最左素短語就是該句型中所找到的最左邊的那個(gè)素短語，即最左素短語必須具備三個(gè)條件： 至少包含一個(gè)終結(jié)符(是否包含非終結(jié)符則按短語的要求確定)； 除自身外不得包含其他素短語(最小性)； 在句型中具有最左性。 圖3-9 句型(SdSdS)的優(yōu)先關(guān)系 簡單短語(即直接短語)：S句柄(即最左直接短語)：S可以通過分析圖3-8的語法樹來求素短語和最左素短語，即找出語法樹中的所有相鄰終結(jié)符(中間可有一個(gè)非終結(jié)符)之間的優(yōu)先關(guān)系。確定優(yōu)先關(guān)系的原則是

25、： 同層的優(yōu)先關(guān)系為； 不同層時(shí)，層次離樹根遠(yuǎn)者優(yōu)先級(jí)高，層次離樹根近者優(yōu)先級(jí)低(恰好驗(yàn)證了優(yōu)先關(guān)系表的構(gòu)造算法)； 在句型兩側(cè)加上語句括號(hào)“#”，即#，則有#和#，由此我們得到句型(SdSdS)的優(yōu)先關(guān)系如圖3-9所示。因此，由圖3-9得到SdS為句型(SdSdS)的素短語，它同時(shí)也是該句型的最左素短語。(3) 輸入串(adb)#的分析過程見表3-7。表3-7 輸入串(adb)#的分析過程為便于分析，同時(shí)給出了(adb)#的語法樹，如圖3-10所示。 圖3-10 (adb)的語法樹 3.14 在算符優(yōu)先分析法中，為什么要在找到最左素短語的尾時(shí)才返回來確定其對(duì)應(yīng)的頭，能否按掃描順序先找到頭后再

26、找到對(duì)應(yīng)的尾，為什么？ 【解答】 設(shè)句型的一般形式為N1a1N2a2NnanNn+1。其中，每個(gè)ai都是終結(jié)符，而Ni則是可有可無的非終結(jié)符。對(duì)上述句型可以找出該句型中的所有素短語，每個(gè)素短語都具有如下形式：aj-1ajaj+1aiai+1 如果某句型得到的優(yōu)先關(guān)系如下： 則當(dāng)從左至右掃描到第一個(gè)“”時(shí)，再由此從右至左掃描到第一個(gè)“”時(shí)，它們之間(當(dāng)然不包含第一個(gè)“”前一個(gè)終結(jié)符和第二個(gè)“”后一個(gè)終結(jié)符)即為最左素短語。如果由左至右掃描到第一個(gè)“”，可以看出這并不一定是最左素短語的開頭，因?yàn)橛伤_始并不一定是素短語(在其內(nèi)部還可能包含其他更小的素短語)，所以，在算符優(yōu)先分析算法中，只有先找到最

27、左素短語的尾(即“”)，才返回來確定與其對(duì)應(yīng)的頭(即“”)；而不能按掃描順序先找到頭然后再找到對(duì)應(yīng)的尾。3.15 試證明在算符文法中，任何句型都不包含兩個(gè)相鄰的非終結(jié)符。【解答】 設(shè)文法G=(VT,VN,S, )，其中VT是終結(jié)符集；VN是非終結(jié)符集；為產(chǎn)生式集合；S是開始符號(hào)。對(duì)句型的推導(dǎo)長度n作如下歸納：(1) 當(dāng)n=1時(shí)，S，則存在一條產(chǎn)生式S屬于，其中a(VTVN) *。由于文法是算符文法，所以中沒有兩個(gè)相鄰非終結(jié)符，故歸納初始成立。(2) 設(shè)n=k時(shí)結(jié)論成立，則對(duì)任何k+1步推導(dǎo)所產(chǎn)生的句型必為S其中，、(VTVN) *，UVN，而UV是一條產(chǎn)生式。由歸納假設(shè)，U是非終結(jié)符，設(shè)=12

28、n，=12m，其中i、j (VTVN) (1in-1,2jm) ；但n和m必為位于U兩側(cè)的終結(jié)符。設(shè)V=V1V2Vr，由于它是算符文法的一個(gè)產(chǎn)生式右部候選式，因此V1V2Vr中不會(huì)有相鄰的非終結(jié)符出現(xiàn)。又因?yàn)閚V1和Vr1中的n、1為終結(jié)符，也即在推導(dǎo)長度為k+1時(shí)所產(chǎn)生的句型12nV1V2Vr12m不會(huì)出現(xiàn)相鄰的非終結(jié)符，故n=k+1時(shí)結(jié)論成立。顯然，在或?yàn)榭諘r(shí)結(jié)論也成立。 3.16 給出文法GS: SaSbPPbPcbQc QQaa (1) 它是Chomsky哪一型文法？ (2) 它生成的語言是什么？ (3) 它是不是算符優(yōu)先文法？請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表證實(shí)之；(4) 文法GS消除左遞歸、提

29、取公共左因子后是不是LL(1)文法？請(qǐng)證實(shí)?！窘獯稹?(1) 根據(jù)Chomsky的定義，對(duì)任何形如A的產(chǎn)生式，有AVN，(VTVN)*時(shí)為2型文法。而文法GS恰好滿足這一要求，故為Chomsky 2型文法。(2) 由文法GS可以看出：S推出串的形式是ai P bi(i0)，P推出串的形式是bjQcj(j1)，Q推出串的形式是ak(k1)。因此，文法GS生成的語言是L=aibjakcjbi|i0, j1, k1。(3) 求出文法GS的FIRSTVT集和LASTVT集：FIRSTVT(S)=a,b FIRSTVT(P)=bFIRSTVT(Q)=aLASTVT(S)=b,c LASTVT(P)=cL

30、ASTVT(Q)=a構(gòu)造優(yōu)先關(guān)系表如表3-8所示。由于在優(yōu)先關(guān)系中同時(shí)出現(xiàn)了aa和aa以及bb和bb，故文法GS不是算符優(yōu)先文法。表3-8 優(yōu)先關(guān)系表 (4) 消除文法GS的左遞歸：SaSb | PPbPc | bQcQaQQaQ| 提取公共左因子后得到文法GS:SaSb | PPbPPPc | QcQaQQaQ| 求每個(gè)非終結(jié)符的FIRST集和FOLLOW集如下：FIRST(S)=a,b FIRST(P)=bFIRST(P)=a,b FIRST(Q)=aFIRST(Q)=a, FOLLOW(S)=b,# FOLLOW(P)=b,c,#FOLLOW(P)=b,c,# FOLLOW(Q)=cFO

31、LLOW(Q)=c通過檢查GS可以得到： 每一個(gè)非終結(jié)符的所有候選式首符集兩兩不相交； 存在形如A的產(chǎn)生式QaQ| ，但有 FIRST(aQ)FOLLOW(Q)=ac=所以文法GS是LL(1)文法。*3.17 LR分析器與優(yōu)先關(guān)系分析器在識(shí)別句柄時(shí)的主要異同是什么？【解答】 如果SaA且有A，則稱是句型相對(duì)于非終結(jié)符A的短語。特別的，如果有A，則稱是句型相對(duì)于規(guī)則A的直接短語。一個(gè)句型的最左直接短語稱為該句型的句柄。規(guī)范歸約是關(guān)于的一個(gè)最右推導(dǎo)的逆過程，因此，規(guī)范歸約也稱最左歸約。請(qǐng)注意句柄的“最左”特征。LR分析器用規(guī)范歸約的方法尋找句柄，其基本思想是：在規(guī)范歸約的過程中，一方面記住已經(jīng)歸約

32、的字符串，即記住“歷史”；另一方面根據(jù)所用的產(chǎn)生式推測未來可能碰到的輸入字符串，即對(duì)未來進(jìn)行“展望”。當(dāng)一串貌似句柄的符號(hào)串呈現(xiàn)于棧頂時(shí)，則可根據(jù)歷史、展望以及現(xiàn)實(shí)的輸入符號(hào)等三方面的材料，來確定棧頂?shù)姆?hào)串是否構(gòu)成相對(duì)某一產(chǎn)生式的句柄。事實(shí)上，規(guī)范歸約的中心問題恰恰是如何尋找或確定一個(gè)句型的句柄。給出了尋找句柄的不同算法也就給出了不同的規(guī)范歸約方法，如LR(0)、SLR(1)、LR(1)以及LALR就是在歸約方法上進(jìn)行區(qū)別的。算符優(yōu)先分析不是規(guī)范歸約，因?yàn)樗豢紤]了終結(jié)符之間的優(yōu)先關(guān)系，而沒有考慮非終結(jié)符之間的優(yōu)先關(guān)系。此外，算符優(yōu)先分析比規(guī)范歸約要快得多，因?yàn)樗惴麅?yōu)先分析跳過了所有單非產(chǎn)生

33、式所對(duì)應(yīng)的歸約步驟。這既是算符優(yōu)先分析的優(yōu)點(diǎn)，同時(shí)也是它的缺點(diǎn)，因?yàn)楹雎苑墙K結(jié)符在歸約過程中的作用存在某種危險(xiǎn)性，可能導(dǎo)致把本來不成句子的輸入串誤認(rèn)為是句子，但這種缺陷容易從技術(shù)上加以彌補(bǔ)。為了區(qū)別于規(guī)范歸約，算符優(yōu)先分析中的“句柄”被稱為最左素短語。3.18 什么是規(guī)范句型的活前綴？引進(jìn)它的意義何在？【解答】 在討論LR分析器時(shí)，需要定義一個(gè)重要概念，這就是文法的規(guī)范句型的“活前綴”。字的前綴是指該字的任意首部，例如，字abc的前綴有、a、ab或abc。所謂活前綴，是指規(guī)范句型的一個(gè)前綴，這種前綴不含句柄之后的任何符號(hào)。之所以稱為活前綴，是因?yàn)樵谄溆疫呍鎏硪恍┙K結(jié)符號(hào)后，就可以使它成為一個(gè)規(guī)

34、范句型。引入活前綴的意義在于它是構(gòu)造LR(0)項(xiàng)目集規(guī)范族時(shí)必須用到的一個(gè)重要概念。 對(duì)于一個(gè)文法G，首先要構(gòu)造一個(gè)NFA，它能識(shí)別G的所有活前綴，這個(gè)NFA的每個(gè)狀態(tài)即為一個(gè)“項(xiàng)目”。文法G每一個(gè)產(chǎn)生式的右部添加一個(gè)圓點(diǎn)稱為G的一個(gè)LR(0)項(xiàng)目(簡稱項(xiàng)目)，可以使用這些項(xiàng)目狀態(tài)構(gòu)造一個(gè)NFA。我們能夠把識(shí)別活前綴的NFA確定化，使之成為一個(gè)以項(xiàng)目集為狀態(tài)的DFA，這個(gè)DFA就是建立LR分析算法的基礎(chǔ)。構(gòu)成識(shí)別一個(gè)文法活前綴的DFA項(xiàng)目集(狀態(tài))的全體稱為這個(gè)文法的LR(0)項(xiàng)目集歸范族。 3.19 試構(gòu)造下述文法的SLR(1)分析表。GS: SbASB | bA AdSa | e BcAa

35、 | c【解答】 首先將文法GS拓廣為GS: GS： (0) SS(1)  SbASB(2)  SbA(3)  AdSa(4)  Ae(5)  BcAa(6)  Bc構(gòu)造文法GS的LR(0)項(xiàng)目集規(guī)范族如下： I0: S·S I5: Ae·S·bASB I6: SbAS·BS·bA B·cAaI1: SS· B·cI2: Sb·ASB I7: AdS·aSb·A I8: SbASB·A·dSa I

36、9: Bc·AaA·e Bc·I3: SbA·SB A·dSaSbA· A·eS·bASB I10: AdSa·S·bA I11: BcA·aI4: Ad·Sa I12: BcAa·S·bASBS·bA文法GS的DFA如圖3-11所示。圖3-11 文法GS的DFA 注意，在比較熟練的情況下，也可以不構(gòu)造LR(0)項(xiàng)目集規(guī)范族而直接畫出文法GS的DFA。由于I3和I9既含有移進(jìn)項(xiàng)目又含有歸約項(xiàng)目，故文法GS不是LR(0)文法。我們構(gòu)造文法GS的FO

37、LLOW集如下：(1) FOLLOW(S)=#；(2) 由SAS得FIRST(S) FOLLOW(A)；即FOLLOW(A)=b；由SSB得FIRST(B) FOLLOW(S)；即FOLLOW(S)=c；由ASa得FIRST(a) FOLLOW(S)；即FOLLOW(S)=a,c；(3) 由SS得FOLLOW(S)FOLLOW(S)，即FOLLOW(S)=a,c,#； 由SB得FOLLOW(S)FOLLOW(B)，即FOLLOW(B)=a,c,#； 由SA得FOLLOW(S)FOLLOW(A)，即FOLLOW(A)=a,b,c,#；對(duì)I3有：bFOLLOW(S)=ba,c,#=對(duì)I9有：d,e

38、FOLLOW(B)=d,ea,c,#= 故文法GS是SLR(1)文法。最后得到SLR(1)分析表見表3-9。表3-9 SLR(1)分析表3.20 LR(0)、SLR(1)、LR(1)及LALR有何共同特征？它們的本質(zhì)區(qū)別是什么？【解答】 LR(0)、SLR(1)、LR(1)及LALR的共同特征是都用規(guī)范歸約的方法尋找句柄，即LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)行輸入符號(hào)所唯一決定的。它們的本質(zhì)區(qū)別是尋找句柄的方法不同。如果當(dāng)前的棧頂狀態(tài)為歸約狀態(tài)(即有形如A·的項(xiàng)目屬于棧頂狀態(tài))，則：(1) 對(duì)LR(0)來說，無論現(xiàn)行輸入符號(hào)是什么，都認(rèn)為棧頂?shù)姆?hào)串為句柄而進(jìn)行歸約。 (2)

39、對(duì)SLR(1)來說，則對(duì)現(xiàn)行輸入符號(hào)加了一點(diǎn)限制，即該輸入符號(hào)必須屬于允許跟在句柄之后的字符范圍內(nèi)，才認(rèn)為棧頂?shù)姆?hào)串為句柄而進(jìn)行歸約。(3) 對(duì)LR(1)來說，對(duì)現(xiàn)行輸入符號(hào)的限制則更加嚴(yán)格，它在該輸入符號(hào)跟在棧頂符號(hào)串后形成一個(gè)規(guī)范句型的前綴時(shí)，才認(rèn)為棧頂?shù)倪@個(gè)符號(hào)串為句柄，從而進(jìn)行歸約。由于要對(duì)不同的輸入符號(hào)進(jìn)行判斷，因此LR(1)的狀態(tài)數(shù)要比LR(0)、SLR(1)多。(4) LALR從本質(zhì)上講與LR(1)相同，只不過它把那些棧頂符號(hào)串相同但現(xiàn)行輸入符號(hào)不同(即認(rèn)為這個(gè)相同的棧頂符號(hào)串為同心)的判斷合一(使?fàn)顟B(tài)數(shù)又減少到與LR(0)、SLR(1)一樣)，只有輸入符號(hào)跟在棧頂符號(hào)串后面形

40、成一規(guī)范句型前綴時(shí)，才認(rèn)為棧頂?shù)倪@個(gè)符號(hào)串為句柄而進(jìn)行歸約。對(duì)于同心的棧頂符號(hào)串而言，由于面對(duì)不同的輸入符號(hào)將形成不同規(guī)范句型的前綴，這就給歸約帶來一些困難；也即，當(dāng)輸入串有誤時(shí)，LR(1)能夠及時(shí)地發(fā)現(xiàn)錯(cuò)誤，而LALR則可能還繼續(xù)執(zhí)行一些多余的歸約動(dòng)作，但決不會(huì)執(zhí)行新的移進(jìn)，即LALR能夠像LR(1)一樣準(zhǔn)確地指出出錯(cuò)的地點(diǎn)。此外，LALR這種同心集的合并有可能帶來新的“歸約”/“歸約”沖突。3.21 請(qǐng)指出圖3-12中的LR分析表(a)、(b)、(c)分屬LR(0)、SLR(1)和LR(1)中的哪一種，并說明理由。 【解答】 我們知道，LR(0)、SLR(1)和LR(1)分析表構(gòu)造的主要差

41、別是構(gòu)造算法(2)。其區(qū)別如下：(1) 對(duì)LR(0)分析表來說，若項(xiàng)目A·屬于Ik(狀態(tài))，則對(duì)任何終結(jié)符a(或結(jié)束符#)，置ACTIONk,a為“用產(chǎn)生式A進(jìn)行歸約(A為第j個(gè)產(chǎn)生式)”，簡記為“rj”。表現(xiàn)在ACTION子表中，則是每個(gè)歸約狀態(tài)所在的行全部填滿“rj”；并且，同一行的“rj”其下標(biāo)j相同，而不同行的“rj”其下標(biāo)j是不一樣的。 圖3-12 LR分析表(2) 對(duì)SLR(1)分析表來說，若項(xiàng)目A·屬于Ik，則對(duì)任何輸入符號(hào)a，僅當(dāng)aFOLLOW(A)時(shí)置ACTIONk,a為“用產(chǎn)生式A進(jìn)行歸約(A為第j個(gè)產(chǎn)生式)”，簡記為“rj”。表現(xiàn)在ACTION子表中，

42、則存在某個(gè)歸約狀態(tài)所在的行并不全部填滿rj，并且不同行的“rj”其下標(biāo)j不同。(3) 對(duì)LR(1)來說，若項(xiàng)目A·,a屬于Ik(狀態(tài))，則置ACTIONk,a為“用產(chǎn)生式A進(jìn)行歸約”，簡記為“rj”。LR(1)是在SLR(1)狀態(tài)(項(xiàng)目集)的基礎(chǔ)上，通過狀態(tài)分裂的辦法(即分裂成更多的項(xiàng)目集)，使得LR分析器的每個(gè)狀態(tài)能夠確切地指出當(dāng)后跟哪些終結(jié)符時(shí)才容許把歸約為A。例如，假定A·,a屬于Ik(狀態(tài))，則置ACTIONk,a欄目為rj(A為第j個(gè)產(chǎn)生式)；而A·,b屬于Im(狀態(tài))，則同樣置ACTIONm,b欄目為rj。表現(xiàn)在ACTION子表中，則在不同的行(即不同

43、的狀態(tài))里有相同的rj存在。因此，圖3-12(a)的分析表為LR(1)分析表(在不同行有相同的r2存在)；圖3-12(b)為LR(0)分析表(有rj的行是每行都填滿了rj且同一行rj的j相同，不同行rj的j不同)；而圖3-12(c)為LR(0)分析表(存在并不全部填滿rj的行，且不同行rj的j不同)。3.22 文法G(S)的產(chǎn)生式集為 S(EtSeS) | (EtS) | i =EE+EF | FF*Fi | i構(gòu)造文法G的SLR(1)分析表，要求先畫出相應(yīng)的DFA?！窘獯稹?將文法G拓廣為文法GS：(0)SS(1) S(EtSeS)(2) S(EtS)(3) Si=E(4) E+EF(5)

44、EF(6) F*Fi(7) Fi列出LR(0)的所有項(xiàng)目：1. S·S 9. S (EtSeS·) 17. S·i=E 25. E·F 2. SS· 10. S (EtSeS)· 18. Si·=E 26. EF· 3. S·(EtSeS) 11. S·(EtS) 19. Si=·E 27. F·*Fi4. S (·EtSeS) 12. S (·EtS) 20. Si=E· 28. F*·Fi5. S (E·tSeS) 13.

45、 S (E·tS) 21. E·+EF 29. F*F·i6. S (Et·SeS) 14. S (Et·S) 22. E+·EF 30. F*Fi· 7. S (EtS·eS) 15. S (EtS·) 23. E+E·F 31. F·i 8. S (EtSe·S) 16. S (EtS)· 24. E+EF· 32. Fi·用_CLOSURE方法構(gòu)造文法GS的LR(0)項(xiàng)目集規(guī)范族：I0: S·S I5: S (EtS·e

46、S) I13: E+·EFS·(EtSeS) S (EtS·) E·+EFS·(EtS) I6: S (EtSe·S) E·FS·i=E S·(EtSeS) I14: E+E·FI1: SS· S·(EtS) F·*FiI2: S (·EtSeS) S·i=E F·iS (·EtS) I7: S (EtSeS·) I15: E+EF·E·+EF I8: S (EtSeS)· I16: E

47、F·E·F I9: S (EtS)· I17: F*·FiI3: S(E·tSeS) I10: Si·=E F·*FiS(E·tS) I11:Si=·E F·iI4: S (Et·SeS) E·+EF I18: F*F·iS (Et·S) E·F I19: F*Fi·S·(EtSeS) I12: Si=E· I20: Fi·S·(EtS)S·i=E文法GS的DFA如圖3-13所示。圖3-13 習(xí)題3.22的DFA 構(gòu)造SLR(1)分析表必須先求出所有形如“A·”的FOLLOW(A)，即由FOLLOW集的構(gòu)造方法求得GS的FOLLOW集如下：(1) FOLLOW(S)=#；(2) 由S(EtSeS