5 LR(0)自动机

$LR(k)$ 语法分析

L 表示对输入从左向右扫描，R 表示反向构造一个最右推导序列。

k 表示在做语法分析决定时向前看 k 个符号。即当我们在一个最右句型中看到某个产生式右部时，再向前看 k 个符号就可以决定是否采用这个产生式进行规约。

$k=0,1$ 的情况是具有实践意义的，只考虑这两种情况。

如果省略 k，默认 $k=1$ 。

LR 语法分析的优点

几乎所有上下文无关文法都可以构造出相应的 LR 语法分析器
LR 语法分析是已知的最通用的无回溯的移进-规约分析技术，并且也很高效
LR 语法分析器在扫描时尽可能早地检测到错误
LR(k) 语法分析的要求比 LL(k) 宽松，所以后者能描述的语言前者也能描述

预备工作

项（目）

移进-规约（S-R）冲突的产生提示我们，可以通过维护一些状态，来表明我们现在的语法分析所处的位置，从而方便做出 S-R 决策。

定义：上面所说的状态代表的是某些项的集合

那什么是项呢？一个文法 G 的一个产生式，比如 $A→XYZ$ 可以产生四个 LR(0) 项：

$A→·XYZ$
$A→X·YZ$
$A→XY·Z$
$A→XYZ·$

这里面的点表示的是我们的分析情况，如：

$A→·XYZ$ 表示我们希望接下来从输入中看到一个从 $XYZ$ 推导出来的串
$A→X·YZ$ 表示我们已经看到了一个 $X$ 推导的串，接下来想从输入中看到一个从 $YZ$ 推导出来的串
$A→XYZ·$ 表示我们已经看到了一个 $XYZ$ 推导的串，是时候将其规约为 $A$ 了

规范 $LR(0)$ 项集族的构造

一个 规范 LR(0) 项集族 是一些项集的集合（所以被称之为集族）。

增广文法 $G'$

设 $G$ 是一个以 $S$ 为开始符号的文法，则其增广文法 $G'$ 就是在 $G$ 中加上新的开始符号 $S'$ 和产生式 $S'→S$ 得到的文法

引入这个新的产生式的目的：告诉语法分析器何时（当且仅当要使用 $S'→S$ 规约时）应该停止并宣告接受

CLOSURE 函数（闭包）

CLOSURE 函数是作用在项集 $I$ 上的一个函数，得到 $I$ 的闭包

算法：

（1）将 $I$ 中的项全部加入 $C(I)$ 中

（2）如果某个 $A→\alpha·B\beta\in C(I)$ ， $B→\gamma$ 是一个产生式，且 $B→·\gamma$ 不在 $C(I)$ 中，就把 $B→·\gamma$ 加入 $C(I)$

（3）对 $C(I)$ 中的项 $A→\alpha·B\beta$ 遍历，对于项又遍历 $B→\gamma$ ，不断应用（2），直到没有新项可以加入为止

注意：

闭包运算的结果往往非常大，考虑到存储空间的问题，一个闭包运算的结果 $C(I)$ 可以被划分为两个部分：

内核项：包括初始项 $S'→S$ 和点不在最左侧的所有项
非内核项：除了 $S'→S$ 之外的点在最左侧的所有项

可以看出，求闭包时，（2）加入的项不可能是内核项，而所有非内核项可以在运行时临时计算，不必在一开始就全部计算出然后保存。

GOTO 函数

$GOTO(I,X)$ ，其中 $I$ 是一个项集， $X$ 是一个文法符号。

$GOTO(I,X)$ 被定义为 $I$ 中所有形如 $A→\alpha·X\beta$ 的项所对应的项 $A→\alpha X·\beta$ 集合的闭包，形式上来说：

$\begin{aligned} I'(I, X) &= \{A→\alpha X·\beta|A→\alpha·X\beta\in I\}\newline GOTO(I,X)&=C(I'(I,X)) \end{aligned}$

直观上来说， $GOTO$ 函数定义了一个文法的 LR(0) 自动机中的转换， $GOTO(I,X)$ 就是当输入为 $X$ 时离开状态 $I$ 的转换。

构造规范 LR(0) 项集族

void items(G’) {
    C = {CLOSURE({[S’→·S]})}                // 需要计算CLOSURE
    repeat {
        for (C中的每个项集I)
            for (每个文法符号X)
                if (GOTO(I,X)非空且不在C中)   // 需要计算GOTO
                    将GOTO(I,X)加入C中
    }
    until 某一轮中没有新的项集加入C中
}

GOTO 函数和 LR(0) 规范项目集族组成了一个 LR(0) 状态的自动机。

本文阅读量