【文章內(nèi)容簡(jiǎn)介】 ③ 對(duì) P→ … Rb… 而 a∈ FIRSTVT(R)， 有 a?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?, )?。 最后得到算符優(yōu)先關(guān)系表 ， 見表 36。 第三章 語(yǔ)法分析 表 36 習(xí)題 a b ( ) d a ? ? ? b ? ? ? ( ? ? ? ? ) ? ? ? d ? ? ? ? ? ? ? ? 第三章 語(yǔ)法分析 由表 36可以看出 ， 任何兩個(gè)終結(jié)符之間至多只滿足 、?、 ?三種優(yōu)先關(guān)系之一 ， 故 G[S]為算符優(yōu)先文法 。 (2) 為求出句型 (SdSdS)的短語(yǔ) 、 簡(jiǎn)單短語(yǔ) 、 句柄 ， 我們先畫出該句型對(duì)應(yīng)的語(yǔ)法樹 ， 如圖 38所示 。 第三章 語(yǔ)法分析 ( A )SS d AS d AS圖 38 句型 (SdSdS)的語(yǔ)法樹 第三章 語(yǔ)法分析 由圖 38得到： 短語(yǔ)： S， SdS， SdSdS， (SdSdS) 簡(jiǎn)單短語(yǔ) (即直接短語(yǔ) )： S 句柄 (即最左直接短語(yǔ) )： S 可以通過分析圖 38的語(yǔ)法樹來(lái)求素短語(yǔ)和最左素短語(yǔ) ，即找出語(yǔ)法樹中的所有相鄰終結(jié)符 (中間可有一個(gè)非終結(jié)符 )之間的優(yōu)先關(guān)系 。 確定優(yōu)先關(guān)系的原則是： ① 同層的優(yōu)先關(guān)系為； ② 不同層時(shí) ， 層次離樹根遠(yuǎn)者優(yōu)先級(jí)高 ， 層次離樹根近者優(yōu)先級(jí)低 (恰好驗(yàn)證了優(yōu)先關(guān)系表的構(gòu)造算法 )； ③ 在句型 ω 兩側(cè)加上語(yǔ)句括號(hào) “ ”， 即 ω ， 則有 ?ω和 ω ?， 由此我們得到句型 (SdSdS)的優(yōu)先關(guān)系如圖 39所示 。 第三章 語(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ǔ)法分析 因此 ， 由圖 39得到 SdS為句型 (SdSdS)的素短語(yǔ) ，它同時(shí)也是該句型的最左素短語(yǔ) 。 (3) 輸入串 (adb)的分析過程見表 37。 第三章 語(yǔ)法分析 表 37 輸入串 (adb)的分析過程 符號(hào)棧 輸入串 說(shuō) 明 (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 分析成功 第三章 語(yǔ)法分析 為便于分析，同時(shí)給出了 (adb)的語(yǔ)法樹，如圖 310所示。 ( A )SS d ASba圖 310 (adb)的語(yǔ)法樹 第三章 語(yǔ)法分析 在算符優(yōu)先分析法中 ， 為什么要在找到最左素短語(yǔ)的尾時(shí)才返回來(lái)確定其對(duì)應(yīng)的頭 ， 能否按掃描順序先找到頭后再找到對(duì)應(yīng)的尾 ， 為什么 ？ 【 解答 】 設(shè)句型的一般形式為 N1a1N2a2… NnanNn+1。其中 ， 每個(gè) ai都是終結(jié)符 ， 而 Ni則是可有可無(wú)的非終結(jié)符 。 對(duì)上述句型可以找出該句型中的所有素短語(yǔ) ， 每個(gè)素短語(yǔ)都具有如下形式： … aj1?ajaj+1… ai?ai+1… 第三章 語(yǔ)法分析 如果某句型得到的優(yōu)先關(guān)系如下： … ?… ?…… ?… ? 則當(dāng)從左至右掃描到第一個(gè) “ ?” 時(shí) ， 再由此從右至左掃描到第一個(gè) “ ?” 時(shí) ， 它們之間 (當(dāng)然不包含第一個(gè) “ ?” 前一個(gè)終結(jié)符和第二個(gè) “ ?” 后一個(gè)終結(jié)符 )即為最左素短語(yǔ) 。 第三章 語(yǔ)法分析 如果由左至右掃描到第一個(gè) “ ?” ， 可以看出這并不一定是最左素短語(yǔ)的開頭 ， 因?yàn)橛伤_始并不一定是素短語(yǔ) (在其內(nèi)部還可能包含其他更小的素短語(yǔ) )，所以 ， 在算符優(yōu)先分析算法中 ， 只有先找到最左素短語(yǔ)的尾 (即 “ ?” )， 才返回來(lái)確定與其對(duì)應(yīng)的頭 (即“ ?” )；而不能按掃描順序先找到頭然后再找到對(duì)應(yīng)的尾 。 試證明在算符文法中 ， 任何句型都不包含兩個(gè)相鄰的非終結(jié)符 。 【 解答 】 設(shè)文法 G=(VT,VN,S, ξ )， 其中 VT是終結(jié)符集； VN是非終結(jié)符集； ξ 為產(chǎn)生式集合； S是開始符號(hào) 。 第三章 語(yǔ)法分析 對(duì)句型的推導(dǎo)長(zhǎng)度 n作如下歸納： (1) 當(dāng) n=1時(shí) ， S? α ， 則存在一條產(chǎn)生式 S→ α 屬于 ε ， 其中 a∈ (VT∪ VN) *。 由于文法是算符文法 ， 所以 α 中沒有兩個(gè)相鄰非終結(jié)符 ， 故歸納初始成立 。 (2) 設(shè) n=k時(shí)結(jié)論成立 ， 則對(duì)任何 k+1步推導(dǎo)所產(chǎn)生的句型必為 Sα ∪ β ? α ∨ β 其中 ， α 、 β ∈ (VT∪ VN) *， U∈ VN， 而 U→ V是一條產(chǎn)生式 。 第三章 語(yǔ)法分析 由歸納假設(shè) ， U是非終結(jié)符 ， 設(shè) α =α 1α 2… α n，β =β 1β 2… β m ， 其中 α i 、 β j ∈ (VT∪ VN) (1≤ i≤ n1,2≤ j≤ m) ；但 α n和 β m必為位于 U兩側(cè)的終結(jié)符 。 設(shè) V=V1V2… Vr， 由于它是算符文法的一個(gè)產(chǎn)生式右部候選式 ， 因此 V1V2… Vr中不會(huì)有相鄰的非終結(jié)符出現(xiàn) 。又因?yàn)?α nV1和 Vrβ 1中的 α n、 β 1為終結(jié)符 ， 也即在推導(dǎo)長(zhǎng)度為 k+1時(shí)所產(chǎn)生的句型 α 1α 2… α nV1V2… Vrβ 1β 2… β m 不會(huì)出現(xiàn)相鄰的非終結(jié)符，故 n=k+1時(shí)結(jié)論成立。顯然，在 α或 β為空時(shí)結(jié)論也成立。 第三章 語(yǔ)法分析 給出文法 G[S]: S→ aSb∣ P P→ bPc∣ bQc Q→ Qa∣ a (1) 它是 Chomsky哪一型文法 ？ (2) 它生成的語(yǔ)言是什么 ？ (3) 它是不是算符優(yōu)先文法 ？ 請(qǐng)構(gòu)造算符優(yōu)先關(guān)系表證實(shí)之； (4) 文法 G[S]消除左遞歸 、 提取公共左因子后是不是 LL(1)文法 ？ 請(qǐng)證實(shí) 。 第三章 語(yǔ)法分析 【 解答 】 (1) 根據(jù) Chomsky的定義 ， 對(duì)任何形如A→ β 的產(chǎn)生式 ， 有 A∈ VN， β ∈ (VT∪ VN)*時(shí)為 2型文法 。而文法 G[S]恰好滿足這一要求 ， 故為 Chomsky 2型文法 。 (2) 由文法 G[S]可以看出： S推出串的形式是 ai P bi(i≥ 0)， P推出串的形式是 bjQcj(j≥ 1)， Q推出串的形式是 ak(k≥ 1)。 因此 ， 文法 G[S]生成的語(yǔ)言是L={aibjakcjbi|i≥ 0, j≥ 1, k≥ 1}。 第三章 語(yǔ)法分析 (3) 求出文法 G[S]的 FIRSTVT集和 LASTVT集： FIRSTVT(S)={a,b} FIRSTVT(P)= FIRSTVT(Q)={a} LASTVT(S)={b,c} LASTVT(P)={c} LASTVT(Q)={a} 構(gòu)造優(yōu)先關(guān)系表如表 38所示 。 由于在優(yōu)先關(guān)系中同時(shí)出現(xiàn)了 a?a和 a?a以及 b?b和b?b， 故文法 G[S]不是算符優(yōu)先文法 。 第三章 語(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ǔ)法分析 通過檢查 G′[S]可以得到： ① 每一個(gè)非終結(jié)符的所有候選式首符集兩兩不相交； ② 存在形如 A→ε 的產(chǎn)生式 Q′→aQ ′| ε， 但有 FIRST(aQ′)∩FOLLOW(Q′)={a}∩{c}=Φ 所以文法 G′[S]是 LL(1)文法 。 第三章 語(yǔ)法分析 ** LR分析器與優(yōu)先關(guān)系分析器在識(shí)別句柄時(shí)的主要異同是什么？ 【 解答 】 如果 S? aAδ 且有 A? β ， 則稱 β 是句型 α β δ相對(duì)于非終結(jié)符 A的短語(yǔ) 。 特別的 ， 如果有 A? β ， 則稱 β 是句型 α β δ 相對(duì)于規(guī)則 A→ β 的直接短語(yǔ) 。 一個(gè)句型的最左直接短語(yǔ)稱為該句型的句柄 。 規(guī)范歸約是關(guān)于 α 的一個(gè)最右推導(dǎo)的逆過程 ， 因此 ， 規(guī)范歸約也稱最左歸約 。 請(qǐng)注意句柄的 “ 最左 ” 特征 。 第三章 語(yǔ)法分析 LR分析器用規(guī)范歸約的方法尋找句柄 ， 其基本思想是：在規(guī)范歸約的過程中 ， 一方面記住已經(jīng)歸約的字符串 ， 即記住 “ 歷史 ” ；另一方面根據(jù)所用的產(chǎn)生式推測(cè)未來(lái)可能碰到的輸入字符串 ， 即對(duì)未來(lái)進(jìn)行“ 展望 ” 。 當(dāng)一串貌似句柄的符號(hào)串呈現(xiàn)于棧頂時(shí) ，則可根據(jù)歷史 、 展望以及現(xiàn)實(shí)的輸入符號(hào)等三方面的材料 ， 來(lái)確定棧頂?shù)姆?hào)串是否構(gòu)成相對(duì)某一產(chǎn)生式的句柄 。 事實(shí)上 ， 規(guī)范歸約的中心問題恰恰是如何尋找或確定一個(gè)句型的句柄 。 給出了尋找句柄的不同算法也就給出了不同的規(guī)范歸約方法 ， 如 LR(0)、 SLR(1)、LR(1)以及 LALR就是在歸約方法上進(jìn)行區(qū)別的 。 第三章 語(yǔ)法分析 算符優(yōu)先分析不是規(guī)范歸約 ， 因?yàn)樗豢紤]了終結(jié)符之間的優(yōu)先關(guān)系 ， 而沒有考慮非終結(jié)符之間的優(yōu)先關(guān)系 。 此外 ， 算符優(yōu)先分析比規(guī)范歸約要快得多 ，因?yàn)樗惴麅?yōu)先分析跳過了所有單非產(chǎn)生式所對(duì)應(yīng)的歸約步驟 。 這既是算符優(yōu)先分析的優(yōu)點(diǎn) ， 同時(shí)也是它的缺點(diǎn) ， 因?yàn)楹雎苑墙K結(jié)符在歸約過程中的作用存在某種危險(xiǎn)性 ， 可能導(dǎo)致把本來(lái)不成句子的輸入串誤認(rèn)為是句子 ， 但這種缺陷容易從技術(shù)上加以彌補(bǔ) 。 為了區(qū)別于規(guī)范歸約 ， 算符優(yōu)先分析中的 “ 句柄 ” 被稱為最左素短語(yǔ) 。 第三章 語(yǔ)法分析 什么是規(guī)范句型的活前綴 ？ 引進(jìn)它的意義何在 ？ 【 解答 】 在討論 LR分析器時(shí) ， 需要定義一個(gè)重要概念 ， 這就是文法的規(guī)范句型的 “ 活前綴 ” 。 字的前綴是指該字的任意首部 ， 例如 ， 字 abc的前綴有 ε 、 a、 ab或 abc。 所謂活前綴 ， 是指規(guī)范句型的一個(gè)前綴 ， 這種前綴不含句柄之后的任何符號(hào) 。 之所以稱為活前綴 ， 是因?yàn)樵谄溆疫呍鎏硪恍┙K結(jié)符號(hào)后 ，就可以使它成為一個(gè)規(guī)范句型 。 引入活前綴的意義在于它是構(gòu)造 LR(0)項(xiàng)目集規(guī)范族時(shí)必須用到的一個(gè)重要概念。 第三章 語(yǔ)法分析 對(duì)于