【正文】 VT集構(gòu)造方法： ① 由 P→ … a或 P→ … aQ, 則 a∈ LASTVT(P)。 第三章 語(yǔ)法分析 得到優(yōu)先關(guān)系表見(jiàn)表 33。 也可由定義直接構(gòu)造優(yōu)先函數(shù)，其方法是：對(duì)每個(gè)終結(jié)符 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? (； 第三章 語(yǔ)法分析 ③ 由 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)的分析過(guò)程見(jiàn)表 37。 第三章 語(yǔ)法分析 對(duì)句型的推導(dǎo)長(zhǎng)度 n作如下歸納： (1) 當(dāng) n=1時(shí) ， S? α ， 則存在一條產(chǎn)生式 S→ α 屬于 ε ， 其中 a∈ (VT∪ VN) *。 第三章 語(yǔ)法分析 【 解答 】 (1) 根據(jù) Chomsky的定義 ， 對(duì)任何形如A→ β 的產(chǎn)生式 ， 有 A∈ VN， β ∈ (VT∪ VN)*時(shí)為 2型文法 。 特別的 ， 如果有 A? β ， 則稱 β 是句型 α β δ 相對(duì)于規(guī)則 A→ β 的直接短語(yǔ) 。 第三章 語(yǔ)法分析 算符優(yōu)先分析不是規(guī)范歸約 ， 因?yàn)樗豢紤]了終結(jié)符之間的優(yōu)先關(guān)系 ， 而沒(méi)有考慮非終結(jié)符之間的優(yōu)先關(guān)系 。 引入活前綴的意義在于它是構(gòu)造 LR(0)項(xiàng)目集規(guī)范族時(shí)必須用到的一個(gè)重要概念。 S→ a S→ bdSa S→ bA S→ bA S B S → bA I3： S →bA e I1： S ′→S 由于 I3和 I9既含有移進(jìn)項(xiàng)目又含有歸約項(xiàng)目 ， 故文法G[S]不是 LR(0)文法 。 第三章 語(yǔ)法分析 (3) 對(duì) LR(1)來(lái)說(shuō) ， 對(duì)現(xiàn)行輸入符號(hào)的限制則更加嚴(yán)格 ， 它在該輸入符號(hào)跟在棧頂符號(hào)串后形成一個(gè)規(guī)范句型的前綴時(shí) ， 才認(rèn)為棧頂?shù)倪@個(gè)符號(hào)串為句柄 ，從而進(jìn)行歸約 。屬于 Ik(狀態(tài) )，則對(duì)任何終結(jié)符 a(或結(jié)束符 )，置 ACTION[k,a]為 “ 用產(chǎn)生式 A→ α進(jìn)行歸約 (A→ α為第 j個(gè)產(chǎn)生式 )”，簡(jiǎ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òu)造方法求得 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}； 第三章 語(yǔ)法分析 (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 → 為了減少?zèng)_突 ， 最好采用SLR(1)、 LR(1)或 LALR分析表 。AT卻要求移進(jìn) )。 ； I7： T →bT I4： T →T A T A T T → 用 ε _CLOSURE方法構(gòu)造文法 G[S]的 LR(0)項(xiàng)目集規(guī)范族 ， 并根據(jù)轉(zhuǎn)換函數(shù) GO構(gòu)造出文法 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→ 第三章 語(yǔ)法分析 用 ε _CLOSURE方法構(gòu)造文法 G[S′ ]的 LR(0)項(xiàng)目集規(guī)范族： I0: S′ → 7. S→ (EtSFi 第三章 語(yǔ)法分析 5. S→ (E 3. S→ 第三章 語(yǔ)法分析 【 解答 】 將文法 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 第三章 語(yǔ)法分析 列出 LR(0)的所有項(xiàng)目： 1. S′ → ,a]屬于 Ik(狀態(tài) )， 則置 ACTION[k,a]為 “ 用產(chǎn)生式 A→ α 進(jìn)行歸約 ” ， 簡(jiǎn)記為 “ rj”。 第三章 語(yǔ)法分析 【 解答 】 我們知道 ， LR(0)、 SLR(1)和 LR(1)分析表構(gòu)造的主要差別是構(gòu)造算法 (2)。的項(xiàng)目屬于棧頂狀態(tài) )， 則： (1) 對(duì) LR(0)來(lái)說(shuō) ， 無(wú)論現(xiàn)行輸入符號(hào)是什么 ， 都認(rèn)為棧頂?shù)姆?hào)串為句柄而進(jìn)行歸約 。 a I12： B →c A a A → S a S → c I0： S ′→a I4: A→ d 第三章 語(yǔ)法分析 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 第三章 語(yǔ)法分析 (3) A→ dSa (4) A→ e (5) B→ cAa (6) B→ c 構(gòu)造文法 G[S′ ]的 LR(0)項(xiàng)目集規(guī)范族如下： I0: S′ → 所謂活前綴 ， 是指規(guī)范句型的一個(gè)前綴 ， 這種前綴不含句柄之后的任何符號(hào) 。 事實(shí)上 ， 規(guī)范歸約的中心問(wèn)題恰恰是如何尋找或確定一個(gè)句型的句柄 。 第三章 語(yǔ)法分析 表 38 優(yōu)先關(guān)系表 a b c a ? ? ? ? b ? ? c ? ? 第三章 語(yǔ)法分析 (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 ′| ε 第三章 語(yǔ)法分析 求每個(gè)非終結(jié)符的 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} 第三章 語(yǔ)法分析 通過(guò)檢查 G′[S]可以得到： ① 每一個(gè)非終結(jié)符的所有候選式首符集兩兩不相交； ② 存在形如 A→ε 的產(chǎn)生式 Q′→aQ ′| ε， 但有 FIRST(aQ′)∩FOLLOW(Q′)={a}∩{c}=Φ 所以文法 G′[S]是 LL(1)文法 。顯然，在 α或 β為空時(shí)結(jié)論也成立。 試證明在算符文法中 ， 任何句型都不包含兩個(gè)相鄰的非終結(jié)符 。 第三章 語(yǔ)法分析 ( A )SS d AS d AS ＜ ( ＜ d ＜ d ＞ ) ＞ . . . . .圖 39 句型 (SdSdS)的優(yōu)先關(guān)系 第三章 語(yǔ)法分析 注意 ， 句型中的素短語(yǔ)具有如下形式： aj1?ajaj+1… ai?ai+1 而最左素短語(yǔ)就是該句型中所找到的最左邊的那個(gè)素短語(yǔ) ， 即最左素短語(yǔ)必須具備三個(gè)條件： ① 至少包含一個(gè)終結(jié)符 (是否包含非終結(jié)符則按短語(yǔ)的要求確定 )； ② 除自身外不得包含其他素短語(yǔ) (最小性 )； ③ 在句型中具有最左性 。 第三章 語(yǔ)法分析 【 解答 】 (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,)}； 第三章 語(yǔ)法分析 由 A→ … dA得 LASTVT(A)=nhcuj7d3， 又由 A→ S得 LASTVT(S) ? LASTVT(A)， 即 LASTVT(A)={d,a,b,)}。 得到優(yōu)先函數(shù)見(jiàn)表 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′ ]的預(yù)測(cè)分析表 ， 見(jiàn)表 31。 要將 G[A]改造為 LL(1)文法 ， 首先要消除文法的左遞歸 ， 即將形如 P→ Pα | β 的產(chǎn)生式改造為 P→ β P′ P→ α P′ | ε 第三章 語(yǔ)法分析 來(lái)消除左遞歸 。 S ( )。 第三章 語(yǔ)法分析 下述文法描述了 C語(yǔ)言整數(shù)變量的聲明語(yǔ)句： G[D]: D→ TL T→ int|long|short L→ id|L,id (1) 改造上述文法 ， 使其接受相同的輸入序列 ，但文法是右遞歸的； (2) 分別用上述文法 G[D]和