LR分析器SLR规范的LR课件

LR分析器（SLR，规范的LR）4.6-4.7LR分析器（SLR，规范的LR）4.6-4.7SLRSLR4.5

LR分析器4.5.3构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式4.5LR分析器4.5.3构造SLR分析表4.5

LR分析器4.5.3构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态4.5LR分析器4.5.3构造SLR分析表4.5

LR分析器4.5.3构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态exprexpr+term

4.5LR分析器4.5.3构造SLR分析表exprex4.5

LR分析器4.5.3构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态exprexpr+term*termfactor

4.5LR分析器4.5.3构造SLR分析表exprex4.5

LR分析器4.5.3构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态exprexpr+term*termfactor

4.5LR分析器4.5.3构造SLR分析表exprex4.5

LR分析器4.5.3构造SLR分析表术语：LR(0)项目（简称项目）在右部的某个地方加点的产生式加点的目的是用来表示分析过程中的状态例 A

XYZ对应有四个项目

A

·XYZ A

X·YZ A

XY·Z A

XYZ·例 A

只有一个项目和它对应 A

·

4.5LR分析器4.5.3构造SLR分析表4.5

LR分析器构造SLR分析表的两大步骤1、从文法构造识别可行前缀的DFA2、从上述DFA构造分析表4.5LR分析器构造SLR分析表的两大步骤4.5

LR分析器1、从文法构造识别可行前缀的DFA

1）拓广文法

E

E+T|T T

T

F|F F

(E)|id

4.5LR分析器1、从文法构造识别可行前缀的DFA4.5

LR分析器1、从文法构造识别可行前缀的DFA

1）拓广文法

E

E

E

E+T|T T

T

F|F F

(E)|id

4.5LR分析器1、从文法构造识别可行前缀的DFA4.5

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E

·E4.5LR分析器1、从文法构造识别可行前缀的DFA4.5

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E

·E E

·E+T E

·T4.5LR分析器1、从文法构造识别可行前缀的DFA4.5

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E

·E E

·E+T E

·T T

·T

F T

·F4.5LR分析器1、从文法构造识别可行前缀的DFA4.5

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E

·E E

·E+T E

·T T

·T

F T

·F F

·(E) F

·id4.5LR分析器1、从文法构造识别可行前缀的DFA4.5

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族I0:

E

·E (核心项目) E

·E+T E

·T (非核心项目， T

·T

F 通过对核心项目求闭包

T

·F 而获得) F

·(E) F

·id4.5LR分析器1、从文法构造识别可行前缀的DFA4.5

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族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、从文法构造识别可行前缀的DFAE4.5

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族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、从文法构造识别可行前缀的DFAE4.5

LR分析器1、从文法构造识别可行前缀的DFA 2）构造LR(0)项目集规范族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、从文法构造识别可行前缀的DFAET4.5

LR分析器1、从文法构造识别可行前缀的DFA

2）构造LR(0)项目集规范族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、从文法构造识别可行前缀的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·

无状态转换

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·

无状态转换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把所有状态都作为接受状态这是一个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也可以构造一个识别可行前缀的NFAN4.5LR分析器I0: 也可以构造一个识别可行前例子1.给出接受文法S->(L)|aL->L,S|S的活前缀的一个DFA例子1.给出接受文法答案-1答案-1例子2.求接受文法S->Aa|bAc|dc|bdaA->d的活前缀DFA和SLR(1)分析表例子2.求接受文法答案-2（DFA）答案-2（DFA）答案-2（状态分析表）答案-2（状态分析表）4.5

LR分析器构造SLR分析表的两大步骤1、从文法构造识别可行前缀的DFA2、从上述DFA构造分析表4.5LR分析器构造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第一项目使得action[2,=]=s6第二项目使得 action[2,=]为按EV归约，因为=是E的一个后继符=是E的一个后继符：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第一项目使得action[2,=]=s6第二项目使得 action[2,=]为按EV归约，因为=是E的一个后继符在所关注场合E的后继是$：S$

V=E$

E=E$

S$

E

$

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

LR分析器4.5.4

构造规范的LR分析表LR(1)项目：

重新定义项目，让它带上搜索符，成为如下形式

[A

·

,a]LR(1)项目[A

·

,a]对可行前缀

有效： 如果存在着推导S

*rm

Aw

rm

w，其中：

=

；a是w的第一个符号，或者w是

且a是$4.5LR分析器4.5.4构造规范的LR分析表4.5

LR分析器例 S

BB B

bB|a 从最右推导S

*rm

bbBba

rm

bbbBba看出：

[B

b·B,b]对可行前缀

=bbb是有效的 对于项目[A

·

,a]，当

为空时，是根据搜索符a来填表（归约项目），而不是根据A的后继符来填表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分析器构造规范的LR分析表(1)基于LR(1)项目来构造识别G

可行前缀的DFA(2)从Ii构造分析器的状态i,状态i的action函数如下确定如果[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 如果用上面规则构造出现了冲突，那么文法就不是LR(1)的4.5LR分析器构造规范的LR分析表4.5

LR分析器先前基于SLR(1)有移进-归约冲突的例子，在基于规范LR(1)时无冲突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)有移进-归约冲突的例4.5

LR分析器4.5.5

构造LALR分析表研究LALR的原因规范LR分析表的状态数偏多LALR特点LALR和SLR的分析表有同样多的状态，比规范LR分析表要小得多LALR的能力介于SLR和规范LR之间LALR的能力在很多情况下已经够用LALR分析表构造方法通过合并规范LR(1)项目集来得到4.5LR分析器4.5.5构造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分析器