Stanford Compiler Week 4 Bottom-Up Parsing II
课程主页：
https://www.edx.org/course/compilers
课程视频：
https://www.bilibili.com/video/BV1NE411376V?p=20&t=6
这次回顾自顶向下解析II。
备注：
1.这部分比较难，感觉还需要多理解几遍。
2.由于hexo渲染的问题，下文中*符号经常会表示为$\star$
Handles
引子
自底向上解析使用两种行动：
Shift:
Reduce:
左字符串可以由栈实现
- 栈顶是$|$
Shift将终止符push入栈
Reduce
- 从栈中弹出0个或多个符号
- 生产Rhs
- 将非终止符push到栈上
- 生产lhs
- 从栈中弹出0个或多个符号
现在的问题是我们如何决定何时shift或reduce？
语法示例：
考虑步骤$\text { int } \mid * \text { int }+\text { int }$
- 我们可以通过$\mathrm{T} \rightarrow \text { int }$，reduce得到$\mathrm T \mid * \text { int }+\text { int }$
- 一个致命的错误！
- 无法reduce到起始符号$\mathrm E$
直觉：只有当结果可以reduce到起始符号时，我们才希望reduce
Handle定义
假设有最右派生
那么$\alpha\beta$是$\alpha\beta\omega$的handle
注意reduce的步骤为
handle使直觉正规化
- handle是允许进一步reduction到起始符号的reduction
即我们只想在handle处reduce
注意：我们只说过什么是handle，但没有说过如何找到handle
重要事实
关于自底向上解析的重要事实2：
- 在shift-reduce解析中，handle只出现在堆栈的顶部，从不出现在堆栈内部
利用归纳法简单证明：
堆栈为空该结论显然成立
在reduce一个handle后
- 最右边的非终止符在栈顶（reduce定义）
- 下一个handle必须在最右非终止符右边，因为这是一个最右派生
- 如果在左侧则与最右派生矛盾
- 进行一系列shift到达下一个handle
堆栈示例：
结合上一讲的例子理解：
总结
- 在shift-reduce解析中，handle总是出现在栈的顶部
- handle从在最右侧非终止符的左侧
- 因此，shift-reduce的移动就足够了；因为$|$从不向左移动
- 自底向上的解析算法基于识别handle
习题
解析步骤：
- $\mathrm{E}^{\prime}+-\mathrm{id} \mid+-(\mathrm{id}+\mathrm{id})$
- $\mathrm{E}^{\prime}+-\mathrm{E’} \mid+-(\mathrm{id}+\mathrm{id})$
- $\mathrm{E}^{\prime}+\mathrm{E’} \mid+-(\mathrm{id}+\mathrm{id})$
- $\mathrm{E}^{\prime}+\mathrm{E} \mid+-(\mathrm{id}+\mathrm{id})$
- $\mathrm{E}\mid+-(\mathrm{id}+\mathrm{id})$
- $\mathrm{E}+\mid-(\mathrm{id}+\mathrm{id})$
- $\mathrm{E}+-\mid(\mathrm{id}+\mathrm{id})$
- $\ldots$
注意到
所以选第一项。
识别Handles
引子
- 坏消息
- 目前尚无已知的高效算法来识别handles
- 好消息
- 有很好的启发式方法来猜测handle
- 在某些CFG上，启发式算法总是猜对的
如何检测handles不明显
在每个步骤中，解析器只能看到栈，而不是整个输入
$\alpha$是可行的前缀，如果存在$w$使得$a|w$是shift-reduce解析器的状态
- $\alpha$是栈
- $w$是剩余输入
这意味着什么？几点：
- 一个可行的前缀不能延伸到handle的右端
- 这是一个可行的前缀，因为它是handle的前缀
- 只要解析器在栈上具有可行的前缀，就不会检测到解析错误
重要事实
- 关于自底向上解析的重要事实3：
- 对于任何语法，一组可行的前缀都是正则语言
- 事实3是非平凡的
- 我们将演示如何计算接受可行前缀的自动机
在讨论之前引入item的概念：
item
- item是在rhs的某处有”.”的production
- $\mathrm T\to (\mathrm E)$的item是
- $\mathrm{T} \rightarrow .(\mathrm{E})$
- $\mathrm{T} \rightarrow(. \mathrm{E})$
- $\mathrm{T} \rightarrow(\mathrm{E}.)$
- $\mathrm{T} \rightarrow(\mathrm{E}) .$
- $\mathrm X\to\varepsilon$的唯一item是$\mathrm X\to.$
- item被称为”LR(0) items”
继续讨论
识别可行前缀的问题是，堆栈仅包含production中rhs的零碎部分
- 即如果它有一个完整的rhs，我们可以reduce
这些零碎部分始终是rhs production的前缀
考虑输入$(\text{int})$，规则如下：
那么$(\mathrm E|)$是一个shift-reduce解析的状态
$(\mathrm E$是$\mathrm T\to(\mathrm E)$的rhs的前缀
- shift后将reduct
Item $\mathrm T\to(\mathrm E.)$表示，到目前为止，我们已经看到这一production的$(\mathrm E$部分，并将看到$)$
栈可能有许多rhs的前缀
$\mathrm{Prefix}_i$为$\mathrm X_{i} \rightarrow \alpha_{i}$的rhs的前缀
- 即前缀最终会reduce到$\mathrm X_i$
- $\alpha_{i-1}$的缺失部分以“$\mathrm X_i$”开头
- 即，对于某个$\beta$，$\mathrm X_{i-1} \rightarrow \operatorname{Prefix}_{i-1} \mathrm X_{i} \beta$
递归地，前缀$\text { Prefix}_{k+1} \ldots \text { Prefix}_{n}$最终reduce到$\alpha_k$的缺失部分。
例子
- 考虑字符串$(\text {int } \star \text { int})$：
- $(\text {int } \star \mid \text { int})$是shift-reduce解析的状态
- $”(“$是$\mathrm T \rightarrow(\mathrm E)$ rhs的前缀
- $\varepsilon$是$\mathrm E\to \mathrm T$ rhs的前缀
- $\mathrm {int}^{\star}$是$\mathrm{T} \rightarrow \operatorname{int}^{\star} \mathrm{T}$ rhs的前缀
items和上式例子的关系：
“stack of items”
是说
- 我们已经看到了$\mathrm T\to(\mathrm E)$的$”(“$
- 我们已经看到了$\mathrm E\to \mathrm T$的$”\varepsilon”$
- 我们已经看到了$\mathrm{T} \rightarrow \operatorname{int}^{\star} \mathrm{T}$的$\mathrm {int}^\star$
总结
- 想法：为了识别可行的前缀，我们必须
- 识别production的部分rhs序列，其中每个部分的rhs最终可以reduce到它的前一个后缀缺失的一部分
识别可行前缀
方法
在$\mathrm G$中添加一个虚拟production $\mathrm S’\to \mathrm S$
NFA状态为$G$中item
- 包括额外production
对于item $\mathrm E \rightarrow \alpha . \mathrm X \beta$，添加转移
对于item $\mathrm E \rightarrow \alpha . \mathrm X \beta$和production $\mathrm X \to \gamma $添加
每个状态是接受状态
起始状态为$\mathrm S’\to \mathrm S$
例子
依旧考虑规则
添加规则
得到
状态转移图如下：
初始的，根据规则3,4可得
习题
选第二项。
有效item
之前的状态机是NFA，可以将其转换为DFA：
DFA
- DFA的状态是
- item的规范集合
- LR(0)项的规范集合
- 龙书提供了构造LR(0)项的另一种方法
总结
item $\mathrm X\to \beta. \gamma$对于前缀$\alpha\beta$是有效的，如果根据最右派生
在解析$\alpha\beta$之后，有效item是item栈可能的顶部
如果DFA识别可行的前缀终止于输入$\alpha$，且状态$s$包含$|$，则item$|$对可行前缀$\alpha$有效
$s$中的item描述读取输入$\alpha$后项栈的顶部可能是什么
item通常对许多前缀有效
例子：item $\mathrm T \rightarrow(. \mathrm E)$对如下前缀有效
习题
这部分没有完全理解，感觉应该选择前三项。
SLR解析
回顾
- $\mathrm {LR}(0)$解析：假设
- 栈有$\alpha$
- 下一个输入为$\mathrm t$
- 为输入$\mathrm a$的DFA终止于状态$\mathrm s$
- 通过$\mathrm X\to\beta$ reduce，如果
- $\mathrm s$包含item $\mathrm X\to\beta.$
- shift，如果满足如下条件，
- $\mathrm s$包含item $\mathrm X \rightarrow \beta . \mathrm t\ \omega$
- 等价于说$\mathrm s$具有标记为$\mathrm t$的转移
- $\mathrm {LR}(0)$有reduce/reduce冲突，如果
- 某个状态有两reduce items：
- $\mathrm X\to\beta.,\mathrm Y\to \omega.$
- $\mathrm {LR}(0)$有shift/reduce冲突，如果
- 某个状态有reduce item和shift item：
- $\mathrm X\to\beta.,\mathrm Y \rightarrow \omega . \mathrm t\ \delta$
例子
SLR
- SLR=”Simple LR”
- SLR改进了$\mathrm {LR}(0)$ shift/reduce
- 更少的状态有冲突
正式定义
- 想法：假设
- 栈有$\alpha$
- 下一个输入为$\mathrm t$
- 输入为$\mathrm a$的DFA终止于状态$\mathrm s$
- 通过$\mathrm X\to\beta$ reduce，如果
- $\mathrm s$包含item $\mathrm X\to \beta.$
- $\mathrm{t} \in \text { Follow}(\mathrm{X})$
- Shift，如果
- $\mathrm s$包含item $\mathrm X\to\beta.\mathrm t\ \omega$
- 如果在这些规则下存在冲突，则语法不是SLR
- 规则相当于启发式检测handle
- SLR语法是那些启发式方法能够准确检测出handle的语法
小结
很多语法不是SLR
- 包括所有有歧义的语法
我们可以通过使用优先级声明来解析更多语法
- 解决冲突的说明
依然考虑有歧义的语法
该语法的DFA包含具有以下各项的状态：
- $\mathrm E \rightarrow \mathrm E^{*}\mathrm E, \mathrm E \rightarrow \mathrm E .+\mathrm E$
- shift/reduce冲突
声明“*的优先级高于+”可解决此冲突，更偏向于reduce
“优先声明”一词具有误导性
这些声明未定义优先级，实际上是定义了冲突解决方案
算法
- 令$\mathrm M$为$\mathrm G$的可行前缀DFA
- 令$\mid x_{1} \ldots x_{n}$$为初始配置
- 重复执行，直到配置为$\mathrm S | $$
- 令$\alpha \mid \omega$为当前配置
- 在当前栈$\alpha$上运行$\mathrm M$
- 如果$\mathrm M$拒绝$\alpha$，则报告解析错误
- 栈a不是可行的前缀
- 如果$\mathrm M$接受根据item $\mathrm |$接收$\alpha$，则令$\mathrm a$为下一个输入
- 如果$\mathrm X \rightarrow \beta . \text { a } \gamma \in |$，则shift
- 如果$\mathrm X \rightarrow \beta . \in |$，$a \in \text { Follow }(\mathrm X)$，则reduce
- 如果都不适用，则报告解析错误
补充：
- 如果最后一步有冲突，则语法不是SLR(k)
- k是超前量
- 实际上k = 1
SLR解析例子
习题
选择第二项。
SLR提升
每个步骤中在堆栈上重新运行可行的前缀自动机是浪费的
- 重复大部分工作
记住堆栈每个前缀上自动机的状态
更改栈以包含pair
对于stack
DFA在的$\mathrm{sym}_1\ldots \mathrm {sym_n}$上的最终状态为$\text{state}_{\text n}$
细节：栈底是$\langle\text{any,start}\rangle$，其中
- any是任何虚拟符号
- start是DFA的启动状态
定义$\operatorname{goto}[i, A]=j$，如果$\text { state}_{\mathrm{i}} \rightarrow^{\mathrm{A}} \text {state}_{\mathrm{j}}$
goto只是DFA的转移函数
- 两个解析表之一
算法改进
- shift $\mathrm x$
- push $\langle a,\mathrm x\rangle$入栈
- $a$是当前输出
- $\mathrm x$是DFA状态
- reduce $\mathrm X \to \alpha$
- 和之前一样
- 接收
- 错误
具体来说
对每个状态$\mathrm s_i$和终止符号$a$
- 如果$\mathrm s_i$有item $\mathrm X\to \alpha.\mathrm a\beta$以及$\operatorname{goto}[i, A]=j$，那么$\text { action[i, a}]=\text { shift } \mathrm{j}$
- 如果$\mathrm s_i$有item $\mathrm X\to \alpha.$并且$\text { a}\in \text{Follow(X)},\mathrm X\neq \mathrm S’$，那么$\text { action[i, a}]=\text { reduce } \mathrm X \rightarrow \alpha$
- 如果$\mathrm s_i$有item $\mathrm S’\to \mathrm S$。那么$\text { action[i, } $]=\text {accept }$
- 否则，$\text { action[i,a] = error }$
算法
- 请注意，该算法仅使用DFA状态和输入
- 不使用栈符号！
- 但是，我们仍然需要符号来进行语义动作
总结
- 一些常见的构造不是SLR(1)
- LR(1)更强大
- 将item提前建立
- LR(1)项是pair：$\mathrm{LR}(0) \text { item } \times\text { lookahead }$
- $[\mathrm T \rightarrow . \operatorname{int} * \mathrm T, $]$表示
- 看到$\mathrm T \rightarrow . \operatorname{int} $后，如果lookahead为$$$，则reduce
- 比仅使用follow sets更准确
- 看看解析器的LR(1)自动机！
SLR例子