【正文】 第六章 LR分析法及分析程序自動構造 第六章 LR分析法及分析程序自動構造（ 1） 第一節(jié) 概述 ?本章介紹上下文無關文法的 LR分析方法及分析程序的自動構造 ?LR：自左至右掃描 ,最右推導的逆過程 一、 LR方法 在規(guī)范歸約過程中，一方面記住已移進和歸約的整個符號串，另一方面根據(jù)當前所用的產(chǎn)生式推測未來可能碰到的輸入符號 . 第六章 LR分析法及分析程序自動構造（ 2） 第一節(jié) 概述 一、 LR方法 ? 優(yōu)點：與其它技術相比，適應文法范圍更廣。能力更強，識別效率相當，尤其在自左向右掃描輸入串時就能發(fā)現(xiàn)其中錯誤，并能準確指出出錯位置。 ? 缺點：若用手工構造分析程序，工作量太大，且容易出錯，所以必須使用自動產(chǎn)生這種分析程序的產(chǎn)生器。 ? 應用產(chǎn)生器產(chǎn)生一大類上下文無關文法的 LR分析程序 ? 對二義性文法或難分析的特殊文法，施加一些限制，使之能用 LR分析。 第六章 LR分析法及分析程序自動構造（ 3） ?LR分析法通過 LR分析器來實現(xiàn) 總控程序 分析表 輸出帶 第一節(jié) 概述 二、 LR分析器 輸入帶 下推棧 第六章 LR分析法及分析程序自動構造（ 4） 從邏輯上說， LR分析器包括兩部分： —總控程序，或稱為語法分析程序； —分析表 ? 注：后面要學習的所有 LR分析器的總控程序都相同。僅僅是它們的分析表不同 總控程序作用： —查分析表，根據(jù)分析表的內(nèi)容做若干簡單動作，如讀頭后移，入棧出棧等。 ? 注：由于總控程序很簡單，所以產(chǎn)生器的任務就是產(chǎn)生分析表 第一節(jié) 概述 二、 LR分析器 第六章 LR分析法及分析程序自動構造（ 5） ? 一個文法的 LR分析器常常對應著若干不同分析表，所有分析表都恰好識別文法所產(chǎn)生的所有語句 ? 本章將討論四種不同分析表構造方法 —(0)分析表： ? 分析能力有限，但這是建立其它 LR分析法的基礎。 —： ? 簡單 LR分析表構造法，是一種容易實現(xiàn)又有實用價值的方法，但存在一些文法構造不出 SLR分析表 第一節(jié) 概述 三、分析表 第六章 LR分析法及分析程序自動構造（ 6） ? 規(guī)范 LR分析表 —它能力最強，但實現(xiàn)代價過高，分析表尺寸太大 ? LALR分析表 —向前看 LR分析表構造文法，也是一種常用方法 ? 注：實際上， SLR和 LALR分別是對 LR(0)和規(guī)范 LR的改進 ? 最后，將討論如何使用二義文法構造 LR分析器并產(chǎn)生高效的分析技術 第一節(jié) 概述 三、分析表 第六章 LR分析法及分析程序自動構造（ 7） LR分析器 一、 LR分析法的基本思想 ? 在規(guī)范歸約時，當一串貌似句柄的符號串呈現(xiàn)于棧頂時， LR分析法根據(jù)三方面的信息找句柄： —歷史：記錄在棧內(nèi)的符號串移進，歸約的歷史情況 —展望：預測句柄之后可能出現(xiàn)的信息； —現(xiàn)實：讀頭下的符號 ? 注： LR分析法的基本思想是符號人的思維習慣的，但實現(xiàn)有困難，因為基于 “ 歷史 ” 對未來的 “ 展望 ”可能存在多種可能。當把 “ 歷史 ” 和 “ 展望 ” 材料綜合在一起時復雜性就大大增加。如果簡化對“ 展望 ” 的要求，就可獲得實際可行的分析算法。 第六章 LR分析法及分析程序自動構造（ 8） LR分析器 總控程序 分析表 輸出帶 輸入帶 下推棧 二、 LR分析器 ?一個 LR分析器實際上是帶有下推棧的確定的有限狀態(tài)自動機?？蓪⒁粋€ “ 歷史 ” 與這個 “ 歷史 ” 下的展望信息綜合為抽象的一個狀態(tài) 第六章 LR分析法及分析程序自動構造（ 9） ?下推棧： —下推棧用于存放分析輸入串過程中的所有和“ 歷史 ” 及相應 “ 展望 ” 信息形成的抽象狀態(tài) —由于每個狀態(tài)都概括了從分析開始到歸約階段的全部 “ 歷史 ” 和 “ 展望 ” 信息，所以 LR分析器的每步動作可由棧頂狀態(tài)和讀頭下符號唯一確定 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動構造（ 10） 下推棧： LR分析器 二、 LR分析器 sm s0 xm … … 狀態(tài)棧 符號棧 下推棧 棧頂指針 — 把一個 “ 歷史 ” 和這個 “ 歷史 ” 下的 “ 展望 ” 信息綜合為抽象的一個狀態(tài)，下推棧用于存放在對輸入串進行分析的過程中這些狀態(tài)，由于每個狀態(tài)都概括了從分析開始到歸約階段的全部 “ 歷史 ” 和 “ 展望 ” 信息，所以棧頂?shù)臓顟B(tài)就可用于決定當前的動作 第六章 LR分析法及分析程序自動構造（ 11） ?下推棧 ： LR分析器 二、 LR分析器 sm s0 xm … … 狀態(tài)棧 符號棧 下推棧 棧頂指針 — 為了便于了解棧頂狀態(tài)對正規(guī)分析過程的作用，我們把棧分為兩欄：狀態(tài)欄和符號欄。符號棧僅用于記錄迄今移進 歸約所得到的文法符號，由于它們已經(jīng)被概括在 “ 狀態(tài) ” 里了，所以對語法分析不起作用。 — 初始時，狀態(tài)棧放 S0（初態(tài)），符號棧放 “ ” （棧底符）；棧頂 Sm代表符號棧內(nèi)的符號串 XmXm1… X1及其展望信息 第六章 LR分析法及分析程序自動構造（ 12） LR分析器 二、 LR分析器 2 .分析表 ? LR分析器的核心是分析表 a1 a2 …… a n a1 a2… a n A1 A2… A n S0 . . Sk ?這張分析表包含兩部分：動作表（ Action)和轉(zhuǎn)向表 (GoTo)，它們都是二維數(shù)組 ?Si表示狀態(tài)， ai表示終結符， Ai表示非終結符 Action goto 第六章 LR分析法及分析程序自動構造（ 13） 狀態(tài) ACTION GOTO i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構造（ 15） 2 .分析表 ? 2）動作表 ACTION —ACTION[S,a]表示在當前狀態(tài) S下，面臨讀頭下的符號 a所應采取的動作， —注：該動作有四種可能：移進，歸約，出錯，接受 ? 3）轉(zhuǎn)向表 (GOTO) —GOTO[S,X]表示：若 X∈V T，表示在當前狀態(tài)下，讀入 X應轉(zhuǎn)向什么狀態(tài)；若 X∈V N，表示當前棧頂句柄歸約成 X后，應轉(zhuǎn)向什么狀態(tài) —注：對終結符的移進動作和轉(zhuǎn)向動作可以合并在一起填在動作表中，這樣，轉(zhuǎn)向表可以只保留非終結符轉(zhuǎn)向部分 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動構造（ 14） 狀態(tài) ACTION GOTO i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構造（ 15） ? 1）移進 把 (Sm,ai)的下一個狀態(tài) S’=GOTO(Sm,ai)連同讀頭下符號推進棧內(nèi) ,棧頂成為 (S’,ai),讀頭前進一格 ? 2）歸約 指用某產(chǎn)生式 A b進行歸約。若 b的長度為 g，則彈出棧頂?shù)?g個元素，使得棧頂?shù)臓顟B(tài)變成 Smg,然后把 （ Smg,A)的下一個狀態(tài) S’=GOTO(Smg,A)連同非終結符 A一起推進棧，棧頂變成（ S’,A)，讀頭不動。 ? 3）接受 分析成功，退出總控程序 ? 4）報錯 輸入串出錯，調(diào)出相應出錯程序 ? 注：不管哪一類分析程序，總控程序的動作都一樣。程序本身很簡單，按動作表中填的內(nèi)容具體實施而已。 LR分析器 二、 LR分析器 第六章 LR分析法及分析程序自動構造（ 17） LR分析器 ?例：根據(jù)表達式文法的 LR分析表分析輸入串i*i+i的 LR動作過程 ? E E+T ? E T ? T T*F ? T F ? F (E) ? F i 第六章 LR分析法及分析程序自動構造（ 18） 狀態(tài) ACTION GOTO i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構造（ 19） ? 注：表中符號的含義： ? —Sj shift j,指將讀入符號 a移進棧內(nèi)并轉(zhuǎn)到 j狀態(tài)，棧頂變成（ j,a)。 ? —rj reduce j ,按第 j號產(chǎn)生式進行歸約； ? —acc accept,分析成功； ? —空白格 出錯標志，若填入相應出錯處理程序的編號，便轉(zhuǎn)相應程序處理。 ? —分析過程 ? —LR分析器的動作情況也可以描述成機器內(nèi)部的格局間轉(zhuǎn)換，其格局用三元式表示為（狀態(tài)棧，已歸約的符號棧，待繼續(xù)分析的輸入串） LR分析器 第六章 LR分析法及分析程序自動構造（ 16） 狀態(tài) ACTION GOTO i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構造（ 19） 0 狀態(tài)、符號棧 i*i+i ?E E+T ?E T ?T T*F ?T F ?F (E) ?F i 第六章 LR分析法及分析程序自動構造（ 20） 狀態(tài) ACTION GOTO i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構造（ 19） 0 狀態(tài)、符號棧 *i+i ?E E+T ?E T ?T T*F ?T F ?F (E) ?F i 5 i 5 i 第六章 LR分析法及分析程序自動構造（ 21） 狀態(tài) ACTION GOTO i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1 10 r3 r3 r3 r3 11 r5 r5 r5 r5 第六章 LR分析法及分析程序自動構造（ 19） 0 狀態(tài)、符號棧 *i+i ?E E+T ?E T ?T T*F ?T F ?F (E) ?F i 3 F 第六章 LR分析法及分析程序自動構造（ 22） 狀態(tài) ACTION GOTO i + * ( ) E T F 0 S5 S4 1 2 3 1 S6 acc 2 r2 S7 r2 r2 3 r4 r4 r4 r4 4 S5 S4 8 2 3 5 r6 r6 r6 r6 6 S5 S4 9 3 7 S5 S4 10 8 S6 S11 9 r1 r1 r1