電腦如何判讀高階語言？形式語言
如果你想要學編譯器的相關原理，必修形式語言的邏輯。
1950 年代的電腦程式都還是機器語言，也就是所有的指令只能用 0 與 1 的排列組合來表示，這使得寫程式、除錯、修改程式都相當浪費時間。
美國電腦科學家約翰·巴克斯（John Backus）當時在 IBM 工作，後來向老闆提出：應該開發比較接近人類語言的高階語言，更方便編程。
要怎麼讓電腦辨識人類的語言特性呢？
這就要用到形式語言啦！在數學、邏輯和電腦科學領域中，形式語言（Formal language）是用精確的數學或機器、可處理的公式定義的語言。
形式語言的研究始於 20 世紀初，而把形式語言用於模擬自然語言是 1950 年代左右。
當時，許多數理語言學家致力於用數學方法研究自然語言的結構，尤其是 1946 年第一台電腦 ENIAC 出現以後，人們很快想到能用電腦來作自然語言的機械翻譯。
可是這項工作在取得一些初步的成功以後便停滯不前，翻譯的質量很難提高，主要是因為當時對自然語言結構的理解太表面化。
1956 年，喬姆斯基發表了用形式語言方法研究自然語言的第一篇文章，稱為「轉換生成文法」。
轉換生成文法繼續發展喬姆斯基先前提出的普遍文法理論 (Universal Grammar)。喬姆斯基認為，若普遍文法是正確的話，人類的大腦應該能夠系統性地生產文法正確的字句。
因此他嘗試利用轉換生成文法，來描述生產正確文法字句的過程。
1957 年，IBM 的約翰．巴克斯等人發明了高階語言 Fortran 語言與編譯器。人們發現巴克斯使用的語法幾乎就是喬姆斯基發表的文法理論。
從而成了形式語言被廣泛應用於程式語言的濫觴，使程式語言設計成為現代電腦科學的一個重要分支。
—
在數學或電腦科學當中，形式語言就是「一個符號字串的集合、加上其所對應規則的集合。」
（In mathematics and computer science, a formal language is a set of strings of symbols together with a set of rules that are specific to it.）
所以我們在分析語言時，需要將語言以數學模型的抽象形式表達。比如機器翻譯、語音識別等，然後利用計算機去針對該數學模型求解。
來看看語言要如何用數學式來表達吧！
什麼是語言？字串所成的集合
a, b, 3, *, %, w, 0… 這些符號都叫做一個「符號」或「字元」。把字元集合起來可以變成「字串」，比如變成：abcde，這就叫「含有五個字元的字串」。
喬姆斯基對語言的定義方法是：給定一組符號（有限多個），稱為字母表，以 ∑ 表示之。
又以 ∑* 表示由 ∑ 中字母組成的所有字串的集合。則 ∑* 的每個子集都是 ∑ 上的一個語言。
例如，若令 ∑ 為 26 個字母加上空格和標點符號，則每個英語句子都是 ∑* 中的一個元素，所有合法的英語句子的集合是 ∑* 的一個子集，最後構成一個語言。
喬姆斯基的語言定義方法為人們所公認，一直沿用下來。
將上述理論以數學表達：
假設 ∑ 為一個有限的非空符號所成的集合，稱為符號集 (alphabet)。
∑ 的次方定義成：
- ∑1 = ∑
- ∑n+1 = { xy | x ∈ ∑, y ∈ ∑n }
（ $latex \sum^{n}$ 表示佈於 $latex \sum$ 的 n 個符號或字母的串連 (concatenation) ）
—舉例—
$latex \sum = \left\{ 0, 1 \right\}$，則 $latex \sum^{2} = \left\{ 00, 01, 10, 11 \right\}$
$latex \sum = \left\{ a, b, c, d \right\}$，則 $latex \sum^{3}$ 包含的字串個數為 $latex 4^{3} = 64$，例如 aaaa, abad, bcda 等皆為 $latex \sum^{3}$ 的字串。
我們也可找到由一個符號集，來構成一個語言：
假設 $latex \sum$ 為一個符號集，若 $latex A \subseteq \sum^{*}$ 則稱 A 為佈於 $latex \sum$ 的一個語言。( A is a language over $latex \sum$ )
—舉例—
$latex \sum = \left\{ a, b, c \right\}$
- $latex L{1} = \left\{ a, ab, ac, bc, abc, acb, cab \right\}$
- $latex L{2} = \left\{ abcba, bcbca \right\}$
- $latex L{3} = \left\{ \right\}$
- $latex L{4} = \left\{a^{i}cb^{i} \mid i\geqslant 1 \right\}$
則 $latex L{1}, L{2}, L{3}, L{4}$ 均為佈於 $latex \sum$ 的語言。
轉換生成文法：生成文法正確的語言
喬姆斯基提出了「轉換生成文法」(Transformational-Generative Grammar) 作為描述形式語言的方法。比如：
- 語言 ɑ*, 意指包括了 a, aa, aaa, aaaa… 等至少包含一個 a 的字串。
- 其文法為 {S → ɑ, S → ɑS}
這個文法由兩條規則所產生。
每一步轉換（推導），都用一條轉換規則的右邊、替換它的左邊。
S 是出發點，代表語言 ɑ 中任何一個可能的句子。
例如，句子 ɑɑɑɑɑ 可以這樣推導出來：S → ɑS → ɑɑS → ɑɑɑS → ɑɑɑɑS → ɑɑɑɑɑ。
推導共分五步。前四步用了第二條規則，第五步用了第一條規則。
按這個辦法，可以生成 ɑ* 中的所有句子，即整個 ɑ* 語言。
——A language could be generated by the grammar.
note: 文法四要素組成：起始, 非終端, 終端, 產生規則
嚴格來說，喬姆斯基將「轉換生成文法」定義為四個要素：
G 為一個文法，$latex G = \left ( S, N, T, P \right ) $
(1) T 為終端符號（有限集合），表示不能再以其他符號代替
(2) N 為非終端符號，表示可以再以其他符號來替代。而 N 與 T 須具以下的關係：N∩T=φ
(3) S 為起始符號，表示文法推演之步驟由 S 開始，S ∈ N
(4) P 為文法產生規則的集合
(a) P 中的每個規則，具有 α → β 的形式。
(b) 其中 α ∈ (N U T)* – T*, β ∈ (N U T)*
(c) α ∈ (N U T)*-T* 代表 α 由非終端符號與終端符號所組成的任意長度之字串，但至少包含一個非終端符號。
(d) β ∈ (N U T)* 代表由 β 非終端符號與終端符號所組成的任意長度之字串。
note: 文法 G 能用來生成語言 l(g)
$latex G = \left ( S, N, T, P \right ) $ 為一個文法。
可由 S 推導出的所有字串、所成的集合，稱為 G 生成的語言 (Language generated by G)，記作 L(G)。
數學式記為：$latex L(G) = \left\{ \alpha \in T^{*} \mid S \overset{*}{\rightarrow} \alpha \right\}$
文法的分類—喬姆斯基體系中的四型文法
根據 P 中的產生規則 a → β 的特點，可以將形式文法及其產生的形式語言分類，構成形式語言譜系，也被稱為「喬姆斯基譜系」。
在形式語言的理論中，主要研究四類型的文法、和其所生成的語言（也是現在電腦科學程式語言設計的重點研究項目）：
假設 $latex G = \left ( S, N, T, P \right ) $ 為一個文法：
(1) 0 型文法 (Type-0 Grammar)
每個推論規則 $latex \alpha \rightarrow \beta$ 無任何限制。
(2) 1 型文法 (Type-1 Grammar)
與上下文有關文法 (Context-Sensitive Grammar)，其文法產生規則必須滿足：
α → β ∈ P，其中 |α| ≤ |β\
規定文法產生規則，左方的符號長度不得大於右方的符號長度。
(3) 2 型文法 (Type-2 Grammar)
與上下文無關文法 (Context-Free Grammar)，又稱為 BNF 文法。（Backus Normal Form，由開發 Fortan 語言的 John Backus 和 Peter Naur 首先引入、用來描述電腦語言語法的符號集）
文法產生規則必須滿足：
α → β ∈ P，其中 α ∈ N, β ∈ (N U T)* – {λ} （λ表示空字串）
規定文法產生規則，左方僅允許長度為 1 之非終端符號。
因為 α 符號可以被 β 字串自由替換，而無需考慮 α 符號出現的上下文，故稱為與上下文無關。由於此語法良好的表達能力，幾乎所有程式語言的語法都是用此語法定義。
(4) 3 型文法 (Type-3 Grammar)
正規文法 (Regular Grammar)。
規定文法產生規則，左方僅允許長度為 1 之非終端符號，右方僅允許長度為 1 之終端符號。
也被應用為「正規表達式」，通常用來定義檢索模式。
從 Type-0 到 Type-3 的四種文法、依次擁有越來越嚴格的產生式規則，同時文法所能表達的語言也越來越少。
Type-0 文法必包含 Type-1、Type-2、Type-3；Type-1 文法必包含 Type-2 和 Type-3… 以此類推。
編譯器在編譯時，會對程式碼中的每一條敘述，按照先後順序均做一次之轉換處理、產生對應之目的碼。
這種轉換處理的工作，必須完全遵守該程式語言所規定的文法規則 (grammar rules)。
不同程式語言的文法規則是不相同的。若撰寫程式時違背了程式語言的文法規則，編譯時會發生文法錯誤之訊息。
如何讓電腦判斷一段字串是否屬於合法的句子？
給定一個字串，電腦需要判定這個字串，是否屬於我們給定的一個語法 G 、所產生的語言L(G) 。
也就是說，電腦需要判定一個字串是不是屬於這個集合。
在轉換生成語法理論中，一個句子要麼是「正確的」，要麼是「不正確的」。
換句話說，轉換生成語法的規則是一個算法，會對一個句子的合法度（符合語法 Syntax 的程度）進行判斷，但只會得出「是」或「否」的結果。
當我們在寫程式時遇到 Syntax Error 訊息，代表電腦判斷不過你這個句子屬於它看得懂得語言。
要做到這一步，是一個非常難解的問題。實際上涉及到語法分析的問題——給你一個句子，如果這個句子是屬於這個語言的句子的話，那麼你要給出它被構造而出的過程。
這個構造的過程，與我們在形式系統當中進行證明這是一樣的——假設這個命題是正確的，那你要用我一系列的公式、給出一個證明，說明命題是正確的。
同樣的，如果想判定這個句子是屬於這個語言的（命題是正確的），你也必須要給出一個構造的過程——如何用這個產生式一步一步地推出來（證明過程）。
這就叫識別和判定的過程。
一般來講，要讓機器要能判定喬姆斯基的各種類型語法，是一個難解的問題。
好消息是，科學家的確研究出了幾種不同的機器（事實上是數學模型），能拿來判定語言。但因為機器的能力依其強弱不同，所以能判斷的文法範圍也不同：
(1) Type-0 文法產生的語言，能被圖靈機 (Turing Machine) 所辨識
(2) Type 1 文法所產生的語言可被線性限制自動機 (Linear Bounded Automata) 辨識
(3) Type 2 文法所產生的語言可利用推壓自動機 (Push Down Automata) 辨識
(4) Type 3 文法所產生的語言可利用有限狀態自動機 (Finite State Automata) 辨識
規則越嚴越好判定，需要的機器能力越弱。所以「圖靈機」是裡面最強的機器。
由於 Type-3 語言（文法）、也就是正規表達語言，是一個最嚴謹的語言，因此它可以透過一個比較簡單的識別機器來進行判定，也就是上面提到的「有限狀態自動機」。
下一集開始，就讓我們來為大家介紹，什麼是有限狀態自動機吧：）
-
後記補充
我們能使用文法來推導出語言，
並判斷一個字串是否屬於該語言：
G 為一個文法，$latex G = \left ( S, N, T, P \right )$
(1) S 為起始符號，$latex S \in N$
(2) $latex N = \left\{ S, A \right\}$
(3) $latex T = \left\{ a, b\right\}$
(4) $latex P = \left\{ S \rightarrow bS, S \rightarrow aS, A \rightarrow bA, A \rightarrow b \right\}$
找出此文法的語言 L(G) ：
G 中 由 S 開始的推導過程為——
其中 $latex n\geqslant 0, m\geqslant 1$，所以由 G 所導出的語言為 $latex L(G) = \left \{ b^{n}ab^{m-1} \mid n\geqslant 0, m\geqslant 1 \right \}$
判斷：字串 bbabb 是否屬於這個語言？
推導過程：
S 可導出字串 bbabb，故屬於這個語言。
我們也可以設計一個文法，來生成所指定的語言。
設計一文法，能生成語言 $latex L= \left \{ a^{i}b^{i} \mid i, j \geq 1, i \neq j \right \}$
設計過程：
假設 $latex L{1} = \left \{ a^{i}b^{i} \mid i, j\geq 1, i > j \right \} , L{2} = \left \{ a^{i}b^{i} \mid i, j\geq 1, i < j \right \} $
令 $latex G{1} = \left ( S, N{1}, T, P{1} \right )$ 為生成 $latex L{1} $ 的文法
$latex T = \left\{ a, b\right\}, N = \left\{A, B \right\} $
- A 為起始符號，表示 a 出現的個數比 b 出現的個數至少多一個。
- B 表示 a 出現的個數與 b 出現的個數相同。
因為 a 出現的個數比 b 出現的個數至少多一個可分成兩種情形，一種為剛好多一個、一種為至少多兩個。
- 剛好多一個： A → aB
- 至少多二個：A → aA
所以 $latex P{1} $ 包含以下推論規則：
A → aA, A → aB, B → aBb, B → ab
令 $latex G{2} = \left ( S, N{2}, T, P{2} \right ) $ 為生成 $latex L{2} $ 的文法
$latex T = \left\{ a, b \right\}, N = \left\{C, B \right\} $
- C 為起始符號，表示 a 出現的個數比 b 出現的個數至少少一個。
- B 表示 a 出現的個數與 b 出現的個數相同。
a 出現的個數比 b 出現的個數至少少一個可分成：剛好少一個、至少少兩個，因此 $latex P{2} $ 包含以下推論規則：
C → Bb, C → Cb, B → aBb, B → ab
欲求的生成語言 $latex L = L{1} \cup L{2}$ ，其文法 $latex G = \left ( S, N, T, P \right )$ 。令：
- $latex N = N{1} \cup N{2}$
- $latex P = P{1} \cup P{2} \cup \left\{ S \rightarrow A, S \rightarrow C \right\} $
- P 包含下列推論規則：
- S → A, A → aA, A → aB, B → aBb, B → ab, S → C, C → Cb, C → Bb
此即為生成語言 L 的文法 G。
