Stanford Compiler Week 4 Bottom-Up Parsing I

课程主页：

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

课程视频：

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

整理笔记的时候发现每周的内容过多，所以还是分两次整理，这次回顾自顶向下解析I。

预测性解析

• 预测性解析类似递归下降，但解析器可以预测使用哪个production

  • 通过看接下来的几个符号
  • 不回溯

• 预测性解析器接受$LL(k)$语法

  • (left-to-right) (left-most derivation) (k tokens look ahead)

• 在递归下降中，

  • 在每一步中，有多种production选择
  • 回溯用来撤销错误选择

• 在$LL(1)$中，

  • 每一步只能选择一种production

• 回顾语法

  $$\begin{array}{l} \mathrm{E} \rightarrow \mathrm{T}+\mathrm{E} | \mathrm{T} \\ \mathrm{T} \rightarrow \operatorname{int}\left|\mathrm{int}^{*} \mathrm{T}\right|(\mathrm{E}) \end{array}$$

• 很难预测，因为

  • T的两个production以int开头
  • E不清楚如何预测

• 我们需要对语法进行左分解（production的第一个符号不同）

  • $$\begin{array}{ll} \mathrm{E} \rightarrow \mathrm{T} \mathrm{X} & \mathrm{X} \rightarrow+\mathrm{E} \mid \varepsilon \\ \mathrm{T} \rightarrow(\mathrm{E}) \mid \text { int } \mathrm{Y} & \mathrm{Y} \rightarrow^{*} \mathrm{T} \mid \varepsilon \end{array}$$

  • $LL(1)$解析表：

    

• 考虑$\text{[E,int]}$

  • 当前非终止符为$\text{E}$，下一个输入为$\text{int}$时，使用$\mathrm{E} \rightarrow \mathrm{T} \ \mathrm{X}$

• 考虑$\text{[Y,+]}$

  • 当前非终止符为$\text{Y}$，当前输入为$\text{+}$时，去掉$\text{Y}$
  • 只有当$\text{Y}\to \varepsilon$时，$\text{Y}$后面才能跟着$+$

• 考虑$\text{[E,}\star]$

  • 无法从非终止符$\text{E}$派生出以$\text{*}$开头的字符串

小结

• 类似于递归下降的方法，除了

  • 对最左侧非终止符S
  • 我们查看下一个输入符号a
  • 并选择[S,a]对应production

• 栈记录解析树的前端

  • 待拓展的非终止符
  • 尚未匹配输入的终止符
  • 栈顶=最左边的待处理终止符或非终止符

• 到达错误状态时拒绝

• 在输入结束并且栈空时接受

伪代码

• 伪代码如下

  

• S表示起始符号，$表示输入的结束，X表示非终止符，t表示终止符

• 之前例子的算法调用流程：

  

• 解析表加以参考：

  

习题

选第四项。

选第二项。

First Sets

• 考虑非终止符$\mathrm A$，production $\mathrm A\to \alpha$，符号$\mathrm t$
• $\text{T}[\text{A,t}]=\alpha$的两种情形：
  • 如果$\alpha\to^{\star}\mathrm t \beta$
    • $\alpha$在第一个位置可以派生出$\mathrm t$
    • 我们称$\text{t}\in\text{First}(\alpha)$
  • 如果$\mathrm A\to \alpha,\alpha \to^{\star}\varepsilon, \text{S}\to^{\star}\beta \text{At}\delta$
    • 如果堆栈有A，输入为t，并且A不能派生t，则很有用
    • 在这种情况下，唯一的选择是去掉A（通过派生$\varepsilon$）
      • 只有$\text{t}$至少在一次派生紧随$\text{A}$才能起作用
    • 我们称$\text{t}\in \text{Follow}(\text{A})$

定义

定义

$$\operatorname{First}(\text{X})=\left\{t \mid \text{X} \rightarrow^{*} \text{t} \alpha\right\} \cup\left\{\varepsilon \mid \text{X} \rightarrow^{*} \varepsilon\right\}$$

算法概述：

1. $\text { First }(t)=\{t\}$，$t$表示终止符
2. $\varepsilon \in \text { First }(X)$
   1. 如果$X \rightarrow \varepsilon$
   2. 如果$X \rightarrow \mathrm{A}_{1} \ldots \mathrm{A}_{\mathrm{n}}$，并且$\varepsilon \in \operatorname{First}\left(\mathrm{A}_{\mathrm{i}}\right),1\le i\le n$
3. $\text { First }(\alpha) \subseteq \text { First }(\mathrm{X})$，如果$\mathrm{X} \rightarrow \mathrm{A}_{1} \ldots \mathrm{A}_{\mathrm{n}} \alpha$，并且$\varepsilon \in \operatorname{First}\left(\mathrm{A}_{\mathrm{i}}\right),1\le i\le n$

例子

回顾语法

$$\begin{array}{ll} \mathrm{E} \rightarrow \mathrm{T} \mathrm{X} & \mathrm{X} \rightarrow+\mathrm{E} \mid \varepsilon \\ \mathrm{T} \rightarrow(\mathrm{E}) \mid \text { int } \mathrm{Y} & \mathrm{Y} \rightarrow{*} \mathrm{T} \mid \varepsilon \end{array}$$

基本情形：

• $\text{First}(t)=\{t\}$
• $\text{First}(\star)=\{\star\}$
• $\text{First}(()=\{(\}$
• $\text{First}())=\{)\}$
• $\text{First}(\text{int})=\{\text{int}\}$

进一步，我们有

$$\text{First}(T)\subseteq \text{First}(E)$$

显然我们有

$$\text{First}(T)=\{(,\text{int}\}$$

注意$\text{First}(T)$不包含$\varepsilon$，所以实际上我们有

$$\text{First}(T)=\text{First}(E)$$

其余两个First是显然的：

$$\begin{aligned} \text{First}(X)&=\{t,\varepsilon\} \\ \text{First}(Y)&=\{\star,\varepsilon\} \end{aligned}$$

Follow Sets

定义

• 定义

  $$\text { Follow }(\mathrm{X})=\left\{\mathrm{t} \mid \mathrm{S} \rightarrow^{*} \beta \mathrm{X} \mathrm{t} \delta\right\}$$

• 直觉

  • 如果$\mathrm{X} \rightarrow \mathrm{A}\ \mathrm{B}$，那么$\text { First(B) } \subseteq \text { Follow }(\mathrm{A})$并且$\text { Follow }(\mathrm{X}) \subseteq \text { Follow }(\mathrm{B})$
    • 如果$\mathrm B \rightarrow^{*} \varepsilon$，那么$\text { Follow }(\mathrm{X}) \subseteq \text { Follow }(\mathrm{A})$
  • 如果$\mathrm S$是起始符号，那么$$ \in \text { Follow(S) }$

算法概述：

1. $$ \in \text { Follow(S) }$
2. $\text { First }(\beta)-\{\varepsilon\} \subseteq \text { Follow }(\mathrm X)$
   1. 对每个production$A \rightarrow \alpha X \beta$
3. $\text { Follow(A) } \subseteq \text { Follow }(\mathrm{X})$
   1. 对每个production $\mathrm A \rightarrow \alpha\mathrm X \beta$，其中$\varepsilon \in \text { First }(\beta)$

例子

回顾语法

$$\begin{array}{ll} \mathrm{E} \rightarrow \mathrm{T} \mathrm{X} & \mathrm{X} \rightarrow+\mathrm{E} \mid \varepsilon \\ \mathrm{T} \rightarrow(\mathrm{E}) \mid \text { int } \mathrm{Y} & \mathrm{Y} \rightarrow{*} \mathrm{T} \mid \varepsilon \end{array}$$

将4个production按照从左到右，从上到下的顺序标号为1,2,3,4。

由production1,2可得

$$\text{Follow(X)=Follow(E)}$$

由production3可得

$$\text{Follow(E)}\subseteq \text{Follow(T)}$$

由production3,4可得

$$\text{Follow(Y)}=\text{Follow(T)}$$

对于终止符号，不难看出

$$\begin{aligned} \text{Follow}(()&=\{\text{(,int}\}\\ \text{Follow}())&=\{\text{+,\$,)}\}\\ \text{Follow}(+)&=\{\text{(,int}\}\\ \text{Follow}(*)&=\{\text{(,int}\}\\ \text{Follow}(\text{int})&=\{\text{*,+,\$,)}\}\\ \end{aligned}$$

对于非终止符

$$\begin{aligned} \text{Follow(E)}&=\{\$,)\}\\ \text{Follow(X)}&=\{\$,)\}\\ \text{Follow(T)}&=\{+,$,)\}\\ \text{Follow(Y)}&=\{+,$,)\}\\ \end{aligned}$$

$LL(1)$解析表

• 为CFG $G$构造一个解析表$T$
• 对每个production $A\to \alpha$：
  • 对每个终止符$t\in \text{First}(\alpha)$
    • $T[A,t]=\alpha$
  • 如果$\varepsilon\in \text{First}(\alpha)$，对每个$t\in\text{Follow}(A)$
    • $T[A,t]=\alpha$
  • 如果$\varepsilon\in \text{First}(\alpha),$\in\text{Follow}(A)$
    • $T[A,$]=\alpha$

例子

考虑production

$$S\to S\ a | b$$

那么

$$\begin{aligned} \text{First}(S)&=\{b\} \\ \text{Follow}(S)&=\{\$,a\} \end{aligned}$$

构造解析表

	$a$	$b$	$$$
$S$		$b,Sa$

• 如果任何一项被定义多次，那么$G$不是$LL(1)$
• 大多数编程语言CFG不是$LL(1)$

自底向上解析

介绍

• 自底向上的解析比（确定性的）自顶向下的解析更通用

  • 同样高效
  • 建立在自顶向下的分析方法的基础上

• 自底向上是首选方法

• 自底向上的解析器不需要左分解语法

• 回到我们的例子中的“自然”语法

  $$\begin{array}{l} \mathrm{E} \rightarrow \mathrm{T}+\mathrm{E} | \mathrm{T} \\ \mathrm{T} \rightarrow \operatorname{int}\left|\mathrm{int}^{*} \mathrm{T}\right|(\mathrm{E}) \end{array}$$

例子

• 考虑字符串：$\text { int }^{*} \text { int }+\text { int }$

• 自底向上解析通过反转production将字符串缩减为起始符号

  

• 注意结果，向后向前看，跟踪最右派生

• 关于自底向上解析的重要事实1：

  • 自底向上的解析器反向跟踪最右边的派生
  • 

习题

第三项。

Shift-Reduce解析

引子

• 关于自底向上解析的重要事实1：

  • 自底向上的解析器反向跟踪最右边派生

• 重要事实1有一个有趣的结果：

  • 令$\alpha\beta \omega$成为自底向上解析的一个步骤
  • 假设下一个reduction是$X\to\beta$
  • 那么$\omega$是终止符构成的字符串

• 为什么？因为$\alpha X\omega \to \alpha \beta \omega$是最右派生中的一个步骤（更右侧已经化为终止符）

• 想法：将字符串拆分为两个子字符串

  • 右子串尚未通过解析进行检查
  • 左子串有终止符和非终止符
  • 分界点用$|$标记
    • $\alpha X|\omega$

• 自底向上解析使用两种行动

  • Shift
  • Reduce

• Shift：向右移动$|$一位

  • 将终止符移到左边的字符串 $$ABC|xyz \Rightarrow ABCx|yz$$

• Reduce：在左字符串的右端应用inverse production

  • 如果$A\to xy$是production，那么 $$Cbxy|ijk \Rightarrow CbA|ijk$$

例子

总结

• 左字符串可以由栈实现
  • 栈顶部是$|$
• Shift
  • 向栈上push一个终止符
• Reduce
  • 从栈中弹出符号（production rhs）
  • 向栈上push非终止符（production lhs）
• 在给定的状态下，多个操作（shift或reduce）可能导致有效的解析
• 如果shift或reduce是合法的，则存在shift-reduce冲突
• 如果按两种不同的production，reduce是合法的，则存在reduce-reduce冲突

习题

第四项