編譯原理第4章語(yǔ)法分析自下而上LR分析法.ppt

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

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