跳转至

8 规范LR和LALR

更强大的 LR 语法分析器

（1）(规范) LR：使用 LR(1) 项目集

（2）向前看 LR（LALR）：基于 LR(0) 项目集族

LR(1) 项目集

和 LR(0) 项目的区别在于每个项目都带一个搜索符（lookahead），如 $$ [A→\alpha·\beta,a] $$ 表示 A 之后紧跟 a，如果存在 S\Rightarrow_{rm}^*\delta Aw\Rightarrow_{rm}\delta\alpha\beta w，则 a 是 w 的第一个符号，或者 w 是 \varepsilon 且 a 是 \$

LR(1) 项目集族构造算法 items(G')

输入：一个拓广文法 G'

求闭包 c(I) 的算法：

image-20221016131242286

计算 goto(I,X) 的算法（X 是文法符号，可以是终结符也可以是非终结符）：

image-20221016132450061

计算 items(G') 的算法：

image-20221016132750679

举例

考虑下面的增广文法，求项集：

  1. S'→S
  2. S→CC
  3. C→cC|d

按如下思路进行：

  • 计算 c([S'→·S,\$])，进入第一个 for 循环
  • 进入第二个 for 循环，此时满足条件的产生式只有 S→CC
  • 计算 FIRST(\varepsilon\$) = \{\$\}，进入第三个 for 循环
  • 闭包中加入 [S→·CC,\$]，跳回第一个 for 循环
  • 对刚刚新加入这一个，进入第二个 for 循环，此时满足条件的产生式为 C→cC|d
  • 计算 FIRST(C\$) = FIRST(C) = \{c,d\}，第一个等号是因为 C 不能推导出空串
  • 闭包中加入 [C→·cC,c/d],[C→·d,c/d]
  • 上面新加入的两个项，点的后面都不是非终结符，所以进行到这就结束了
  • 第一个项集 I_0 就由如上四个项组成
  • 得到初始项集 I_0 后，就可以用 goto 函数计算其他项集了

注意

在求 LR(1) 项目集时，经常会看到多个 LR(1) 项目具有相同的第一分量，只有搜索符不同。之后会深入讨论这个现象。

规范的 LR(1) 分析

LR(1) 规范项目集族

按上面的算法构造项目集族 C=\{I_0,...,I_m\}

ACTION 函数表

  • 如果 [A→\alpha·a\beta,b]\in I_i 且 goto(I_i,a)=I_j，则 action(i,a)=sj
  • 如果 [A→\alpha·,a]\in I_i 且 A\neq S'，则 action[i,a]=rj
  • 如果 [S'→S·,\$]\in I_i，则 action[i,\$]=acc
  • 其他未定义的条目都是 error

注意到，SLR 是根据 Follow(A) 来确定归约动作，这里是根据搜索符（上下文信息）来确定。

如果没有多重定义的条目，该文法就称之为 LR(1) 文法，如果不会引起误解的话可以省略 (1)

GOTO 函数表

  • 如果 goto(I_i,A)=I_j，则 goto[i,A]=j
  • 其他未定义的条目都是 error

LALR 分析

规范 LR(1) 产生的状态数目偏多，LALR 是介于 SLR 和 LR 之间的一种分析方法。

需要寻找同心的 LR(1) 项目集，把这些同心集合合并成一个项目集（搜索符也要合并），如把 [C→d·,c/d] 与 [C→d·,\$] 合并成 [C→d·,c/d/\$]

此时，同心集合并带来的影响可能导致最多一步是错误的，而这一步必定会在对下一个输入字符做操作时被发现并报告错误。

  • goto(I, X) 的心仅仅依赖于 I 的心，被合并集合的 goto 函数结果也可以合并
  • action 函数可能要做修改
  • 对 LR(1) 文法合并所有同心集不会导致新的移进-规约冲突，但可能导致新的规约-规约冲突

—— 不会导致新的移进-规约冲突

如果存在，比如面临 a，有一个项目 [A→\alpha·,a] 要求规约，另一个 [B→β·aγ,b] 要求移进，说明合并前就有两个同心的项集包含 [A→\alpha·,a],[B→\beta·a\gamma,c]，合并前这种冲突就存在了。

—— 可能导致新的规约-规约冲突

image-20221123193544897

一种简易但耗空间的 LALR 分析表构造法

输入：拓广文法 G'

（1）构造 LR(1) 项目集族 C=\{I_0,...,I_n\}

（2）合并同心集至 C'=\{J_0,...,J_m\}

（3）以与规范 LR 同样的方式构造 action 表，如果有冲突表示文法不是 LALR(1) 的

（4）设某个状态 J=I_1\cup I_2\cup ...\cup I_h，则 K=goto(J,X) 是所有和 goto(I_1,X) 同心的项目集的并集，也就是全部合并，goto(J,X)=K

高效构造 LALR 语法分析表的方法

目标：使得在创建 LALR(1) 分析表的过程中不需要构造完整的 LR（1）规范项目集族

  • 只使用内核项来表示 LR(0/1) 项集：只使用 [S'→S(,\$)] 以及那些点不在产生式左端的项来表示项集
  • 使用 “传播和自发生成” 来生成 LA 符号：根据 LR(0) 项目的内核生成 LALR(1) 项目的内核
  • 用 CLOSURE 函数对 LALR(1) 内核求 LR(1) 闭包：把这些项集当作规范 LR(1) 项集族

这一块教材没讲，龙书 175 页左右，有需要再看。

本文阅读量