错误处理

在语法分析阶段，我们要检查程序中的语法是否正确，如果有错误，需要一些方法报错，以及越过错误点继续检查。

下面是几个错误处理方法

恐慌模式

最简单同时也是使用最多的方法。

当遇到一个错误时，我们跳过一些输入字符，直到遇到指定的字符（串）后从该处继续检查，这些指定的字符需要人为设置，通常称为同步字符（synchronizing token）。

错误产生式

在产生式集合中加入可以推导出含有错误的产生式，如果在程序推导过程中推导出了含有错误的产生式，就说明程序有语法错误，并且可以根据该含有错误的产生式报相应的信息。

局部和全局纠正

当错误产生时，在错误点修改（增删改）尽可能少的字符，以使程序正确，这个方法目前仅具理论价值。

自顶向下的语法分析

在自顶向下的分析中，我们要从开始符开始，如果通过推导可以得到输入串，那么说明输入串没有语法错误，并且在这个过程中我们也生成了语法分析树，如果不能推导出，则输入串有语法错误。

有两种方法：

1. 第一种说白了，就是普通的深度搜索算法，其中会发生回溯，开销较大，不常用。
2. 第二种是不会发生回溯的搜索算法，比第一种常用，结果是给出输入串的最左推导或发现输入中有错。

带回溯的深度搜索算法

对于当前的公式，从左到右对每个非终结符的可能推导一个一个尝试，直到找到结果（返回答案），或发现不匹配（回溯），如果所有可能都无法匹配，那么报错。

左递归

立即左递归

形如 A → A α A\rightarrow A\alpha A→Aα的产生式为立即左递归。

消除立即左递归

将 A → A α ∣ β A\rightarrow A\alpha |\beta A→Aα∣β替换为： A → β A ′ A\rightarrow \beta A^{'} A→βA′和 A ′ → α A ′ ∣ ϵ A^{'}\rightarrow \alpha A^{'} | \epsilon A′→αA′∣ϵ

消除一般的左递归

处理算法：

将非终结符排序为A1 A2 ... An
for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
        将((Ai) -> (Aj)r) 替换为 
          (Ai) -> (c1)r | (c2)r | ... | (ck)r 
    }
    消除Ai产生式间的立即左递归
}
           

不带回溯的预测算法

通过查看输入串中当前字符的下一个字符（look ahead），可以指导我们选择哪一个产生式进行推导，从而避免了开销较大的回溯过程。在这里需要使用LL(k)语法。

先来解释两个概念：

First(a)

我们需要知道从一个字符可以推导出的首个字符有哪些。

定义：从a可以推出的串的首字符的集合记为First(a)。

求First(a)的方法：

运用下面的3条规则直到没有可以被加入 F i r s t ( a ) First(a) First(a)的元素为止：

1. 若 a a a为终结符，则 F i r s t ( a ) = a First(a) = {a} First(a)=a
2. 若 a a a为非终结符，且 a → Y 1 Y 2 . . . Y n a\rightarrow Y_1Y_2...Y_n a→Y1​Y2​...Yn​是一个产生式，对于任意 i ∈ [ 1 , n ] i \in [1,n] i∈[1,n]，若有 Y 1 Y 2 . . . Y i − 1 ⇒ ∗ ϵ Y_1Y_2...Y_{i-1} \Rightarrow ^* \epsilon Y1​Y2​...Yi−1​⇒∗ϵ，则 F i r s t ( Y i ) ⊆ F i r s t ( a ) First(Y_i) \subseteq First(a) First(Yi​)⊆First(a)
3. 如果有 a → ϵ a\rightarrow \epsilon a→ϵ，则将 ϵ \epsilon ϵ加入 F i r s t ( a ) First(a) First(a)。

我的理解：

1. 对于规则1，终结符不能推出任何字符串，因此必然没有首字符集合。
2. 对于规则2，若一个产生式右部的前半部分可以推成空，那么后半部分的首字符当然就是整个右部的首字符，即当作推出串的首字符。

Follow(a)

定义：紧跟在从a可以推出的串后面的第一个终结字符的集合即为Follow(a)。

方法：

1. 将输入结束符$加入 F o l l o w ( S ) Follow(S) Follow(S)，其中S为开始符号
2. 若存在 A → α B β A\rightarrow \alpha B\beta A→αBβ，则 F i r s t ( β ) − ϵ ⊆ F o l l o w ( B ) First(\beta)-\epsilon \subseteq Follow(B) First(β)−ϵ⊆Follow(B)
3. 若存在 A → α B A \rightarrow \alpha B A→αB，则 F o l l o w ( A ) ⊆ F o l l o w ( B ) Follow(A) \subseteq Follow(B) Follow(A)⊆Follow(B)
4. 若存在 A → α B β A \rightarrow \alpha B \beta A→αBβ，且 ϵ ∈ β \epsilon \in \beta ϵ∈β，则 F o l l o w ( A ) ⊆ F o l l o w ( B ) Follow(A) \subseteq Follow(B) Follow(A)⊆Follow(B)

LL(k)语法

含义

第一个L表示从左到右遍历解析，第二个L表示产生最左推导，k表示向前看k个字符，通常是1。

判定

使用下面的规则判断文法G是否是LL（1）的：

当且仅当G中任意的两个产生式 A → α A\rightarrow \alpha A→α和 A → β A\rightarrow \beta A→β满足下面的条件：

1. F i r s t ( α ) First(\alpha) First(α)和 F i r s t ( β ) First(\beta) First(β)不含相同终结符
2. α \alpha α和 β \beta β中至多一个可以推出空串
3. 若 β \beta β可以推出空串，则 α \alpha α不能推出以 F o l l o w ( A ) Follow(A) Follow(A)中某个终结符开头的串，同理对 α \alpha α。

我的理解：

1. 这3条都是为了避免在推导中有多个选择的情况。
2. 前两条说 F i r s t ( α ) First(\alpha) First(α)和 F i r s t ( β ) First(\beta) First(β)不相交，即在一个产生式右部的开头，一个终结符只能出现一次，换句话说，对于一个终结符，只能选择这一个产生式进行推导，也就避免了多个选择的情况。
3. 第3条说，若 ϵ ∈ F i r s t ( β ) \epsilon \in First(\beta) ϵ∈First(β)，则 F i r s t ( α ) First(\alpha) First(α)和 F o l l o w ( A ) Follow(A) Follow(A)不相交。

LL（1）的预测分析表构造

预测分析表是一个二维表格，其中某一项为M[A, a]，表示当推导A时，若下一个字符为a，应该执行的产生式，即这个表告诉我们什么时候应该做什么事。

构造方法：

对于G中的每个产生式 A → α A \rightarrow \alpha A→α：

1. 对于 F i r s t ( α ) First(\alpha) First(α)中的每个终结符a，将 A → α A \rightarrow \alpha A→α加入M[A, a]
2. 若 ϵ ∈ F i r s t ( α ) \epsilon \in First(\alpha) ϵ∈First(α)，对所有终结符 b ∈ F o l l o w ( A ) b \in Follow(A) b∈Follow(A)，将 A → α A \rightarrow \alpha A→α加入M[A, b]
3. 若 ϵ ∈ F i r s t ( α ) \epsilon \in First(\alpha) ϵ∈First(α)，且$$ \in Follow(A) ，将 ，将 ，将A \rightarrow \alpha$加入M[A, $]