第五章 自底向上分析方法 LR(0)分析法

活前缀状态机提供的语法分析信息： 1、移入信息：如果活前缀状态机中状态ISi包含形如Aa的项目，即ISi有a的输出边，其中a是终极符，则表示ISi状态遇当前输入符为a时应将其移入符号栈，状态机沿着其a的输出边转向其后继状态。 2、归约信息：如果状态ISi包含形如X Y1 Y2 ……Yn的项目，则表示ISi状态可按该产生式做归约动作，归约后状态机回退n个(Y1 Y2 ……Yn的长度)状态至状态ISj，随后沿着ISj的X输出边转向其后继状态。

语法分析过程的直观描述： a d e c # 符号栈 # a B d e c B 状态栈 2 5 6 3 4 1 例1 G[S]: S → aBc[1] B → e[2] B → dB[3] S → aBc [1] a S → aBc[1] B → e[2] B → dB[3] 1 B S → aBc[1] 2 S →aBc[1] 3 c e B → e [2] 4 d d e B → dB [3] B → e[2] B → dB[3] 5 B B → dB [3] 6

# X1 X2 … Xk Xt Si0 Si1 Si2 Sik Sit aiai+1…an # # X1 X2 … Xk Xt Si0 活前缀状态机提供的语法分析信息（续） 设当前格局是： # X1 X2 … Xk Xt Si0 Si1 Si2 Sik Sit aiai+1…an # 移入动作：设Sit的ai输入边所指向的状态为S* # X1 X2 … Xk Xt Si0 Si1 Si2 Sik Sit ai S* 归约动作：设按A→Xk+1Xk+2…Xt进行归约，则首先归约为A # X1 X2 … Xk Si0 Si1 Si2 Sik A Sik的A输出边所指向的状态设为S*，即GO（ Sik ，A）= S*则格局变为： # X1 X2 … Xk Si0 Si1 Si2 Sik A S*

LR分析模型 LR(0)分析器的结构 Input a1 … ai … an # LR分析驱动器 Output St Xt … action goto 状态栈　符号栈 　分析栈 分析表 LR分析模型

LR(0)分析表 LR分析表是提取活前缀状态机LRSM中的信息形成的矩阵形式的表。包括Action表和GoTo表两部分： Action矩阵：行代表状态，列代表输入符，而矩阵元素则表示相应的分析动作：移入Shift / 归约Reduce / 成功Accept / 失败Error GoTo矩阵：行代表状态，列则代表非终极符，而矩阵元素则表示归约后的转向状态。

a 1 A d 3 5 B b c 6 2 4 Action 例：构造G[S]的基于LR(0) 方法的Action矩阵。 a b c d # S → aAd[1] A → Bc[2] B → b[3] a b c d # S1 1 S2 2 R3 3 S5 4 S6 5 Acc 6 R2 S → aAd[1] a S → aAd[1] A → Bc[2] B → b[3] 1 A d S → aAd [1] 3 S →a A d[1] 5 B b c A → Bc[2] 6 2 B → b[3] A → Bc[2] 4

GoTo表 例：构造G[S]的基于LR(0) 方法的GoTo矩阵。 G[S]: S → aAd[1] A → Bc[ 2] B → b[3] S A B 1 3 4 2 5 6 S → aAd [1] a S → aAd [1] A → Bc[2] B → b[3] 1 A S → aAd [1] 3 d S →a A d[1] 5 B b c A → Bc[2] 4 A → Bc[2] 6 2 B → b[3]

a b c d # S1 1 S2 2 R3 3 S5 4 S6 5 6 R2 S A B 3 4 例：构造G[S]的分析表。 S → aAd[1] A → Bc[ 2] B → b[3] Action表 GoTo表 a b c d # S1 1 S2 2 R3 3 S5 4 S6 5 Acc 6 R2 S A B 3 4

LR(0)驱动程序 首先置状态栈、符号栈和输入流的开始格局为： （S1, #, a1a2…an#） 则： 1移入：若当前格局为: （S1S2…Sn, #X1X2…Xn, aiai+1…an#）， 且action(Sn, ai)=Sj，aiVT，则ai入符号栈，第j个状态Sj入状态栈。即移入后的格局变为： （S1S2…Sn Sj, #X1X2…Xnai, ai+1…an#）

LR(0)驱动程序（续1） 2归约：若当前格局为： （S1S2…Sn, #X1X2…Xn, aiai+1…an#） 且action(Sn, ai)=Rj，aVT{#}，则按照第j个产生式进行归约，符号栈和状态栈相应元素退栈，归约后的文法符号和S入栈。假设第j个产生式为A，k=|| (=Xn-k+1…Xn)，则归约后的格局变为： （S1S2…Sn-kS, #X1X2…Xn-kA, aiai+1…an#） 其中S=GoTo(Sn-k, A)。

LR(0)驱动程序（续2） 3.若状态栈的栈顶状态为Si，输入流当前值为#，且action(Si, #)=Accept，则分析成功。 4.若状态栈的栈顶状态为Si，输入流当前值为a，且action(Si, a)=Error或空，则转向出错处理程序。

LR(0)文法 形如A→•的项目称为归约型项目 形如A→•的项目称为移入型项目 若LRSM0中存在一个状态（项目集）既包含移入型项目又包含归约型项目，则说有移入-归约冲突；如果同时存在两个或两个以上归约型项目，则说有归约-归约冲突。 若LRSM0中任何状态都不存在冲突，则称该文法为LR(0)文法。

练习：构造LR(0)状态机 S  E $[1] E  E + T[2] E  T[3] T  id[4] T ( E ) [5]

T T 6 9 ( ( 5 id id E id ( E + 1 3 7 + $ ) T 2 4 8 T→( E) E→ E+T S  E $ E  E + T E  T T  id T ( E ) T T 6 T→( E) E→ E+T E→ T T→ id T→ ( E ) S→ E $ E→ E+T E→ T T→ id T→ ( E ) 9 E→T  ( ( 5 T→id  id id E id ( E + 1 S→E $ E→E +T 3 E→E+  T T→ id T→ (E) 7 T→(E ) E→E +T + $ ) T 2 S→E $ 4 E→E+T  8 T→(E) 

1 5 3 4 9 6 7 8 T ( id E ) + 2 $ S→ E $ E→ E+T E→ T T→ id S→ E $ E→ E+T E→ T T→ id T→ ( E ) 1 S→E $ E→E +T 5 T→id  3 E→E+  T T→ (E) 4 E→E+T  9 E→T  6 T→( E) 7 T→(E ) 8 T→(E)  T ( id E ) + 2 S→E $ $

$ + id ( ) # E T S5 S6 1 9 S2 S3 2 Acc 3 4 R2 5 R4 6 7 S8 8 R5 R3 Action表 GoTo表 S  E $[1] E  E + T[2]| T[3] T  id[4]| ( E )[5] $ + id ( ) # E T S5 S6 1 9 S2 S3 2 Acc 3 4 R2 5 R4 6 7 S8 8 R5 R3

LR(0)分析实例 状态栈 符号栈 输入串 Action Goto 0 # i+i$# 05 # i +i$# 09 # T +i$# G[S]: S  E $[1] E  E + T[2]| T[3] T  id[4]| ( E )[5] LR(0)分析实例 分析： i+i$ 状态栈 符号栈 输入串 Action Goto 0 # i+i$# 05 # i +i$# 09 # T +i$# 01 # E +i$# 013 # E+ i$# 0135 # E+i $# 0134 # E+T $# 01 # E $# 012 # E$ # A[0,i]=S5 reduce4 G[0,T]= 9 reduce3 G[0,E]= 1 A[1,+]=S3 A[3,i]=S5 reduce4 G[3,T]= 4 reduce2 G[0,E]= 1 A[1, $]=S2 accept