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