《編譯原理第4章語法分析自下而上LR分析法.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理第4章語法分析自下而上LR分析法.ppt（121頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

4 3LR分析法 圖1 語法分析概述 LR分析法是一種自下而上進(jìn)行規(guī)范歸約的語法分析方法 L指自左向右掃描輸入串 R指最右推導(dǎo) 規(guī)范歸約 LR分析法比遞歸下降分析法 LL 1 分析法對文法的限制要少得多 大多數(shù)無二義性CFG語言都可用LR分析器識別 且速度快 并能準(zhǔn)確 指出輸入串的語法錯誤及出錯位置 LR分析法的主要缺點(diǎn) 手工構(gòu)造工作量相當(dāng)大 必須求助自動產(chǎn)生工具 LR分析程序 器 自左向右掃描 識別句柄 自下而上歸約的語法分析程序 LR分析程序生成器 自動生成LR分析程序的程序 LR分析器 分析表 的分類 LR 0 表構(gòu)造法 這種方法的局限性較大 但它是建立其它較一般的LR分析法的基礎(chǔ) 簡單LR 簡稱SLR 表構(gòu)造法 雖然一些文法不能構(gòu)造SLR分析表 但是 它是一種比較容易實(shí)現(xiàn)又很有使用價值的方法 規(guī)范LR表構(gòu)造法 這種分析表能力最強(qiáng) 能夠適用一大類文法 但實(shí)現(xiàn)代價高 或者說 分析表的體積非常大 向前LR表構(gòu)造法 簡稱LALR 這種分析表的能力介于SIR和規(guī)范LR之間 可以高效地實(shí)現(xiàn) LR分析器的工作原理規(guī)范歸約 最右推導(dǎo)逆過程 的關(guān)鍵是尋找句柄 LR分析法的基本思想 在規(guī)范歸約過程中 一方面記住已移進(jìn)和歸約出的符號串 即記住 歷史 棧 另一方面根據(jù)所用產(chǎn)生式推測未來可能遇到的輸入符 即對未來進(jìn)行 展望 當(dāng)一串貌似句柄的符號串呈現(xiàn)于分析棧棧頂時 希望能根據(jù)所記載的 歷史 展望 及 現(xiàn)實(shí) 材料來確定棧頂符號是否構(gòu)成句柄 分析表產(chǎn)生器 文法 分析表 LR分析程序結(jié)構(gòu) 一個LR分析器實(shí)質(zhì)上是一個帶先進(jìn)后出存儲器 棧 的確定有限狀態(tài)自動機(jī) 我們將把 歷史 和 展望 材料綜合地抽象成某些 狀態(tài) 自動機(jī) 分析棧 先進(jìn)后出存儲器 用來存放狀態(tài) 棧里的每個狀態(tài)概括了從分析開始直到某一歸約階段的全部 歷史 和 展望 資料 任何時候 棧頂?shù)臓顟B(tài)都代表了整個的歷史和已推測出的展望 因此 在任何時候都可從棧頂狀態(tài)得知所想了解的文法的一切信息 而沒有必要從底而上翻閱整個棧 LR分析器的每一步工作都是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一決定的 4 3 1LR分析過程 LR分析的核心 分析表 分析表由ACTION表和GOTO表兩部分組成 ACTION s a 表示當(dāng)狀態(tài)s面臨輸入a時的動作GOTO s x 規(guī)定了狀態(tài)s面對文法符號X 非終結(jié)符 時的下一狀態(tài) 文法G 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 分析表 圖 分析表中記號的含義sj 把下一狀態(tài)j和現(xiàn)行輸入符號a移進(jìn)棧 rj 按第j個產(chǎn)生式進(jìn)行歸約 acc 接受 空白格 出錯標(biāo)志 報錯 給出下述文法G的LR分析表 幻燈片11 ACTION k a 的動作 1 移進(jìn) 設(shè)表中ACTION k a Sj 當(dāng)S棧頂狀態(tài)為k 現(xiàn)行輸入符號為a 總控程序根據(jù) k 和 a 查LR 0 分析表 得 ACTION k a Sj此時 Sj表示j狀態(tài)進(jìn)S棧 a進(jìn)T棧 文法符號棧 2 歸約 設(shè)LR 0 分析表中的ACTION mn a rj 其中rj表示使用文法的第j個產(chǎn)生式A x1x2 xp歸約 mn表示LR分析表的一個狀態(tài) 假設(shè)總控程序按S棧頂狀態(tài)mn和現(xiàn)行輸入符號a查LR分析表 得ACTION mn a rj此時 S棧的狀態(tài)為 m1 mn p 1 mn文法符號T棧的符號為 x1x2 xp按ACTION mn a rj的要求 S棧應(yīng)刪除棧頂p個狀態(tài) mn p 1 mn刪除后 S棧成為 m1 mn p T棧中x1x2 xp歸約成A 即T棧棧頂刪除p個文法符號 非終極符A進(jìn)T棧 若GOTO mn p A j 則狀態(tài)j進(jìn)S棧 3 接受 宣布分析成功 分析器停止工作 當(dāng)S棧頂狀態(tài)為k 現(xiàn)行輸入符號為a 總控程序根據(jù) k 和 a 查LR分析表得 ACTION k a accacc說明語法分析成功 4 報錯 報告發(fā)現(xiàn)源程序有錯 調(diào)用出錯處理程序 總控程序若按 k 和 a 查表得 ACTION k a 空白說明語法分析出錯 所給輸入串不是本文法的句子 LR分析器總控程序的工作十分簡單 它的任一步只需按分析棧棧頂狀態(tài)s和現(xiàn)行輸入符a執(zhí)行ACTION s a 所規(guī)定的動作 LR分析器的工作過程可看成是棧中狀態(tài)序列 已歸約串和輸入串構(gòu)成的三元式的變化過程 2 句型分析過程 設(shè)所給輸入串為 i i i 則總控程序分析此輸入串的過程 如表4 11所示 通過分析 說明i i i是文法例4 4的句子 例利用上述分析表 假定輸入串為i i i 描述LR分析器的工作過程 狀態(tài) 符號 輸入串 1 0 i i i 2 05 i i i 3 03 F i i 4 02 T i i 5 027 T i i 6 0275 T i i 7 02710 T F i 8 02 T i 9 01 E i ACTION 0 i s5移進(jìn)5和i ACTION 5 r6按第6個產(chǎn)生式進(jìn)行歸約 即 6 F i GOTO 0 F 3移進(jìn)狀態(tài)3 ACTION 10 r3按第3個產(chǎn)生式進(jìn)行歸約 即 3 T T F GOTO 0 T 2移進(jìn)狀態(tài)2 例利用上述分析表 假定輸入串為i i i 描述LR分析器的工作過程 續(xù) 狀態(tài) 符號 輸入串 10 016 E i 11 0165 E i 12 0163 E F 13 0169 E T 14 01 E ACTION 1 acc接受輸入串 LR文法 LR k 文法 一個文法 如果能用一個每步頂多向前檢查k個輸入符號的LR分析器進(jìn)行分析 則這個文法就稱為LR k 文法 定義 對于一個文法 如果能夠構(gòu)造一張分析表 使得它的每個入口均是唯一確定的 則我們把這個文法稱為LR文法 存在不是LR的上下文無關(guān)文法若一個文法的任何 移進(jìn) 歸約 分析器都存在下述情況 盡管棧的內(nèi)容和下一輸入符都已了解 但仍無法確定是 移進(jìn) 還是 歸約 或無法從幾種可能的歸約中確定其一 則該文法為非LR文法 注意 1 LR文法肯定是無二義的 一個二義文法不會是LR文法 2 LR分析技術(shù)可適當(dāng)修改以適于一定的二義文法 LR分析法的主要任務(wù) 構(gòu)造一張LR分析表首先討論一種只概括 歷史 資料而不包含推測性 展望 材料的 狀態(tài) 希望僅由這種簡單狀態(tài)就能識別呈現(xiàn)在棧頂?shù)哪承┚浔?LR 0 項(xiàng)目集就是這樣一種簡單狀態(tài) 4 3 2 LR 0 項(xiàng)目集規(guī)范族和LR 0 分析表 兩種LR 0 分析表的構(gòu)造算法 方法一 先構(gòu)造識別文法的活前綴非確定有限自動機(jī) 然后確定化 再構(gòu)造LR 0 分析表 方法二 是直接構(gòu)造LR 0 項(xiàng)目集規(guī)范族 再構(gòu)造LR 0 分析表 方法一 LR 0 分析表的構(gòu)造步驟 確定G的LR 0 項(xiàng)目 以LR 0 項(xiàng)目為狀態(tài) 構(gòu)造一個能識別文法G的所有活前綴的NFA 利用子集法 將NFA確定化 成為以項(xiàng)目集合為狀態(tài)的DFA根據(jù) 上述DFA可直接構(gòu)造出LR分析表 定義 文法G每一個產(chǎn)生式的右部添加一個圓點(diǎn) 稱為G的一個LR 0 項(xiàng)目 設(shè)文法G的某一產(chǎn)生式為A x1x2 xn 則A x1 xi xi 1 xn稱為文法G的LR 0 項(xiàng)目 如 A XY對應(yīng)三個項(xiàng)目 A XYA X YA XY 而 A 的項(xiàng)目A B 句型的活前綴及文法的LR 0 分析表 項(xiàng)目的意義 指明在分析過程的某時刻 我們看到產(chǎn)生式多大一部分 項(xiàng)目在計(jì)算機(jī)中的表示 m n intm nm 代表產(chǎn)生式編號n 指出圓點(diǎn)的位置 如 abc前綴 a ab abc活前綴 規(guī)范句型的一個前綴 該前綴是不含句柄之后的任何符號 C 字的前綴 指該字的任意首部 例4 5文法為 1 S E 2 E aA 3 A cA 4 A d其句型 acd d是句柄 活前綴為 a ac acd同理 在句型 acA 中 句柄是 cA 活前綴為 a ac acA 稱為活前綴原因 在右邊增添一些終結(jié)符號就可以使它成為一個規(guī)范句型 在LR分析工作過程中的任何時候 棧里的文法符號 自棧底而上 X1X2 Xm應(yīng)該構(gòu)成活前綴 把輸入串的剩余部分配上之后即應(yīng)成為規(guī)范句型 如果整個輸入串確實(shí)構(gòu)成一個句子 因此 只要輸入串的已掃描部分保持可歸約成一個活前綴 那就意味著所掃描過的部分沒有錯誤 D 對文法G 構(gòu)造能識別G的所有活前綴的NFA 識別文法句型活前綴的非確定有限自動機(jī) NFAM 包括 狀態(tài) 狀態(tài)轉(zhuǎn)換 初態(tài) 終態(tài) NFA的狀態(tài) 是一個LR 0 項(xiàng)目 一個項(xiàng)目指明了在分析過程的某時刻看到產(chǎn)生式多大一部分 構(gòu)造方法 a 文法開始符號的形如S S的項(xiàng)目為NFA的唯一初態(tài) 文法的所有LR 0 項(xiàng)目構(gòu)成的狀態(tài)都是識別文法的規(guī)范句型的活前綴的終態(tài) 活前綴識別態(tài) b 若狀態(tài)i和j出自同一個產(chǎn)生式 而且j的圓點(diǎn)只落后于i的圓點(diǎn)一個位置 就從i畫一條標(biāo)志為Xi的弧到j(luò) 即 i X X1 Xi 1 Xi Xnj X X1 Xi 1Xi Xn c 若狀態(tài)i的圓點(diǎn)之后的符號為非終結(jié)符 如i為X A 其中A屬于VN 就從狀態(tài)i畫 弧到所有A 狀態(tài) 例 構(gòu)造以下文法的NFA 文法G的所有LR 0 項(xiàng)目 文法GS EE aA bBA cA dB cB d 1 S E2 S E 3 E aA4 E a A5 E aA 6 A cA7 A c A8 A cA 9 A d10 A d 11 E bB12 E b B13 E bB 14 B cB15 B c B16 B cB 17 B d18 B d 利用上述規(guī)則a b c構(gòu)造NFA 如圖所示 E E 使用子集方法 將NFA確定化 使之成為一個以項(xiàng)目集合為狀態(tài)的DFA 1 S E 2 E aA 3 A cA 4 A d 可將文法的LR 0 項(xiàng)目分成如下四類 A 歸約項(xiàng)目S 接收項(xiàng)目 其中 S是開始符號A a 移進(jìn)項(xiàng)目 其中 a VTA B 待歸約項(xiàng)目 其中 B VN識別例4 5的文法的句型 acd 的過程 先構(gòu)造識別句型的活前綴NFAM 然后確定化太繁瑣 下面給出一種直接構(gòu)造DFAM 的方法 3 LR 0 項(xiàng)目集規(guī)范族 方法二 相關(guān)定義 定義4 12若I是一個LR 0 項(xiàng)目集 則項(xiàng)目集Closure I 的定義如下 a Closure I I b 若項(xiàng)目A B Closure I B VN 則Closure I Closure I B c 重復(fù) b 直至Closure I 不再擴(kuò)大為止 定義4 13設(shè)I為LR 0 項(xiàng)目集 X是一文法符號 LR 0 狀態(tài)轉(zhuǎn)換函數(shù)GO I X 的定義如下 GO I X Closure J 其中 J 任何形如A X 的項(xiàng)目 A X I 文法 1 S E 2 E aA 3 A cA 4 A d若S E I 則Closure I S E E aA 令I(lǐng)0 S E E aA 則GO I0 E S E I1GO I0 a E a A A cA A d I2從項(xiàng)目集I0開始 將I0定義成一個狀態(tài) 按照狀態(tài)轉(zhuǎn)換函數(shù)GO I X 的定義可以找出所有的項(xiàng)目集 狀態(tài) 由GO I X 所產(chǎn)生的項(xiàng)目集 狀態(tài) 全體稱為LR 0 項(xiàng)目集規(guī)范族 構(gòu)造一個G 它包含了整個G 但它引進(jìn)了一個不出現(xiàn)在G中的非終結(jié)符S 并加進(jìn)一個新產(chǎn)生式S S 而這個S 是G 的開始符號 稱G 是G的拓廣文法 把文法G進(jìn)行拓廣為了使 接受 狀態(tài)易于識別 有一個僅含項(xiàng)目S S的狀態(tài) 這就是唯一的 接受 態(tài) 拓廣文法 步驟一 令NFA的初態(tài)為I 求其CLOSURE I 得到初態(tài)項(xiàng)目集 即 求CLOSURE S S 步驟二 對所得項(xiàng)目集I和文法G的每個文法符號X 包括VT和VN 計(jì)算GO I X CLOSURE J 得到新的項(xiàng)目集 其中J 任何形如A X 的項(xiàng)目 A X 屬于I 步驟三 重復(fù)步驟二 直至沒有新的項(xiàng)目集出現(xiàn) 經(jīng)過以上步驟構(gòu)造出的項(xiàng)目集的全體即為LR 0 項(xiàng)目集規(guī)范族 利用LR 0 項(xiàng)目集規(guī)范族和GO函數(shù)畫出DFA 構(gòu)造項(xiàng)目集規(guī)范族方法 構(gòu)造LR 0 項(xiàng)目集規(guī)范族的 例如 文法G為 S aBCB bC c拓廣文法G 為 1 S S 2 S aBC 3 B b 4 C c句子 abc 的規(guī)范歸約過程如下 abc aBc aBC S S 運(yùn)用圖識別輸入串 abc 的過程 有效項(xiàng)目 課本P86類似 項(xiàng)目A 1 2對活前綴 1是有效的 存在規(guī)范推導(dǎo) 在任何時候 分析棧中的活前綴X1X2 Xm的有效項(xiàng)目集正是狀態(tài)棧頂Sm所代表的那個集合 也正是從識別活前綴的DFA的初態(tài)出發(fā) 讀出X1X2 Xm后到達(dá)的那個項(xiàng)目集 狀態(tài) LR分析的基本定理 陳火旺 P108 文法G S S EE aA bBA cA dB cB d考慮 項(xiàng)目 B c BB cBB d活前綴 bcS E bB bc B 項(xiàng)目B c B S E bB bcB bccB 項(xiàng)目B cB S E bB bcB bcd 項(xiàng)目B d 項(xiàng)目A 1 2對活前綴 1是有效的 其條件是存在規(guī)范推導(dǎo) 相關(guān)定義 LR 0 文法 不存在以下兩種沖突的文法移進(jìn) 歸約沖突歸約 歸約沖突LR 0 表 由LR 0 文法得到的分析表LR 0 分析器 使用LR 0 表的分析器 LR 0 分析表的構(gòu)造 給定文法G 設(shè)文法G拓廣為文法G 假若文法G 的項(xiàng)目集規(guī)范族 識別句型的活前綴確定有限自動機(jī) 已經(jīng)給出 其狀態(tài) 項(xiàng)目集 為I0 I1 In 則分析表的構(gòu)造算法如下 算法中 Ii狀態(tài)用右下角標(biāo)i表示 Sj rk的意義同前 分析表的構(gòu)造方法如下 1 設(shè)GO Ii X Ij 若X VT 則置Action i X Sj 表示將狀態(tài)j和終結(jié)符X移進(jìn)棧 若X VN 則置GOTO i X j 表示將狀態(tài)轉(zhuǎn)換為j進(jìn)棧 2 設(shè)項(xiàng)目A Ii 若A不是文法的開始符號 則置Action i a rk rk表示用文法的第k個產(chǎn)生式進(jìn)行歸約 a 表示集合VT 的所有符號 若A是文法的開始符號 則置Action i acc 符號 表示句子右界符 3 分析表中的空白表示出錯 1 S S 2 S aBC 3 B b 4 C c 練習(xí) 假定文法的各個產(chǎn)生式的編號如下 構(gòu)造其LR 0 項(xiàng)目集規(guī)范族和LR 0 分析表 0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d DFA構(gòu)造 部分 CLOSURE S E S E E aA E bB 此即為DFA的狀態(tài)0 令I(lǐng) S E E aA E bB GO I a CLOSURE E a A 即I中所有圓點(diǎn)之后緊跟a的 E a A A cA A d GO I b CLOSURE E b B E b B B cB B d GO I E CLOSURE S E S E 同上步驟 依次對各項(xiàng)目集進(jìn)行計(jì)算 略 LR 0 分析表構(gòu)造 DFA部分圖 全圖見下頁 文法G0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d E a b 文法G0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d E 該文法的LR 0 分析表 該文法的LR 0 分析表如下所示 文法G0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d 試對acccd進(jìn)行分析 例 按上表對acccd進(jìn)行分析步驟狀態(tài)棧符號棧輸入串10 acccd 202 acccd 3024 acccd 40244 acccd 502444 acccd 60244410 acccd 7024448 acccA 802448 accA 90248 acA 10026 aA 1101 E 文法G0 S E1 E aA2 E bB3 A cA4 A d5 B cB6 B d LR 0 分析法的局限性 語法動作沖突 LR 0 分析法的關(guān)鍵 由項(xiàng)目集規(guī)范族構(gòu)造LR 0 分析表任給一狀態(tài) 項(xiàng)目集 和任一符號 a a VT 使得Action i a 的值是唯一的 無沖突 若Action i a 值不唯一 我們稱為語法動作沖突 分情況討論 1 無沖突 若一個項(xiàng)目集Ii中僅含移進(jìn)項(xiàng)目或僅含一個規(guī)約項(xiàng)目 則Action i a 的值是唯一的 其中 a VT 2 移進(jìn)歸約沖突 若一個項(xiàng)目集Ii中 既含有移進(jìn)項(xiàng)目 又含有歸約項(xiàng)目 此時 Action i a 值不唯一 其中 a VT i表示狀態(tài)Ii 3 歸約歸約沖突 若一個項(xiàng)目集Ii中 存在兩個或兩個以上的歸約項(xiàng)目 則Action i a 的值不唯一上述 2 3 兩種情況中的動作沖突 有一部分可以使用FOLLOW集解決 即SLR 1 分析法 例4 6設(shè)文法為 0 S S 1 S abdD 2 S aBc 3 B b 4 D dLR 0 項(xiàng)目集規(guī)范族應(yīng)按如下規(guī)則填寫 c FOLLOW B Action 3 c r3Action 3 d S4 d不屬于FOLLOW B 所以 Action 3 d r3 4 3 3 SLR 1 表的構(gòu)造方法 SLR是LR 0 的一種改進(jìn) 它在歸約時除了考慮歷史情況之外還考慮了現(xiàn)實(shí)輸入 0 S S 1 S abdD 2 S aBc 3 B b 4 D d 對于I3SLR 1 填寫規(guī)則 c FOLLOW B Action 3 c r3Action 3 d S4 為什么當(dāng)x FOLLOW B 時 SLR 1 分析表填A(yù)ction 3 x r3 而Action 3 d s4呢 因?yàn)镾 aBdD不成立 而S S abdD成立 也就是說 aBdD 不是句型 B后面只能出現(xiàn) x 不能出現(xiàn) d 0 S S 1 S abdD 2 S aBc 3 B b 4 D d 歸約 歸約沖突例若I X b A B 若當(dāng)前輸入符號為b 則含有移進(jìn) 歸約沖突 而A和B 又含有歸約 歸約沖突 則當(dāng)I面臨任何輸入符號a時 可做出如下 移進(jìn) 歸約 決策 若a b 移進(jìn) 若a屬于FOLLOW A 則用A 歸約 若a屬于FOLLOW B 則用B 歸約 此外 報錯 I X b A B 2 SLR 1 表的構(gòu)造方法 若項(xiàng)目A a 屬于Ik且GO Ik a Ij a為終結(jié)符 且置ACTION k a 為 把狀態(tài)j和符號a移進(jìn)棧 簡記為 sj 若項(xiàng)目A 屬于Ik 那么 對任何輸入符號a a FOLLOW A 置ACTION k a 為 用產(chǎn)生式A 進(jìn)行歸約 簡記為 rj 其中 假定A 為文法G 的第j個產(chǎn)生式 若項(xiàng)目S S 屬于Ik 則置ACTION k 為 接受 簡為 acc 若GO Ik A Ij A為非終結(jié)符 則置GOTO k A j 分析表中凡不能使用規(guī)則1至4填入信息的空白格均置上 出錯標(biāo)志 只在歸約時展望 即 已到產(chǎn)生式末尾 則去判斷FOLLOW A SLR 1 分析表項(xiàng)目集 0 S S 1 S abdD 2 S aBc 3 B b 4 D d 文法G 0 S E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 練習(xí) 對如下文法構(gòu)造其SLR 1 分析表 FOLLOW集如下 FOLLOW S FOLLOW E FOLLOW T FOLLOW F 該文法的LR 0 項(xiàng)目集規(guī)范族 由這些項(xiàng)目集的轉(zhuǎn)換函數(shù)GO表示成的DFA 文法G的非終結(jié)符的FOLLOW集如下 FOLLOW S FOLLOW E FOLLOW T FOLLOW F SLR分析表 I0 S EE E TE TT T FT FF E F i I2 E T T T F I1 S E E E T I4 F E E E TE TT T FT FF E F i I7 T T FF E F i I10 T T F I6 E E TT T FT FF E F i I8 F E E E T I11 F E I9 E E T T T F I5 F i I3 T F T E i i F F E T I2 T F i I3 I5 F I4 i I5 FOLLOW S FOLLOW E FOLLOW T FOLLOW F 文法G的SLR分析表如下所示 FOLLOW S FOLLOW E FOLLOW T FOLLOW F 任一文法 可按上述算法構(gòu)造一張表 若表無多重定義入口 則此表稱為SLR 1 分析表 具有SLR 1 分析表的文法 稱為SLR 1 文法 具有SLR 1 分析表的分析器 SLR 1 分析表 總控程序 稱為SLR 1 分析器 1 非SLR 1 文法舉例例4 7文法 0 S S 1 S aCaCb 2 S aDb 3 C a 4 D a 4 3 4 LR 1 分析表的構(gòu)造 I3有歸約沖突 用C D的后繼符號 FOLLOW C a b FOLLOW D b 解決不了沖突 因?yàn)?FOLLOW C FOLLOW D b 完整LR 0 項(xiàng)目集規(guī)范族見課本 0 S S 1 S aCaCb 2 S aDb 3 C a 4 D a 問題 有些無二義文法會產(chǎn)生 移進(jìn) 歸約 沖突或 歸約 歸約 沖突產(chǎn)生原因 SLR 1 分析法未包含足夠多的 展望 信息解決辦法 讓每個狀態(tài)含有更多的 展望 信息方法 重新定義項(xiàng)目 使得每個項(xiàng)目都附帶有k個終結(jié)符 即每個項(xiàng)目的形式為 A a1a2 ak LR 1 分析表的構(gòu)造 LR 0 項(xiàng)目A 加上k個搜索符a1a2 ak 就構(gòu)成一個LR k 項(xiàng)目 A a1a2 ak 其中 ai VT i 1 2 k 此項(xiàng)目要求存在規(guī)范推導(dǎo)S Aa1a2 ak a1a2 ak 這里僅考慮LR 1 項(xiàng)目 A a LR 0 項(xiàng)目與LR 1 項(xiàng)目之間的區(qū)別是后者多了一個搜索符 2 LR k 項(xiàng)目與LR 1 有效項(xiàng)目 向前搜索符a僅對歸約項(xiàng)目 A a 有意義 歸約項(xiàng)目 A a 意味著 當(dāng)它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的輸入符號為a時 才可以把棧頂上的 歸約為A只研究k 1的情形 說明 定義4 15我們稱一個LR 1 項(xiàng)目 A a 對活前綴 是有效的 如果存在規(guī)范推導(dǎo)S AW W其中 a FIRST W 若W 則a S AW W其中 a FIRST W 例4 8 0 S S 1 S BB 2 B aB 3 B bLR 1 項(xiàng)目 B a B a 對活前綴 aaa是有效的 這里 aa a B 對于活前綴 aaa 下面給出規(guī)范推導(dǎo)證明 S S BB Bab aBab aaBab aaa Bab即 S aaBab aaaBab aaaBab 中 aaa 是規(guī)范句型的前綴 而且不含句柄 aB 之后的符號 所以是活前綴 3 LR 1 項(xiàng)目集規(guī)范族的構(gòu)造算法 算法與構(gòu)造LR 0 項(xiàng)目集規(guī)范族類似 對任意LR 1 項(xiàng)目集I 需定義Closure I 和GO I X 其中 X VN VT 定義4 16 a 若I是一個LR 1 項(xiàng)目集 則置Closure I I b 若項(xiàng)目 A B a Closure I 且B 是一產(chǎn)生式 則對于b FIRST a 的每個符號 做 Closure I Closure I B b c 重復(fù) b 直至Closure I 不再擴(kuò)大為止 對于A有 S AW B W 同理對于B也符合定義 例如 文法S ABA aB b假設(shè)I S AB 則Closure I S AB A a b 定義4 17 令I(lǐng)是一個項(xiàng)目集 X是一個文法符號 函數(shù)GO I X 定義為 GO I X CLOSURE J 其中J 形如 A X a 的項(xiàng)目 A X a I 注意 搜索符號a不改變 例如項(xiàng)目集I0 S AB A a b 則GO I0 A S A B B b LR 1 項(xiàng)目集規(guī)范族算法設(shè)所給文法G 定義拓廣文法G S voidintemsetsb G C closure S S do for C中的每個項(xiàng)目集I和G 中的每個文法符號X if GO I X 非空且不屬于G 將GO I X 加入G while G不擴(kuò)大為止 例4 7 0 S S 1 S aCaCb 2 S aDb 3 C a 4 D a 練習(xí) 例4 8 0 S S 1 S BB 2 B aB 3 B b構(gòu)造LR 1 項(xiàng)目集規(guī)范族 0 S S 1 S BB 2 B aB 3 B b 4 構(gòu)造LR 1 分析表的步驟 確定LR 1 項(xiàng)目 利用函數(shù)CLOSURE和GO求DFA 即 構(gòu)造LR 1 項(xiàng)目集規(guī)范族 根據(jù)DFA 構(gòu)造LR 1 分析表 根據(jù)DFA 構(gòu)造LR 1 分析表 設(shè)文法G的LR 1 項(xiàng)目集為 I0 I1 In 在分析表中 用狀態(tài)i表示第i個項(xiàng)目集Ii 分析表的構(gòu)造算法如下 1 若LR 1 項(xiàng)目 A X a Ii 且GO Ii X Ij 則當(dāng)X VT時 置ACTION i X Sj 當(dāng)X VN時 置GOTO Ii X j 2 若 A a Ii 且A 是文法的第k個產(chǎn)生式 則當(dāng)A Vn S 時 置ACTION i a rk rk表示使用第k個產(chǎn)生式的歸約 當(dāng)A S a 時 置ACTION i acc 3 空白表示出錯 例4 8拓廣文法的規(guī)范LR分析表 0 S S 2 B aB 1 S BB 3 B b LR 1 分析法小結(jié) LR 1 分析表的構(gòu)造 狀態(tài)集的計(jì)算方法和LR 0 基本相同 分析表的構(gòu)造方法和LR 0 基本相同 構(gòu)造方法的不同點(diǎn) 歸約動作的選擇 SLR 1 分析參考FOLLOW集歸約 LR 1 分析僅考慮LR 1 項(xiàng)目中的后繼符 LR 1 方法的優(yōu)缺點(diǎn) 解決了SLR 1 分析所難以解決的 移進(jìn) 歸約 或 歸約 歸約 沖突 LR 1 分析表狀態(tài)多 規(guī)模大 算法適用范圍廣 4 3 5LALR 1 方法 LALR lookahead LR 技術(shù) 這種方法在實(shí)際中是經(jīng)常使用的 LALR 1 和SLR LR 0 的分析表有同樣多的狀態(tài) 而規(guī)范LR分析表要大得多 LALR 1 的能力介于SLR 1 和規(guī)范LR 1 之間 LALR 1 分析表的構(gòu)造 問題 對于一般的語言 規(guī)范LR分析表要用幾千個狀態(tài) 實(shí)際應(yīng)用很困難分析 由例4 8中可以看到 有些狀態(tài)集除了搜索符不同外是兩兩相同的解決辦法 合并同心集 構(gòu)造LALR 1 分析表 我們稱兩個LR 1 項(xiàng)目集具有相同的心 如果除去搜索符之后 這兩個集合是相同的 LR 0 項(xiàng)目相同 將所有同心的LR 1 項(xiàng)目集合并后 得到一個心就是一個LR 0 項(xiàng)目集 說明 I3 B a B a bB aB a bB b a b I6 B a B B aB B b I36 B a B a b B aB a b B b a b 合并為 合并項(xiàng)目集時要修改轉(zhuǎn)換函數(shù) 即GO I X 動作ACTION應(yīng)進(jìn)行修改 使得能夠反映各被合并的集合的既定動作 LR 1 項(xiàng)目集導(dǎo)入同心集Ii0 Ii1 Iik的弧 現(xiàn)導(dǎo)入合并后的項(xiàng)目集JP 弧上標(biāo)記不變 由同心集Ii0 Ii1 Iik導(dǎo)出的弧 改由JP導(dǎo)出 弧上標(biāo)記不變 根據(jù)圖4 13I3和I6 I4和I7 I8和I9分別為同心集 I3 B a B a bB aB a bB b a b I6 B a B B aB B b I4 B b a b I7 B b I8 B aB a b I9 B aB I36 B a B a b B aB a b B b a b I47 B b a b I89 B aB a b 合并為 合并為 合并為 合并同心集不會產(chǎn)生新的移進(jìn) 歸約沖突 但有可能產(chǎn)生新的 歸約 歸約 沖突 若同心集合并前 任一同心集無移進(jìn) 歸約沖突 則合并后 不可能引起歸約 移進(jìn)沖突 若 a1 am X1 Xn 則有語法分析動作沖突 反之無沖突 合并同心集 可能引起歸約與歸約沖突 例 下面文法是LR 1 的 但不是LALR 1 的 S SS aAd bBd aBe bAeA cB c S S S aAd S bBd S aBe S bAe S S S a Ad S a Be A c d B c e a S S b Bd S b Ae A c e B c d b A S aA d B S aB e c A c d B c e A c e B c d c 引起歸約與歸約沖突 I3和I5合并得 對于同一個文法 LALR分析表和SLR分析表具有相同數(shù)目的狀態(tài) 卻能處理一些SLR所不能分析的文法 思考 文法 S L R 2 S R 3 L R 4 L i 5 R L 0 S S判斷該文法是否是LR 0 SLR 1 LR 1 LALR 1 文法 文法 S L R 2 S R 3 L R 4 L i 5 R L 0 S S S L RR L LR 0 項(xiàng)目 S L R R L LALR 1 項(xiàng)目 A 構(gòu)造LALR分析表的第一個算法 步驟 構(gòu)造文法G的LR 1 項(xiàng)目集族C I0 I1 In 把所有的同心集合并在一起 記C J0 J1 Jm 為合并后的新族 那個含有項(xiàng)目 S S 的Jk為分析表的初態(tài)從C 構(gòu)造ACTION表構(gòu)造GOTO表分析表空白格均填上 出錯標(biāo)志 a 若項(xiàng)目 A a b 屬于Jk且GO Jk a Jj a為終結(jié)符 則置ACTION k a 為 sj b 若項(xiàng)目 A a 屬于Jk 則置ACTION k a 為 用產(chǎn)生式A 歸約 簡記為 rj 其中 假定A 為文法G 的第j個產(chǎn)生式 c 若項(xiàng)目 S S 屬于Jk 則置ACTION k 為 接受 簡記為 acc 從C 構(gòu)造ACTION表 根據(jù)圖4 13I3和I6 I4和I7 I8和I9分別為同心集 I3 B a B a bB aB a bB b a b I6 B a B B aB B b I4 B b a b I7 B b I8 B aB a b I9 B aB I36 B a B a b B aB a b B b a b I47 B b a b I89 B aB a b 合并為 合并為 合并為 由合并后的集族所構(gòu)成的LALR分析表 結(jié)論 LALR 1 分析法比LR 1 分析法對某些錯誤發(fā)現(xiàn)的時間推遲 合并同心集后多做了規(guī)約 一個文法是LALR 1 文法 也是LR 1 文法 但不一定是SLR 1 LR 0 文法 一個文法是LR 1 文法 不一定是LALR 1 文法 LR 1 分析方法和LL 1 分析方法的比較 LR分析方法和LL 1 分析方法的比較 LR 1 分析方法和LL 1 分析方法的比較 4 3 6二義文法的應(yīng)用 任何二義文法不是一個LR文法 因而也不是SLR 1 或LALR 1 文法 但二義文法的問題是因其沒有定義算符優(yōu)先級和結(jié)合規(guī)則而產(chǎn)生了二義性 因此 下面討論使用LR分析法的基本思想 憑借一些其它條件分析二義文法 二義文法G1 E E E E E E i非二義的文法G2 E E T TT T F FF E i對比可以發(fā)現(xiàn)G1有兩個優(yōu)點(diǎn) 1 若需要改變算符的優(yōu)先級或結(jié)合規(guī)則 不需要改變文法G1本身 2 文法G1的分析表所包含的狀態(tài)肯定比G2的狀態(tài)要少得多 因?yàn)?在文法G2中含有單個非終結(jié)符的產(chǎn)生式 這些產(chǎn)生式是用來定義算符的優(yōu)先級和結(jié)合規(guī)則的 它們要占用不少狀態(tài)和消耗不少時間 二義文法分析 使用LR分析法的基本思想 憑借其他一些條件 來分析二義文法所定義的語言 可以根據(jù)二義文法構(gòu)造出LR分析表 其步驟是 1 構(gòu)造LR 0 分析表 2 對于發(fā)生沖突的項(xiàng)目用SLR方法解決 3 對于SLR方法解決不了的沖突借助于其它條件解決 使用算符的優(yōu)先級和結(jié)合規(guī)則的有關(guān)信息解決 移進(jìn) 或接受 歸約 或接受 沖突 賦予每個終結(jié)符和產(chǎn)生式以一定的優(yōu)先級 假定在面臨輸入符號a時碰到移進(jìn) 歸約 假定用A 歸約 的沖突 則比較終結(jié)符a和產(chǎn)生式A 的優(yōu)先級 若A 的優(yōu)先級高于a的優(yōu)先級 則執(zhí)行歸約 反之則執(zhí)行移進(jìn) E E E E E E i1 構(gòu)造LR 0 分析表 部分 E EE E EE E EE E E i E E E E EE E E E E E E E EE E EE E E i E i i i E E EE E EE E EE E E i E E E E E E EE E E I7 E E E E E E i2 用SLR方法解決部分沖突例如 狀態(tài)I1 E E E E EE E i其中存在接受 移進(jìn)沖突 它可以用SLR方法解決 3 用SLR方法解決不了的沖突例如 狀態(tài)I7 E E E E E EE E E其中存在歸約 移進(jìn)沖突 此時 只能采取加入附加條件的辦法 對狀態(tài)7 讀到 究竟應(yīng)該先做加法的歸約呢還是應(yīng)該先做乘號的移進(jìn) 由于我們認(rèn)為乘法的優(yōu)先級高于加法 所以這里應(yīng)該做乘法的移進(jìn) 對狀態(tài)7 讀到 究竟應(yīng)該先做加法的歸約呢還是應(yīng)該先做加號的移進(jìn) 由于我們認(rèn)為相同優(yōu)先級的算符服從左結(jié)合 所以這里應(yīng)該做加法的歸約 例4 9設(shè)描述兩種條件語句的文法為 0 S S 1 S iSeS 2 S iS 3 S aFOLLOW S e 按照算法語言的習(xí)慣要求 我們規(guī)定Action 4 e S5 相當(dāng)于有 else 的條件語句優(yōu)先 圖4 16的項(xiàng)目集除了 I4 以外無動作沖突 所以 人為地解決LR項(xiàng)目集的動作沖突 可構(gòu)造出LR分析表 一 基本含義YetAnotherCompiler compilerSteveJohnson在1975年為Unix系統(tǒng)編寫的Yacc的GNU GNU sNotUnix自由軟件 版叫做Bison二 基本功能接受用戶提供的文法 可能是二義性的 優(yōu)先級 結(jié)合性質(zhì)等附加信息 自動產(chǎn)生這個文法的LALR分析表 有些YACC甚至可包括接受語義描述和目標(biāo)機(jī)器描述 并完成源語言到目標(biāo)代碼的翻譯 分析表的自動生成 YACC 用生成器Yacc構(gòu)造翻譯器的過程 Yacc編譯器 yacc源程序translate y y tab c C編譯器 y tab c a out a out 源程序 輸出 語法分析小結(jié) 語法分析 自上而下語法分析 自下而上語法分析 LL 1 分析法 遞歸下降分析法 優(yōu)先分析法 LR分析法 LR 0 SLR 1 LR 1 LALR 1 直觀算符優(yōu)先分析法 算符優(yōu)先分析法 參考資料 陳火旺 程序設(shè)計(jì)語言編譯原理 第三版 國防工業(yè)出版社 83 129馮博琴譯 現(xiàn)代編譯程序設(shè)計(jì) 郵電出版社 2 2 3 2 2 4KennethC Louden 馮博琴等譯 編譯原理與實(shí)踐 機(jī)械工業(yè)出版社AlfredV Aho RaviSethi JeffreyD Ullman Compilers Principles Techniques andTools Addison Wesly 1986