SLR(1)分析方法

例1：一个非LR(0)文法例: S→E $ [1] E→E + T [2] E→T [3] T→T  P [4] T→P [5] G[s]: S→E $ [1] E→E + T [2] E→T [3] T→T  P [4] T→P [5] P→id [6] P→( E ) [7]

状态 $ + × id ( ) # ... 7 R3 R3/ S8 11 R2 R2/ 状态 $ + × id ( ) # ... 7 R3 G[s]: S→E $ [1] E→E + T [2] E→T [3] T→T  P [4] T→P [5] P→id [6] P→( E ) [7] 状态 $ + × id ( ) # ... 7 R3 R3/ S8 11 R2 R2/ 状态 $ + × id ( ) # ... 7 R3 R3/ S8 S→  E $ [1] E→  E+T [2] E→  T [3] T→  TP [4] T→  P [5] P→  id [6] P→  (E) [7] E $ S→ E  $ E→ E  + T   1 2 + S→ E $    P id E→ E +  T T→  T  P T→  P P→  id P→  (E) 3 4 P + T→ P    ( T id P→ id    5 ( E→ T  T→ T   P 7 id T id E→ E+T  T→ T  P 11 P → (  E ) E→  E+T E→  T T→  TP T→  P P→  id P→  (E) 6   T→ T   P P→  id P→  (E) 8 8 E P→ (E  ) E→ E  +T 12 ( P ) ( T→ T * P  9 P T 7 P→(E)  10 4 GE 的LRSM0

LR(0)分析方法的不足 LR(0)方法对文法的要求严格。 LR(0)方法容易出现冲突状态。

{ A → , D→  d  }，则存在移入-归约冲突 。 可以如下解决： 非LR(0)文法的原因 1、如果某个状态有如下项目集： { A → , D→  d  }，则存在移入-归约冲突 。 可以如下解决： 若当前输入符在A的Follow集中，则应用A → 归约； 若当前输入符为d则应移入 。 而对当前输入符为d， d又 在A的Follow集中，则无法解决。

非LR(0)文法的原因（续） 如果某个状态有如下项目集： { A → , B → }，则存在着归约-归约冲突 。 可以如下解决： 若用A → 归约，则当前输入符应在A的Follow集中 若用B → 归约，则当前输入符应在B 的Follow集 当前输入符应在A的Follow集中又在B 的Follow集 中，则无法解决。

SLR(1)分析条件 LRSM0中存在着状态： { A1 →1， …， An →n， B1→1 a1r1， Bm→ mamrm } 则集合： Follow(A1)、…、Follow(An)、{a1, …, am} 两两相交为空。注： a1, …, am中可以有相同者。

SLR(1)分析表的构造 与LR(0)分析表的构造不同之处只是action表中归约项的填写，其他都一样。 若AISk，则对任意aVT，aFollow(A)，令action(ISk, a)=Rj，其中产生式A的编号为j，表示用编号为j的产生式进行归约。

State Action－ Lookahead GoTo Follow(S)={#} Follow(E)={$,+,)} GE: S→E $ [1] E→E + T [2] E→T [3] T→T  P [4] T→P [5] P→id [6] P→( E ) [7] Follow(S)={#} Follow(E)={$,+,)} Follow(T)={$,+,), } Follow(P) ={$,+,), } E→ T  T→ T   P 7 T→ T   P P→  id P→  (E) 8 x  E→ E+T  [2] T→ T  P [4] 11 8 State Action－ Lookahead GoTo # ＋  id ( ) $ E T P S5 S6 1 7 4 S3 S2 … 11 12 S10 R3 S8 R3 R3 R2 S8 R2 R2

State Action－ Lookahead GoTo # ＋  id ( ) $ E T P S5 S6 1 7 4 S3 S2 2 S5 S6 1 7 4 S3 S2 2 Acc 3 11 R5 5 R6 6 12 R3 S8 8 9 R4 10 R7 R2 S10

SLR(1)驱动器 与LR(0)驱动程序相同

SLR(1)文法定义 对于一个文法，若按照上述算法构造的分析表中没有冲突动作，则称该文法为SLR(1)文法。 从定义可以看出SLR(1)分析方法是用LR(0)项目构成的LRSM0来识别活前缀，因此它们的状态数相同，但是，由于LR(0)方法只看状态栈的内容而SLR(1)方法还要向前看展望符，因此SLR(1)文法要比LR(0)文法应用广。

SLR(1)与LR(0) SLR(1)和LR(0)具有相同的状态机 LR(0)归约时不考虑当前输入符，SLR(1)在动作有冲突时考虑输入符，用follow集来解决冲突，因此SLR(1)要比LR(0)分析能力强

括号文法定义如下： 练习题 Z → S$ S → (S) S |  构造该文法的SLR(1)分析表，并给出输入流( )( )$的SLR(1)分析过程。 follow Z # S $,)

2 3 ( S ) （ S 4 1 5 S Z → S$ S → (S)S S →  6 $ ( S (S)S[2] S (S)S[2] 3 ( S ) （ S S (S)S[2] S (S)S[2] S  [3] 4 Z S$ [1] 1 Z S$ [1] 5 $ S （ ） $ # S Z S2 R3 1 S5 2 3 S4 4 6 5 acc R2 Z → S$ S → (S)S S →  S (S)S[2] 6 follow Z # S $,)

Z → S$ [1] S → (S) S [2] |  [3] 状态栈 符号栈 输入串 Action Goto 0 # ( )( )$# 0 # ( )( )$# 02 # ( )( )$# 023 # ( S )( )$# 0234 # ( S ) ( )$# 02342 # ( S)( )$# 023423 # ( S)( S )$# 0234234 # ( S) (S ) $# 02342346 #( S)(S ) S $# 02346 # ( S)S $# 01 # S $# 015 # S$ # （ ） $ # S Z S2 R3 1 S5 2 3 S4 4 6 5 acc R2 Z → S$ [1] S → (S) S [2] |  [3]

例子：G[s]: S→E $ [1] E→E + T [2] E→T [3] T→T  P [4] T→P [5] P→id [6] P→( E ) [7] S→  E $ [1] E→  E+T [2] E→  T [3] T→  TP [4] T→  P [5] P→  id [6] P→  (E) [7] E $ S→ E  $ E→ E  + T   1 2 + S→ E $    P id E→ E +  T T→  T  P T→  P P→  id P→  (E) 3 4 P + T→ P    ( T id P→ id    5 ( E→ T  T→ T   P 7 id T id E→ E+T  T→ T  P 11 P → (  E ) E→  E+T E→  T T→  TP T→  P P→  id P→  (E) 6   T→ T   P P→  id P→  (E) 8 8 E P→ (E  ) E→ E  +T 12 ( P ) ( T→ T * P  9 P T 7 P→(E)  10 4 GE 的LRSM0

State Action－ Lookahead GoTo # ＋  id ( ) $ E T P S5 S6 1 7 4 S3 S2 2 S5 S6 1 7 4 S3 S2 2 Acc 3 11 R5 5 R6 6 12 R3 S8 8 9 R4 10 R7 R2 S10

分析栈 符号栈 输入串 分析动作 转向状态 0 # id id+id$# S5 0,5 #id id+id$# R6 4 分析栈 符号栈 输入串 分析动作 转向状态 0 # id id+id$# S5 0,5 #id id+id$# R6 4 0,4 #P id+id$# R5 7 0,7 #T id+id$# S8 0,7,8 #T id+id$# S5 0,7,8,5 #Tid +id$# R6 9 0,7,8,9 #TP +id$# R4 7 0,7 #T +id$# R3 1 0,1 #E +id$# S3 0,1,3 #E+ id$# S5 0,1,3,5 #E+id $# R6 4 0,1,3,4 #E+P $# R5 11 0,1,3,11 #E+T $# R2 1 0,1 #E $# S2 0,1,2 #E$ # Accept G[E]: S→E $ [1] E→E + T [2] E→T [3] T→T  P [4] T→P [5] P→id [6] P→( E ) [7]