第五章語法分析5.1自下而上分析基本問題5.2算符優(yōu)先分析

5.3LR分析5.4YACC第五章語法分析5.1自下而上分析基本問題5.3LR分析5.3.1LR分析器5.3.2LR(0)項目集族＆LR(0)分析表的構造5.3.3SLR分析表的構造5.3.4規(guī)范LR分析表的構造5.3.5LALR分析表的構造5.3.6二義文法的應用5.3LR分析5.3.1LR分析器5.3.2LR(0)項目集族＆LR(0)分析表的構造一、前綴、活前綴p104二、構造識別文法所有活前綴的DFAp104三、LR(0)項目集規(guī)范族的構造p106四、有效項目p108五、LR(0)分析表的構造p1095.3.2LR(0)項目集族＆LR(0)分析表的構造一、前一、前綴、活前綴前綴

:符號串的頭活前綴

:規(guī)范句型的一個前綴,這種前綴不包含句柄之后的任何符號.*可歸前綴:包含句柄的活前綴.一、前綴、活前綴前綴:符號串的頭規(guī)范

推導

序列 S =>aAcBe =>aAcde =>aAbcde =>abbcdeε,a,abε,a,aA,aAb

ε,a,aA,aAc,aAcdε,a,aA,aAc,aAcB,aAcBe活前綴可歸前綴ab,aAb,aAcd,aAcBe補充例:找出句型

#abbcde# 的所有活前綴G:S→aAcBe [1]

A→b [2]

A→Ab [3]

B→d [4]abbcdeAABS當棧頂出現(xiàn)可歸前綴即可歸約規(guī)范

推導

序列 S =>aAcBeε,a步驟符號棧剩余輸入串動作1#abbcde#移進2#abbcde#移進3#abbcde#歸約A→b4#aAbcde#移進5#aAbcde#歸約A→Ab6#aAcde#移進7#aAcde#移進8#aAcde#歸約B→d9#aAcBe#移進10#aAcBe#歸約S→aAcBe11#S#接受abbcdeAABS棧里的文法符號與剩余符號串一起構成了規(guī)范句型棧里的文法符號構成活前綴S=>aAcBe=>aAcde=>aAbcde=>abbcde規(guī)范

推導

序列#abbcde#的規(guī)范歸約過程步符號棧剩余動作1#abbcde#移進2#abbcde#移進S'=>S=>aAcBe=>aAcde=>aAbcde=>abbcde規(guī)范

推導

序列識別句型#abbcde#所有活前綴的DFASabaAbaAcdaAcBeεεεεε確定化最小化0245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]利用DFA進行移近-歸約分析(見黑板)S'=>S規(guī)范

推導

序列識別句型#abbcde#所有活前acebd#SAB02112343465567878990245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]rrrrrrrrrrrrrrrrrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析表DFA的矩陣表示一個LR分析器實質上是一個DFAacebd#SAB0211234346556787小結識別文法所有活前綴的DFALR分析表LR分析小結識別文法所有活前綴的DFALR分析表LR分析二、構造識別文法所有活前綴的DFA

1.LR(0)項目2.構造識別文法所有活前綴的DFA3.LR(0)項目的分類求出文法所有的活前綴根據產生式得出可能出現(xiàn)在棧中的符號串二、構造識別文法所有活前綴的DFA1.LR(0)項目求出1.LR(0)項目在文法G中每個產生式的右部適當位置添加一個圓點構成項目.對空產生式A→ε,僅有項目A→·

例:產生式AXYZ

對應的項目有

A·XYZ AX·YZ AXY·Z AXYZ·一個產生式可對應的項目個數是它的右部符號長度加1每個項目的含義與圓點的位置有關1.LR(0)項目在文法G中每個產生式的右部適當位置添加一補充例對應的項目:(1)S·aAd (2)Sa·Ad (3)SaA·d (4)SaAd·

(5)A·bc(6)Ab·c(7)Abc·借助項目構造識別文法活前綴的DFAG:

SaAd

Abc補充例對應的項目:2.構造識別文法所有活前綴的DFA1).文法的每個項目都為NFA的一個狀態(tài)2).確定狀態(tài)之間的轉換關系3).確定化最小化2.構造識別文法所有活前綴的DFA1).文法的每個項目都例5.8p105G':

S'→E

E→aA|bB

A→cA|d

B→cB|d更正1．S'→·E

2．S'→E· 11.E→·bB

3．E→·aA

12.E→b·B

4．E→a·A

13.E→bB·

5．E→aA·

14.B→·cB

6．A→·cA

15.B→c·B

7．A→c·A

16.B→cB·

8．A→cA·

17.B→·d

9．A→·d

18.B→d·10.A→d·文法的項目:1).文法的每個項目都為NFA的一個狀態(tài)例5.8p105G': 2).確定狀態(tài)之間的轉換關系XiX→X1X2…Xi-1·Xi…XnX→X1X2…Xi·Xi+1…XnεX→α·AβA→·γ狀態(tài)i狀態(tài)j出自同一產生式2).確定狀態(tài)之間的轉換關系XiX→X1X2…Xi-1·X項目1為初態(tài)

P106NFA1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·每個狀態(tài)都為活前綴識別態(tài)◎句柄識別態(tài)(可歸前綴識別態(tài)):圓點在最后的項目句子識別態(tài)

aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε項目1P106NFA1．S'→·E每個狀態(tài)都為活前綴識別態(tài)p106識別一個文法活前綴的DFA3).確定化

最小化每個狀態(tài)是一個項目集,稱作LR(0)項目集整個狀態(tài)集稱為LR(0)項目集規(guī)范族p106識別一個文法活前綴的DFA3).確定化

3.LR(0)項目的分類移進項目:

A→α·aβ

分析時把a移進符號棧待約項目:

A→α·Bβ 用產生式A的右部歸約時,首先要將B的產生式右部歸約為B,對A的右部才能繼續(xù)進行分析歸約項目:

A→α·

表明一個產生式的右部已分析完，句柄已形成可以歸約接受項目:

S'→S·

表明已分析成功3.LR(0)項目的分類移進項目:A→α·aβ 三、LR(0)項目集規(guī)范族的構造構造識別文法活前綴DFA的三種方法*求出活前綴的正規(guī)表達式，然后由此正規(guī)表達式構造NFA,再確定化為DFA。求出文法的所有項目，按一定規(guī)則構造識別活前綴的NFA,再確定化為DFA。通過閉包函數和轉換函數，直接求出LR(0)項目集規(guī)范族，再由轉換函數建立狀態(tài)之間的連接關系得到識別活前綴的DFA。三、LR(0)項目集規(guī)范族的構造構造識別文法活前綴DFA的三1.拓廣文法2.項目集I的閉包函數CLOSURE(I)3.狀態(tài)轉換函數GO(I,X)4.構造文法的LR(0)項目集規(guī)范族1.拓廣文法21可編輯21可編輯1.拓廣文法原文法G的開始符號為S,在G中加S'→S

后得新的文法G'， 則稱 G'為原文法G的拓廣文法。使文法的開始符號不出現(xiàn)在任何產生式右部，當棧頂出現(xiàn)S′,則分析完成。注:即使原開始符號S不出現(xiàn)在任何產生式右部,為了統(tǒng)一起見也要增加該產生式。1.拓廣文法原文法G的開始符號為S,2.項目集I的閉包函數CLOSURE(I)a)I的項目均在CLOSURE(I)中。b)

若A→α·Bβ屬于CLOSURE(I),則每一形如B→·γ的項目也屬于CLOSURE(I)c)

重復b)直到CLOSURE(I)不再擴大。NFA:狀態(tài)集合I的ε-閉包ε-closure(I)εA→α·BβB→·γ2.項目集I的閉包函數CLOSURE(I)a)I的項目aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε補充例I＝{S'→·E}CLOSURE(I)={S'→·E,E→·aA,E→·bB}1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·1311aεεE*εεεεεεεAcAddcBbB7863410593.狀態(tài)轉換函數GO(I,X)GO(I,X)=CLOSURE(J)

,X∈(VN∪VT), J={A→αX·β|A→α·Xβ∈I}XA→α·XβA→αX·β若狀態(tài)I識別活前綴γ,則狀態(tài)J識別活前綴γX

狀態(tài)I狀態(tài)JNFA:狀態(tài)集合I的a弧轉換3.狀態(tài)轉換函數GO(I,X)GO(I,X)=CLaεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε補充例I＝{S'→·E,E→·aA,E→·bB

}GO(I,a)=CLOSURE({E→a·A}) ={E→a·A

,A→·cA,A→·d

}1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·1311469aεεE*εεεεεεεAcAddcBbB7863410594.構造文法的LR(0)項目集規(guī)范族C={I0,I1,……,In}核:圓點不在產生式右部最左邊的項目稱為核a)置項目S'→·S為初態(tài)集的核，然后對核求閉包，CLOSURE({S'→·S}）得到初態(tài)的項目集。b)對初態(tài)集或其它所構造的項目集應用轉換函數GO(I，X)=CLOSURE(J)求出新狀態(tài)J的項目集。c)重復b)直到不出現(xiàn)新的項目為止。4.構造文法的LR(0)項目集規(guī)范族C={I0,I1,……算法Procedureitemsets(G')

Begin C:={CLOSURE({S'·S})}

Repeat

for

C中的每一個I和每一個X

do

if

GO(I,X)非空且不屬于Cthen

把GO(I,X)放入C中

until

C不再增大endp107初態(tài)的項目集應用狀態(tài)轉換函數得到新的項目集算法Procedureitemsets(G')G':

S'→E

E→aA|bB

A→cA|d B→cB|dI0:

S'?E

E?aAE?bBI8:

Bc?B

B?cBB?dI3:

Eb?B

B?cBB?dI2:Ea?A

A?cAA?dI1:

S'E?I5:Ac?A

A?cAA?dI10:AcA?I6:Ad?I4:EaA?I7:EbB?I9:Bd?I11:BcB?

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B識別文法所有活前綴的DFALR(0)項目集規(guī)范族{I0,I1,…,I11}G':S'→EI0:S'?EI8:四、有效項目*如果存在規(guī)范推導則項目A1·2

對活前綴1

是有效的。如果2，應該移進如果2=

，應該用產生式A1歸約*RR12AS'四、有效項目*如果存在規(guī)范推導*RR12AI0:S'?EE?aAE?bBI5:Bc?B

B?cB

B?dI3:Eb?B

B?cB

B?dI2:Ea?A

A?cAA?dI1:S'E?I4:Ac?A

A?cAA?dI8:AcA?I10:Ad

?I6:EaA

?I7:EbB?I11:Bd

?I9:BcB?

b

E

a

c

c

c

c

d

d

d

d

A

A

B

BG':

S'→EE→aA|bBA→cA|dB→cB|d項目集I5對活前綴bc有效考慮如下規(guī)范推導(1)

SE

bB

bcB(2)

SE

bB

bcB

bccB(3)SE

bB

bcB

bcdI0:S'?EI5:Bc?BI3:Eb?B圖5.7p106識別文法活前綴的DFA從初態(tài)出發(fā),經讀出活前綴γ后,而到達的項目集稱為活前綴γ的有效項目集I0:S'?E

E?aAE?bBI5:Bc?B

B?cB

B?dI3:Eb?B

B?cB

B?dI2:Ea?A

A?cAA?dI1:S'E?I4:Ac?A

A?cAA?dI8:AcA?I10:Ad

?I6:EaA

?I7:EbB?I11:Bd

?I9:BcB?

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B圖5.7p106識別文法從初態(tài)出發(fā),經讀出活前綴γ后,而到LR分析理論的一條基本定理p108在任何時候，分析棧中的活前綴X1X2...Xm的有效項目集正是棧頂狀態(tài)Sm所代表的那個集合。LR分析理論的一條基本定理p108在任何時候，分析棧中I0:S'?EE?aAE?bBI5:Bc?B

B?cB

B?dI3:Eb?B

B?cB

B?dI2:Ea?A

A?cA

A?dI1:S'E?I4:Ac?A

A?cAA?dI8:AcA?I10:Ad

?I6:EaA

?I7:EbB?I11:Bd

?I9:BcB?

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B同一個項目可能對好幾個活前綴都有效G':

S'→EE→aA|bBA→cA|dB→cB|dI0:S'?EI5:Bc?BI3:Eb?B同一個活前綴，可能存在若干個項目對它都是有效的，而且告訴我們應做的事情各不相同，相互沖突。這種沖突通過向前多看幾個輸入符號,或許能夠獲得解決。同一個活前綴，可能存在若干個項目對它都是有效的，而且告訴我們移進-歸約沖突

一個項目集中移進和歸約項目同時存在： A→α·aβ B→γ·歸約-歸約沖突 一個項目集中歸約和歸約項目同時存在:

A→β· B→γ·五、LR(0)分析表的構造移進-歸約沖突五、LR(0)分析表的構造LR(0)文法假若一個文法G的拓廣文法G的活前綴識別自動機中的每個狀態(tài)(項目集)不存在下述情況 ①既含移進項目又含歸約項目 ②或者含有多個歸約項目 則稱G是一個LR(0)文法。LR(0)文法規(guī)范族的每個項目集不包含任何沖突項目(移進-歸約沖突、歸約-歸約沖突)。LR(0)文法假若一個文法G的拓廣文法G的活前綴識別自動機LR(0)分析表的構造假設已構造出LR(0)項目集規(guī)范族為:C={I0,I1,…,In}令包含S'→·S

項目的集合Ik的下標k為分析器的初始狀態(tài)。LR(0)分析表的構造假設已構造出LR(0)項目集規(guī)范族為:a)

若項目A→α·aβ屬于Ik,且GO(Ik,a)=Ij

則置ACTION[k,a]為Sjb)

若項目A→α·

屬于Ik，則對任何終結符a和‘#’

置ACTION[k,a]和ACTION[k,#]為“rj”,j為在文法G'中某產生式A→α的序號。c)若項目S'→S·

屬于Ik, 則置ACTION[k,#]為“acc”/接受d)

若GO(Ik,A)＝Ij，則置GOTO[k,A]

為"j"e)

凡不能用上述方法填入的元素,均填上“報錯標志”/“空白”a)若項目A→α·aβ屬于Ik,且GO(Ik,a)I0:

S'?E

E?aAE?bBI8:

Bc?B

B?cBB?dI3:

Eb?B

B?cBB?dI2:Ea?A

A?cAA?dI1:

S'E?I5:Ac?A

A?cAA?dI10:AcA?I6:Ad?I4:EaA?I7:EbB?I9:Bd?I11:BcB?

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B(0)S'→E

(1)E→aA

(2)E→bB

(3)A→cA(4)A→d(5)B→cB(6)B→d構造LR(0)分析表過程見黑板I0:S'?EI8:Bc?BI3:Eb?B根據這種方法構造的LR(0)分析表不含多重定義時，稱這樣的分析表為LR(0)分析表能用LR(0)分析表的分析器稱為LR(0)分析器根據這種方法構造的LR(0)分析表不含多重定義時，稱這樣的分42可編輯42可編輯第五章語法分析5.1自下而上分析基本問題5.2算符優(yōu)先分析

5.3LR分析5.4YACC第五章語法分析5.1自下而上分析基本問題5.3LR分析5.3.1LR分析器5.3.2LR(0)項目集族＆LR(0)分析表的構造5.3.3SLR分析表的構造5.3.4規(guī)范LR分析表的構造5.3.5LALR分析表的構造5.3.6二義文法的應用5.3LR分析5.3.1LR分析器5.3.2LR(0)項目集族＆LR(0)分析表的構造一、前綴、活前綴p104二、構造識別文法所有活前綴的DFAp104三、LR(0)項目集規(guī)范族的構造p106四、有效項目p108五、LR(0)分析表的構造p1095.3.2LR(0)項目集族＆LR(0)分析表的構造一、前一、前綴、活前綴前綴

:符號串的頭活前綴

:規(guī)范句型的一個前綴,這種前綴不包含句柄之后的任何符號.*可歸前綴:包含句柄的活前綴.一、前綴、活前綴前綴:符號串的頭規(guī)范

推導

序列 S =>aAcBe =>aAcde =>aAbcde =>abbcdeε,a,abε,a,aA,aAb

ε,a,aA,aAc,aAcdε,a,aA,aAc,aAcB,aAcBe活前綴可歸前綴ab,aAb,aAcd,aAcBe補充例:找出句型

#abbcde# 的所有活前綴G:S→aAcBe [1]

A→b [2]

A→Ab [3]

B→d [4]abbcdeAABS當棧頂出現(xiàn)可歸前綴即可歸約規(guī)范

推導

序列 S =>aAcBeε,a步驟符號棧剩余輸入串動作1#abbcde#移進2#abbcde#移進3#abbcde#歸約A→b4#aAbcde#移進5#aAbcde#歸約A→Ab6#aAcde#移進7#aAcde#移進8#aAcde#歸約B→d9#aAcBe#移進10#aAcBe#歸約S→aAcBe11#S#接受abbcdeAABS棧里的文法符號與剩余符號串一起構成了規(guī)范句型棧里的文法符號構成活前綴S=>aAcBe=>aAcde=>aAbcde=>abbcde規(guī)范

推導

序列#abbcde#的規(guī)范歸約過程步符號棧剩余動作1#abbcde#移進2#abbcde#移進S'=>S=>aAcBe=>aAcde=>aAbcde=>abbcde規(guī)范

推導

序列識別句型#abbcde#所有活前綴的DFASabaAbaAcdaAcBeεεεεε確定化最小化0245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]利用DFA進行移近-歸約分析(見黑板)S'=>S規(guī)范

推導

序列識別句型#abbcde#所有活前acebd#SAB02112343465567878990245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]rrrrrrrrrrrrrrrrrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析表DFA的矩陣表示一個LR分析器實質上是一個DFAacebd#SAB0211234346556787小結識別文法所有活前綴的DFALR分析表LR分析小結識別文法所有活前綴的DFALR分析表LR分析二、構造識別文法所有活前綴的DFA

1.LR(0)項目2.構造識別文法所有活前綴的DFA3.LR(0)項目的分類求出文法所有的活前綴根據產生式得出可能出現(xiàn)在棧中的符號串二、構造識別文法所有活前綴的DFA1.LR(0)項目求出1.LR(0)項目在文法G中每個產生式的右部適當位置添加一個圓點構成項目.對空產生式A→ε,僅有項目A→·

例:產生式AXYZ

對應的項目有

A·XYZ AX·YZ AXY·Z AXYZ·一個產生式可對應的項目個數是它的右部符號長度加1每個項目的含義與圓點的位置有關1.LR(0)項目在文法G中每個產生式的右部適當位置添加一補充例對應的項目:(1)S·aAd (2)Sa·Ad (3)SaA·d (4)SaAd·

(5)A·bc(6)Ab·c(7)Abc·借助項目構造識別文法活前綴的DFAG:

SaAd

Abc補充例對應的項目:2.構造識別文法所有活前綴的DFA1).文法的每個項目都為NFA的一個狀態(tài)2).確定狀態(tài)之間的轉換關系3).確定化最小化2.構造識別文法所有活前綴的DFA1).文法的每個項目都例5.8p105G':

S'→E

E→aA|bB

A→cA|d

B→cB|d更正1．S'→·E

2．S'→E· 11.E→·bB

3．E→·aA

12.E→b·B

4．E→a·A

13.E→bB·

5．E→aA·

14.B→·cB

6．A→·cA

15.B→c·B

7．A→c·A

16.B→cB·

8．A→cA·

17.B→·d

9．A→·d

18.B→d·10.A→d·文法的項目:1).文法的每個項目都為NFA的一個狀態(tài)例5.8p105G': 2).確定狀態(tài)之間的轉換關系XiX→X1X2…Xi-1·Xi…XnX→X1X2…Xi·Xi+1…XnεX→α·AβA→·γ狀態(tài)i狀態(tài)j出自同一產生式2).確定狀態(tài)之間的轉換關系XiX→X1X2…Xi-1·X項目1為初態(tài)

P106NFA1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·每個狀態(tài)都為活前綴識別態(tài)◎句柄識別態(tài)(可歸前綴識別態(tài)):圓點在最后的項目句子識別態(tài)

aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε項目1P106NFA1．S'→·E每個狀態(tài)都為活前綴識別態(tài)p106識別一個文法活前綴的DFA3).確定化

最小化每個狀態(tài)是一個項目集,稱作LR(0)項目集整個狀態(tài)集稱為LR(0)項目集規(guī)范族p106識別一個文法活前綴的DFA3).確定化

3.LR(0)項目的分類移進項目:

A→α·aβ

分析時把a移進符號棧待約項目:

A→α·Bβ 用產生式A的右部歸約時,首先要將B的產生式右部歸約為B,對A的右部才能繼續(xù)進行分析歸約項目:

A→α·

表明一個產生式的右部已分析完，句柄已形成可以歸約接受項目:

S'→S·

表明已分析成功3.LR(0)項目的分類移進項目:A→α·aβ 三、LR(0)項目集規(guī)范族的構造構造識別文法活前綴DFA的三種方法*求出活前綴的正規(guī)表達式，然后由此正規(guī)表達式構造NFA,再確定化為DFA。求出文法的所有項目，按一定規(guī)則構造識別活前綴的NFA,再確定化為DFA。通過閉包函數和轉換函數，直接求出LR(0)項目集規(guī)范族，再由轉換函數建立狀態(tài)之間的連接關系得到識別活前綴的DFA。三、LR(0)項目集規(guī)范族的構造構造識別文法活前綴DFA的三1.拓廣文法2.項目集I的閉包函數CLOSURE(I)3.狀態(tài)轉換函數GO(I,X)4.構造文法的LR(0)項目集規(guī)范族1.拓廣文法63可編輯21可編輯1.拓廣文法原文法G的開始符號為S,在G中加S'→S

后得新的文法G'， 則稱 G'為原文法G的拓廣文法。使文法的開始符號不出現(xiàn)在任何產生式右部，當棧頂出現(xiàn)S′,則分析完成。注:即使原開始符號S不出現(xiàn)在任何產生式右部,為了統(tǒng)一起見也要增加該產生式。1.拓廣文法原文法G的開始符號為S,2.項目集I的閉包函數CLOSURE(I)a)I的項目均在CLOSURE(I)中。b)

若A→α·Bβ屬于CLOSURE(I),則每一形如B→·γ的項目也屬于CLOSURE(I)c)

重復b)直到CLOSURE(I)不再擴大。NFA:狀態(tài)集合I的ε-閉包ε-closure(I)εA→α·BβB→·γ2.項目集I的閉包函數CLOSURE(I)a)I的項目aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε補充例I＝{S'→·E}CLOSURE(I)={S'→·E,E→·aA,E→·bB}1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·1311aεεE*εεεεεεεAcAddcBbB7863410593.狀態(tài)轉換函數GO(I,X)GO(I,X)=CLOSURE(J)

,X∈(VN∪VT), J={A→αX·β|A→α·Xβ∈I}XA→α·XβA→αX·β若狀態(tài)I識別活前綴γ,則狀態(tài)J識別活前綴γX

狀態(tài)I狀態(tài)JNFA:狀態(tài)集合I的a弧轉換3.狀態(tài)轉換函數GO(I,X)GO(I,X)=CLaεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε補充例I＝{S'→·E,E→·aA,E→·bB

}GO(I,a)=CLOSURE({E→a·A}) ={E→a·A

,A→·cA,A→·d

}1．S'→·E2．S'→E·

3．E→·aA

4．E→a·A

5．E→aA·

6．A→·cA7．A→c·A

8．A→cA·

9．A→·d

10.A→d·11.E→·bB12.E→b·B13.E→bB·14.B→·cB15.B→c·B

16.B→cB·17.B→·d18.B→d·1311469aεεE*εεεεεεεAcAddcBbB7863410594.構造文法的LR(0)項目集規(guī)范族C={I0,I1,……,In}核:圓點不在產生式右部最左邊的項目稱為核a)置項目S'→·S為初態(tài)集的核，然后對核求閉包，CLOSURE({S'→·S}）得到初態(tài)的項目集。b)對初態(tài)集或其它所構造的項目集應用轉換函數GO(I，X)=CLOSURE(J)求出新狀態(tài)J的項目集。c)重復b)直到不出現(xiàn)新的項目為止。4.構造文法的LR(0)項目集規(guī)范族C={I0,I1,……算法Procedureitemsets(G')

Begin C:={CLOSURE({S'·S})}

Repeat

for

C中的每一個I和每一個X

do

if

GO(I,X)非空且不屬于Cthen

把GO(I,X)放入C中

until

C不再增大endp107初態(tài)的項目集應用狀態(tài)轉換函數得到新的項目集算法Procedureitemsets(G')G':

S'→E

E→aA|bB

A→cA|d B→cB|dI0:

S'?E

E?aAE?bBI8:

Bc?B

B?cBB?dI3:

Eb?B

B?cBB?dI2:Ea?A

A?cAA?dI1:

S'E?I5:Ac?A

A?cAA?dI10:AcA?I6:Ad?I4:EaA?I7:EbB?I9:Bd?I11:BcB?

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B識別文法所有活前綴的DFALR(0)項目集規(guī)范族{I0,I1,…,I11}G':S'→EI0:S'?EI8:四、有效項目*如果存在規(guī)范推導則項目A1·2

對活前綴1

是有效的。如果2，應該移進如果2=

，應該用產生式A1歸約*RR12AS'四、有效項目*如果存在規(guī)范推導*RR12AI0:S'?EE?aAE?bBI5:Bc?B

B?cB

B?dI3:Eb?B

B?cB

B?dI2:Ea?A

A?cAA?dI1:S'E?I4:Ac?A

A?cAA?dI8:AcA?I10:Ad

?I6:EaA

?I7:EbB?I11:Bd

?I9:BcB?

b

E

a

c

c

c

c

d

d

d

d

A

A

B

BG':

S'→EE→aA|bBA→cA|dB→cB|d項目集I5對活前綴bc有效考慮如下規(guī)范推導(1)

SE

bB

bcB(2)

SE

bB

bcB

bccB(3)SE

bB

bcB

bcdI0:S'?EI5:Bc?BI3:Eb?B圖5.7p106識別文法活前綴的DFA從初態(tài)出發(fā),經讀出活前綴γ后,而到達的項目集稱為活前綴γ的有效項目集I0:S'?E

E?aAE?bBI5:Bc?B

B?cB

B?dI3:Eb?B

B?cB

B?dI2:Ea?A

A?cAA?dI1:S'E?I4:Ac?A

A?cAA?dI8:AcA?I10:Ad

?I6:EaA

?I7:EbB?I11:Bd

?I9:BcB?

b

E

a

c

c

c

c

d

d

d

d

A

A

B

B圖5.7p106識別文法從初態(tài)出發(fā),經讀出活前綴γ后,而到LR分析理論的一條基本定理p108在任何時候，分析棧中的活前綴X1X2...Xm的有效項目集正是棧頂狀態(tài)Sm所代表的那個集合。LR分析理論的一條基本定理p108在任何時候，分析棧中I0:S'?EE?aA