LR分析器SLR規(guī)范的LR課件

LR分析器（SLR，規(guī)范的LR）4.6-4.7LR分析器（SLR，規(guī)范的LR）4.6-4.7SLRSLR4.5

LR分析器4.5.3構(gòu)造SLR分析表術(shù)語(yǔ)：LR(0)項(xiàng)目（簡(jiǎn)稱(chēng)項(xiàng)目）在右部的某個(gè)地方加點(diǎn)的產(chǎn)生式4.5LR分析器4.5.3構(gòu)造SLR分析表4.5

LR分析器4.5.3構(gòu)造SLR分析表術(shù)語(yǔ)：LR(0)項(xiàng)目（簡(jiǎn)稱(chēng)項(xiàng)目）在右部的某個(gè)地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來(lái)表示分析過(guò)程中的狀態(tài)4.5LR分析器4.5.3構(gòu)造SLR分析表4.5

LR分析器4.5.3構(gòu)造SLR分析表術(shù)語(yǔ)：LR(0)項(xiàng)目（簡(jiǎn)稱(chēng)項(xiàng)目）在右部的某個(gè)地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來(lái)表示分析過(guò)程中的狀態(tài)exprexpr+term

4.5LR分析器4.5.3構(gòu)造SLR分析表exprex4.5

LR分析器4.5.3構(gòu)造SLR分析表術(shù)語(yǔ)：LR(0)項(xiàng)目（簡(jiǎn)稱(chēng)項(xiàng)目）在右部的某個(gè)地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來(lái)表示分析過(guò)程中的狀態(tài)exprexpr+term*termfactor

4.5LR分析器4.5.3構(gòu)造SLR分析表exprex4.5

LR分析器4.5.3構(gòu)造SLR分析表術(shù)語(yǔ)：LR(0)項(xiàng)目（簡(jiǎn)稱(chēng)項(xiàng)目）在右部的某個(gè)地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來(lái)表示分析過(guò)程中的狀態(tài)exprexpr+term*termfactor

4.5LR分析器4.5.3構(gòu)造SLR分析表exprex4.5

LR分析器4.5.3構(gòu)造SLR分析表術(shù)語(yǔ)：LR(0)項(xiàng)目（簡(jiǎn)稱(chēng)項(xiàng)目）在右部的某個(gè)地方加點(diǎn)的產(chǎn)生式加點(diǎn)的目的是用來(lái)表示分析過(guò)程中的狀態(tài)例 A

XYZ對(duì)應(yīng)有四個(gè)項(xiàng)目

A

·XYZ A

X·YZ A

XY·Z A

XYZ·例 A

只有一個(gè)項(xiàng)目和它對(duì)應(yīng) A

·

4.5LR分析器4.5.3構(gòu)造SLR分析表4.5

LR分析器構(gòu)造SLR分析表的兩大步驟1、從文法構(gòu)造識(shí)別可行前綴的DFA2、從上述DFA構(gòu)造分析表4.5LR分析器構(gòu)造SLR分析表的兩大步驟4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA

1）拓廣文法

E

E+T|T T

T

F|F F

(E)|id

4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA

1）拓廣文法

E

E

E

E+T|T T

T

F|F F

(E)|id

4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA 2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0:

E

·E4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA 2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0:

E

·E E

·E+T E

·T4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA 2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0:

E

·E E

·E+T E

·T T

·T

F T

·F4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA 2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0:

E

·E E

·E+T E

·T T

·T

F T

·F F

·(E) F

·id4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA 2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0:

E

·E (核心項(xiàng)目) E

·E+T E

·T (非核心項(xiàng)目， T

·T

F 通過(guò)對(duì)核心項(xiàng)目求閉包

T

·F 而獲得) F

·(E) F

·id4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA 2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0: I1:

E

·E E

E·

E

·E+T E

E·+T

E

·T T

·T

F T

·F F

·(E) F

·id E4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFAE4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA 2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0: I1:

E

·E E

E·

E

·E+T E

E·+T

E

·T T

·T

F I1:=goto(I0,E) T

·F F

·(E) F

·id E4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFAE4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA 2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0: I1:

E

·E E

E· E

·E+T E

E·+T

E

·T T

·T

F I2: T

·F E

T·

F

·(E) T

T·

F

F

·id ET4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFAET4.5

LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFA

2）構(gòu)造LR(0)項(xiàng)目集規(guī)范族I0: I1:

E

·E E

E·

E

·E+T E

E·+T

E

·T T

·T

F I2: T

·F E

T·

F

·(E) T

T·

F

F

·id I3:

T

F·

ETF4.5LR分析器1、從文法構(gòu)造識(shí)別可行前綴的DFAETF4.5

LR分析器I0: I4:

E

·E F

(·E) E

·E+T E

·T T

·T

F T

·F F

·(E) F

·id

(4.5LR分析器I0: I4:(4.5

LR分析器I0: I4:

E

·E F

(·E) E

·E+T E

·E+T E

·T E

·T T

·T

F T

·T

F T

·F T

·F F

·(E) F

·(E) F

·id F

·id

(4.5LR分析器I0: I4:(4.5

LR分析器I0: I4:

E

·E F

(·E) E

·E+T E

·E+T E

·T E

·T T

·T

F T

·T

F T

·F T

·F F

·(E) F

·(E) F

·id F

·id

I5:

F

id·

(id4.5LR分析器I0: I4:(id4.5

LR分析器I1I0EI3I2I4I5TF(id

4.5LR分析器I1I0EI3I2I4I5TF(id4.5

LR分析器I1I0EI3I2I4I5TF(idI1:

E

E· E

E·+T

4.5LR分析器I1I0EI3I2I4I5TF(idI14.5

LR分析器I1I0EI3I2I4I5TF(idI1:

E

E· E

E·+TI6:

E

E+·T

T

·T

F

T

·F

F

·(E)

F

·id+4.5LR分析器I1I0EI3I2I4I5TF(idI14.5

LR分析器I1I0EI3I2I4I5TF(idI1: I2:

E

E·

E

T· E

E·+T T

T·

FI6:

E

E+·T

T

·T

F

T

·F

F

·(E)

F

·id+4.5LR分析器I1I0EI3I2I4I5TF(idI14.5

LR分析器I1I0EI3I2I4I5TF(idI1: I2:

E

E·

E

T· E

E·+T T

T·

FI6: I7:

E

E+·T T

T

·F

T

·T

F

F

·(E)

T

·F F

·id

F

·(E)

F

·id+

4.5LR分析器I1I0EI3I2I4I5TF(idI14.5

LR分析器I1I0EI3I2I4I5TF(idI3: T

F·

無(wú)狀態(tài)轉(zhuǎn)換

4.5LR分析器I1I0EI3I2I4I5TF(idI34.5

LR分析器I1I0EI3I2I4I5TF(idI4: F

(·E) E

·E+T E

·TT

·T

F T

·F F

·(E) F

·id

4.5LR分析器I1I0EI3I2I4I5TF(idI44.5

LR分析器I1I0EI3I2I4I5TF(idI4: I8:F

(·E) F

(E·)E

·E+T E

E·+T

E

·TT

·T

F T

·F F

·(E) F

·id

E4.5LR分析器I1I0EI3I2I4I5TF(idI44.5

LR分析器I1I0EI3I2I4I5TF(idI4: I8:F

(·E) F

(E·)E

·E+T E

E·+T

E

·TT

·T

F I2:T

·F E

T·F

·(E) T

T·

FF

·id

TE4.5LR分析器I1I0EI3I2I4I5TF(idI44.5

LR分析器I1I0EI3I2I4I5TF(idI4: I8:F

(·E) F

(E·)E

·E+T E

E·+T

E

·TT

·T

F I2:T

·F E

T·F

·(E) T

T·

FF

·id I3:

T

F·

TFE4.5LR分析器I1I0EI3I2I4I5TF(idI44.5

LR分析器I1I0EI3I2I4I5TF(idI4: I8:F

(·E) F

(E·)E

·E+T E

E·+T

E

·TT

·T

F I2:T

·F E

T·F

·(E) T

T·

FF

·id I3:

T

F·

I4:

F

(·E)

... TF(E4.5LR分析器I1I0EI3I2I4I5TF(idI44.5

LR分析器I1I0EI3I2I4I5TF(idI4: I8:F

(·E) F

(E·)E

·E+T E

E·+T

E

·TT

·T

F I2:T

·F E

T·F

·(E) T

T·

FF

·id I3:

T

F·

I4:

I5:

F

(·E)

F

id·

... TF(idE4.5LR分析器I1I0EI3I2I4I5TF(idI44.5

LR分析器I1I0EI3I2I4I5TF(idI5:F

id·

無(wú)狀態(tài)轉(zhuǎn)換4.5LR分析器I1I0EI3I2I4I5TF(idI54.5

LR分析器I1I0+EI6I3I2I4I8I7I5指向I2指向I3T*F(Eidid(FT4.5LR分析器I1I0+EI6I3I2I4I8I7I54.5

LR分析器I1I0+指向I7EI6I9I3I2I4I11I8I7I10*TI5指向I4指向I3指向I5指向I4指向I5指向I6指向I2指向I3F(FTid*id(F(Eid+)id(FTE

E

E+T

E+T

F

E+T

id

E+T

F

id把所有狀態(tài)都作為接受狀態(tài)這是一個(gè)DFAE+T

F

的所有前綴都可接受4.5LR分析器I1I0+指向I7EI6I9I3I2I44.5

LR分析器I0:

E

·E E

·E+T E

·T T

·T

F T

·F F

·(E) F

·id也可以構(gòu)造一個(gè)識(shí)別可行前綴的NFAN4.5LR分析器I0: 也可以構(gòu)造一個(gè)識(shí)別可行前例子1.給出接受文法S->(L)|aL->L,S|S的活前綴的一個(gè)DFA例子1.給出接受文法答案-1答案-1例子2.求接受文法S->Aa|bAc|dc|bdaA->d的活前綴DFA和SLR(1)分析表例子2.求接受文法答案-2（DFA）答案-2（DFA）答案-2（狀態(tài)分析表）答案-2（狀態(tài)分析表）4.5

LR分析器構(gòu)造SLR分析表的兩大步驟1、從文法構(gòu)造識(shí)別可行前綴的DFA2、從上述DFA構(gòu)造分析表4.5LR分析器構(gòu)造SLR分析表的兩大步驟4.5

LR分析器例 SLR(1)文法的描述能力有限S

V=ES

EV

EV

idE

VI0:S

·S

S·V=ES·EV

·

EV·idE

·VI2:S

V·=EE

V·

V第一項(xiàng)目使得action[2,=]=s6第二項(xiàng)目使得 action[2,=]為按EV歸約，因?yàn)?是E的一個(gè)后繼符=是E的一個(gè)后繼符：S$

V=E$

E=E$4.5LR分析器例 SLR(1)文法的描述能力有限S4.5

LR分析器例 SLR(1)文法的描述能力有限S

V=ES

EV

EV

idE

VI0:S

·S

S·V=ES·E

V

·

EV·idE

·V

I2:S

V·=EE

V·

V第一項(xiàng)目使得action[2,=]=s6第二項(xiàng)目使得 action[2,=]為按EV歸約，因?yàn)?是E的一個(gè)后繼符在所關(guān)注場(chǎng)合E的后繼是$：S$

V=E$

E=E$

S$

E

$

V$4.5LR分析器例 SLR(1)文法的描述能力有限S4.5

LR分析器4.5.4

構(gòu)造規(guī)范的LR分析表LR(1)項(xiàng)目：

重新定義項(xiàng)目，讓它帶上搜索符，成為如下形式

[A

·

,a]LR(1)項(xiàng)目[A

·

,a]對(duì)可行前綴

有效： 如果存在著推導(dǎo)S

*rm

Aw

rm

w，其中：

=

；a是w的第一個(gè)符號(hào)，或者w是

且a是$4.5LR分析器4.5.4構(gòu)造規(guī)范的LR分析表4.5

LR分析器例 S

BB B

bB|a 從最右推導(dǎo)S

*rm

bbBba

rm

bbbBba看出：

[B

b·B,b]對(duì)可行前綴

=bbb是有效的 對(duì)于項(xiàng)目[A

·

,a]，當(dāng)

為空時(shí)，是根據(jù)搜索符a來(lái)填表（歸約項(xiàng)目），而不是根據(jù)A的后繼符來(lái)填表4.5LR分析器例 SBB4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/a4.5LR分析器S·S,$I04.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/aB

·bB,b/aB

·a,b/aI3B

a·,b/aI4ab4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/aB

·bB,b/aB

·a,b/aI3B

a·,b/aI4aabbS

BB·,$I5B

b·B,$B

·bB,$B

·a,$I6B

bB·,$I9B

a·,$I7B

bB·,b/aI8BbbBaaB4.5LR分析器S·S,$I0S4.5

LR分析器構(gòu)造規(guī)范的LR分析表(1)基于LR(1)項(xiàng)目來(lái)構(gòu)造識(shí)別G

可行前綴的DFA(2)從Ii構(gòu)造分析器的狀態(tài)i,狀態(tài)i的action函數(shù)如下確定如果[A

·a

,b]在Ii中，且goto(Ii,a)=Ij，那么置action[i,a]為sj如果[A

·

,

a]在Ii中，且A

S

，那么置action[i,a]為rj

如果[S

S·,

$]在Ii中，那么置action[i,$]=acc 如果用上面規(guī)則構(gòu)造出現(xiàn)了沖突，那么文法就不是LR(1)的4.5LR分析器構(gòu)造規(guī)范的LR分析表4.5

LR分析器先前基于SLR(1)有移進(jìn)-歸約沖突的例子，在基于規(guī)范LR(1)時(shí)無(wú)沖突S

V=ES

EV

EV

idE

VI0:S

·S，$S·V=E,$S·E,$V

·

E,=/$V·id,=/$E

·V,$I2:S

V·=E,$E

V·,$V4.5LR分析器先前基于SLR(1)有移進(jìn)-歸約沖突的例4.5

LR分析器4.5.5

構(gòu)造LALR分析表研究LALR的原因規(guī)范LR分析表的狀態(tài)數(shù)偏多LALR特點(diǎn)LALR和SLR的分析表有同樣多的狀態(tài)，比規(guī)范LR分析表要小得多LALR的能力介于SLR和規(guī)范LR之間LALR的能力在很多情況下已經(jīng)夠用LALR分析表構(gòu)造方法通過(guò)合并規(guī)范LR(1)項(xiàng)目集來(lái)得到4.5LR分析器4.5.5構(gòu)造LALR分析表4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/aB

·bB,b/aB

·a,b/aI3B

a·,b/aI4aabbS

BB·,$I5B

b·B,$B

·bB,$B

·a,$I6B

bB·,$I9B

a·,$I7B

bB·,b/aI8BbbBaaBI4和I7僅搜索符不一樣4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/aB

·bB,b/aB

·a,b/aI3B

a·,b/aI4aabbS

BB·,$I5B

b·B,$B

·bB,$B

·a,$I6B

bB·,$I9B

a·,$I7B

bB·,b/aI8BbbBaaBI4和I7合并4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/aB

·bB,b/aB

·a,b/aI3B

a·,b/aI4aabbS

BB·,$I5B

b·B,$B

·bB,$B

·a,$I6B

bB·,$I9B

a·,$I7B

bB·,b/aI8BbbBaaB輸入為bbabba$4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/aB

·bB,b/aB

·a,b/aI3B

a·,b/aI4aabbS

BB·,$I5B

b·B,$B

·bB,$B

·a,$I6B

bB·,$I9B

a·,$I7B

bB·,b/aI8BbbBaaB輸入為bba$4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/aB

·bB,b/aB

·a,b/aI3B

a·,b/aI4aabbS

BB·,$I5B

b·B,$B

·bB,$B

·a,$I6B

bB·,$I9B

a·,$I7B

bB·,b/aI8BbbBaaB有三組同心集，都合并4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/a/$B

·bB,b/a/$B

·a,b/a/$I36B

a·,b/a/$I47aabbS

BB·,$I5B

bB·,b/a/$I89BbBa4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/a/$B

·bB,b/a/$B

·a,b/a/$I36B

a·,b/a/$I47aabbS

BB·,$I5B

bB·,b/a/$I89BbBa棧 輸入0 bba$4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/a/$B

·bB,b/a/$B

·a,b/a/$I36B

a·,b/a/$I47aabbS

BB·,$I5B

bB·,b/a/$I89BbBa棧 輸入0b36 ba$4.5LR分析器S·S,$I0S4.5

LR分析器S

·S,$I0S

·BB,$B

·bB,b/aB

·a,b/aS

S·,$I1S

B·B,$B

·bB,$B

·a,$I2SBB

b·B,b/a/$B

·bB,b/a/$B

·a,b/a/$I36B

a·,b/a/$I47aabbS

BB·,$I5B

bB·,b/a/$I89BbBa棧 輸入0b36b36a$4.5LR分析器S·S,$I0S4.5

LR分析器