3.语法分析-LR(0)方法-2

第四章：自底向上语法分析

LR(0)语法分析

构造下列文法的LR(0)状态机。G[S]: S→aAd[1]

A→Bc[2]

B→b[3]

例子bG[S]的LRSM0da0

S→

aAd[1]

NO

S→a

Ad[1]

A→

Bc[2]B→

b[3]

1

NO2

B→b

[3]

NO

S→aAd

[1]5

NOAG[S]: S→aAd[1]

A→Bc[2]

B→b[3]

A→B

c[2]

4

NO

A→Bc

[2]6

NOc

S→aA

d[1]3

NOB构造过程：

1、移入信息：如果活前缀状态机中状态ISi包含形如A

a

的项目，即ISi有a的输出边，其中a是终极符，则表示ISi状态遇当前输入符为a时应将其移入符号栈，状态机沿着其a的输出边转向其后继状态。

2、归约信息：如果状态ISi包含形如X

Y1Y2……Yn

的项目，则表示ISi状态可按该产生式做归约动作，约后状态机回退n个(Y1Y2……Yn的长度)状态至状态ISj，随后沿着ISj的X输出边转向其后继状态。1.活前缀状态机提供的语法分析信息bda0

S→

aAd[1]

S→a

Ad[1]

A→

Bc[2]B→

b[3]

12

B→b

[3]S→aAd

[1]5A

A→B

c[2]

4

A→Bc

[2]6c

S→aA

d[1]3B语法分析过程的直观描述：#0符号栈状态栈a1b2B4c6A3d5ab#cd#X1X2…Xk…XtSi0Si1Si2…Sik…Sit

aiai+1…an#移入动作：设Sit的ai输入边所指向的状态为S*#X1X2…Xk…XtSi0Si1Si2…Sik…SitaiS*归约动作：设按A→Xk+1Xk+2…Xt进行归约，则首先归约为ASik的A输出边所指向的状态设为S*，则格局变为：#X1X2…XkSi0Si1Si2…SikAS*设当前格局是：#X1X2…XkSi0Si1Si2…SikA活前缀状态机提供的语法分析信息（续）2.LR分析模型OutputStack#an…ai…a1LR分析驱动器gotoactionInputStXt……语法分析表2.1LR分析表Action表：

状态×(VT∪{#})

动作动作包括：Shift/Reduce/Accept/Error（移入、归约、成功、失败）Goto表：

状态×VN

状态|error2.2LR(0)分析表的构造假设ISk为LR(0)项目集，action矩阵：若A

a

ISk，且GO(ISk,a)=ISi，a

VT，则action(ISk,a)=Si，表示移入动作。若A

ISk，则对任意a

VT

{#}，令action(ISk,a)=Rj，其中产生式A

的编号为j，表示用编号为j的产生式进行归约。若Z

ISk，且Z为拓广产生式的左部非终极符(文法的开始符)，则action(ISk,#)=Accept。其它情形，则Error(n)，表示出错标志，也可不填。goto矩阵：若GO(ISk,A)=ISi，A

VN，则goto(ISk,A)=i。bda0

S→

aAd[1]

S→a

Ad[1]

A→

Bc[2]B→

b[3]

12

B→b

[3]S→aAd

[1]5A例：构造G[S]的基于LR(0)方法的Action矩阵。G[S]: S→aAd[1]

A→Bc[2]

B→b[3]

A→B

c[2]4

A→Bc

[2]6c

S→aA

d

[1]3Babcd#0S11S22R3

R3R3R3R33S54S65Acc6R2R2R2R2R2Actionbda0

S→

aAd[1]

S→a

Ad[1]A→

Bc[2]B→

b[3]

12

B→b

[3]S→aAd

[1]5A例：构造G[S]的基于LR(0)方法的GoTo矩阵。G[S]: S→aAd[1]

A→Bc[2]

B→b[3]

A→B

c[2]

4

A→Bc

[2]6c

S→aA

d

[1]3BSAB013423456GoTo表GoTo表Action表SAB34abcd#0S11S22R3

R3R3R3R33S54S65Acc6R2R2R2R2R2例：构造G[S]的分析表。G[S]: S→aAd[1]

A→Bc[2]

B→b[3]

2.3LR分析表提供的信息合法性检查信息[A

a

]移入/归约信息[A

a

][A

]移入/归约后的转向状态信息2.4LR驱动程序状态栈、符号栈和输入流的开始格局为：（#S1,#,a1a2…an#）移入：若当前格局为（#S1S2…Sn,#X1X2…Xn,aiai+1…an#），且Action(Sn,ai)=Sj，ai

VT，则ai入符号栈，第j个状态Sj入状态栈。即移入后的格局变为：（#S1S2…SnSj,#X1X2…Xnai,ai+1…an#）2.4LR驱动程序归约：若当前格局为（#S1S2…Sn,#X1X2…Xn,aiai+1…an#），且Action(ISn,a)=Rj，a

VT

{#}，则按照第j个产生式进行归约，符号栈和状态栈相应元素退栈，归约后的文法符号入栈。假设第j个产生式为A

，k=|

|(

=Xn-k+1…Xn)，则归约后的格局变为： （#S1S2…Sn-kS,#X1X2…Xn-kA,aiai+1…an#）其中S=Goto(Sn-k,A)。2.4LR驱动程序成功：若状态栈的栈顶状态为Si，输入流当前值为#，且action(Si,#)=Accept，则分析成功。失败：若状态栈的栈顶状态为Si，输入流当前值为a，且action(Si,a)=Error或空，则转向出错处理程序。构造LR(0)状态机

SE$[1]EE+T[2]ET[3]Tid[4]T(E)[5]2.5LR(0)分析实例0

S→

E$

E→

E+TE→

T

T→

idT→

(E)1

S→E

$E→E

+T

5

T→id

3

E→E+

T

T→

idT→

(E)

4

E→E+T

9

E→T

6

T→(

E)

E→

E+TE→

T

T→

idT→

(E)7

T→(E

)E→E

+T

8

T→(E)

TT(idETid)E+id((+2

S→E$

$$+id()#ET0S5S6191S2S32Acc3S5S644R2

R2R2R2R2R25R4R4R4R4R4R46S5S6797S3S88R5R5R5R5R5R59R3R3R3R3R3R3GoTo表Action表

SE$[1] EE+T[2]|T[3] Tid[4]|(E)[5]LR(0)分析实例状态栈符号栈输入串ActionGoto0 #i+i$#05 #i+i$# 09 #T+i$# 01 #E+i$# 013 #E+i$# 0135 #E+i$# 0134 #E+T$# 01 #E$# 012 #E$#分析：i+i$

G[S]: SE$[1] EE+T[2]|T[3] Tid[4]|(E)[5]

A[0,i]=S5reduce4G[0,T]=9reduce3G[0,E]=1A[1,+]=S3A[3,i]=S5reduce4G[3,T]=4reduce2G[0,E]=1A[1,$]=S2accept3.1LR(0)文法的限定条件定义：在可归前缀图中，如果一个状态含有两个或两个以上的以上的归约项目，则称有归