LALR(1)分析方法.

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

1 LALR(1)分析方法

2 引进LALR（1）方法的目的 LR(1)语法分析方法的不足：
解决方法： 合并LR(1) 状态机中的等价状态. 在LR(0)状态机中用传播方式求每个项目集的展望符.

3 LALR(1)的思想来源 A→B, a B→, b LR(1)状态机中扩展项集A的闭包生成与LR(0)是一样的，只是增加了该状态下对B的展望符集bFirst(a)部分，以增加对B分析完成后(B→)是否进行归约的精准判断。 所以LR(1)状态机中会由于展望符的不同，使得同一核心项目集被分裂多个不同状态，造成状态数目的剧烈增加，导致时间和空间上的急剧上升； LALR(1)考虑将LR(1)中的核心相同的状态进行合并，从而大大减少状态数。

4 S R L = L a a b R b a a L b R b R L ZS SL=R SR LaR Lb RL #
ZS SL=R SR LaR Lb RL # = # 1 ZS # 6 SL=  R R  L LaR Lb # 7 SL=R  # S R L = 2 SL=R RL # L a a b 9 RL # R b a a 8 LaR RL LaR Lb # 5 LaR RL LaR Lb # = 3 SR # L b R 4 Lb =# b R L 13 LaR # 12 Lb # 10 LaR #= 11 RL # = 4

5 S R L = L a a b R b a a L b R b R L ZS SL=R SR LaR Lb RL #
ZS SL=R SR LaR Lb RL # = # 1 ZS # 6 SL=  R R  L LaR Lb # 7 SL=R  # S R L = 2 SL=R RL # L a a b 9 RL # R b a a 8 LaR RL LaR Lb # 5 LaR RL LaR Lb # = 3 SR # L b R 4 Lb =# b R L 13 LaR # 12 Lb # 10 LaR #= 11 RL # = 状态4和状态12 状态5和状态8 状态9和状态11 状态10和状态13

6 相关术语 LR(1)项目的心 假设[A, b]是LR(1)项目，则称其中的LR(0)部分A为该项目的心.
状态（项目集）的心 假设S是LR(1)状态（项目集），则称其中的每个LR(1)项目的LR(0)部分组成的集合为该状态（项目集）的心. 同心状态 称LR(1)状态机中具有相同心的状态为同心状态.

7 用SameCoreState(S)表示所有与S同心的状态集合; 用Merge(SS)表示同心状态集SS中所有状态的项目的合并.具体定义如下：
用Core(S)表示状态S的心部分; 用SameCoreState(S)表示所有与S同心的状态集合; 用Merge(SS)表示同心状态集SS中所有状态的项目的合并.具体定义如下： Core(S)={LR0item | [LR0item, a]S} SameCoreState(S)={S’ | Core(S’)=Core(S)} Merge(SS)={LR1item | LR1itemS, SSS}

8 A B a1 b1 A B a2 b2 A B a1/a2 b2/b2
S1 A B a1 b1 S2 A B a2 b2 S1,2 A B a1/a2 b2/b2 Core(S1)=Core(S2)= { A, B} SameCoreState(S1)={S1, S2} Merge({S1, S2}) ={ [ A, a1], [ A, a2], [B, b1], [B, b2]} ={[ A, {a1/ a2}], [B, {b1/ b2}]}

9 例：构造下列文法的LALR(1)状态机. Z → S S → L= R S → R L → aR L → b R → L

10 S R L = L a a b R b a a L b R b R L ZS SL=R SR LaR Lb RL #
ZS SL=R SR LaR Lb RL # = # 1 ZS # 6 SL=  R R  L LaR Lb # 7 SL=R  # S R L = 2 SL=R RL # L a a b 9 RL # R b a a 8 LaR RL LaR Lb # 5 LaR RL LaR Lb # = 3 SR # L b R 4 Lb =# b R L 13 LaR # 12 Lb # 10 LaR #= 11 RL # = 10

11 S R L = L a a b R b a a L b R b R L ZS SL=R SR LaR Lb RL #
ZS SL=R SR LaR Lb RL # = # 1 ZS # 6 SL=  R R  L LaR Lb # 7 SL=R  # S R L = 2 SL=R RL # L a a b 9 RL # R b a a 8 LaR RL LaR Lb # 5 LaR RL LaR Lb # = 3 SR # L b R 4 Lb =# b R L 13 LaR # 12 Lb # 10 LaR #= 11 RL # = 状态4和状态12 状态5和状态8 状态9和状态11 状态10和状态13

12 S R L = L a b a a b R a a L b R R R b L ZS SL=R SR LaR Lb
ZS SL=R SR LaR Lb RL # = # 1 ZS # 6 SL=  R R  L LaR Lb # 7 SL=R  # S R L = 2 SL=R RL # L a a b a 9 RL # 9-11 RL =# R b a a 8 LaR RL LaR Lb # 5 LaR RL LaR Lb # = 5-8 LaR RL LaR Lb # = 3 SR # L L b R R 4-12 Lb =# 4 Lb =# b R L 13 LaR # 12 Lb # 4-12 状态4和状态12 状态5和状态8 状态9和状态11 状态10和状态13 10-13 LaR #= 10 LaR #= 11 RL # =

13 LALR(1) 分析表的构造 与LR（1）相同

14 a b = # S L R S5,8 S4,12 1 2 3 1 ACC 2 S6 R6 3 R3 4，12 R5 R5 5，8 S5,8
S5,8 S4,12 1 2 3 1 ACC 2 S6 R6 3 R3 4，12 R5 R5 5，8 S5,8 S4,12 11,9 10,13 6 S5,8 S4,12 11,9 7 7 R2 9，11 R6 R6 10，13 R4 R4 Z → S （1） S → L= R （2） S → R （3） L → aR （4） L → b （5） R → L （6）

15 合并后产生的LALR（1）冲突 无冲突状态的LR（1）活前缀状态机合并同心状态后得到的活前缀状态机可能存在冲突状态。只可能产生归约—归约冲突，但是不可能产生移入—归约冲突.

16 例如，假定Si、Sj是某一LR(1)状态机的两个状态，
其中，u1、u2、v1、v2、t1、t2分别为归约展望符集 , aVT. 在Si中有: u1v1=、u1{a}=、v1{a}=; 在Sj中有: u2v2=、u2{a}=、v2{a}=. 显然Si和Sj是同心状态，合并后得到新状态Sij : A B Ca u1 v1 t1 Si u2 v2 t2 Sj A B Ca u1∪ u2 v1 ∪ v2 t1 ∪ t2 Si 因： (u1∪ u2 ) {a}= (v1 ∪ v2 ) {a}= 所以不可能产生移入—归约冲突. 因： (u1∪ u2 ) {a}= (v1 ∪ v2 ) {a}= 所以不可能产生移入—归约冲突. 因： (u1∪ u2 )  (v1 ∪ v2 ) =？ 所以可能产生归约—归约冲突.

17 LALR(1)文法的定义 对于一个文法，若按照上述算法构造的分析表中没有冲突动作，则称该文法为LALR(1)文法.

18 LALR(1)驱动程序 LALR(1)的驱动程序与LR(1)的驱动程序是相同的，可共用一个.

19 LALR(1)方法注意事项 LALR(1)对LR(1)状态机进行合并时，合并的同心状态的后继状态，也会出现同心状态，也需要进行合并。

20 LALR(1)方法特点 它具有SLR(1)的状态数少的优点和LR(1)的适用范围广的优点.
LALR(1)状态机的状态个数和LR(0)状态机的状态个数相同，而其展望符则即不采用SLR(1)的Follow集方法，也不采用LR(1)的完全精确法.

21 LR方法小结* 从功能上看，各种语法分析方法的分析能力从小到大依次为：
LR(0)<SLR(1)<LALR(1)<LR(1) 从活前缀状态机的状态数方面考虑： LR(0)和SLR(1)分析用的都是LR(0)状态机，因此它们的状态数相等； LALR(1)分析是把LR(1)状态机中的同心状态合并，显然合并同心状态后的LALR(1)状态机的状态个数和ＳLR(1)状态机的状态数是相等的； 因此从状态数方面看，各种语法分析方法的状态数有如下关系： LR(0)=SLR(1)=LALR(1)<LR(1)

22 例1. 有如下文法G[T]： TF*T TF F a 该文法是不是LR(0)文法，是不是SLR(1)文法.

23 3 4 2 1 5 文法G[T]的LR(0)活前缀状态机 Z → T T  F a a F T F  * T F Z → T 
Z → T T  F*T T  F F  a 3 F →a  a a F 2 T F  *T T F  * 4 T F *  T T  F*T T  F F  a T F 1 Z → T  T T F * T  5 拓广产生式后的文法： Z → T TF*T TF Fa 因状态2存在移入-归约冲突，所以该文法不是LR(0)文法. 但因：Follow(T)={#}、*Follow(T)，所以该文法为SLR(1)文法.

24 例2. 有如下文法G[S]： SAaB SB AaB Ab BA 该文法是不是SLR(1)文法，是不是LALR(1)文法.

25 所以该文法不是SLR(1)文法. a A Follow（B）={#，a} Z→S SAaB SB AaB Ab BA ZS
Z→S SAaB SB AaB Ab BA ZS SAaB 2 SB A SAaB AaB BA Ab a BA 3 Follow（B）={#，a} S Aa B .... … a # 2 S3 /R6 R6 …. 所以该文法不是SLR(1)文法.

26 S B A a A a a b b B a a A b B B b A ZS SAaB SB AaB Ab BA #
ZS SAaB SB AaB Ab BA # a # 1 ZS # 6 SAa  B B  A AaB Ab # 7 SAaB # S B A a 2 SAaB BA # A a a b 9 BA # B b a a 8 AaB BA AaB Ab # 5 AaB BA AaB Ab # a 3 SB # Z→S SAaB SB AaB Ab BA A b B 4 Ab a# b B A 13 AaB # 12 Ab # 10 AaB #a 11 BA # a

27 所以该文法是LALR(1)文法. S B A a A a a b b B a a A b B B b A ZS SAaB SB
ZS SAaB SB AaB Ab BA # a # 1 ZS # 6 SAa  B B  A AaB Ab # 7 SAaB # S B A a 2 SAaB BA # A a a b 9 BA # b B a a 8 AaB BA AaB Ab # 5 AaB BA AaB Ab # a 3 SB # A b B 4 Ab a# b 13 AaB # B 所以该文法是LALR(1)文法. A 12 Ab # 状态4和状态12 状态5和状态8 状态9和状态11 状态10和状态13 10 AaB #a 11 BA # a

28 例3 .有如下文法G[S]： SaAd SbAc SaBc SbBd Ae Be 该文法不是LALR(1)文法，是LR(1)文法.

29 S S # aAd# aAd # A d a a ed# b B c e aed# be d# be c# b ed#
 aec# ZS SaAd SbAc SaBc SbBd # S 1 ZS # S #  bed#  bec# aAd# aAd # A 4 SaAd # d 10 SaAd # a a ed# aec# 2 SaAd SaBc A   e B   e # d c b aBc# B 5 SaBc # c 11 SaBc  # aBc# e 6 A  e  B  e  d c aed# aec# S  aAd [1] S  bAc [2] S  aBc [3] S  bBd [4] A  e [5] B  e [6] be d# 9 A  e  B  e  c d be c# b ed# b ec# bA c# bAc# 3 SbAc SbBd A   e B   e # c d A 7 SbAc # c 12 SbAc  # e bB d# bBd# B 8 SbBd # d 13 SbBd  # LR(1)状态机

30 S A d a B c e b e e e A c B d LALR(1)状态机 ZS SaAd SbAc SaBc
ZS SaAd SbAc SaBc SbBd # 1 ZS # A 4 SaAd # d 10 SaAd # a 2 SaAd SaBc A   e B   e # d c B 5 SaBc # c 11 SaBc  # e 6 A  e  B  e  d c S  aAd [1] S  bAc [2] S  aBc [3] S  bBd [4] A  e [5] B  e [6] b 9 A  e  B  e  c d e 6,9 A  e  B  e  c,d d,c e e 3 SbAc SbBd A   e B   e # c d A 7 SbAc # c 12 SbAc  # B 8 SbBd # d 13 SbBd  #