1、6.1 LR分析法、LR分析法是自下而上進(jìn)行規(guī)范歸納的語(yǔ)法分析方法。 其中l(wèi)表示從左到右掃描輸入符號(hào)串。 r是從結(jié)構(gòu)的最右邊導(dǎo)出的逆過(guò)程。 與遞歸下降分析法、預(yù)測(cè)分析法、運(yùn)算符優(yōu)先分析法相比，該分析法對(duì)語(yǔ)法的限制少得多。 6.1 LR分析法可對(duì)許多用無(wú)二義上下文無(wú)關(guān)語(yǔ)法描述的語(yǔ)言用LR分析法進(jìn)行高效分析，而且該分析法分析速度快，能準(zhǔn)確及時(shí)地指出輸入列的語(yǔ)法錯(cuò)誤和錯(cuò)誤位置。 但是，該分析法存在主要缺點(diǎn)，對(duì)于一種語(yǔ)言的語(yǔ)法，構(gòu)建LR分析器的工作量相當(dāng)大，難以具體實(shí)現(xiàn)。 因此，現(xiàn)在對(duì)于實(shí)用的編譯器，使用構(gòu)筑LR分析器的專(zhuān)用工具“YACC”自動(dòng)構(gòu)筑LALR(1)解析器。 本章主要介紹LR分析法的基本思

2、想和LR(0)、SLR(1)、LR(1)、LALR(1)分析器的工作原理和構(gòu)造方法。 6.1 LR分析法、LR分析法的基本思想：LR分析法是規(guī)范歸約分析法。 規(guī)范歸約分析法的關(guān)鍵是在分析過(guò)程中如何確定分析棧的最上面的符號(hào)串是否形成句柄。 6.1.1 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程，LR分析法確定句柄的基本思想在規(guī)范歸約分析過(guò)程中，根據(jù)記錄在分析棧中的移動(dòng)和歸約的符號(hào)串整體(即歷史)和使用的規(guī)則，將來(lái)可能遇到的輸入符號(hào)(即展望) 和根據(jù)現(xiàn)實(shí)讀取的輸入符號(hào)三個(gè)方面的信息確定分析堆棧上的符號(hào)串，6.1.1 LR分析器的邏輯結(jié)構(gòu)和動(dòng)作過(guò)程，LR分析器的邏輯結(jié)構(gòu)，一個(gè)LR分析器的邏輯結(jié)構(gòu)的示意圖如下圖所

3、示。 由分析堆棧、分析表、總控制程序三部分組成。 分析堆棧、輸出、6.1.1 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程、分析堆棧用于存儲(chǔ)分析中的歷史和展望信息。 LR分析法將歷史和展望信息抽象化為狀態(tài)，放置在分析堆棧中，即分析堆棧的各狀態(tài)概括了從分析開(kāi)始到某歸約階段的分析的歷史整體和對(duì)未來(lái)的展望。 1 .分析堆棧，對(duì)此用簡(jiǎn)單的例子進(jìn)行說(shuō)明。 對(duì)于6.1.1 LR分析器的邏輯結(jié)構(gòu)和操作過(guò)程，例如語(yǔ)法GE:EE T| T、TT*F | F、F(E) | id，狀態(tài)Sm不僅表示從分析開(kāi)始到現(xiàn)在掃描的輸入符號(hào)約束，而且表示FOLLOW(T)=、*、#、分析堆棧6.1.1 LR分析器的邏輯結(jié)構(gòu)和操作過(guò)程包括：如果

4、只有FOLLOW(T )中的符號(hào)跟在t之后，并且如果當(dāng)前正在讀取的輸入符號(hào)為*，則當(dāng)前正在讀取的輸入符號(hào)為或#，如果從語(yǔ)法發(fā)現(xiàn)句柄形成在棧的頂部，則將符號(hào)串ET映射到可以看出，堆棧上的狀態(tài)和當(dāng)前輸入符號(hào)唯一決定了LR分析器中每個(gè)步驟的分析工作。 6.1.1 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程，LR分析表是LR分析器的核心部分。 中的組合圖層性質(zhì)變更選項(xiàng)。 LR分析表由“分析操作”(ACTION )表和“狀態(tài)轉(zhuǎn)移”(GOTO )表兩部分組成，它們都是二維數(shù)組。 狀態(tài)轉(zhuǎn)移表元素GOTOSi，x定義了當(dāng)狀態(tài)Si面對(duì)語(yǔ)法符號(hào)x時(shí)將要轉(zhuǎn)移的下一狀態(tài)。 2. LR分析表，6.1.1 LR分析器的邏輯結(jié)構(gòu)和操作

5、過(guò)程，參見(jiàn)表，分析操作表元素ACTIONSi，a規(guī)定了狀態(tài)Si面對(duì)輸入符號(hào)a時(shí)應(yīng)執(zhí)行的操作。 分析操作表對(duì)應(yīng)于四種可能的操作：狀態(tài)Sj=GOTOSi，a和將輸入符號(hào)a移動(dòng)到分析堆棧。 歸約：當(dāng)棧頂符號(hào)串形成句柄，且語(yǔ)法有a規(guī)則時(shí)，其中|=、=歸約動(dòng)作從解析棧頂中刪除語(yǔ)法符號(hào)和狀態(tài)，并將歸約符號(hào)a和GOTOSi-、A=Sj轉(zhuǎn)移到解析棧中。參照6.1.1 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程，參照表，接受6.1.1 LR分析器的邏輯結(jié)構(gòu)和工作過(guò)程，(acc):表示分析成功。 此時(shí)，解析堆棧中殘留的語(yǔ)法開(kāi)始符號(hào)s和當(dāng)前讀取的輸入符號(hào)為#。 即，輸入符號(hào)串結(jié)束。 錯(cuò)誤：表示輸入字符串中包含錯(cuò)誤。 此時(shí)，在堆

6、棧的最上面的狀態(tài)下，檢測(cè)到了不應(yīng)該檢測(cè)的輸入符號(hào)。 參見(jiàn)表，總控制程序也稱(chēng)為驅(qū)動(dòng)程序。 綜合控制程序從左向右掃描輸入符號(hào)串，根據(jù)當(dāng)前分析棧的堆棧狀態(tài)和當(dāng)前讀取的輸入符號(hào)由LR分析表元素指示的操作完成每一步驟的分析工作。 3 .總控制程序?qū)λ蠰R分析器的總控制程序相同。 6.1.1 LR分析器的邏輯結(jié)構(gòu)和操作過(guò)程，總控制程序算法：輸入：輸入字符串w和LR分析表。 輸出：如果w是句子，則w的自下而上分析成功，否則輸出錯(cuò)誤信息。(LR分析器工作過(guò)程的形式化描述)，算法：初始化時(shí)，初始狀態(tài)S0位于分析堆棧的最上方，輸入列w#的第一個(gè)符號(hào)被讀入a。 6.1.1 LR分析器的邏輯結(jié)構(gòu)和動(dòng)作過(guò)程、6.1.

7、1 LR分析器的邏輯結(jié)構(gòu)和動(dòng)作過(guò)程、例1語(yǔ)法g為：對(duì)應(yīng)于語(yǔ)法的LR分析表如下表所示。 0. SS、1. SA、2. SB、3. AaAb、4. Ac、5. BaBb、6. Bd、6.1.1 LR分析器的邏輯結(jié)構(gòu)和操作過(guò)程將繼續(xù)介紹，6.1.1 LR分析器的邏輯結(jié)構(gòu)和操作過(guò)程，6.1.1 LR分析器的邏輯分析是分析的各個(gè)步驟，LR分析器的重要部分是分析表的結(jié)構(gòu)，不需要根據(jù)當(dāng)前堆棧的頂層狀態(tài)積極地看。 構(gòu)建LR分析表的基本思想是：根據(jù)給定的上下文相關(guān)語(yǔ)法構(gòu)建直接識(shí)別語(yǔ)法所有規(guī)范句型前綴的DFA，然后將DFA轉(zhuǎn)換成一張LR分析表。 6.1.2 LR(0)分析法需要定義若干重要概念和術(shù)語(yǔ)，以給出構(gòu)建L

8、R分析表的算法。句法規(guī)范句型的活前綴，1 .字符串前綴指字符串的任意開(kāi)頭。 例如，字符串a(chǎn)bc的前綴是a、ab和abc。 2 .規(guī)范句型活前綴是指規(guī)范句型前綴，該前綴不包含手柄右側(cè)的符號(hào)。 中的組合圖層性質(zhì)變更選項(xiàng)。 請(qǐng)注意，活動(dòng)前綴可以是一個(gè)或多個(gè)規(guī)范語(yǔ)句類(lèi)型的前綴。 6.1.2 LR(0)分析法，6.1.2 LR(0)分析法，從前例，從輸入列aacbb#的歸約過(guò)程，如果分析的輸入列沒(méi)有語(yǔ)法錯(cuò)誤，則在分析的各個(gè)步驟，6.1.2 LR(0)分析法，即LR分析中的任意時(shí)刻，堆中6.1.2 LR(0)分析法，例如對(duì)于前例來(lái)說(shuō)，用于語(yǔ)法GS的規(guī)范語(yǔ)法類(lèi)型aAbb中的句柄將是aab，其中，只有輸入串被

9、掃描的部分將是活動(dòng)前綴，因?yàn)橐坏┰跅５捻敳啃纬闪司湫途浔土⒓幢粴w約它們是aaA、aaAb，單擊時(shí)，句柄的識(shí)別將成為規(guī)范句型的活動(dòng)前綴的識(shí)別。 在6.1.2 LR(0)分析法中，由于用于分析每個(gè)步驟的分析棧中如何標(biāo)識(shí)語(yǔ)法規(guī)范句型的活動(dòng)前綴的所有語(yǔ)法符號(hào)是當(dāng)前規(guī)范句型的活動(dòng)前綴并且與當(dāng)前棧頂狀態(tài)相關(guān)聯(lián)，所以使用窮人機(jī)器人給出的所有語(yǔ)法可以將LR分析器的操作過(guò)程看作是逐步識(shí)別給定語(yǔ)法規(guī)范句型的前綴的過(guò)程。 6.1.2 LR(0)分析法，由此6.1.2 LR(0)分析法，LR(0)項(xiàng)可以從活前綴定義中看出，一個(gè)規(guī)范句型的活前綴中不包括句柄右側(cè)的任何項(xiàng)因此，在活動(dòng)前綴和句柄之間的關(guān)系中，活動(dòng)前綴包含句

10、柄的所有符號(hào)，指示此時(shí)某個(gè)規(guī)則a的右部符號(hào)串已經(jīng)出現(xiàn)在堆棧的頂部，并且與此相應(yīng)的分析操作可以按照此規(guī)則歸約。 在上述例子中，步驟6 :6.1.2 LR(0)分析法、6.1.2 LR(0)分析法、活動(dòng)前綴中僅包含句柄的一部分符號(hào)，這時(shí)形狀為A12規(guī)則的右部的部分列1已經(jīng)出現(xiàn)在堆棧的頂部， 2意味著，在以上描述的期望來(lái)自保留的輸入的例子中步驟5 :不在活動(dòng)前綴中包括手柄的符號(hào)，這意味著，在此情況下，期望符號(hào)串能夠被從保留輸入串推壓到規(guī)則a的右端。 在以上實(shí)例中的步驟3 :6.1.2 LR(0)分析法和6.1.2 LR(0)分析法對(duì)于上述三種情況可以標(biāo)記語(yǔ)法的每一規(guī)則右部的適當(dāng)位置，以便繪出在分析過(guò)

11、程中語(yǔ)法的一個(gè)規(guī)則右部的符號(hào)串的部分識(shí)別。 應(yīng)該注意的是對(duì)于空的規(guī)則a，只有LR(0)項(xiàng)目a。 直觀地說(shuō)，一個(gè)LR(0)項(xiàng)表示對(duì)句法規(guī)范句型活前綴的不同識(shí)別狀態(tài)，而語(yǔ)法g的所有LR(0)項(xiàng)是構(gòu)建對(duì)語(yǔ)法的所有規(guī)范句型活前綴進(jìn)行識(shí)別的DFA的基礎(chǔ)。 可以看出，該DFA的各個(gè)狀態(tài)與貧窮LR(0)項(xiàng)目的集合相關(guān)。 因?yàn)椴煌腖R(0)項(xiàng)反映了分析過(guò)程中堆棧頂部的差異，所以可以根據(jù)點(diǎn)的位置和點(diǎn)的后面是終結(jié)符號(hào)還是非終結(jié)符號(hào)來(lái)對(duì)一個(gè)語(yǔ)法中的所有LR(0)項(xiàng)進(jìn)行分類(lèi)。 6.1.2 LR(0)分析法、6.1.2 LR(0)分析法、LR(0)項(xiàng)目的分類(lèi)如下，轉(zhuǎn)移到A a這樣的項(xiàng)目中。 其中(VNVT)* (點(diǎn)后

12、面有終結(jié)符號(hào)的項(xiàng)目)表示希望從輸入字符串中刪除符號(hào)以形成句柄。6.1.2 LR(0)分析法、要保留的項(xiàng)目、形式如A B，其中(VNVT) *、B VN*，即點(diǎn)后面有非終結(jié)符的項(xiàng)目表示從侑留的輸入串中保留b，希望對(duì)a的右邊進(jìn)行分析其中，s是語(yǔ)法的開(kāi)始符號(hào)，即語(yǔ)法開(kāi)始符號(hào)的歸約項(xiàng)目。 s只有左部的一條規(guī)則，這是歸約項(xiàng)目的特殊情況，表示句子整體已經(jīng)分析完畢，可以接受。6.1.2 LR(0)分析法，構(gòu)建識(shí)別語(yǔ)法的所有規(guī)范句型活動(dòng)前綴DFA的方法：在此項(xiàng)目集中，所有LR(0)項(xiàng)所識(shí)別的活動(dòng)前綴相同，并且能夠使用閉包函數(shù)來(lái)確定DFA的狀態(tài)， 對(duì)于構(gòu)成識(shí)別句法規(guī)范句型活用前綴DFA的各狀態(tài)由多個(gè)LR(0)項(xiàng)

13、組成的集合，稱(chēng)為L(zhǎng)R(0)項(xiàng)集，4.5.2 LR(0)分析法，為了使“接受”項(xiàng)唯一，我們對(duì)語(yǔ)法假設(shè)語(yǔ)法g的開(kāi)始符號(hào)為s，在語(yǔ)法g中引入新的開(kāi)始符號(hào)s (1)定義閉包函數(shù)，將I作為拓寬語(yǔ)法g的一個(gè)LR(0)項(xiàng)目集，定義和結(jié)構(gòu)I的閉包CLOSURE(I )如下：6.1.2 LR(0)分析法，I的任何一個(gè)項(xiàng)目都屬于cllosure，(b)ab屬于CLOSURE(I )， 重復(fù)(b )直到CLOSURE(I )變大為止。6.1.2 LR(0)分析法，例如對(duì)于例1中的語(yǔ)法，定義了6.1.2 LR(0)分析法，(2)狀態(tài)轉(zhuǎn)移函數(shù)GO，其中I是初始狀態(tài)的項(xiàng)集I0、CLOSURE(I )、SS、以及定義x )

14、的s )、=、關(guān)閉(SS )、=、SS、=、I1、GO(I0，a )、=、關(guān)閉(BaBb，BaBb )、=。 I0=，6.1.2 LR(0)分析法能夠容易地構(gòu)建根據(jù)閉包函數(shù)(CLOSURE )和狀態(tài)轉(zhuǎn)移函數(shù)(GO )來(lái)識(shí)別語(yǔ)法g的句法規(guī)范文型活用前綴的DFA。 建立識(shí)別6.1.2 LR(0)分析法、(3)句法規(guī)范文型活用前綴DFA的方法：求出(CLOSURESS )，得到初始狀態(tài)項(xiàng)目集。 (b )對(duì)初始狀態(tài)項(xiàng)目集或者其他已構(gòu)筑的項(xiàng)目集，應(yīng)用狀態(tài)遷移函數(shù)GO(I，x )而求出新的項(xiàng)目集(后續(xù)狀態(tài))。 6.1.2 LR(0)分析法、(d )轉(zhuǎn)移函數(shù)GO建立狀態(tài)間的連接關(guān)系。對(duì)于前例的語(yǔ)法，構(gòu)成識(shí)別語(yǔ)法的所有規(guī)范句型活前綴的DFA，如下圖所示，(c )重復(fù)(b )直到新的項(xiàng)目集(新的狀態(tài))不再出現(xiàn)為止。 當(dāng)狀態(tài)I1中的6.1.2 LR(0)分析法、識(shí)別語(yǔ)法g活動(dòng)前綴的DFA、6.1.2 LR(0)分析法、識(shí)別語(yǔ)法g活動(dòng)前綴的DFA、6.1.2 LR(0)分析法、m時(shí)，m所識(shí)別的前綴是s，并且輸入串是成功的6.1.2 LR(0)分析法構(gòu)成LR(0)項(xiàng)集規(guī)范族，該LR(0)項(xiàng)