【正文】 4： A →d I11： B →c A 請指出圖 312中的 LR分析表 (a)、 (b)、 (c)分屬 LR(0)、 SLR(1)和 LR(1)中的哪一種 ， 并說明理由 。 文法 G(S)的產(chǎn)生式集為 S→ (EtSeS) | (EtS) | i =E E→ +EF | F F→ *Fi | i 構(gòu)造文法 G的 SLR(1)分析表 ， 要求先畫出相應(yīng)的 DFA。 28. F→ * 32. F→ i*Fi 第三章 語法分析 I2: S→ (tS) I11: S→ i= S S → E F E → ( E t S ) S → 【 解答 】 首先將文法 G[T]拓廣為文法 G[S]： (0) S→ T 第三章 語法分析 (1)T→ TAT (2) T→ bTe (3) T→ a (4) A→ ， (5) A→ ； 下面列出 LR(0)的所有項(xiàng)目： 1 ． S→ I6： A→ ； 要求歸約 ， 而 T→ T ， A → T →T 4． T→ T 最后得到 SLR(1)分析表 ， 見表 310。 I4： S →( E t I3： S →( E (EtS) S→ Fi I3: S→ (E(EtSeS) I14: E→ +EF 31. F→ E 27. F→ ,a]屬于 Ik(狀態(tài) )， 則置 ACTION[k,a]欄目為rj(A→ α 為第 j個產(chǎn)生式 )；而 [A→ α 由于要對不同的輸入符號進(jìn)行判斷 ，因此 LR(1)的狀態(tài)數(shù)要比 LR(0)、 SLR(1)多 。 I5： A →e bA I2： S →b A→ bASB I6: S→ bAS 此外 ， 算符優(yōu)先分析比規(guī)范歸約要快得多 ，因?yàn)樗惴麅?yōu)先分析跳過了所有單非產(chǎn)生式所對應(yīng)的歸約步驟 。而文法 G[S]恰好滿足這一要求 ， 故為 Chomsky 2型文法 。 第三章 語法分析 表 37 輸入串 (adb)的分析過程 符號棧 輸入串 說 明 (a db) 移進(jìn) ( a db) 移進(jìn) (a db) 用 S → a 歸約 (S db) 移進(jìn) (S d b) 移進(jìn) (S db ) 用 S → b 歸約 (S dS ) 用 A → S 歸約 (S dA ) 用 A → S dA 歸約 (A ) 移進(jìn) (A ) 用 S → (A ) 歸約 S 分析成功 第三章 語法分析 為便于分析，同時給出了 (adb)的語法樹，如圖 310所示。重復(fù)上述過程，直到每個終結(jié)符的函數(shù)值不再變化為止。 ② 若 a∈ LASTVT(Q)， 且 P→ … Q， 則 a∈ LASTVT(P)，也即 LASTVT(Q)? LASTVT(P)。 對 A′→ ABl來說，F(xiàn)IRST(A)∩ FOLLOW(A′ )={a}∩ {,d}=Φ，所以文法G′ [A]為所求等價的 LL(1)文法。 else error ( )。 也即為了保證 b和 A的個數(shù)一致 ， 應(yīng)有 A→ bAA；同理有B→ aBB。 ”動作的一定是 。aβ 為 項(xiàng)目 。 因此 ， 所求上下文無關(guān)文法 G[S]為 G[S]： S→ aSb|Sb|b 第三章 語法分析 (2) 為了構(gòu)造字母表 Σ ={a,b}上同時只有奇數(shù)個 a和奇數(shù)個 b的所有串集合的正規(guī)式 ， 我們畫出如圖 33所示的 DFA， 即由開始符 S出發(fā) ， 經(jīng)過奇數(shù)個 a到達(dá)狀態(tài)A， 或經(jīng)過奇數(shù)個 b到達(dá)狀態(tài) B；而由狀態(tài) A出發(fā) ， 經(jīng)過奇數(shù)個 b到達(dá)狀態(tài) C(終態(tài) )；同樣 ， 由狀態(tài) B出發(fā)經(jīng)過奇數(shù)個 a到達(dá)終態(tài) C。 第三章 語法分析 下述文法描述了 C語言整數(shù)變量的聲明語句： G[D]: D→ TL T→ int|long|short L→ id|L,id (1) 改造上述文法 ， 使其接受相同的輸入序列 ，但文法是右遞歸的； (2) 分別用上述文法 G[D]和改造后的文法 G[D′ ]為輸入序列 int a,b,c構(gòu)造分析樹 。 要將 G[A]改造為 LL(1)文法 ， 首先要消除文法的左遞歸 ， 即將形如 P→ Pα | β 的產(chǎn)生式改造為 P→ β P′ P→ α P′ | ε 第三章 語法分析 來消除左遞歸 。 由 ① 得：由 E→ E+… 得 FIRSTVT(E)={+}； 由 T→ T*… 得 FIRSTVT(T)={*}； 由 P→ i得 FIRSTVT(P)={i}。 得到優(yōu)先函數(shù)見表 34。 第三章 語法分析 ( A )SS d AS d AS ＜ ( ＜ d ＜ d ＞ ) ＞ . . . . .圖 39 句型 (SdSdS)的優(yōu)先關(guān)系 第三章 語法分析 注意 ， 句型中的素短語具有如下形式： aj1?ajaj+1… ai?ai+1 而最左素短語就是該句型中所找到的最左邊的那個素短語 ， 即最左素短語必須具備三個條件： ① 至少包含一個終結(jié)符 (是否包含非終結(jié)符則按短語的要求確定 )； ② 除自身外不得包含其他素短語 (最小性 )； ③ 在句型中具有最左性 。顯然，在 α或 β為空時結(jié)論也成立。 事實(shí)上 ， 規(guī)范歸約的中心問題恰恰是如何尋找或確定一個句型的句柄 。 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òu)造文法 G[S′ ]的 LR(0)項(xiàng)目集規(guī)范族如下： I0: S′ → 第三章 語法分析 I3: S→ bA c I0： S ′→ A →的項(xiàng)目屬于棧頂狀態(tài) )， 則： (1) 對 LR(0)來說 ， 無論現(xiàn)行輸入符號是什么 ， 都認(rèn)為棧頂?shù)姆柎疄榫浔M(jìn)行歸約 。,a]屬于 Ik(狀態(tài) )， 則置 ACTION[k,a]為 “ 用產(chǎn)生式 A→ α 進(jìn)行歸約 ” ， 簡記為 “ rj”。 3. S→ 7. S→ (EtSS) E→ E→ (EtSeS) I12: S→ i=EE E → I2 0： F →i I9： S →( E t S ) TAT 7 ． T→ T A T T → ； I7： T →bT 為了減少沖突 ， 最好采用SLR(1)、 LR(1)或 LALR分析表 。 T A T T → I0： S →e 13． A→ ) I6： S →( E t S e F F → i ＝ E I2： S →( SeS) E→ i S→ (eS) I13: E→ +tS) 21. E→ ) 17. S→ 屬于 Ik(狀態(tài) )，則對任何終結(jié)符 a(或結(jié)束符 )，置 ACTION[k,a]為 “ 用產(chǎn)生式 A→ α進(jìn)行歸約 (A→ α為第 j個產(chǎn)生式 )”，簡記為“ rj”。 由于 I3和 I9既含有移進(jìn)項(xiàng)目又含有歸約項(xiàng)目 ， 故文法G[S]不是 LR(0)文法 。 bA I3： S →bA S→ a S→ b 引入活前綴的意義在于它是構(gòu)造 LR(0)項(xiàng)目集規(guī)范族時必須用到的一個重要概念。 特別的 ， 如果有 A? β ， 則稱 β 是句型 α β δ 相對于規(guī)則 A→ β 的直接短語 。 第三章 語法分析 對句型的推導(dǎo)長度 n作如下歸納： (1) 當(dāng) n=1時 ， S? α ， 則存在一條產(chǎn)生式 S→ α 屬于 ε ， 其中 a∈ (VT∪ VN) *。 由此得到： ① 由 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?, )?。 第三章 語法分析 得到優(yōu)先關(guān)系表見表 33。 第三章 語法分析 表 32 輸入串 aadl的分析過程 符號棧 當(dāng)前輸入符號 輸入串 說 明 A a a dl 彈出棧頂符號 A 并將 A → aA ′ 產(chǎn)生式右部反序壓棧 A ′ a a a dl 匹配，彈出棧頂符號 a 并讀出下一個輸入符號 a A ′ a dl 彈出棧頂符號 A ′ 并將 A ′ → A Bl 產(chǎn)生式右部反序壓棧 l BA a dl 彈出棧頂符號 A 并將 A → aA ′ 產(chǎn)生式右部反序壓棧 l BA ′ a a dl 匹配，彈出棧頂符號 a 并讀出下一個輸入符號 d l BA ′ d l 由 A ′ → ε 僅彈出棧頂符號 A ′ l B d l 彈出棧頂符號 B 并將 B → dB ′ 產(chǎn)生式右部反序壓棧 l B ′ d d l 匹配，彈出棧頂符號 d 并讀出下一個輸入符號 l l B ′ l 由 B ′ → ε 僅彈出棧頂符號 B ′ l l 匹配，彈出棧頂符號 l 并讀出下一個輸入符號 匹配，分析成功 第三章 語法分析 將下述文法改造為 LL(1)文法： G[V]: V→ N | N[E] E→ V | V+E N→ i 【 解答 】 LL(1)文法的基本條件是不含左遞歸和回溯(公共左因子 )， 而文法 G[V]中含有回溯 ， 所以先消除回溯 ，得到文法 G[V′ ]： G [V′ ]： V→ NV′ V′ → ε | [E] E→ VE′ E′ → ε | +E N→ i 第三章 語法分析 一個 LL(1)文法的充要條件是：對每一個終結(jié)符 A的任何兩個不同產(chǎn)生式 A→ α |β 有下面的條件成立： (1) FIRST(α )∩ FIRST(β )=Φ； (2) 假若 βε， 則有 FIRST(α )∩ FOLLOW(A)= Φ 。 T′ ( )。 能否不畫出語法樹 ， 而直接由定義 (即在句型中 )尋找滿足某個產(chǎn)生式的候選式這樣一個最左子串 (即句柄 )呢 ？ 例如 ， 對句型 aAaBcbbdcc， 我們可以由左至右掃描找到第一個子串 AaB， 它恰好是滿足 A→ AaB右部的子串；與樹 (a)對照 ， AaB的確是該句型的句柄 。 已知文法 G[S]為 S→ SaS|ε ， 試證明文法 G[S]為二義文法 。第三章 語法分析 第三章 語法分析 完成下列選擇題： (1) 文法 G： S→ xSx|y所識別的語言是 。 第三章 語法分析 Sa S ba S bS bba S bS bSa S bb圖 31 句子 aabbbb對應(yīng)的兩棵不同語法樹 第三章 語法分析 因此 ， 文法