SLR(1)分析方法.

Presentation on theme: "SLR(1)分析方法."— Presentation transcript:

1 SLR(1)分析方法

2 例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]

3 状态 $ + × 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

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

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

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

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

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

9 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

10 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

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

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

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

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

15 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 $,)

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

17 例子：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

18 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

19 分析栈 符号栈 输入串 分析动作 转向状态 0 # id id+id$# S5 0,5 #id id+id$# R6 4
分析栈 符号栈 输入串 分析动作 转向状态 # id id+id$# S5 0, #id id+id$# R 0, #P id+id$# R 0, #T id+id$# S8 0,7, #T id+id$# S5 0,7,8, #Tid id$# R 0,7,8, #TP id$# R 0, #T id$# R 0, #E id$# S3 0,1, #E id$# S5 0,1,3, #E+id $# R 0,1,3, #E+P $# R 0,1,3, #E+T $# R 0, #E $# S2 0,1, #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]