# 【Compiler】 Ch2. Languages and Their Representations

## Alphabets and Languages
* 如何定義一個"語言"？這邊先定義語言的"字母集"。
* 字母集(alphabet)是任何有限符號的集合，例如：
* 英文alphabet {A, B, C..., Z}
* 希臘alphabet {α, β, γ..., ω}
* 二元alphabet {0, 1}
* 而sentence就是從alphabet的符號中組合出的有限string(這邊的sentence不是句子是單字!)
* 空的sentence習慣用 є 表示。
* 如果$V$是一個alphabet，則
* $V^*$為在$V$裡面的所有sentence。
* $V^+=V^*-\{\epsilon\}$(不包含空字串的意思)
---
* 有了上述的定義，我們到底如何定義一個Language？
* 我們必須用有限的東西去定義一個無限的語言
* 兩種方法：
* 給一個演算法，丟入sentence時可以回傳它在該語言內或不是。
* 給予一個語法，能產生所有該語言內的sentence。

## Grammars

* 先給個語法範例：
* 
* 看不懂沒關係，下面帶你來了解Grammar

### Formal Notation of a Grammar

* Grammar有`4`個元素：
* Nonterminals
* 不在alphabet中的符號，衍生符號，如範例中的`<sentence>` `<adjective>`等
* Terminals
* 與Nonterminals，最原始的符號，如範例中的`The` `little` `boy`等
* Productions
* 符號(Terminals和Nonterminals)的轉換關係，如範例中的`<sentence> -> <noun phrase><verb phrase>`等
* Start Symbol
* 開始符號，如果輸入的terminal最後可以透過Productions轉換為Start Symbol，表示該輸入屬於該語言。例如範例中的`<sentence>`(在Productions或parse tree的最上面)
---
* 使用數學的方式來表達：
* $G = (V_N, V_T, P, S)$
* $V_N$: nonterminals
* $V_T$: terminals ($V_N \bigcap V_T = \phi, V_N \bigcup V_T = V$)
* $P$: productions, $\alpha \rightarrow \beta \in P$
* $S$: start symbol
* 習慣上nonterminals會用大寫字母表示，而$V_T$是小寫。

### Derivation

* Derivation(推導)指將productions左側符號變為右側符號的動作。
* 例如： $\alpha \rightarrow \beta \in P$ 且 $\gamma, \delta \in V$，則$\gamma \alpha \delta \Rightarrow \gamma \beta \delta$。
* 其中我們可以說$\gamma \alpha \delta$ derives $\gamma \beta \delta$。
* 如果有一段連續的Derivation，可以用*表示：
* 如果$\alpha_1 \Rightarrow \alpha_2 \Rightarrow ... \Rightarrow \alpha_m$ 則可寫為 $\alpha_1 \overset{*}{\Rightarrow} \alpha_m$
* $L(G) = \{w|w \in V^*_T \wedge S \overset{*}{\Rightarrow} w \}$
* 表示使用語法G的語言L
* 如果兩個語法$G_1$ $G_2$是相等的，則$L(G_1) = L(G_2)$
---
範例問題
$G = (V_N, V_T, P, S)$
$V_N = \{S\}, V_T = \{0, 1\}, P = \{S \rightarrow 0S1, S \rightarrow 01\}$
根據以上語法，請描述L(G)為何？

答案
L(G) = $\{0^n1^n\}$

### Types of Grammars

* 在這邊將介紹四種不同等級的Grammar，先大致上有個印象就可以了。
* 越下面的限制越高。
* 給予語法$G = (V_N, V_T, P, S)$
1. Type 0 grammar
* 沒有任何限制。
2. Type 1 grammar (context-sensitive grammar)
* 必須符合$\alpha \rightarrow \beta \in P, |\alpha| \leq |\beta|$
* 也就是說，Derivation不會讓句子變短。
3. Type 2 grammar (context-free grammar)
* 必須符合$\alpha \rightarrow \beta \in P, |\alpha| = 1, \beta \ne \epsilon$
* 也就是說，production的左側只能有一個符號。
4. Type 3 grammar (regular grammar)
* 所有production都只能是
1. $A \rightarrow aB$
2. $A \rightarrow a$

###### tags: `compiler` `note`