【正文】 第三章 語(yǔ)法分析 第三章 語(yǔ)法分析 完成下列選擇題： (1) 文法 G： S→ xSx|y所識(shí)別的語(yǔ)言是 。 a. xyx b. (xyx)* c. xnyxn(n≥ 0) d. x*yx* (2) 如果文法 G是無(wú)二義的 ， 則它的任何句子 α 。 a. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹必定相同 b. 最左推導(dǎo)和最右推導(dǎo)對(duì)應(yīng)的語(yǔ)法樹可能不同 c. 最左推導(dǎo)和最右推導(dǎo)必定相同 d. 可能存在兩個(gè)不同的最左推導(dǎo) ， 但它們對(duì)應(yīng)的語(yǔ)法樹相同 第三章 語(yǔ)法分析 (3) 采用自上而下分析 ， 必須 。 a. 消除左遞歸 b. 消除右遞歸 c. 消除回溯 d. 提取公共左因子 (4) 設(shè) a、 b、 c是文法的終結(jié)符 ， 且滿足優(yōu)先關(guān)系ab和 bc， 則 。 a. 必有 ac b. 必有 ca c. 必有 ba d. a～ c都不一定成立 第三章 語(yǔ)法分析 (5) 在規(guī)范歸約中 ， 用 來(lái)刻畫可歸約串 。 a. 直接短語(yǔ) b. 句柄 c. 最左素短語(yǔ) d. 素短語(yǔ) (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) a∈ FOLLOW(A)時(shí) ， 才采取 “ A→ α ”動(dòng)作的一定是 。 a. LALR文法 b. LR(0)文法 c. LR(1)文法 d. SLR(1)文法 第三章 語(yǔ)法分析 (8) 同心集合并有可能產(chǎn)生新的 沖突 。 a. 歸約 b. “移進(jìn) ” /“移進(jìn) ” c.“移進(jìn) ” /“歸約 ” d. “歸約 ” /“歸約 ” 【 解答 】 (1) c (2) a (3) c (4) d (5) b (6) b (7) d (8) d 令文法 G[N]為 G[N]: N→ D|ND D→ 0|1|2|3|4|5|6|7|8|9 (1) G[N]的語(yǔ)言 L(G[N])是什么 ? (2) 給出句子 012 34和 568的最左推導(dǎo)和最右推導(dǎo) 。 第三章 語(yǔ)法分析 【 解答 】 (1) G[N]的語(yǔ)言 L(G[N])是非負(fù)整數(shù) 。 (2) 最左推導(dǎo)： NNDNDDNDDDDDDD0DDD01DD012D0127 NNDDD3D34 NNDNDDDDD5DD56D568 最右推導(dǎo)： NNDN7ND7N27ND27N127D1270127 NNDN4D434 NNDN8ND8N68D68568 第三章 語(yǔ)法分析 已知文法 G[S]為 S→ aSb|Sb|b， 試證明文法G[S]為二義文法 。 【 解答 】 由文法 G[S]： S→ aSb|Sb|b， 對(duì)句子aabbbb可對(duì)應(yīng)如圖 31所示的兩棵語(yǔ)法樹 。 第三章 語(yǔ)法分析 Sa S ba S bS bba S bS bSa S bb圖 31 句子 aabbbb對(duì)應(yīng)的兩棵不同語(yǔ)法樹 第三章 語(yǔ)法分析 因此 ， 文法 G[S]為二義文法 (對(duì)句子 abbb也可畫出兩棵不同語(yǔ)法樹 )。 已知文法 G[S]為 S→ SaS|ε ， 試證明文法 G[S]為二義文法 。 【 解答 】 由文法 G[S]： S→ SaS|ε，句子 aa的語(yǔ)法樹如圖 32所示。 第三章 語(yǔ)法分析 SS SaS Sa? ??SSS aSS a???( a ) ( b )圖 32 句子 aa對(duì)應(yīng)的兩棵不同的語(yǔ)法樹 第三章 語(yǔ)法分析 由圖 32可知 ， 文法 G[S]為二義文法 。 按指定類型 ， 給出語(yǔ)言的文法 。 (1) L={aibj|j＞ i≥ 0}的上下文無(wú)關(guān)文法； (2) 字母表 Σ ={a,b}上的同時(shí)只有奇數(shù)個(gè) a和奇數(shù)個(gè)b的所有串的集合的正規(guī)文法； (3) 由相同個(gè)數(shù) a和 b組成句子的無(wú)二義文法 。 【 解答 】 (1) 由 L={aibj|j＞ i≥ 0}知 ， 所求該語(yǔ)言對(duì)應(yīng)的上下文無(wú)關(guān)文法首先應(yīng)有 S→ aSb型產(chǎn)生式 ， 以保證 b的個(gè)數(shù)不少于 a的個(gè)數(shù)；其次 ， 還需有 S→ Sb或 S→ b型的產(chǎn)生式 ， 用以保證 b的個(gè)數(shù)多于 a的個(gè)數(shù) 。 因此 ， 所求上下文無(wú)關(guān)文法 G[S]為 G[S]： S→ aSb|Sb|b 第三章 語(yǔ)法分析 (2) 為了構(gòu)造字母表 Σ ={a,b}上同時(shí)只有奇數(shù)個(gè) a和奇數(shù)個(gè) b的所有串集合的正規(guī)式 ， 我們畫出如圖 33所示的 DFA， 即由開始符 S出發(fā) ， 經(jīng)過(guò)奇數(shù)個(gè) a到達(dá)狀態(tài)A， 或經(jīng)過(guò)奇數(shù)個(gè) b到達(dá)狀態(tài) B；而由狀態(tài) A出發(fā) ， 經(jīng)過(guò)奇數(shù)個(gè) b到達(dá)狀態(tài) C(終態(tài) )；同樣 ， 由狀態(tài) B出發(fā)經(jīng)過(guò)奇數(shù)個(gè) a到達(dá)終態(tài) C。 由圖 33可直接得到正規(guī)文法 G[S]如下： G[S]： S→ aA|bB A→ aS|bC|b B→ bS|aC|a C→ bA|aB|ε 第三章 語(yǔ)法分析 圖 33 習(xí)題 DFA S CABaabbbbaa第三章 語(yǔ)法分析 (3) 我們用一個(gè)非終結(jié)符 A代表一個(gè) a(即有 A→ a)，用一個(gè)非終結(jié)符 B代表一個(gè) b(即有 B→ b)；為了保證 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)有 A→ bAA；同理有B→ aBB。 此外 ， 為了保證遞歸地推出所要求的 ab串 ，應(yīng)有 S→ aBS和 S→ bAS。 由此得到無(wú)二義文法 G[S]為 G[S]： S→ aBS|bAS|ε A→ bAA|a B→ aBB|b 第三章 語(yǔ)法分析 有文法 G[S]: S→ aAcB|Bd A→ AaB|c B→ bScA|b (1) 試求句型 aAaBcbbdcc和 aAcbBdcc的句柄； (2) 寫出句子 acabcbbdcc的最左推導(dǎo)過(guò)程 。 【 解答 】 (1) 分別畫出對(duì)應(yīng)句型 aAaBcbbdcc和aAcbBdcc的語(yǔ)法樹如圖 34的 (a)、 (b)所示 。 第三章 語(yǔ)法分析 A a B b S c ABA caSB dbb S c ABA caSB d c( a ) ( b )c圖 34 習(xí)題 (a) aAaBcbbdcc。 (b) aAcbBdcc 第三章 語(yǔ)法分析 對(duì)樹 (a)， 直接短語(yǔ)有 3個(gè)： AaB、 b和 c， 而 AaB為最左直接短語(yǔ) (即為句柄 )。 對(duì)樹 (b)， 直接短語(yǔ)有兩個(gè)：Bd和 c， 而 Bd為最左直接短語(yǔ) 。 能否不畫出語(yǔ)法樹 ， 而直接由定義 (即在句型中 )尋找滿足某個(gè)產(chǎn)生式的候選式這樣一個(gè)最左子串 (即句柄 )呢 ？ 例如 ， 對(duì)句型 aAaBcbbdcc， 我們可以由左至右掃描找到第一個(gè)子串 AaB， 它恰好是滿足 A→ AaB右部的子串；與樹 (a)對(duì)照 ， AaB的確是該句型的句柄 。 是否這一方法始終正確呢 ？ 我們繼續(xù)檢查句型 aAcbBdcc， 由左至右找到第一個(gè)子串 c， 這是滿足 A→ C右部的子串 ， 但由樹 (b)可知 ， c不是該句型的句柄 。 由此可知 ， 畫出對(duì)應(yīng)句型的語(yǔ)法樹然后尋找最左直接短語(yǔ)是確定句柄的好方法 。 第三章 語(yǔ)法分析 (2) 句子 acabcbbdcc的最左推導(dǎo)如下： SaAcBaAaBcBacaBcBacabcBacabcbScAacabcbBdcA acabcbbdcAacabcbbdcc 對(duì)于文法 G[S]: S→ (L)|aS|a L→ L,S|S (1) 畫出句型 (S,(a))的語(yǔ)法樹； (2) 寫出上述句型的所有短語(yǔ) 、 直接短語(yǔ) 、 句柄 、 素短語(yǔ)和最左素短語(yǔ) 。 【 解答 】 (1) 句型 (S, (a))的語(yǔ)法樹如圖 35所示 。 第三章 語(yǔ)法分析 ( L )SL , SS ( L )Sa圖 35 句型 (S,(a))的語(yǔ)法樹 第三章 語(yǔ)法分析 (2) 由圖 35可知： 短語(yǔ)： S、 a、 (a)、 S,(a)、 (S,(a))； 直接短語(yǔ)： a、 S； 句柄： S； 素短語(yǔ)：素短語(yǔ)可由圖 35中相鄰終結(jié)符之間的優(yōu)先關(guān)系求得 ， 即： ? (?， ? (?a?)?)? 因此 ， 素短語(yǔ)為 a。 第三章 語(yǔ)法分析 下述文法描述了 C語(yǔ)言整數(shù)變量的聲明語(yǔ)句： G[D]: D→ TL T→ int|long|short L→ id|L,id (1) 改造上述文法 ， 使其接受相同的輸入序列 ，但文法是右遞歸的； (2) 分別用上述文法 G[D]和改造后的文法 G[D′ ]為輸入序列 int a,b,c構(gòu)造分析樹 。 第三章 語(yǔ)法分析 【 解答 】 (1) 消除左遞歸后 ， 文法 G[D′ ]如下： D→ TL T→ int|long|short L→ idL 第三章 語(yǔ)法分析 L , cLDTi ntL , ba, bLDTi nt a L′L′, c L′?( a ) ( b )圖 36 兩種文法為 int a,b,c構(gòu)造的分析樹 (a) 文法 G(D)； (b) 文法 G′(D) 第三章 語(yǔ)法分析 考慮文法 G[S]: S→ (T) | a+S | a T→ T,S | S 消除文法的左遞歸及提取公共左因子 ， 然后對(duì)每個(gè)非終結(jié)符寫出不帶回溯的遞歸子程序 。 【 解答 】 消除文法 G[S]的左遞歸： S→ (T) | a+S | a T→ ST′ T′ → ,ST′ | ε 第三章 語(yǔ)法分析 提取公共左因子： S→ (T) | aS′ S′ → +S | ε T→ ST′ T′ → ,ST′ | ε 改造后的文法已經(jīng)是 LL(1)文法 ， 不帶回溯的遞歸子程序如下： void match (token t) { if ( lookahead==t) lookahead=nexttoken。 else error ( )。 } 第三章 語(yǔ)法分析 void S ( ) { if ( lookahead==′ a′ ) match (′ a′ )。 else if ( lookahead==′ (′ ) { match (′ (′ )。 T ( )。 第三章 語(yǔ)法分析 void S′ ( ) { if ( lookahead==′ +′ ) { match (′ +′ )。 S ( )。 } } 第三章 語(yǔ)法分析 void T ( ) { S ( )。 T′ ( )。 } void T′ ( ) { if ( lookahead==′ , ′ ) { match (′ , ′ )。 S ( )。 T′ ( )。 } } 第三章 語(yǔ)法分析 已知文法 G[A]: A→ aABl|a B→ Bb|d (1) 試給出與 G[A]等價(jià)的 LL(1)文法 G[A′ ]； (2) 構(gòu)造 G[A′ ]的 LL(1)分析表； (3) 給出輸入串 aadl的分析過(guò)程 。 【 解答 】 (1) 文法 G[A]存在左遞歸和回溯 ， 故其不是LL(1)文法 。 要將 G[A]改造為 LL(1)文法 ， 首先要消除文法的左遞歸 ， 即將形如 P→ Pα | β 的產(chǎn)生式改造為 P→ β P′ P→ α P′ | ε 第三章 語(yǔ)法分析 來(lái)消除左遞歸 。 由此 ， 將產(chǎn)生式 B→ Bb|d改造為 B→ dB′ B′ → bB′ | ε 其次 ， 應(yīng)通過(guò)提取公共左因子的方法來(lái)消除 G[A]中的回溯 ， 即將產(chǎn)生式