引言

语法分析器的作用

输入：词法分析器输出的词法单元序列
输出：语法树表示
语法分析器功能
- 验证输入源程序的合法性，输出良构程序的语法结构
- 对于病构的程序，能够报告语法错误，进行错误恢复
语法分析器的类型
- 通用型
- 自顶向下：通常处理LL文法（从左到右扫描字符）
- 自底向上：通常处理LR文法
类型检查，语义分析，翻译生成中间代码等往往和语法分析过程交错完成，实践中往往和语法分析放入一个模块，图上用“前端的其余部分”表示上述活动

文法

一种用于描述程序设计语言语法的表示方法，能够自然地描述程序设计语言构造的层次化语法结构

文法给出了一个程序设计语言的精确易懂的语法规约
可以基于文法构造语法分析器，帮助确定源程序的语法结构
语法结构有助于把源程序翻译为正确的目标代码
文法的扩展性，有助于迭代的语言演化

代表性文法

LR文法类

该文法指明了运算符的结合性和优先级
各式的解释：
- $E$ 表示一组以 $+$ 分隔的项所组成的表达式
- $T$ 表示一组以 $*$ 分隔的项所组成的表达式
- $F$ 表示因子，可能是括号括起来的表达式，也可能是标识符$id$
属于LR文法类，适用于自底向上的语法分析技术
是左递归的，不能用于自顶向下的语法分析

LL文法

上面文法的无左递归版本，可用于自顶向下的语法分析

上下文无关文法

上下文无关文法(Context Free Grammar, CFG)
上下文无关文法是一种能够很好描述程序设计语言的表示方法

上下文无关文法的定义

一个CFG由以下几个部分构成
- 终结符号
  - 组成串的基本符号，与“词法单元名字”同义
  - 上例中，终结符号为关键字 $if$ 和 $else$ 以及左右括号
- 非终结符号
  - 语法变量，表示特定串的集合
  - 给出了语言的层次结构，这种层次结构是语法分析和翻译的关键
  - 上例中，非终结符号为 $stmt$ 和 $expr$
- 一个开始符号
  - 某个特定的非终结符号，其表示的串集合是这个文法生成的语言
- 一组产生式
  - 描述将终结符号和非终结符号组合成串的方法，由下列元素组成
    - 产生式左部（头）是一个非终结符号
    - 符号 “ → ” ，有时用 $::=$ 代替箭头
    - 一个由零个或多个终结符号与非终结符号组成的产生式右部（体）

上下文有关文法与上下文无关文法

什么是上下文？
- 在应用一个产生式进行推导时，前后已经推导出的部分结果就是上下文
- 上下文无关的意思是，只要文法的定义里有某个产生式，不管一个非终结符前后的串是什么，就可以应用相应的产生式进行推导
文法的分类
- 上下文有关文法
- 上下文无关文法

一个简单的上下文无关文法例子

其中英文字母都是非终结符（SVO 分别表示主谓宾），汉字都是终结符
可推导出“天吃肉”。其（最左）推导过程为：Sent -> SVO -> 天VO -> 天吃O -> 天吃肉

一个简单的上下文有关文法例子

其中英文字母都是非终结符（SVO 分别表示主谓宾），汉字都是终结符
可推导出“人吃饭”。过程：Sent -> SVO -> 人VO -> 人吃O -> 人吃饭

用于描述算术表达式的文法定义

推导

产生式又可称为重写规则（Rewriting rule）
推导
- 将待处理的串中的某个非终结符号替换为这个非终结符号的某个产生式的体
- 从开始符号出发，不断进行上面的替换，就可以得到文法的不同句型
推导的实例
- 文法: E → -E | E+E | E*E | (E) | id
- 从E到-(id)的推导序列：E => -E => -(E) => -(id)
推导的一般性定义
- 如果$A\rightarrow \gamma$是一个产生式，那么$\alpha A \beta \Rightarrow \alpha \gamma \beta$
- 经过零步或者多步推导出：$\mathop{\Longrightarrow}\limits^{*}$
  - 对于任何串$\alpha$, $\alpha \mathop{\Longrightarrow}\limits^{*}\alpha$
  - 如果$\alpha \mathop{\Longrightarrow}\limits^{} \beta$且$\beta \mathop{\Longrightarrow}\limits^{} \gamma$，那么$\alpha \mathop{\Longrightarrow}\limits^{*} \gamma$
- 经过一步或者多步推导出：$\mathop{\Longrightarrow}\limits^{+}$
  - $\alpha \mathop{\Longrightarrow}\limits^{*} \beta$且$\alpha$不等于$\beta$等价于$\alpha \mathop{\Longrightarrow}\limits^{+} \beta$
- 最左(右)推导
  - 符号：$\mathop{\Longrightarrow}\limits{lm}^{*}, \mathop{\Longrightarrow}\limits{rm}^{*}$
推导实例

句型/句子/语言

句型（sentential form）
- 如果$S \mathop{\Longrightarrow}\limits^{*} \alpha$，那么$\alpha$就是文法的一个句型
- 可能既包含非终结符，又包含终结符号；可以是空串
句子（sentence）
- 文法的句子就是不包含非终结符号的句型
语言
- 文法G的语言就是G的句子的集合，记为L(G)
- $\omega$在L(G)中当且仅当$\omega$是G的句子，即$S \mathop{\Longrightarrow}\limits^{*} \omega$

推导的问题

从推导的角度看，语法分析的任务是：接受一个终结符号串作为输入，找出从文法的开始符号推导出这个串的方法
推导中可能遇到的两个问题
- 每一步替换哪个非终结符号？
- 若以这个非终结符号为头的产生式有多个，用哪个产生式的右部替换？

非终结符号的替换顺序

通常使用两种方式进行推导
- 最左推导：总是选择每个句型的最左非终结符号。记作$\mathop{\Longrightarrow}\limits_{lm}$
- 最右推导：总是选择最右边的非终结符号。记作$\mathop{\Longrightarrow}\limits_{rm}$
每个最左推导步骤可以写成 $\omega A \gamma \mathop{\Longrightarrow}\limits_{lm} \omega \delta \gamma$
- 应用产生式: $A \rightarrow \delta$
如果$\alpha$经过最左推导得到$\beta$，记作$\alpha \mathop{\Longrightarrow}\limits_{lm}^{*} \beta$
最左句型：S是文法G的识别符号，如果$S \mathop{\Longrightarrow}\limits_{lm}^{*} \alpha$ ，则$\alpha$是G的最左句型
最右推导也有类似的定义。最右推导有时也称为规范推导
- 此例中第一行为最左推导，第二行为最右推导

语法分析树

推导的图形表示形式
- 根结点的标号是文法的开始符号
- 每个叶子结点的标号是非终结符号、终结符号或$\epsilon$
- 每个内部节点的标号是非终结符号
- 每个内部结点表示某个产生式的一次应用
  - 内部结点的标号为产生式头，结点的子结点从左到右是产生式的体
有时允许树的根不是开始符号（对应于某个短语）
树的叶子组成的序列是根的文法符号的句型
一棵分析树可对应多个推导序列，但是分析树和最左（右）推导序列之间具有一一对应关系

推导的图形表示形式，树上看不出来推导的顺序
能够反映串的语法层次结构
语法分析树
- 内部节点：对应于一个非终结符号
- 子节点：对应于其父节点为头的产生式体
- 叶子节点：可以是终结符号或非终结符号，从左到右排列可以得到一个句型，称为这棵树的结果

推导和语法树

考虑任意的推导$\alpha{1} \Rightarrow \alpha{2} \Rightarrow…\Rightarrow \alpha{n}$，其中$\alpha{1}$是单个非终结符$A$
对于推导中的每个句型$\alpha{i}$ ，我们都可以构造出一个结果为$\alpha{i}$的语法树
上例的推导过程

二义性文法

如果一个文法可以为一个句子生成多棵不同的语法分析树，则该文法为二义性文法
通常情况下，我们需要无二义性的文法

二义性

程序设计语言的文法通常都应该是无二义性的
- 否则就会导致一个程序有多种“正确”的解释
- 如上例(a)图按照常规运算优先级处理了，而(b)则没有
但有些二义性的情况可以方便文法或语法分析器的设计
- 需要消二义性规则来剔除不要的语法分析树
- 比如：先乘除后加减

文法及其生成的语言

语言是由文法的开始符号出发，能够推导得到的所有句子的集合

验证文法生成的语言

验证文法G生成语言L可以帮助我们了解文法可以生成什么样的语言

词法分析与语法分析

上下文无关文法和正则表达式
正则表达式 → 词法
上下文无关文法 → 语法

二者比较

文法比正则表达式描述能力更强
正则表达式描述词法单元比较简洁
基于正则表达式构造的词法分析器效率更高
正则表达式适合描述词法结构，文法适合描述嵌套结构

补充

文法的类别，Chomsky文法类

上下文无关文法和正则表达式✨

上下文无关文法的表达能力更强
- 证明：
每个正则表达式都可以用一个上下文无关文法来描述，反之不成立
每个正则语言都是一个上下文无关语言，反之不成立

文法的设计

程序设计语言所需要的文法
- 上下文无关文法足够用来描述语法吗？
  - 标识符必须先声明后使用
- 语法分析器能够完全按照上下文无关文法来构造吗？
  - 二义性、左递归的文法可能给语法分析器造成很大麻烦
可以怎么做？
- 改造语法分析器，添加语义规则，使它可以做得更多
- 改造上下文无关文法，消除二义性和左递归
在进行高效的语法分析之前，需要对文法做以下处理
- 消除二义性
  - 文法的二义性：文法可以为一个句子生成多颗不同的树
- 消除左递归
- 提取左公因子

消除文法的二义性

二义性实例
一些二义性文法可以被改成等价的无二义性的文法
例子
改写文法，基本思想: 在一个then和一个else之间出现的语句必须是“已匹配的”。也就是说then和else中间的语句不能以一个尚未匹配的then结尾
解决方案：引入新的非终结符号matched_stmt，用来区分是否是成对的then/else
注
- 二义性的消除方法没有规律可循
- 通常并不是通过改变文法来消除二义性

消除左递归

立即左递归的消除

示例

消除多步左递归

消除立即左递归的方法并不能消除因为两步或多步推导而产生的左递归

消除算法

通用的左递归消除方法

示例

提取左公因子

在推导的时候，不知道该如何选择（自顶向下算法会详细描述）

提取左公因子算法

非上下文无关语言的构造

抽象语言 L1={wcw | w在(a|b)*中}
这个语言不是上下文无关的语言
它抽象地表示了C或者Java中“标识符先声明后使用”的规则
- 说明了C/Java这些语言不是上下文无关语言，不能使用上下文无关文法描述
- 通常用上下文无关文法描述其基本结构，不能用文法描述的特性在语义分析阶段完成。原因是上下文无关文法具有高效的处理算法

自顶向下语法分析

自顶向下分析技术

自顶向下分析可以被看作是为输入串构造语法分析树的问题，也可以看作一个寻找输入串的最左推导的过程
问题
- 在推导的每一步，对非终结符号A，应用哪个产生式，以可能产生于输入串相匹配的终结符号串

自顶向下语法分析

问题：对于非终结符号A，选择哪一个产生式
一种通用的递归下降分析框架
- 由一组过程组成，每个非终结符号对应一个过程
- 程序的执行从开始符号对应的过程开始
- 每个过程的功能是：选择一个产生式体，扫描相应的句子。若遇到非终结符号，调用该符号对应的过程

递归下降过程

可能需要回溯
回溯显然是笨方法

预测分析法简介

试图从开始符号推导出输入符号串
以开始符号作为初始的当前句型
每次为最左边的非终结符号选择适当的产生式
- 通过查看下一个输入符号来选择这个产生式
- 有多个可能的产生式时预测分析法无能为力
需要提取公因子

预测分析技术

一种确定性的、无回溯的分析技术
在每一步选择正确的产生式
通过在输入中向前看固定多个符号来选择正确的产生式
通常情况下，我们只需要向前看一个符号
递归下降分析一般只适合于每个子表达式的第一个终结符能够为产生式选择提供足够信息的那些文法
给出两个与文法相关的两个函数
- FIRST
- FOLLOW
基于上述两个函数，可以根据下一个输入符号来选择应用哪个产生式

FIRST和FOLLOW

在自顶向下的分析技术中，通常使用向前看几个符号来唯一地确定产生式（这里假定只看一个符号）
$FIRST(\alpha)$
$FOLLOW(A)$
- 可能在某些句型中紧跟在A右边的终结符号的集合

$FIRST(\alpha)$

First的计算

$FOLLOW$函数

FOLLOW计算

LL(1)文法

LL(1)文法，第一个L表示自左向右扫描，第二个L指产生最左推导，而1则表示向前看一个输入符号
LL(1)文法可以利用不回溯的确定性的预测分析技术，因为只需要检查当前输入符号就可以为一个非终结符号选择正确的产生式
定义：对于文法的任意两个不同的产生式A→α|β
- 不存在终结符号a使得α和β都可以推导出以a开头的串
- α和β最多只有一个可以推导出空串
- 如果β可以推导出空串，那么α不能推导出以FOLLOW 中任何终结符号开头的串
等价于
对于LL(1)文法，可以在自顶向下分析过程中，根据当前输入符号来确定使用的产生式

LL(1)文法的预测分析技术

LL(1)文法 ==>预测分析表
将First和Follow集合中的信息放入一个预测分析表M[A,a]，该预测表告诉我们当非终结符号为A，当前输入符号为a时，要选择哪条产生式

预测分析表构造

输入：文法G
输出：预测分析表M
方法：对于文法G的每个产生式A→α，进行如下处理
- 对于First(α)中的每个终结符号a，将A→α加入到M[A,a]
- 如果$\epsilon$在First(α)中，那么对于Follow(A)中的每个终结符号b，将A→α加入到M[A,b]中
- 如果$\epsilon$在First(α)中，且$在Follow(A)中，将A → α加入到 M[A,$]中 ◼
完成上述操作后，若M[A,a]中没有产生式，填为Error

预测分析方法

对于任何文法G，都可以构造预测分析表
对于LL(1)文法，预测表中每个条目都唯一地指定了一个产生式，或者标明Error

二义性文法的预测分析表

对于某些文法，表中可能会有一些多重定义的条目，比如左递归或二义性文法

非递归的预测分析

在自顶向下分析的过程中，我们总是
- 匹配掉句型中左边的所有终结符号
- 对于最左边的非终结符号，我们选择适当的产生式展开
- 匹配成功的终结符号不会再被考虑，因此我们只需要记住句型的余下部分，以及尚未匹配的输入终结符号串
- 由于展开的动作总是发生在余下部分的左端，我们可以用栈来存放这些符号
分析处理过程
- 初始化时，栈中仅包含开始符号
- 如果栈顶元素是终结符号，那么进行匹配
- 如果栈顶元素是非终结符号
  - 使用预测分析表来选择适当的产生式
  - 在栈顶用产生式右部替换产生式左部
- 对所有文法的预测分析都可以共用同样的驱动程序

非递归的预测分析技术

文法符号栈
输入缓冲区
控制程序

分析表驱动的预测分析器

性质1：如果栈中的符号序列为α，而w‘是已经被读入的部分输入，w’是尚未处理的输入，那么
- S推导出wα
- 我们试图从α推导出余下的输入终结符号串w’
预测分析程序使用M[X,a]来扩展X，将此产生式的右部按倒序压入栈中
请注意：这样的操作使得分析过程中性质1得到保持

表驱动的非递归的预测语法分析

输入：一个串w，文法G的预测分析表M
输出：如果w在L(G)中，输出w的一个最左推导；否则报错
方法：初始化输入缓冲区为w$, 栈顶是G的开始符号S，下面是$

自底向上语法分析

概述

为一个输入串构造语法分析树的过程
从叶子（输入串中的终结符号，将位于分析树的底端）开始，向上到达根结点
重要的自底向上语法分析的通用框架
- 移入-归约
LR：最大的可以构造出移入-归约语法分析器的语法类

归约

Bottom-Up Parsing
Bottom-up parsing – 将一个串w归约为文法符号的过程
在每一步的归约中，一个与某产生式体相匹配的特定子串被替换为该产生式头部的非终结符号，一次归约实质上是一个推导的反向操作

归约的例子

id * id的归约过程
- id id ，F id，T id，T F，T，E
对于句型T * id，有两个子串和某产生式右部匹配
- T是E → T的右部
- id是F → id的右部
- 为什么选择将id归约为F，而不是将T归约为E？
  - T归约为E之后，E * id不再是句型

规约

自底向上分析的过程也是规约的过程
规约的问题：
- 选择哪部分进行归约?
- 应用哪个产生式进行归约?

回顾：句型/句子/语言

句柄

最右句型γ的一个句柄
- 满足下述条件的产生式A→β及串β在γ中出现的位置
- 条件：将这个位置上的β替换为A之后得到的串是γ的某个最右推导序列中出现在位于γ之前的最右句型
通俗地说
- 句柄是最右推导的反向过程中被规约的那些部分
句柄的作用
- 对句柄的规约，代表了相应的最右推导中的一个反向步骤
句柄是最右推导的反向过程中被规约的那些部分

句柄剪枝

注意：
- 归约前后都是最右句型
- 和某个产生式匹配的最左子串不一定是句柄
- 无二义性的文法，其每个最右句型都有且只有一个句柄

移入-归约语法分析框架

一种自底向上的分析形式
使用一个栈保存文法符号，一个输入缓冲区存放将要进行分析的剩余符号
初始栈： $ 初始输入 w$
对输入串的一次从左到右的扫描过程中，语法分析器将零个或多个输入符号移到栈的顶端，直到它可以对栈顶的一个文法符号串进行归约为止。它将归约为某个产生式的头。不断重复这个循环，直到它检测到一个语法错误，或者栈中包含了开始符号且输入缓冲区为空
分析成功时：栈 $ S, 输入 $
可行性分析：句柄总是出现在栈的顶端，绝不会出现在栈的中间
- 语法分析器进行一次归约以后，都必须接着移入零个或多个符号才能在栈顶找到下一个句柄
- 不需要去栈中间去寻找句柄

移入-归约分析技术

使用一个栈来保存归约/扫描移入的文法符号
栈中符号（从底向上）和待扫描的符号组成了一个最右句型
开始时刻：栈中只包含$，而输入为w$
成功结束时刻：栈中$S，而输入$
在分析过程中，不断地移入符号，并在识别到句型时进行归约

主要分析动作

移入：将下一个输入符号移动到栈顶
归约：将句柄归约为相应的非终结符号
- 句柄总是在栈顶
- 具体操作时弹出句柄，压入被归约到的非终结符号
接受：宣布分析过程成功完成
报错：发现语法错误，调用错误恢复子程序

冲突

移进/归约冲突

移入-归约技术并不能处理所有上下文无关文法
某些上下文无关文法（比如二义性文法）
- 移入/归约冲突：栈中的内容和接下来的k个输入符号，都不能确定进行移入还是归约操作 (不能确定是否是句柄)
- 归约/归约冲突：存在多个可能的归约到不同非终结符号的归约(不能确定句柄归约到那个非终结符号)

归约/归约冲突

解决冲突问题

让词法分析区分id和procid
用[]表示数组，用()表示函数
……
但是并不能完全解决冲突问题
有一类文法可以解决句柄查找及归约唯一性的问题

LR语法分析技术

LR(k)的语法分析概念
- L表示最左扫描，R表示反向构造出最右推导
- k表示最多向前看k个符号
当k的数量增大时，相应的语法分析器的规模急剧增大
- K=2时，程序设计语言的语法分析器的规模通常非常庞大
- 当k=0、1时已经可以解决很多语法分析问题，因此具有实践意义
- 因此，我们只考虑k<=1的情况

LR语法分析器的优点

表格驱动
- 虽然手工构造表格工作量大，但表格可以自动生成
对于几乎所有的程序设计语言，只要写出上下文无关文法，就能够构造出识别该构造的LR语法分析器
最通用的无回溯移入-归约分析技术，且和其它技术一样高效
可以尽早检测到错误
能分析的文法集合是LL(k)文法的超集

LR分析相关概念

移入-归约语法分析器如何知道何时该移入、何时该归约呢？
- LR语法分析器试图用一些状态来表明我们在移进归约语法分析过程中所处的位置，从而做出移入-归约决定
项的意义
- 指明在语法分析过程中的给定点上，我们已经看到了一个产生式的哪些部分。或者说，如果我们想用这个产生式进行归约，还需要看到哪些文法符号
项的集合（项集）对应于一个状态

LR(0)项

文法的一个产生式加上在其产生式体中某处的一个点
- A →.XYZ，A → X.YZ，A → XY.Z，A → XYZ.
- 注意：A → ε只对应一个项A →.
直观含义
- 项A → α.β表示已经扫描/归约到了α，并期望接下来的输入中经过扫描/归约得到β，然后把αβ归约到A
- 如果β为空，表示我们可以把α归约为A
项也可以用一对整数表示
- (i,j)表示第i条规则，点位于右部第j个位置

规范LR(0)项集族

规范LR(0)项集族提供构建LR(0)自动机的基础
- LR(0)自动机可用于做出语法分析决定
- LR(0)自动机中每个状态代表了LR(0)项集族中的一个项集

以项为基础构造自动机

构造以项为状态的自动机
- 开始状态S’ →.S
- 转换
  - A → α.Bβ到B →. γ有一个ε转换
  - 从A → α.Xβ到A → αX.β有一个X转换
- 接受状态：A → α.，即点在最后的项

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

三个概念
- 增广文法
- 项集闭包：CLOSURE
- GOTO
增广文法
- G的增广文法G’是在G中增加新开始符号S’，并加入产生式S’→S而得到的
- G’和G接受相同的语言，且按照S’→ S进行归约实际上就表示已经将输入符号串归约成为开始符号
- 引入的目的是告诉语法分析器何时宣布接受输入符号串，即用S’→S进行归约时，表明分析结束。
构造过程中用到的子函数
- CLOSURE(I)：I的项集闭包
  - 对应于DFA化算法的 ε-CLOSURE
- GOTO(I,X)：I的X后继
  - 对应于DFA化算法的MOVE(I,X)

CLOSURE(I)的构造算法

如果I是文法G的一个项集，那么CLOSURE(I)就是根据下列规则从I构造得到的项集
- 将I中的各个项加入到CLOSURE(I)中
- 如果A → α.Bβ在CLOSURE(I)中，那么对B的任意产生式B → γ，将B →.γ加到CLOSURE(I)中
- 不断重复第二步，直到收敛
第二步的意义
- 项A → α.Bβ表示期望在接下来的输入中归约到B
- 显然，要归约到B，首先要扫描归约到B的某个产生式的右部
- 因此对每个产生式B → γ，加入B →.γ
  - 表示它期望能够扫描归约到γ

项集闭包构造的例子

增广文法：
- E’ → E E → E+T | T T → T*F | F F →(E) | id
项集 I={[E’ →.E]} 的闭包
- [E’ →.E]在闭包中
- [E →.E+T]，[E →.T]在闭包中
- [T →.T*F]，[T →.F]在闭包中
- [F →.(E)]，[F →.id]在闭包中

LR(0)项集中的内核项和非内核项

内核项：初始项S’ →.S、以及所有点不在最左边的项
非内核项：除了S’ →.S之外、点在最左边的项
由于表可能很庞大，实现算法时可以考虑只保存相应的非终结符号；甚至可以只保存内核项，而在要使用非内核项时调用CLOSURE函数重新计算

GOTO函数

I是一个项集，X是一个文法符号，GOTO(I,X)定义为I中所有形如的项[A → α·Xβ]所对应的项[A → αX·β]的集合的闭包
- 根据项的历史-期望的含义，GOTO(I,X)表示读取输入中的X或者归约到一个X之后的情况
- GOTO(I,X)定义了LR(0)自动机中状态I在X之上的转换
例如
- I={[E’ → E.], [E → E.+T]}
- GOTO(I,+)计算如下
  - I中只有一个项的点后面跟着+，对应的项为[E → E+.T] ◼
  - CLOSURE({[E → E+.T]}) = {[E → E+.T]，[T →.T*F], [T→.F]， [F →.(E)]，[F →.id]}

求LR(0)项集规范族的算法

为文法G构造LR(0)项集规范族C

LR(0)自动机的构造

构造方法
- 规范LR(0)项集族中的项集可以作为LR(0)自动机的状态
- GOTO(I,X)=J，则从I到J有一个标号为X的转换
- 初始状态为CLOSURE({S’ →.S})对应的项集
- 接受状态：包含形如A → α.的项集对应的状态

LR(0)自动机的作用

根据文法构造出LR(0)自动机，通过自动机的运行进行语法分析
假设文法符号串γ使LR(0)自动机从开始状态0运行到某个状态j，LR(0)自动机按照如下方式决定移入或归约
- 如果下一个输入符号为a，且状态j上有a的转换，就移入a
- 否则就归约，状态j中的项会告诉我们使用那个产生式进行归约
假设文法符号串γ使LR(0)自动机从开始状态运行到状态（项集）j
- 如果j中有一个形如A → α.的项，那么
  - 在γ之后添加一些终结符号可以得到一个最右句型
  - α是γ的后缀，且A → α是这个句型的句柄
  - 表示可能找到了当前最右句型的句柄
- 如果j中存在一个项B → α.Xβ，那么
  - 在γ之后添加Xβ，然后再添加一个终结符号串可得到一个最右句型
  - 在这个句型中B → αXβ是句柄
  - 此时表示还没有找到句柄，需要移入
LR(0)自动机的使用
- 移入-归约时，LR(0)自动机被用于识别句型
- 已经归约/移入得到的文法符号序列对应于LR(0)自动机的一条路径
- 如果路径到达接受状态，表明栈上端的某个符号串可能是句柄
不需要每次用归约/移入得到的串来运行LR(0)自动机
- 路径被放到栈中；且文法符号可以省略，因为由LR(0)状态可以确定相应文法符号
- 在移入后，根据原来的栈顶状态即可知道新的状态
- 在归约时，根据归约产生式的右部长度弹出相应状态，仍然可以根据此时的栈顶状态计算得到新状态