动机
文法说明哪些字存在以及它们有什么结构;语法分析器则必须从输入中恢复这种结构,自左向右读入,并在每一点决定下一步做什么。自底向上分析保存一个已读符号的栈,并反复在两类动作之间选择:移进把下一个输入符号移到栈上,归约把构成某条规则右部的符号替换为它的左部变元。困难在于判断何时可以归约。LR 分析用一个以规则的部分识别状态为状态集、以文法符号为字母表的有限自动机来回答这个问题。
本节对小型文法展开 LR(0) 机制,定义 LR(k),并用一个最小的例子说明前瞻为什么会改变可分析的范围。本节不为任意 LR(k) 文法构造分析表,也不涉及 LALR。
定义
定义 3.1.1
(增广文法与结束标记)
给定上下文无关文法 ,其增广文法加入新变元 与规则 ,并以 为新的起始变元。符号 是结束标记,置于每个输入字之后。由于 不出现在任何右部,规则 在每个推导中恰好使用一次,即第一步。
定义 3.1.2
(LR(0) 项目、闭包与 goto)
LR(0) 项目是在右部中标出一个位置的规则,对规则 写作 。对项目集 , 是满足如下条件的最小集合 :只要 且 是规则,就有 。对文法符号 ,
规范族是包含 、且对所有符号 的 封闭(舍去空结果)的最小项目集族 。
定义 3.1.3
(分析表与移进-归约分析器)
给规则编号,并以 为状态索引。ACTION 表对每个状态 设一行,对每个终结符及 设一列;GOTO 表对每个变元设一列。表项定义如下:
- 若 ,,且 ,则 含移进 ;
- 若 且 ,则对每个 , 含归约 ;
- 若 ,则 含接受;
- 对变元 ,。
含两个或更多动作的表项称为冲突:含一个移进和一个归约的是移进/归约冲突,含两个归约的是归约/归约冲突(含接受时类似)。若没有表项含有多于一个动作,则称该文法按表为 LR(0)。
分析器的格局由栈 (状态与符号交替)和剩余输入组成。设 为下一个输入符号(或 )。若 为移进 ,则压入 与 并前进。若为归约 ,则弹出 项,设此时栈顶状态为 ,压入 与 ,输入不前进。若为接受,则成功停止。空白表项表示错误。
概念视角结构
栈作为有限自动机中的一条路径
把规范族看作以文法符号为字母表的确定型自动机:状态是项目集,转移是 goto。分析器的栈记录了从 出发走过的路径,而按 归约就是把这条路径倒退 步,然后从所到达的状态取 转移。因此栈始终是有限图中的一条路径,分析器唯一的无限资源是这条路径的长度。
为使下文的可靠性证明独立完整,本节采用带检查的归约:按 归约之前,验证栈顶恰有足够的符号与状态对、最上面的 个文法符号正好拼成 ,且归约后的 GOTO 表项有定义;否则报告错误。通常的可行前缀定理可在完整 LR 实现中证明无需重复此检查,但本节的初等逆推导证明明确使用它。
定义 3.1.4
(LR(k) 文法)
设 是增广文法,。对终结符串 ,记 为 的前 个符号。若下述条件成立,则称该文法是 LR(k)。只要 且 ,其中 为终结符串, 且 ,就有 , 且 。这里 表示替换最右边变元的一步。
通俗地说:在看到栈内容 之后,接下来的 个输入符号决定归约哪条规则以及在哪里归约。 的情形在这一决定中不允许任何前瞻。
定理
定理 3.1.5
(闭包、goto 与规范族是良定义且有限的)
对有限文法的任一有限项目集 , 存在且有限,并满足 。规范族存在且有限,至多有 个成员,其中 为该文法的项目数。
证明
(闭包步骤的最小不动点)
令 ,令 为 加上所有由 中点号位于 之前的项目所要求的项目 。这一序列递增,且每个 都在文法的有限项目集之内,所以它稳定于某个集合 。这个 是封闭的且包含 。任何封闭的 对 归纳可知包含每个 ,所以 是这类集合中最小的。由于 本身已经封闭且包含自身, 的最小封闭超集就是 ,这证明了幂等性。于是每个 是有限项目集。规范族通过反复添加尚未出现的 goto 得到;每个成员都是有限项目集的子集,所以至多有 种可能,过程必然终止。
定理 3.1.6
(分析器所做的归约构成一个最右推导)
设 是增广文法,假设移进-归约分析器在用上述规则构造的任一分析表下接受 。则 ,且所做的归约按相反次序恰是某个最右推导的各步。特别地,。
证明
(把归约倒过来读)
固定对 的一次接受运行。在每个时刻 ,令 为栈上的符号, 为剩余输入(终结符串),并令 。起初栈上没有符号,所以 。移进把一个终结符从输入移到栈顶,不改变 。按 归约把 变成 ;由于 是终结符串, 是 的最右变元,所以 是最右的一步。把这些步骤连起来,得到从最终的 到 的最右推导。余下要证最终的 就是 。接受发生在含 的状态。因为 不出现在任何右部,含 的集合只有 ,产生项目 的转移只有 。此外, 永远不是某个 goto 的目标,因为每个 goto 目标都含有点号位于至少一个符号之后的项目,而 的每个项目点号都在开头。所以状态 只出现在栈底,接受时的栈恰是 ,且剩余输入为空。因此最终的 就是 。
证明透视
为什么可靠性证明不需要完整的自动机理论
所用的假设只是:归约恰好弹出它所指明的规则的右部,而被移进的只有终结符。表项是否正确(点号项目是否真的刻画了可行前缀)并未被使用,所以该定理是一个安全性陈述:分析器接受的一切都是可推导的。它没有说语言中的每个字都被接受,也没有说分析器是确定的。完备性需要有效项目的理论,本节不予展开;确定性则需要没有冲突。
证明思路
定理 3.1.7
( 的分析器)
增广后为 ,规则编号为 ,。规范族恰有五个状态:,,,,,且 ,,,,,。该表没有冲突,且分析器接受 当且仅当 。
证明
(小文法的项目、goto 与运行轨迹)
所列的项目集与 goto 直接来自定义: 的闭包加入 的两条规则;让点号越过 、、 分别得到 、内核为 的集合(其闭包加入 与 )以及 ;从 出发,符号 得到 ,而 与 分别回到 与 。再无其他 goto,所以该族封闭。状态 各含一个完整项目且没有点号后为终结符的项目,所以它们的行各只有一个动作; 与 不含完整项目,所以只有移进。因此没有冲突。关于接受性,我们跟踪运行。字 的处理为:从 或 作 次移进到 ,移进 到 ,按 归约,落在 (从 来)或 (若 ,从 来);然后,若 ,作 次按 的归约,每次弹出两对并在下方状态之上压入 ,最终在 之上到达 ,并在 上接受。反之,不属于 的输入要么在 或 中耗尽输入而 无表项,要么在 之后还读到符号,要么带着终结符到达 ,每种情形都遇到空白表项。 中的归约对所有前瞻符号都执行,所以这样的错误可能比出错的输入符号晚一次归约才被发现;这是 LR(0) 的特点。
定理 3.1.8
(前瞻区分 LR(0) 与 LR(1))
文法 不是 LR(0) 的,而是 LR(1) 的。其 LR(0) 自动机的表在读入 后到达的状态中有移进/归约冲突。
证明
(读入 a 之后的冲突与 LR(1) 检验)
对 ,增广文法有 ,且 。第一个项目对所有终结符(包括 )给出归约,第二个项目对 给出移进,所以 列的表项含两个动作。取 ,其中 ,,,;再取 ,其中 ,,。则 ,。对 ,前瞻条件是空的,但 ,所以该文法不是 LR(0)。对 ,,所以这一对不受约束。为验证 LR(1) 条件,列出所有归约情形。共有三种,都有 :步骤 ,此时 ;步骤 ,此时 ;步骤 ,此时 。一对情形要满足 ,只有当第二个串 以第一个情形的 为前缀才可能。串 既不是 或 的前缀,也不以它们为前缀,而 不是 的前缀。相同的情形平凡地满足结论。唯一余下的一对就是上面处理过的那一对,其前瞻假设不成立。所以 LR(1) 条件成立。
反例模式
无歧义不等于 LR(0)
断言(错误):每个字恰有一棵分析树的文法可以不用前瞻来分析。文法 是无歧义的,因为两个字的树形状不同,且每个字只有一棵树。但它的 LR(0) 自动机有一个状态,同时含完整项目 与项目 ,所以读入 之后分析器无法在归约与移进 之间决定。有一个符号的前瞻就能强制决定:在 上归约,在 上移进。修正:允许前瞻,如 LR(1) 的定义。LR(k) 文法都是无歧义的,这是一个标准事实,此处不予证明;这个例子表明对 仅有无歧义是不够的。
例题
例题 3.1.9
( 的完整分析表)
规则:,。空白表项表示错误。
| 状态 | ||||
|---|---|---|---|---|
| 0 | 移进 2 | 移进 3 | 1 | |
| 1 | 接受 | |||
| 2 | 移进 2 | 移进 3 | 4 | |
| 3 | 归约 2 | 归约 2 | 归约 2 | |
| 4 | 归约 1 | 归约 1 | 归约 1 |
归约状态的各行体现了 LR(0) 的特征:完整项目在每一列上都归约。没有一行含两个动作,所以该文法按表为 LR(0)。
例题 3.1.10
(分析 aab)
初始栈为 ,输入为 。移进 :栈 ,输入 。移进 :,输入 。移进 :,输入 。按规则 ()归约:弹出一对,栈顶状态为 ,压入 与 :。按规则 ()归约:弹出两对,栈顶状态为 ,压入 :。再按规则 归约:弹出两对,栈顶为 ,压入 与 :。在 上,状态 的表项是接受。归约按相反次序给出 ,正是一个最右推导,与可靠性定理的预言一致。对只含 的串,分析更短:移进 到状态 ,按规则 归约并取 ,然后接受。
例题 3.1.11
(前瞻能解决的冲突,与不能解决的冲突)
对 ,读入 之后的状态是 ,LR(0) 表中 列的表项是移进/归约冲突。若有前瞻集, 只在下一个符号可以跟在 之后时才可归约,这里只有 ,于是冲突消失。再看 。在 之后,状态含 与 。可以跟在 之后的符号是 与 ,所以在 上归约是允许的,移进 也是允许的。即使有一个符号的前瞻,冲突依然存在,因为该文法有歧义,两个动作对应两棵不同的分析树。
常见错误
另有一点属于记账层面。不要混淆符号栈与状态栈:符号拼出可行前缀,而状态记录自动机的位置;归约按右部符号的个数弹出。
常见错误
(零前瞻不等于不看输入)
不要把“LR(0)”理解为“分析器从不查看输入”。移进依赖于下一个终结符;零前瞻指的是归约的决定,它必须仅由状态决定。
常见错误
(计算 goto 时漏掉闭包)
计算 时漏掉闭包这一步,会丢掉紧跟在点号之后的变元所对应的项目。对 ,移动后的集合 在 与 上都不给出移进。
常见错误
(更长的前瞻不能消除歧义)
不要相信增加前瞻就能让每个文法都可分析:歧义与前瞻的长度无关。上面的 就是例子:它的冲突对每个 都存在。
总结
LR 分析运行一个由项目集自动机引导的基于栈的移进-归约循环。闭包与 goto 是良定义的,规范族有限。这样的分析器接受的一切都是可推导的,所做的归约按相反次序构成最右推导。对 ,表有五个状态且无冲突;字 被明确地分析了一遍。文法 表明,一个符号的前瞻可以解决零前瞻无法解决的冲突。
练习
快速检查
(构造增广文法 的规范族与分析表。)
先闭包,再 goto。
解答 · 答案
规则编号为 ,。状态:;;;;;;此外 ,。表:第 0 行: 上移进 2, 上移进 3,GOTO 为 1;第 1 行: 上接受;第 2 行: 上移进 2, 上移进 3,GOTO 为 4;第 3 行:在 上归约 2;第 4 行: 上移进 5;第 5 行:在 上归约 1。没有冲突。
快速检查
(对该文法,给出分析 时每一步的栈与输入。)
同时记录状态与符号。
解答 · 答案
栈与剩余输入: 配 ;移进: 配 ;移进: 配 ;移进 : 配 ;归约 2:;移进 : 配 ;归约 1 弹出三对,剩下 ,压入 与 GOTO:;移进 : 配 ;归约 1 弹出三对,剩下 ,压入 :;接受。
快速检查
(证明 ,, 的 LR(0) 表中有归约/归约冲突,并把它与文法联系起来。)
检查读入 、再读入 之后的状态。
解答 · 答案
读入 之后的状态是 ,且 ,它在每一列上都有两个归约:这是归约/归约冲突。它反映了歧义: 有两棵分析树,一棵经过 ,一棵经过 。
快速检查
(证明对有限项目集 有 ,并举例说明 不一定等于上面所定义的 。)
用闭包的最小性。
解答 · 答案
集合 包含 且封闭,因为若某个点号位于 之前的项目属于其中一部分,则所要求的项目 属于同一部分。由最小性,。反之, 是 的封闭超集,故包含 ,同理包含 ;所以 。举例:在文法 中取 ,按定义 ,因为 中没有点号位于 之前的项目,而 。这就是定义要把 goto 作用于封闭项目集(例如规范族的成员)的原因。