语法分析：自顶向下方法

语法分析器从词法分析器获得 Token 序列，确认该序列是否可以由语言的文法生成，然后：

• 对于语法错误的程序，报告错误信息
• 对于语法正确的程序，生成语法分析树，例如抽象语法树（Abstract Syntax Tree, AST）

自顶向下指的是，从文法的开始符号出发，尝试推导出输入的串。以分析树（Parse Tree）的角度来看，自顶向下方法从根节点出发，构建分析树。

描述编程语言的语法结构

为描述编程语言的语法结构，引入以下概念：

上下文无关文法（Context-Free Grammar, CFG）

上下文无关语言 $L(G)$ 是正则语言 $L(r)$ 的超集。

正则语言不能用于描述配对或嵌套的结构，原因在于有穷自动机无法记录访问同一状态的次数，因此不能够表达例如 $(^n)^n$ 的结构。正则语言是线性文法产生的所有句子的集合。

$$G = (T, N, P, S) $$

$T$ - 终结符集合（Terminals）：组成串的基本符号（token），例如 $T = \{num, +, -\}$

$N$ - 非终结符集合（Non-terminals）：语法变量，最终应通过产生式与终结符组合成串，例如 $N = \{expr, stmt\}$

$P$ - 产生式集合（Productions）：产生式描述将终结符和非终结符组合成串的方法，例如 $E \rightarrow E + E\ |\ (E)\ |\ id$

$S$ - 开始符号（Start symbol）：某一个特定非终结符。它对应的串的集合就是文法的语言。

上下文无关文法的含义是，对于推导 $\alpha A \beta \Rightarrow \alpha \gamma \beta$ 来说，符号串 $\gamma$ 仅仅根据产生式 $A \rightarrow \gamma$ 推导，而与 $A$ 的上下文 $\alpha$，$\beta$ 无关。

推导与规约

推导与规约是产生式和非终结符之间的转换过程，它们拥有相反的含义。以产生式 $A \rightarrow \gamma$ 、串 $\alpha A \beta$ 为例：

直接推导 把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。

用符号 $\Rightarrow$ 表示直接推导，$\alpha A \beta \Rightarrow \alpha \gamma \beta$

直接规约 把符号串中的某一部分用某一个产生式左部来代替。

即如果 $\alpha A \beta \Rightarrow \alpha \gamma \beta$ ，则称 $\alpha \gamma \beta$ 直接规约到 $\alpha A \beta$

最左推导 指的是每步总是代换最左边的非终结符。在自顶向下的语法分析中，总是采用最左推导的方式。

最左规约 是最右推导的反过程，在自底向上的语法分析中，总是采用最左归约的方式。

句型、句子、语言

句型（Sentential form） - 对开始符号为 $S$ 的文法 $G$ 如果从 $S$ 出发能够经过零步或一步或若干步推导得到 $\alpha$，则称 $\alpha$ 是 $G$ 的一个句型。句型可以包含终结符、非终结符，也可以是空串。

句子（Sentence） - 句子是指不含非终结符的句型。

语言（Language） - 语言是指由文法 $G$ 推导出的所有句子构成的集合，用 $L(G)$ 表示。

编程语言文法

上下文无关文法也是编程语言文法的超集。因为上下文无关文法仍然可能具有二义性，而编程语言的文法通常是无二义的。

如果文法的某些句子存在不止一棵分析树，则称该文法是二义的，例如：

产生式 $E \rightarrow E + E\ |\ E \times E\ |\ (E)\ |\ id$

对于句子 $id \times id + id$ 存在两棵不同的分析树：

src:https://rainoftime.github.io/teaching/index.html

在编程语言文法的情形下，如果令从左往右的三个 $id$ 分别为 $3,4,5$，则这两棵分析树将分别导出 $3\times(4 + 5)$ 和 $(3\times 4) + 5$，这显然是不可以接受的。

将文法进行分层，规定在最左推导中更深层的非终结符总是会被优先替换，确保只有一种最左推导，可以消除上面的二义性问题。这是消除二义性的的惯用技术：分层，它需要规定符号的优先级以及规定符号的结合性。

我们首先考虑符号的优先级（终结符大于非终结符，括号大于乘法大于加法），将产生式改写为：

$$\begin{array}{rl} E \rightarrow & E + E \\ | & E \times E \\ | & (E)\ |\ id \end{array} $$

然后考虑符号的结合性，将上面的产生式进一步改写为：

$$\begin{array}{l} E \rightarrow E + T\ |\ T \\ T \rightarrow T \times F\ |\ F \\ F \rightarrow (E)\ |\ id \end{array} $$

这里的改写方法是：

1. （优先级）根据算符不同的优先级，为每一个算符引入新的非终结符，越接近开始符号的算符优先级越低
2. （结合性）递归非终结符在终结符左边，运算就左结合，反之就右结合，例如上面的 $+$ 与 $\times$

递归下降分析（Recursive-Descent Parsing）

使用递归实现的穷举法，对于非终结符 $A$ ，利用它的文法规则 $A \rightarrow X_1\ |\ X_2\ |\ \dots\ |\ X_k$，穷举所有选择。对于每一个选择 $X_i$，调用对应的处理过程：

• 如果 $X_i$ 是一个非终结符，递归调用非终结符 $X_i$ 对应的处理过程
• 如果 $X_i$ 是一个终结符 $a$，匹配输入串中对应的终结符 $a$

如果选择了不合适的产生式，得到一个非预期的串，则回溯。

例如，文法 $S \rightarrow cAd$，$A \rightarrow ab\ |\ a$，考虑输入串 $cad$ 的分析树：

src:https://rainoftime.github.io/teaching/index.html

由于往往需要对多个非终结符进行推导展开，因此尝试的路径可能呈指数级爆炸。

预测分析法（Predictive Parsing）

$LL(k)$ 文法

L = left-to-right （从左到右扫描）

L = leftmost derivation （最左推导）

k = 向前看 $k$ 个 Token 来确定产生式

$LL(1)$ 文法

$LL(1)$ 文法：每次为最左边的非终结符号选择产生式时，向前看 $1$ 个输入符号，预测要使用的产生式。

$\text{First}(\alpha) ::= \{a | \alpha \Rightarrow^* a\dots,a \in T\}$，即：可从 $\alpha$ 推导得到的串的首个终结符的集合。

$\text{Follow}(A) ::= \{a | S \Rightarrow^* \dots Aa\dots, a \in T\}$，即：从开始符号 $S$ 出发，可能在推导过程中跟在 $A$ 右边的终结符的集合。

$\text{Nullable}(A) ::= \text{whether A can derive } \varepsilon$，即：从非终结符 $A$ 出发，是否能推导出空串。

为确保产生式选择的唯一性，$LL(1)$ 文法中的任何产生式 $A \rightarrow \alpha\ |\ \beta$，其 $\alpha$ 和 $\beta$ 都需要满足（定义）：

• $\text{First}(\alpha) \cap \text{First}(\beta) = \varnothing$（即：$\alpha$ 与 $\beta$ 不能推导出以同一个字符为首的串）
• 若 $\beta \Rightarrow^* \varepsilon$，那么 $\alpha \nRightarrow^* \varepsilon$，且 $\text{First}(\alpha) \cap \text{Follow}(A) = \varnothing$（即：$\alpha$ 与 $\beta$ 不能同时推导出 $\varepsilon$。在 $\beta$ 能推导出空串的情形下，$\alpha$ 可能推导出的串的首部不应该出现在可能在推导过程中跟在 $A$ 右边的终结符号集中）

$LL(1)$ 文法满足以下三个性质：

• $LL(1)$ 文法是无二义的
• $LL(1)$ 文法是无左递归的（即：不存在 $A \rightarrow^* A\alpha$）
• $LL(1)$ 文法是无左公因子的（即：不存在 $X \rightarrow \alpha\beta\ |\ \alpha\gamma$）

消除左递归

对于产生式 $A \rightarrow^* A\alpha\ |\ \beta$，其中 $\alpha \neq \varepsilon$，$\beta \neq \varepsilon$，$A \notin \text{First}(\alpha)$，$A \notin \text{First}(\beta)$：通过以下方法将这个文法限制为仅含右递归、不含左递归的形式：

$$\begin{array}{l} A \rightarrow \beta A'\\ A' \rightarrow \alpha A'\ |\ \varepsilon \end{array} $$

观察：去掉 $A\alpha \alpha \dots$ 的病态情形之后，由 $A$ 生成的串只能以某个 $\beta$ 开头，然后跟上零个或多个 $\alpha$。

消除左公因子

对于产生式 $X \rightarrow \alpha\beta\ |\ \alpha\gamma$，使用下面的产生式替换：

$$\begin{array}{l} X \rightarrow \alpha X'\\ X' \rightarrow \beta\ |\ \gamma \end{array} $$

通过改写产生式来推迟决定，等读入了足够多的输入，获得足够信息后再做选择。

$LL(1)$ 的预测分析法（递归下降实现）

1. 计算所有非终结符的 $\text{First}()$，$\text{Follow}()$，$\text{Nullable}()$
2. 构造预测分析表
3. 根据预测分析表上的内容，即可通过向前看一个输入符号来唯一地确定选择哪个产生式

计算所有非终结符的 $\text{Nullable}()$，$\text{First}()$，$\text{Follow}()$

$\text{Nullable}()$

根据 $\text{Nullable}()$ 的归纳定义 base case 以及 inductive case，迭代地从 base case 开始计算，直到所有非终结符的 $\text{Nullable}()$ 不再变化。初始状态下，令所有非终结符的 $\text{Nullable}()$ 为 False。

src:https://rainoftime.github.io/teaching/index.html

$\text{First}()$

根据 $\text{First}()$ 的归纳定义 base case 以及 inductive case，迭代地从 base case 开始计算 $\text{First}()$ 不再变化。初始状态下，令所有非终结符的 $\text{First}()$ 为 $\varnothing$。

src:https://rainoftime.github.io/teaching/index.html

$\text{Follow}()$

根据 $\text{Follow}()$ 的归纳定义 base case 以及 inductive case，迭代地从 base case 开始计算 $\text{Follow}()$ 不再变化。初始状态下，令所有非终结符的 $\text{Follow}()$ 为 $\varnothing$。

src:https://rainoftime.github.io/teaching/index.html

构造预测分析表

以非终结符为行，终结符为列建表。预测分析表初始是空的。检定文法中的每一个产生式 $A \rightarrow \alpha$，按以下的规则填充分析表的 $A$ 行某列单元格：

for each production "A -> \alpha"
    for each a \in first(\alpha)
        add "A -> \alpha" to T[A, a]
    if \varepsilon \in first(\alpha) then
        for each b \in follow(A)
            add "A -> \alpha" to T[n , b]

或者引入 $\text{Nullable}$ 的概念时：

for each production "A -> \alpha"
    for each a \in first(\alpha)
        add "A -> \alpha" to T[A, a]
    if \alpha is Nullable then
        for each a \in follow(A)
            add "A -> \alpha" to T[A, a]

注意 这里的 $\alpha$ 可能是由若干终结符与非终结符组合而成的右部（例如 $E \rightarrow A\ B\ \gamma$），对于 $\text{First}(A\ B\ \gamma)$ ，应当参照上面计算 $\text{First}(A)$ 之相同方法。也可以利用已经生成好的所有非终结符的 $\text{First}()$ 集合：

对于产生式 $E \rightarrow E_1\ E_2\ E_3\ \dots \ E_n$：

令右部 $\text{First}(\text{RHS})$ 集初始为空。

顺序检定终结符或非终结符 $E_i$，从 $i = 1$ 开始：

• 如果 $E_i$ 是终结符 $t$：
  • 如果 $t \neq \varepsilon$，则将 $t$ 并入 $\text{First}(\text{RHS})$ 集，然后终止检定
  • 如果 $t = \varepsilon$，则将 $\varepsilon$ 并入 $\text{First}(\text{RHS})$ 集，然后检定 $E_{i+1}$
• 如果 $E_i$ 是非终结符：
  • 如果 $\text{Nullable}(E_i) = 0$，则将 $\text{First}(E_i)$ 并入 $\text{First}(\text{RHS})$ 集，然后终止检定
  • 如果 $\text{Nullable}(E_i) = 1$，则将 $\text{First}(E_i)$ 并入 $\text{First}(\text{RHS})$ 集，然后检定 $E_{i+1}$

如图所示（注意每一张子图中的算法最后一行有一点错误，应该为 add "A -> \alpha" to T[n , b]）：

src: https://www.cs.york.ac.uk/fp/lsa/

可以证明，对于 $LL(1)$ 文法，预测分析表的每一个单元格要么没有元素，要么只有一个元素。

$LL(1)$ 语法分析器可视化：
https://www.cs.princeton.edu/courses/archive/spring20/cos320/LL1/

错误恢复

如果语法分析器的接收的 token 流不是文法所能够接受的，语法分析器需要抛出异常并停止语法分析，然后打印错误信息并从错误中恢复。

我们可以通过删除、替换、插入 token 来从错误中恢复。其中，插入 token 是存在风险的，因为这可能使得语法分析器不会停止；而删除 token 则不会遇到无限循环的问题，这是因为我们总会碰到 token 流的 EOF 然后停止我们的语法分析器。

一个通过删除 token 实现的从错误中恢复的方法是，按顺序跳过 token 流中所有不在当前分析的非终结符之 $\text{Follow}()$ 集合中的 token。