LR(0)、SLR(1)、LR(1)、LALR(1)

自底向上的语法分析展开目录

从分析树的底部（叶节点）向顶部（根结点）方向构造分析树
可以看成是将输入串 $w$ 规约为文法开始符号 $S$ 的过程
自顶向下的语法分析采用最左推导的方式
自底向上的语法分析采用最左归约的方式（方向构造最右推导）
自底向上语法分析的通用框架 —— 移入 - 归约分析（Shift-Reduce Parsing）

例：移入 - 归约分析
栈内符号串 + 剩余输入 =“规范句型”

移入 - 归约分析的工作过程展开目录

在对输入串的一次从左到右扫描过程中，语法分析将零个或多个输入符号移入到栈的顶端，直到它可以对栈顶的一个文法符号串 $\beta$ 进行归约为止

然后，它将 $\beta$ 归约为某个产生式的左部

语法分析器不断地重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空 (当进入这样的格局时，语法分析器停止运行，并宣称成功完成了语法分析) 为止

移入 - 归约分析其可采取的 4 种动作展开目录

移入：将下一个输入符号移到栈的顶端
归约：被归约的符号串的右端必然处于栈顶。语法分析器在栈中确定这个串的左端，并决定用哪个非终结符来替换这个串
接收：宣布语法分析过程成功完成
报错：发现一个语法错误，并调用错误恢复子例程

LR (0) 分析法展开目录

LR 文法 (Knuth, 1963) 是最大的、可以构造出相应移入 - 归约语法分析器的文法类

L：对输入进行从左到右的扫描
R: 反向构造出一个最右推导序列

LR (k) 分析：需要向前查看 k 个输入符号的 LR 分析。k=0 和 k=1 这两种情况具有实践意义当省略 (k) 时，表示 k=1

LR (0) 项目展开目录

右部某位置标有圆点的产生式称为相应文法的一个 LR (0) 项目（简称为项目）$A \to a_1・a_2$。项目描述了句柄的识别状态

例：$S \to bBB$

$S \to・bBB$ 移进项目
$S \to b・BB$ 待约项目
$S \to bB・B$ 待约项目
$S \to bBB・$ 规约项目

产生式 $A \to \epsilon$ 只生成一个项目 $A \to・$

增广文法（Augmented Grammar）展开目录

如果 G 是一个以 S 为开始符号的文法，则 G 的增广文法 G' 就是在 G 中加上新开始符号 S' 和产生式 $S' \to S$ 而得到的文法
引入这个新的开始产生式的目的是使得文法开始符号仅出现在一个产生式的左边，从而使得分析器只有一个接受状态

文法中的项目展开目录

后继项目（Successive Item）：同属于一个产生式的项目，但圆点的位置只相差一个符号，则称后者是前者的后继项目。例如 $A \to a・X\beta$ 的后继项目是 $A \to aX・\beta$

可以把等价的项目组成一个项目集 (I)，称为项目集闭包 (Closure of Item Sets)，每个项目集闭包对应着自动机的一个状态

CLOSURE () 函数展开目录

计算给定项目集 I 的闭包

$$ CLOSURE(I) = I \cup \{B \to ·\gamma | A \to \alpha·|B\beta \in CLOSURE(I),B \to \gamma \in P\} $$

SetOfltems CLOSURE (I) {
    J = I;
    repeat
        for ( J中的每个项A → α·Bβ )
            for ( G的每个产生式B → γ )
                if ( 项B → ·γ不在J中)
                    将B → ·γ加入J中;
    until 在某一轮中没有新的项被加入到J中；
    return J;
}

GOTO () 函数展开目录

返回项目集 I 对应于文法符号 X 的后继项目集闭包

$$ GOTO(I,X) = CLOSURE(\{A \to \alpha X·\beta | A \to \alpha·X\beta \in I\}) $$

SetOfltems GOTO (I,X) {
    将J 初始化为空集;
    for ( I 中的每个项A → α·Xβ )
        将项A → αX·β 加入到集合J 中;
    return CLOSURE ( J );
}

规范 LR (0) 项集族展开目录

$$ C = \{I_0\} \cup \{I | \exists J \in C, X \in V_N \cup V_T,I = GOTO(J,X)\} $$

void items( G' ) {
    C＝{ CLOSURE ({[ S'→ ·S ] } ) };
    repeat
        for (C中的每个项集I )
            for(每个文法符号X )
                if ( GOTO ( I，X )非空且不在C中)
                    将GOTO ( I，X )加入C中;
    until在某一轮中没有新的项集被加入到C中;
}

LR (0) 分析表构造算法展开目录

SLR 分析法展开目录

由于 LR 分析中可能存在冲突（移进 - 归约冲突、归约 - 归约冲突），因此引入分析能力更强的 SLR (1) 分析法

SLR 分析法的基本思想展开目录

构造 G' 的规范 LR (0) 项集族 $C = \{I_0,I_1,…,I_n\}$
根据 $I_i$ 构造得到状态 i。状态 i 的语法分析动作按照下面的方法决定：
- if $A \to \alpha·a\beta \in I_i$ and $GOTO(I_i,a) = I_j$ then $ACTION[i,a] = s_j$
- if $A \to \alpha·B\beta \in I_i$ and $GOTO(I_i,B) = I_j$ then $GOTO[i,B] = j$
- if $A\to \alpha・\in I_i$ 且 $A ≠ S'$ then for $\forall a \in FOLLOW (A)$ do $ACTION [i,a] = r_j$（$j$ 是产生式 $A \to \alpha $ 的编号）
- if $S'\to S·\in I_i$ then ACTION[i,$] = acc
没有定义的所有条目都设置为 "error"

如果给定文法的 SLR 分析表中不存在有冲突的动作，那么该文法称为 SLR 文法

用一句话概括 SLR 分析表的构造算法：移进策略与 LR (0) 分析法相同，只有归约时不同，仅对当前产生式左部字母的 Follow 集进行归约

LR (1) 分析展开目录

SLR 分析存在的问题：SLR 只是简单地考察下一个输入符号 b 是否属于与归约项目 $A\to α$ 相关联的 FOLLOW(A)，但 $b \in FOLLOW (A)$ 只是归约 $alpha$ 的一个必要条件，而非充分条件

对于产生式 $A\to α$ 的归约，在不同的使用位置，A 会要求不同的后继符号
在特定位置，A 的后继符集合是 FOLLOW (A) 的子集

规范 LR (1) 项目展开目录

将一般形式为 $[A\to \alpha・\beta,a]$ 的项称为 LR (1) 项，其中 $A\to \alpha \beta$ 是一个产生式，$a$ 是一个终结符 (这里将 $ 视为一个特殊的终结符) 它表示在当前状态下，A 后面必须紧跟的终结符，称为该项的展望符 (lookahead)

LR (1) 中的 1 指的是项的第二个分量的长度
在形如 $[A\to \alpha・\beta,a]$ 且 $\beta ≠ \epsilon$ 的项中，展望符 a 没有任何作用
但是一个形如 $[A\to \alpha・,a]$ 的项在只有在下一个输入符号等于 a 时才可以按照 $A\to \alpha・$ 进行归约
这样的 a 的集合总是 FOLLOW (A) 的子集，而且它通常是一个真子集

如果除展望符外，两个 LR (1) 项目集是相同的，则称这两个 LR (1) 项目集是同心的。例如，再上图的 LR (1) 自动机中，$I_4$ 和 $I_{11}$ 是同心集，$I_5$ 和 $I_{12}$ 是同心集，$I_1$ 和 $I_{13}$ 是同心集，$I_8$ 和 $I_{10}$ 是同心集

LR (1) 项目集闭包展开目录

$CLOSURE(I) = I\cup \{[B\to·\gamma,b] | [A\to \alpha·B\beta,a] \in CLOSURE(I), B\to \gamma \in P, b\in FIRST(\beta a)\}$

SetOfltems CLOSURE ( I ) {
    repeat
        for ( I中的每个项[A → α·Bβ，a ])
            for (G'的每个产生式B → γ)
                for ( FIRST (βa)中的每个符号b )
                    将[ B → · γ ，b]加入到集合I中;
    until 不能向I中加入更多的项;
    until I;
}

GOTO 函数展开目录

$GOTO(I,X) = CLOSURE(\{[A\to \alpha X·β,a]|[A\to \alpha·X\beta,a]\in I\})$

SetOfltems GOTO ( I，X ) {
    将J 初始化为空集;
    for ( I 中的每个项[A → α·Xβ，a ])
        将项[ A → αX·β，a]加入到集合J 中;
    return CLOSURE ( J );
}

构造文法 G' 的 LR (1) 项目集族展开目录

void items (G' ) {
    将C初始化为{CLOSURE ({[ S' → · S, $]} )};
    repeat
        for ( C中的每个项集I )
            for ( 每个文法符号X )
                if (GOTO(I，X )非空且不在C中)
                    将GOTO(I，X )加入C中;
    until 不再有新的项集加入到C中;
}

LR 分析表构造算法展开目录

构造 G' 的规范 LR (1) 项集族 $C = \{I_0,I_1,…,I_n\}$
根据 $I_i$ 构造得到状态 i。状态 i 的语法分析动作按照下面的方法决定：
- if $[A\to \alpha·a\beta,b] \in I_i$ and $GOTO(I_i,a) = I_j$ then $ACTION[i,a]=sj$
- if $[A\to \alpha·B\beta,b] \in I_i$ and $GOTO(I_i,B) = I_j$ then $GOTO[i,B]=j$
- if $[A\to \alpha・,a] \in I_i$ 且 $A ≠ S'$ then $ACTION [i,a]=rj$（$j$ 是产生式 $A\to \alpha$ 的编号）
- if $S' \to S \cdot \in I_i$ then ACTION [i,$] = acc
没有定义的所有条目都设置为 "error"

如果 LR (1) 分析表中没有语法分析动作冲突，那么给定的文法就称为 LR (1) 文法

LALR 分析法展开目录

LALR (lookahead-LR) 分析的基本思想如下：

寻找具有相同核心的 LR (1) 项集，并将这些项集合并为一个项集。所谓项集的核心就是其第一分量的集合
然后根据合并后得到的项集族构造语法分析表
如果分析表中没有语法分析动作冲突，给定的文法就称为 LALR(1) 文法，就可以根据该分析表进行语法分析

合并同心项集不会产生移进 - 归约冲突，但是有可能产生归约归约冲突。因为合并的时候合并的是同心项的展望符，而展望符只在规约的时候起作用，在移入的时候是不起作用的，只要合并前各个同心项目集本身是没有冲突的，就不会有冲突

LALR 的特点展开目录

形式上与 LR (1) 相同
大小上与 LR (0) 和 SLR 相当
分析能力介于 SLR 和 LR (1) 二者之间
合并后的展望符集仍为 FOLLOW 集的子集

Catalog