【正文】 VT集構造方法： ① 由 P→ … a或 P→ … aQ, 則 a∈ LASTVT(P)。 第三章 語法分析 得到優(yōu)先關系表見表 33。 也可由定義直接構造優(yōu)先函數(shù)，其方法是：對每個終結符 a，令 f(a)=g(a)=1；如果 a?b，而 f(a)≤ g(b)，則令 f(a)=g(b)+1；如果 a?b，而 f(a)≥ g(b)，則令g(b)=f(a)+1；如果 ab，而 f(a)≠ g(b)，則令 min{f(a),g(b)}=max{f(a),g(b)}。 由此得到： ① 由 S→ (A)得 ()； ② 由 S→ (A… 得 (?FIRSTVT(A) ， 即(?d,(?a,(?b,(?(； 由 A→ … dA得 d?FIRSTVT(A)， 即 d?d,d?a,d?b,d? (； 第三章 語法分析 ③ 由 S→ … A) 得 LASTVT(A)?) ， 即d?),a?),b?),)?)； 由 A→ Sd… 得 LASTVT(S)?d， 即 a?d,b?d,)?d； 此外 ， 由 S得 ； 由 ?FIRSTVT(S)得 ?a, ?b, ? (； 由 LASTVT(S)?得 a?, b?, )?。 (3) 輸入串 (adb)的分析過程見表 37。 第三章 語法分析 對句型的推導長度 n作如下歸納： (1) 當 n=1時 ， S? α ， 則存在一條產(chǎn)生式 S→ α 屬于 ε ， 其中 a∈ (VT∪ VN) *。 第三章 語法分析 【 解答 】 (1) 根據(jù) Chomsky的定義 ， 對任何形如A→ β 的產(chǎn)生式 ， 有 A∈ VN， β ∈ (VT∪ VN)*時為 2型文法 。 特別的 ， 如果有 A? β ， 則稱 β 是句型 α β δ 相對于規(guī)則 A→ β 的直接短語 。 第三章 語法分析 算符優(yōu)先分析不是規(guī)范歸約 ， 因為它只考慮了終結符之間的優(yōu)先關系 ， 而沒有考慮非終結符之間的優(yōu)先關系 。 引入活前綴的意義在于它是構造 LR(0)項目集規(guī)范族時必須用到的一個重要概念。 S→ a S→ bdSa S→ bA S→ bA S B S → bA I3： S →bA e I1： S ′→S 由于 I3和 I9既含有移進項目又含有歸約項目 ， 故文法G[S]不是 LR(0)文法 。 第三章 語法分析 (3) 對 LR(1)來說 ， 對現(xiàn)行輸入符號的限制則更加嚴格 ， 它在該輸入符號跟在棧頂符號串后形成一個規(guī)范句型的前綴時 ， 才認為棧頂?shù)倪@個符號串為句柄 ，從而進行歸約 。屬于 Ik(狀態(tài) )，則對任何終結符 a(或結束符 )，置 ACTION[k,a]為 “ 用產(chǎn)生式 A→ α進行歸約 (A→ α為第 j個產(chǎn)生式 )”，簡記為“ rj”。 例如 ，假定 [A→ α ) 17. S→ (EtS) 19. S→ i=tS) 21. E→ ) 23. E→ +EeS) I13: E→ +i=E S→ i S→ ( I17: F→ *SeS) E→ S→ i ＝ E I2： S →( F I12： S →i ＝ E F F → i I1 9： F →* F i ) I6： S →( E t S e ”的FOLLOW(A)， 即由 FOLLOW集的構造方法求得 G[S′ ]的FOLLOW集如下： (1) FOLLOW(S′ )={}； (2) 由 S→ (EtSeS)得 FIRST(′ t′ ) ? FOLLOW(E)，即 FOLLOW(E)={t}； FIRST(′ e′ ) ? FOLLOW(S)， 即 FOLLOW(S)={e}； FIRST(′ ) ′ ) ? FOLLOW(S)， 即 FOLLOW(S)={e,)}； 由 F→ *Fi得 FIRST(′ i′ ) ? FOLLOW(F)， 即 FOLLOW(F)={i}； 由 E→ +EF得 FIRST(′ F′ )/{ε}? FOLLOW(E)，即 FOLLOW(E)={t,i}； 第三章 語法分析 (3) 由 S′ → S得 FOLLOW(S′ ) ? FOLLOW(S)， 即FOLLOW(S)={e,),}； 由 S→ i=E 得 FOLLOW(S) ? FOLLOW(E) ， 即FOLLOW(E)={t,i,e,),}； 由 E→ F 得 FOLLOW(E) ? FOLLOW(F) ， 即FOLLOW(F)={t,i,e,),}。e 13． A→ a 15． A→ I0： S → a I3： S →T T A T T → A T A → 為了減少沖突 ， 最好采用SLR(1)、 LR(1)或 LALR分析表 。AT卻要求移進 )。 ； I7： T →bT I4： T →T A T A T T → 用 ε _CLOSURE方法構造文法 G[S]的 LR(0)項目集規(guī)范族 ， 并根據(jù)轉換函數(shù) GO構造出文法 G[S]的 DFA， 如圖314所示 。TAT 7 ． T→ T 5 ． T→ TA I9： S →( E t S ) i ＝ E I5： S →( E t S I2 0： F →i ＋ EF E →E E → ( E t S e S ) S →(EtSeS) I12: S→ i=EE F→ E→ EtSeS) S→ S) E→ 第三章 語法分析 用 ε _CLOSURE方法構造文法 G[S′ ]的 LR(0)項目集規(guī)范族： I0: S′ → 7. S→ (EtSFi 第三章 語法分析 5. S→ (E 3. S→ 第三章 語法分析 【 解答 】 將文法 G 拓 廣 為 文 法 G[S′ ] ：(0)S′ → S (1) S→ (EtSeS) (2) S→ (EtS) (3) S→ i=E (4) E→ +EF (5) E→ F (6) F→ *Fi (7) F→ i 第三章 語法分析 列出 LR(0)的所有項目： 1. S′ → ,a]屬于 Ik(狀態(tài) )， 則置 ACTION[k,a]為 “ 用產(chǎn)生式 A→ α 進行歸約 ” ， 簡記為 “ rj”。 第三章 語法分析 【 解答 】 我們知道 ， LR(0)、 SLR(1)和 LR(1)分析表構造的主要差別是構造算法 (2)。的項目屬于棧頂狀態(tài) )， 則： (1) 對 LR(0)來說 ， 無論現(xiàn)行輸入符號是什么 ， 都認為棧頂?shù)姆柎疄榫浔M行歸約 。 a I12： B →c A a A → S a S → c I0： S ′→a I4: A→ d 第三章 語法分析 I3: S→ bAc I2: S→ b G[S]: S→ bASB | bA A→ dSa | e B→ cAa | c 【 解答 】 首先將文法 G[S]拓廣為 G[S′ ]: G[S′ ]： (0) S′ → S (1) S→ bASB (2) S→ bA 第三章 語法分析 (3) A→ dSa (4) A→ e (5) B→ cAa (6) B→ c 構造文法 G[S′ ]的 LR(0)項目集規(guī)范族如下： I0: S′ → 所謂活前綴 ， 是指規(guī)范句型的一個前綴 ， 這種前綴不含句柄之后的任何符號 。 事實上 ， 規(guī)范歸約的中心問題恰恰是如何尋找或確定一個句型的句柄 。 第三章 語法分析 表 38 優(yōu)先關系表 a b c a ? ? ? ? b ? ? c ? ? 第三章 語法分析 (4) 消除文法 G[S]的左遞歸： S→aSb | P P→bPc | bQc Q→aQ ′ Q′→aQ ′| ε 提取公共左因子后得到文法 G′[S]: S→aSb | P P→bP ′ P′→Pc | Qc Q→aQ ′ Q′→aQ ′| ε 第三章 語法分析 求每個非終結符的 FIRST集和 FOLLOW集如下： FIRST(S)={a,b} FIRST(P)= FIRST(P′)={a,b} FIRST(Q)={a} FIRST(Q′)={a, ε} FOLLOW(S)={b,} FOLLOW(P)={b,c,} FOLLOW(P′)={b,c,} FOLLOW(Q)={c} FOLLOW(Q′)={c} 第三章 語法分析 通過檢查 G′[S]可以得到： ① 每一個非終結符的所有候選式首符集兩兩不相交； ② 存在形如 A→ε 的產(chǎn)生式 Q′→aQ ′| ε， 但有 FIRST(aQ′)∩FOLLOW(Q′)={a}∩{c}=Φ 所以文法 G′[S]是 LL(1)文法 。顯然，在 α或 β為空時結論也成立。 試證明在算符文法中 ， 任何句型都不包含兩個相鄰的非終結符 。 第三章 語法分析 ( A )SS d AS d AS ＜ ( ＜ d ＜ d ＞ ) ＞ . . . . .圖 39 句型 (SdSdS)的優(yōu)先關系 第三章 語法分析 注意 ， 句型中的素短語具有如下形式： aj1?ajaj+1… ai?ai+1 而最左素短語就是該句型中所找到的最左邊的那個素短語 ， 即最左素短語必須具備三個條件： ① 至少包含一個終結符 (是否包含非終結符則按短語的要求確定 )； ② 除自身外不得包含其他素短語 (最小性 )； ③ 在句型中具有最左性 。 第三章 語法分析 【 解答 】 (1) 先求文法 G[S]的 FIRSTVT集和 LASTVT集： 由 S→ a|b|(A)得 FIRSTVT(S)={a,b,(}； 由 A→ Sd… 得 FIRSTVT(A)=nhcuj7d3 ， 又由 A→ S… 得FIRSTVT(S) ? FIRSTVT(A) ， 即 FIRSTVT(A)={d,a,b, ( }； 由 S→ a|b|(A)得 LASTVT(S) ={a,b,)}； 第三章 語法分析 由 A→ … dA得 LASTVT(A)=nhcuj7d3， 又由 A→ S得 LASTVT(S) ? LASTVT(A)， 即 LASTVT(A)={d,a,b,)}。 得到優(yōu)先函數(shù)見表 34。 由 ② 得： E→ … +T， 即 +?FIRSTVT(T)， 有 +?*， +?i； T→ … *P， 即 *?FIRSTVT(P)， 有 *i。 由 ① 得：由 E→ E+… 得 FIRSTVT(E)={+}； 由 T→ T*… 得 FIRSTVT(T)={*}； 由 P→ i得 FIRSTVT(P)={i}。 由此得到 G[A′ ]的預測分析表 ， 見表 31。 要將 G[A]改造為 LL(1)文法 ， 首先要消除文法的左遞歸 ， 即將形如 P→ Pα | β 的產(chǎn)生式改造為 P→ β P′ P→ α P′ | ε 第三章 語法分析 來消除左遞歸 。 S ( )。 第三章 語法分析 下述文法描述了 C語言整數(shù)變量的聲明語句： G[D]: D→ TL T→ int|long|short L→ id|L,id (1) 改造上述文法 ， 使其接受相同的輸入序列 ，但文法是右遞歸的； (2) 分別用上述文法 G[D]和