第五章語法自底向上方法

1、主要內(nèi)容主要內(nèi)容l自底向上分析的基本思想自底向上分析的基本思想l簡單優(yōu)先分析方法簡單優(yōu)先分析方法lLRLR類分析方法類分析方法基本思想基本思想 從待分析的符號串開始，自左向右進(jìn)行從待分析的符號串開始，自左向右進(jìn)行掃描，自下而上進(jìn)行分析，通過反復(fù)查找當(dāng)前句型掃描，自下而上進(jìn)行分析，通過反復(fù)查找當(dāng)前句型的句柄，并使用產(chǎn)生式規(guī)則將找到的句柄歸約為相的句柄，并使用產(chǎn)生式規(guī)則將找到的句柄歸約為相應(yīng)產(chǎn)生式的左部非終極符，直到將輸入串歸約為文應(yīng)產(chǎn)生式的左部非終極符，直到將輸入串歸約為文法的開始符。法的開始符。( (移入移入- -歸約分析歸約分析) )兩種分析方法兩種分析方法 簡單優(yōu)先和簡單優(yōu)先和LRLR類分

2、析方法類分析方法5.1 自底向上語法分析方法介紹自底向上語法分析方法介紹l例：例：S aAcBe 1 A b 2 A Ab 3 B d 4l輸入流：輸入流：abbcde。l規(guī)范推導(dǎo)過程為：規(guī)范推導(dǎo)過程為： 逆過程逆過程: :( (符號棧，輸入流符號棧，輸入流) )( -, abbcde)( -, abbcde)(a,bbcde)(a,bbcde)(a(ab b,bcde) ,bcde) (aA,bcde)(aA,bcde)(a(aAbAb,cde),cde)(aA,cde)(aA,cde)(aAc,de)(aAc,de)(aAc(aAcd d,e),e)(aAcB,e)(aAcB,e)( (a

3、AcBeaAcBe,-),-)(S,-)(S,-) S S aAcBeaAcBe11 aAc aAcd d44e e11 a aAbAb33cdcd44e e11 a ab b22b b33cdcd44e e11一種一種shift-reduce分析方法分析方法根據(jù)文法符號的優(yōu)先關(guān)系確定句柄根據(jù)文法符號的優(yōu)先關(guān)系確定句柄文法符號的優(yōu)先關(guān)系的確定文法符號的優(yōu)先關(guān)系的確定X X Y Y ：當(dāng)且僅當(dāng)存在一個產(chǎn)生式當(dāng)且僅當(dāng)存在一個產(chǎn)生式AXYAXYX X Y Y ：當(dāng)且僅當(dāng)存在一個產(chǎn)生式當(dāng)且僅當(dāng)存在一個產(chǎn)生式AXBAXB 并有并有B B+ +YY。X X Y Y ：當(dāng)且僅當(dāng)存在一個產(chǎn)生式當(dāng)且僅當(dāng)存在一個

4、產(chǎn)生式ABCABC 并有并有B B+ +XX，C C* *YY。 文法文法G G為為簡單優(yōu)先文法簡單優(yōu)先文法如果滿足：如果滿足： 對于任意兩個語法符號對于任意兩個語法符號X X和和Y Y，至多成立一種至多成立一種 優(yōu)先關(guān)系；優(yōu)先關(guān)系； 任意兩個產(chǎn)生式都具有不同的右部。任意兩個產(chǎn)生式都具有不同的右部。 FIRST(W) =S | W + S，S (VN VT) LAST(W) =S | W + S，S (VN VT) 若有若有USiSj: 則有則有Si Sj ;若有若有USiW:任任Sj FIRST(W),有有Si Sj若有若有UVW:任任Si LAST(V), Sj (FIRST(W) W)則

5、有則有Si Sj 輸入流的開始和結(jié)束標(biāo)志輸入流的開始和結(jié)束標(biāo)志 ，文法的開始符為，文法的開始符為Z，S FIRST(Z),有有# S，; 且且 ZS LAST(Z)，有有S #，; 且且Z 優(yōu)先關(guān)系矩陣優(yōu)先關(guān)系矩陣 一個文法的全部優(yōu)先關(guān)系可以用矩陣一個文法的全部優(yōu)先關(guān)系可以用矩陣來表示，稱作優(yōu)先關(guān)系矩陣。來表示，稱作優(yōu)先關(guān)系矩陣。l 例：例：l Z bMbl M a l M (Ll L Ma)#)a(bLMZ#)a(bLMZ)a L )bM ( a a ( bLMZFIRSTFIRST LASTLAST l定理定理：設(shè)設(shè)X1XiXi+1XjXn是一個句型，若有是一個句型，若有Xi Xi+1 X

6、i+2 Xj-1 Xj Xj+1則則Xi+1Xi+2Xj-1Xj一定是該句型的簡單短語。一定是該句型的簡單短語。l結(jié)論：結(jié)論： 用來確定句柄的頭；用來確定句柄的頭； 用來確定句柄用來確定句柄的內(nèi)部；的內(nèi)部； 用來確定句柄的結(jié)束。用來確定句柄的結(jié)束。l找第一個使找第一個使Sj Sj+1的的Sj。l從從Sj開始往前開始往前(左左)找第一個使找第一個使Si-1 Si的的Si。l用用SiSi+1Sj去查產(chǎn)生式的右部，并用相應(yīng)去查產(chǎn)生式的右部，并用相應(yīng)的左部符號代替句柄的左部符號代替句柄SiSi+1Sj (歸約歸約) 。l重復(fù)上述過程，直至輸入符結(jié)束。如果歸重復(fù)上述過程，直至輸入符結(jié)束。如果歸約出文法的

7、開始符號則成功。否則失敗。約出文法的開始符號則成功。否則失敗。符號棧符號棧 關(guān)系關(guān)系 輸入流輸入流 # b ( a a ) b # b ( a a ) b # b ( a a ) b # b ( a a ) b # b ( M a ) b # b ( M a ) b # b ( M a ) b # b ( L b # b M b # b M b # Z # 規(guī)范句型：規(guī)范句型：用最右推導(dǎo)導(dǎo)出的句型用最右推導(dǎo)導(dǎo)出的句型(也稱右句也稱右句型）。型）。 規(guī)范前綴：規(guī)范前綴：若存在規(guī)范句型若存在規(guī)范句型，且，且 是終極符是終極符串或空串，則稱串或空串，則稱 為規(guī)范前綴。為規(guī)范前綴。 規(guī)范活前綴：規(guī)范活

8、前綴：若規(guī)范前綴若規(guī)范前綴 不含句柄或含一個不含句柄或含一個句柄并且具有形式句柄并且具有形式 =( 是句柄是句柄)，則稱規(guī)范，則稱規(guī)范前綴前綴 為規(guī)范活前綴為規(guī)范活前綴(簡稱活前綴）。簡稱活前綴）。 歸約規(guī)范活前綴：歸約規(guī)范活前綴：若活前綴若活前綴 是含句柄的活前是含句柄的活前綴，即有綴，即有 =，且，且 是句柄，則稱活前綴是句柄，則稱活前綴 為歸為歸約規(guī)范活前綴（簡稱歸約活前綴）。約規(guī)范活前綴（簡稱歸約活前綴）。l活前綴的描述性定義：活前綴的描述性定義：形成可歸前綴之形成可歸前綴之前，包括可歸前綴在內(nèi)所有規(guī)范句型的前，包括可歸前綴在內(nèi)所有規(guī)范句型的前綴都稱為活前綴。前綴都稱為活前綴。l活前綴

9、活前綴 為一個或若干規(guī)范句型的前綴。為一個或若干規(guī)范句型的前綴。l在規(guī)范歸約過程中的任何時刻已分析過在規(guī)范歸約過程中的任何時刻已分析過的部分，即在分析棧（符號棧）中的符的部分，即在分析棧（符號棧）中的符號串均為規(guī)范句型的活前綴，表明輸入號串均為規(guī)范句型的活前綴，表明輸入串的已被分析過的部分是該文法某規(guī)范串的已被分析過的部分是該文法某規(guī)范句型的一個正確部分。句型的一個正確部分。l線性正則式：線性正則式：不含不含*符號的正則表達(dá)式符號的正則表達(dá)式lLRSM：(Linear Regular States Machine)(1)從從LRSM可構(gòu)造出恰好接受給定所有正可構(gòu)造出恰好接受給定所有正 則式的確

10、定自動機(jī)則式的確定自動機(jī)DA；(2)從從LRSM的終止?fàn)顟B(tài)可判定接受的是哪的終止?fàn)顟B(tài)可判定接受的是哪 個正則式；個正則式；(3)從從LRSM的狀態(tài)可判定一個正則式是不的狀態(tài)可判定一個正則式是不 是另一正則式的前綴。是另一正則式的前綴。 l項目項目：假設(shè)：假設(shè)P是一個正則式，則我們稱形是一個正則式，則我們稱形如如P的表示為項目，其中的表示為項目，其中P是正則式編號。是正則式編號。其中黑點(diǎn)可出現(xiàn)于任何位置上。其中黑點(diǎn)可出現(xiàn)于任何位置上。 l項目集項目集：用：用IS表示表示lIS(X) ： SubItems(IS,X)= XP|X P IS,X SymbSet 簡記為簡記為IS(X) 假設(shè)有線性正則

11、項集假設(shè)有線性正則項集: :IS = IS = abd1,abd1, abc2,abc2, bc3,debc3,de 4,4, de de c5,c5, 則有則有 ：ISIS(a)(a) = a = a bd1, abd1, a bc2 bc2 ISIS(b)(b) = b= b c3 c3 ISIS(c)(c) = dec = dec 4 4 給定正則式集給定正則式集 1 1, , 2 2, n n ：構(gòu)造初始項目集構(gòu)造初始項目集ISIS0 0=1 11,.,1,.,n nnn，并給并給ISIS0 0標(biāo)上標(biāo)上NO(NO(表示未處理）。表示未處理）。從已構(gòu)造的從已構(gòu)造的LRSMLRSM部分圖選

12、擇被標(biāo)為部分圖選擇被標(biāo)為NONO的任一項目集的任一項目集ISISi i，并做下面動作：并做下面動作： 1 1 對每個符號對每個符號X X SymbSetSymbSet： 若若ISISi iX X非空，給非空，給ISISi iX X標(biāo)上標(biāo)上NONO，并在并在ISISi i和和ISISi iX X之間之間 畫有向畫有向X X邊邊: :ISISi i ISISi iX X。 2 2 給給ISISi i標(biāo)上標(biāo)上OKOK。 重復(fù)上述步驟二，直至在重復(fù)上述步驟二，直至在LRSMLRSM中沒有被標(biāo)記為中沒有被標(biāo)記為NONO的的 狀態(tài)（項目集）節(jié)點(diǎn)為止。狀態(tài)（項目集）節(jié)點(diǎn)為止。 abdcdbecdabc1ab

13、c1abd2abd2 ad3 ad3 bec4bec4bed5bed5S S0 0a abc1bc1a abd2bd2 a ad3 d3 S S1 1=S=S0 0a aababc1c1ababd2d2S S3 3b bec4ec4b bed5ed5S S2 2bebec4c4bebed5d5S S5 5abcabc11S S6 6abdabd22S S7 7adad33S S4 4becbec44S S8 8bedbed55S S9 9正則式到正則式到LRSMLRSM的轉(zhuǎn)換例的轉(zhuǎn)換例l展望符展望符：Lookup(S)Lookup(S)l有效前綴集有效前綴集 Prefix(S)Prefix(S

14、)l狀態(tài)狀態(tài)SiSi中的項目中的項目 PP表示表示 部分已被輸部分已被輸入，而且是入，而且是SiSi的前綴的后綴，的前綴的后綴， 表示待輸表示待輸入部分。入部分。l可構(gòu)造接受給定正則式集合的可構(gòu)造接受給定正則式集合的DADAl嚴(yán)格前綴：嚴(yán)格前綴：某狀態(tài)中既含有定位點(diǎn)在尾處某狀態(tài)中既含有定位點(diǎn)在尾處的項目又含有定位點(diǎn)不在尾處的項目，則的項目又含有定位點(diǎn)不在尾處的項目，則一個正則式是另一個正則式的嚴(yán)格前綴。一個正則式是另一個正則式的嚴(yán)格前綴。 開始符產(chǎn)生式的右部是歸約活前綴。開始符產(chǎn)生式的右部是歸約活前綴。 如果如果 A A 是歸約活前綴，且是歸約活前綴，且AA 是產(chǎn)生式，是產(chǎn)生式， 則則也是歸約

15、活前綴。也是歸約活前綴。 任何歸約活前綴，都可按上述方式被派生。任何歸約活前綴，都可按上述方式被派生。l 設(shè)文法開始符的產(chǎn)生式是：設(shè)文法開始符的產(chǎn)生式是： S S 1 1| | 2 2| n n RPSRPSG G= 1 1, n n | | A ARPSRPSG G,A,AP P + 識別規(guī)約活前綴的識別規(guī)約活前綴的LRSMLRSM的構(gòu)造的構(gòu)造b 例有文法例有文法GS: S aAc1 A Abb2 A b3 可歸前綴集：可歸前綴集： aAcaAc aAbb aAbb ab ab Y LR(0) LR(0)項目：項目：若若AA是產(chǎn)生式，是產(chǎn)生式， 則稱則稱AA為為LR(0)LR(0)項目項目(

16、 (簡稱項目），也簡稱項目），也 寫作寫作 pp形式。形式。Y 項目集的投影：項目集的投影：假設(shè)假設(shè)ISIS是是LR(0)LR(0)項目集，則項目集，則 稱下面稱下面ISIS(X)(X) 為為ISIS關(guān)于關(guān)于X X的投影集：的投影集： ISIS(X)(X) = A = A X X |A |AX XIS,IS, X X (V(VT T V VN N).).Y 項目集的閉包：項目集的閉包：假設(shè)假設(shè)ISIS是是LR(0)LR(0)項目集，則項目集，則 稱下面稱下面CLOSURE(IS)CLOSURE(IS)為為ISIS的閉包集：的閉包集： CLOSURE(IS)= IS CLOSURE(IS)= I

17、S A A | Y | YA ACLOSURE(IS)CLOSURE(IS) A A 是產(chǎn)生式是產(chǎn)生式 Z 歸約活前綴的性質(zhì)：若歸約活前綴的性質(zhì)：若 A A 是歸約活前是歸約活前 綴，綴，AA 是產(chǎn)生式，則是產(chǎn)生式，則也是歸約活也是歸約活 前綴。前綴。 Z 活前綴狀態(tài)機(jī)性質(zhì)：若有活前綴狀態(tài)機(jī)性質(zhì)：若有 Prefix(ISPrefix(ISi i ) )，且且AAISISi i ，則則 是歸約活前綴。是歸約活前綴。 v 若有若有 Prefix(ISPrefix(ISi i ) )，YYA AISISi i ，則則 根據(jù)性質(zhì)根據(jù)性質(zhì)2(2(活前綴狀態(tài)機(jī)的性質(zhì)），活前綴狀態(tài)機(jī)的性質(zhì)）， A A 是歸

18、約活前綴。再根據(jù)派生原理，若是歸約活前綴。再根據(jù)派生原理，若 AA 是是A A的產(chǎn)生式，則的產(chǎn)生式，則也是歸約活前綴。也是歸約活前綴。v 構(gòu)造構(gòu)造LRSMLRSM的思想：的思想： 如果在狀態(tài)項目集如果在狀態(tài)項目集ISISi i 中有項目中有項目AAB B ， 且且BB 是是B B的產(chǎn)生式，則在的產(chǎn)生式，則在ISISi i 中增加項目中增加項目 B B；對于對于ISISi i 這個過程繼續(xù)到不可再擴(kuò)這個過程繼續(xù)到不可再擴(kuò) 充為止。充為止。 u構(gòu)造初始狀態(tài)構(gòu)造初始狀態(tài)ISIS0 0：ISIS0 0=CLOSURE(Z=CLOSURE(Z S)S)，并給并給ISIS0 0標(biāo)標(biāo)上上NONO。u從已構(gòu)造

19、的從已構(gòu)造的LRSMLRSM部分圖選擇被標(biāo)為部分圖選擇被標(biāo)為NONO的任一狀態(tài)的任一狀態(tài)ISIS，并做并做 1 1 對每個符號對每個符號X X V VT T V VN N，做下面動作：做下面動作： 1) 1) 令令I(lǐng)SISj j = CLOSURE( IS= CLOSURE( IS(X)(X) )，若非空。若非空。 2) 2) 若在若在LRSMLRSM部分圖中已有部分圖中已有ISISk k與與ISISj j有相同項目有相同項目 集，則令集，則令m=km=k；否則構(gòu)造否則構(gòu)造ISISj j的狀態(tài)點(diǎn)的狀態(tài)點(diǎn)ISISj j， 并給并給ISISj j標(biāo)上標(biāo)上NONO，同時令同時令m=jm=j。 3)

20、3) 在在ISIS和和ISISm m之間畫有向之間畫有向X X邊：邊：IS IS ISISm m 。 2 2 給給ISIS標(biāo)上標(biāo)上OKOK。u重復(fù)上一步驟，直至沒有被標(biāo)記為重復(fù)上一步驟，直至沒有被標(biāo)記為NONO的狀態(tài)節(jié)點(diǎn)為止。的狀態(tài)節(jié)點(diǎn)為止。xk 例：構(gòu)造例：構(gòu)造LR(0)狀態(tài)機(jī)狀態(tài)機(jī) S E $ E E + T E T T id T ( E )0 S E $ E E+T E T T id T ( E )1 SE $ EE +T 5 Tid 3 EE+ T T id T (E) 4 EE+T 9 ET 6 T( E) E E+T E T T id T ( E )7 T(E ) EE +T 8

21、T(E) TT(idETid)E+id(G GE E的的LRSMLRSM+2 SE $ $Z LRSM LRSM給出了所有的可歸活前綴給出了所有的可歸活前綴Z LRSM LRSM中的每個狀態(tài)將對應(yīng)一個飽和項目集：中的每個狀態(tài)將對應(yīng)一個飽和項目集： （1 1）其中一部分是由先驅(qū)狀態(tài)分出來）其中一部分是由先驅(qū)狀態(tài)分出來 ( (稱為基本項目稱為基本項目) )； （2 2）一部分則是由基本項目擴(kuò)展出來的）一部分則是由基本項目擴(kuò)展出來的 ( (稱為擴(kuò)展項目或派生項目稱為擴(kuò)展項目或派生項目) )。派生部。派生部 分項目的特點(diǎn)是其中的分項目的特點(diǎn)是其中的“ ”出現(xiàn)在出現(xiàn)在產(chǎn)產(chǎn) 生式右部的最左側(cè)。生式右部的最

22、左側(cè)。Y 形如形如A A PP的項目稱為的項目稱為歸約型項目歸約型項目Y 形如形如AA PP的項目稱為的項目稱為移入型項目移入型項目Y 移入歸約沖突移入歸約沖突Y 歸約歸約沖突歸約歸約沖突Y LRSMLRSM不能直接用于不能直接用于LRLR分析分析Y LRSMLRSM提供的信息：提供的信息： （1 1）合法性檢查信息）合法性檢查信息 AAa a （2 2）移入）移入/ /歸約信息歸約信息 AAa a ； AA （3 3）移入）移入/ /歸約后的轉(zhuǎn)向狀態(tài)信息歸約后的轉(zhuǎn)向狀態(tài)信息#X1X2 Xk XtSi0Si1Si2 Sik Sit aiai+1an #移入動作：設(shè)移入動作：設(shè)Sit的的ai輸入

23、邊所指向的狀態(tài)為輸入邊所指向的狀態(tài)為S*#X1X2 Xk XtSi0Si1Si2 Sik SitaiS*歸約動作：設(shè)按歸約動作：設(shè)按AXAXk+1k+1X Xk+2k+2XXt t進(jìn)行歸約，則首先歸約為進(jìn)行歸約，則首先歸約為A AS Sikik的的A A輸出邊所指向的狀態(tài)設(shè)為輸出邊所指向的狀態(tài)設(shè)為S S* *，則格局變?yōu)椋簞t格局變?yōu)椋?X1X2XkSi0Si1Si2SikAS*設(shè)當(dāng)前格局是：設(shè)當(dāng)前格局是：#X1X2XkSi0Si1Si2SikAOutputOutputStackStack# #a an na ai ia a1 1LRLR分析驅(qū)動器分析驅(qū)動器gotoactionInputInpu

24、tS St tX Xt t 1 LR(0)分析分析lActionAction矩陣：行代表狀態(tài)，列代表輸入矩陣：行代表狀態(tài)，列代表輸入符，而矩陣元素則表示相應(yīng)的分析動作：符，而矩陣元素則表示相應(yīng)的分析動作：Shift / Reduce / Accept / ErrorShift / Reduce / Accept / Error 。lGoToGoTo矩陣：行代表狀態(tài)，而列則代表語矩陣：行代表狀態(tài)，而列則代表語法符號（非終極符，終極符），而矩陣法符號（非終極符，終極符），而矩陣元素則表示移入或歸約后的轉(zhuǎn)向狀態(tài)。元素則表示移入或歸約后的轉(zhuǎn)向狀態(tài)。l定義定義 若若ISIS是一個是一個LR(0)LR(0

25、)項目集，項目集，X X是一個是一個文法符號，函數(shù)文法符號，函數(shù)GOGO（IS, XIS, X）定義為）定義為GOGO（IS, XIS, X）=CLOSURE=CLOSURE（ISIS(X)(X)），其中），其中ISIS(X)(X)為為LR(0)LR(0)項目集項目集ISIS的投影。的投影。 假設(shè)假設(shè)ISISk k為為LR(0)LR(0)項目集，則項目集，則 l若若A Aa aISISk k，且，且GO(ISGO(ISk k, a)= IS, a)= ISi i，a a V VT T，則，則action(ISaction(ISk k, a)=S, a)=Si i，表示把狀態(tài)，表示把狀態(tài)ISIS

26、i i和展望符和展望符a a入棧。入棧。l若若A AISISk k，則對任意，則對任意a a V VT T #，令，令action(ISaction(ISk k, , a)=Ra)=Rj j，其中產(chǎn)生式，其中產(chǎn)生式A A 的編號為的編號為j j，表示用編號為，表示用編號為j j的產(chǎn)生式進(jìn)行歸約。的產(chǎn)生式進(jìn)行歸約。l若若Z ZISISk k，且，且Z Z為拓廣產(chǎn)生式的左部非終極符，則為拓廣產(chǎn)生式的左部非終極符，則action(ISaction(ISk k, #)=Accept, #)=Accept。l若若GO(ISGO(ISk k, A)=IS, A)=ISi i，A A V VN N，則，則g

27、oto(ISgoto(ISk k, A)=i, A)=i。l其它情形，則其它情形，則Error(n)Error(n)，表示出錯標(biāo)志，也可不填。，表示出錯標(biāo)志，也可不填。文法如下：文法如下：S E $E E+T | TT id | (E)$ $+ +idid( () )# #E ET TS S0 0S S5 5S S6 61 19 9S S1 1S S2 2S S3 3S S2 2AccAccS S3 3S S5 5S S6 64 4S S4 4R2 R2R2R2R2R2S S5 5R4R4R4R4R4R4S S6 6S S5 5S S6 67 79 9S S7 7S S3 3S S8 8S S

28、8 8R5R5R5R5R5R4S S9 9R3R3R3R3R3R3GoToGoTo表表ActionAction表表首先置狀態(tài)棧、符號棧和輸入流的開始格局為：首先置狀態(tài)棧、符號棧和輸入流的開始格局為：（#S1,#,a1a2an#），則：），則：z若當(dāng)前格局為（若當(dāng)前格局為（#S1S2Sn,#X1X2Xn, aiai+1an#），且），且action(Sn, ai)=Sj，ai VT，則，則ai入符號棧，第入符號棧，第j個狀態(tài)個狀態(tài)Sj入狀入狀態(tài)棧。即移入后的格局變?yōu)椋簯B(tài)棧。即移入后的格局變?yōu)椋海?S1S2Sn Sj,#X1X2Xnai,ai+1an#）z若當(dāng)前格局為（若當(dāng)前格局為（#S1S2Sn

29、,#X1X2Xn, aiai+1an#），且），且action(ISn, a)=Rj，a VT #，則按照第，則按照第j個產(chǎn)生式進(jìn)行歸約，個產(chǎn)生式進(jìn)行歸約，符號棧和狀態(tài)棧相應(yīng)元素退棧，歸約后的文法符號入棧。符號棧和狀態(tài)棧相應(yīng)元素退棧，歸約后的文法符號入棧。假設(shè)第假設(shè)第j個產(chǎn)生式為個產(chǎn)生式為A ，k=| | ( =Xn-k+1Xn)，則歸約后，則歸約后的格局變?yōu)椋旱母窬肿優(yōu)椋海?S1S2Sn-kS,#X1X2Xn-kA,aiai+1an#）其中其中S=goto(Sn-k, A)。z若狀態(tài)棧的棧頂狀態(tài)為若狀態(tài)棧的棧頂狀態(tài)為Si，輸入流當(dāng)前值為，輸入流當(dāng)前值為#，且，且action(Si, #)=A

30、ccept，則分析成功。，則分析成功。z若狀態(tài)棧的棧頂狀態(tài)為若狀態(tài)棧的棧頂狀態(tài)為Si，輸入流當(dāng)前值為，輸入流當(dāng)前值為a，且，且action(Si, a)=Error或空，則轉(zhuǎn)向出錯處理程序?；蚩?，則轉(zhuǎn)向出錯處理程序。 狀態(tài)棧狀態(tài)棧 符號棧符號棧 輸入串輸入串 Action Goto0 id+id$# shift 505 id +id$# reduce4 909 T +id$# reduce3 101 E +id$# shift 3013 E+ id$# shift 50135 E+id $# reduce4 40134 E+T $# reduce2 101 E $# shift 2012 E$

31、 # accept id+id$ id+id$z 文法文法G G： Z aAc1 Z aAc1 A bB 2 | ba3A bB 2 | ba3 B dB 4 | e 5 B dB 4 | e 5 構(gòu)造文法的構(gòu)造文法的LR(0)LR(0)狀態(tài)機(jī)，狀態(tài)機(jī)，ActionAction表和表和 goto goto表，并給出符號串表，并給出符號串a(chǎn)bdecabdec的的LR(0)LR(0) 分析過程。分析過程。+ SLR(1)SLR(1)分析方法分析方法ZLR(0)方法對文法的要求嚴(yán)格。方法對文法的要求嚴(yán)格。ZLR(0)方法容易出現(xiàn)沖突狀態(tài)。方法容易出現(xiàn)沖突狀態(tài)。一個文法例一個文法例: : lG GE

32、E: SE $ : SE $ 1 1lEE + T 2EE + T 2lET ET 3 3lTT TT P 4 P 4 l TP TP 5 5lPid Pid 6 6l P( E ) 7P( E ) 7 圖圖4.5.5.3 G E 的的LRSM0 + +E EP Pidid$ $+ +P Pidid( (T TT Tidid( ( ididE E( (P P ) ) 4 4 E T E T T T T T P P 7 7 P id P id 5 5 E E + E E + T T T T T T P P T T P P P P id id P P (E) (E) 3 3 T P T P 4 4

33、 S E S E $ $ E E E E + T + T 1 1 S S E $ E $ 11 E E E+T E+T 2 2 E E T T 3 3 T T T T P P 4 4 T T P P 5 5 P P id id 6 6 P P (E) (E) 7 7 0 0 T T T T P P P P id id P P (E) (E) 8 8 T T T T * * P P 9 9 E E+T E E+T T T T T P P 11 11 P (E P (E ) ) E E E E +T +T 12 12 P(E) P(E) 10 10P P( (T T P ( P ( E ) E )

34、 E E E+T E+T E E T T T T T T P P T T P P P P id id P P (E) (E) 6 6 7 7 8 8 S E $ S E $ 2 2如果某個狀態(tài)有如下項目集：如果某個狀態(tài)有如下項目集： A , B , D d ，則存在則存在著歸約著歸約-歸約，移入歸約，移入-歸約沖突歸約沖突 l若用若用A 歸約，則當(dāng)前輸入符應(yīng)在歸約，則當(dāng)前輸入符應(yīng)在A的的Follow集中集中 l若用若用B 歸約，則當(dāng)前輸入符應(yīng)在歸約，則當(dāng)前輸入符應(yīng)在B 的的Follow集集 l若移入，則當(dāng)前輸入符應(yīng)為若移入，則當(dāng)前輸入符應(yīng)為d。lLRSM0中存在著狀態(tài)中存在著狀態(tài) A1 1 ，

35、An n ， B1 1 a1r1，Bm m amrm則集合：則集合： Follow(A1)、Follow(An)、a1,am 兩兩相交為空兩兩相交為空假設(shè)假設(shè)ISk為為LR(0)項目集，則項目集，則l若若AaISk，且，且GO(ISk, a)= ISi，a VT，則，則action(ISk, a)=Si，表示把狀態(tài)，表示把狀態(tài)ISi和展望符和展望符a入棧。入棧。l若若AISk，則對任意，則對任意a VT，a Follow(A)，令令action(ISk, a)=Rj，其中產(chǎn)生式，其中產(chǎn)生式A 的編號為的編號為j，表示用編號為表示用編號為j的產(chǎn)生式進(jìn)行歸約。的產(chǎn)生式進(jìn)行歸約。l若若ZISk，且，

36、且Z為拓廣產(chǎn)生式的左部非終極為拓廣產(chǎn)生式的左部非終極符，則符，則action(ISk, #)=Accept。l若若GO(ISk, A)=ISi，A VN，則，則goto(ISk, A)=i。l其它情形，則其它情形，則Error(n)，表示出錯標(biāo)志，也可不，表示出錯標(biāo)志，也可不填。填。 l對于一個文法，若按照上述算法構(gòu)造的分析表對于一個文法，若按照上述算法構(gòu)造的分析表中沒有沖突動作，則稱該文法為中沒有沖突動作，則稱該文法為SLR(1)文法。文法。l從定義可以看出從定義可以看出SLR(1)分析方法是用分析方法是用LR(0)項項目構(gòu)成的目構(gòu)成的LRSM0來識別活前綴，因此它們的來識別活前綴，因此它們

37、的狀態(tài)數(shù)相同，但是，由于狀態(tài)數(shù)相同，但是，由于LR(0)方法只看狀態(tài)方法只看狀態(tài)棧的內(nèi)容而棧的內(nèi)容而SLR(1)方法還要向前看展望符，因方法還要向前看展望符，因此此SLR(1)文法要比文法要比LR（0）文法廣。）文法廣。 圖圖4.5.5.3 G E 的的LRSM0 + +E EP Pidid$ $+ +P Pidid( (T TT Tidid( ( ididE E( (P P ) ) 4 4 E T E T T T T T P P 7 7 P id P id 5 5 E E + E E + T T T T T T P P T T P P P P id id P P (E) (E) 3 3 T

38、P T P 4 4 S E S E $ $ E E E E + T + T 1 1 S S E $ E $ 11 E E E+T E+T 2 2 E E T T 3 3 T T T T P P 4 4 T T P P 5 5 P P id id 6 6 P P (E) (E) 7 7 0 0 T T T T P P P P id id P P (E) (E) 8 8 T T T T * * P P 9 9 E E+T E E+T T T T T P P 11 11 P (E P (E ) ) E E E E +T +T 12 12 P(E) P(E) 10 10P P( (T T P ( P

39、( E ) E ) E E E+T E+T E E T T T T T T P P T T P P P P id id P P (E) (E) 6 6 7 7 8 8 S E $ S E $ 2 2lFollow(S)=#lFollow(E)=$,+,)lFollow(T)=$,+,),*lFollow(P) =$,+,),*# id()$ ETP0S5S6 1741S3S22Acc3S5S61144R5R5R5R55R6R6R6R66S5S6 12747R3S8R3R38S5S699R4R4R4R410R7R7R7R711R2S8R2R212S3S10State Action Lookahe

40、ad GoTol初始格局初始格局(#S0,#,a1a2an#)l若當(dāng)前格局為若當(dāng)前格局為 (#S0S1Sn,#X1X2Xn, aiai+1an#)，則，則若若action(Sn, ai)=Sk，則當(dāng)前格局變?yōu)椋?，則當(dāng)前格局變?yōu)椋?#S0S1Sn Sk,#X1X2Xnai, ai+1an#)若若action(Sn, ai)=Rp，則當(dāng)前格局變?yōu)椋?，則當(dāng)前格局變?yōu)椋?#S0Sn-kS,#X1X2Xn-kA,aiai+1an#)其中其中g(shù)oto(Sn-k, A)=S若若action(Sn, ai)=Accept，則成功，則成功l其它情形，出錯其它情形，出錯分析棧分析棧 符號棧符號棧 輸入串輸入串 分

41、析動作分析動作 轉(zhuǎn)向狀態(tài)轉(zhuǎn)向狀態(tài) 0 id id+id$# S50,5 id id+id$# R6 40,4 P id+id$# R5 70,7 T id+id$# S80,7,8 T id+id$# S50,7,8,5 T id +id$# R6 90,7,8,9 T P +id$# R4 70,7 T +id$# R3 10,1 E +id$# S30,1,3 E+ id$# S50,1,3,5 E+id $# R6 40,1,3,4 E+P $# R5 110,1,3,11 E+T $# R2 10,1 E $# S20,1,2 E$ # AcceptZSLR(1)和和LR(0)具有相同

42、的狀態(tài)機(jī)具有相同的狀態(tài)機(jī)ZLR(0)只看分析棧的內(nèi)容，不考慮當(dāng)前輸入符只看分析棧的內(nèi)容，不考慮當(dāng)前輸入符 SLR(1)考慮輸入符，用考慮輸入符，用follow集來解決沖突，集來解決沖突，因此因此SLR(1)要比要比LR(0)分析能力強(qiáng)分析能力強(qiáng) z 括號文法定義如下：括號文法定義如下： Z S$ Z S$ S (S) S | S (S) S | 構(gòu)造該文法的構(gòu)造該文法的SLR(1)SLR(1)分析表，并給出輸分析表，并給出輸入流入流( )( )( )( )$ $的的SLR(1)SLR(1)分析過程。分析過程。主要內(nèi)容：主要內(nèi)容：+ LR(1)LR(1)分析方法分析方法 Z E E (L,E)

43、E S L L,E L E S id S (S)Z EE(L,E)ESSidS (S)0E( L,E)S( S)L L,EL EE (L,E)E SS idS (S)1ES S(S )2(S狀態(tài)狀態(tài)2存在移入存在移入-歸約沖突歸約沖突ZLR(0)LR(0)方法不依賴輸入流，直接判定歸約，方法不依賴輸入流，直接判定歸約，容易出現(xiàn)沖突。容易出現(xiàn)沖突。ZSLR(1)SLR(1)方法簡單的把非終極符的方法簡單的把非終極符的followfollow集做集做為可歸約的依據(jù)，并不精確。為可歸約的依據(jù)，并不精確。Z一個非終極符在不同的位置上出現(xiàn)，它所允一個非終極符在不同的位置上出現(xiàn)，它所允許的后繼符是不同的。

44、許的后繼符是不同的。LR(1)LR(1)針對不同產(chǎn)生針對不同產(chǎn)生式上的非終極符，分別定義其后繼符集（展式上的非終極符，分別定義其后繼符集（展望符集望符集ReducelookupReducelookup），），減少了移入減少了移入/ /歸約歸約沖突。沖突。lLR(1)LR(1)項目：項目： AA, a , a 。LR(0)LR(0)項目及一個項目及一個V VT T #的展望符集合的展望符集合lIS:IS:LR(1)LR(1)項目集項目集lISIS(X)(X): : IS IS(X)(X) = A = A X X,a |A,a |AX X ,a,a IS IS lCLOSURE ( IS )CLO

45、SURE ( IS ) = IS = IS B B,b |A,b |AB B ,a,a CLOSURE(IS), CLOSURE(IS), B B 是產(chǎn)生式是產(chǎn)生式 , , b b First(First( a)a) lGOGO: :若若ISIS是一個是一個LR(1)LR(1)項目集，項目集，X X是一個文法符號是一個文法符號, ,則則GOGO（IS, XIS, X）=CLOSURE=CLOSURE（ISIS(X)(X)），），其中其中ISIS(X)(X)為為LR(1)LR(1)項目集項目集ISIS的投影的投影 l初始項目集：初始項目集：l ISS=CLOSURE( Z ISS=CLOSURE

46、( Z S, # )S, # )l若所有狀態(tài)都處理完，則結(jié)束若所有狀態(tài)都處理完，則結(jié)束l選一未處理完狀態(tài)選一未處理完狀態(tài)ISIS，對所有語法符號對所有語法符號l X X （V VT T V VN N #),#),求求ISISX X, ,令令l IS IS = CLOSURE(IS= CLOSURE(ISX X) )，若若ISIS不為空：不為空：l 若若ISIS為新狀態(tài)，則增加為新狀態(tài)，則增加IS ISIS IS, ,把把ISIS加加l 入入LRSMLRSM1 1中；否則為圖中某個狀態(tài)中；否則為圖中某個狀態(tài)ISISj j，則則在在ISISl 和和ISISj j之間增加一條轉(zhuǎn)換邊：之間增加一條轉(zhuǎn)換

47、邊：IS ISIS ISj jl轉(zhuǎn)到步驟轉(zhuǎn)到步驟2 2XXl 非非SLR(1)SLR(1)文法：文法： Z SZ S S L= R S L= R S R S R L aR L aR L b L b R L R L 0ZSSL=RSRLaRLbRL#= #= #1ZS #2SL =RRL #6SL= RR LLaRLb#7SL=R #3SR #4Lb =#10LaR #=5La RR LLaRLb# =# =# =# =11RL # =8La RR LLaRLb#9RL #12Lb #13LaR #SLabRb=RLRLabaaLRb假設(shè)假設(shè)ISk為為LR(1)項目集則：項目集則：l若若Z, #

48、 ISk，且，且Z為拓廣產(chǎn)生式的左部非終為拓廣產(chǎn)生式的左部非終極符，則極符，則action(ISk, #)=Accept。l若若A, a ISk，且產(chǎn)生式，且產(chǎn)生式A 的編號為的編號為j，則，則action(ISk, a)=Rj，表示用編號為，表示用編號為j的產(chǎn)生式進(jìn)行的產(chǎn)生式進(jìn)行歸約。歸約。l若若Aa , b ISk，且，且GO(ISk, a)=ISi，a VT，則則action(ISk, a)=Si，表示把狀態(tài)，表示把狀態(tài)ISi和展望符和展望符a入入棧。棧。l若若GO(ISk, A)= ISi，A VN，則，則goto(ISk, A)=i。l其它情形，則其它情形，則Error(n)，表示出

49、錯標(biāo)志，也可不，表示出錯標(biāo)志，也可不填。填。 l對于一個文法，若按照上述算法構(gòu)造的對于一個文法，若按照上述算法構(gòu)造的分析表中沒有沖突動作，則稱該文法為分析表中沒有沖突動作，則稱該文法為LR(1)文法。文法。R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62A1321S4S50RLS#=balLR(1)的驅(qū)動程序與的驅(qū)動程序與SLR(1)的驅(qū)動程序是的驅(qū)動程序是相同的，可共用一個。相同的，可共用一個。狀態(tài)棧狀態(tài)棧 符號棧符號棧 輸入串輸入串 Action GoToAction GoTo0 aab=b# S5 0,5

50、a ab=b# S50,5,5 aa b=b# S4 0,5,5,4 aab =b# R5 110,5,5,11 aaL =b# R6 100,5,5,10 aaR =b# R4 110,5,11 aL =b# R6 10 0,5,10 aR =b# R4 20,2 L =b# S60,2,6 L= b# S120,2,6,12 L=b # R5 9 0,2,6,9 L=L # R6 70,2,6,7 L=R # R2 10,1 S # Az設(shè)文法設(shè)文法GS為：為：SAS | A aA | b 證明證明GS是是LR(1)文法；構(gòu)造它的文法；構(gòu)造它的LR(1)分析表；給出符號串分析表；給出符號串

51、abab#的的分析過程分析過程它具有它具有SLR(1)SLR(1)的狀態(tài)數(shù)少的優(yōu)點(diǎn)和的狀態(tài)數(shù)少的優(yōu)點(diǎn)和LR(1)LR(1)的適用范圍廣的優(yōu)點(diǎn)。的適用范圍廣的優(yōu)點(diǎn)。 LALR(1)LALR(1)方法的功能介于方法的功能介于SLR(1)SLR(1)和和LR(1)LR(1)之間。之間。LALR(1)LALR(1)狀態(tài)機(jī)的狀態(tài)個數(shù)和狀態(tài)機(jī)的狀態(tài)個數(shù)和LR(0)LR(0)狀態(tài)狀態(tài)機(jī)的狀態(tài)個數(shù)相同，而其展望符則即不機(jī)的狀態(tài)個數(shù)相同，而其展望符則即不采用采用SLR(1)SLR(1)的的FollowFollow集方法，也不采用集方法，也不采用LR(1)LR(1)的完全精確法。的完全精確法。 LR(1)LR(1

52、)狀態(tài)機(jī)和狀態(tài)機(jī)和LR(0)LR(0)狀態(tài)機(jī)從它們所表狀態(tài)機(jī)從它們所表示的自動機(jī)角度來看是等價的示的自動機(jī)角度來看是等價的 ；自動機(jī)可通過合并等價狀態(tài)來減少狀態(tài)自動機(jī)可通過合并等價狀態(tài)來減少狀態(tài)個數(shù)。個數(shù)。 在在LR(1)LR(1)狀態(tài)機(jī)出現(xiàn)很多同心狀態(tài)，而狀態(tài)機(jī)出現(xiàn)很多同心狀態(tài)，而LALR(1)LALR(1)狀態(tài)機(jī)則不產(chǎn)生同心的狀態(tài)，狀態(tài)機(jī)則不產(chǎn)生同心的狀態(tài)， 從而大大減少狀態(tài)數(shù)，這就是從而大大減少狀態(tài)數(shù)，這就是LALR(1)LALR(1)和和LR(1)LR(1)的主要差別。的主要差別。 LALR(1)LALR(1)狀態(tài)機(jī)的定義方式：狀態(tài)機(jī)的定義方式：用用LR(1)LR(1)狀態(tài)機(jī)來定義；狀態(tài)機(jī)來定義；用用L