LR(1)分析方法.

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

1 LR(1)分析方法

2 问题的引入 例1： S → AaAb S → BbBa A →  B →  ZS [1] SAaAb [2]
ZS [1] SAaAb [2] SBbBa [3] A  [4] B  [5] Follow（S）={#} Follow（A）={a,b} Follow（B）={b,a} 存在归约-归约冲突 该文法不是SLR(1)文法。 a b # R4/R5 ...

3 LR(1)方法 LR(0)方法不依赖输入流，直接判定归约，容易出现冲突。
SLR(1)方法简单的把非终极符的Follow集做为可归约的依据，并不精确。 一个非终极符在不同的位置不同状态上出现，它所允许的后继符是不同的。针对产生式的非终极符在不同位置上，分别定义其归约后继符集（展望符集Reducelookup），减少了移入/归约冲突。 LR（0）状态 LR（1）状态 ZS SAaAb SBbBa A  B  # a b ZS SAaAb SBbBa A  B 

4 LR(1)的基本概念 LR(1)项目：[A→, a ]。LR(0)项目及一个VT{#}的展望符。 IS:LR(1)项目集
IS(X): LR(1)项目集IS对文法符号X的投影 IS(X) = {[A→X,a] |[A→X,a]IS }

5 LR(1)的基本概念（续） CLOSURE ( IS ) = IS∪ {[B→,b] |[A→B,a] CLOSURE(IS),
ZS SAaAb SBbBa A  B  # a b CLOSURE ( IS ) = IS∪ {[B→,b] |[A→B,a] CLOSURE(IS), B→是产生式 , bFirst(a)} GO:若IS是一个LR(1)项目集，X是一个文法符号,则 GO（IS, X）=CLOSURE（IS(X)）

6 构造LR(1)活前缀状态机LRSM1的算法 Step1.构造初始状态IS0：IS0 = CLOSURE({ [Z→ S,#] })。
Step2.从已构造的LRSM1部分图选择未处理的任一状态IS，对每个符号XVTVN，求其后继状态ISj = CLOSURE( IS(X))，同时在IS和ISj之间画有向X边。 重复Step2 ，直至所有状态结点处理完为止。

7 例：构造下列文法的LR(1)状态机。 1 Z → S 2 S → AaAb 3 S → BbBa 4 A →  5 B →  S a a
ZS SAaAb SBbBa A  B  # a b 1 ZS # S 2 SAaAb # 4 SAa Ab A   # b a a 5 SAaA b # A A b B 6 SAaAb # 3 SBbBa # 7 SBb Ba B   # a b 8 SBbB a # 9 SBbBa  # B a

8 LR(1) 分析表的构造 LR(1)的项目分为两部分：[A→, a ]，即项目的心LR(0)项目部分和一个终极符的展望集。展望符望符集{a}是在心的项目分析完,归约到A后，当前输入可能出现的终极符集。{a}在整个项目的投影分析过程都不会改变。 所以，对LR(1)分析表的构造和LR(0)分析表大部分相同，只是在归约动作Ri的矩阵元素的确定上，需要通过展望符集中的字符来确定列项。

9 S a a A A b B b B a 例：构造下列文法的LR(1)状态机。 1 Z → S 2 S → AaAb 3 S → BbBa
ZS SAaAb SBbBa A  B  # a b 1 ZS # S a b # S A B R4 R5 S1 S2 S3 1 Acc 2 S4 3 S7 4 S5 5 S6 6 R2 7 S8 8 S9 9 R3 2 SAaAb # 4 SAa Ab A   # b a a 5 SAaA b # A A b B 6 SAaAb # 3 SBbBa # 7 SBb Ba B   # a b 8 SBbB a # 9 SBbBa  # B a

10 S a a A A b B b B a 例：构造下列文法的LR(1)状态机。 1 Z → S 2 S → AaAb 3 S → BbBa
# S A B R4 R5 S1 S2 S3 1 Acc 2 S4 3 S7 4 S5 5 S6 6 R2 7 S8 8 S9 9 R3 ZS SAaAb SBbBa A  B  # a b 1 ZS # S 2 SAaAb # 4 SAa Ab A   # b a a 5 SAaA b # A A b B 6 SAaAb # 3 SBbBa # 7 SBb Ba B   # a b 8 SBbB a # 9 SBbBa  # B a

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

12 LR(1)分析条件 LR1的活前缀状态机中存在着状态： A1 →1，{a11,a12，…} …，
An →n， {an1,an2，…} B1→1 c1r1， {b11,b12，…} Bm→ mcmrm ， {bm1,bm2，…} 则集合： {a11,a12，…} 、…、{an1,an2，…}、{c1, …, cm} 两两相交为空。 注： {an1,an2，…} 为A1项的展望符集。 c1, …, cm为可移入终极符，可以有相同者。

13 Z → S S → L= R S → R L → aR L → b R → L
例：构造下列文法的LR(1)状态机，判断是否为LR(1)文法。 Z → S S → L= R S → R L → aR L → b R → L

14 L = L a a L L Follow（R）={#，=} 6 ZS # SL=  R # SL=R # R  L #
6 ZS # SL=  R # SL=R # R  L # SR # L = LaR # 2 L LaR = # Lb # SL=R # Lb = = # a a RL # RL # 9 RL # 5 8 L LaR LaR # =# G[Z]： 1. Z → S 2. S → L= R 3. S → R 4. L → aR 5. L → b 6. R → L RL =# RL # LaR =# LaR # Lb =# Lb # L 11 Follow（R）={#，=} RL =#

15 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 # =

16 没有冲突，是LR(1）文法 a b = # S L R S5 S4 1 2 3 1 Acc 2 S6 R6 3 R3 4 R5 R5 5
S5 S4 1 2 3 1 Acc 2 S6 R6 3 R3 4 R5 R5 5 S5 S4 11 10 6 S8 S12 9 7 没有冲突，是LR(1）文法 7 R2 8 S8 S12 9 13 9 R6 10 R4 R4 11 R6 R6 示例2 12 R5 13 R4

17 LR(1)驱动程序 LR(1)的驱动程序与SLR(1)的驱动程序是相同的，可共用一个。

18 例： 设文法G[S]为： SAS |  A aA | b 证明G[S]是LR(1)文法； 构造它的LR(1)分析表； 给出符号串abab#的分析过程

19 G[Z]： Z → S[0] SAS[1] S [2] A aA[3] A  b[4] S A A S b a b a A a b
1 ZS # 5 S ZS[0] # S AS[1] # A SA S [1] # S [2] # 2 S AaA[3] # ab A SA S[1] # Ab[4] # ab S AS[1] # b G[Z]： Z → S[0] SAS[1] S [2] A aA[3] A  b[4] b a S [2] # AaA[3] ab# Ab[4] ab# a 3 AaA[3] ab# 6 A a AaA[3] ab# AaA [3] ab# Ab[4] ab# b 4 Ab [4] ab#

20 S A A S b a b a A a b 1 ZS # 5 ZS[0] # S AS[1] # SA S [1] #
1 ZS # 5 S ZS[0] # S AS[1] # A SA S [1] # S [2] # 2 S A AaA[3] # ab SA S[1] # Ab[4] # ab S AS[1] # b a b # s3 s4 R2 1 Acc 2 3 4 R4 5 R1 6 R3 A S 2 1 5 3 6 4 b a S [2] # AaA[3] ab# Ab[4] ab# a 3 AaA[3] ab# 6 A a AaA[3] ab# AaA [3] ab# Ab[4] ab# b 4 Ab [4] ab#

21 Action Goto 状态栈 符号栈 输入流 动作 G[Z]： Z → S[0] SAS[1] S [2] A aA[3]
b # S3 S4 R2 1 Acc 2 3 4 R4 5 R1 6 R3 A S 2 1 5 3 6 4 # abab# 移入S3 03 #a bab # 移入S4 034 #ab ab # 归约R4转S6 036 #aA ab # 归约R3转S2 02 #A ab # 移入S3 023 #Aa b # 移入S4 0234 #Aab # 归约R4转S6 0236 #AaA # 归约R3转S2 022 #AA # 归约R2转S5 G[Z]： Z → S[0] SAS[1] S [2] A aA[3] A  b[4] 0225 #AAS # 归约R1转S5 025 #AS # 归约R1转S1 01 #S # 成功

22 例： 非LR(1)文法 设有下列文法： LMLb|a M 说明上述文法是否为LR(1)文法，若不是，请说明理由。 Z  L #
非LR(1)文法 Z  L # L  MLb # L  a # M   a

23 (1) 构造该文法的LR(1)可归活前缀状态机，并构造LR(1)分析表。
练习： 设有文法G[Z]如下: Z AB [1] A aB [2] | b [3] B aB [4] | b [5] (1) 构造该文法的LR(1)可归活前缀状态机，并构造LR(1)分析表。 (2) 试应用LR(1)分析技术，使用下表格式识别输入符号串abb是否为文法G[Z]的句子。 表2 状态栈 符号栈 输入串 分析动作 转向状态 # abb# ...