LR項(xiàng)目集族和LR分析表的構(gòu)造

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

推導(dǎo)

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

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

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

A→b [2]

A→Ab [3]

B→d [4]abbcdeAABS當(dāng)棧頂出現(xiàn)可歸前綴即可歸約步驟符號(hào)棧剩余輸入串動(dòng)作1#abbcde#移進(jìn)2#abbcde#移進(jìn)3#abbcde#歸約A→b4#aAbcde#移進(jìn)5#aAbcde#歸約A→Ab6#aAcde#移進(jìn)7#aAcde#移進(jìn)8#aAcde#歸約B→d9#aAcBe#移進(jìn)10#aAcBe#歸約S→aAcBe11#S#接受abbcdeAABS棧里的文法符號(hào)與剩余符號(hào)串一起構(gòu)成了標(biāo)準(zhǔn)句型棧里的文法符號(hào)構(gòu)成活前綴S=>aAcBe=>aAcde=>aAbcde=>abbcde標(biāo)準(zhǔn)

推導(dǎo)

序列#abbcde#的標(biāo)準(zhǔn)歸約過程S'=>S=>aAcBe=>aAcde=>aAbcde=>abbcde規(guī)范

推導(dǎo)

序列識(shí)別句型#abbcde#所有活前綴的DFASabaAbaAcdaAcBeεεεεε確定化最小化0245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]利用DFA進(jìn)行移近-歸約分析(見黑板)acebd#SAB02112343465567878990245136897SaAbcBed*bG:S→aAcBe [1] A→b [2] A→Ab [3] B→d [4]rrrrrrrrrrrrrrrrrrrrrrrraccSSSSSSGOTOACTION222222333333444444111111LR分析表DFA的矩陣表示一個(gè)LR分析器實(shí)質(zhì)上是一個(gè)DFA小結(jié)識(shí)別文法所有活前綴的DFALR分析表LR分析二、構(gòu)造識(shí)別文法所有活前綴的DFA

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

S

aAd

A

bc2.構(gòu)造識(shí)別文法所有活前綴的DFA1).文法的每個(gè)工程都為NFA的一個(gè)狀態(tài)2).確定狀態(tài)之間的轉(zhuǎn)換關(guā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).文法的每個(gè)工程都為NFA的一個(gè)狀態(tài)2).確定狀態(tài)之間的轉(zhuǎn)換關(guā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·

每個(gè)狀態(tài)都為活前綴識(shí)別態(tài)◎句柄識(shí)別態(tài)(可歸前綴識(shí)別態(tài)):圓點(diǎn)在最后的工程句子識(shí)別態(tài)

aεεE*εεεεεεεAcAddcBbB786341059121318161112141517εp106識(shí)別一個(gè)文法活前綴的DFA3).確定化

最小化每個(gè)狀態(tài)是一個(gè)工程集,稱作LR(0)工程集整個(gè)狀態(tài)集稱為LR(0)工程集標(biāo)準(zhǔn)族3.LR(0)工程的分類移進(jìn)工程:A→α·aβ 分析時(shí)把a(bǔ)移進(jìn)符號(hào)棧待約工程:A→α·Bβ 用產(chǎn)生式A的右部歸約時(shí),首先要將B的產(chǎn)生式右部歸約為B,對(duì)A的右部才能繼續(xù)進(jìn)行分析歸約工程:A→α· 說明一個(gè)產(chǎn)生式的右部已分析完，句柄已形成可以歸約接受工程:S'→S·說明已分析成功三、LR(0)工程集標(biāo)準(zhǔn)族的構(gòu)造構(gòu)造識(shí)別文法活前綴DFA的三種方法*求出活前綴的正規(guī)表達(dá)式，然后由此正規(guī)表達(dá)式構(gòu)造NFA,再確定化為DFA。求出文法的所有工程，按一定規(guī)那么構(gòu)造識(shí)別活前綴的NFA,再確定化為DFA。通過閉包函數(shù)和轉(zhuǎn)換函數(shù)，直接求出LR(0)工程集標(biāo)準(zhǔn)族，再由轉(zhuǎn)換函數(shù)建立狀態(tài)之間的連接關(guān)系得到識(shí)別活前綴的DFA。1.拓廣文法2.工程集I的閉包函數(shù)CLOSURE(I)3.狀態(tài)轉(zhuǎn)換函數(shù)GO(I,X)4.構(gòu)造文法的LR(0)工程集標(biāo)準(zhǔn)族1.拓廣文法原文法G的開始符號(hào)為S,在G中加S'→S后得新的文法G'， 那么稱 G'為原文法G的拓廣文法。使文法的開始符號(hào)不出現(xiàn)在任何產(chǎn)生式右部，當(dāng)棧頂出現(xiàn)S′,那么分析完成。注:即使原開始符號(hào)S不出現(xiàn)在任何產(chǎn)生式右部,為了統(tǒng)一起見也要增加該產(chǎn)生式。2.工程集I的閉包函數(shù)CLOSURE(I)a)I的工程均在CLOSURE(I)中。b)假設(shè)A→α·Bβ屬于CLOSURE(I),那么每一形如B→·γ的工程也屬于CLOSURE(I)c)重復(fù)b)直到CLOSURE(I)不再擴(kuò)大。NFA:狀態(tài)集合I的ε-閉包ε-closure(I)εA→α·BβB→·γaεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε補(bǔ)充例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·β假設(shè)狀態(tài)I識(shí)別活前綴γ,那么狀態(tài)J識(shí)別活前綴γX狀態(tài)I狀態(tài)JNFA:狀態(tài)集合I的a弧轉(zhuǎn)換aεεE*εεεεεεεAcAddcBbB786341059121318161112141517ε補(bǔ)充例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.構(gòu)造文法的LR(0)工程集標(biāo)準(zhǔn)族C={I0,I1,……,In}核:圓點(diǎn)不在產(chǎn)生式右部最左邊的工程稱為核a)置工程S'→·S為初態(tài)集的核，然后對(duì)核求閉包，CLOSURE({S'→·S}〕得到初態(tài)的工程集。b)對(duì)初態(tài)集或其它所構(gòu)造的工程集應(yīng)用轉(zhuǎn)換函數(shù)GO(I，X)=CLOSURE(J)求出新狀態(tài)J的工程集。c)重復(fù)b)直到不出現(xiàn)新的工程為止。算法Procedureitemsets(G')

Begin C:={CLOSURE({S'

·S})}

Repeat

for

C中的每一個(gè)I和每一個(gè)X

do

if

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

把GO(I,X)放入C中

until

C不再增大endp107初態(tài)的工程集應(yīng)用狀態(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識(shí)別文法所有活前綴的DFALR(0)工程集標(biāo)準(zhǔn)族{I0,I1,…,I11}四、有效工程*如果存在標(biāo)準(zhǔn)推導(dǎo)那么工程A1·2對(duì)活前綴1是有效的。如果2，應(yīng)該移進(jìn)如果2=，應(yīng)該用產(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對(duì)活前綴bc有效考慮如下標(biāo)準(zhǔn)推導(dǎo)(1)SEbBbcB(2)SEbBbcBbccB(3)SEbBbcBbcd圖5.7p106識(shí)別文法活前綴的DFA從初態(tài)出發(fā),經(jīng)讀出活前綴γ后,而到達(dá)的工程集稱為活前綴γ的有效工程集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在任何時(shí)候，分析棧中的活前綴X1X2...Xm的有效工程集正是棧頂狀態(tài)Sm所代表的那個(gè)集合。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è)工程可能對(duì)好幾個(gè)活前綴都有效G':

S'→EE→aA|bBA→cA|dB→cB|d同一個(gè)活前綴，可能存在假設(shè)干個(gè)工程對(duì)它都是有效的，而且告訴我們應(yīng)做的事情各不相同，相互沖突。這種沖突通過向前多看幾個(gè)輸入符號(hào),或許能夠獲得解決。移進(jìn)-歸約沖突 一個(gè)工程集中移進(jìn)和歸約工程同時(shí)存在： A→α·aβ B→γ·歸約-歸約沖突 一個(gè)工程集中歸約和歸約工程同時(shí)存在: A→β· B→γ·五、LR(0)分析表的構(gòu)造LR(0)文法假假設(shè)一個(gè)文法G的拓廣文法G的活前綴識(shí)別自動(dòng)機(jī)中的每個(gè)狀態(tài)(工程集)不存在下述情況 ①既含移進(jìn)工程又含歸約工程 ②或者含有多個(gè)歸約工程 那么稱G是一個(gè)LR(0)文法。LR(0)文法標(biāo)準(zhǔn)族的每個(gè)工程集不包含任何沖突工程(移進(jìn)-歸約沖突、歸約-歸約沖突)。LR(0)分析表的構(gòu)造假設(shè)已構(gòu)造出LR(0)工程集標(biāo)準(zhǔn)族為:C={I0,I1,…,In}令包含S'→·S工程的集合Ik的下標(biāo)k為分析器的初始狀態(tài)。a)假設(shè)工程A