LR項目集族和LR分析表的構造

第五章語法分析5.1自下而上分析根本問題5.2算符優(yōu)先分析5.3LR分析5.4YACC5.3LR分析5.3.1LR分析器5.3.2LR(0)工程集族＆LR(0)分析表的構造5.3.3SLR分析表的構造5.3.4標準LR分析表的構造5.3.5LALR分析表的構造5.3.6二義文法的應用5.3.2LR(0)工程集族＆LR(0)分析表的構造一、前綴、活前綴p104二、構造識別文法所有活前綴的DFAp104三、LR(0)工程集標準族的構造p106四、有效工程p108五、LR(0)分析表的構造p109一、前綴、活前綴前綴:符號串的頭活前綴:標準句型的一個前綴,這種前綴不包含句柄之后的任何符號.*可歸前綴:包含句柄的活前綴.標準

推導

序列 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)可歸前綴即可歸約步驟符號棧剩余輸入串動作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棧里的文法符號與剩余符號串一起構成了標準句型棧里的文法符號構成活前綴S=>aAcBe=>aAcde=>aAbcde=>abbcde標準

推導

序列#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進行移近-歸約分析(見黑板)acebd#SAB02112343465567878990245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]rrrrrrrrrrrrrrrrrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析表DFA的矩陣表示一個LR分析器實質(zhì)上是一個DFA小結識別文法所有活前綴的DFALR分析表LR分析二、構造識別文法所有活前綴的DFA

1.LR(0)工程2.構造識別文法所有活前綴的DFA3.LR(0)工程的分類求出文法所有的活前綴根據(jù)產(chǎn)生式得出可能出現(xiàn)在棧中的符號串1.LR(0)工程在文法G中每個產(chǎn)生式的右部適當位置添加一個圓點構成工程.對空產(chǎn)生式A→ε,僅有工程A→·例:產(chǎn)生式AXYZ對應的工程有A·XYZ AX·YZ AXY·Z AXYZ·一個產(chǎn)生式可對應的工程個數(shù)是它的右部符號長度加1每個工程的含義與圓點的位置有關補充例對應的工程:(1)S·aAd (2)Sa·Ad (3)SaA·d (4)SaAd· (5)A·bc(6)Ab·c(7)Abc·借助工程構造識別文法活前綴的DFAG:

S

aAd

A

bc2.構造識別文法所有活前綴的DFA1).文法的每個工程都為NFA的一個狀態(tài)2).確定狀態(tài)之間的轉(zhuǎn)換關系3).確定化最小化例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)2).確定狀態(tài)之間的轉(zhuǎn)換關系XiX→X1X2…Xi-1·Xi…XnX→X1X2…Xi·Xi+1…XnεX→α·AβA→·γ狀態(tài)i狀態(tài)j出自同一產(chǎn)生式工程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εp106識別一個文法活前綴的DFA3).確定化

最小化每個狀態(tài)是一個工程集,稱作LR(0)工程集整個狀態(tài)集稱為LR(0)工程集標準族3.LR(0)工程的分類移進工程:A→α·aβ 分析時把a移進符號棧待約工程:A→α·Bβ 用產(chǎn)生式A的右部歸約時,首先要將B的產(chǎn)生式右部歸約為B,對A的右部才能繼續(xù)進行分析歸約工程:A→α· 說明一個產(chǎn)生式的右部已分析完，句柄已形成可以歸約接受工程:S'→S·說明已分析成功三、LR(0)工程集標準族的構造構造識別文法活前綴DFA的三種方法*求出活前綴的正規(guī)表達式，然后由此正規(guī)表達式構造NFA,再確定化為DFA。求出文法的所有工程，按一定規(guī)那么構造識別活前綴的NFA,再確定化為DFA。通過閉包函數(shù)和轉(zhuǎn)換函數(shù)，直接求出LR(0)工程集標準族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關系得到識別活前綴的DFA。1.拓廣文法2.工程集I的閉包函數(shù)CLOSURE(I)3.狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)4.構造文法的LR(0)工程集標準族1.拓廣文法原文法G的開始符號為S,在G中加S'→S后得新的文法G'， 那么稱 G'為原文法G的拓廣文法。使文法的開始符號不出現(xiàn)在任何產(chǎn)生式右部，當棧頂出現(xiàn)S′,那么分析完成。注:即使原開始符號S不出現(xiàn)在任何產(chǎn)生式右部,為了統(tǒng)一起見也要增加該產(chǎn)生式。2.工程集I的閉包函數(shù)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→·γ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·

13113.狀態(tài)轉(zhuǎn)換函數(shù)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弧轉(zhuǎn)換aεε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·

13114694.構造文法的LR(0)工程集標準族C={I0,I1,……,In}核:圓點不在產(chǎn)生式右部最左邊的工程稱為核a)置工程S'→·S為初態(tài)集的核，然后對核求閉包，CLOSURE({S'→·S}〕得到初態(tài)的工程集。b)對初態(tài)集或其它所構造的工程集應用轉(zhuǎn)換函數(shù)GO(I，X)=CLOSURE(J)求出新狀態(tài)J的工程集。c)重復b)直到不出現(xiàn)新的工程為止。算法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)轉(zhuǎn)換函數(shù)得到新的工程集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)工程集標準族{I0,I1,…,I11}四、有效工程*如果存在標準推導那么工程A1·2對活前綴1是有效的。如果2，應該移進如果2=，應該用產(chǎn)生式A1歸約

*R

R

1

2

A

S'I0:S'?EE?aAE?bBI5:Bc?BB?cBB?dI3:Eb?BB?cBB?dI2:Ea?AA?cAA?dI1:S'E?I4:Ac?AA?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有效考慮如下標準推導(1)SEbBbcB(2)SEbBbcBbccB(3)SEbBbcBbcd圖5.7p106識別文法活前綴的DFA從初態(tài)出發(fā),經(jīng)讀出活前綴γ后,而到達的工程集稱為活前綴γ的有效工程集I0:S'?E

E?aAE?bBI5:Bc?B

B?cBB?dI3:Eb?B

B?cBB?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

BLR分析理論的一條根本定理p108在任何時候，分析棧中的活前綴X1X2...Xm的有效工程集正是棧頂狀態(tài)Sm所代表的那個集合。I0:S'?EE?aAE?bBI5:Bc?BB?cBB?dI3:Eb?BB?cBB?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|d同一個活前綴，可能存在假設干個工程對它都是有效的，而且告訴我們應做的事情各不相同，相互沖突。這種沖突通過向前多看幾個輸入符號,或許能夠獲得解決。移進-歸約沖突 一個工程集中移進和歸約工程同時存在： A→α·aβ B→γ·歸約-歸約沖突 一個工程集中歸約和歸約工程同時存在: A→β· B→γ·五、LR(0)分析表的構造LR(0)文法假假設一個文法G的拓廣文法G的活前綴識別自動機中的每個狀態(tài)(工程集)不存在下述情況 ①既含移進工程又含歸約工程 ②或者含有多個歸約工程 那么稱G是一個LR(0)文法。LR(0)文法標準族的每個工程集不包含任何沖突工程(移進-歸約沖突、歸約-歸約沖突)。LR(0)分析表的構造假設已構造出LR(0)工程集標準族為:C={I0,I1,…,In}令包含S'→·S工程的集合Ik的下標k為分析器的初始狀態(tài)。a)假設工程A