形式陈述
LR(0) 分析把“已经读过的符号可能对应哪几条产生式的哪一段”编码成有限状态,再由这个状态驱动移进和归约。它从左向右读取输入,反向构造最右推导;括号里的 0 表示归约决定不使用向前看 token 来区分上下文。
先清理文法理路上下文无关文法Context-free grammar · CFG每条产生式左侧是单个非终结符的生成系统。:删除不能生成终结词的非终结符及涉及它们的规则,再删除从开始符号不可达的部分。若开始符号本身不能生成终结词,语言为空,直接使用始终拒绝的解析器。以下可行前缀定理、构表及文法类别判断均针对这份清理后的文法;保语言的清理不承诺保留原表中的无用冲突。
加新开始规则 。LR(0) 项目在一条产生式右部放一个点,例如
点左边是已经识别的右部,右边是尚待识别的部分。 是完整项目,提示可能把栈顶 归约成 。它并不单独证明当前输入的剩余部分合法。
给项目集 定义闭包:只要含 ,就加入 的每条规则 ,重复到稳定。定义
从 开始,枚举所有非空 goto,得到以终结符和非终结符共同作为边标签的项目自动机。若按完整 DFA理路确定性有限自动机Deterministic finite automaton · DFA以有限状态和总转移函数为每个输入字规定唯一运行的识别模型。的约定识别可行前缀,须把这些非空项目集设为接受态,并把所有缺边接到一个拒绝的空项目死状态;死状态在每个文法符号上自环。解析表通常省略这个死状态,把缺边直接解释为错误。这台 DFA 读取的是分析栈上的文法符号,不是直接用有限记忆识别整个上下文无关输入;处理嵌套所需的记忆仍由栈提供。
同一个驱动器,两个表
若终结符边 存在,令 ACTION[] 包含“移进 ”;非终结符边则填入 GOTO[]=。若 含完整项目 ,其中 ,就在该行每个输入 token 及 下加入“按此规则归约”。 只在 下接受。
同一 ACTION 格不能有两个不同动作。移进与归约同时出现称移进/归约冲突,两条不同归约称归约/归约冲突。无冲突时,这张表定义 LR(0) 解析器。
状态栈理路栈Stack · LIFO stack以栈顶为唯一更新端、按后进先出规则组织元素的抽象数据类型;接口语义与具体表示的成本分别规定。初始为 。移进 时消费输入并压入目标状态。归约 时弹出 个状态,查看露出的状态 ,再压入 GOTO[]。归约不消费输入;空规则弹零个状态。若同时存符号或语义值栈,它们也要按同一右部长度弹出,并把对应的子树理路语法树Parse tree · Derivation tree用有序树记录产生式层次,以完整例子区分推导顺序、文法歧义、优先级及抽象语法树。接到新节点 下。
直觉
状态栈保存了沿“当前文法符号栈”运行 DFA 所经过的状态。移进是在这条路径末端续上一条边。归约则先撤去一段表示右部的路径,再从它之前的状态沿左部非终结符边前进。正因保留了整条状态历史,归约后不用从 重新扫描整栈。
文法符号栈是某个最右句型中不越过最右句柄的前缀,称为可行前缀。闭包中的预测项目表达:若下一段打算识别 ,那么 的任何产生式都可开始;goto 则同时推进所有可能项目。有限项目集合足以总结前缀的解析可能性,栈深度可以继续增长。
例子与边界
七个状态完整解析 cdd
给产生式编号:,,。加 后,可达项目集如下:
| 状态 |
项目 |
|
;;; |
|
;; |
|
|
|
;; |
|
|
|
|
|
|
全部表格为:
| 状态 |
c |
d |
|
S |
C |
| 0 |
s3 |
s4 |
— |
2 |
1 |
| 1 |
s3 |
s4 |
— |
— |
5 |
| 2 |
— |
— |
acc |
— |
— |
| 3 |
s3 |
s4 |
— |
— |
6 |
| 4 |
r3 |
r3 |
r3 |
— |
— |
| 5 |
r1 |
r1 |
r1 |
— |
— |
| 6 |
r2 |
r2 |
r2 |
— |
— |
s3 表示消费一个 token 后压状态 3,r3 表示按产生式 3 归约。输入 cdd 的每一步为:
| 状态栈 |
符号栈 |
剩余输入 |
动作 |
| 0 |
空 |
cdd |
s3 |
| 0,3 |
c |
dd |
s4 |
| 0,3,4 |
cd |
d |
|
| 0,3,6 |
cC |
d |
|
| 0,1 |
C |
d |
s4 |
| 0,1,4 |
Cd |
|
|
| 0,1,5 |
CC |
|
|
| 0,2 |
S |
|
acc |
第二次归约弹掉的是状态 3 和 6,露出 0,再查 GOTO[0,C]=1。若误用归约前的栈顶 6 查询 GOTO,就会查不到正确后继。
输入 cd 则只形成第一个 。栈到 时输入已经结束,ACTION[1,] 为空,因此拒绝。最后读到 或曾经归约成 都不等于整句完成。
为什么先清理无用规则
若直接对 、、 做闭包,初态含 ,因此沿 的 goto 非空。但最右推导只能从 到 ,随后一直改写最右的 ;根本没有以 开头的最右句型。这时把所有非空项目集都设为接受态,就不能声称恰好识别可行前缀。机械闭包仍可计算,缺的是这个精确语言解释的前提:从 预测 时,右侧后缀 必须能够先在最右推导中化成终结串,才能给 留出真实的最右展开位置。
完整项目也可能过早
改用 。读入一个 后,状态中同时有 与 ,闭包还预测能继续读 。下一 token 为 时,移进和立即归约都被 LR(0) 规则放进同一格。
这个冲突没有证明语言有歧义;语言只是非空的 串。它说明“一个右部已经完整”还不足以决定此时该不该结束它。SLR理路SLR 分析表SLR parsing · Simple LR parsing保留LR(0)状态,只在左部FOLLOW集合上允许归约的确定解析方法。加入 FOLLOW,LR(1)理路规范 LR(1) 分析Canonical LR(1) parsing在项目中保存局部右上下文,以一个向前看token区分归约的LR构表方法。把更精确的右上下文直接附在项目上。
推论与应用
LR 驱动器的栈不变量解释了为何无需回溯:若表无冲突,选定动作对应唯一可行的句柄处理;每次归约都是反向走一条最右推导。接受时归约得到开始符号且输入恰好结束,因此生成的树确实属于文法。完整性还依赖 LR(0) 无冲突条件,不能对任意 CFG 的任意冲突消解作相同承诺。
令项目总数为 ,项目集最多有 种,因此构表最坏可指数膨胀。令实际状态数为 ,稠密 ACTION/GOTO 表占 。固定有用的无冲突文法后,移进/归约次数随解析树大小增长,通常按输入长度记为 时间、 栈空间;构表成本与运行成本应分开报告。
状态编号没有数学意义。本页编号由按符号排序的可达搜索确定;检查另一份表时应比较项目集和转移,而不是要求“状态3”在所有资料中都代表同一集合。
参考资料
-
Stanford CS143, Lecture 8: Bottom-Up Parsing,可行前缀、项目自动机、LR(0) 与 SLR 部分,尤其 slides 54–81
-
Cornell CS4120, LR(1) and LALR Parsing,LR(0) 状态与向前看扩展的衔接
-
Aho, Lam, Sethi, Ullman, Compilers, 2nd ed., 2007,§4.6
-
San Skulrattanakulchai, SLR parser generation, 2019,Items 与 LR(0) automaton 部分:明确先假定无无用非终结符,再由项目 NFA 的闭包与子集构造得到 DFA