【正文】 第七章 LR 分析法 1965年， LR(K)文法及 LR(K)分析技術(shù)。 LR(K)分析是指自左向右掃描和自底向上的語法分析，且 在分析的每一步，只須根據(jù)分析棧中當(dāng)前已移進和歸約出的 全部文法符號，并至多再向前查看 K個輸入符號，就能確定 相當(dāng)于某一產(chǎn)生式右部符號的句柄是否已在分析棧的頂部形 成。從而也就可以確定所應(yīng)采取的分析動作（是移進輸入符號 還是按某產(chǎn)生式進行歸約）。 當(dāng)前掃描到 Xn+1,向前查看 k個符號，來確定是把 Xn+1移進棧，還是把 Xi…Xn 作為句柄進行歸約。 1） 要歸約時，則根據(jù)某產(chǎn)生式 U→XiXi+1…Xn 進行歸約： X1X2…Xi 1UXn+1Xn+2…Xn+k… 例： X1X2…Xi… Xn Xn+1Xn+2…Xn+kXn+k+1… 棧頂 （續(xù)頁） LR(0) 表示在每一步分析時都不用向前輸入符號 LR(1) 表示在每一步分析時都向前看一個輸入符號來決定當(dāng) 前的動作。 SLR(1) 表示簡單的 LR(1)，即只在動作不唯一的地方向前看一個符號，在動作唯一時則不向前看輸入符號。 2） 要移進時，即把 Xn+1進棧，并讀下一符號： X1X2…Xi…XnXn+1 Xn+2…Xn+k… 在棧中 當(dāng)前掃描符 棧頂 LR分析概論 一 .LR分析器的邏輯結(jié)構(gòu)及工作過程 從邏輯上來說，一個 LR分析器如圖 所示。 輸入串 … ai … a1 Sp→ X1 S1 S0 ┋ ┋ ┋ ┋ Xm Sm 總 控 程 序 輸出 ACTION 表 GOTO 表 其中 S棧為狀態(tài)棧 X棧為符號棧 棧 產(chǎn)生式 表 圖 LR分析器的邏輯結(jié)構(gòu) 即一個 LR(k)分析器主要由：總控程序，分析棧（狀態(tài)棧和符號棧）輸入隊列和分析表組成。一般來說所有 LR分析器的總控程序基本上是大同小異。只有分析表各不相同。一般主要討論三種不同的分析表的構(gòu)造方法。 第一種稱為規(guī)范 LR分析表構(gòu)造法。用此法構(gòu)造的分析表功能最強而且也適合于很多文法，但實現(xiàn)代價比較高。 第二種稱為簡單 LR(即 SLR)分析表構(gòu)造法。這是一種比較容易實現(xiàn)的方法。但 SLR分析表的功能太弱，而且對某些文法可能根本就構(gòu)造不出相應(yīng)的 SLR分析表。 第三種稱為向前 LR（即 LALR）分析表構(gòu)造法。這種方法構(gòu)造的分析表功能介于規(guī)范 LR分析表 SLR分析表之間。這種表適用于絕大多數(shù)程序語言的文法。而且也可以設(shè)法有效的實現(xiàn)。 二、 LR 分析器的分析過程如下： S0及句子的左界限 分別壓入狀態(tài)棧和符號棧中。 則用棧頂狀態(tài) Sm和當(dāng)前掃描符 ai組成符號對（ Sm, ai)去查 分析動作表，根據(jù) ACTION[Sm, ai]的指示完成相應(yīng)的分析動作。 表中每一表元素所規(guī)定的動作僅能是下列四種動作之一： S0S1 S2 … Sm Sm+1 ai+1 ai+2 … an X1 X2 … X m ai ↑ ↑ ↓ ，分析棧及余留的輸入串為如下格局： ↓ S0S1… Sm ai ai+1… an X1… X m ↑ ↑ （ 1） ACTION[Sm, ai]= Sm+1 （移進） 表明句柄尚未在棧頂形成，此時正期待移進輸入符號以便形成 句柄。故將當(dāng)前的輸入符號和表元素 Sm+1分別壓入棧中，有 （ 2） ACTION[Sm, ai]= Rj (歸約） 表明此時應(yīng)按文法的第 j個產(chǎn)生式 A→ Xmk+1Xmk+2 … Xm 進行歸約。即棧頂符號串 Xmk+1Xmk+2 … Xm已成為當(dāng)前句型的句 柄。所謂按第 j個產(chǎn)生式歸約，就是將分析棧中從頂向下的 k個符 號退棧，然后將文法符號 A壓入符號棧中。此時分析的格局為： ↓ S0S1… Smk ai ai+1… an X1… X mk A ↑ ↑ 然后以（ Smk,A)去查狀態(tài)轉(zhuǎn)移表，設(shè) GOTO[Smk,A]= Sl ,則將此新狀態(tài)壓入狀態(tài)棧中，則有如下格局： ↓ S0S1… Smk Sl ai ai+1… an X1… X mk A ↑ ↑ （ 3） ACTION[Sm, ai]=acc （接受） 表明當(dāng)前的輸入串已被成功地分析完畢，應(yīng)停止分析器的工作。 其中 Z為文法開始符號 Sα為使 ACTION[Sα ， ]=acc的 唯一狀態(tài)（接受狀態(tài)） （ 4） ACTION[Sm, ai]=ERROR（空白）。 表明當(dāng)前的輸入串中含有錯誤，也應(yīng)終止當(dāng)前的分析工作。轉(zhuǎn)出錯處理。 3. 重復(fù)上述第 2步的工作，直到分析棧頂出現(xiàn)“接受狀態(tài)”或“出錯狀態(tài)“為止。對接受狀態(tài)，分析棧的格局為： ↓ S0 Sα Z ↑ ↑ 例： 有文法 G[S]:1： S→aAcBe 2： A→b 3： A→Ab 4： B→d 其 ACTION表和 GOTO表為： 考察對輸入串 abbcde 的分析過程。 r1 r1 r1 r1 r1 r1 r4 r4 r4 r4 r4 r4 S9 r3 r3 r3 r3 r3 r3 7 S8 r2 r2 r2 r2 r2 r2 S6 S5 3 S4 acc 1 S2 B A S d b e c a GOTO ACTION 0 1 2 3 4 5 6 7 8 9 S a A c B e A b d b 圖 abbcde 的語法樹 對輸入串 abbcde 的分析過程為： ACTION GOTO 步驟 狀態(tài)棧 符號棧 輸入流 分析動作 下一狀態(tài) 1 0 abbcde S2(0,a) 2 02 a bbcde S4(2,b) 3 024 ab bcde r2(4,b) GOTO[2,A]=3 4 023 aA bcde S6(3,b) 6 023 aA cde S5(3,c) 5 0236 aAb cde r3(6,b) GOTO[2,A]=3 7 0235 aAc de S8(5,d) 8 02358 aAcd e r4(8,d) GOTO[5,B]=7 9 02357 aAcB e S9(7,e) 10 023579 aAcBe r1(9,) GOTO[0,S]=1 11 01 S acc(1,) 圖 abbcde的分析過程 ? LR分析過程中的性質(zhì)與特點： ? 棧中的文法符號串并上剩余的輸入串構(gòu)成一個右句型（規(guī)范句型） ? 當(dāng)該右句型的句柄出現(xiàn)在棧頂時，歸約，否則，移進 ? 棧中的文法符號串是當(dāng)前句型的前綴，該前綴不包含句型句柄后面的符號，稱之為 活前綴（ Viable Prefixes） LR(0) 分析表的構(gòu)造 為了給出構(gòu)造 LR(0)分析表的算法，引出一些術(shù)語： 規(guī)范句型的活前綴 前綴： 一個符號串的前綴是指該串的任意首部（包括 ?）。 例如 abc的前綴有： ?,a,ab,abc abcd的前綴有：?,a,ab,abc,abcd 由此可知，對于符號串 ? 而言，其前綴的數(shù)量為 ???+1。 例：有文法 G[S]:S→aAcBe[1] A→b[2] 這里在每條產(chǎn)生式后加上了產(chǎn) A→Ab[3] 生式的序號 [i]當(dāng)進行推導(dǎo)時把 B→d[4] 序號帶上，以便說明問題。 對輸入串 abbcde進行推導(dǎo)如下（最右推導(dǎo)）： S ? aAcBe[1] ? aAcd[4]e[1] ? aAb[3]cd[4]e[1] ? ab[2]b[3]cd[4]e[1] 由此可知， abbcde是該文法的句子。由于 LR方法是自底向上的 分析，故應(yīng)采用歸約。 最左歸約為： ab[2]b[3]cd[4]e[1] 用 [2]式歸約 ? aAb[3]cd[4]e[1] [3] ? aAcd[4]e[1] [4] ? aAcBe[1] [1] ? S 其中 ?表示歸約符 從歸約的過程可看出，每次歸約時，歸約前和歸約后的被 歸約部分與剩余部分合起來僅構(gòu)成文法的規(guī)范句型，而用哪個 產(chǎn)生式歸約僅取決于當(dāng)前句型的前面部分； X1X2…Xn[p] 其中 Xi為文法的符號， [p]為第 p個產(chǎn)生式序號。 如上例中每次歸約前句型的前面部分為： ab[2] aAb[3] aAcd[4] aAcBe[1] 我們把規(guī)范句型的這種前端部分的串稱為可歸前綴。實際上，它們恰好是符號棧棧頂形成句柄時符號棧中的內(nèi)容。 S→aAcBe[1] A→b[2] A→Ab[3] B→d[4] 這是因為一旦句型的句柄在符號棧頂形成，將會立即被歸約 之故。所以我們將把規(guī)范句型具有上述性質(zhì)（即不含句柄之后的 任何符號）的前綴稱之為 可歸前綴 。 對各規(guī)范句型有前綴： ab[2]b[3]cd[4]e[1]