錯誤處理

在文法分析階段，我們要檢查程式中的文法是否正确，如果有錯誤，需要一些方法報錯，以及越過錯誤點繼續檢查。

下面是幾個錯誤處理方法

恐慌模式

最簡單同時也是使用最多的方法。

當遇到一個錯誤時，我們跳過一些輸入字元，直到遇到指定的字元（串）後從該處繼續檢查，這些指定的字元需要人為設定，通常稱為同步字元（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, $]