第五章語(yǔ)法自底向上方法

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

自底向上語(yǔ)法分析方法介紹例：SaAcBe[1] Ab[2] AAb[3]Bd[4]輸入流：abbcde。規(guī)范推導(dǎo)過(guò)程為：

逆過(guò)程:(符號(hào)棧，輸入流)(-,abbcde)(a,bbcde)(ab,bcde)(aA,bcde)(aAb,cde)(aA,cde)(aAc,de)(aAcd,e)(aAcB,e)(aAcBe,-)(S,-)SaAcBe[1]

aAcd[4]e[1]

aAb[3]cd[4]e[1]ab[2]b[3]cd[4]e[1]5.2簡(jiǎn)單優(yōu)先分析一種shift-reduce分析方法根據(jù)文法符號(hào)的優(yōu)先關(guān)系確定句柄文法符號(hào)的優(yōu)先關(guān)系的確定簡(jiǎn)單優(yōu)先分析中的三種關(guān)系XY：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式A→…XY…X?Y：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式A→…XB…

并有B+Y…。X?Y：當(dāng)且僅當(dāng)存在一個(gè)產(chǎn)生式A→…BC…

并有B+…X，C*Y…。

文法G為簡(jiǎn)單優(yōu)先文法如果滿足：

對(duì)于任意兩個(gè)語(yǔ)法符號(hào)X和Y，至多成立一種優(yōu)先關(guān)系；

任意兩個(gè)產(chǎn)生式都具有不同的右部。文法優(yōu)先關(guān)系的確定

FIRST(W)={S|W+S…，S(VNVT)}LAST(W)={S|W+…S，S(VNVT)}若有U…SiSj…:則有Si

Sj;若有U…SiW…:任SjFIRST(W),有Si?Sj若有U…VW…:任SiLAST(V),

Sj(FIRST(W){W})則有Si?Sj

輸入流的開(kāi)始和結(jié)束標(biāo)志‘?！?，文法的開(kāi)始符為Z，SFIRST(Z),有#?S，;且＃?ZSLAST(Z)，有S?

#，;且Z?＃優(yōu)先關(guān)系矩陣一個(gè)文法的全部?jī)?yōu)先關(guān)系可以用矩陣來(lái)表示，稱作優(yōu)先關(guān)系矩陣。

例：

ZbMbMaM(LLMa)#)a(bLMZ#)a(bLMZ)a

L)bM(aa(bLMZFIRST

LAST???????????????定理： 設(shè)X1…XiXi+1…Xj…Xn是一個(gè)句型，若有 Xi

?Xi+1

Xi+2

…Xj-1Xj

?Xj+1 則Xi+1Xi+2…Xj-1Xj一定是該句型的簡(jiǎn)單短語(yǔ)。結(jié)論：

?用來(lái)確定句柄的頭；用來(lái)確定句柄的內(nèi)部；?用來(lái)確定句柄的結(jié)束。簡(jiǎn)單優(yōu)先分析算法要點(diǎn)找第一個(gè)使Sj?Sj+1的Sj。從Sj開(kāi)始往前(左)找第一個(gè)使Si-1?Si的Si。用SiSi+1…Sj去查產(chǎn)生式的右部，并用相應(yīng)的左部符號(hào)代替句柄SiSi+1…Sj

(歸約)。重復(fù)上述過(guò)程，直至輸入符結(jié)束。如果歸約出文法的開(kāi)始符號(hào)則成功。否則失敗。簡(jiǎn)單優(yōu)先分析實(shí)例符號(hào)棧關(guān)系輸入流#?

b(aa)b##b?(aa)b##b(?aa)b##b(a?a)b##b(M

a)b##b(Ma)b##b(Ma)?b##b(L?b##bMb##bMb?##Z?#規(guī)范句型：用最右推導(dǎo)導(dǎo)出的句型(也稱右句型）。規(guī)范前綴：若存在規(guī)范句型，且是終極符串或空串，則稱為規(guī)范前綴。規(guī)范活前綴：若規(guī)范前綴不含句柄或含一個(gè)句柄并且具有形式=(是句柄)，則稱規(guī)范前綴為規(guī)范活前綴(簡(jiǎn)稱活前綴）。歸約規(guī)范活前綴：若活前綴是含句柄的活前綴，即有=，且是句柄，則稱活前綴為歸約規(guī)范活前綴（簡(jiǎn)稱歸約活前綴）。5.3LR類分析方法活前綴的描述性定義：形成可歸前綴之前，包括可歸前綴在內(nèi)所有規(guī)范句型的前綴都稱為活前綴?；钋熬Y為一個(gè)或若干規(guī)范句型的前綴。在規(guī)范歸約過(guò)程中的任何時(shí)刻已分析過(guò)的部分，即在分析棧（符號(hào)棧）中的符號(hào)串均為規(guī)范句型的活前綴，表明輸入串的已被分析過(guò)的部分是該文法某規(guī)范句型的一個(gè)正確部分。線性正則式狀態(tài)機(jī)－LRSM線性正則式：不含*符號(hào)的正則表達(dá)式LRSM：(LinearRegularStatesMachine) (1)從LRSM可構(gòu)造出恰好接受給定所有正則式的確定自動(dòng)機(jī)DA； (2)從LRSM的終止?fàn)顟B(tài)可判定接受的是哪個(gè)正則式； (3)從LRSM的狀態(tài)可判定一個(gè)正則式是不是另一正則式的前綴。

項(xiàng)目：假設(shè)[P]是一個(gè)正則式，則我們稱形如[P]的表示為項(xiàng)目，其中P是正則式編號(hào)。其中黑點(diǎn)可出現(xiàn)于任何位置上。項(xiàng)目集：用IS表示IS(X)：SubItems(IS,X)={X[P]|X[P]IS,XSymbSet}簡(jiǎn)記為IS(X)

假設(shè)有線性正則項(xiàng)集:IS={abd[1],abc[2],bc[3],de[4],dec[5]},

則有：IS(a)={abd[1],abc[2]}IS(b) ={bc[3]}IS(c)={dec[4]}線性正則式到LRSM的構(gòu)造給定正則式集{1,2,…n}：■構(gòu)造初始項(xiàng)目集IS0={1[1],...,n[n]}，并給IS0標(biāo)上NO(表示未處理）?！鰪囊褬?gòu)造的LRSM部分圖選擇被標(biāo)為NO的任一項(xiàng)目集ISi，并做下面動(dòng)作：[1]對(duì)每個(gè)符號(hào)XSymbSet：若ISiX非空，給ISiX標(biāo)上NO，并在ISi和ISiX之間畫有向X邊:ISi

→

ISiX。[2]給ISi標(biāo)上OK。■

重復(fù)上述步驟二，直至在LRSM中沒(méi)有被標(biāo)記為NO的狀態(tài)（項(xiàng)目集）節(jié)點(diǎn)為止。abdcdbecd?abc[1]?abd[2]?ad[3]?bec[4]?bed[5]S0a?bc[1]a?bd[2]a?d[3]S1=S0aab?c[1]ab?d[2]S3b?ec[4]b?ed[5]S2be?c[4]be?d[5]S5abc?[1]S6abd?[2]S7ad?[3]S4bec?[4]S8bed?[5]S9正則式到LRSM的轉(zhuǎn)換例LRSM的性質(zhì)展望符：Lookup(S)有效前綴集

Prefix(S)狀態(tài)Si中的項(xiàng)目?[P]表示部分已被輸入，而且是Si的前綴的后綴，表示待輸入部分?？蓸?gòu)造接受給定正則式集合的DA嚴(yán)格前綴：某狀態(tài)中既含有定位點(diǎn)在尾處的項(xiàng)目又含有定位點(diǎn)不在尾處的項(xiàng)目，則一個(gè)正則式是另一個(gè)正則式的嚴(yán)格前綴。派生定理

開(kāi)始符產(chǎn)生式的右部是歸約活前綴。如果A是歸約活前綴，且A→是產(chǎn)生式，則也是歸約活前綴。任何歸約活前綴，都可按上述方式被派生。設(shè)文法開(kāi)始符的產(chǎn)生式是： S→1|2|…|n

RPSG={1,…,n}{|ARPSG,A→P}識(shí)別規(guī)約活前綴的LRSM的構(gòu)造

例有文法G[S]: S→aAc[1] A→Abb[2] A→b[3]

可歸前綴集：

aAcaAbbabLR(0)項(xiàng)目：若A→是產(chǎn)生式，則稱A→為L(zhǎng)R(0)項(xiàng)目(簡(jiǎn)稱項(xiàng)目），也寫作[p]形式。項(xiàng)目集的投影：假設(shè)IS是LR(0)項(xiàng)目集，則稱下面IS(X)

為IS關(guān)于X的投影集：

IS(X)={A→X|A→XIS, X(VTVN)}.項(xiàng)目集的閉包：假設(shè)IS是LR(0)項(xiàng)目集，則稱下面CLOSURE(IS)為IS的閉包集：

CLOSURE(IS)=IS

{A→|Y→ACLOSURE(IS)A→是產(chǎn)生式}兩個(gè)重要的性質(zhì)歸約活前綴的性質(zhì)：若A是歸約活前綴，A→是產(chǎn)生式，則也是歸約活前綴?；钋熬Y狀態(tài)機(jī)性質(zhì)：若有

Prefix(ISi

)，且A→ISi

，則

是歸約活前綴。若有Prefix(ISi

)，Y→AISi

，則根據(jù)性質(zhì)2—(活前綴狀態(tài)機(jī)的性質(zhì)），

A是歸約活前綴。再根據(jù)派生原理，若

A→是A的產(chǎn)生式，則也是歸約活前綴。構(gòu)造LRSM的思想：

如果在狀態(tài)項(xiàng)目集ISi

中有項(xiàng)目A→B，且B→是B的產(chǎn)生式，則在ISi

中增加項(xiàng)目B→；對(duì)于ISi

這個(gè)過(guò)程繼續(xù)到不可再擴(kuò)充為止。

構(gòu)造LR(0)活前綴狀態(tài)機(jī)LRSM的算法要點(diǎn)

構(gòu)造初始狀態(tài)IS0：IS0=CLOSURE({Z→S})，并給IS0標(biāo)上NO。從已構(gòu)造的LRSM部分圖選擇被標(biāo)為NO的任一狀態(tài)IS，并做

[1]對(duì)每個(gè)符號(hào)XVTVN，做下面動(dòng)作：

1)令I(lǐng)Sj

=CLOSURE(IS(X))，若非空。2)若在LRSM部分圖中已有ISk與ISj有相同項(xiàng)目集，則令m=k；否則構(gòu)造ISj的狀態(tài)點(diǎn)ISj，

并給ISj標(biāo)上NO，同時(shí)令m=j。3)在IS和ISm之間畫有向X邊：IS

ISm

。

[2]給IS標(biāo)上OK。重復(fù)上一步驟，直至沒(méi)有被標(biāo)記為NO的狀態(tài)節(jié)點(diǎn)為止。x例：構(gòu)造LR(0)狀態(tài)機(jī)SE$EE+TETTidT(E)0

S→E$E→E+TE→TT→idT→(E)1

S→E$E→E+T

5

T→id

3

E→E+TT→idT→(E)

4

E→E+T

9

E→T

6

T→(E)E→E+TE→TT→idT→(E)7

T→(E)E→E+T

8

T→(E)

TT(idETid)E+id((GE的LRSM+2

S→E$

$LRSM給出了所有的可歸活前綴LRSM中的每個(gè)狀態(tài)將對(duì)應(yīng)一個(gè)飽和項(xiàng)目集：

（1）其中一部分是由先驅(qū)狀態(tài)分出來(lái)(稱為基本項(xiàng)目)；（2）一部分則是由基本項(xiàng)目擴(kuò)展出來(lái)的(稱為擴(kuò)展項(xiàng)目或派生項(xiàng)目)。派生部分項(xiàng)目的特點(diǎn)是其中的“”出現(xiàn)在產(chǎn)生式右部的最左側(cè)。形如A→?[P]的項(xiàng)目稱為歸約型項(xiàng)目形如A→?[P]的項(xiàng)目稱為移入型項(xiàng)目

移入－歸約沖突

歸約－歸約沖突

LRSM不能直接用于LR分析

LRSM提供的信息：（1）合法性檢查信息[A→a]

（2）移入/歸約信息[A→a]；[A→]

（3）移入/歸約后的轉(zhuǎn)向狀態(tài)信息#X1X2…Xk…XtSi0Si1Si2…Sik…Sitaiai+1…an#移入動(dòng)作：設(shè)Sit的ai輸入邊所指向的狀態(tài)為S*#X1X2…Xk…XtSi0Si1Si2…Sik…SitaiS*歸約動(dòng)作：設(shè)按A→Xk+1Xk+2…Xt進(jìn)行歸約，則首先歸約為ASik的A輸出邊所指向的狀態(tài)設(shè)為S*，則格局變?yōu)椋?X1X2…XkSi0Si1Si2…SikAS*設(shè)當(dāng)前格局是：#X1X2…XkSi0Si1Si2…SikALR分析模型OutputStack#an…ai…a1LR分析驅(qū)動(dòng)器gotoactionInputStXt……LR(0)分析LR分析表Action矩陣：行代表狀態(tài)，列代表輸入符，而矩陣元素則表示相應(yīng)的分析動(dòng)作：Shift/Reduce/Accept/Error。GoTo矩陣：行代表狀態(tài)，而列則代表語(yǔ)法符號(hào)（非終極符，終極符），而矩陣元素則表示移入或歸約后的轉(zhuǎn)向狀態(tài)。定義若IS是一個(gè)LR(0)項(xiàng)目集，X是一個(gè)文法符號(hào)，函數(shù)GO（IS,X）定義為 GO（IS,X）=CLOSURE（IS(X)），其中IS(X)為L(zhǎng)R(0)項(xiàng)目集IS的投影。

假設(shè)ISk為L(zhǎng)R(0)項(xiàng)目集，則若AaISk，且GO(ISk,a)=ISi，aVT，則action(ISk,a)=Si，表示把狀態(tài)ISi和展望符a入棧。若AISk，則對(duì)任意aVT{#}，令action(ISk,a)=Rj，其中產(chǎn)生式A的編號(hào)為j，表示用編號(hào)為j的產(chǎn)生式進(jìn)行歸約。若ZISk，且Z為拓廣產(chǎn)生式的左部非終極符，則action(ISk,#)=Accept。若GO(ISk,A)=ISi，AVN，則goto(ISk,A)=i。其它情形，則Error(n)，表示出錯(cuò)標(biāo)志，也可不填。LR(0)分析表的構(gòu)造LR(0)分析例文法如下： S→E$ E→E+T|T T→id|(E)$+id()#ETS0S5S619S1S2S3S2AccS3S5S64S4R2

R2R2R2R2R2S5R4R4R4R4R4R4S6S5S679S7S3S8S8R5R5R5R5R5R4S9R3R3R3R3R3R3GoTo表Action表LR(0)驅(qū)動(dòng)程序首先置狀態(tài)棧、符號(hào)棧和輸入流的開(kāi)始格局為： （#S1, #, a1a2…an#），則：若當(dāng)前格局為（#S1S2…Sn, #X1X2…Xn, aiai+1…an#），且action(Sn,ai)=Sj，aiVT，則ai入符號(hào)棧，第j個(gè)狀態(tài)Sj入狀態(tài)棧。即移入后的格局變?yōu)椋? （#S1S2…SnSj, #X1X2…Xnai, ai+1…an#）若當(dāng)前格局為（#S1S2…Sn, #X1X2…Xn, aiai+1…an#），且action(ISn,a)=Rj，aVT{#}，則按照第j個(gè)產(chǎn)生式進(jìn)行歸約，符號(hào)棧和狀態(tài)棧相應(yīng)元素退棧，歸約后的文法符號(hào)入棧。假設(shè)第j個(gè)產(chǎn)生式為A，k=||(=Xn-k+1…Xn)，則歸約后的格局變?yōu)椋? （#S1S2…Sn-kS, #X1X2…Xn-kA, aiai+1…an#） 其中S=goto(Sn-k,A)。若狀態(tài)棧的棧頂狀態(tài)為Si，輸入流當(dāng)前值為#，且action(Si,#)=Accept，則分析成功。若狀態(tài)棧的棧頂狀態(tài)為Si，輸入流當(dāng)前值為a，且action(Si,a)=Error或空，則轉(zhuǎn)向出錯(cuò)處理程序。

LR(0)分析實(shí)例狀態(tài)棧符號(hào)棧輸入串ActionGoto0id+id$#shift505id+id$#reduce4909T+id$#reduce3101E+id$#shift3013E+id$#shift50135E+id$#reduce440134E+T$#reduce2101E$#shift2012E$#accept

id+id$文法G：Z→aAc[1]

A→bB[2]|ba[3]B→dB[4]|e[5]

構(gòu)造文法的LR(0)狀態(tài)機(jī)，Action表和

goto表，并給出符號(hào)串a(chǎn)bdec的LR(0)

分析過(guò)程。

SLR(1)分析方法LR(0)分析方法的不足LR(0)方法對(duì)文法的要求嚴(yán)格。LR(0)方法容易出現(xiàn)沖突狀態(tài)。一個(gè)文法例:GE:S→E$ [1] E→E+T[2] E→T [3] T→TP[4] T→P [5] P→id [6] P→(E)[7]

圖

GE

的LRSM0+EPid$+Pid(TTid(

idE(P)

4

E→T

T→T

P7

P→id

5

E→E+T

T→TP

T→P

P→id

P→(E)

3

T→P

4

S→E$

E→E+T

1S→E$

[1]

E→E+T[2]E→T[3]T→TP[4]T→P[5]P→id[6]P→(E)[7]0T→T

P

P→id

P→(E)8

T→T*P

9

E→E+T

T→T

P

11

P→(E)

E→E+T

12

P→(E)

10P(T

P→(E)

E→E+T

E→T

T→TP

T→P

P→id

P→(E)

678

S→E$

2如果某個(gè)狀態(tài)有如下項(xiàng)目集：{A→

,B→

,D→

d}，則存在著歸約-歸約，移入-歸約沖突若用A→

歸約，則當(dāng)前輸入符應(yīng)在A的Follow集中若用B→

歸約，則當(dāng)前輸入符應(yīng)在B的Follow集若移入，則當(dāng)前輸入符應(yīng)為d。SLR(1)分析條件LRSM0中存在著狀態(tài){A1→1，…，An→n，B1→1

a1r1，…，Bm→

mamrm}則集合： Follow(A1)、…、Follow(An)、{a1,…,am}

兩兩相交為空SLR(1)分析表的構(gòu)造假設(shè)ISk為L(zhǎng)R(0)項(xiàng)目集，則若AaISk，且GO(ISk,a)=ISi，aVT，則action(ISk,a)=Si，表示把狀態(tài)ISi和展望符a入棧。若AISk，則對(duì)任意aVT，aFollow(A)，令action(ISk,a)=Rj，其中產(chǎn)生式A的編號(hào)為j，表示用編號(hào)為j的產(chǎn)生式進(jìn)行歸約。若ZISk，且Z為拓廣產(chǎn)生式的左部非終極符，則action(ISk,#)=Accept。若GO(ISk,A)=ISi，AVN，則goto(ISk,A)=i。其它情形，則Error(n)，表示出錯(cuò)標(biāo)志，也可不填。

SLR(1)文法定義對(duì)于一個(gè)文法，若按照上述算法構(gòu)造的分析表中沒(méi)有沖突動(dòng)作，則稱該文法為SLR(1)文法。從定義可以看出SLR(1)分析方法是用LR(0)項(xiàng)目構(gòu)成的LRSM0來(lái)識(shí)別活前綴，因此它們的狀態(tài)數(shù)相同，但是，由于LR(0)方法只看狀態(tài)棧的內(nèi)容而SLR(1)方法還要向前看展望符，因此SLR(1)文法要比LR（0）文法廣。

圖

GE

的LRSM0+EPid$+Pid(TTid(

idE(P)

4

E→T

T→T

P7

P→id

5

E→E+T

T→TP

T→P

P→id

P→(E)

3

T→P

4

S→E$

E→E+T

1S→E$

[1]

E→E+T[2]E→T[3]T→TP[4]T→P[5]P→id[6]P→(E)[7]0T→T

P

P→id

P→(E)8

T→T*P

9

E→E+T

T→T

P

11

P→(E)

E→E+T

12

P→(E)

10P(T

P→(E)

E→E+T

E→T

T→TP

T→P

P→id

P→(E)

678

S→E$

2Follow(S)={#}Follow(E)={$,+,)}Follow(T)={$,+,),*}Follow(P)={$,+,),*}#＋id()$ETP0S5S61741S3S22Acc3S5S61144R5R5R5R55R6R6R6R66S5S612747R3S8R3R38S5S699R4R4R4R410R7R7R7R711R2S8R2R212S3S10StateAction－Lookahead

GoToSLR(1)驅(qū)動(dòng)器初始格局(#S0, #, a1a2…an#)若當(dāng)前格局為(#S0S1…Sn, #X1X2…Xn,aiai+1…an#)，則若action(Sn,ai)=Sk，則當(dāng)前格局變?yōu)椋? (#S0S1…SnSk, #X1X2…Xnai,ai+1…an#)若action(Sn,ai)=Rp，則當(dāng)前格局變?yōu)椋? (#S0…Sn-kS’,#X1X2…Xn-kA,aiai+1…an#)

其中g(shù)oto(Sn-k,A)=S’若action(Sn,ai)=Accept，則成功其它情形，出錯(cuò)分析棧符號(hào)棧

輸入串分析動(dòng)作轉(zhuǎn)向狀態(tài)

0idid+id$#S50,5idid+id$#R640,4Pid+id$#R570,7Tid+id$#S80,7,8Tid+id$#S50,7,8,5Tid+id$#R690,7,8,9TP+id$#R470,7T+id$#R310,1E+id$#S30,1,3E+id$#S50,1,3,5E+id$#R640,1,3,4E+P$#R5110,1,3,11E+T$#R210,1E$#S20,1,2E$#AcceptSLR(1)與LR(0)SLR(1)和LR(0)具有相同的狀態(tài)機(jī)LR(0)只看分析棧的內(nèi)容，不考慮當(dāng)前輸入符SLR(1)考慮輸入符，用follow集來(lái)解決沖突，因此SLR(1)要比LR(0)分析能力強(qiáng)

括號(hào)文法定義如下：Z→S$S→(S)S|

構(gòu)造該文法的SLR(1)分析表，并給出輸入流()()$＃的SLR(1)分析過(guò)程。主要內(nèi)容：

LR(1)分析方法ZEE(L,E)ESLL,ELESidS(S)ZEE(L,E)ESSidS(S)0E(L,E)S(S)LL,ELEE(L,E)ESSidS(S)1ESS(S)2(S狀態(tài)2存在移入--歸約沖突LR(0)方法不依賴輸入流，直接判定歸約，容易出現(xiàn)沖突。SLR(1)方法簡(jiǎn)單的把非終極符的follow集做為可歸約的依據(jù)，并不精確。一個(gè)非終極符在不同的位置上出現(xiàn)，它所允許的后繼符是不同的。LR(1)針對(duì)不同產(chǎn)生式上的非終極符，分別定義其后繼符集（展望符集Reducelookup），減少了移入/歸約沖突。LR(1)項(xiàng)目：[A→,a]。LR(0)項(xiàng)目及一個(gè)VT{#}的展望符集合IS:LR(1)項(xiàng)目集IS(X):IS(X)={[A→X,a]|[A→X,a]IS}CLOSURE(IS)=IS∪{[B→,b]|[A→B,a]CLOSURE(IS),B→是產(chǎn)生式,

bFirst(a)}GO:若IS是一個(gè)LR(1)項(xiàng)目集，X是一個(gè)文法符號(hào),則

GO（IS,X）=CLOSURE（IS(X)），其中IS(X)為L(zhǎng)R(1)項(xiàng)目集IS的投影

LRSM1的構(gòu)造算法初始項(xiàng)目集：ISS=CLOSURE({[Z→S,{#}]})若所有狀態(tài)都處理完，則結(jié)束選一未處理完?duì)顟B(tài)IS，對(duì)所有語(yǔ)法符號(hào)X（VTVN

{#}),求ISX,令I(lǐng)S’=CLOSURE(ISX)，若IS’不為空：

若IS’為新?tīng)顟B(tài)，則增加ISIS’,把IS’加入LRSM1中；否則為圖中某個(gè)狀態(tài)ISj，則在IS和ISj之間增加一條轉(zhuǎn)換邊：ISISj轉(zhuǎn)到步驟2XX

非SLR(1)文法：

Z→SS→L=RS→RL→aRL→bR→L

0ZSSL=RSRLaRLbRL###=#=##1ZS#2SL=RRL##6SL=RRLLaRLb####7SL=R#3SR#4Lb=#10LaR#=5LaRRLLaRLb#=#=#=#=11RL#=8LaRRLLaRLb####9RL#12Lb#13LaR#SLabRb=RLRLabaaLRbLR(1)分析表的構(gòu)造假設(shè)ISk為L(zhǎng)R(1)項(xiàng)目集則：若[Z,#]ISk，且Z為拓廣產(chǎn)生式的左部非終極符，則action(ISk,#)=Accept。若[A,a]ISk，且產(chǎn)生式A的編號(hào)為j，則action(ISk,a)=Rj，表示用編號(hào)為j的產(chǎn)生式進(jìn)行歸約。若[Aa,b]ISk，且GO(ISk,a)=ISi，aVT，則action(ISk,a)=Si，表示把狀態(tài)ISi和展望符a入棧。若GO(ISk,A)=ISi，AVN，則goto(ISk,A)=i。其它情形，則Error(n)，表示出錯(cuò)標(biāo)志，也可不填。

LR(1)文法的定義對(duì)于一個(gè)文法，若按照上述算法構(gòu)造的分析表中沒(méi)有沖突動(dòng)作，則稱該文法為L(zhǎng)R(1)文法。R413R512R6R611R4R410R69139S12S88R2779S12S861011S4S55R5R54R33R6S62A1321S4S50RLS#=baLR(1)驅(qū)動(dòng)程序LR(1)的驅(qū)動(dòng)程序與SLR(1)的驅(qū)動(dòng)程序是相同的，可共用一個(gè)。狀態(tài)棧符號(hào)棧

輸入串ActionGoTo0aab=b#S50,5aab=b#S50,5,5aab=b#S40,5,5,4aab=b#R5 110,5,5,11aaL=b#R6 100,5,5,10aaR=b#R4 110,5,11aL=b#R6 100,5,10aR=b#R4 20,2L=b#S60,2,6L=b#S120,2,6,12L=b#R5 90,2,6,9L=L#R6 70,2,6,7L=R#R2 10,1S#A設(shè)文法G[S]為： SAS|AaA|b 證明G[S]是LR(1)文法；構(gòu)造它的LR(1)分析表；給出符號(hào)串a(chǎn)bab#的分析過(guò)程LALR(1)方法它具有SLR(1)的狀態(tài)數(shù)少的優(yōu)點(diǎn)