編譯原理 第06章_LR分析法(1).ppt

《編譯原理 第06章_LR分析法(1).ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、6.1LR分析法LR分析法是一種自下而上進(jìn)行規(guī)范歸約的語法分析方法。這里L(fēng)是指從左到右掃描輸入符號串。R是指構(gòu)造最右推導(dǎo)的逆過程。LR分析法主要缺點(diǎn)：對于一個(gè)語言的文法，構(gòu)造LR分析器的工作量相當(dāng)大，具體實(shí)現(xiàn)較困難。因此，目前對于真正實(shí)用的編譯程序，采用構(gòu)造LR分析器的專用工具“YACC”自動(dòng)地構(gòu)造出LALR(1)語法分析器。本章主要介紹LR分析法的基本思想和LR(0)、SLR(1)、LR(1)、LALR(1)分析器的工作原理和構(gòu)造方法。6.1LR分析法LR分析法的基本思想:LR分析法是一種規(guī)范歸約分析法。規(guī)范歸約分析法的

2、關(guān)鍵是在分析過程中如何確定分析棧棧頂?shù)姆柎欠裥纬删浔?.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程LR分析法確定句柄的基本思想:在規(guī)范歸約分析過程中，根據(jù)分析棧中記錄的已移進(jìn)和歸約出的整個(gè)符號串（即歷史）和根據(jù)使用的規(guī)則推測未來可能遇到的輸入符號（即展望）以及現(xiàn)實(shí)讀到的輸入符號這三個(gè)方面的信息來確定分析棧棧頂?shù)姆柎欠駱?gòu)成句柄。6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程LR分析器的邏輯結(jié)構(gòu)一個(gè)LR分析器的邏輯結(jié)構(gòu)示意圖如下圖所示。它由分析棧、分析表和總控程序3個(gè)部分組成?？偪爻绦騆R分析表a1···ai···am#SmXm

3、······#S0X1S1分析棧輸出6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程分析棧用來存放分析過程中的歷史和展望信息。LR分析法將歷史和展望信息抽象成狀態(tài)，并放在分析棧中，這就是說分析棧中的每個(gè)狀態(tài)概括了從分析開始到某一歸約階段的整個(gè)分析歷史和對未來進(jìn)行的展望。1.分析棧6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程例如，對文法G[E]:E→E+T

4、TT→T*F

5、FF→(E)

6、id狀態(tài)Sm不僅表征了從分析開始到現(xiàn)在已掃描過的輸入符號被歸約成#E＋T，而且由Sm可以預(yù)測，如果輸入串沒有語法錯(cuò)誤，根據(jù)歸約時(shí)所用規(guī)則（非終結(jié)符T的規(guī)則

7、）推測出未來可能遇到的輸入符號僅是中的任意一個(gè)符號。FOLLOW(T)={+,*,),#}SmTE#···+S0S1分析棧示意圖6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程只有FOLLOW(T)中的符號才會(huì)跟在T后面若當(dāng)前讀到的輸入符號是‘*’，根據(jù)文法可知‘*’的優(yōu)先級高于‘＋’，棧頂尚未形成句柄，則應(yīng)將‘*’移入棧中；若當(dāng)前讀到的輸入符號是‘＋’或’)’或‘#’時(shí)，根據(jù)文法可知棧頂已形成句柄，則應(yīng)將符號串E＋T歸約為E；若當(dāng)前讀到的輸入符號不是上述四種符號之一，則表示輸入串有語法錯(cuò)誤。由此可知，LR分析器的每一步分析工作，

8、都是由棧頂狀態(tài)和現(xiàn)行輸入符號所唯一確定的。6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程LR分析表是LR分析器的核心部分。一張LR分析表由分析動(dòng)作(ACTION)表和狀態(tài)轉(zhuǎn)換(GOTO)表兩部分組成，它們都是二維數(shù)組。狀態(tài)轉(zhuǎn)換表元素GOTO[Si,X]規(guī)定了當(dāng)狀態(tài)Si面臨文法符號X時(shí)，應(yīng)轉(zhuǎn)移到的下一個(gè)狀態(tài)。2.LR分析表6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程見表分析動(dòng)作表元素ACTION[Si,a]規(guī)定了當(dāng)狀態(tài)Si面臨輸入符號a時(shí)應(yīng)執(zhí)行的動(dòng)作。分析動(dòng)作表對應(yīng)四種可能動(dòng)作：移進(jìn)：把狀態(tài)Sj=GOTO[Si,a]和輸入符號a移入分

9、析棧。歸約：當(dāng)棧頂符號串α形成句柄，且文法中有A→α的規(guī)則，其中

10、α

11、=β，則歸約動(dòng)作是從分析棧棧頂去掉β個(gè)文法符號和β個(gè)狀態(tài)，并把歸約符A和GOTO[Si-β，A]=Sj移入分析棧中。6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程見表6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程接受（acc):表示分析成功。此時(shí)，分析棧中只剩文法開始符號S'和當(dāng)前讀到的輸入符號‘#’。即輸入符號串已經(jīng)分析結(jié)束。報(bào)錯(cuò)：表示輸入串含有錯(cuò)誤，此時(shí)出現(xiàn)棧頂?shù)哪骋粻顟B(tài)遇到了不該遇到的輸入符號。見表總控程序也稱為驅(qū)動(dòng)程序。總控程序從左至右掃描輸入符號串，并根據(jù)

12、當(dāng)前分析棧中棧頂狀態(tài)以及當(dāng)前讀到的輸入符號按照LR分析表元素所指示的動(dòng)作完成每一步的分析工作。3.總控程序?qū)λ械腖R分析器其總控程序是相同的。6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程總控程序算法：輸入：輸入串w和LR分析表。輸出：若w是句子，得到w的自下而上分析成功，否則輸出錯(cuò)誤信息。(LR分析器的工作過程的形式化描述)算法：初始化時(shí)，初始狀態(tài)S0在分析棧棧頂，輸入串w#的第1個(gè)符號讀入a中。6.1.1LR分析器的邏輯結(jié)構(gòu)和工作過程{};)(error)]a,[(ERRORSACTIONifelse==)]a,[(rSA

13、CTIONifelsej==)]a,[(SSACTIONifi==)]!a,[(accSACTIONwhile=}aa{i中；將下一個(gè)輸入符號讀入進(jìn)棧；和輸入符號將狀態(tài)}SA],SGOTO[AS′

14、

15、

16、

17、{Aj〞=′→進(jìn)棧；和，將當(dāng)前棧頂狀態(tài)為個(gè)輸入符號退棧；個(gè)狀態(tài)和將歸約：條規(guī)則用第aaa6.1.1