編譯原理第5章：語法分析-自下而上分析

第五章語法分析—自下而上分析22023/12/17主要內(nèi)容：

5.1自下而上分析基本問題

5.2算符優(yōu)先分析

5.3LR分析概述

5.4LR(0)分析

5.5SLR(1)分析

5.6LR(1)分析

5.7LALR(1)分析

5.8二義文法的應(yīng)用32023/12/175.1自下而上分析基本問題自下而上分析法(Bottom-up)基本思想：從輸入串開始，逐步進行“歸約”,直到文法的開始符號。即從樹末端開始，構(gòu)造語法樹。所謂歸約，是指根據(jù)文法的產(chǎn)生式規(guī)則，把產(chǎn)生式的右部替換成左部符號。算符優(yōu)先分析法：按照算符的優(yōu)先關(guān)系和結(jié)合性質(zhì)進行語法分析。適合分析表達式。LR分析法：規(guī)范歸約42023/12/17例：G(E)：E

i|E+E|E-E|E*E|E/E|(E)

i*i+i E*i+i E*E+i E+i E+E Ei+*EiiEEEE52023/12/17一、歸約采用“移進－歸約”思想進行自下而上分析。基本思想：設(shè)計一個堆棧，把符號串從左至右壓入棧中，判別棧頂符號是否為某一個產(chǎn)生式的右部，若是則把棧頂?shù)倪@一部分替換成(歸約為)該產(chǎn)生式的左部符號?？蓺w約串在算符優(yōu)先分析法中即為最左素短語，在規(guī)范歸約中是句柄。最左歸約是最右推導(dǎo)的逆過程，最左歸約稱為規(guī)范。62023/12/17例：設(shè)文法G(S)：(1)SaAcBe (2)Ab (3)AAb (4)Bd試對abbcde進行“移進－歸約”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAa

S

BcAae72023/12/1782023/12/17二、分析樹語法分析過程可用一棵語法分析樹表示出來。自下而上分析過程：邊輸入單詞符號，邊歸約。即，在自下而上分析的每一步，都可畫出一棵子樹，隨著歸約的完成，便最終形成一棵分析樹。如果文法無二義，分析樹恰好等同于語法樹。核心問題：識別可歸約串bdbaceSABA92023/12/17三、規(guī)范歸約定義：令G是一個文法，S是文法的開始符號，假定

是文法G的一個句型，如果有且則

稱是句型

相對于非終結(jié)符A的短語。特別地，如果有A,則稱

是句型

相對于規(guī)則A

的直接短語。一個句型的最左直接短語稱為該句型的句柄。

102023/12/17例：考慮文法G(E)：E

T|E+TTF|T*FF(E)|i

和句型i1*i2+i3：E

E+T

E+FE+i3T+i3

T*F+i3T*i2+i3

F*i2+i3

i1*i2+i3短語：i1，i2，i3，i1*i2，i1*i2+i3直接短語：i1，i2，i3句柄：i1112023/12/17在一個句型對應(yīng)的語法樹中，以某非終結(jié)符為根的兩代以上的子樹的所有末端結(jié)點從左到右排列就是相對于該非終結(jié)符的一個短語，如果子樹只有兩代，則該短語就是直接短語。EFFTTTi1+*EFi3i2122023/12/17可用句柄來對句子進行歸約 句型歸約規(guī)則 abbcde(2)Ab aAbcde(3)AAb aAcde(4)Bd

aAcBe(1)SaAcBeS132023/12/17定義：假定

是文法G的一個句子，我們稱序列

n，n-1，，0是

的一個規(guī)范歸約，如果此序列滿足：

1、

n=

2、

0為文法的開始符號，即

0=S3、對任何i，0

i

n，

i-1是從

i經(jīng)把句柄替換成為相應(yīng)產(chǎn)生式左部符號而得到的。142023/12/17把上例倒過來寫，則得到：S

aAcBe

aAcde

aAbcde

abbcde

顯然這是一個最右推導(dǎo)。最右推導(dǎo)常被稱為規(guī)范推導(dǎo)。容易看到，規(guī)范歸約是關(guān)于的一個最右推導(dǎo)的逆過程。因些，規(guī)范歸約也稱最左歸約。由規(guī)范推導(dǎo)推出的句型稱為規(guī)范句型。152023/12/17bdbaceSABAdbaceSABAdaceSABaceSABS162023/12/17四、符號棧的使用棧是語法分析的一種基本數(shù)據(jù)結(jié)構(gòu)?！?’作為棧底符號。初始狀態(tài)：棧＃輸入串ω#自左至右把輸入符號一一進棧，一旦棧頂形成句柄，就把其歸約，直至棧頂不再形成句柄為止。然后繼續(xù)移進，重復(fù)上述過程，直至形成棧＃S,輸入串＃。若達到上述狀態(tài)，則表示分析成功，否則輸入串不是句子。

172023/12/17步驟

符號棧

輸入串

動作0 # i1*i2+i3# 預(yù)備1 #i1 *i2+i3# 進2 #F *i2+i3# 歸，用F→i3#T *i2+i3# 歸，用T→F4 #T* i2+i3# 進例：考慮文法G(E)：E

T|E+TTF|T*FF(E)|i輸入串為i1*i2+i3，分析步驟為：182023/12/17步驟

符號棧

輸入串

動作4 #T* i2+i3# 進5 #T*i2 +i3# 進6 #T*F +i3# 歸，用F→i7 #T +i3# 歸，用T→T*F8 #E +i3# 歸，用E→T9 #E+ i3#進例：考慮文法G(E)：E

T|E+TTF|T*FF(E)|i輸入串為i1*i2+i3，分析步驟為：192023/12/17步驟

符號棧

輸入串

動作9#E+i3# 進10 #E+i3 # 進11 #E+F # 歸，用F→i12 #E+T # 歸，用T→F13 #E # 歸，用E→E+T14 #E # 接受例：考慮文法G(E)：E

T|E+TTF|T*FF(E)|i輸入串為i1*i2+i3，分析步驟為：202023/12/175.2算符優(yōu)先分析四則運算的優(yōu)先規(guī)則：先乘除后加減，同級從左到右考慮二義文法文法G(E)：G(E)：E

i|E+E|E-E|E*E|E/E|(E)

它的句子有幾種不同的規(guī)范規(guī)約。歸約即計算表達式的值。歸約順序不同，則計算的順序也不同，結(jié)果也不一樣。如果規(guī)定算符的優(yōu)先次序，并按這種規(guī)定進行歸約，則歸約過程是唯一的。212023/12/17算符優(yōu)先分析過程是自下而上的歸約過程，但未必是嚴(yán)格的最左歸約。也就是說，算符優(yōu)先分析法不是一種規(guī)范歸約法。所謂算符優(yōu)先分析法就是定義算符之間的某種優(yōu)先關(guān)系，借助于這種關(guān)系尋找“可歸約串”進行歸約的一種方法。222023/12/17首先必須定義任何兩個可能相繼出現(xiàn)的終結(jié)符a與b的優(yōu)先關(guān)系三種關(guān)系a<·b

a的優(yōu)先級低于bab

a的優(yōu)先級等于ba·>b

a的優(yōu)先級高于b注意：與數(shù)學(xué)上的<,>,=不同a<·b并不意味著b·>a一、直觀算符優(yōu)先分析法232023/12/17直觀算符優(yōu)先分析法使用兩個工作棧。OPTR--寄存操作符及＃，初值為＃，（輸入串末尾也加＃）OPND--寄存操作數(shù)及結(jié)果，初值為空，最后為運算結(jié)果。242023/12/17設(shè)Q代表OPTR棧頂?shù)漠?dāng)前符號，a代表新的輸入符號，則直觀算符優(yōu)先算法為：1．Readnextsymboltoa;2．Ifa=ithenpushaintoOPND,GOTO1;3．IfQ·>

athenCallE(1)QE(2);GOTO3;(注：E(1)QE(2)指popE(1);popE(2);t:=E(1),&,E(2)進行Q運算；pusht;popQ);4．IfQathenIfQ=’(‘a(chǎn)nda=‘)’thenpopQ;GOTO1;IfQ=a=‘?！痶hensuccess;halt.5．IfQ<·athenpushaintoOPTR;GOTO1;6．If(Q,a)=Err.ThenCallERROR.

252023/12/17二、算符優(yōu)先文法及優(yōu)先表構(gòu)造一個文法，如果它的任一產(chǎn)生式的右部都不含兩個相繼(并列)的非終結(jié)符，即不含如下形式的產(chǎn)生式右部：…QR…

則我們稱該文法為算符文法。約定：a、b代表任意終結(jié)符；P、Q、R代表任意非終結(jié)符；‘…’代表由終結(jié)符和非終結(jié)符組成的任意序列，包括空字。262023/12/17假定G是一個不含

-產(chǎn)生式的算符文法。對于任何一對終結(jié)符a、b，我們說：1.ab 當(dāng)且僅當(dāng)文法G中含有形如P→…ab…或P→…aQb…的產(chǎn)生式；3.a·>b 當(dāng)且僅當(dāng)G中含有形如P→…Rb…的產(chǎn)生式，而R…a或R…aQ。2.a<·

b 當(dāng)且僅當(dāng)G中含有形如P→…aR…的產(chǎn)生式，而Rb…或RQb…；如果一個算符文法G中的任何終結(jié)符對(a，b)至多只滿足下述三關(guān)系之一：a<·b，ab，a·>b則稱G是一個算符優(yōu)先文法。272023/12/17FIRSTVT構(gòu)造集合FIRSTVT(P)的算法。按其定義，可用下面兩條規(guī)則來構(gòu)造集合FIRSTVT(P)：1.若有產(chǎn)生式P→a…或P→Ra…，

則a

FIRSTVT(P)；2.若a

FIRSTVT(R)，且有產(chǎn)生式P→R…，

則a

FIRSTVT(P)。282023/12/17構(gòu)造集合LASTVT(P)的算法。按其定義，可用下面兩條規(guī)則來構(gòu)造集合LASTVT(P)：1.若有產(chǎn)生式P→…a或P→…aQ，則a

LASTVT(P)；2.若a

LASTVT(Q)，且有產(chǎn)生式P→…Q，則a

LASTVT(P)。LASTVT292023/12/17檢查G的每個候選式，若有p→…aQb…或p→…ab…的產(chǎn)生式，則置ab若G中有形如…aP…的候選式，則對于所有的b∈FIRSTUT(P)，有a<·b若G中有形如…Pb…的候選式，則對于所有的a∈LASTUT(P)有a·>b優(yōu)先關(guān)系表的構(gòu)造302023/12/17數(shù)據(jù)結(jié)構(gòu)：布爾數(shù)組F[P，a]，使得F[P，a]為真的條件是，當(dāng)且僅當(dāng)a

FIRSTVT(P)。開始時，按上述的規(guī)則(1)對每個數(shù)組元素F[P，a]賦初值。棧STACK，把所有初值為真的數(shù)組元素F[P，a]的符號對(P，a)全都放在STACK之中。構(gòu)造優(yōu)先關(guān)系表的算法312023/12/17運算：如果棧STACK不空，就將頂項逐出，記此項為(Q，a)。對于每個形如P→Q…

的產(chǎn)生式，若F[P，a]為假，則變其值為真且將(P，a)推進STACK棧。上述過程必須一直重復(fù)，直至棧STACK拆空為止。322023/12/17如果把這個算法稍為形式化一點，我們可得如下所示的一個程序(包括一個過程和主程序)：PROCEDUREINSERT(P，a)；IFNOTF[P，a]THENBEGINF[P，a]:=TRUE；

把(P，a)下推進STACK棧END；332023/12/17主程序：BEGIN

FOR每個非終結(jié)符P和終結(jié)符aDOF[P，a]:=FALSE；

FOR每個形如P→a…或P→Qa…的產(chǎn)生式DO INSERT(P，a)；

WHILESTACK非空DO BEGIN

把STACK的頂項，記為(Q，a)，上托出去； FOR每條形如P→Q…的產(chǎn)生式DO INSERT(P，a)； ENDOFWHILE；END342023/12/17這個算法的工作結(jié)果得到一個二維數(shù)組F，從它可得任何非終結(jié)符P的FIRSTVT。FIRSTVT(P)＝{a|F[P，a]=TRUE}同理，可構(gòu)造計算LASTVT的算法。352023/12/17三、算符優(yōu)先分析法的設(shè)計可歸約串，句型，短語，直接短語，句柄，規(guī)范歸約。一個文法G的句型的素短語是指這樣一個短語，它至少含有一個終結(jié)符，并且，除它自身之外不再含任何更小的素短語。最左素短語是指處于句型最左邊的那個素短語。362023/12/17例：考慮下面的文法G(E)：(1)E→E+T|T(2)T→T*F|F (3)F→P

F|P(4)P→(E)|iEEF+*TiFTFTP+ETP句型：T+F*P+i短語：直接短語：句柄：素短語：最左素短語：,T+F*P+iT,F,P,F*P,,iT+F*PT,F,P,iTF*P,iF*P372023/12/17算符優(yōu)先文法句型(括在兩個＃之間)的一般形式寫成：#N1a1N2a2…NnanNn+1#

其中，每個ai都是終結(jié)符，Ni是可有可無的非終結(jié)符。定理：一個算符優(yōu)先文法G的任何句型的最左素短語是滿足如下條件的最左子串Njaj…NiaiNi+1，

其中，aj-1<·aj ajaj+1，…，ai-1ai ai·>ai+1382023/12/17根據(jù)這個定理，下面我們討論算符優(yōu)先分析算法。為了和定理敘述的相適應(yīng)，我們使用一個符號棧S，用它寄存終結(jié)符和非終結(jié)符，下面的分析算法是直接根據(jù)這個定理構(gòu)造出來的，k代表符號棧S的使用深度。

392023/12/17k:=1; S[k]:=‘#’;REPEAT

把下一個輸入符號讀進a中； IFS[k]

VTTHENj:=kELSEj:=k-1; WHILES[j]aDO BEGIN REPEAT Q:=S[j]; IFS[j-1]

VTTHENj:=j-1ELSEj:=j-2 UNTILS[j]Q;

把S[j+1]…S[k]歸約為某個N； k:=j+1; S[k]:=N ENDOFWHILE; IFS[j]aORS[j]aTHEN BEGINk:=k+1;S[k]:=aEND ELSEERROR/*調(diào)用出錯診察程序*/UNTILa=‘#’自左至右，終結(jié)符對終結(jié)符，非終結(jié)符對非終結(jié)符，而且對應(yīng)的終結(jié)符相同。N→X1X2…Xk-j

???S[j+1]S[j+2]…S[k]402023/12/17在算法的工作過程中，若出現(xiàn)j減1后的值小于等于0時，則意味著輸入串有錯。在正確的情況下，算法工作完畢時，符號棧S應(yīng)呈現(xiàn)：#N#。由于非終結(jié)符對歸約沒有影響，因此，非終結(jié)符根本可以不進符號棧S。412023/12/17算符優(yōu)先分析一般并不等價于規(guī)范歸約。EE+*iTP+iPiPiPEEF+*TiFTFTP+ETiFPiPiP考慮下面的文法G(E)：(1)E→E+T|T(2)T→T*F|F (3)F→P

F|P(4)P→(E)|i的句子i+i*i+i422023/12/17算符優(yōu)先分析法特點：優(yōu)點:簡單，快速缺點:可能錯誤接受非法句子，能力有限.算符優(yōu)先分析法是一種廣為應(yīng)用、行之有效的方法。用于分析各類表達式ALGOL60432023/12/17四、優(yōu)先函數(shù)把每個終結(jié)符

與兩個自然數(shù)f(

)與g(

)相對應(yīng)，使得若

1

2，則f(

1)<g(

2)若

1

2，則f(

1)=g(

2)若

1

2，則f(

1)>g(

2)f稱為入棧優(yōu)先函數(shù)，g稱為比較優(yōu)先函數(shù)。優(yōu)點:便于比較，節(jié)省空間；缺點:原來不存在優(yōu)先關(guān)系的兩個終結(jié)符，由于自然數(shù)相對應(yīng)，變成可以比較的。要進行一些特殊的判斷。442023/12/17例：文法G(E)(1)E→E+T|T(2)T→T*F|F (3)F→P

F|P(4)P→(E)|i的優(yōu)先函數(shù)如下表452023/12/17有許多優(yōu)先關(guān)系表不存在優(yōu)先函數(shù)，如：

不存在對應(yīng)的優(yōu)先函數(shù)f和g

假定存在f和g，則有f(a)=g(a)，f(a)>g(b)，f(b)=g(a)，f(b)=g(b)

導(dǎo)致如下矛盾:f(a)>g(b)=f(b)=g(a)=f(a)如果優(yōu)先函數(shù)存在，則不唯一(無窮多)462023/12/17如果優(yōu)先函數(shù)存在，則可以通過以下三個步驟從優(yōu)先表構(gòu)造優(yōu)先函數(shù):1對于每個終結(jié)符a，令其對應(yīng)兩個符號fa和ga，畫一以所有符號和為結(jié)點的方向圖。

如果a

b，則從fa畫一條弧至gb。

如果a

b，則畫一條弧從gb至fa

。2對每個結(jié)點都賦予一個數(shù)，此數(shù)等于從該結(jié)點出發(fā)所能到達的結(jié)點(包括出發(fā)點自身)。賦給fa的數(shù)作為f(a)，賦給ga的數(shù)作為g(a)。3檢查所構(gòu)造出來的函數(shù)f和g是否與原來的關(guān)系矛盾。若沒有矛盾，則f和g就是要求的優(yōu)先函數(shù)，若有矛盾，則不存在優(yōu)先函數(shù)。472023/12/17現(xiàn)在必須證明：若ab，則f(a)＝g(b)；若ab，則f(a)<g(b)；若ab，則f(a)>g(b)。第一個關(guān)系可從函數(shù)的構(gòu)造直接獲得。因為，若ab，則既有從fa到gb的弧，又有從gb到fa的弧。所以，fa和gb所能到達的結(jié)是全同的。至于ab和ab的情形，只須證明其一。482023/12/17如果ab，則有從fa到gb的弧。也就是，gb能到達的任何結(jié)fa也能到達。因此，f(a)

g(b)。我們所需證明的是，在這種情況下，f(a)＝g(b)不應(yīng)成立。我們將指出，如果f(a)＝g(b)，則根本不存在優(yōu)先函數(shù)。假若f(a)＝g(b)，那么必有如下的回路：492023/12/17

因此有ab,a1b,a1b1,…,ambm,abm對任何優(yōu)先函數(shù)f’和g’來說，必定有f’(a)>g’(b)

f’(a1)

g’(b1)

…

f’(am)

g’(bm)

f’(a)從而導(dǎo)致f’(a)>f’(a)，產(chǎn)生矛盾。因此，不存在優(yōu)先函數(shù)f和g。fa1fafamgb1gbgbm……502023/12/175.3LR分析概述

1、ＬＲ分析器模型總控程序outputInput#S1Xm…S1…X1S0#棧狀態(tài)文法符號ACTIONGOTOLR分析表產(chǎn)生式表512023/12/17邏輯上說，一個LR分析器由3個部分組成：(1)

總控程序，也可以稱為驅(qū)動程序。對所有的LR分析器總控程序都是相同的。(2)

分析表或分析函數(shù)，不同的文法分析表將不同，同一個文法采用的LR分析器不同時，分析表也不同，分析表又可分為動作表（ACTION）和狀態(tài)轉(zhuǎn)換（GOTO）表兩個部分，它們都可用二維數(shù)組表示。

(3)分析棧，包括文法符號棧和相應(yīng)的狀態(tài)棧，它們均是先進后出棧。分析器的動作就是由棧頂狀態(tài)和當(dāng)前輸入符號所決定。2、LR分析方法的邏輯結(jié)構(gòu)522023/12/17

總控程序根據(jù)不同的分析表來決定其下一步的處理動作，分析表是根據(jù)具體的文法按某種規(guī)則構(gòu)造出來的。LR方法是根據(jù)具體文法的分析表對輸入串進行分析處理。

LR分析過程的思想是在總控程序的控制下，從左到右掃描輸入符號串，根據(jù)分析棧中的狀態(tài)和文法及當(dāng)前輸入符號，按分析表完成相應(yīng)的分析工作。532023/12/17分析表的組成：(1)分析動作表Action

符號狀態(tài)a1a2…atS0action[S0,

a1]action[S0,

a2]…action[S0,

at]S1action[S1,

a1]action[S1,

a2]…action[S1,

at]……………Snaction[Sn,

a1]action[Sn,

a2]…action[Sn,

at]542023/12/17

表中action[Si,aj]為二維數(shù)組，指出當(dāng)前棧頂為狀態(tài)Si，輸入符號為aj是所執(zhí)行的動作。其動作有四種可能，分別為移進(S)、歸約(r)、接受(acc)、出錯(error)。(2)狀態(tài)轉(zhuǎn)換表goto552023/12/17

符號狀態(tài)x1x2…xtS0goto[S0,

x1]goto[S0,

x2]…goto[S0,

xt]S1goto[S1,x1]goto[S1,

x2]…goto[S1,

xt]……………Sngoto[Sn,

x1]goto[Sn,

x2]…goto[Sn,

xt]

表中g(shù)oto[Si,xj]指出棧頂狀態(tài)為Si，文法符號為xj時應(yīng)轉(zhuǎn)到的下一狀態(tài)。562023/12/175656分析表種類的不同決定使用不同的LR分析方法a)SLR分析表(簡單LR分析表)

b)LR分析表(規(guī)范LR分析表)構(gòu)造簡單,最易實現(xiàn),大多數(shù)上下文無關(guān)文法都可以構(gòu)造出SLR分析表,所以具有較高的實用價值。使用SLR分析表進行語法分析的分析器叫SLR分析器適用文法類最大,大多數(shù)上下文無關(guān)文法都能構(gòu)造出LR分析表,但其分析表體積太大.暫時實用價值不大.572023/12/175757c)LALR分析表(超前LR分析表)這種表適用的文法類及其實現(xiàn)上難易在上面兩種之間,在實用上很吸引人.使用LALR分析表進行語法分析的分析器叫LALR分析器。例：YACC

文法規(guī)則文件YACC源文件YACC某語言的LALR分析器582023/12/1758581.三種分析表對應(yīng)三類文法幾點說明2.一個SLR文法必定是LALR文法和LR文法592023/12/173、LR分析過程：LR分析步驟：(a)將初始狀態(tài)S0和句子的左界符#分別進分析棧。(b)根據(jù)棧頂狀態(tài)和當(dāng)前輸入符號查動作表，進行如下的工作。※移進：當(dāng)前輸入符號進符號棧，根據(jù)狀態(tài)轉(zhuǎn)換表新的狀態(tài)進狀態(tài)棧，繼續(xù)掃描，從而下一輸入符號變成當(dāng)前輸入符號。

※歸約：(1)按某個產(chǎn)生式進行歸約，若產(chǎn)生式的右端長度為n，則符號棧頂和狀態(tài)頂n個元素同時相應(yīng)退棧。(2)歸約后的文法符號進符號棧，(3)查602023/12/17狀態(tài)轉(zhuǎn)換表，新的狀態(tài)進狀態(tài)棧。(c)接受：分析成功，終止分析。

(d)出錯：報告出錯信息。(2)具體分析過程：舉例說明具體分析過程：設(shè)文法為G[L]

（假定已存在LR分析表）

(1)LE,L(2)LE(3)Ea(4)Eb612023/12/17

LR分析算法置ip指向輸入串w的第一個符號令S為棧頂狀態(tài)a是ip指向的符號重復(fù)beginifACTION[S,a]=Sj

then

beginPUSHj,a(進棧)ip前進(指向下一輸入符號)

endelse

ifACTION[S,a]=rj(第j條產(chǎn)生式為A)622023/12/17LR分析算法then

beginpop||項令當(dāng)前棧頂狀態(tài)為S’pushGOTO[S’,A]和A(進棧)endelse

ifACTION[s,a]=accthenreturn(成功）elseerrorend.重復(fù)632023/12/17

為了介紹LR分析過程，在這里直接給出該文法的分析表，之后再介紹如何生成該表。狀態(tài)ACTIONGOTOab,#LES0S3S412S1accS2S5r2S3r3r3S4r4r4S5S3S462S6r1ri表示按第i個產(chǎn)生式進行歸約Si表示把當(dāng)前輸入符號移進棧，且轉(zhuǎn)第i個狀態(tài)，即第i個狀態(tài)進狀態(tài)棧。i表示轉(zhuǎn)第i個狀態(tài)，即第i個狀態(tài)進狀態(tài)棧?？瞻妆硎痉治鰟幼鞒鲥e。642023/12/17

根據(jù)上述分析表，即可對輸入串進行分析。如輸入串為#a,b,a#具體分析過程如下：狀態(tài)棧符號棧產(chǎn)生式輸入符號說明S0#a,b,a#S0和#進棧S0S3#a,b,a#a和S3進棧S0S2#EE

a,b,a#a和S3退棧E和S2進棧S0S2S5#E,b,a#,和S5進棧S0S2S5S4#E,b,a#b和S4進棧S0S2S5S2#E,EE

b,a#b和S4退棧E和S2進棧652023/12/17狀態(tài)棧符號棧產(chǎn)生式輸入符號說明S0S2S5S2S5#E,E,a#,和S5進棧S0S2S5S2S5S3#E,E,a#a和S3進棧S0S2S5S2S5S2#E,E,EE

a#a和S3退棧E和S2進棧S0S2S5S2S5S6#E,E,LL

E#E和S2退棧L和S6進棧S0S2S5S6#E,LL

E,L#E,L和S2S5S6退L和S6進棧S0S1#LL

E,L#E,L和S2S5S6退L和S1進棧acc662023/12/17自底向上分析法的關(guān)鍵問題是在分析過程中如何確定句柄。LR方法中的句柄是通過求可歸前綴而求得。672023/12/17例：文法G[S]為：SaAcBeAbAAbBd為產(chǎn)生式加序號變?yōu)椋篠aAcBe[1]Ab[2]AAb[3]Bd[4]對于輸入串a(chǎn)bbcde句子的最右推導(dǎo)（規(guī)范推導(dǎo)）如下：SaAcBe[1]aAcd[4]e[1]aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]活前綴與可歸前綴682023/12/17對它的逆過程最左歸約(規(guī)范歸約)為：ab[2]b[3]cd[4]e[1]

aAb[3]cd[4]e[1]

aAcd[4]e[1]

aAcBe[1]

S用哪個產(chǎn)生式繼續(xù)歸約僅取決于當(dāng)前句型的前部。

我們把每次采取歸約動作前的符號串部分稱為可歸前綴。

LR分析的關(guān)鍵就是識別何時到達可歸前綴。為產(chǎn)生式加序號變?yōu)椋篠aAcBe[1]Ab[2]AAb[3]Bd[4]692023/12/17在規(guī)范句型中形成可歸前綴之前包括可歸前綴的所有前綴稱為活前綴?；钋熬Y為一個或若干規(guī)范句型的前綴。在規(guī)范歸約過程中的任何時刻只要已分析過的部分即在符號棧中的符號串均為規(guī)范句型的活前綴，則表明輸入串的已被分析過的部分是某規(guī)范句型的一個正確部分。例如：有下面規(guī)范句型的前綴：

，a，ab

，a，aA，aAb

，a，aA，aAc，aAcd

，a，aA，aAc，aAcB，aAcBe左部均為活前綴，其中，紅色部分為可歸前綴702023/12/17G=(Vn,Vt,P,S),若有S’

αAω

αβω,Aβ（β是句柄）γ是αβ的前綴,則稱是文法G的活前綴αβ是含句柄的活前綴，并且句柄是αβ的后端，則稱αβ是可歸前綴或可規(guī)范前綴。在LR分析過程中，實際上是把αβ的前綴（即文法G的活前綴）列出放在符號棧中，一旦在棧中出現(xiàn)αβ（形成可歸前綴），即句柄已經(jīng)形成，則用產(chǎn)生式Aβ進行歸約?；钋熬Y的定義及在LR分析中的應(yīng)用712023/12/17識別活前綴的有限自動機對任何一個上下文無關(guān)文法，只要能構(gòu)造出它的識別可歸前綴的有限自動機，就可以構(gòu)造其相應(yīng)的分析表（狀態(tài)轉(zhuǎn)換表和動作表）。722023/12/17☆

狀態(tài)棧:S0,S1,…,Sm

狀態(tài)S0---初始狀態(tài)Sm---棧頂狀態(tài)

棧頂狀態(tài)概括了從分析開始到該狀態(tài)的全部分析歷史.☆符號棧:

X1X2.....Xm

為從開始狀態(tài)(S0)到當(dāng)前狀態(tài)(Sm)所識別的規(guī)范句型的活前綴.#S0x1S1x2......xmSmS0S1......Sm#x1x2.....xm732023/12/17☆分析表是一個矩陣：行---分析器的狀態(tài)列----文法符號狀態(tài)符號ETFS0S1S2:SnGOTO表a.狀態(tài)轉(zhuǎn)移表(GOTO表)742023/12/17GOTO[Si-1,xi]=Si Si-1---當(dāng)前狀態(tài)(棧頂狀態(tài)) xi---新的棧頂符號

Si------

新的棧頂狀態(tài)(狀態(tài)轉(zhuǎn)移)Si需要滿足條件是:

若X1X2….Xi-1是由S0到Si-1所識別的規(guī)范句型的活前綴,則X1X2….Xi是由S0到Si所識別的規(guī)范句型的活前綴#S0x1S1x2......xi-1Si-1xiSi狀態(tài)符號ETFS0S1S2:SnGOTO表752023/12/17通過對有窮自動機的了解,我們可以看出:

狀態(tài)轉(zhuǎn)移函數(shù)GOTO是定義了一個以文法符號集為字母表的有窮自動機，該自動機識別文法所有規(guī)范句型的活前綴及可歸前綴。M=(S,V,GOTO,S0,Z)S0S1Si-1S2SiX1X2Xi-1Xi762023/12/17b.分析動作表(ACTION表)Sn狀態(tài)s輸入符號ai+*()#S0S1S2:ACTION表ACTION[Si,a]=動作分析a∈Vt識別為活前綴的，則移進；識別為可歸前綴的，則歸約772023/12/17分析動作：1)移進(shift)ACTION[Si,a]=S動作：將a推進棧，并設(shè)置新的棧頂狀態(tài)SjSj=GOTO[Si,a]，將指針指向下一個輸入符號2)規(guī)約(reduce)ACTION[Si,a]=rdd：文法規(guī)則編號(d)A→β動作：將符號串β(假定長度為n)連同狀態(tài)從棧內(nèi)彈出把A推進棧，并設(shè)置新的棧頂狀態(tài)Sj,Sj=GOTO[Si-n,A]3)接受(accept)ACTION[Si,#]=accept4)出錯(error)ACTION[Si,a]=error782023/12/17☆控制程序:(DriverRoutine)1)根據(jù)棧頂狀態(tài)和現(xiàn)行輸入符號，查分析動作表(ACTION表)，執(zhí)行有分析表所規(guī)定的操作；

2)并根據(jù)GOTO表設(shè)置新的棧頂狀態(tài)(即實現(xiàn)狀態(tài)轉(zhuǎn)移)792023/12/17例：文法G[E] (1)E::=E+T (2)E::=T (3)T::=T*F (4)T::=F (5)F::=(E) (6)F::=i（2）LR分析過程該文法是SLR文法,故可以構(gòu)造出SLR分析表(ACTION表和GOTO表)802023/12/17ACTION表GOTO表文法G[E]：(1)E::=E+T(2)E::=T(3)T::=T*F(4)T::=F(5)F::=(E)(6)F::=i文法符號狀態(tài)i+*()#ETF0(S0)S5S41231(S1)S6ACCEPT2(S2)R2S7R2R23(S3)R4R4R4R4

4(S4)S5S48235(S5)R6R6R6R66(S6)S5S4937(S7)S5S4108(S8)S6S119(S9)R1S7R1R110(S10)R3R3R3R311(S11)R5R5R5R5812023/12/17ACTION表GOTO表輸入符號狀態(tài)文法G[E](1)E::=E+T(2)E::=T(3)T::=T*F(4)T::=F(5)F::=(E)(6)F::=iSi：移入，i為狀態(tài)Ri：規(guī)約，i為產(chǎn)生式編號822023/12/17分析過程：

i*i+i步驟 狀態(tài)棧 符號 輸入串 動作1 ＃0 ＃ i*i+i# 初始化2 ＃0i5 ＃i *i+i# S3 ＃0F3 ＃F *i+i# R64 ＃0T2 ＃T *i+i# R45 ＃0T2*7 ＃T* i+i# S6 ＃0T2*7i5 ＃T*i +i# S7 ＃0T2*7F10 ＃T*F +i# R6832023/12/1711 ＃0E1+6i5 #E+i # S12 ＃0E1+6F3 #E+F # R613 ＃0E1+6T9 #E+T # R414 ＃0E1 #E # R115 #E Accept9 ＃0E1 #E +i# R210 ＃0E1+6 #E+ i# S8 ＃0T2 #T +i# R3842023/12/17由分析過程可以看到:(1)每次規(guī)約總是規(guī)約當(dāng)前句型的句柄，是規(guī)范規(guī)約，可以看到語法樹(算符優(yōu)先是規(guī)約最左素短語)EET+TT*FFiiFi87564321(2)分析的每一步棧內(nèi)符號串均是規(guī)范句型的活前綴，與輸入串的剩余部分構(gòu)成規(guī)范句型.852023/12/17LR方法概述（回顧）LR文法：

如果一個文法能構(gòu)造一張LR分析表，使其每個入口均是唯一確定的，那么稱此文法為LR文法。LR(k)指分析的每步最多只需向前搜索k個字符便能確定采取什么動作。

任何二義文法都不可能是LR(k)的，不管k多大。862023/12/17LR分析法如何分析句子？

移進歸約（從左到右掃描(L)自底向上進行規(guī)約(R)）移進歸約的關(guān)鍵問題是什么？

判斷符號棧頂?shù)姆柎欠駱?gòu)成句柄。LR分析法如何識別句柄？LR分析法在分析過程中并不是直接分析符號棧中的符號是否形成句柄，而是通過識別可歸前綴來識別句柄。

具體地，LR分析法的分析過程可以看作識別活前綴和可歸前綴的過程，只要符號棧中的符號串構(gòu)成活前綴，就表示已分析過的部分是正確的，繼續(xù)移進；直到符號棧中的符號串構(gòu)成可歸前綴，則表示當(dāng)前棧頂符號串已形成句柄，則進行歸約。872023/12/17如何識別活前綴和可歸前綴？

通過有限自動機來識別。如何構(gòu)造識別活前綴和可歸前綴的有限自動機？

根據(jù)文法規(guī)則：

狀態(tài)集合：列出所有活前綴的識別狀態(tài)

符號表：所有的終結(jié)符和非終結(jié)符

狀態(tài)轉(zhuǎn)換函數(shù)：f(Ki，a)=Kj某一個活前綴的識別狀態(tài)，在輸入符號表中的一個符號之后，轉(zhuǎn)向另一個活前綴的識別狀態(tài)。

終態(tài)集：所有可歸前綴的識別狀態(tài)882023/12/175.4LR(0)分析構(gòu)造LR分析器的關(guān)鍵是構(gòu)造其分析表構(gòu)造LR分析表的方法是:（1）根據(jù)文法構(gòu)造識別規(guī)范句型活前綴的有窮自動機DFA（2）由DFA構(gòu)造LR分析表892023/12/171.構(gòu)造DFA(1)DFA是一個五元式M=(S,V,GOTO,S0,Z)S：有窮狀態(tài)集在此具體情況下，S=LR(0)項目集規(guī)范族LR(0)。項目集規(guī)范族：其元素是由項目所構(gòu)成的集合.V：文法字匯表Vn∪VtS0：初始狀態(tài)GOTO:狀態(tài)轉(zhuǎn)移函數(shù)GOTO[Si,X]=SjSi,Sj∈SSi,Sj為項目集合X∈Vn∪Vt表示當(dāng)前狀態(tài)Si面臨文法符號為X時，應(yīng)將狀態(tài)轉(zhuǎn)移到

SjZ：終態(tài)集合902023/12/171）確定S集合，即LR（0）項目集規(guī)范族，同時確定S02）確定狀態(tài)轉(zhuǎn)移函數(shù)GOTO∴構(gòu)造DFA方法：912023/12/17LR(0)分析確定狀態(tài)集合每一個狀態(tài)對應(yīng)文法中某一個產(chǎn)生式規(guī)則的某一個項目每一個產(chǎn)生式規(guī)則的每一個項目代表一個活前綴的識別狀態(tài)。產(chǎn)生式規(guī)則的項目？922023/12/17項目:文法G的每個產(chǎn)生式(規(guī)則)的右部添加一個圓點就構(gòu)成一個項目。例:產(chǎn)生式:A→XYZ

項目:A→.XYZA→X.YZA→XY.ZA→XYZ.

產(chǎn)生式:A→ε

項目:A→.項目的直觀意義:指明在分析過程中的某一時刻已經(jīng)規(guī)約的部分和等待規(guī)約部分。其中，ε、X、XY、XYZ為活前綴，XYZ是可歸前綴。932023/12/17

例如：產(chǎn)生式S

aAcBe對應(yīng)有6個項目。

[0]S

·aAcBe[1]S

a·AcBe[2]S

aA·cBe[3]S

aAc·Be[4]S

aAcB·e[5]S

aAcBe·942023/12/17項目類型：

項目類型有歸約項目、移進項目、待約項目和接受項目。

歸約項目：后繼符號為空的項目稱為歸約項目。如：A·此時已把分析結(jié)束，已在棧頂，從而可按相應(yīng)的產(chǎn)生式進行歸約。

移進項目：后繼符號為終結(jié)符的項目稱為移進項目。如A

·X

，XVt

此時把X移進，即X進符號棧。

待約項目：后繼符號為非終結(jié)符的項目，稱為待約項目。952023/12/17

此時期待著從余留的輸入符號中進行歸約而得到X。

接受項目：當(dāng)歸約項目為S’S·時則表明已分析成功，即輸入串為該文法的句子，相應(yīng)狀態(tài)為接受狀態(tài)。構(gòu)造識別活前綴的NFAP131從A

·X

畫X弧指向A

X·

；如果XVn，則還需要畫空子弧指向X

·w962023/12/17例：文法：S→aAbA→aA|a972023/12/17IIaIbIA確定化為：982023/12/17992023/12/17狀態(tài)內(nèi)容是項目集組成的，它分為基本(BASIC)部分和閉包(CLOSURE)部分?！驜ASIC和CLOSURE的方法如下：設(shè)Si是Sk關(guān)于符號X的后繼狀態(tài)，則有

BASIC(Si)的計算：BASIC(Si)={AX·|A·XSk}CLOSURE(Si)的計算：

BASIC(Si)

CLOSURE(Si)LR(0)項目集規(guī)范族的構(gòu)造1002023/12/17

若A

·YCLOSURE(Si),且YVn則Y·rCLOSURE(Si),r為符號串

重復(fù)直到CLOSURE(Si)不再增加為止。例如：文法G[S]：S

AA

aAbA

c設(shè)開始狀態(tài)為S0，則S0的狀態(tài)內(nèi)容為：BASIC(S0)={S

·A}CLOSURE(S0)={S

·A,A

·aAb,A

·c}1012023/12/17A.項目集閉包closure的定義和計算:

令I(lǐng)是文法G’的任一項目集合，定義closure(I)為項目集合I的閉包，可用一個過程來定義并計算closure(I)。Procedureclosure(I);begin

將屬于I的項目加入closure(I);repeatforclosure(I)中的每個項目A→α.Bβ(B∈Vn)do

將B→.r(r∈V*)加入closure(I)untilclosure(I)不再增大end例:G’[E’]令I(lǐng)={E’→.E}closure(I)={E’→.E,E→.E+T,E→.T,T→.T*F,T→.F,F→.(E),F→.i}1022023/12/17B狀態(tài)轉(zhuǎn)移函數(shù)GOTO的定義:GOTO(I,X)=closure(J)I：項目集合

X：文法符號，X∈VJ：項目集合J={任何形如A→αX.β的項目|A→α.Xβ∈I}closure(J):項目集J的閉包仍是項目集合所以,GOTO(I,X)=closure(J)的直觀意義是:

它規(guī)定了識別文法規(guī)范句型活前綴的DFA從狀態(tài)I(項目集)出發(fā),經(jīng)過X弧所應(yīng)該到達的狀態(tài)(項目集合)1032023/12/17LR(0)項目集規(guī)范族的構(gòu)造算法:P107步驟（1）、（2）、（3）G'→LR(0)ProcedureITEMSETS(G');beginLR(0):={closure({E'→.E})};repeatforLR(0)中的每個項目集I和G'的每個符號XdoifGOTO(I,X)非空,且不屬于LR(0)then把GOTO(I,X)放入LR(0)中

untilLR(0)不再增大end1042023/12/17例.求G'[E']的LR(0)V={E,T,F,I,+,*,(,)}G'[E']共有20個項目LR(0)={I0,I1,I2,…I11}有12個項目組成:I0: E'→.E E→.E+T E→.T T→.T*F T→.F F→.(E) F→.iI1: E'→E. E→E.+TClosure({B’→.B})=I0GOTO(I0,E)=closure({E’→E.E→E.+T})=I1(0)E’→E(4)T→FE→E+T(5)F→(E)E→T(6)F→iT→T*F1052023/12/17I2: E→T.GOTO(I0,T)=closure({E→T.T→T.*F})=I2T→T.*FI3: T→F.GOTO(I0,F)=closure({T→F.})=I3I4: F→(.E)GOTO(I0,()=closure({F→(.E)})=I4E→.E+TE→.T T→.T*F T→.F F→.(E) F→.iI5: F→i.GOTO(I0,i)=closure({F→i.})=I5GOTO(I0,*)=φGOTO(I0,+)=φGOTO(I0,))=φI0:E'→.EE→.E+TE→.TT→.T*FT→.FF→.(E)F→.i1062023/12/17I6: E→E+.TGOTO(I1,+)=closure({E→E+.T})=I6 T→.T*FGOTO(I1,其他符號)為空

T→.F F→.(E) F→.iI7: T→T*.F GOTO(I2,*)=closure({T→T*.F})=I7 F→.(E) GOTO(I2,其他符號)為空

F→.i GOTO(I3,其他符號)為空

I1:E'→E.E→E.+TI2:E→T.T→T.*F1072023/12/17I8: F→(E.) GOTO(I4,E)=closure({F→(E.),E→E.+T})=I8 E→E.+T GOTO(I4,T)=I2∈LR(0) GOTO(I4,F)=I3∈LR(0) GOTO(I4,()=I4∈LR(0) GOTO(I4,i)=I5∈LR(0) GOTO(I4,+)=φ GOTO(I4,*)=φ GOTO(I4,))=φGOTO(I5,其他符號)=φI9: E→E+T. GOTO(I6,T)=closure({E→E+T.,T→T.*F})=I9 E→T.*F GOTO(I6,F)=I3 GOTO(I6,()=I4 GOTO(I6,i)=I5

I4: F→(.E)E→.E+TE→.TT→.T*F T→.F F→.(E) F→.i1082023/12/17I10:T→T*F. GOTO(I7,T)=closure({T→T*F.})=I10 GOTO(I7,()=I4 GOTO(I7,i)=I5I11:F→(E). GOTO(I8,))=closure({F→(E).})=I11 GOTO(I7,()=I4 GOTO(I7,i)=I5求完所有Ii的后繼GOTO(I8,+)=I6GOTO(I9,*)=I7GOTO(I10,所有符號)=φ,GOTO(I11,所有符號)=φ1092023/12/17構(gòu)造DFA

M=(S,V,GOTO,S0,Z) S={I0,I1,I2,…,I11}=LR(0) V={+,*,i,(,),E,T,F} GOTO(Im,X)=Im

S0=I0 Z=S-{I0}={I1,I2,…,I11}1102023/12/17I0I5I2I4I3I1I11I8I6I10I7I9startE++iF(TTF(iF(iE(**)+iF1112023/12/17除I0以外,其余狀態(tài)都是活前綴的識別狀態(tài),從I0到每一狀態(tài)的每條路徑都識別和接受一個規(guī)范句型的活前綴。1122023/12/17項目集的相容性：〖定義〗滿足下列兩個條件的項目集稱為相容的項目集。

※無移進項目和歸約項目并存。※無多個歸約項目并存。例如：若有項目集｛A·，B·｝此時棧頂為，根據(jù)項目集無法確定是移進還是歸約。項目集是不相容的。

對一個文法的LR(0)項目集規(guī)范族不存在移進歸約或歸約歸約沖突時，稱該文法為LR(0)文法。

1132023/12/17LR(0)分析表的構(gòu)造LR（0）分析表由兩部分組成：動作表表示當(dāng)前狀態(tài)下面臨輸入符號應(yīng)做的動作是移進、歸約、接受或出錯；狀態(tài)轉(zhuǎn)換表表示在當(dāng)前狀態(tài)下面臨文法符號時應(yīng)轉(zhuǎn)向的下一個狀態(tài)。1142023/12/17(2)LR(0)分析表的構(gòu)造構(gòu)造原則：

設(shè)有文法G[S]，則LR(0)分析表的構(gòu)造規(guī)則為：

對于A·XSi，GOTO(Si,X)=Sj

若X

Vt，則置action[Si,X]=Sj

若XVn，則置goto[Si,X]=j

對于A·Si，若A是文法的第j個產(chǎn)生式，則對所有的xVt，均置action[Si,x]=rj

若S·Si，則置action[Si,#]=acc

其他均置出錯。1152023/12/17LR(0)分析表的構(gòu)造假定C={I0,I1,……，In}，令每個項目集Ik的下標(biāo)k為分析器的一個狀態(tài)，因此，G`的LR(0)分析表含有狀態(tài)0，1，……，n。令那個含有項目S`→．S的Ik的下標(biāo)k為初態(tài)。ACTION和GOTO可按如下方法構(gòu)造：若項目A→α．a(chǎn)β屬于Ik且GO(Ik,a)=Ij,a為終結(jié)符，則置ACTION[k,a]為“把狀態(tài)j和符號a移進?！保営洖椤皊j”;若項目A→α．屬于Ik,那么，對任何終結(jié)符a,置ACTION[k,a]為“用產(chǎn)生式A→α進行規(guī)約”，簡記為“rj”;其中，假定A→α為文法G`的第j個產(chǎn)生式；若GO(Ik,A)=Ij,A為非終結(jié)符，則置GOTO(k,A)=j;若項目S`→S．屬于Ik,則置ACTION[k,#]為“接受”，簡記為“acc”;分析表中凡不能用規(guī)則1至4填入信息的空白格均置上“出錯標(biāo)志”1162023/12/17例子：文法G為：(0)S’E

(1)EaA(2)EbB(3)A

cA(4)A

d(5)B

cB(6)B

d該文法的狀態(tài)描述序列見下表：1172023/12/17狀態(tài)項目集后繼符號后繼狀態(tài)S0{S’·EE·aAE·bBEabS1S2S3S1{S’E·}#S12S2{Ea·AA·cAA·d}AcdS6S4S10S3{Eb·BB·cBB·d}BcdS7S5S111182023/12/17狀態(tài)項目集后繼符號后繼狀態(tài)S4{Ac·AA·cAA·d}AcdS8S4S10S5{Bc·BB·cBB·d}BcdS9S5S11S6{EaA·}#E

aAS12S7{EbB·}#E

bBS12S8{AcA·}#A

cAS121192023/12/17狀態(tài)項目集后繼符號后繼狀態(tài)S9{BcB·}#B

cBS12S10{Ad·}#A

dS12S11{Bd·}#B

dS12S12{}

根據(jù)狀態(tài)描述序列和分析表的構(gòu)造規(guī)則得到的LR(0)分析表如下：1202023/12/17狀態(tài)ACTIONGOTOabcd#EABS0S2S31S1accS2S4S106S3S5S117S4S4S108S5S5S119S6r1r1r1r1r1S7r2r2r2r2r2S8r3r3r3r3r3S9r5r5r5r5r5S10r4r4r4r4r4S11r6r6r6r6r61212023/12/17狀態(tài)棧符號棧產(chǎn)生式輸入符actiongoto說明S0#bccd#S3b和S3進棧S0S3#bccd#S5c和S5進棧S0S3S5#bccd#S5c和S5進棧S0S3S5S5#bccd#S11d和S11進棧S0S3S5S5S11#bccdBd#r69d和S11退棧B和S9進棧S0S3S5S5S9#bccBBcB#r59…S0S3S5S9#bcBBcB#r57…S0S3S7#bBE

bB#r21…S0S1#E#acc接受對于輸入串#bccd#的分析過程如下：1222023/12/175.5SLR（1）分析

SLR(1)分析表的構(gòu)造1、問題的提出：只有當(dāng)一個文法G是LR(0)文法，即G的每一個狀態(tài)項目集相容時，才能構(gòu)造出LR(0)分析表；由于大多數(shù)適用的程序設(shè)計語言的文法不能滿足LR(0)文法的條件，因此本節(jié)將介紹對于LR(0)規(guī)范族中沖突的項目集（狀態(tài)）用向前查看一個符號的辦法進得處理，以解決沖突。因為只對有沖突的狀態(tài)才向前查看一個符號，以確定做那種動作，因而稱這種分析方法為簡單的LR(1)分析法，用SLR(1)表示。1232023/12/17文法G為：(0)S’SSrDDD,iDi狀態(tài)描述序列見下表：狀態(tài)項目集后繼符號后繼狀態(tài)S0S’·SS·rDSrS1S2S1S’

S·#S’

SS71242023/12/17S2S

r·DD·D,iD·iDDiS3S3S4S3S

rD