# Theory of Computation Chapter 5, 6 - Context Free Grammar

（請搭配達叔的投影片一起服用）

**上下文無關語言 (Context free language)** 是一種形式語言，其滿足:

* 可以用**上下文無關文法 (Context free grammar)** 定義
* 可以被**下推自動機 (Pushdown automata)** 所接受

上下文無關語言是正則語言的超集，即上下文無關語言包含正則語言。

## Context Free Grammar

* 上下文無關文法(Context Free Grammar)
* 可以表示為一個四元組 $(V, T, S, P)$
* $V$ 是**非終結符號 / 變數(variables)** 的有限集
* $T$ 是**終止符號 (terminals)** 的有限集
* $S$ 是**起始符號 (start variable)**， $S \in V$
* $P$ 是**產生式規則 (production rules)**， 形式如 $A \rightarrow x$， 其中 $A \in V$， $x \in (V \cup T)^*$
* 之所以是「上下文無關」，是因為無論變數 $A$ 在字串中的任何一個位子，這樣的變換都可以成立
* 根據以上定義，上下文無關文法可以產生的語言為 $L(G) = \{ w: S^* \Rightarrow w, w \in T^* \}$
* 線性文法（右手邊只有一個變數的形式文法）為和正則文法都屬於上下文無關文法，他們是上下文無關文法的子集
* 一個語言 $L$ 是上下文無關的，若且唯若存在一個上下文無關文法 $G$， 使得 $L = L(G)$
* 舉例： $L(G) = \{ a^nb^n : n \geq 0\}$ 是上下文無關語言，其對應的上下文無關文法是
$$
\begin{equation}
\begin{split}
&S \rightarrow aSb \\
&S \rightarrow \lambda
\end{split}
\end{equation}
$$
* 舉例： $L(G) = \{ a^{2n}b^m : n \geq 0, m \geq 0\}$ 是上下文無關語言，其對應的上下文無關文法是
$$
\begin{equation}
\begin{split}
&S \rightarrow AB \\
&A \rightarrow aaA \\
&A \rightarrow \lambda \\
&B \rightarrow Bb \\
&B \rightarrow \lambda \\
\end{split}
\end{equation}
$$
* 一個非線性的上下文無關文法，其箭頭的右邊可能會有兩個以上的變數，所以可以產生出兩種以上的推導過程 (derivation)
* 以上面第二個舉例為例：
* Leftmost derivation （每次先換最左邊的）: $S \rightarrow AB \rightarrow aaAB \rightarrow aaB \rightarrow aaBb \rightarrow aab$
* Rightmost derivation （每次先換最右邊的）: $S \rightarrow AB \rightarrow ABb \rightarrow Ab \rightarrow aaAb \rightarrow aab$

### Derivation Tree

* **推導樹 (Derivation Tree)** 是一棵有序樹，其中的每一個父節點都是某文法的產生式規則的左手邊，而這個父節點的子節點們都是這個產生式文法的右手邊
> Figure 1. 一棵推導樹
* 給定一個上下文無關文法 $G = (V, T, S, P)$， 則存在一棵有序樹是 $G$ 的推導樹，若且唯若以下性質成立：
1. 這棵樹的根節點是 $S$
2. 每個葉子都屬於 $T \cup \{ \lambda \}$
3. 每個內節點都屬於 $V$
4. 如果有一個節點 $A \in V$， 且他的子節點包含 $a_1, a_2...$， 則 $P$ 當中必定存在一條規則是 $A \rightarrow a_1a_2...$
5. 如果一個節點是 $\lambda$， 則這個節點沒有兄弟節點
* 部份推導樹 (Partial derivation tree) 則擁有以下性質：
1. 根節點不一定要是 $S$
2. 每個葉子都屬於 $V \cup T \cup \{ \lambda \}$
3. 其餘三點同一般的推導樹
* 一個上下文無關文法的推導樹的葉子節點組成的字串會屬於該上下文無關文法描述的語言，而他的部份推導樹的葉子節點組成的字串會是這個文法的句型 (sentential form)
* 在不曖昧的 (unambiguous) 非線性文法中，推導的順序並不會影響最終產生的推導樹的長相
> Figure 2. 部份推導樹和完整的推導樹

## Parsing Context Free Grammar

> Figure 3. 一個文法解析的過程
* 文法解析(Grammar Parsing)， 指的是給定一個 $w \in L(G)$， 試著找出以 $G$ 推導出此字串的推導過程
* input: 一個字串 $w$， 以及一個文法 $G$
* output: 一個推導過程 (Derivation)

### Exhaustive Search Parsing / Brute Force Parsing

* 文法解析當中最基本的一個方法，就是暴力列舉所有可能推導過程，並且看看有沒有任何一個可以接受給定的字串
* 如果 input 是沒有任何限制的上下文無關文法
* 由 $S$ 開始，把 $P$ 當中的每一條規則都試過一遍，刪除不可能的選項，得到一個句型後，再把句型當中的所有變數，用 $P$ 當中的每一條規則都代換看看…，以此類推，直到推導出 $w$ 為止
* 很沒有效率
* 如果 $w$ 根本不在 $L(G)$ 當中，這個演算法很有可能不會終止
* 如果 input 是沒有 lambda-production （$A \to \lambda$） 和 unit-production （$A \to B$） 的文法
* 在這種文法中，每一步的代換 (Phase) 都會使句型的長度至少增加一個字，所以最多只需要 $2|w|$ 次的代換，就可以確定能不能推導出 $w$
* 從 $S$ 開始，以 $P$ 當中的規則不停代換，直到得到有 $|w|$ 個變數的句型後，再繼續根據 $P$ 當中的規則，將所有的變數全部替換成字母，最多只要 $|2w|$ 次的代換就可以換出 $w$。
* 第一次的代換 (Phase 1) 最多有 $|P|$ 種選擇，第二次的代換 (Phase 2) 最多有 $|P|^2$ 種選擇…， 第 $2|w|$ 次代換最多有 $|P|^{2|w|}$ 種選擇，所以解析的時間複雜度約為 $|P| + |P|^2 + ... + |P|^{2|w|} = O(|P|^{2|w|+1})$， 相當的久
* 對於任意的上下文無關文法，其實是存在一個解析演算法，可以在 $|w|^3$ 的時間之內解析出 $w$ 的推導過程的。但這是一個相當複雜的議題，因此留至編譯原理再進行說明。
* 如果 input 是 Simple Grammar， 即對於所有的 $A \rightarrow ax$， $(A,a)$ 這樣的 pair 在整個 $P$ 當中只會出現一次（意思就是說，右手邊第一個字是 $a$ 的規則只有一個），這樣的文法
* 則在每一次的轉換當中，都只有一個產生式規則可以選擇
* 因此解析的時間複雜度只要 $O(|w|)$， 快達線性時間

## Normal Form of Context Free Grammar

* 在暴力列舉的過程當中，我們可以觀察到，如果一個文法當中存在以下的產生式規則，就會導致列舉變得沒有效率
* $\lambda$ - Production: 型如 $A \Rightarrow^{*} \lambda$ 的規則，這會讓推導過程中的字串長度變短
* Unit Production: 型如 $A \rightarrow B$ 的規則，這會讓推導過程中字串的長度一直維持不變
* Useless Production: 根本就走不到的規則，或是永遠都無法換到只剩terminal的規則
* 如果可以把這些規則都去掉，那麼在解析文法時的效率就會好很多

### Methods for Transforming Grammars

* 已知：給定一個文法 $G = (V, T, S, P)$， 內含產生式規則 $A \rightarrow x_1Bx_2$ 以及 $B \rightarrow y_1\ |\ y_2\ |\ ...\ |\ y_n$。 若取另一個 $\hat{G} = (V, T, S, \hat{P})$， 其規則為 $G$ 的規則中刪除 $B \rightarrow y_1\ |\ y_2\ |\ ...\ |\ y_n$， 並將 $A \rightarrow x_1Bx_2$ 取代為 $A \rightarrow x_1y_1x_2\ |\ x_1y_2x_2\ |\ ...\ |\ x_1y_nx_2$， 則 $L(G) = L(\hat{G})$
* 根據以上定理，可以將上述三種不好的規則代換掉
* $\lambda$ - Production
* 把所有會換出 $\lambda$ 的變數都刪掉，並且把原本需要由該變數替換的地方都用 $\lambda$ 填入，產生新的規則
* 舉例： $S \rightarrow aS_1b$， $S_1 \rightarrow aS_1b\ |\ \lambda$ 可以被替換成 $S \rightarrow aS_1b\ |\ ab$， $S_1 \rightarrow aS_1b\ |\ ab$
* Unit Production
* 先把原本的語法分成是 unit production 以及不是 unit production 的兩類，保留前者，將後者替換成所有可能的 terminal 字串，產生新的規則
* 舉例：$S \rightarrow Aa\ |\ B$， $B \rightarrow A\ |\ bb$， $A \rightarrow a\ |\ bc\ |\ B$， 可以如下替換
* Useless Production
* 先去除所有會產生無限循環的規則，再移除所有走不到的規則
* 在做文法的轉換時，應該先去除 $\lambda$-production， 再去除 unit production， 再去除 useless production， 才可以避免已經去除的類型在下一步的轉換之後又重新出現的情況
* 但僅僅是去除掉文法中這些不好的產生式規則，產生的推導樹還是不夠容易解析。如果可以讓推導樹有一些特殊的結構，就可以很有效的提升解析的效率

### Chomsky Normal Form (CNF)

* 在 CNF 中，所有的產生式規則只能是 $A \rightarrow BC$ 或是 $A \rightarrow a$ 這兩種形式
* 由 CNF 文法產生出來的推導樹一定會是二元樹，且樹高一定會是 $2|w| - 1$， 也就是說，使用 CNF 產生長度為 $|w|$ 的字串時，恰好需要 $2|w|-1$ 次的推導
* 所有的上下文無關文法都可以很簡單的得到等價的 CNF 形式，步驟如下：
* 先去除所有的 $\lambda$-production 和 unit production
* 對於 $T$ 當中的所有元素，都新增一個變數 $T_t$， 以及一條規則 $T_t \rightarrow t$
* 把原本規則中所有的 terminal 全部替換成對應的變數 $T_t$
* 把原本規則中，右手邊長度超過 2 個變數的規則遞迴縮短到只剩兩個，舉例： $A \rightarrow BCD$ 可以替換成 $A \rightarrow BV_1$， $V_1 \rightarrow CD$

### Greibach Normal Form

* 在 GNF 中，所有的產生式規則只能是 $A \rightarrow aX$ 的形式（一個 terminal 後接 0 到多個變數）
* GNF 文法在解析上效率很好
* 所有的上下文無關文法都可以找到一個等價的 GNF 形式，但是並沒有如 CNF 那樣快速且簡單的轉換演算法

## A Membership Algorithm for CFGs*

由於 CNF 的特殊長相，讓他可以很快速的解析出一個字串是不是屬於該文法，該演算法稱為 **CYK 演算法**。
* 是一個動態規劃演算法
* 輸入為一個 CNF 文法 $G$， 以及一個字串 $w$， 輸出為 $w$ 是否可由 $G$ 產生
* 先窮舉所有 $w$ 中長度分別為 $1,2,...,|w|$ 且相鄰的子字串
* 從長度為 $1$ 的子字串開始檢查他可能是由哪一條規則產生出來的，並且記錄下來
* 檢查長度為 $k$ 的子字串，可能是由長度為 $1$ 與 $k-1$， 或由 $2$ 與 $k-2$… 的哪些字串藉由產生式規則生成的，並且記錄下來
* 檢查長度為 $|w|$ 的字串（即 $w$ ），如果該字串可以由 $S$ 產生，代表 $w$ 屬於 $G$， 反之則否
* 由於檢查每一條子字串最多只需要 $|w|$ 時間，總共只有 $\frac{|w|^2}{2}$ 個子字串要檢查，因此 **CYK 演算法的時間複雜度快達 $O(|w|^3)$， 是多項式時間**
>Figure 5. 由 CYK 演算法可以得知，字串 $aabbb$ 屬於此文法

## Ambiguity of Grammars

* 在一個上下文無關文法 $G$ 中，如果存在一個字串 $w \in L(G)$， **可以對應出兩種以上的最左 / 最右推導過程，即可以對應出兩棵以上不同的推導樹**，我們就說這個文法是**曖昧的 (Ambiguous)**
* 舉例： 文法 $E \rightarrow E + E\ |\ E * E\ |\ (E)\ |\ a$ 是曖昧的，因為字串 $a + a * a$ 可以有兩種不同的最左推導過程
* $E \Rightarrow E + E \Rightarrow a + E \Rightarrow a + E * E \Rightarrow a + a * E \Rightarrow a + a * a$
* $E \Rightarrow E * E \Rightarrow E + E * E \Rightarrow a + E * E \Rightarrow a + a * E \Rightarrow a + a * a$
> Figure 6. $a + a * a$ 可以對應到兩棵不同的推導樹
* 在編譯程式語言的時候，曖昧的文法是我們不樂見的
* 以上面例子來說，將 $a = 2$ 代入，左邊的推導樹產生的結果是 $2 + (2 * 2) = 2 + 4 = 6$， 右邊的推導樹產生的結果則是 $(2 + 2) * 2 = 4 * 2 = 8$， 很顯然只有左邊是對的
* 在設計程式語言的文法時，我們希望可以**移除所有的曖昧狀況**。以上述情況為例，透過**增加運算子之間的優先序 (Priority)**， 就可以避免誤解析的狀況發生
> 增加運算子之間的Priority，就可以讓所有的字串都對應到唯一的一個推導樹
* 但是有些文法天生就是曖昧的 (Inherent ambiguity)， 沒有辦法透過增加優先序的方式消除
* 舉例： 語言 $L = \{a^nb^nc^m\} \cup \{a^nb^mc^m\}$， 其對應出來的文法是曖昧的
* 其文法為
$$
\begin{equation}
\begin{split}
&S \rightarrow S_1\ |\ S_2 \\
&S_1 \rightarrow S_1c\ |\ A \\
&A \rightarrow aAb\ |\ \lambda \\
&S_2 \rightarrow aS_2\ |\ B \\
&B \rightarrow bBc\ |\ \lambda
\end{split}
\end{equation}
$$
* 字串 $a^nb^nc^n$ 在這個文法當中必定會對應到兩棵不同的推導樹，而這是無法透過文法轉換消除的
> $a^nb^nc^n$一定會對應出兩棵不同的推導樹

## Context Free Grammars and Programming Languages

* 現今世上大部分的程式語言幾乎都是以上下文無關文法實作的，因為上下文無關文法有足夠強的表達力，可以構造出演算法所需要的敘述句，但同時也夠容易解析，使得編譯的過程不會耗時太久
* 編譯器的運作過程可以分解為以下幾個步驟
* 詞法分析器 (Lexer): 將純文字解析唯一個一個的標記 (token)
* 解析器 (Parser): 透過文法將一串一串的標記轉換成一棵的推導樹
* 組語產生器 (codegen): 將推導樹中的每一個節點 替換成對應的變數或常數，將每一棵子樹轉換成對應的組合語言，最後產生出 object file
* 巴科斯範式 (Backus-Naur Form, BNF) 是設計程式語言時最常實作的文法類型
* LL 解析器和 LR 解析器，可以有效的在線性時間內完成解析