編譯原理課件

1、編 譯 原 理 LR分分析析編 譯 原 理 LR分分析析本章知識點本章知識點(內(nèi)容內(nèi)容)LR分析概述分析概述LR（0）分析）分析SLR（1）分析）分析LR（1）分析）分析LALR（1）分析）分析二義文法在二義文法在LRLR分析中的應用分析中的應用編 譯 原 理 LR分分析析算符優(yōu)先分析法存在的問題算符優(yōu)先分析法存在的問題 強調(diào)算符之間的優(yōu)先關系的唯一性，這使得它的強調(diào)算符之間的優(yōu)先關系的唯一性，這使得它的適應面比較窄；算法在發(fā)現(xiàn)最左素短語的尾時，需要適應面比較窄；算法在發(fā)現(xiàn)最左素短語的尾時，需要返回來尋找對應的最左素短語頭。返回來尋找對應的最左素短語頭。LR分析法：分析法：1 對文法限制少；對

2、文法限制少；2 適用范圍廣；適用范圍廣；3 分析速度快；分析速度快； 4報錯準確。報錯準確。5 易于實現(xiàn)自動生成。由于構造分析器的工作量很大，易于實現(xiàn)自動生成。由于構造分析器的工作量很大，不大可能手工構造；如用軟件工具不大可能手工構造；如用軟件工具Yacc-Yet Another Compiler Compiler,Bell，這些軟件工具叫，這些軟件工具叫LR生成器生成器。 首頁首頁結束結束編 譯 原 理 LR分分析析一、一、LR(k)LR(k)分析法分析法 L L ：從左到右掃描輸入符號，：從左到右掃描輸入符號， R R ：最右推導對應的最左歸約：最右推導對應的最左歸約, , k k ：超前

3、讀入：超前讀入k k個符號，用以確定歸約所用的規(guī)則個符號，用以確定歸約所用的規(guī)則。LR分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)其中分析法在自左至右掃描輸入串時就能發(fā)現(xiàn)其中的任何錯誤并能準確地指出出錯地點。的任何錯誤并能準確地指出出錯地點。 大多數(shù)用上下文無關文法描述的程序語言都可用大多數(shù)用上下文無關文法描述的程序語言都可用LR分析器予以識別。分析器予以識別。主要缺點是，用手工構造分析程序則工作量相當主要缺點是，用手工構造分析程序則工作量相當大。因此，必須求助于自動產(chǎn)生這種分析程序的產(chǎn)大。因此，必須求助于自動產(chǎn)生這種分析程序的產(chǎn)生器。生器。 編 譯 原 理 LR分分析析二、二、LRLR分析法分類：分

4、析法分類：LR(0)表構造法。這種方法的局限性極大、但它是建立表構造法。這種方法的局限性極大、但它是建立其它較一般的其它較一般的LR分析法的基礎。分析法的基礎。SIR表構造法。雖然，有一些文法構造不出表構造法。雖然，有一些文法構造不出SLR分析表，分析表，但是，這是一種比較容易實現(xiàn)又極有使用價值的方法。但是，這是一種比較容易實現(xiàn)又極有使用價值的方法。規(guī)范規(guī)范LR表構造法。這種分析表能力最強，能夠適用一大表構造法。這種分析表能力最強，能夠適用一大類文法，但實現(xiàn)代價過高，或者說，分析表的體積非常大。類文法，但實現(xiàn)代價過高，或者說，分析表的體積非常大。向前向前LR表構造法（簡稱表構造法（簡稱LAIR

5、）。這種分析表的能力介）。這種分析表的能力介于于SIR和規(guī)范和規(guī)范LR之間，稍加努力，就可以高效地實現(xiàn)。之間，稍加努力，就可以高效地實現(xiàn)。 首頁首頁結束結束編 譯 原 理 LR分分析析規(guī)范歸約（最左歸約一最右推導的逆過程）的關鍵規(guī)范歸約（最左歸約一最右推導的逆過程）的關鍵問題是尋找句柄。問題是尋找句柄。 LR方法的基本思想是方法的基本思想是:在規(guī)范歸約的過程中，一方在規(guī)范歸約的過程中，一方面要記住已移進和歸約出的整個字符串，也就是說面要記住已移進和歸約出的整個字符串，也就是說要記住歷史；一方面能夠根據(jù)所用的產(chǎn)生式的推測要記住歷史；一方面能夠根據(jù)所用的產(chǎn)生式的推測未來可能碰到的輸入符號，也就是說

6、能夠對未來進未來可能碰到的輸入符號，也就是說能夠對未來進行展望。這樣，當一串貌似句柄的字符串出現(xiàn)在分行展望。這樣，當一串貌似句柄的字符串出現(xiàn)在分析棧的頂部時，我們希望能夠根據(jù)歷史和展望以及析棧的頂部時，我們希望能夠根據(jù)歷史和展望以及現(xiàn)實的輸入符號這三部分的材料，決定出現(xiàn)在棧頂現(xiàn)實的輸入符號這三部分的材料，決定出現(xiàn)在棧頂?shù)倪@一串符號是否就是我們要找的的這一串符號是否就是我們要找的句柄。句柄。 首頁首頁結束結束編 譯 原 理 LR分分析析三、三、LR分析器的邏輯結構分析器的邏輯結構 一個一個LR分析器包括兩部分：一個總控分析器包括兩部分：一個總控(驅動驅動)程序和一張分析表。注意：所有程序和一張分

7、析表。注意：所有LR分析器的總分析器的總控程序都是一樣的，只是分析表各有不同。因此控程序都是一樣的，只是分析表各有不同。因此產(chǎn)生器的主要任務就是產(chǎn)生分析表。產(chǎn)生器的主要任務就是產(chǎn)生分析表。LRLR分析器的分析器的核心部分是一張分析表。核心部分是一張分析表。采用下推自動機這種數(shù)據(jù)模型。包括以下幾個部采用下推自動機這種數(shù)據(jù)模型。包括以下幾個部分：分： 1.輸入帶。輸入帶。 2.分析棧：包括狀態(tài)棧和文法符號棧兩部分。分析棧：包括狀態(tài)棧和文法符號棧兩部分。 3.LR 分析表：包括動作表和狀態(tài)轉移表兩張表。分析表：包括動作表和狀態(tài)轉移表兩張表。首頁首頁結束結束編 譯 原 理 LR分分析析a1 ai an

8、 #動作表動作表 action轉移表轉移表 goto狀態(tài)棧狀態(tài)棧 符號棧符號棧輸入緩沖區(qū)輸入緩沖區(qū)分析表分析表SmSm-1S1S0XmXm-1X1#首頁首頁結束結束編 譯 原 理 LR分分析析分析表包括兩部分：分析表包括兩部分：一部分是（一部分是（ACTION)表，另一部分是表，另一部分是狀態(tài)轉狀態(tài)轉換換(GOTO)表。它們都是二維數(shù)組。表。它們都是二維數(shù)組。ACTIONS，a中規(guī)定了當狀態(tài)中規(guī)定了當狀態(tài)S面臨輸入符號面臨輸入符號a時應采取什么動作。時應采取什么動作。GOTOS，X規(guī)定了狀態(tài)規(guī)定了狀態(tài)S面對文法符號面對文法符號X(終結終結符或非終結符符或非終結符)時下一狀態(tài)是什么。時下一狀態(tài)是

9、什么。顯然，顯然，GOTOS，X定義了一個以文法符號為定義了一個以文法符號為字母表的字母表的DFA。 【例】演示【例】演示首頁首頁結束結束編 譯 原 理 LR分分析析每一項每一項ACTIONSACTIONS，aJaJ所規(guī)定的動作是下述所規(guī)定的動作是下述4 4種可能之種可能之-： (1)(1)移進移進：把：把(S(S，a)a)的下一狀態(tài)的下一狀態(tài)S =ACTIONSS =ACTIONS，aa和輸和輸入符號入符號a a推進棧（對終結符，推進棧（對終結符，GOTOSGOTOS，aa的值已放入的值已放入ACTIONSACTIONS，aa中中) )，下一個，下一個輸入符號變成現(xiàn)行輸入符號。輸入符號變成現(xiàn)

10、行輸入符號。 (2)(2)歸約：歸約：指用某一產(chǎn)生式指用某一產(chǎn)生式A A 進行歸約。假若進行歸約。假若 的長的長度為度為 ，歸約的動作是去掉棧頂?shù)?，歸約的動作是去掉棧頂?shù)?個項，然后把個項，然后把(Sm(Sm- - ，A)A)的下一狀態(tài)和文法符號的下一狀態(tài)和文法符號A A推進棧。歸約動作不改變現(xiàn)行推進棧。歸約動作不改變現(xiàn)行輸入符號。執(zhí)行歸約的動作意味著呈現(xiàn)于棧頂?shù)姆柎禽斎敕?。?zhí)行歸約的動作意味著呈現(xiàn)于棧頂?shù)姆柎且粋€相對于一個相對于A A的句柄。的句柄。 (3)(3)接受：接受：宣布分析成功，停止分析器的工作。宣布分析成功，停止分析器的工作。 (4)(4)報錯報錯：報告發(fā)現(xiàn)源程序含有錯

11、誤，調(diào)用出錯處理程：報告發(fā)現(xiàn)源程序含有錯誤，調(diào)用出錯處理程序。序。首頁首頁結束結束編 譯 原 理 LR分分析析 對于對于-個文法，如果能構造一張分析表，使得它的每個個文法，如果能構造一張分析表，使得它的每個入口均是唯一確定的，則把這個文法稱為入口均是唯一確定的，則把這個文法稱為LR文法。對于文法。對于一個一個LR文法，當分析器對輸入串進行自左至右掃描時，文法，當分析器對輸入串進行自左至右掃描時，一旦句柄呈現(xiàn)于棧頂，就能及時對它實行歸約。一旦句柄呈現(xiàn)于棧頂，就能及時對它實行歸約。 一個一個LR分析器有時需要分析器有時需要“展望展望”和實際檢查未來和實際檢查未來的的k個輸入符號才能決定應采取什么樣

12、的個輸入符號才能決定應采取什么樣的“移進一歸約移進一歸約”決策。一般而言，決策。一般而言， 一個文法如果能用一個每步頂多向前一個文法如果能用一個每步頂多向前檢查檢查K個輸入符號的個輸入符號的LR分析器進行分析，則這個文法就分析器進行分析，則這個文法就稱為稱為LR(k)文法。文法。 對于一個文法，如果它的任何對于一個文法，如果它的任何移進一歸約移進一歸約分析器都分析器都存在盡管棧的內(nèi)容和符號都已了解，但存在盡管棧的內(nèi)容和符號都已了解，但無法確定是無法確定是“移移進進”還是還是“歸約歸約”；或者，無法從幾種可能的規(guī)約中確或者，無法從幾種可能的規(guī)約中確定其一的情形，那么這個文法就是非定其一的情形，那

13、么這個文法就是非LR(1)的。的。 首頁首頁結束結束編 譯 原 理 LR分分析析【例【例】已知文法已知文法GS，分析符號串，分析符號串a(chǎn)bbcde是否是是否是GS的句子的句子 。 (1) S aAcBe1 (2) A b2 (3) A Ab3 (4) B d4【解【解】這里每個產(chǎn)生式的右部字符串末尾的編號是為了這里每個產(chǎn)生式的右部字符串末尾的編號是為了方便查看在最右推導中是選擇哪個產(chǎn)生式推導的，并不是方便查看在最右推導中是選擇哪個產(chǎn)生式推導的，并不是產(chǎn)生式的一部分。產(chǎn)生式的一部分。 句子的最右推導過程為：句子的最右推導過程為： S =aAcBe1 =aAcd4e1=aAb3cd4e1=ab2b

14、3cd4e1首頁首頁結束結束編 譯 原 理 LR分分析析 由于最右推導就是規(guī)范推導，因此句型由于最右推導就是規(guī)范推導，因此句型aAcBe、aAcde、aAbcde、abbcde為規(guī)范句型。為規(guī)范句型。 規(guī)范句型的規(guī)范句型的這種前部分符號串稱為可歸前綴這種前部分符號串稱為可歸前綴?！纠纭纠纭糠柎柎產(chǎn)AcBe是規(guī)范句型是規(guī)范句型aAcBe的可歸前綴，的可歸前綴，aAcd是規(guī)范句型是規(guī)范句型aAcd4e1的可歸前綴，的可歸前綴，aAb是規(guī)范句型是規(guī)范句型aAb3cd4e1的可歸前綴，的可歸前綴，ab是規(guī)范句型是規(guī)范句型ab2b3cd4e1的可歸前綴。的可歸前綴。 我們把形成可歸前綴之前包括

15、可歸前綴在內(nèi)的我們把形成可歸前綴之前包括可歸前綴在內(nèi)的所有規(guī)范句型的前綴都稱為所有規(guī)范句型的前綴都稱為活前綴?；钋熬Y。所謂前綴所謂前綴就就是是符號串的任意首部。活前綴符號串的任意首部。活前綴就是就是可歸前綴可歸前綴的任意首部的任意首部。首頁首頁結束結束編 譯 原 理 LR分分析析【例如【例如】可歸前綴可歸前綴ab的活前綴為的活前綴為,a,ab可歸前綴可歸前綴aAb的活前綴為的活前綴為,a,aA,aAb可歸前綴可歸前綴aAcd的活前綴為的活前綴為,a,aA,aAc,aAcd可歸前綴可歸前綴aAcBe的活前綴為的活前綴為,a,aA,aAc,aAcB,aAcBe首頁首頁結束結束編 譯 原 理 LR分

16、分析析 因為規(guī)范歸約實際上就是規(guī)范推導的逆過程。因為規(guī)范歸約實際上就是規(guī)范推導的逆過程?？蓺w前綴就是存放在文法符號棧中的內(nèi)容可歸前綴就是存放在文法符號棧中的內(nèi)容，它和它和輸入緩沖器的剩余內(nèi)容合在一起如果剛好就是規(guī)輸入緩沖器的剩余內(nèi)容合在一起如果剛好就是規(guī)范句型，就能夠保證我們的歸約是一個規(guī)范歸約范句型，就能夠保證我們的歸約是一個規(guī)范歸約的過程。的過程。即棧內(nèi)符號串總是規(guī)范句型的前綴即棧內(nèi)符號串總是規(guī)范句型的前綴,且且不含句柄右側的符號。原因不含句柄右側的符號。原因:句柄一旦在棧頂形句柄一旦在棧頂形成成,就不再移進新符號就不再移進新符號,而是要進行歸約了。而是要進行歸約了。我們把具有上述性質的符

17、號串稱為規(guī)范句型的活我們把具有上述性質的符號串稱為規(guī)范句型的活前綴。前綴。 為什么要引進活前綴的概念？為什么要引進活前綴的概念？ 首頁首頁結束結束編 譯 原 理 LR分分析析一、活前綴和可歸前綴的形式定義一、活前綴和可歸前綴的形式定義 若若S A ,則稱則稱為可歸前綴為可歸前綴; 若有串若有串W是是的前綴，則稱的前綴，則稱W是是G的一個活前綴（的一個活前綴（S為文法拓廣后的為文法拓廣后的開始符，它只出現(xiàn)在規(guī)則左部）。可歸前綴是包含句柄的開始符，它只出現(xiàn)在規(guī)則左部）?？蓺w前綴是包含句柄的活前綴?；钋熬Y。 二、說明：二、說明： 規(guī)范句型的活前綴有兩個要點規(guī)范句型的活前綴有兩個要點:(1)它是規(guī)范句

18、型的前綴它是規(guī)范句型的前綴; (2)它不含句柄右側符號它不含句柄右側符號編 譯 原 理 LR分分析析 由于活前綴實際上就是滿足一定要求的符號由于活前綴實際上就是滿足一定要求的符號串，因此識別活前綴的工作和識別單詞的工作非串，因此識別活前綴的工作和識別單詞的工作非常類似，所以我們可以采用常類似，所以我們可以采用有窮自動機有窮自動機這種數(shù)這種數(shù)據(jù)模型來實現(xiàn)活前綴的識別。據(jù)模型來實現(xiàn)活前綴的識別。 如何識別文法符號棧中的內(nèi)容就是活前綴如何識別文法符號棧中的內(nèi)容就是活前綴 首頁首頁結束結束編 譯 原 理 LR分分析析 基本思想基本思想是我們可以把文法的終結符和非是我們可以把文法的終結符和非終結符都看成

19、有窮自動機的輸入符號，每次把一終結符都看成有窮自動機的輸入符號，每次把一個符號進?？闯梢炎R別過了該符號，同時狀態(tài)進個符號進?？闯梢炎R別過了該符號，同時狀態(tài)進行轉換，當識別到可歸前綴時，相當于在棧中形行轉換，當識別到可歸前綴時，相當于在棧中形成句柄，達到了識別句柄的終態(tài)。成句柄，達到了識別句柄的終態(tài)。首頁首頁結束結束編 譯 原 理 LR分分析析實現(xiàn)識別活前綴的有窮自動機的構造有兩種實現(xiàn)識別活前綴的有窮自動機的構造有兩種方法：方法：方法方法1： 由文法的產(chǎn)生式直接構造識別活前綴和可歸前由文法的產(chǎn)生式直接構造識別活前綴和可歸前綴的有窮自動機綴的有窮自動機 方法方法2： 通過構造文法通過構造文法G的的

20、LR(0)的項目集規(guī)范族來直的項目集規(guī)范族來直接構造識別活前綴的接構造識別活前綴的DFA 【說明】由于【說明】由于NFA確定化為確定化為DFA的工作量較大，我的工作量較大，我們考慮直接構造出項目集規(guī)范族作為們考慮直接構造出項目集規(guī)范族作為DFA的狀態(tài)，的狀態(tài)，來構造來構造DFA。 首頁首頁結束結束編 譯 原 理 LR分分析析LR(0)項目集規(guī)范族的構造項目集規(guī)范族的構造 定義：構成識別一個文法活前綴的定義：構成識別一個文法活前綴的DFA項目集項目集（狀態(tài)）的全體，稱為這個文法的（狀態(tài)）的全體，稱為這個文法的LR(0)項目集項目集規(guī)范族。規(guī)范族。 ( (一一) LR) LR（0 0）項目）項目在

21、每個產(chǎn)生式的右部適當位置添加一個圓點構成在每個產(chǎn)生式的右部適當位置添加一個圓點構成項目（項目（item）。每個項目的含義和圓點的位置有）。每個項目的含義和圓點的位置有關。項目圓點的左部表示分析過程的某個時刻用關。項目圓點的左部表示分析過程的某個時刻用該產(chǎn)生式歸約時句柄已識別的部分，圓點右部表該產(chǎn)生式歸約時句柄已識別的部分，圓點右部表示待識別的部分。示待識別的部分。首頁首頁結束結束編 譯 原 理 LR分分析析根據(jù)圓點所在的位置和圓點后是終結符還是非終根據(jù)圓點所在的位置和圓點后是終結符還是非終結符把項目分為以下幾種：結符把項目分為以下幾種： 1、移進項目，形如、移進項目，形如 A a . ab 2

22、、待約項目，形如、待約項目，形如 A a . Bb 3、歸約項目，形如、歸約項目，形如 A a . 4、接受項目，形如、接受項目，形如 SS .首頁首頁結束結束編 譯 原 理 LR分分析析【例】產(chǎn)生式【例】產(chǎn)生式S SaAcBe對應的對應的6個項目是：個項目是：0S S.aAcBe1S Sa.AcBe 2S SaA.cBe3S SaAc.Be4S SaAcB.e5S SaAcBe. 首頁首頁結束結束編 譯 原 理 LR分分析析一個產(chǎn)生式可對應的項目為它的右部符號長度加一個產(chǎn)生式可對應的項目為它的右部符號長度加1，對空產(chǎn)生式，對空產(chǎn)生式 A- 僅有一個項目僅有一個項目 A-.【例】產(chǎn)生式【例】產(chǎn)

23、生式A-X YZ 對應對應4個項目個項目 A-.XY Z A-XY Z A-X YZ A-X YZ編 譯 原 理 LR分分析析（二）（二）LR(0)LR(0)項目集規(guī)范族的構造項目集規(guī)范族的構造對于構成識別一個文法活前綴的對于構成識別一個文法活前綴的DFA項目集的全體項目集的全體稱為這個文法的稱為這個文法的LR（0）項目集規(guī)范族）項目集規(guī)范族 （1）首先，為了使）首先，為了使接受接受狀態(tài)易于識別，總是狀態(tài)易于識別，總是將文法將文法G進行拓廣。假定文法進行拓廣。假定文法G是一個以是一個以S為開始符為開始符號的文法，我們構造一個號的文法，我們構造一個G，它包含了整個，它包含了整個G并引并引進了一個

24、不出現(xiàn)在進了一個不出現(xiàn)在G中的非終結符中的非終結符S；同時加進了；同時加進了一個新產(chǎn)生式一個新產(chǎn)生式S一一S，而這個，而這個S是是G的開始符號，的開始符號，稱稱G是是G的拓廣文法。會有一個僅含項目的拓廣文法。會有一個僅含項目S-S的的狀態(tài)，這就是唯一狀態(tài)，這就是唯一的的接受接受態(tài)。態(tài)。 編 譯 原 理 LR分分析析如果如果I是文法是文法G的一個項目集，定義和構造的一個項目集，定義和構造I的閉包的閉包CLOSURE(I)如下：如下： a)I的項目都在的項目都在CLOSURE(I)中中 b)若若Aa . Bb屬于屬于CLOSURE(I)，則每一，則每一形如形如B. g的項目也屬于的項目也屬于CLO

25、SURE(I) c)重復重復b)直到直到CLOSURE(I)不再擴大。不再擴大?！菊f明【說明】求閉包函數(shù)的過程實際上就是求求閉包函數(shù)的過程實際上就是求所有等價狀態(tài)的過程。所有等價狀態(tài)的過程。（2）閉包函數(shù)）閉包函數(shù)CLOSURE(I)編 譯 原 理 LR分分析析（3）轉換函數(shù)）轉換函數(shù)GOTO（I，X) 定義轉換函數(shù)如下：定義轉換函數(shù)如下： GOTO（I，X）= CLOSURE（J） 其中：其中：I為包含某一項目集的狀態(tài)，為包含某一項目集的狀態(tài)，X為一文法符為一文法符號號 J=任何形如任何形如AaX . b的項目的項目| Aa . X b屬于屬于I 定義兩個函數(shù)后，就可以通過定義兩個函數(shù)后，就

26、可以通過閉包函數(shù)閉包函數(shù)CLOSURE求求DFA一個狀態(tài)的項目集，通過轉換函一個狀態(tài)的項目集，通過轉換函數(shù)求數(shù)求DFA一個狀態(tài)的項目集一個狀態(tài)的項目集 【例【例】A-a.XbA-aX.bX首頁首頁結束結束編 譯 原 理 LR分分析析構造文法構造文法G的的LR(0) 項目集規(guī)范族的方法項目集規(guī)范族的方法 :把文法的所有產(chǎn)生式的項目都引出，每個項目都把文法的所有產(chǎn)生式的項目都引出，每個項目都為為NFA的一個狀態(tài)。其中文法的第一個產(chǎn)生式的的一個狀態(tài)。其中文法的第一個產(chǎn)生式的第一個項目第一個項目S . S為文法的初態(tài)集的核心項。為文法的初態(tài)集的核心項。 a)置項目置項目S . S為初態(tài)集的核心項后，對

27、核心為初態(tài)集的核心項后，對核心項求閉包項求閉包CLOSURE（S . S）得到初態(tài)的項目）得到初態(tài)的項目集集 b)對初態(tài)集或其它所構造的項目集應用轉換函對初態(tài)集或其它所構造的項目集應用轉換函數(shù)數(shù)GOTO(I，X)= CLOSURE(J)求出新狀態(tài)求出新狀態(tài)J的項的項目集目集 c)重復重復b)直到不出現(xiàn)新的項目集為止直到不出現(xiàn)新的項目集為止首頁首頁結束結束編 譯 原 理 LR分分析析【例】文法【例】文法GS: 0SEE1EaA1EaA2EbB2EbB3AcA3AcA4Ad4Ad5BcB5BcB6Bd 6Bd 其規(guī)范項目集族構造如其規(guī)范項目集族構造如下：下：首頁首頁結束結束編 譯 原 理 LR分分

28、析析編 譯 原 理 LR分分析析 假定假定C=I。，。，I1，In)。由于我們已。由于我們已經(jīng)習慣用數(shù)字表示狀態(tài)，因此令每個項目經(jīng)習慣用數(shù)字表示狀態(tài)，因此令每個項目集集Ik的下標的下標k作為分析器的狀態(tài)。特別是作為分析器的狀態(tài)。特別是令包含項目令包含項目SS(表示整個句子還未輸表示整個句子還未輸入入)的集合的集合Ik的下標的下標k為分析器的初態(tài)。為分析器的初態(tài)。 LR(0)分析表的構造分析表的構造編 譯 原 理 LR分分析析分析表的分析表的ACTION子表和子表和GOTO子表可按如下方子表可按如下方法構造：法構造： (1)若項目若項目A- a 屬于屬于Ik 且且GO(Ik,a)= Ij ，a為

29、終結符，置為終結符，置ACTIONk,a 為將為將(j，a)移進棧移進棧”，簡記為簡記為“Sj (2)若項目若項目A-. 屬于屬于Ik，則對任何終結符，則對任何終結符a(或或結束符結束符#)，置，置ACTIONk,a 為用產(chǎn)生式為用產(chǎn)生式A-a進行進行歸約，簡記為歸約，簡記為“rj”(注意：注意：j是產(chǎn)生式的編號而不是產(chǎn)生式的編號而不是項目集的狀態(tài)號，即是項目集的狀態(tài)號，即A-a是文法是文法G的第的第j個產(chǎn)生個產(chǎn)生式式)。編 譯 原 理 LR分分析析 （3）若項目）若項目S-S 屬于屬于Ik (S 表示整個句子已表示整個句子已輸入并歸約結束輸入并歸約結束)，則置，則置ACTIONK，#為可為可

30、“接接受受”，簡記為，簡記為“acc”。 (4)若若GO(Ik ,A)=Ij , A為非終結符，則置為非終結符，則置GOTOk，A=j。 (5)分析表中凡不能用規(guī)則分析表中凡不能用規(guī)則(1)一一(4)填入的空白填入的空白格均置上格均置上“報錯標志報錯標志”。首頁首頁結束結束編 譯 原 理 LR分分析析首頁首頁結束結束編 譯 原 理 LR分分析析1 1、置輸入指針、置輸入指針 ipip 指向輸入串的第一個符號；指向輸入串的第一個符號；令令 s s 是棧是棧頂狀態(tài)，頂狀態(tài)， a a 是是 ipip 所指向的符號所指向的符號; ;將將# #壓入符號棧，將開始狀態(tài)壓入符號棧，將開始狀態(tài)0 0壓入狀態(tài)棧

31、；壓入狀態(tài)棧； 2 2、重復執(zhí)行如下過程：、重復執(zhí)行如下過程： ifif（actions,a=sjactions,a=sj） 把符號把符號a a入符號棧，把狀態(tài)入符號棧，把狀態(tài)j j入狀態(tài)棧；入狀態(tài)棧； 使使 ipip 指向下一個輸入符號。指向下一個輸入符號。 else if else if （actions,a=rjactions,a=rj）首頁首頁結束結束編 譯 原 理 LR分分析析 從棧頂彈出第從棧頂彈出第j j條規(guī)則右部串長條規(guī)則右部串長|個符個符號；號； 把歸約得到的非終結符把歸約得到的非終結符A A壓入符號棧；壓入符號棧； 將將gotos,Agotos,A 的值的值j j壓入狀態(tài)棧

32、；壓入狀態(tài)棧； 并輸出規(guī)則并輸出規(guī)則 AA。 else if else if （actions,a=accactions,a=acc） returnreturn； else else error() error()； 首頁首頁結束結束編 譯 原 理 LR分分析析【例】文法【例】文法GS: 0SE1EaA2EbB3AcA4Ad5BcB6Bd,對輸入串對輸入串bccdbccd# #分析如下：分析如下：首頁首頁結束結束編 譯 原 理 LR分分析析步驟步驟狀態(tài)棧狀態(tài)棧符號棧符號棧輸入串輸入串a(chǎn)ctionGoto1 0#bccd#S32 03#bccd#S53 035#bccd#S54 0355#bcc

33、d#S115 0355(11)#bccd#r696 03559#bccB#r597 0359#bcB#r578 037#bB#r219 01#E#acc首頁首頁結束結束編 譯 原 理 LR分分析析 1、如果、如果 I 中至少含兩個歸約項目，則稱中至少含兩個歸約項目，則稱 I 有有歸約歸約歸約沖突歸約沖突（Reduce/Reduce Conflict） 2、如果、如果 I 中既含歸約項目，又含移進項目，則稱中既含歸約項目，又含移進項目，則稱 I 有有移進移進歸約沖突歸約沖突（Shift/Reduce Conflict） 3、如果、如果 I 既沒有歸約既沒有歸約歸約沖突，又沒有移歸約沖突，又沒有移

34、進進歸約沖突，則稱歸約沖突，則稱 I 是相容的是相容的(Consistent)，否，否則稱則稱 I 是不相容的。是不相容的。 4、對文法、對文法G，如果，如果 IC,都是相容的，則稱都是相容的，則稱G為為LR(0)文法。文法。編 譯 原 理 LR分分析析【例】有產(chǎn)生式如下【例】有產(chǎn)生式如下 SBB BaB|b構造該文法的構造該文法的LR(0)分析表分析表 將文法將文法G拓廣為文法拓廣為文法G 0)S一一S 1)SBB 2)BaB 3)Bb 列出列出LR(0)的所有項目的所有項目 1、SS 5、SBB 9、B-.b 2、S一一S. 6、 BaB 10、B-b. 3、S一一.BB 7、BaB 4、

35、SBB 8、BaB.編 譯 原 理 LR分分析析用用e_CLOSURE辦法構造文法辦法構造文法G的的LR(0)項目集規(guī)范族項目集規(guī)范族 I0: S-.S S-.BB B-.aB B-.b I1: S-S. I2：SBB B一一.aB B.b I3: B-a.B B-.aB B-.b I4: B-b. I5: S-BB. I6: B-aB.編 譯 原 理 LR分分析析 狀態(tài)狀態(tài) ACTlONACTlON GOTO GOTO a b # S B a b # S B 0 s3 S4 1 2 0 s3 S4 1 2 1 aCC 1 aCC 2 s3 S4 5 2 s3 S4 5 3 S3 s4 6 3

36、 S3 s4 6 4 r3 r3 r3 4 r3 r3 r3 5 r1 r1 rl 5 r1 r1 rl 6 r2 r2 r2 6 r2 r2 r2 LR(0)分析表分析表編 譯 原 理 LR分分析析【練習】設有文法【練習】設有文法GS： S-E E-Aa |bB A-cA |d B-cB |d 構造構造LR(0)分析表，并利用此分析表判斷符號串分析表，并利用此分析表判斷符號串a(chǎn)cccd是否是文法是否是文法GS的句子。的句子。編 譯 原 理 LR分分析析 LR(0)文法是一類非常簡單的文法，沒有文法是一類非常簡單的文法，沒有查看下一符號查看下一符號(Token),決定分析動作僅僅根據(jù)決定分析動

37、作僅僅根據(jù)到目前已經(jīng)看到的東西，分析能力弱。即使到目前已經(jīng)看到的東西，分析能力弱。即使是定義算術表達式這樣的簡單文法也不是是定義算術表達式這樣的簡單文法也不是LR(0)。改進辦法改進辦法:向前查看下一符號向前查看下一符號-SLR(1),LR(1),LALR(1)7.3 SLR(1)7.3 SLR(1)分析分析首頁首頁結束結束編 譯 原 理 LR分分析析一、一、LR(0)LR(0)分析存在的問題分析存在的問題 【例】已知文法【例】已知文法G,開始符號為開始符號為S,判斷該文法是判斷該文法是否為否為LR(0) 文法。文法。 (0) S S (1) S rD (2) DD,i (3) D i單擊演示

38、單擊演示首頁首頁結束結束編 譯 原 理 LR分分析析這里僅僅憑這里僅僅憑LR(0) LR(0) 項目本身的信息已經(jīng)無法項目本身的信息已經(jīng)無法解決項目之間的沖突，需要向前查看一個解決項目之間的沖突，需要向前查看一個符號，再來決定到底是采取移進動作還是符號，再來決定到底是采取移進動作還是歸約動作。歸約動作。首頁首頁結束結束編 譯 原 理 LR分分析析 二、解決方法二、解決方法對含有移進對含有移進-歸約和歸約歸約和歸約-歸約沖突的項目集歸約沖突的項目集I=Xa.bb , Ag. ,Bd. 若有：若有：FOLLOW(A) FOLLOW(B) = FOLLOW(A) b = FOLLOW(B) b =

39、狀態(tài)狀態(tài)I面臨某輸入符號面臨某輸入符號a 1) 若若a=b，則移進，則移進 2) 若若aFOLLOW(A), 則用產(chǎn)生式則用產(chǎn)生式 A g 進行歸約進行歸約 3) 若若aFOLLOW(B), 則用產(chǎn)生式則用產(chǎn)生式 B d 進行歸約進行歸約 4) 此外，報錯此外，報錯 首頁首頁結束結束編 譯 原 理 LR分分析析若一個文法的若一個文法的LR(0)LR(0)分析表中所含有的分析表中所含有的動作沖突都能用上述方法解決，則稱動作沖突都能用上述方法解決，則稱這個文法是這個文法是SLR(1)SLR(1)文法。文法。SLR(1)SLR(1)文法文法是無二義的。是無二義的。編 譯 原 理 LR分分析析 對任給

40、的一個文法對任給的一個文法G，我們可用如下的，我們可用如下的辦法構造它的辦法構造它的SLR(1)分析表：分析表：首先把首先把G拓廣為拓廣為G，對，對G構造構造LR(0)項目集項目集規(guī)范族和活前綴識別自動機的狀態(tài)轉換函數(shù)規(guī)范族和活前綴識別自動機的狀態(tài)轉換函數(shù)GO，使用閉包函數(shù)和函，使用閉包函數(shù)和函數(shù)，然后再按下面的算法構造數(shù)，然后再按下面的算法構造G的的SLR分析分析表。表。SLR(1)SLR(1)分析表構造方法分析表構造方法編 譯 原 理 LR分分析析 (1)若項目若項目A- a 屬于屬于Ik 且且GO(Ik,a)= Ij ，a為終結符，為終結符，置置ACTIONk,a 為將為將(j，a)移進

41、棧移進?！?，簡記為，簡記為“Sj。 (2)若項目若項目A-. 屬于屬于Ik，則對任何終結符，則對任何終結符a(或結束符或結束符#)，且，且aFOLLOW（A)，置，置ACTIONk,a 為用產(chǎn)生式為用產(chǎn)生式A-a進行歸進行歸約，簡記為約，簡記為“rj”。(3)若項目若項目S-S 屬于屬于Ik (S 表示整個句子已輸入并歸約結表示整個句子已輸入并歸約結束束)，則置，則置ACTIONK，#為可為可“接受接受”，簡記為，簡記為“acc”。(4)若若GO(Ik ,A)=Ij , A為非終結符，則置為非終結符，則置GOTOk，A=j；。；。(5)分析表中凡不能用規(guī)則分析表中凡不能用規(guī)則(1)一一(4)填

42、入的空白格均置上填入的空白格均置上“報錯報錯標志標志”。分析表的分析表的ACTION子表和子表和GOTO子表構造方法：子表構造方法：首頁首頁結束結束編 譯 原 理 LR分分析析【練習】判斷下列文法是否是【練習】判斷下列文法是否是LRLR（0 0），如），如不是說明理由，判斷是否是不是說明理由，判斷是否是SLRSLR（1 1）文法。）文法。文法文法GSS-iSeSS-iSS-a編 譯 原 理 LR分分析析【練習】文法個【練習】文法個GE為：為：EE+T|TT-T*F|FF-(E)|i分析它是分析它是LR（0）文法還是）文法還是SLR（1）文法。）文法。編 譯 原 理 LR分分析析SLRSLR（1

43、 1）的局限性：）的局限性： 在在SLR方法中，若項目集方法中，若項目集Ik含有含有A- .，那么在狀態(tài)，那么在狀態(tài)k時，只要所面臨的輸入時，只要所面臨的輸入符號符號a FOLLOW(A)，就確定采取，就確定采取“用用A- 歸約歸約”的動作。但是在某種情況下，當狀的動作。但是在某種情況下，當狀態(tài)態(tài)k呈現(xiàn)于棧頂時，棧里的符號串所構成的活呈現(xiàn)于棧頂時，棧里的符號串所構成的活前綴前綴未必允許把未必允許把歸約為歸約為A，因為可能沒有，因為可能沒有一個規(guī)范句型含有前綴一個規(guī)范句型含有前綴 Aa。因此，在這種。因此，在這種情況下，用情況下，用A- 進行歸約未必有效。進行歸約未必有效。 即在即在SLR方法中

44、存在無效歸約。方法中存在無效歸約。7.4 LR（1）分析）分析【例】下列文法【例】下列文法G為為0)S-S1)S一一aAd2)S-bAc3)Saec4)S一一bed5)A-elo：S-S S一一aAd S-.bAc Saec S一一bedaI2：SaAd Sa.ec A一一eeI5：S-aec A-e AI4： SaA . dcI9: S-aec.I1:S-S.SI3：SbAc Sbed A-e bI8:S-aAd .dI6： S-bA. cAI7：S-bed A-e eI10: SbAc.cI11: S-bed .d LR(0)識別識別G的活前綴的的活前綴的DFA編 譯 原 理 LR分分析析

45、項目項目I5 、I7 中的移進中的移進-歸約沖突，不能用歸約沖突，不能用SLR(1)解決。解決。I5：S-aec A-e 因因S=S=aAd=aedRRS=S=aec對活前綴對活前綴ae，面臨輸入符號，面臨輸入符號c時應移進，面臨時應移進，面臨d時時應用應用A-e 歸約歸約FOLLOW(A)=c,d,其中面臨其中面臨c 時時存在無效歸約。存在無效歸約。首頁首頁結束結束編 譯 原 理 LR分分析析 LRLR（1 1）項目的一般形式）項目的一般形式 重新定義項目，使得每個項目都附帶有重新定義項目，使得每個項目都附帶有K個終結符。每個項目的個終結符。每個項目的一般形式是一般形式是: A- ，ala2

46、 akA- 是一個是一個LR(0)項目，每一個項目，每一個a都是終結符。這樣的一個項目都是終結符。這樣的一個項目稱為一個稱為一個LRIk項目。項目中的項目。項目中的ala2ak稱為它的向前搜索符串稱為它的向前搜索符串(或或展望串展望串)。向前搜索符串僅對歸約項目。向前搜索符串僅對歸約項目A- ，ala2 ak有意有意義。對于任何移進或待約項目義。對于任何移進或待約項目A- ，ala2 ak， ，搜索符串搜索符串a(chǎn)la2 ak不起作用。歸約項目不起作用。歸約項目A- ，ala2 ak ，意味著當它所屬的狀態(tài)呈現(xiàn)在棧頂且，意味著當它所屬的狀態(tài)呈現(xiàn)在棧頂且后續(xù)的后續(xù)的k個輸入符號為個輸入符號為ala

47、2 ak，才可以把棧頂?shù)?，才可以把棧頂?shù)?歸約為歸約為A。這。這里只對里只對k1的情形感興趣，因為對多數(shù)程序語言的語法來說，向前搜的情形感興趣，因為對多數(shù)程序語言的語法來說，向前搜索索(展望一個符號就基本可以確定展望一個符號就基本可以確定“移進移進”或或“歸約歸約”。編 譯 原 理 LR分分析析構造有效的構造有效的LR(1)項目集族的辦法本質上和構造項目集族的辦法本質上和構造LR(0)項目項目集規(guī)范族的辦法是集規(guī)范族的辦法是樣的。即也需要兩個函數(shù)樣的。即也需要兩個函數(shù)CLOSURE和和GO。 假定假定I是一個項目集，它的閉包是一個項目集，它的閉包CLOSURE()可按如下方可按如下方式構造：式

48、構造： (1)I的任何項目都屬于的任何項目都屬于CLOSURE()。 (2)若項目若項目A- ，a屬于屬于CLOSURE()， B是一個產(chǎn)生式，對于是一個產(chǎn)生式，對于FIRST( a)中的每個終結符中的每個終結符b(即即 a 所有可能推導出的開頭終結符所有可能推導出的開頭終結符b，僅當，僅當 時時b=a)如果如果B. ，b原來不在原來不在CLOSURE(I)中，則把它加進去。中，則把它加進去。 (3)重復執(zhí)行步驟重復執(zhí)行步驟(2)，直到，直到CLOSURE(I)不再增大為止不再增大為止lo：S-S ，# S一一aAd，# S-.bAc ，# Saec ，# S一一bed，#eI5：S-aec

49、,# A-e ,dAI4： SaA . d,#cI9: S-aec. ,#aI2：SaAd ,# Sa.ec,# A一一e,dI1:S-S. ，#SI3：SbAc,# Sbed ,# A-e ,c bI8:S-aAd .,#dI6： S-bA. c,#AI7：S-bed ,# A-e ,ceI10: SbAc.,#cI11: S-bed .,#dLR（1）項目集和轉換函數(shù)【例】下列文法【例】下列文法G為為0)S-S1)S一一aAd2)S-bAc3)Saec4)S一一bed5)A-e編 譯 原 理 LR分分析析假定假定C=I。，。，Il，In。，令每個，令每個Ik的下標的下標k為分析表的狀態(tài)，令

50、那個含有為分析表的狀態(tài)，令那個含有S- S，#的的Ik的的k為分析器的初態(tài)。動作為分析器的初態(tài)。動作ACTION和狀態(tài)轉換和狀態(tài)轉換GOTO可按如下方法構造：可按如下方法構造： (1)若項目若項目A一一a，b屬于屬于Ik且且GO(Ik,a)=Ij，a為終結符，則置為終結符，則置ACTIONk，a為為將狀態(tài)將狀態(tài)i和符號和符號a移進棧移進棧，簡記為，簡記為Si。 (2)若項目若項目A一一 ，a屬于屬于Ik，則置，則置ACTIONk，a為為“用產(chǎn)生式用產(chǎn)生式A-歸約歸約”，簡記為，簡記為rj,其中，其中，j是是產(chǎn)生式的編號，即產(chǎn)生式的編號，即A-是文法是文法G的第的第j個產(chǎn)生式。個產(chǎn)生式。文法的文

51、法的LR(1)項目集族構造分析表的算法是：項目集族構造分析表的算法是：首頁首頁結束結束編 譯 原 理 LR分分析析(3)若項目若項目S-S ，#屬于屬于Ik，則置，則置ACTIONk，#為為接受接受，簡記為，簡記為acc。(4)若若GO(Ik，A)=Ij，A為非終結符，則置為非終結符，則置GOTO(Ik，A)=j。(5)分析表中凡不能用規(guī)則分析表中凡不能用規(guī)則(1)(4)填入信息的空填入信息的空白欄均填上白欄均填上出錯標志出錯標志。文法的文法的LR(1)項目集族構造分析表的算法是：項目集族構造分析表的算法是：編 譯 原 理 LR分分析析按上述算法構造的分析表，若不存在多重定按上述算法構造的分析

52、表，若不存在多重定義入口義入口(即動作沖突即動作沖突)的情形，則稱它是文法的情形，則稱它是文法G的一張規(guī)范的的一張規(guī)范的LR(1)分析表。使用這種分析表分析表。使用這種分析表的分析器叫做一個規(guī)范的的分析器叫做一個規(guī)范的LR分析器。具有規(guī)分析器。具有規(guī)范的范的LR(1)分析表的文法稱為一個分析表的文法稱為一個LR(1)文法。文法。編 譯 原 理 LR分分析析【例【例】 (0) SS (1)SL=RL=R (2)SR (2)SR (3)L (3)L * *R R (4)Li (4)Li (5)RL (5)RLLR(1)比比SLR（1）能力強）能力強編 譯 原 理 LR分分析析I0:S S,# S

53、L=R,# S R,# L *R,=/#L i,=/# R L,# I1:SS ,#sI9:SL=R ,#RI6:S L= R,# R L,# L *R,# L i,# =I2:S L =R,# R L,# LI3:SR ,#RI5:Li ,=/#iiI12:Li ,#iiI13:L*R ,#RLI10:RL ,#LI7:L*R ,=/#RI8:RL ,=/#LI4: L *R,=/# R L,=/#L i,=/# L *R,=/#*I11:L * R,# R L,# L *R,# L i,# *LR(1)LR(1)項目集及轉換函數(shù)項目集及轉換函數(shù)編 譯 原 理 LR分分析析例：給定文法例：給

54、定文法GA： A-(A)|a1)畫出畫出LR（1）項目識別所有活前綴的）項目識別所有活前綴的DFA2)構造構造LR（1）分析表）分析表I0:A-.A,#A-.(A),#A-.a,#AI1:A-A.,#(I2:A-(.A),#A-.(A), )A- .a, )aI3:A- a. ,#AI4:A-(A.),#aI6:A- a. ,)AI8:A-(A.), )(I5:A-(.A), )A-.(A), )A- .a, )(a)I9:A-(A). ,)I7:A-(A). , #)LR（1）項目集和轉換函數(shù)）項目集和轉換函數(shù)編 譯 原 理 LR分分析析每個每個SLR(1)SLR(1)文法都是文法都是LR(

55、1)LR(1)的，一個的，一個SLR(1)SLR(1)文法的規(guī)范文法的規(guī)范LRLR分析器比其分析器比其SLR(1)SLR(1)分析器的分析器的狀態(tài)要多。狀態(tài)要多?！纠俊纠縂SGS：(1)S (1)S BB BB (2)B(2)BaB aB (3)B (3)B b b 編 譯 原 理 LR分分析析I0:S S,# S BB,#B aB,a/bB b,a/b I1:S S,#sI2:S BB,# B aB,#B b,# BI5:S BB,#BI6:S aB,# B aB,#B b,# aI7:B b,#bI4:B b,a/bbbI8:B aB,a/bBI9:B aB,#BI3:B aB,a/b

56、 B aB,a/b B b,a/b aaaLR(1)項目集和轉換函數(shù)b編 譯 原 理 LR分分析析ACTIONGOTOab#SB狀態(tài)0 S3 S4 1 21 acc2 S6 S7 53 S3 S4 84 r3 r3 5 r1 6 S6 S7 97 r38 r2 r2 9 r2 LR(1)分析表分析表編 譯 原 理 LR分分析析 對輸入串對輸入串a(chǎn)b#用用LR(1)分析的過程分析的過程 1 0 # ab# S3 2 03 #a b# S4 3 034 #ab # 出錯 步驟狀態(tài)棧符號棧輸入串ACTIONGOTO編 譯 原 理 LR分分析析 對輸入串對輸入串a(chǎn)bb#用用LR(1)分析的過程分析的過

57、程步驟狀態(tài)棧符號棧輸入串ACTIONGOTO1 0 # abb# S32 03 #a bb# S43 034 #ab b# r3歸約 8 4 038 #aB b# r2歸約 25 02 #B b# S76 027 #Bb # r3 57 025 #BB # r1 18 01 #S # acc abb#是該文法的一個句子是該文法的一個句子編 譯 原 理 LR分分析析7.5 LALR（1）分析）分析如果除去搜索符之后，這兩個集合是相同的，我如果除去搜索符之后，這兩個集合是相同的，我們稱兩個們稱兩個LR(1)項目集具有相同的心。把所有同項目集具有相同的心。把所有同心的心的LR(1)項日集合并為一，將

58、看到一個心就是項日集合并為一，將看到一個心就是一個一個LR(0)項目集，項目集，這種這種LR分析法稱為分析法稱為LALR(lookahead LR)方法。方法。LALR方法的特點方法的特點: 1）LALR分析表比規(guī)范分析表比規(guī)范LR分析表要小，能分析表要小，能力也差一點，但它卻能解決一些力也差一點，但它卻能解決一些SLR所不能解決所不能解決的情形。的情形。 2）對于同一個文法，）對于同一個文法，LALR分析表和分析表和LR(0)以及以及SLR分析表永遠具相同數(shù)目的狀態(tài)。分析表永遠具相同數(shù)目的狀態(tài)。編 譯 原 理 LR分分析析LALR分析表的算法基本思想是分析表的算法基本思想是： 首先構造首先構

59、造LR(1)項目集族，如不存在沖突，項目集族，如不存在沖突，就把同心集合并在一起。若合并后的集族不就把同心集合并在一起。若合并后的集族不存在歸約存在歸約歸約沖突歸約沖突(即不存在同即不存在同個項目集個項目集中像中像 A一一 和和B一一 這樣的產(chǎn)生式具有這樣的產(chǎn)生式具有相同的搜索符相同的搜索符)，就按這個項目集規(guī)范族構造，就按這個項目集規(guī)范族構造分析表。分析表。編 譯 原 理 LR分分析析LALRLALR分析表的主要步驟如下分析表的主要步驟如下: : (1)構造文法構造文法G的的LR(1)項目集族項目集族C=I0,I1,.In (2)把所有的同心集合并在一起，記把所有的同心集合并在一起，記C=J

60、0,J1,Jn含有項目含有項目S，一，一S，#的的Jk為分析表的初態(tài)。為分析表的初態(tài)。 (3)(3)從從CC構造構造ACTIONACTION表：表： A)若項目若項目A一一a，b屬于屬于Jk且且GO(Jk,a)=Jj，a為為終結符，則置終結符，則置ACTIONk，a為為將狀態(tài)將狀態(tài)i和符號和符號a移進棧移進棧，簡記為簡記為Sj。 B)若項目若項目A一一 ，a屬于屬于Jk，則置，則置ACTIONk，a為為“用產(chǎn)生式用產(chǎn)生式A-歸約歸約”，簡記為，簡記為rj,其中，其中，j是產(chǎn)生式的是產(chǎn)生式的編號，即編號，即A-是文法是文法G的第的第j個產(chǎn)生式。個產(chǎn)生式。 C)若項目若項目S-S ，#屬于屬于Jk