(3条消息) LR 类分析方法总结

文章目录

  • LR 类分析方法相关定义
  • LR 类分析法的基本思想和工作过程
    • LR 分析表
    • LR 驱动程序
  • LR 分析法的关键问题
    • 可归前缀的判断
    • 确定句柄
  • LR(0) 分析法
    • LR(0) 分析法基本概念
      • LR(0) 项目
      • 项目集的闭包
      • 项目集的投影
      • 项目集的转换函数（GO 函数）
    • 构造 LR(0) 可归前缀状态机 LRSM
    • LR(0) 分析表的构造
    • LR(0) 驱动程序
    • LR(0) 分析实例
    • LR(0) 文法的限定条件 | 定义
  • SLR(1) 分析法
    • LR(0) 分析法的不足
    • 不是 LR(0) 文法的情况
    • SLR(1) 分析条件
    • 构造 SLR(1) 可归前缀状态机
    • SLR(1) 分析表的构造
    • SLR(1) 驱动程序
    • SLR(1) 分析实例
    • SLR(1) 文法限定条件 | 定义
    • SLR(1) 与 LR(0)
  • LR(1) 分析法
    • SLR(1) 分析法的不足
    • 几种 LR 方法的简单对比
    • LR(1) 的基本概念
      • LR(1) 基本思想
      • LR(1) 项目、投影
      • LR(1) 闭包集、GO 函数
    • 构造 LR(1) 可归前缀状态机 LRSM1
    • LR(1) 分析表的构造
    • LR(1) 驱动程序
    • LR(1) 分析实例
      • 例 1
      • 例 2
    • LR(1) 分析条件 | 定义
  • LALR(1) 分析法
    • LR(1) 语法分析方法的不足
    • LALR(1) 的思想来源
      • 同心状态
    • 由 LR(1)SM 构造 LALR(1) 可归前缀状态机
    • LALR(1) 分析表的构造
    • LALR(1) 分析条件 | 定义
    • 合并同心状态带来的问题
    • LALR(1) 方法
  • LR 方法总结

LR 类分析方法相关定义

LR(k) 分析方法是 1965 年由 D. Knuth 提出来的一种自底向上的语法分析文法。这里的 L 表示从左向右扫描输入串，R 表示构造一个最右推导的逆过程，k 表示在决定语法分析动作时需要向前看的符号个数。由于 LR(k) 分析方法对文法的限制很少，因而大多数能用上下文无关文法描述的程序设计语言都可用 LR 分析法进行有效的分析。LR(k) 分析方法适用范围较广、分析速度很快，并且能够准确及时地发现语法错误，因此，LR 分析法是当前最一般的语法分析方法（这里我书上是这样写的，但是我听老师好像说过因为移入归约冲突等不好解决就用的少了）。LR 分析法主要有 LR(0)、SLR(1)、LR(1)、LALR(1) 方法。

下面是其中的一些术语以及定义：

  • 规范句型: 用最右推导导出的句型，也称右句型。
  • 规范前缀: 若有规范句型 αβ, 且 β 是终极符串或空串, 则称 α 为规范前缀。
  • 规范活前缀：若某一规范句型的规范前缀 α 不含句柄或含一个句柄并且具有形式 α=α′π( π 是句柄)，则称规范前缀 α 为规范活前缀（简称活前缀）。
  • 可归前缀：若活前缀 α 是含句柄的规范前缀，且句柄在 α 的最右端，即有 α=α′π，且 π 是句柄，则称活前缀 α 为可归前缀（归约规范活前缀、归约活前缀和可归活前缀都是指这个）

注：可归前缀中，『句柄在 α 的最右端』这里说的『最右端』是因为规范句型是指最右推导导出的句型，因此每次都选择最右边的非终极符进行替换。如果最右边出现了句柄，则可以将句柄归约。（这里存疑，看本节例题就可以很容易从符号栈中看出是从最右端开始的，因为例题中符号栈栈底在左边）

LR 类分析法的基本思想和工作过程

LR 方法的主要思想是，从输入流依此把符号移入符号栈，直至栈顶出现一个句柄；之后对句柄进行归约，直至栈顶不出现句柄；重复上述过程，直至最终归约为一个开始符，且输入流为空。

一个 LR 分析器由以下几个部分组成：

  1. 输入流（Input）：一个有待分析的输入符号串
  2. 分析栈：其中包括文法符号栈和相应的状态栈
  3. 分析表：其中包括 Action 表和 GoTo 表。
  4. 驱动程序：对于不同的 LR 分析方法其驱动程序都是相同的。

LR 分析表

LR 分析表是提取可归前缀状态机 LRSM 中的信息形成的矩阵形式的表。包括 Action 表和 GoTo 表两部分：

  • Action 矩阵：行代表状态，列代表输入符（包括输入结束符 #，值得注意的是输入符都是终极符），而矩阵元素则表示相应的分析动作：移入 Shift / 归约 Reduce / 成功 Accept / 失败 Error

  • GoTo 矩阵：行代表状态，列则代表非终极符，而矩阵元素则表示归约后的转向状态。

  • Action(s, a) 规定了当状态 s 面对输入符号 a 时采用什么动作，用『动作矩阵』存储

  • Goto(s, x) 规定了状态 s 面对符号 x 时下一个状态是什么，用『转向矩阵』存储。

LR 驱动程序

不妨假设状态栈、符号栈和输入流的开始格局为：（#S1, #, a1a2…an#），各部分以逗号分隔。

  • 移入：若当前格局为（#S1S2…Sn, #X1X2…Xn, aiai+1…an#），且 Action(Sn, ai)=Sj，ai∈VT，则 ai 入符号栈，第 j 个状态 Sj 入状态栈。即移入后的格局变为：（#S1S2…Sn Sj, #X1X2…Xn ai, ai+1…an#）
  • 归约：若当前格局为（#S1S2…Sn, #X1X2…Xn, aiai+1…an#），且 Action(ISn, a)=Rj，a∈VT∪{#}，则按照第 j 个产生式进行归约，符号栈和状态栈相应元素退栈，归约后的文法符号入栈。假设第 j 个产生式为 A→α，k=|α| (α=Xn-k+1…Xn)，则归约后的格局变为：（#S1S2…Sn-kS, #X1X2…Xn-kA, aiai+1…an#），其中 S=GoTo(Sn-k, A)。
  • 成功：若状态栈的栈顶状态为 Si，输入流当前值为 #，且 Action(Si, #)=Accept，则分析成功。
  • 失败：若状态栈的栈顶状态为 Si，输入流当前值为 a，且 Action(Si, a)=Error 或空，则转向出错处理程序。

例: 设文法 G(S) : \
[1] S → aAdBc \
[2] A → Aaa\
[3] A → a\
[4] B → Bbb\
[5] B → b

则对句子 aaaacbbbd 有如下规范推导:

S ⇒ aAdBc[1] \
⇒ aAdBbb[4]c[1] \
⇒ aAdb[5]bb[4]c[1] \
⇒ aAaa[2]db[5]bb[4]c[1] \
⇒ aa[3]aa[2]db[5]bb[4]c[1]

其归约过程为:

aa[3]aa[2]db[5]bb[4]c[1] \
⇒ aAaa[2]db[5]bb[4]c[1] \
⇒ aAdb[5]bb[4]c[1] \
⇒ aAdBbb[4]c[1] \
⇒ aAdBc[1] \
⇒ S

LR 分析法的关键问题

  • 如何判断分析栈内容是否为可归前缀
  • 能唯一的确定可归前缀中的句柄

可归前缀的判断

我们有如下『派生定理』

  1. 开始符产生式的右部是可归前缀。
  2. 如果 α1Aα2 是可归前缀，且 A→β 是产生式，则 α1β 也是可归前缀。

第一个就是 Z->α1|α2|...αn 则 α1，…αn 都为可归前缀，这个结论对不对稍微分析一下就可以知道。

比如说一开始符号栈里是 α1，输入流是一个#，相当于 β=空，所以 α1 首先是一个规范前缀，然后他也是必然为一个句柄，也就是可归前缀了。所以第一点就是开始符的右部都是可归前缀。以它为基础可以推出其他的可归前缀。

第二个结论怎么得出来的呢，思想是 α1Aα2 是可归前缀，这里的右端肯定有句柄，大概有几种可能

  • 要么 A 不在句柄里，而在 α2 里，假如 A 不在里面的话，α2 有一颗子树，又有 A→β，α1 里面一定没有句柄存在，否则 α1Aα2 是可归前缀就不可满足。这样的话，α1β 一定是含有句柄，并且在最右边。
  • 要么 A 在句柄里，假如 A 在句柄里，一定是一层节点，然后 A→β 是下一层的，所以依然成立。

例子：设有文法 G[S]:

[1] S → aAc
[2] A → Abb
[3] A → b

其中可归前缀为：aAc，aAbb，ab

确定句柄

因为本文是先画可归前缀状态机的，然后进行 Action 矩阵等的填写。而可归前缀状态机本身就可以提供出可归前缀的判断信息（待补充如何判断）

LR(0) 分析法

LR(0) 分析法基本概念

LR(0) 项目

LR(0)项目（简称项目）是带一个圆点 『·』 的产生式。每个项目都标志分析时的某一状态。

即：若 A→α 是产生式，则称 A→α·β 为 LR(0) 项目(简称项目）

项目的含义：对产生式 A 进行分析的某个状态：圆点的左部表示分析过程已经识别过的部分，圆点右部表示期待的后缀部分。简单来说就表示分析到哪了。

  • 形如 A→ α· 的项目称为 归约型项目 （点在最后）
  • 形如 A→ α·β 的项目称为 移入型项目

这里有个特殊情况是：·ε 这一个是看作归约项的。

归约型项目按照自动机来说，实际上是自动机的一个终止状态，也就自动机可以接受的一个 可归前缀 。

例：起始符 S → aAc 对应四个 LR(0) 项目：

  1. S → ·aAc 表明我们希望接下来在输入中看到一个从 aAc 推导得到的串。这时符号栈为空。
  2. S → a·Ac 表明刚在输入中看到了一个 a，我们希望接下来看到一个能从 Ac 推导得到的串。这时符号栈中包含活前缀 a。
  3. S → aA·c 表明刚在输入中看到了一个可以由 aA 推导得到的串。这时符号栈中包含活前缀 aA。
  4. S → aAc· 表明我们已经看到了产生式全体 aAc，已经是时候把 aAc 归约为 S 了。符号栈中为可归前缀，右部为句柄。

项目集的闭包

项目集就是项目的集合的简称。

假设 IS 是 LR(0) 项目集，则称下面 CLOSURE(IS) 为 IS 的闭包集：

CLOSURE(IS) = IS∪{ A→·π | Y→β·Aη∈CLOSURE(IS)，A→π是产生式 }

项目集的闭包 CLOSURE(IS) 的含义：表示项目集 IS 中每一个 Y→β·Aη 项目的圆点右部非终极符 A，可以应用的所有可能产生式。

值得注意的是，这是一个动态的过程。也就是说，A 可以应用的产生式作为项目后，还要继续判断这些新产生的项目。

例 1：G[S]:

  • [1] S → aAc （S 可以应用的产生式）
  • [2] A → dbb （A 可以应用的产生式）
  • [3] A → b （A 可以应用的产生式）

令项目集 IS={S → a·Ac[1]}，则

CLOSURE(IS) ={S→a·Ac[1]，A→·dbb[2]，A→·b[3] }

例 2：G[S]:

  • S → E
  • E → E+T | T
  • T → T*F | F
  • F → (E) | id

令项目集 IS={S→·E}

CLOSURE(IS):

  • S → ·E
  • E → ·E+T
  • E → ·T
  • T → ·T*F
  • T → ·F
  • F → ·(E)
  • F → ·id

项目集的投影

假设 IS 是 LR(0) 项目集，则称下面定义的 IS(X) 为 IS 关于 X 的投影集：

IS (X) = {A→αX·β | A→α·Xβ∈IS, X∈(V T∪V N)}

项目集 IS 关于 X 的投影集的含义：项目集中每个项目 A→α·Xβ 所描述的状态，处理完一个符号 X 后所对应的后继项目。

这里说句人话就是 IS 中的一个项目接收一个符号（终极符或非终极符）到达的下一个项目。

比如 S → ·aAB 这个项目可以接收 a 会到 S → a·AB 这个项目。不能接收 A 所以到空状态。

这样对项目集里的所有项目尝试接收所有终极符和非终极符后能到的下一个项目就是该项目关于那个满足条件的符号的投影集。

例：G[S]:

  • [1] S → aAB
  • [2] A → dbb
  • [3] A → b
  • [4] B → e

令项目集 IS={S → a·AB[1]，A → ·dbb[2] ，A →·b[3] }，则：

  • IS(A)={S → aA·B[1]}
  • IS(S)={ }
  • IS(d)={A →d·bb [2] }
  • IS(b)={A →b·[3] }
  • IS(a)={ }
  • IS©={ }

项目集的转换函数（GO 函数）

若 IS 是一个 LR(0) 项目集，X∈(VT∪VN)，函数 GO(IS, X) 定义为

GO(IS, X)=CLOSURE(IS (X))

其中 IS(X) 为 LR(0) 项目集 IS 关于 X 的投影。

例：G[S]:

  • [1] S → aAc
  • [2] A → dbb
  • [3] A → b

令项目集 IS={S → ·aAc [1]}，则：

GO(IS, a )
= CLOSURE(IS(a))
= CLOSURE({S→a·Ac[1]})
= {S → a·Ac[1]，A → ·dbb[2]，A → ·b[3]}

构造 LR(0) 可归前缀状态机 LRSM

这里的 LRSM 应该是 线性正则式状态机，即 linear regex state machine，这个名词我并没有 Google 到，貌似是我们学校老师起得名字。

不过可能也是 LR state machine，反正我也不太知道。

为了使“成功”状态易于识别，通常 LR 文法要求文法的开始符 唯一 且不出现于产生式的右部，因此要增加一个新的产生式，称 拓广产生式

Z→S

其中 S 是原文法的开始符，而 Z 则是新符号。

下面给出构造 LR(0) 可归前缀 LRSM 的算法

  • Step1. 构造初始状态 IS0 ：IS0=CLOSURE({Z→·S})，其中 Z 是开始符
  • Step2. 已构造的可归前缀自动机的任一状态 IS，对每个符号 X∈VT∪VN，通过项目集转移函数 GoTo(IS,X) 求其后继状态 ISj
  • Step3. 重复 Step2，直至所有状态处理完毕。

LRSM 特点：

  • LRSM 给出了所有的可归活前缀
  • LRSM 中的每个状态将对应一个项目集：
    1. 其中一部分是由先驱状态分出来(称为基本项目)；
    2. 一部分则是由基本项目扩展出来的(称为扩展项目或派生项目)。派生部分项目的特点是其中的“·”出现在产生式右部的最左侧。
  • LRSM 不能直接用于 LR 分析,因为它识别的是 VT ∈ VN上的符号串，而语法识别的是 VT组成的句子。但它提供了 LR 分析所需的信息。
  • LRSM 提供的信息：
    • 移入/归约信息: [A→α·a β]、[A→π·];
    • 移入/归约后的转向状态信息.

可归前缀状态机实际上不能够完成语法分析的全部工作，他只能用来找句柄（走到某一个终止状态，我们就知道出现了可归前缀，句柄是什么也知道了），除此之外我们还需要做其他的工作来完成语法分析。

首先我们来看可归前缀状态机提供的语法分析信息：

  1. 合法性检查信息，就是当前允许输入哪些符号
  2. 移入/归约信息，移入状态可以做移入动作，归约状态可以做归约动作
  3. 移入/归约后的转向信息，移入简单这里不解释，归约就回归到含有 Vn 输出边的状态，然后按照 Vn 进行移入。

什么是移入和归约信息呢？

  1. 移入信息：如果可归前缀状态机 ISi 包含形如 A→α·aβ 的项目，即 ISi 有 a 的输出边，其中 a 是终极符，则表示 ISi 状态遇当前输入符为 a 时应将其移入符号栈，状态机沿着其 a 的输出边转向其后继状态。
  2. 归约信息：如果状态 ISi 包含形如 X →Y1 Y2 ……Yn· 的项目，则表示 ISi 状态可按该产生式做归约动作，归约后状态机回退 n 个（Y1 Y2 ……Yn 的长度）状态至状态 ISj，随后沿着 ISj 的 X 输出边转向其后继状态。

例子：
构造 LR(0)状态机

  • S → E $
  • E → E + T
  • E → T
  • T → id
  • T → ( E )

对图像做一些解释：

  • 黄色的部分是状态的编号
  • 绿色的部分是求闭包产生的
  • 四个 0 是 ·，因为编码原因，不能正常显示。

上面那个图是从状态 0 开始画得，然后编号这个基本都是随便编的，每个人的不需要一样。

本例不是太好，因为状态 0 包含了全部的产生式，可能会让人误解一开始就要包含所有的产生式，其实这里一开始只有 S → ·E$ 这一个项目的。这里需要注意的是：其余的都是这个项目的闭包。这样计算完后才导致文法的所有产生式都在里面。

LR(0) 分析表的构造

假设 ISk 为 LR(0) 项目集，

  • Action 矩阵：

    1. 若 A→α·aβ∈ISk，且 GO(ISk, a)= ISi，a∈VT，则 Action(ISk, a)=Si，表示移入动作。
    2. 若 A→α·∈ISk，则对任意 a∈VT∪{#}，令 Action(ISk, a)=Rj，其中产生式 A→α 的编号为 j，表示用编号为 j 的产生式进行归约。
    3. 若 Z→α·∈ISk，且 Z 为拓广产生式的左部非终极符(文法的开始符)，则 Action(ISk, #)=Accept。
    4. 其它情形，则 Error(n)，表示出错标志，也可不填。
  • GoTo 矩阵：
    • 若 GO(ISk, A)=ISi，A∈VN，则 GoTo(ISk, A)=i。

例子

  1. S → E $
  2. E → E + T
  3. E → T
  4. T → id
  5. T → ( E )
Action 表 GoTo 表
$ + i ( ) # E T
0 S5 S6 1 9
1 S2 S3
2 Ac
3 S5 S6 4
4 R2 R2 R2 R2 R2 R2
5 R4 R4 R4 R4 R4 R4
6 S5 S6 7 9
7 S3 S8
8 R5 R5 R5 R5 R5 R4
9 R3 R3 R3 R3 R3 R3

解释

  • 这里 S 打头的都是移入，R 打头的都是归约
  • 对于归约项目 4 5 8 9 来说，它们 R 后面的是对应产生式的序号，表示使用第几个产生式进行归约。
  • 对于移入项目来说，S 后面的接收终极符后到达的项目状态的序号

LR(0) 驱动程序

见开头

LR(0) 分析实例

G[S]

  • S → E$ [1]
  • E → E+T [2] | T [3]
  • T → id [4] | (E) [5]

分析：i+i$

状态栈 符号栈（#代表栈底） 输入串（#代表输入串结束） Action Goto
0 # i+i$# A[0,i]=S5
05 # i +i$# reduce4 G[0,T]=9
09 # T +i$# reduce3 G[0,E]=1
01 # E +i$# A[1,+]=S3
013 # E+ i$# A[3,i]=S5
0135 # E+i $# reduce4 G[3,T]=4
0134 # E+T $# reduce2 G[0,E]=1
01 # E $# A[1,$]=S2
012 # E$ # accept

这里没啥好说的，对应着 驱动程序 小节那里写就行了。

还是稍微解释一下吧，两个月后自己也看不太明白了…

刚开始时在状态 0，读入输入串头符 i，查 Action 表可得转到状态 5，把状态 5 压入状态栈中，也把输入串头符 i 压入符号栈中。

然后在状态 5 读入输入串头符，查 Action 表是按第四条产生式 T → id 进行归约，即从符号栈栈顶取 i 归约成非终极符 T。现在就相当于状态 5 接收一个归约产生的 T，查 Goto 表可得由状态 5 转到状态 9。

接着这样做就行，需要注意的是，我描述的部分并没有详细的说明符号栈、输入串的变化情况，要想详细知道规则，看 驱动程序 小节。

LR(0) 文法的限定条件 | 定义

  • 若 LRSM 中存在一个状态（项目集）

    • 既包含移入型项目又包含归约型项目，则说有 移入-归约冲突
    • 如果同时存在两个或两个以上归约型项目，则说有 归约-归约冲突
  • 若 LRSM 中任何状态都不存在冲突，则称该文法为 LR(0) 文法。

SLR(1) 分析法

LR(0) 分析法的不足

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

不是 LR(0) 文法的情况

我们先来看一个例子：

3 状态为二义性节点，有移入-归约冲突，原因是没有充分的利用输入流信息

我们来分析一下这个例子，对于状态 3：如果输入流头符为 ‘*’ 就应该移入；如果头符属于 Follow(T) 则应该归约。因此结论就是如果 *∉follow(T) 则这个冲突其实是可以解决的。

SLR(1) 的可归状态机可以直接使用 LR(0) 的状态集，只是出现冲突的时候，向前看一个符号来消除冲突。

总结如下：

  1. 如果某个状态有项目集：{ A→α·, D→μ·dγ}，则存在 移入-归约冲突。可以如下解决：
  • 若当前输入符在 A 的 Follow 集中，则应用 A →α· 归约；
  • 若当前输入符为 d 则应移入 。
  • 而对当前输入符为 d，d 又在 A 的 Follow 集中，则无法解决。
  1. 如果某个状态有项目集：{ A→α·, B→β·}，则存在着 归约-归约冲突 。可以如下解决：
  • 若用 A→α· 归约，则当前输入符应在 A 的 Follow 集中
  • 若用 B→β· 归约，则当前输入符应在 B 的 Follow 集
  • 当前输入符应在 A 的 Follow 集中又在 B 的 Follow 集中，则无法解决。
  1. 如果某个状态有如下项目集：{ A→α·, B→β·, D→μ·dγ }，则存在着归约-归约，移入-归约冲突
  • 若用 A→α· 归约，则当前输入符应在 A 的 Follow 集中
  • 若用 B→β· 归约，则当前输入符应在 B 的 Follow 集
  • 若移入，则当前输入符应为 d。

SLR(1) 分析条件

LRSM0 中存在着状态：
{ A1→α1·，
…，
An→αn·，
B1→β1·a1r1，
…，
Bm→βm·amrm }
则集合：
Follow(A1)、…、Follow(An)、{a1, …, am} 两两相交为空时才能使用 SLR(1) 方法分析。

注：a1, …, am 中可以有相同者。

构造 SLR(1) 可归前缀状态机

这里和 LR(0) 一样

SLR(1) 分析表的构造

与 LR(0) 分析表的构造不同之处只是 Action 表中归约项的填写，其他都一样。

  • 若 A→α·∈ISk，则对任意 a∈VT，a∈Follow(A)，令 Action(ISk, a)=Rj，其中产生式 A→α的编号为 j，表示用编号为 j 的产生式进行归约。

构建 SLR(1) 分析表和 LR(0) 分析表的区别就在归约项这里，原来是对于任意一个 a，现在是对于特殊的 a。

完整方法如下:

假设 ISk 为 LR(0) 项目集，

  • Action 矩阵：

    1. 若 A→α·aβ∈ISk，且 GO(ISk, a)= ISi，a∈VT，则 Action(ISk, a)=Si，表示移入动作。
    2. 若 A→α·∈ISk，则 对任意 a∈VT，a∈Follow(A)，令 Action(ISk, a)=Rj，其中产生式 A→α的编号为 j，表示用编号为 j 的产生式进行归约。
    3. 若 Z→α·∈ISk，且 Z 为拓广产生式的左部非终极符(文法的开始符)，则 Action(ISk, #)=Accept。
    4. 其它情形，则 Error(n)，表示出错标志，也可不填。
  • GoTo 矩阵：
    • 若 GO(ISk, A)=ISi，A∈VN，则 GoTo(ISk, A)=i。

例子:

  1. M → T
  2. T → F
  3. T → F*T
  4. F → a

首先画出该例的可归前缀状态图

算出各非终极符的 Follow 集

  • Follow(M)={#}
  • Follow(T)={#}
  • Follow(F)={*,#}
Action 表 GoTo 表
a * # T F
0 S2 1 3
1 Ac
2 R4 R4
3 S4 R2
4 S2 5 3
5 R3

原来状态 1 2 3 5 下的 Action 表都会填满，现在只填属于非终极符的 Follow 集的。

SLR(1) 驱动程序

见开头

SLR(1) 分析实例

a*a*a

状态栈 符号栈 输入串 分析动作 转向状态
0 # a*a*a# S2
02 #a *a*a# R4 3
03 #F *a*a# S4
034 #F* a*a# S2
0342 #F*a *a# R4 3
0343 #F*F *a# S4
03434 #F*F* a# S2
034342 #F*F*a # R4 3
034343 #F*F*F # R2 5
034345 #F*F*T # R3 5
0345 #F*T # R3 5
01 #T # AC

SLR(1) 文法限定条件 | 定义

语法分析表单值

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

例子
有如下文法 G[T]：

  1. T→F*T
  2. T→F
  3. F→a
    该文法是不是 LR(0) 文法，是不是 SLR(1) 文法 .

拓广产生式后的文法：

  1. Z → T
  2. T→F*T
  3. T→F
  4. F→a

文法 G[T]的 LR(0)可归前缀状态机

因状态 2 存在移入-归约冲突，所以该文法不是 LR(0) 文法 .

但因：Follow(T)={#}、*∉Follow(T)，所以该文法为 SLR(1) 文法 .

SLR(1) 与 LR(0)

  • SLR(1) 和 LR(0) 具有相同的状态机和驱动程序，只是分析表 Action 矩阵在归约条件时有差别。
  • LR(0) 归约时只看分析栈的内容 , 不考虑当前输入符，SLR(1) 在归约动作有冲突时考虑输入符，用 follow 集来解决冲突，因此 SLR(1) 要比 LR(0) 分析能力强。
  • 从定义可以看出 SLR(1) 分析方法是用 LR(0) 项目构成的 LRSM0 来识别活前缀，因此它们的状态数相同，但是，由于 LR(0) 方法只看状态栈的内容而 SLR(1) 方法还要向前看展望符，因此 SLR(1) 文法要比 LR(0) 文法应用广。

LR(1) 分析法

LR 文法都是构造性定义，就是说没法直接判断是哪种，都是要画出状态图以后再判断，给我们个文法我们也不知道用 LR 或者说哪种 LR 方法来算，必须是画图后确定。

他们能解决的问题都是语法分析中的一类问题，并不是所有的问题都能解决。比如归约-归约冲突，我们能解决的是当 follow(a)∩follow(b) 等于空时才能解决，交集不等于空的时候，我们还是不知道怎么办

移入-归约冲突的时候也有不能解决的时候，用 SLR 还是解决不了

有人给出了 LR(1) 对输入串进行更加细化的分析

SLR(1) 分析法的不足

有如下文法

  • Z→B1aB2bB3c
  • B→d

SLR(1) 归约时向前看一个符号，但是不区分相同语法符号的不同出现。上述文法中，B 出现了三次，很显然 B1 的后继符只能是 a，B2 的后继符只能是 b，B3 的后继符只能是 c。而 Follow(B)={a,b,c}，这表示分析到 B1 时，SLR(1) 方法判断输入串头符可以是 abc，但实际上输入串头符只能是 a，所以此时用 SLR(1) 就失去了精度。

因此在这个基础上，我们引出了 LR(1) 的方法，多考虑一些信息，多看一个展望符。

几种 LR 方法的简单对比

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

后继符(搜索符)的概念:

  • 不同的归约中有不同的后继符。
  • 特定位置的后继符是 FOLLOW 集的子集

LR(1) 的基本概念

LR(1) 基本思想

构造各种 LR 分析器的任务就是构造其 Action 表和 GoTo 表，其他部分基本相同。

LR(1) 的基本思想是对非终极符的每个不同出现求其后继符，而不是给每个非终极符求其统一的后继符，我们称其为 展望符集。

LR(1) 项目、投影

LR(1) 项目：[A→α·β, a]，即 LR(0) 项目及一个 VT∪{#} 的展望符组成的二元组。

用 IS 表示 LR(1) 项目的集合，简称 LR(1) 项目集。其中，项 Z→·α 的展望符为 #，Z 为开始符。

IS(X)：LR(1) 项目集 IS 对于 X 的投影

IS (X) = { [A→αX·β, a] | [A→α·Xβ, a]∈IS }

LR(1) 项目有个展望符，当是移入项目的时候展望符是没有作用的。要归约的时候，比如是 a->a·b 这种的时候有作用 ，表示当输入流的头符是符号 b 的时候才进行归约，否则移入。

项目不同了，投影跟以前一样

LR(1) 闭包集、GO 函数

闭包集：

CLOSURE(IS) = IS∪{[A→·β, a] | [B→α 1·Aα 2, b]∈CLOSURE(IS),

其中 A→β 是产生式，a∈First(α2b)}

这里写完自己看了一会才搞懂，解释一下：

  • 我们先有 [B→α1·Aα2, b] 这个项目
  • 点·后面是个非终极符，所以我们要对它求闭包
  • 以这个非终极符开头的产生式假如有 A→β
  • 则该非终极符产生的 LR(0) 项目是 A→·β ，这个项目的展望符 a 满足 a∈First(α2b)}

GO：若 IS 是一个 LR(1) 项目集，X 是一个文法符号 , 则

G O ( I S , X ) = C L O S U R E ( I S ( X ) ) GO(IS,X)=CLOSURE(IS_{(X)}) GO(IS,X)=CLOSURE(IS(X)​)

构造 LR(1) 可归前缀状态机 LRSM1

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

例子：构造下列文法的 LR(1) 状态机。

  1. Z → S
  2. S → AaAb
  3. S → BbBa
  4. A → ε
  5. B → ε

这里就是展望符求法是个重点，总结如下：

  • 开始符的展望符是 #
  • 其他项目的展望符在求闭包时产生，公式在 LR(1) 闭包集、GO 函数 小节。

LR(1) 分析表的构造

LR(1) 的项目分为两部分：[A→α·β, a ]，即 LR(0) 项目部分（项目的心）和一个终极符的展望集。展望符集{a}是在项目的心分析完，归约到 A 后，当前输入可能出现的终极符集。{a} 在整个项目的投影分析过程都不会改变。

所以，对 LR(1) 分析表的构造和 LR(0) 分析表大部分相同，只是在归约动作 Ri 的矩阵元素的确定上，需要通过展望符集中的字符来确定列项。

LR(1) 驱动程序

见开头

LR(1) 分析实例

例 1

有文法：

  1. Z → BB
  2. B → aB
  3. B → b
Action 表 GoTo 表
a b # B
0 S6 S4 1
1 S5 S3 2
2 AC
3 R3
4 R3 R3
5 S5 S3 8
6 S6 S4 7
7 R2 R2
8 R2
状态栈 符号栈 输入串 Action GoTo
0 abaab# S6
0,6 #a baab# S4
0,6,4 #ab aab# R3 7
0,6,7 #aB aab# R2 1
0,1 #B aab# S5
0,1,5 #Ba ab# S5
0,1,5,5 #Baa b# S3
0,1,5,5,3 #Baab # R3 8
0,1,5,5,8 #BaaB # R2 8
0,1,5,8 #BaB # R2 2
0,1,2 #BB # AC

例 2

设文法 G[S] 为：

  1. S→AS | ε
  2. A→aA | b
  • 证明 G[S] 是 LR(1) 文法；
  • 构造它的 LR(1) 分析表；
  • 给出符号串 abab# 的分析过程

G[Z]：

[0] Z → S

[1] S → AS

[2] S → ε

[3] A → aA

[4] A → b

Action

a b #
0 S3 S4 R2
1 Acc
2 S3 S4 R2
3 S3 S4
4 R4 R4 R4
5 R1
6 R3 R3 R3

GoTo

A S
0 2 1
1
2 2 5
3 6
4
5
6
状态栈 符号栈 输入流 动作
0 # 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
0225 #AAS # 归约 R1 转 S5
025 #AS # 归约 R1 转 S1
01 #S # 成功

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 为可移入终极符，可以有相同者。

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

LALR(1) 分析法

LR(1) 语法分析方法的不足

LR(1) 语法分析方法对展望符的计算比较精确，适应的文法类较广。但 LR(1) 状态机的状态数太多，其构造分析表的工作量及所占的存储空间较大，使其使用和推广受到限制。

解决方法：

  • 合并 LR(1) 状态机中的等价状态
  • 在 LR(0) 状态机中用传播方式求每个项目集的展望符

LALR(1) 的思想来源

LR(1) 的最主要问题是 状态用的太多，以至于有些大语言难以在某些微机上实现。因此，必须给出功能较强且状态数不多的切实可行的方法。

LR(1) 状态机中扩展项集 A 的闭包生成与 LR(0) 是一样的，只是增加了该状态下对 B 的展望符集 b∈First(βa) 部分，以增加对 B 分析完成后 (B→γ·) 是否进行归约的精准判断。

所以 LR(1) 状态机中会由于展望符的不同，使得同一核心项目集被分裂多个不同状态，造成状态数目的剧烈增加，导致时间和空间上的急剧上升；

在 LR(1) 状态机出现很多同心状态，而 LALR(1) 状态机则考虑将 LR(1) 中的同心状态进行合并，从而大大减少状态数，这就是 LALR(1) 和 LR(1) 的主要差别。

同心状态

  • 项目的心：假设 [A→α·β, b] 是 LR(1) 项目，则称其中的 LR(0) 项目部分 A→α·β 为该项目的心。
  • 状态的心：设 S 是 LR(1) 状态机的一个状态，则 S 的所有项目心之和称为状态心，并表示为 Core(S)。
  • 同心状态：如果 LR(1) 状态机中的两个状态具有相同的心，则称它们为同心状态。

  • Core(S) 表示状态 S 的心部分;

    Core(S)= { LR0item | [ LR0item, a]∈S }

    就是状态 S 的所有 LR(0) 项目的集合

  • SameCoreState(S): 所有与 S 同心的状态集 (包括 S);

    SameCoreState(S)=S∪{S′ | Core(S′)=Core(S) }

    状态的心相同的 LR(1) 状态

  • Merge(SS): 同心状态集 SS 中所有状态项目的合并

    Merge(SS)= { LR1item | LR1item∈S, S∈SS }

例子
假设在 LR(1) 状态机中有状态 S1 和 S2:

  S1 = { [A→a·b, a1 ], [B→p·, b1 ] },  S2 = { [A→a·b, a2 ], [B→p·, b2 ] }
  • Core(S1)= { A→a·b, B→p· },
  • Core(S2)= { A→a·b, B→p· } ,
  • SameCoreState( S1 )= { S1, S2 }
  • Merge({S1, S2}) = { [A→a·b, {a1, a2} ], [B→p·, {b1 ,b2}] }

由 LR(1)SM 构造 LALR(1) 可归前缀状态机

有两种构造方式：

  1. 用 LR(1) 状态机来构造：合并 LR(1) 状态机中的等价状态。
    具体描述：按 LR(1) 状态机的方式构造，但发现同心状态时不产生新状态，而是采用合并状态的方法。
  2. 用 LR(0) 状态机来构造：用传播方式求出每个项目的展望符集。

下面只介绍第一种构造方式：

例子：
设有文法 G：

  1. Z→bMb
  2. M→a
  3. M→(L
  4. L→Ma)

其中(4, 9) (5,11) (6, 12) (7, 13) (8, 14) (10, 15) 是可合并的同心状态。

合并后得到：

LALR(1) 分析表的构造

LALR(1) 分析表的构造算法和 LR(1) 分析表的构造算法一样。

LALR(1) 分析条件 | 定义

如果合并同心状态后得到的 LALR(1) 状态机中没有冲突，则称其是 LALR(1) 文法。

合并同心状态带来的问题

因为文法是 LR(1) 文法，所以 S1、S2 都不存在移入-归约冲突和归约-归约冲突。所以：

{u1∪v1}∩a、{u2∪v2}∩a = ∅ u1∩v1、u2∩v2 = ∅

合并后：

{u1∪v1∪u2∪v2}∩a = ∅

没有移入-归约冲突。但是不代表 u1∩u2 和 v1∩v2= ∅。可能产生归约-归约冲突

例子：有如下文法：

  1. Z→aAd
  2. Z→bAc
  3. Z→aBc
  4. Z→bBd
  5. A→e
  6. B→e

LR(1) 可归前缀图中无冲突，但是将 3、4 状态合并以后，产生归约-归约冲突。同时延迟发现错误。

LALR(1) 方法

它具有 SLR(1) 的 状态数少 的优点和 LR(1) 的 适用范围广 的优点。

LALR(1) 方法的功能介于 SLR(1) 和 LR(1) 之间。

LALR(1) 状态机的状态个数和 LR(0) 状态机的状态个数相同，而其展望符则既不采用 SLR(1) 的 Follow 集方法，也不采用 LR(1) 的完全精确法。

LR 方法总结

  • LR(0) 分析方法是最简单的一种，也是建立其他 LR 分析法的基础，但它的缺点是分析能力低，局限性大；
  • SLR(1) 分析方法是一种比较容易实现又极有实用价值的方法，但是有一些文法不能构造出 SLR(1) 分析表；
  • LR(1) 分析方法分析能力最强，能够适应大多数语言的文法，缺点是实现代价过高；
  • LALR(1) 分析方法分析能力介于 SLR(1) 和 LR(1) 之间，合并同心状态后对某些错误发现的时间会产生推迟现象，但仍能够找到错误出现的位置，一般来说 LALR(1) 分析表所占的空间要比原 LR(1) 分析表小得多。

下面从『功能和状态数』两个方面来具体讨论这 4 种分析方法的优缺点。

  • 从功能上看，各种语法分析方法的分析能力从小到大依次为：

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)。

赞 (0)

相关推荐