【正文】 第 7章 自下而上的 LR(k)分析 本章討論 LR分析法 LR分析法 LR分析法是一種自下而上進行規(guī)范歸約的語法分析方法。 這里 L是指從左到右掃描輸入符號串。R是指構(gòu)造最右推導(dǎo)的逆過程。 這種分析法比遞歸下降分析法、預(yù)測分析法和算符優(yōu)先分析法對文法的限制要少得多。 大多數(shù)用無二義性上下文無關(guān)文法描述的語言都可以用 LR分析法進行有效的分析 ， LR分析法 而且這種分析法分析速度快，并能準確及時地指出輸入串的語法錯誤和出錯的位置。 但是，這種分析法有一個主要缺點，那就是對于一個語言的文法，構(gòu)造 LR分析器的工作量相當(dāng)大，具體實現(xiàn)較困難。 也就是說， 對于 本章主要 介紹 LR分析法的基本思想和 LR(0)、 SLR(1) 、 LR(1) 、 LALR(1)分析器的工作原理和構(gòu)造方法 。 LR分析法 LR分析法的基本思想 : LR分析法是一種規(guī)范歸約分析法。 規(guī)范歸約分析法的 關(guān)鍵 是在分析過程中如何確定分析棧棧頂?shù)姆柎欠裥纬删浔? LR分析器的邏輯結(jié)構(gòu)和工作過程 LR分析法確定句柄的 基本思想 是在規(guī)范歸約分析過程中，根據(jù)分析棧中記錄的已移進和歸約出的整個符號串（即歷史 ）和根據(jù)使用的規(guī)則推測未來可能遇到的輸入符號（即 展望 ）以及 現(xiàn)實 讀到的輸入符號這三個方面的信息來確定分析棧棧頂?shù)姆柎欠駱?gòu)成句柄。 LR分析器的邏輯結(jié)構(gòu)和工作過程 LR分析器的邏輯結(jié)構(gòu) 一個 LR分析器的邏輯結(jié)構(gòu)示意圖如下圖所示。 它由 分析棧 、 分析表 和 總控程序 3個部分組成。 總控程序 LR分析表 a1 ai am $ Sm Xm $ S0 X1 S1 分析棧 輸出 LR分析器的邏輯結(jié)構(gòu)和工作過程 分析棧用來存放分析過程中的歷史和展望信息。 LR分析法將歷史和展望信息抽象成狀態(tài)，并放在分析棧中，這就是說 分析棧中的每個狀態(tài)概括了從分析開始到某一歸約階段的整個分析歷史和對未來進行的展望 。 1. 分析棧 對此，下面用一個簡單例子來說明。 LR分析器的邏輯結(jié)構(gòu)和工作過程 例如，對文法 G[E]: E→E+T| T T→T*F | F F→(E) | id 狀態(tài) Sm不僅表征了從分析開始到現(xiàn)在已掃描過的輸入符號被歸約成 $E＋ T，而且由 Sm可以預(yù)測，如果輸入串沒有語法錯誤，根據(jù)歸約時所用規(guī)則（非終結(jié)符 T的規(guī)則）推測出未來可能遇到的輸入符號僅是 中的任意一個符號。 FOLLOW(T)={+,*,),$} Sm T E $ + S0 S1 分 析 棧 示 意 圖 LR分析器的邏輯結(jié)構(gòu)和工作過程 若當(dāng)前讀到的輸入符號是‘ *’ ，根據(jù)文法可知‘ *’的優(yōu)先級高于‘＋’，棧頂尚未形成句柄 ， 則應(yīng)將‘ *’移入棧中； 若當(dāng)前讀到的輸入符號是‘＋’或）或‘ $’時，根據(jù)文法可知棧頂已形成句柄，則應(yīng)將符號串 E＋ T歸約為 E； 若當(dāng)前讀到的輸入符號不是上述四種符號之一，則表示輸入串有語法錯誤。 由此可知 ， LR分析器的每一步分析工作，都是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一確定的。 LR分析器的邏輯結(jié)構(gòu)和工作過程 它們都是二維數(shù)組。 LR分析表是 LR分析器的核心部分。 一張 LR分析表由 和 兩部分組成， 狀態(tài)轉(zhuǎn)換表元素 GOTO[Si , X]規(guī)定了當(dāng)狀態(tài) Si面臨文法符號 X時，應(yīng)轉(zhuǎn)移到的下一個狀態(tài)。 2. LR分析表 分析動作 (ACTION)表 狀態(tài)轉(zhuǎn)換 ( GOTO )表 LR分析器的邏輯結(jié)構(gòu)和工作過程 分析動作表元素 ACTION[Si , a]規(guī)定了當(dāng)狀態(tài) Si面臨輸入符號 a時應(yīng)執(zhí)行的動作。 分析動作表對應(yīng)四種可能動作： ?移進 ：把狀態(tài) Sj=GOTO[Si , a]和輸入符號 a移入分析棧。 ?歸約 ：當(dāng)棧頂符號串 α形成句柄，且文法中 有 A→ α的規(guī)則，其中 |α|=β，則歸約 動作是從分析棧棧頂去掉 β個文法符 號和 β個狀態(tài)，并把歸約符 A和 GOTO[Si β， A]=Sj移入分析棧中。 LR分析器的邏輯結(jié)構(gòu)和工作過程 LR分析器的邏輯結(jié)構(gòu)和工作過程 ?接受 （ acc): 表示分析成功。此時，分析棧 中只剩文法開始符號 S39。和當(dāng)前讀到的 輸入符號是‘ $’。即輸入符號串已經(jīng)結(jié) 束。 ?報錯 ：表示輸入串含有錯誤，此時出現(xiàn)棧頂 的某一狀態(tài)遇到了不該遇到的輸入符 號。 總控程序也稱為驅(qū)動程序。 總控程序從左至右掃描輸入符號串，并根據(jù)當(dāng)前分析棧中棧頂狀態(tài)以及當(dāng)前讀到的輸入符號按照 LR分析表元素所指示的動作完成每一步的分析工作。 3. 總控程序 對所有的 LR分析器其總控程序是相同的 。 LR分析器的邏輯結(jié)構(gòu)和工作過程 總控程序算法 ： 輸入 ：輸入串 W和 LR分析表。 輸出 ：若 W是句子，得到 W的自下而上 分析成功，否則輸出錯誤信息。 ( LR分析器的工作過程的形式化描述 ) 算法 ：初始化時，初始狀態(tài) S0在分析棧 棧頂，輸入串 W$的第 1個符號讀 入 a中。 LR分析器的邏輯結(jié)構(gòu)和工作過程 { } 。 ) ( error) ] a , [ ( ERROR S ACTION if else == ) ] a , [ ( r S ACTION if else j == ) ] a , [ ( S S ACTION if i == ) ]! a , [ ( acc S ACTION while = } a a { i中； 將下一個輸入符號讀入 進棧； 和輸入符號將狀態(tài)} S A] , S GOTO[ A S′ | | | | { A j 〞= ? ? 進棧； 和 ，將當(dāng)前棧頂狀態(tài)為 個輸入符號退棧； 個狀態(tài)和 將 歸約： 條規(guī)則 用第a a aLR分析器的邏輯結(jié)構(gòu)和工作過程 例 1 設(shè)文法 G′為： 相應(yīng)于文法的 LR分析表如下表所示。 0. S39?！鶶 1. S→A 2. S→B 3. A→ aAb 4. A→c 5. B→ aBb 6. B→d LR分析器的邏輯結(jié)構(gòu)和工作過程 狀態(tài) ACTION a b c d $ GOTO S A B 6 7 8 9 10 S8 r6 r6 r6 r6 r6 S10 r3 r3 r3 r3 r3 r5 r5 r5 r5 r5 0 1 2 3 4 5 S4 S5 S6 acc S4 S5 S6 r4 r4 r4 r4 r4 1 2 3 7 9 r2 r2 r2 r2 r2 r1 r1 r1 r1 r1 對文法句子 aacbb$的 LR分析過程如下 : 初始化時，初始狀態(tài) 0 和句子的左界符 $在分析棧棧頂，讀入輸入串 aacbb$ 的第 1個符號 a 。 LR分析器的邏輯結(jié)構(gòu)和工作過程 5 0447 $aaA bb$ S8 4 0445 $aac bb$ 用第 4條規(guī)則 A→c 歸約 3 044 $aa cbb$ S5 2 04 $a acbb$ S4 步驟 棧中狀態(tài) 棧中符號 輸入串 分析動作 1 0 $ aacbb$ S4 a b c d $ S A B 0 S4 S5 S6 1 2 4 5 1 2 3 3 acc r1 r1 r1 r1 r1 r2 r2 r2 r2 r2 7 9 S4 S5 S6 r4 r4 r4 r4 r4 10 01 $S $ acc 9 02 $A $ 用第 1條規(guī)則 S→A 歸約 8 0478 $aAb $ 用第 3條規(guī)則 A→aAb 歸約 7 047 $aA b$ S8 6 04478 $aaAb b$ 用第 3條規(guī)則 A→aAb 歸約 5 0447 $aaA bb$ S8 4 0445 $aac bb$ 用第 4條規(guī)則 A→c 歸約 3 044 $aa cbb$ S5 2 04 $a acbb$ S4 步驟 棧中狀態(tài) 棧中符號 輸入串 分析動作 1 0 $ aacbb$ S4 LR分析器的邏輯結(jié)構(gòu)和工作過程 LR（ 0）分析法 LR(0)分析就是在分析的每一步，只需根據(jù)當(dāng)前棧頂狀態(tài)而不必向前查看輸入符號就能確定應(yīng)采取的分析動作。 LR分析器的關(guān)鍵部分是分析表的構(gòu)造。 構(gòu)造 LR分析表的 基本思想是 : 從給定的上下文無關(guān)文法直接構(gòu)造識別文法所有規(guī)范句型活前綴的 DFA，然后再將 DFA轉(zhuǎn)換成一張 LR分析表。 LR（ 0）分析法 為了給出構(gòu)造 LR分析表的算法，需要定義一些重要的概念和術(shù)語。 ?文法規(guī)范句型的活前綴 1. 字符串的前綴是指字符串的任意首部。 例如，字符串 abc的前綴有 ε,a,ab,abc。 2. 規(guī)范句型活前綴是指規(guī)范句型的前綴， 這種前綴不包含句柄右邊的任何符號。 注意，活前綴可以是一個或者是若干個規(guī)范句型的前綴。 LR（ 0）分析法 10 01 $S $ acc 9 02 $A $ 用第 1條規(guī)則 S→A 歸約 8 0478 $aAb $ 用第 3條規(guī)則 A→aAb 歸約 7 047 $aA b$ S8 6 04478 $aaAb b$ 用第 3條規(guī)則 A→aAb 歸約 5 0447 $aaA bb$ S8 4 0445 $aac bb$ 用第 4條規(guī)則 A→c 歸約 3 044 $aa cbb$ S5 2 04 $a acbb$ S4 步驟 棧中狀態(tài) 棧中符號 輸入串 分析動作 1 0 $ aacbb$ S4 LR（ 0）分析法 由前例，對輸入串 aacbb＄的歸約過程，可以看出，當(dāng)所分析的輸入串沒有語法錯誤時，則在分析的每一步，分析棧中已移進一歸約的全部文法符號與余留的輸入符號串合起來，就是所給文法的 一個規(guī)范句型。 LR（ 0）分析法 這也就是說， 在 LR分析過程中的任何時刻，棧中的文法符號應(yīng)是某一規(guī)范句型的活前綴 ，這是因為一旦句型句柄在棧的頂部形成，就會立即被歸約，因此，只要輸入串已掃描過的部分保持可歸約成一個活前綴，那就意味著所掃描過的部分是正確的。 LR（ 0）分析法 例如，對前例，文法 G[S]的規(guī)范句型aaAbb的句柄是 aAb，棧中符號串為 aaAb，此句型的活前綴為 ε,a,aa,aaA,aaAb，它們均不含句柄右邊符號 b。 這樣一來，我們對句柄的識別就變成對規(guī)范句型活前綴的識別。 LR（ 0）分析法 10 01 $S $ acc 9 02 $A $ 用第 1條規(guī)則 S→A 歸約 8 0478 $aAb $ 用第 3條規(guī)則 A→aAb 歸約 7 047 $aA b$ S8 6 04478 $aaAb b$ 用第 3條規(guī)則 A→aAb 歸約 5 0447 $aaA bb$ S8 4 0445 $aac bb$ 用第 4條規(guī)則 A→c 歸約 3 044 $aa cbb$ S5 2 04 $a a