Stanford Compiler Week 3 Parsing and Top-Down Parsing

课程主页：

https://www.edx.org/course/compilers

课程视频：

https://www.bilibili.com/video/BV1NE411376V?p=20&t=6

这次回顾第三周的内容，这一周主要解析以及自顶向下的解析。

解析介绍

引子

正则语言
- 被广泛使用的最弱的形式语言
- 很多应用

考虑语言：

$\left\{(^{i})^{i} \mid i \geq 0\right\}$

该语言表示成对左右括号：

$(),(()),((())),\ldots$

正则语言无法表达上述语言，因为正则语言只能统计$\text{cout mod } k$的值。

解析的输入输出

输入：来自词法器的符号序列
输出：程序的解析树

例子

COOL语言代码
```
if x = y then 1 else 2 fi
```
解析器输入
```
IF ID = ID THEN INT ELSE INT FI
```
解析器输出

解析器和词法器的比较

阶段	输入	输出
词法器	字符构成的字符串	符号构成的字符串
解析器	符号构成的字符串	解析树

上下文无关语法

并非所有的符号字符串都是程序
解析器必须区分有效和无效的符号字符串
我们需要
- 描述有效符号字符串的语言
- 区分有效和无效的符号串的方法

程序设计语言具有递归结构

if EXPR then EXPR else EXPR fi
while EXPR loop EXPR pool
…

上下文无关语法(Context-free grammars,CFG)是这种递归结构的自然表示法

CFG

CFG包括：
- 终止符号集合：$T$
- 非终止符号集合：$N$
- 起始符号集合：$S,S\subset N$
- Productions规则集合：$X\to Y_1\ldots Y_N,X\in N, Y_i \in N\cup T\cup \{\epsilon\}$
  - Productions可以被视为规则： $S\to (S)$

CFG流程

从只包含起始符号$S$的字符串开始
将字符串中任何非终止符$X$替换为某些production $X\to Y_1\ldots Y_n$
重复(2)，直到没有非终止符

例子

例1

回到语言

$\left\{(^{i})^{i} \mid i \geq 0\right\}$

productions：

$\begin{aligned} s &\rightarrow(s)\\ s &\rightarrow \epsilon \end{aligned}$

$N,T$：

$N=\{s\},T=\{(,)\}$

例2

简单算数表达式：

production：

$\begin{aligned} E \rightarrow & E+E\\ |& E * E \\ | & (E) \\ |& \text{id} \end{aligned}$

CFG的语言

设$G$为上下文无关语法，起始符号为$S$，则$G$的语言$L(G)$为：

$\left\{a_{1} \ldots a_{n} \mid \forall {i}, a_{i} \in T \land s \overset \star\rightarrow a_{1} \ldots a_{n}\right\}$

终止符之所以被称为终止符，是因为没有替代规则
终止符一旦产生，就成为永久终止符
终止符应该是语言的符号

注意，这里$\overset \star\rightarrow$是指如下含义：

$a_0\overset \star\rightarrow a_n \triangleq a_0 \to a_1\to \ldots \to a_n$

习题

选择2,3项。

总结

CFG的想法是一个很大的步骤。但是：

语言中的成员身份是“是”或“否”；也需要输入的解析树
必须优雅地处理错误
需要实现CFG
语法的形式很重要
- 很多语法都产生同一种语言
- 工具对语法敏感

Derivations

定义

derivation是production序列：

$\mathrm{S} \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots \rightarrow \ldots$

derivation可以画成一棵树。

开始符号是树的根
对于production$X\to Y_1\ldots Y_n$，将子节点$Y_1\ldots Y_n$添加到节点$X$

例子

语法
$\text{E} \rightarrow \text{E} +\text{E} |\text{E} * \text{E} |(\text{E} ) \mid \text{id}$
字符串
$\text { id } * \text { id }+\text { id }$
derivation如下：

该示例是一个最左边派生
- 在每一步中，更换最左的非终止符
有一个等同的概念，最右派生

最右派生例子：

请注意，这里的最右派生和最左派生具有相同的解析树。

解析树

解析树
- 叶节点是终止符
- 内部节点是非终止符
叶子的中序遍历是原始输入
解析树显示操作的关联，输入字符串不显示这点

习题

选择最后一项。

总结

我们不只是对$s\in L(G)$感兴趣
- 我们需要一个$s$的解析树
派生定义了一个解析树
- 但是一个解析树可能有很多派生
最左派生和最右派生在解析器实现中很重要

歧义

引子

依然考虑如下例子

语法 $\text{E} \rightarrow \text{E} +\text{E} |\text{E} * \text{E} |(\text{E} ) \mid \text{id}$
字符串 $\text { id } * \text { id }+\text { id }$ 该字符有两个解析树：

因此产生了歧义性。

如果语法具有多个字符串的解析树，则语法是有歧义的
- 等价于，对于某个字符串，存在多个最右或最左派生
歧义是不好的
- 部分程序的含义是定义不明确的

处理方法

有几种方法可以处理歧义
最直接的方法是将语法重写为无歧义的
$\begin{array}{l} \text{E} \rightarrow \text{E} ^{\prime} + \text{E} \mid \text{E} ^{\prime} \\ \text{E} ^{\prime} \rightarrow\text{id} * \text{E} ^{\prime} \mid \text{id}\mid(\text{E} ) * \text{E} ^{\prime} \mid(\text{E} ) \end{array}$
强制*优先于+

语法重写后的结果如下：

例子

考虑语法
$\begin{aligned} \text{E}\to &\text{if E then E}\\ | &\text{if E then E else E}\\ |&\text{OTHER} \end{aligned}$
表达式
$\text { if } \text{E}_{1} \text { then } \text{if } \mathrm{E}_{2} \text { then } \mathrm{E}_{3} \text { else } \mathrm{E}_{4}$
有两个解析树：
如果else匹配最近的没有匹配的else
那么此时解析树为

处理方法

无法自动将有歧义的语法转换为没有歧义的语法
小心使用，歧义可以简化语法
- 有时允许歧义会产生更自然的定义
- 我们需要消除歧义的机制
不是重写语法
- 而是使用更自然的（有歧义的）语法
- 其实包括消除歧义的声明
大多数工具允许优先和关联性声明来消除语法歧义

例子

考虑语法： $\text{E} \rightarrow \text{E}+\text{E } \mid \text { int }$
歧义：int+int+int有两棵解析树
左关联声明：%left +
- 在这种情形下，只会取第一种解析树
考虑语法：
- 字符串int+int*int
两颗树分别对应优先级声明：%left和%left *

习题

应该选前两项。

第一项：$\text{aba}$

第二项：$\text{id+id+id}$

选第一项。

错误处理

编译器的作用是
- 检测无效程序
- 翻译合法程序
各种可能的错误（例如，在C中有如下例子：）
错误处理程序应
- 准确、清晰地报告错误
- 快速从错误中恢复
- 不降低有效代码的编译速度

紧急(panic)模式

紧急模式是最简单、最流行的方法
当检测到错误时：
- 丢弃符号，直到找到具有明确角色的符号
- 从那里继续
查找同步符号
- 通常为语句或表达式结束符
考虑一下这个错误的表达式
$(1++2)+3$
紧急模式恢复：
- 跳到下一个整数，然后继续。
Bison：使用特殊的终止错误来描述要跳过多少输入
$\text{E} \to \text{int | E + E | ( E ) | error int | ( error )}$

错误productions

错误productions
- 指定语法中已知的常见错误
例子：
- 写$5\text{x}$而不是$5\text{*x}$
- 添加production $\text{E} \rightarrow \ldots \mid \text{E}\text{E}$
缺点
- 使语法复杂化

错误处理

想法：找到一个正确的“附近”程序
- 尝试符号插入和删除
- 彻底搜索
缺点：
- 难以实现
- 减慢正确程序的解析速度
- “附近”不一定是“预定”的程序

总结

过去
- 缓慢的重新编译周期（甚至每天一次）
- 在一个周期内找到尽可能多的错误
现在
- 快速的重新编译周期
- 用户倾向于每周期更新一个错误
- 复杂的错误恢复不那么引人注目

抽象语法树(Abstract syntax trees)

解析器跟踪符号序列的派生
但编译器的其余部分需要程序的结构表示
抽象语法树
- 类似解析树，但忽略一些细节
- 缩写为AST

例子

考虑语法 $\text{E} \rightarrow \operatorname{int}|(\text{E})| \text{E}+\text{E}$
以及字符串 $5 + (2 + 3)$
词法分析后（符号列表） $\text { int}_{5}\ { }^{\prime}+{ }^{\prime}\ { }^{\prime}\left({ }^{\prime}\ \text { int}_{2}\ { }^{\prime}+{ }^{\prime} \text { int}_{3}\ {}^{\prime}\right)^{\prime}$

在解析过程中，我们构建了一个解析树
该解析树：
跟踪解析器的操作
捕捉嵌套结构
但信息太多
- 括号
- 单个后续节点
AST也捕获嵌套结构
抽象出具体语法
- =>更紧凑、更易用
编译器中重要的数据结构

递归下降解析

解析树按如下方式构造
- 从顶部
- 从左到右
终止符在符号流中的出现顺序：
$t_{2} t_{5} t_{6} t_{8} t_{9}$

例子

考虑语法
$\begin{array}{l} \mathrm{E} \rightarrow \mathrm{T} \mid \mathrm{T}+\mathrm{E} \\ \mathrm{T} \rightarrow \operatorname{int}\left|\mathrm{int}^{*} \mathrm{T}\right|(\mathrm{E}) \end{array}$
符号流是：$\left(\text { int}_{5}\right)$
从顶层非终止符$\text{E}$开始
- 按顺序尝试$\text{E}$的规则

首先得到如下匹配：

该匹配错误，所以回溯。

该匹配依然错误，再次回溯。

匹配成功。

习题

选第二项。

递归下降算法

依然考虑语法： $\begin{array}{l} \mathrm{E} \rightarrow \mathrm{T} \mid \mathrm{T}+\mathrm{E} \\ \mathrm{T} \rightarrow \operatorname{int}\left|\mathrm{int}^{*} \mathrm{T}\right|(\mathrm{E}) \end{array}$
让TOKEN作为符号类型
- 特殊符号INT,OPEN,CLOSE,PLUS,TIMES
让全局next指向下一个输入符号

定义用于检查以下项是否匹配的布尔函数：

一个给定的符号终止符：

bool term(TOKEN tok) { return *next++ == tok; }

$S$的第$n$个production：
```
bool Sn() { … }
```

尝试$S$的所有production：

bool S() { … }

对于production $\text{E}\to\text{T}$：
```
bool E1() { return T(); }
```

对于production $\text{E}\to\text{T}+\text{E}$：

bool E2() { return T() && term(PLUS) && E(); }

对于$\text{E}$的所有production（带回溯）：

bool E() {
    TOKEN *save = next;
    return (next = save, E1())
    	|| (next = save, E2()); }

非终止符$\text{T}$的函数：

bool T1() { return term(INT); }
bool T2() { return term(INT) && term(TIMES) && T(); }
bool T3() { return term(OPEN) && E() && term(CLOSE); }

bool T() {
    TOKEN *save = next;
    return (next = save, T1())
        || (next = save, T2())
        || (next = save, T3()); }

为了启动解析器
- 初始化next，将其指向第一个符号
- 调用E()
易于手工实现

习题

选择第二第四项，第二项错在$\text{&&}$，最后一项错在$\text{T}_1$。

递归下降算法的局限性

例子

依然考虑前一个例子：

假设输入为

$\text{int} *\text{int}$

函数的调用顺序为

T1返回true，函数调用终止，从而解析失败（后续部分无法解析）。

分析

如果非终止符$X$的production成功
- 无法回溯，从而无法尝试其他production
通用递归下降算法支持全回溯
- 能够实现任何语法
提出的递归下降算法不通用
- 但手动执行容易
对于任何非终止最多只有一个production的语法，足以满足要求
可以重写示例语法，以配合所提出的算法使用
- 通过左分解，未来视频的主题

左递归

考虑production $\mathrm{S} \rightarrow \mathrm{S}\ \mathrm{a}$
```
bool S1() { return S() && term(a); }
bool S() { return S1(); }
```
陷入无限循环
左递归语法有一个非终止符$\text{S}$
$\text{S} \rightarrow^+\text{S}\alpha,对某个\alpha$
在这种情况下，递归下降不起作用
- 陷入无限循环

例子

考虑左递归语法 $\text{S} \rightarrow \text{S}\ \alpha \mid \beta$
$S$生成所有以一个$\beta$开始，后面跟任意数量$\alpha$的字符串
可以使用右递归重写
$\begin{aligned} \text{S} &\rightarrow \beta\ \text{S}^{\prime} \\ \text{S}^{\prime} &\rightarrow \alpha\ \text{S}^{\prime} \mid \varepsilon \end{aligned}$
一般的 $\mathrm{S} \rightarrow \mathrm{S} \alpha_{1}|\ldots| \mathrm{S} \alpha_{\mathrm{n}}\left|\beta_{1}\right| \ldots \mid \beta_{\mathrm{m}}$
所有从$\text{S}$派生的字符串都以$\beta_1,\ldots,\beta_m$中的一个开始，后面跟几个$\alpha_1,\ldots\alpha_n$
重写为
$\begin{aligned} \text{S} &\rightarrow {\beta}_{1} \text{S}^{\prime}|\ldots| \beta_{m} \text{S}^{\prime} \\ \text{S}^{\prime} &\rightarrow \alpha_{1} \text{S}^{\prime}|\ldots| \alpha_{n} \text{S}^{\prime} |\varepsilon \end{aligned}$
语法
$\begin{aligned} \text{S} &\rightarrow \text{A} \alpha| \delta \\ \text{A} &\rightarrow \text{S} \beta \end{aligned}$
也是左递归的，因为
$\mathrm{S} \rightarrow^{+} \mathrm{S} \beta \alpha$
这种左递归也可以消除
一般算法见龙书

习题

选第三项。

总结

递归下降
- 简单通用的解析策略
- 必须首先消除左递归
- 但这可以自动完成
用于生产编译器
- 例如gcc