1、精選優質文檔-傾情為你奉上第三章 語法分析 3.1 完成下列選擇題： (1) 文法G：SxSx|y所識別的語言是 。 a. xyx b. (xyx)* c. xnyxn(n0) d. x*yx*(2) 如果文法G是無二義的，則它的任何句子 。 a. 最左推導和最右推導對應的語法樹必定相同b. 最左推導和最右推導對應的語法樹可能不同c. 最左推導和最右推導必定相同d. 可能存在兩個不同的最左推導，但它們對應的語法樹相同(3) 采用自上而下分析，必須 。a. 消除左遞a. 必有ac歸 b. 消除右遞歸c. 消除回溯 d. 提取公共左因子(4) 設a、b、c是文法的終結符，且滿足優先關系ab和bc，

2、則 。b. 必有cac. 必有ba d. ac都不一定成立(5) 在規范歸約中，用 來刻畫可歸約串。 a. 直接短語 b. 句柄 c. 最左素短語 d. 素短語(6) 若a為終結符，則A·a為 項目。 a. 歸約 b. 移進 c. 接受 d. 待約(7) 若項目集Ik含有A· ，則在狀態k時，僅當面臨的輸入符號aFOLLOW(A)時，才采取“A· ”動作的一定是 。 a. LALR文法 b. LR(0)文法 c. LR(1)文法 d. SLR(1)文法(8) 同心集合并有可能產生新的 沖突。a. 歸約 b. “移進”/“移進” c.“移進”/“歸約” 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的最左推導和最右推導。【解答】 (1) GN的語言L(GN)是非負整數。(2) 最左推導：NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568最右推導：NNDN7ND7N27ND27N127D NNDN4D434 NNDN8ND8N68D685683.3 已知

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

5、數個b的所有串的集合的正規文法；(3) 由相同個數a和b組成句子的無二義文法。【解答】 (1) 由L=aibj|ji0知，所求該語言對應的上下文無關文法首先應有SaSb型產生式，以保證b的個數不少于a的個數；其次，還需有SSb或Sb型的產生式，用以保證b的個數多于a的個數。因此，所求上下文無關文法GS為GS：SaSb|Sb|b(2) 為了構造字母表=a,b上同時只有奇數個a和奇數個b的所有串集合的正規式，我們畫出如圖3-3所示的DFA，即由開始符S出發，經過奇數個a到達狀態A，或經過奇數個b到達狀態B；而由狀態A出發，經過奇數個b到達狀態C(終態)；同樣，由狀態B出發經過奇數個a到達終態C。由

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

7、有文法GS: SaAcB|BdAAaB|cBbScA|b(1) 試求句型aAaBcbbdcc和aAcbBdcc的句柄；(2) 寫出句子acabcbbdcc的最左推導過程。【解答】 (1) 分別畫出對應句型aAaBcbbdcc和aAcbBdcc的語法樹如圖3-4的(a)、(b)所示。圖3-4 習題3.6的語法樹 (a) aAaBcbbdcc; (b) aAcbBdcc 對樹(a)，直接短語有3個：AaB、b和c，而AaB為最左直接短語(即為句柄)。對樹(b)，直接短語有兩個：Bd和c，而Bd為最左直接短語。能否不畫出語法樹，而直接由定義(即在句型中)尋找滿足某個產生式的候選式這樣一個最左子串(即

8、句柄)呢？例如，對句型aAaBcbbdcc，我們可以由左至右掃描找到第一個子串AaB，它恰好是滿足AAaB右部的子串；與樹(a)對照，AaB的確是該句型的句柄。是否這一方法始終正確呢？我們繼續檢查句型aAcbBdcc，由左至右找到第一個子串c，這是滿足AC右部的子串，但由樹(b)可知，c不是該句型的句柄。由此可知，畫出對應句型的語法樹然后尋找最左直接短語是確定句柄的好方法。(2) 句子acabcbbdcc的最左推導如下：SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc3.7 對于文法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中相鄰終結符之間的優先關系求得，即： # (， (a)#因此，素短語為a。3.8 下述文法描述了C語言整數變量的聲明語句：GD: DTLTint|long|shortLid|L,id(1) 改造上述文法，使其接受相同的輸入序列，但文法是右遞歸的；(2) 分別用上述文法

10、GD和改造后的文法GD為輸入序列int a,b,c構造分析樹。【解答】 (1) 消除左遞歸后，文法GD如下：DTLTint|long|shortLidL圖3-6 兩種文法為int a,b,c構造的分析樹 (a) 文法G(D)； (b) 文法G(D)3.9 考慮文法GS: S(T) | a+S | aTT,S | S消除文法的左遞歸及提取公共左因子，然后對每個非終結符寫出不帶回溯的遞歸子程序。【解答】 消除文法GS的左遞歸：S(T) | a+S | aTSTT,ST| 提取公共左因子：S(T) | aSS+S | TSTT,ST| 改造后的文法已經是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、價的LL(1)文法GA；(2) 構造GA的LL(1)分析表；(3) 給出輸入串aadl#的分析過程。【解答】 (1) 文法GA存在左遞歸和回溯，故其不是LL(1)文法。要將GA改造為LL(1)文法，首先要消除文法的左遞歸，即將形如PP | 的產生式改造為PPPP| 來消除左遞歸。由此，將產生式BBb|d改造為BdBBbB| 其次，應通過提取公共左因子的方法來消除GA中的回溯，即將產生式AaABl|a改造為AaAAABl | 最后得到改造后的文法為GA：AaAAABl | BdBBbB| 求得： FIRST(A)=a FIRST(A)=a, FIRST(B)=d FIRST(B)=b, 對文法開

13、始符號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。 對AABl來說，FIRST(A)FOLLOW(A)=a#,d=，所以文法GA為所求等價的LL(1)文法。(2) 構造預測分析表的方法如下： 對文法GA的每個產生式A執行、步。 對每個終結符aFIRST

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

15、L(1)文法的充要條件是：對每一個終結符A的任何兩個不同產生式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)= ；則，對V |E有：FIRST()FIRST(= ；對E | +E有：FIRST()FIRST(+)= ；對V | E有：FIRST()FOLLOW(V)=#,+=；對E | +E有：FIRST(+)FOLLOW(E)=+=。故文法GV為LL(1)文法。3.12 對文法GE: EE+T|T TT*P|P P

17、i (1) 構造該文法的優先關系表(不考慮語句括號#)，并指出此文法是否為算符優先文法；(2) 構造文法G的優先函數。【解答】 FIRSTVT集構造方法： 由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集構造方法： 由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。優先關系表構造方法： 對Pab或PaQb，有ab； 對PaR而bFIRSTVT(R)，有

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

20、b，則畫一條從fa到ga的有向弧；若ab或ab，則畫一條從g b到f a的有向弧。最后，對每個結點都賦一個數，此數等于從該結點出發所能到達的結點(包括出發結點)的個數，賦給fa的數作為f(a)，賦給gb的數作為g(b)。用關系圖法構造本題的優先函數，如圖3-7所示。得到優先函數見表3-4。 表3-4 習題3.12的優先函數表 圖3-7 習題3.12關系圖構造該優先函數表經檢查與優先關系表沒有矛盾，故為所求優先函數。也可由定義直接構造優先函數，其方法是：對每個終結符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)。重復上述過程，直到每個終結符的函數值不再變化為止。如果有一個函數值大于2n(n為終結符個數)，則不存在優先函數。優先函數的計算過程如表3-5所示。 表3-5 優先函數的計算過程表計算最終收斂，并且計算得出的優先函數與關系圖構造得出的優先函數是一樣的。3.13 設有文法GS: Sa|b|(A)ASdA|S(1) 構造算符優先關系表；(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,)。構造優先關系表方法如下： 對Pab或PaQb，有ab； 對PaR而bFIRSTVT(R)，有ab； 對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#, )#。最后得到算符優先關系表，見表3-6。表3-6 習題3.13的算符優先關系表 由表3-6可以看出，任何兩個終結符之間至多只滿足、三種優先關系之一，故GS為算符優先文法。(2) 為求出句型(SdSdS)的短語、簡單短語、句柄，我們先畫出該句型對應的語法樹，如圖3-8所示。圖3-8

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

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

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

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

28、n，=12m，其中i、j (VTVN) (1in-1,2jm) ；但n和m必為位于U兩側的終結符。設V=V1V2Vr，由于它是算符文法的一個產生式右部候選式，因此V1V2Vr中不會有相鄰的非終結符出現。又因為nV1和Vr1中的n、1為終結符，也即在推導長度為k+1時所產生的句型12nV1V2Vr12m不會出現相鄰的非終結符，故n=k+1時結論成立。顯然，在或為空時結論也成立。 3.16 給出文法GS: SaSbPPbPcbQc QQaa (1) 它是Chomsky哪一型文法？ (2) 它生成的語言是什么？ (3) 它是不是算符優先文法？請構造算符優先關系表證實之；(4) 文法GS消除左遞歸、提

29、取公共左因子后是不是LL(1)文法？請證實。【解答】 (1) 根據Chomsky的定義，對任何形如A的產生式，有AVN，(VTVN)*時為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構造優先關系表如表3-8所示。由于在優先關系中同時出現了aa和aa以及bb和bb，故文法GS不是算符優先文法。表3-8 優先關系表 (4) 消除文法GS的左遞歸：SaSb | PPbPc | bQcQaQQaQ| 提取公共左因子后得到文法GS:SaSb | PPbPPPc | QcQaQQaQ| 求每個非終結符的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可以得到： 每一個非終結符的所有候選式首符集兩兩不相交； 存在形如A的產生式QaQ| ，但有 FIRST(aQ)FOLLOW(Q)=ac=所以文法GS是LL(1)文法。*3.17 LR分析器與優先關系分析器在識別句柄時的主要異同是什么？【解答】 如果SaA且有A，則稱是句型相對于非終結符A的短語。特別的，如果有A，則稱是句型相對于規則A的直接短語。一個句型的最左直接短語稱為該句型的句柄。規范歸約是關于的一個最右推導的逆過程，因此，規范歸約也稱最左歸約。請注意句柄的“最左”特征。LR分析器用規范歸約的方法尋找句柄，其基本思想是：在規范歸約的過程中，一方面記住已經歸約

32、的字符串，即記住“歷史”；另一方面根據所用的產生式推測未來可能碰到的輸入字符串，即對未來進行“展望”。當一串貌似句柄的符號串呈現于棧頂時，則可根據歷史、展望以及現實的輸入符號等三方面的材料，來確定棧頂的符號串是否構成相對某一產生式的句柄。事實上，規范歸約的中心問題恰恰是如何尋找或確定一個句型的句柄。給出了尋找句柄的不同算法也就給出了不同的規范歸約方法，如LR(0)、SLR(1)、LR(1)以及LALR就是在歸約方法上進行區別的。算符優先分析不是規范歸約，因為它只考慮了終結符之間的優先關系，而沒有考慮非終結符之間的優先關系。此外，算符優先分析比規范歸約要快得多，因為算符優先分析跳過了所有單非產生

33、式所對應的歸約步驟。這既是算符優先分析的優點，同時也是它的缺點，因為忽略非終結符在歸約過程中的作用存在某種危險性，可能導致把本來不成句子的輸入串誤認為是句子，但這種缺陷容易從技術上加以彌補。為了區別于規范歸約，算符優先分析中的“句柄”被稱為最左素短語。3.18 什么是規范句型的活前綴？引進它的意義何在？【解答】 在討論LR分析器時，需要定義一個重要概念，這就是文法的規范句型的“活前綴”。字的前綴是指該字的任意首部，例如，字abc的前綴有、a、ab或abc。所謂活前綴，是指規范句型的一個前綴，這種前綴不含句柄之后的任何符號。之所以稱為活前綴，是因為在其右邊增添一些終結符號后，就可以使它成為一個規

34、范句型。引入活前綴的意義在于它是構造LR(0)項目集規范族時必須用到的一個重要概念。 對于一個文法G，首先要構造一個NFA，它能識別G的所有活前綴，這個NFA的每個狀態即為一個“項目”。文法G每一個產生式的右部添加一個圓點稱為G的一個LR(0)項目(簡稱項目)，可以使用這些項目狀態構造一個NFA。我們能夠把識別活前綴的NFA確定化，使之成為一個以項目集為狀態的DFA，這個DFA就是建立LR分析算法的基礎。構成識別一個文法活前綴的DFA項目集(狀態)的全體稱為這個文法的LR(0)項目集歸范族。 3.19 試構造下述文法的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構造文法GS的LR(0)項目集規范族如下： 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 注意，在比較熟練的情況下，也可以不構造LR(0)項目集規范族而直接畫出文法GS的DFA。由于I3和I9既含有移進項目又含有歸約項目，故文法GS不是LR(0)文法。我們構造文法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,#；對I3有：bFOLLOW(S)=ba,c,#=對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有何共同特征？它們的本質區別是什么？【解答】 LR(0)、SLR(1)、LR(1)及LALR的共同特征是都用規范歸約的方法尋找句柄，即LR分析器的每一步工作都是由棧頂狀態和現行輸入符號所唯一決定的。它們的本質區別是尋找句柄的方法不同。如果當前的棧頂狀態為歸約狀態(即有形如A·的項目屬于棧頂狀態)，則：(1) 對LR(0)來說，無論現行輸入符號是什么，都認為棧頂的符號串為句柄而進行歸約。 (2)

39、對SLR(1)來說，則對現行輸入符號加了一點限制，即該輸入符號必須屬于允許跟在句柄之后的字符范圍內，才認為棧頂的符號串為句柄而進行歸約。(3) 對LR(1)來說，對現行輸入符號的限制則更加嚴格，它在該輸入符號跟在棧頂符號串后形成一個規范句型的前綴時，才認為棧頂的這個符號串為句柄，從而進行歸約。由于要對不同的輸入符號進行判斷，因此LR(1)的狀態數要比LR(0)、SLR(1)多。(4) LALR從本質上講與LR(1)相同，只不過它把那些棧頂符號串相同但現行輸入符號不同(即認為這個相同的棧頂符號串為同心)的判斷合一(使狀態數又減少到與LR(0)、SLR(1)一樣)，只有輸入符號跟在棧頂符號串后面形

40、成一規范句型前綴時，才認為棧頂的這個符號串為句柄而進行歸約。對于同心的棧頂符號串而言，由于面對不同的輸入符號將形成不同規范句型的前綴，這就給歸約帶來一些困難；也即，當輸入串有誤時，LR(1)能夠及時地發現錯誤，而LALR則可能還繼續執行一些多余的歸約動作，但決不會執行新的移進，即LALR能夠像LR(1)一樣準確地指出出錯的地點。此外，LALR這種同心集的合并有可能帶來新的“歸約”/“歸約”沖突。3.21 請指出圖3-12中的LR分析表(a)、(b)、(c)分屬LR(0)、SLR(1)和LR(1)中的哪一種，并說明理由。 【解答】 我們知道，LR(0)、SLR(1)和LR(1)分析表構造的主要差

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

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

43、的狀態)里有相同的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)的產生式集為 S(EtSeS) | (EtS) | i =EE+EF | FF*Fi | i構造文法G的SLR(1)分析表，要求先畫出相應的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)的所有項目：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方法構造文法GS的LR(0)項目集規范族：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 習題3.22的DFA 構造SLR(1)分析表必須先求出所有形如“A·”的FOLLOW(A)，即由FOLLOW集的構造方法求得GS的FOLLOW集如下：(1) FOLLOW(S)=#；(2) 由S(EtSeS