編譯程式概論
===
Compiler(編譯器)的作用是將Source Language轉換成Target Language
* Source Language: C, C++, C# ...
* Target Language: Assembly

好的Compiler必須能辨識合法(不合法)的程式(Source Language)並產生出正確的程式(Target Language)

編譯器結構
===
編譯器主體分成兩大結構：
* Front-End(前端): 將整體Source Program切成片段後分析其內容，產出Intermediate Representation(中間語言)
* Back-End(後端): 將IR重新處理成Target Program，依照不同情況提供更有效率的優化

在編譯程式概論這堂課中，主要著重在Front-end的原理與實現

Front-End結構
---
Front-End將Source Program轉換成IR過程中，需要經過以下步驟:
* Lexical Analyzer(詞法分析): 輸入整段Source Code，將其分段成Lexeme(詞位)，將Lexeme進一步轉換成Token(記號)
* Syntax Analyzer(語法分析): 輸入Token Stream，將其建立成具有相依關係的Abstract-Syntax Tree(抽象語法樹)
* Semantic Analyzer(語義分析): 對Abstract-Syntax Tree進行解釋，轉換為Annotated Abstract-Syntax Tree
* Intermediate Code Generator: 將Annotated Abstract-Syntax Tree轉換成3-address Code(三位址碼)

Front-End過程中不對Source Program進行語義上的改變，不涉及到優化及運算上的處理。

Back-End結構
---
Back-End將IR轉換為Target Program過程中，需要經過以下步驟:
* Machine-Independent Code Optimizer: 對IR進行優化，將可以預先處理的計算先處理好，簡化操作行數
* Code Generator: 將優化後的IR以Target Language表示，通常為Assembly
* Machine-Dependent Code Optimizer: 對個別CPU進行定製化調整，優化對Register操作的效率

Back-End過程中著重於對Code的優化，對於Program的效率一般而言有顯著的效果。

快速流程
===
Lexical Analyzer
---
要讓Compiler了解Code內容，需要先對Code進行切割，使Compiler了解哪些字的組合是指同一個東西。

首先先將輸入的Source Code以文字形式輸入到Scanner，將這些文字分組產生有意義的字段，被稱為Lexeme(詞位)，此時會將空格及註釋給拋棄掉。

>輸入一行代碼 number = initial + rate * 60
>其Lexeme為[number, =, initial, +, rate, \*, 60]共7個

將每個Lexeme轉換成下列格式，並且將Lexeme進行分類整理到Symbol Table:
**Lexeme → <token-name, attribute-value>**
token-name: 將Lexeme進行分類後的類型
attribute-value: 其在Symbol Table中的位置

>將前面的Lexeme轉換為Token後，Token stream會是以下形式：
><id, 1> <=> <id, 2> <+> <id, 3> <\*> <60>

| Number | Name |
|:------:|:-------:|
| 1 | number |
| 2 | initial |
| 3 | rate |

利用Regular Expression(正則表示式)能檢測到Lexical Error例如變數名為數字開頭或者是非法字符的情況
> 1num = <variable, 1>
> !@\#* = <variable, 2>

Syntax Analyzer
---
將先前處理過的Token stream丟入Parser(解析器)後，Parser會將其建立成Syntax Tree:

對Syntax Tree進行檢查，可以檢測符號配對問題的Syntax Error:
> number = ( 1 + 2;

也可以檢查到部分的Static Semantic Error，例如沒有被宣告或者重複宣告的變數:
> int a = 1;
> int a;

Semantic Analyzer
---
對Syntax tree進行Type Checking及Type Conversion:
上圖中，檢測操作符\*左右的兩個Token，左邊為Float，右邊為Int，此時會將右邊轉換成Float使\*可以執行:

可以檢測到Token與操作符完全不適配的Semantic Error(即使Type Converse):
> int number = 1 + "word"
> length(new Class a)

Intermediate Code Generator
---
將上圖依照樹狀關係轉換成3-Address code，3-Address Code的形式為:
* 最多存在三個操作數
* 除了"="以外，最多存在一個操作符

轉換後會成為下列格式：
t~1~ = itof(60)
t~2~ = id~3~ * t~1~
t~3~ = id~2~ + t~2~
id~1~ = t~3~

Optimizer
---
為了提高程式運行的效率與降低記憶體的使用，會對IR中已確定的內容進行簡化:
t~1~ = id~3~ \* 60.0
id~1~ = id~2~ + t~1~

經過簡化步驟後，操作量從原本的4次減少到2次

Code Generation
---
最後將3-Address Code進行轉換，由於Assembly具有完善的Atom Operation，通常都是轉換為Assembly，最後呈現成果如下：
LDF R~2~, id~3~
MULF R~2~, R~2~, #60.0
LDF R~1~, id~2~
ADDF R~1~, R~1~, R~2~
STF id~1~, R~1~

以上為整個Compiler的快速流程，此後章節為每個區塊的實行原理與過程。

Lexical Analysis
===
將文字轉換成Lexeme時，是藉由給定的Pattern形成的，Pattern是對於將Token歸類成一檔的判定規則，以下再對幾個專有名詞進行解釋：

* Symbol: 單一字符
* Lexeme(詞位): Symbol的組合
* Pattern(樣式): 將文字歸類為特定Token種類的規則
* Token(記號): 帶有其種類與編號的Lexeme
* Symbol Table: 將同種類Token進行編號的表格

其中Pattern的呈現方式通常為Regular Expression(正則表達式)
將文字轉換成Pattern指定的Token方法為Finite Automata(有限自動機)

String
---
首先要先引入第一個概念: String(字串)
* Alphabet: 字符的有限集合
* String: 由Alphabet元素組成的有限串列
* |S|: String S的長度
* ε: 串列為空的String

String有以下性質：
* xy: String y接到x後面
* εx = xε = x
* s^0^ = ε
* s^i^ = s^i-1^s
* s^1^ = s, s^2^ = ss, s^3^ = sss

對String有以下擷取方式(例如S = number)：
* Prefix: 從最後方擷取n位(n≥0)，例: number, num, ε
* Suffix: 從最前方擷取n位(n≥0)，例: number, ber, ε
* SubString: 進行任意Prefix與Suffix，例: number, umb, ε
* Subsequence: 進行任意的字串擷取或刪除，例:number, nme, ε
* 若在以上操作前加上Proper，則不包含自身與ε

Language
---
第二個要引入的概念為Language
* Language: 元素為String的可數集合(符合相同的Alphabet)

Language有以下操作:
* 聯集:L∪M = {s\|s∈L ∨ s∈M}
* 結合:LM = {st\|s∈L ∨ t∈M}
* L^0^ = {ε} (帶有空字串的集合)
* L~empty~ = {} (真-空集合)
* L^1^ = L
* L^i^ = LL^i-1^

其中有兩個需要特別解釋的是Kleene Closure與Positive Closure:
* Kleene Closure: L^\*^ = L^0^ ∪ L^1^ ∪ L^2^ ...
* 例: A^\*^ = {ε, A, AA, AAA...}
* Positive Closure L^+^ = L^1^ ∪ L^2^ ∪ L^3^ ...
* 例: A^+^ = {A, AA, AAA...}
* L^\*^ = L^+^ ∪ {ε}

利用Language，便能組出一定規律的String，例如:
L~1~ = {A, B, C, ..., a, b, c, ...}
L~2~ = {1, 2, 3, ..., A, B, C, ..., a, b, c, ...}
L~cid~ = L~1~L~2~^\*^
L~cid~為所有C語言中可定義的變數名集合(C語言不允許變數名首字為數字)

Regular Expression
---
利用Language，便可以創建Regular Expression的規則了

定義一個RE為r，則r為Language\(r\)的表示，RE有以下性質：
* ε是RE，L(ε) = {ε}
* 若a是一個Symbol，則a是RE，L(a) = {a}
* r|s是RE，L(r|s) = L\(r\)∪L(s)
* rs是RE，L(rs) = L\(r\)L(s)
* r^\*^是RE，L(r^\*^) = L\(r\)^\*^

RE的運算有優先級：
* \* > 結合(rs) > |

以下為幾個RE的例子：
* a|b: {a, b}
* (a|b)(a|b): {aa, ab, ba, bb}
* a^\*^: {ε, a, aa, aaa, ...}
* a|a^\*^b: {a, b, ab, aab, ...}
* a|b^\*^: {a, ε, b, bb, ...}
* (a|b)^\+^: {a, b, ab, aab, abb, aaaa, ...}
* ab^\*^(c|ε): {a, ac, abc, abb, abbbc, ...}

Regular Definition
---
若RE僅能使用symbol的話，構建Pattern上會變得非常繁複，因此我們可以創建一些Definition來簡化RE:
* Definition: **name → RE**
* d~1~ → r~1~
* d~2~ → r~2~
* ...
* d~n~ → r~n~

其中d~k~不能與Alphabet中元素與其他d~m~重名以免混淆
對於r~i~，可以使用d~1~\~d~i-1~作為其RE的構建，例如以下C identifier的RE:
letter → a|b|...|z|A|B|...|Z|_
digit → 0|1|2|...|9
cid = letter(letter|digit)*

除此之外，可以用一些簡寫來描述RE：
* r+ ≡ rr*
* r? ≡ r|ε
* \[abc\] ≡ a|b|c
* \[a-z\] ≡ a|b|...|z
* \[^ab] ≡ Alphabet集合 - \[ab\]
* \[^a-z\] ≡ Alphabet集合 - \[a-z\]

所以對於C identifier又可縮寫為:
letter → \[a-zA-Z\]
digit → \[0-9\]
cid = letter(letter|digit)*

以下為幾種Pattern的RE:
* 非負整數: 0|\[1-9]\[0-9]^\*^
* 正偶數: \[02468]|\[1-9]\[0-9]^\*^\[02468]
* 身分證字號: \[A-Z]\[12]\[0-9]^9^

RE的缺點
---
RE可以表達任何有限已確定次數或者單調無限可數的String串列，但只要牽涉到記憶性與非常數的表示，RE就會失效:
* {wcw, w為(a|b)^\*^)
* {a^n^b^n^,n≥0}

Finite Automata
===
Finite Automata(有限自動機)是一種機制，可以在有限次數的操作後從一個狀態抵達另一個狀態，此種性質使得其可以用來解釋RE

FA有以下要素:
* S: 狀態的有限集合，以節點作為表示
* Σ: Alphabet
* δ: 狀態與狀態之間的路徑，以有向連結作為表示
* S~0~: 起始狀態
* F: 結束狀態的有限集合，以兩層圓作為表示

上圖為RE (abc+)+的FA

運行FA時，必須從S~0~開始，依序讀取所求字串s的Symbol，依照δ的條件移動到下一個狀態，若沒有δ符合讀取的Symbol，則s∈L(RE)

當字串的所有Symbol皆被讀取，檢查此時是否處於F，是的話s∈L(RE)，否則反之。

下表為該FA的Transition Table:
| State | a | b | c |
|:-----:|:---:|:---:|:---:|
| 0 | {1} | ∅ | ∅ |
| 1 | ∅ | {2} | ∅ |
| 2 | ∅ | ∅ | {3} |
| 3 | {1} | ∅ | {3} |

Type of FA
---
FA有兩種類型: Deterministic FA(DFA)與Nondeterministic FA(NFA)
* DFA: 對於任意State S與Input Symbol a，最多存在一條標記為a的路徑可以離開S，不存在ε-Transition(存在標記為ε的路徑)
* NFA: 存在State S與Input Symbol a，多於一條標記為a的路徑可以離開S，或者是存在ε-Transition

所有的NFA都能轉換成DFA，該內容將於後面章節講解

Simulation of FA
---
DFA的模擬同前章節的方式，從S~0~開始依序讀取輸入symbol，直到讀取完畢或者中斷

NFA的模擬與DFA有一定不同，在進行模擬時需要考慮所有可能的Transition，任一情況最終停留在F便能確認S∈L(RE)

比如RE (a|b)^\*^abb的NFA模擬，在該NFA的Transition Table中可以發現在狀態0時，讀取到a有兩種Transition的可能，這種情況便需要將兩種可能都執行一遍

| State | a | b |
|:-----:|:------:|:---:|
| 0 | {0, 1} | {0} |
| 1 | ∅ | {2} |
| 2 | ∅ | {3} |

上圖為對此RE進行aabb的NFA模擬，只要可能的Transition中有能抵達Final State的情況，便可以聲明aabb∈(a|b)^\*^abb

若NFA中存在ε-Transition，便需要使用其他方法，因為對於任意symbol間，可能穿插不確定的ε
> abc ≡ ε^2^aε^3^bcε^1^

為了消除ε對Transition的不確定性，需要引入ε-Closure(ε-閉包):
* ε-Closure(T): 狀態T藉由0~n個ε-Transition可抵達的狀態集合

上圖為(a|b)^\*^abb的另一種NFA(帶有ε-Transition)

模擬該NFA時，從S~0~開始，讀取第一個Symbol前，需要先排除ε造成的影響:
> ε-Closure(0) = {0, 1, 2, 4, 7}

得出S~0~的ε-Closure後，從ε-Closure(0)對第一個讀取Symbol進行moveto操作:
* **moveto(set, input) = next_state**

moveto後得到的集合，都必須再對其進行ε-Closure，以確保不一定存在的ε能被消除

以下為aabb對於(a|b)^\*^abb的NFA模擬:
ε-Closure(0) = {0, 1, 2, 4, 7}
moveto(ε-C(0), a) = {3, 8} ==讀取字符a 2→3 7→8==
ε-Closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8}
moveto(ε-C({3, 8}), a) = {3, 8} ==讀取字符a 2→3 7→8==
ε-Closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8}
moveto(ε-C({3, 8}), b) = {5, 9} ==讀取字符b 4→5 8→9==
ε-Closure({5, 9}) = {1, 2, 4, 5, 6, 7, 9}
moveto(ε-C({5, 9}), b) = {5, 10} ==讀取字符b 4→5 9→10==
ε-Closure({5, 10}) = {1, 2, 4, 5, 6, 7, 10}

{1, 2, 4, 5, 6, 7, 10}為從S~0~開始，經過aabb後能抵達的所有狀態，此集合中只要包含F便能確定該字串屬於該RE

NFA to DFA
---
NFA有其模糊性，會在模擬時造成額外的計算量，因此我們會想要將NFA轉換成DFA，NFA轉換成DFA的方式為Subset Construction Algorithm(子集構建算法)，此演算法的概念其實與NFA模擬有一定相似處：
* 輸入: 一個NFA N
* 輸出: 一個DFA D需與N有同樣的Language
* 方法: 構建D的Transition Table

首先，需要對N求ε-Closure(0)，同樣以(a|b)^\*^abb為例:
ε-Closure(0) = {0, 1, 2, 4, 7}

現在我們將這個ε-Closure(0)的集合視為D的第一個State A，接下來對A進行所有可能Input Symbol的moveto，此例中可能的Input Symbol只有a與b:
moveto(A, a) = {3, 8}
ε-Closure({3, 8}) = {1, 2, 3, 4, 6, 7, 8}
此集合不存在於D的State，將其加入Transition Table並稱之為B
moveto(A, b) = {5}
ε-Closure({5}) = {1, 2, 4, 5, 6, 7}
此集合亦不存在於D的State，將其加入Transition Table並稱之為C

此時的Transition Table:
| D State | a | b |
|:-------:|:---:|:---:|
| A | B | C |
| B | | |
| C | | |

對B與C依序進行上述操作，若產生新的集合則加入到D的State，重複執行直到所有State對於a或b都有可移動的狀態或∅

| D State | a | b |
|:-------:|:---:|:---:|
| A | B | C |
| B | B | D |
| C | B | C |
| D | B | E |
| E | B | C |

上圖為(a|b)^\*^abb的DFA

Minimized DFA
---
RE所構建出來的DFA也不一定唯一，由D的Transition Table可見有重複的Transition關係，因此下一步就是將DFA轉換成Minimized DFA

首先需要構建π = {F, S-F}
* F: 已經被確定的狀態集合
* S-F: 還未被確定的狀態集合

將Final State先放入F，檢查所有元素數>2的集合，檢查其對所有Input Symbol的Transition，拆分舊的集合並建構新的集合，將同樣Transition的狀態放在一起，重複同樣的操作直到π再無變化

例如以下DFA的Transition Table，Final State為F與G:
| State | 1 | 0 |
|:-----:|:---:|:---:|
| A | B | C |
| B | A | D |
| C | F | E |
| D | F | E |
| E | F | G |
| F | F | F |
| G | F | G |

首先構建π = {{A, B, C, D, E}, {F, G}}，對各狀態進行檢查:
| State | 1 | 0 |
|:-----:|:---------------:|:---------------:|
| A | {A, B, C, D, E} | {A, B, C, D, E} |
| B | {A, B, C, D, E} | {A, B, C, D, E} |
| C | {F, G} | {A, B, C, D, E} |
| D | {F, G} | {A, B, C, D, E} |
| E | {F, G} | {F, G} |
| F | {F, G} | {F, G} |
| G | {F, G} | {F, G} |

{A, B, C, D, E} → {A, B}, {C, D}, {E}
{F, G} → {F, G}

π = {{A, B}, {C, D}, {E}, {F, G}}，再檢查一次:
| State | 1 | 0 |
|:-----:|:------:|:------:|
| A | {A, B} | {C, D} |
| B | {A, B} | {C, D} |
| C | {F, G} | {E} |
| D | {F, G} | {E} |
| E | {F, G} | {F, G} |
| F | {F, G} | {F, G} |
| G | {F, G} | {F, G} |

確認狀態不需要改變後，將每個子集視為一個狀態構建出新的Transition Table，D為Final State:
| State | 1 | 0 |
|:-----:|:---:|:---:|
| A | A | B |
| B | D | C |
| C | D | D |
| D | D | D |

Analysis of NFA and DFA
---
NFA的時間複雜度: **O(|U|^2^\*|x|)**
DFA的時間複雜度: **O(|x|)**
* |U|: NFA的狀態數
* |x|: Input的長度

NFA的ε-Transition會造成巨額性能損耗，時間複雜度遠遠劣於DFA

NFA的空間複雜度: **O(|U|^2^\*|Σ|)**
DFA的空間複雜度: **O(2^|U|^\*|Σ|)**
* |U|: NFA的狀態數
* |Σ|: Alphabet的元素數量

由於NFA轉換成DFA過程中，會產生大量的狀態，空間複雜度在|U|較大時DFA劣於NFA

Syntax Analysis
===
在Syntax Analysis中，有一個重要的部件為Parser(解析器)，其作用為接收Scanner產生的Token Stream，利用Grammar驗證其正確性，檢查無誤後生成Parsing Tree(分析樹)

目前Parser有兩種類型:
* Top-Down(由上而下):從最上方(Root)建構Parsing Tree到最下方(Leaves)
* Bottom-Up(由下而上):從最下方(Leaves)建構Parsing Tree到最上方(Root)

例如對於以下Grammar，若要檢測aabc是否符合Grammar:
S → aAc
A → aA|b

Top-Down: **S** → a**A**c → aa**A**c → aabc (Accept)
Bottom-Up: a**ab**c → a**aA**c → **aAc** → S (Accept)

Context-Free Grammar
---
Context-Free Grammar(上下文無關文法)是一種相對於RE更能精確描述的句法格式:
* G = (T, N, P, S)
* T: Terminal的集合，Terminal為由Symbol組成的字串
* N: Nonterminal的集合，Nonterminal為構建出來的字串集合
* P: 產生式，形式為A → α~1~α~2~α~3~...(A∈N, α~i~∈N∪T)
* S: 首項Nonterminal，為Grammar的開頭，S∈N

> 下方數行為一個CFG:
> E → E + T
> E → E - T
> E → T
> T → T * F
> T → T / F
> T → F
> F → (E)
> F → id

對於CFG的符號有一定的規定:
* Terminal: 必須為小寫英文字母或者可印出的字串，例: a, b, id, (, ), +, -, *, ...
* Nonterminal: 必須為大寫英文字母開頭的字串，例: E, T, F, Ex
* Production: A → α...，若有A → β...，可寫為A → α...|β...，第一行Production通常被視為開始位置

> 將CFG縮寫後:
> E → E + T | E - T | T
> T → T * F | T / F | F
> F → (E) | id

上圖為id+id\*id的Parsing Tree

對於CFG，需要遵守其推導原則，如下行CFG:
E → E + E | E \* E | -E | (E) | id
其Derivation為 E ⇒ -E ⇒ -(E) ⇒ -(id)

以下為常用的符號:
* ⇒: 一步推導
* ⇒^+^: 一步或更多步推導
* ⇒^\*^: 零步或更多步推導

> E ⇒^+^ -(id)
> E ⇒^\*^ -(id)

若S ⇒^\*^ A，則A是該Grammar的Sentential Form(句型)，A可以包含Terminal或Nonterminal

Grammar的Sentence(句子)是不存在Nonterminal的Sentential Form，由Grammar產生出的Language為其Sentence的集合

Parsing Tree
---
對於String s，若想推導s是否符合CFG的Grammar，較好的做法是建構s的Parsing Tree

將Starting Nonterminal作為Parsing Tree的Root，每次Production時，將Production推導出的結果依順序作為Parsing Tree的葉，重複操作直到Nonterminal全被推導

A → xyz的Parsing Tree

Derivation方式分成兩種:
* Leftmost: 在考慮Derivation時優先考慮從左邊的節點開始
* Rightmost: 在考慮Derivation時優先考慮從右邊的節點開始

在大多情況下Leftmost與Rightmost會建構出相同的Parsing Tree，然而若Grammar為Ambiguous的話則會推導出不同結果

CFG&RE的差異
---
任何能被RE描述的Language皆能被CFG描述，相反則不一定
任何RE都屬於CFG，相反則不一定

例如先前所說到RE無法構建出{a^n^b^n^\|n≥0}的Language，在CFG中，其可以被這樣描述:
S → aA
A → Sb|b

然而CFG也並非萬能，仍然存在Language使得CFG無法描述，例如{a^n^b^m^c^n^\|n≥0,m≥0}，要解決此類問題需要用到Context-Sensitive Grammar(上下文有關文法)

在一般的Compiler中，考慮到效率以及構建方式，通常使用CFG作為Parser的實現

Ambiguous Grammar
---
若一個Grammar能夠推導出不只一種Parsing Tree，則被稱為Ambiguous Grammar

例如E → E + E | E \* E | -E | (E) | id在推導id+id\*id時可能會產生以下結果:

上圖為Leftmost，實際含義為(id+id)\*id

上圖為Rightmost，實際含義為id+(id\*id)

Ambiguous Grammar會導致可能的歧義，例如Dangling else等問題，為了排除Ambiguous Grammar，需要對Grammar的操作設定Precedence(優先級)
> E → E + E | T
> T → T \* T | F
> F → -E | (E) | id

除此之外，對Grammar也要考慮其Associativity(相依性)，當存在同樣的Nonterminal於同個Production時，若要Left Associativity(左相依)應將右邊轉成其他Nonterminal
> E → E + T | T
> T → T \* F | F
> F → -E | (E) | id

然而在解決Associativity時，往往會產生Left Recursion(左遞迴)的問題

Left Recursion
---
若A ⇒^+^ Aαβ，則該Grammar存在Left Recursion，其會導致Top-down Parser在if判定上出現問題

解決方法:
* A → Aα~1~ | Aα~2~ | ... | β~1~ | β~2~ | ...
* ⇓
* A → β~1~A' | β~2~A' | ...
* A' → α~1~A' | α~2~A' | ... | ε

Left Recursion是跨層問題，在遇到多層Production時，需要將前項內容代入後再來判斷是否存在Left Recursion

S → Aa | b
A → Sc | d
乍看兩段Production都是正常的，然而在判斷A → Sc | d時，應將先前的Production代入
A → Aac | d
⇓
A → dA'
A' → acA' | ε

因此解決Left Recursion後的結果應為:
S → Aa | b
A → dA'
A' → acA' | ε

Left Factoring
---
若 A → αβ~1~ | αβ~2~ | ...即為Left Factoring(左因子)，在Predictive Top-Down Parser中也會導致if判斷問題

解決方法:
* 提出因子
* A → αβ~1~ | αβ~2~ | ...
* ⇓
* A → αA'
* A' → β~1~ | β~2~ | ...

Top-Down Parsing
===
Top-Down Parsing採用起始於Root建立節點的方式，採用Preorder(前序，中-左-右)或稱Depth-First(深度優先)，一般情況採用Leftmost來構建Parsing Tree

有兩種Top-Down Parsing方式:
* Recursive-Descent Parsing(遞迴下降分析)
* Predictive Parsing(預測分析)，亦有Recursive與Nonrecursive差異

上圖為對照下方CFG，實現id+id\*id的Parsing Tree

E → TE'
E' → +TE' | ε
T → FT'
T' → \*FT' | ε
F → (E) | id

Recursive-Descent Parsing
---
Top-Down Parsing中最簡單的實現方法，也就是將所有可能性都試過一遍，若發生錯誤則Backtrack(回退)，在所有實現方法中效率最差

上圖為對照下方CFG，實現cad的Parsing Tree

S → cAd
A → ab | a

Predictive Parsing
---
為了避免Backtrack造成的效率損耗，Predictive Parsing採用Lookahead方式，建立Parsing Table，可以僅需Nonterminal與Input Symbol找到相應的Production

該算法又稱為LL(1) Grammar，也就是Left Input與Left Derivation向前探查1個Input Symbol

要實現這個算法需要兩個操作，FIRST()與FOLLOW():
* FIRST(): 若α ⇒^\*^ w，w為該Grammar的Sentence，則w的首位Symbol ∈ FIRST(α)
* 在判斷 A → α | β時，僅需檢測Input Symbol a是否位於FIRST(α)，是的話便可直接選擇A → α，否則選擇A → β
* 若排除掉Left Factoring，則FIRST(α) ∩ FIRST(β) = ∅

判斷FIRST()有以下規則: ==先直接推導，存在ε則追加，全都有ε才加ε==
* α → w~1~w~2~w~3~...
* FIRST(α) += FIRST(w~1~) - {ε}
* 若FIRST(w~1~)存在ε，FIRST(α) += FIRST(w~2~) - {ε}，以此類推直到FIRST(w~i~)不存在ε為止
* 若所有的FIRST(w~n~)皆有ε，FIRST(α) += {ε}

例如以下CFG，對各Nonterminal求FIRST():
| Production | FIRST() |
|:---------------:|:----------------------------------------:|
| E → TE' | FIRST(E) = FIRST(T) = FIRST(F) = {(, id} |
| E' → +TE' \| ε | FIRST(E') = {+, ε} |
| T → FT | FIRST(T) = FIRST(F) = {(, id} |
| T' → \*FT' \| ε | FIRST(T') = {\*, ε} |
| F → (E) \| id | FIRST(F) = {(, id} |

或者是以下CFG:
A → a | BCD
B → b | ε
C → c | ε
D → d | ε

依照上述規則，FIRST(A)
= {a} + FIRST(BCD)
= {a} + {b} + FIRST(CD)
= {a, b} + {c} + FIRST(D)
= {a, b, c} + {d} + {ε}
= {a, b, c, d, ε}

得到各Nonterminal的FIRST()後，可以進一步求出它們的FOLLOW():
* FOLLOW(): 若β ⇒^\*^ αβγδ，γ為該Grammar的Sentence，則γ的首位Symbol ∈ FOLLOW(β)
* 若β在部分Sentential Form中為最右端的Symbol，則$(終止符)∈ FOLLOW(β)

判斷FOLLOW()有以下規則: ==起始先加$，有後面加後面，後面有ε則追加，全都有ε加前面==
* FOLLOW(S) += {$}，S為起始位置
* 若 α → w~1~w~2~w~3~，FOLLOW(w~2~) += FIRST(w~3~) - {ε}
* 若 α → w~1~w~2~w~3~w~4~，且FIRST(w~3~)存在ε，FOLLOW(w~2~) += FIRST(w~4~) - {ε}，以此類推直到FIRST(w~i~)不存在ε為止
* 若所有的FIRST(w~n~)皆有ε，或者是w~2~後無其他東西，FOLLOW(w~2~) += FOLLOW(α)

例如以下CFG，對各Nonterminal求FOLLOW():
| Production | FIRST() | FOLLOW() | FOLLOW() |
|:---------------:|:-------------------:|:----------------------:|:-----------------------:|
| E → TE' | FIRST(E) = {(, id} | FOLLOW(T) += FIRST(E') | FOLLOW(E') += FOLLOW(E) |
| E' → +TE' \| ε | FIRST(E') = {+, ε} | FOLLOW(T) += FIRST(E') | |
| T → FT' | FIRST(T) = {(, id} | FOLLOW(F) += FIRST(T') | FOLLOW(T') += FOLLOW(T) |
| T' → \*FT' \| ε | FIRST(T') = {\*, ε} | FOLLOW(F) += FIRST(T') | |
| F → (E) \| id | FIRST(F) = {(, id} | FOLLOW(E) += {)} | |

由上述線索可發現:
FOLLOW(E) = {$} + FOLLOW(E) = {\$, )}
FOLLOW(E') = FOLLOW(E) = {\$, )}
FOLLOW(T) = FIRST(E') (存在ε) = FIRST(E') - {ε} + FOLLOW(E') = {+} + {$, )} = {+, $, )}
FOLLOW(T') = FOLLOW(T) = {+, $, )}
FOLLOW(F) = FIRST(T') (存在ε) = FIRST(T') - {ε} + FOLLOW(T') = {\*} + {+, $, )} = {\*, +, $, )}

或者是以下CFG:
A → cB
B → dA | e

依照上述規則，FOLLOW(A) = FOLLOW(B) 且 FOLLOW(B) = FOLLOW(A)
遇到這種互相引用的迴圈時，先將其視為空集合，A補上\$，得出FOLLOW(A) = {\$}的結論後，再處理FOLLOW(B) = FOLLOW(A) = {\$}

Parsing Table
---
計算出所有Nonterminal的FIRST()與FOLLOW()後，便可以製作該CFG的Parsing Table了:
* 對於所有Production A → α
* 若Terminal s ∈ FIRST(α)，該Production填入M\[A, s\]
* 若ε ∈ FIRST(α)，該Production填入所有M\[A, FOLLOW(A)\]

例如以下CFG與Parsing Table:
| Nonterminal | Production | FIRST() | FOLLOW() |
|:-----------:|:---------------:|:-------:|:-------------:|
| E | E → TE' | {(, id} | {\$, )} |
| E' | E' → +TE' \| ε | {+, ε} | {\$, )} |
| T | T → FT' | {(, id} | {+, $, )} |
| T' | T' → \*FT' \| ε | {\*, ε} | {+, $, )} |
| F | F → (E) \| id | {(, id} | {\*, +, $, )} |

| | id | + | \* | \( | \) | \$ |
|:---:|:-------:|:---------:|:----------:|:-------:|:------:|:------:|
| E | E → TE' | | | E → TE' | | |
| E' | | E' → +TE' | | | E' → ε | E' → ε |
| T | T → FT' | | | T → FT' | | |
| T' | | T' → ε | T' → \*FT' | | T' → ε | T' → ε |
| F | F → id | | | F → (E) | | |

Ambiguous Grammar的Parsing Table存在一格有兩個Production的情況，因此在判斷上會出現問題，若出現此情況，則不能被稱為LL(1) Grammar

Top-Down Simulation
---
使用Parsing Table可以較有效率的對字串進行驗證，例如用上述Parsing Table驗證id+id\*id

使用Parsing Table有幾個操作:
* Stack放入{$, S}，Input放入{String, $}
* 將Stack最上方對照Parsing Table左側，讀取Input左側第一個Symbol對照Parsing Table上方，若存在Production則將Stack最上方推導(推導結果倒過來放進Stack)，若不存在Production則Reject
* 若Stack最上方與讀取Symbol相同，則兩者相消
* 若Stack與Input皆只剩下\$，則Accept

| Stack | Input | Action |
|:-------- | -----------:|:----------:|
| $E | id+id\*id\$ | E → TE' |
| $E'T | id+id\*id\$ | T → FT' |
| $E'T'F | id+id\*id\$ | F → id |
| $E'T'id | id+id\*id\$ | Match id |
| $E'T' | +id\*id\$ | T' → ε |
| $E' | +id\*id\$ | E' → +TE' |
| $E'T+ | +id\*id\$ | Match + |
| $E'T | id\*id\$ | T → FT' |
| $E'T'F | id\*id\$ | F → id |
| $E'T'id | id\*id\$ | Match id |
| $E'T' | \*id\$ | T' → \*FT' |
| $E'T'F\* | \*id\$ | Match \* |
| $E'T'F | id\$ | F → id |
| $E'T'id | id\$ | Match id |
| $E'T' | \$ | T' → ε |
| $E' | \$ | E' → ε |
| $ | \$ | Accept |

Bottom-Up Parsing
===
與Top-Down不同的是，Bottom-Up先將Input String作為Leaves，目標是將Root(Starting State)給Reduce(反向推導)出來

例如下方CFG，試圖用Bottom-Up推導id\*id:
E → E + T | T
T → T \* F | F
F → (E) | id

id \* id ⇒ F \* id ⇒ T \* id ⇒ T * F ⇒ T ⇒ E

在Bottom-Up中需要考慮兩個問題:
* Reduce的時機?
* 採用的Production?

因此需要引入Handle(控制項)的概念，在進行Reduce時，A → a，a即為Handle，對於Bottom-Up的關鍵就是從Input中尋找正確的Handle，並對其進行Handle Pruning(修剪)，也就是反向推導

在上述例子中，對id\*id的Handle Pruning如下:
| Sentential Form | Handle | Reducing Production |
| ---------------:|:--------:|:-------------------:|
| id\*id | id(Left) | F → id |
| F\*id | F | T → F |
| T\*id | id | F → id |
| T\*F | T\*F | T → T \* F |
| T | T | E → T |
| E | | |

Shift-Reduce Parsing有以下操作:
* Shift: 將下一位Input Symbol放入Stack
* Reduce: 刪除掉Stack頂部的Handle，將Reduce後的結果放入Stack
* Accept: 停止Parsing並回傳成功
* Error: 遇到非預期結果並回傳錯誤

Shift-Reduce Parsing處理上述CFG的流程如下:
| Stack | Input | Action |
|:------- | --------:|:-----------------:|
| \$ | id\*id\$ | Shift |
| \$id | \*id\$ | Reduce F → id |
| \$F | \*id\$ | Reduce T → F |
| \$T | \*id\$ | Shift |
| \$T* | id\$ | Shift |
| \$T\*id | \$ | Reduce F → id |
| \$T\*F | \$ | Reduce T → T \* F |
| \$T | \$ | Reduce E → T |
| \$E | \$ | Accept |

在Shift-Reduce Parsing中，操作的不同會影響最終的結果，會造成兩個問題:
* Shift/Reduce Conflict: 當存在Handle時，是否要Shift產生新的Handle或是直接Reduce
* Reduce/Reduce Conflict: 當存在Handle時，存在多個Production可以Reduce

LR Parsing
---
LR Parsing是一種較為廣泛使用的Parsing方法:
* L: 從左向右讀取Input
* R: 反向Rightmost Derivation
* k: 向前探查k位，k被省略則視為1

在編譯程式概論中，只考慮k=0與k=1的實作方法:
* k=0: LR(0), Simple LR(SLR)
* k=1: Canonical LR(LR), Lookahead Parsing(LALR)

LR Parsing可辨別所有CFG所構建出來的Language，檢查出文法錯誤，能被LL Parsing檢測的Grammar必然能被LR Parsing檢測

LR(0)
---
在Production中加入可以識別位置的點，被稱為item:
> A → •XYZ
> A → X•YZ
> A → XY•Z
> A → XYZ•

加入該點的用意是為了確認Parsing過程中已經讀取到的位置，例如A → X•YZ代表已經讀完X的內容，接下來要讀取YZ，而A → XYZ•則代表該Production皆被讀取，可以進行Reduce

在Canonical LR(0)中，需要先為Start Symbol S定義Augmented Grammar S' → S，確保最後內容僅為S才能進行Reduce

Canonical LR(0)有兩個操作，CLOSURE()與GOTO():
* CLOSURE(I): 對I•後一位進行讀取可能產生的item集合，I為item的集合
* CLOSURE(I) += I
* 若 A → X•YZ ∈ CLOSURE(I)，且Y → β是Production，則將Y → •β加入CLOSURE(I)，重複操作直到CLOSURE(I)無變化
* 可視為加強版的FIRST()

例如以下CFG，尋找I = {\[E' → •E]}的CLOSURE(I):
E' → E
E → E + T | T
T → T \* F | F
F → (E) | id

CLOSURE(I) += \[E' → •E]
E' → •==E==，CLOSURE(I) += {\[E → •E + T], \[E → •T]}
E → •==T==，CLOSURE(I) += {\[T → •T \* F], \[T → •F]}
T → •==F==，CLOSURE(I) += {\[F → •(E)], \[F → •id]}

CLOSURE(I)={\[E' → •E],
\[E → •E + T], \[E → •T],
\[T → •T \* F], \[T → •F],
\[F → •(E)], \[F → •id]}

* GOTO(I, X):對I•後一位讀取特定Symbol，並進行•位移後可能產生的CLOSURE()，I為item的集合，X為讀取的Symbol
* 若 A → X•YZ ∈ I，則將CLOSURE(\[A → XY•Z])加入GOTO(I,Y)
* 可視為加強版的FOLLOW()

例如以下CFG，尋找I = {\[E' → E•], \[E' → E •+ T]}的GOTO(I, +):
E' → E(Augmented Grammar)
E → E + T | T
T → T \* F | F
F → (E) | id

E' → E •+ T，GOTO(I, +) += CLOSURE(\[E' → E + •T])

CLOSURE(\[E' → E + •T]) += {\[E' → E + •T]}
E' → E + •==T==，CLOSURE(\[E' → E + •T]) += {\[T → •T \* F], \[T → •F]}
T → •==F==，CLOSURE(\[E' → E + •T]) += {\[F → •(E)], \[F → •id]}

GOTO(I, +)={\[E' → E + •T],
\[T → •T \* F], \[T → •F],
\[F → •(E)], \[F → •id]}

了解CLOSURE()與GOTO()後，便可以著手建置CFG的LR(0) Grammar的DFA了:
* 將CLOSURE(\[S' → •S])放入I~0~，此為起始狀態
* 將I~0~與所有Grammar Symbol α求GOTO(I~0~, α)，若該GOTO()與I~0~\~I~n~皆不相同，則將該GOTO()放入I~n+1~，並且I~0~ {→|α} I~n+1~
* 對I~1~重複此操作，以此類推直到所有狀態皆被處理且不存在新的狀態
* GOTO(I~0~, S)為最終狀態(通常為I~1~)，I~1~ {→|\$} Accept

例如以下CFG，求其DFA:
E' → E(Augmented Grammar)
E → T | id
T → id + F
F → id | T

第一步先將CLOSURE(\[E' → •E])放入I~0~:
I~0~ = {\[E' → •E], \[E → •T], \[E → •id], \[T → •id + F]}

對I~0~求GOTO():
I~1~ = CLOSURE(\[E' → ==E==•])
= {\[E' → E•]}
I~2~ = CLOSURE(\[E → ==T==•])
= {\[E → T•]}
I~3~ = CLOSURE(\[E → ==id==•], \[T → ==id== •+ F])
= {\[E → id•], \[T → id •+ F]}

I~0~ {→|E} I~1~
I~0~ {→|T} I~2~
I~0~ {→|id} I~3~

對I~1\~3~求GOTO():
I~4~ = CLOSURE(\[T → id ==+== •F])
= {\[T → id + •F], \[F → •id], \[F → •T], \[T → •id + F]}

I~3~ {→|+} I~4~

對I~4~求GOTO():
I~5~ = CLOSURE(\[T → id + ==F==•])
= {\[T → id + F•]}
I~6~ = CLOSURE(\[F → ==id==•], , \[T → ==id== •+ F])
= {\[F → id•], \[T → id •+ F]}
I~7~ = CLOSURE(\[F → ==T==•])
= {\[F → T•]}

I~4~ {→|F} I~5~
I~4~ {→|id} I~6~
I~4~ {→|T} I~7~

對I~6~求GOTO():
I~8~ = CLOSURE(\[T → id ==+== •F])
= {\[T → id + •F], \[F → •id], \[F → •T], \[T → •id + F]} = I~4~

I~6~ {→|+} I~4~

上圖為該CFG的DFA

Simulation of LR(0)
---
採用Shift-Reduce Parsing的方式進行LR(0)的模擬：
* Stack: 紀錄經過的狀態
* Symbol: 紀錄被Shift的Input內容，在該區塊尋找Handle
* Input: 從最左端開始讀取Symbol
* Action: 執行動作
* 開始時，Stack放入0，代表從I~0~開始，Symbol放入\$，Input最右側放入\$
* Shift: 當發現Input第一位為a，且A → α•aβ ∈ I~n~時，Input最左側放入Symbol，並且依照DFA讀取a方向移動
* Reduce: 當A → a• ∈ I~n~時，移除Stack最上方n個(n為a的Symbol個數)，反向Derivation後，依照DFA讀取A方向移動
* Accept: 於Final State讀取到$
* Error: 無法執行Shift或Reduce

LR(0)對上述DFA檢測id+id+id的流程如下:

| Stack | Symbol | Input | Action |
|:----------- |:---------- | ----------:|:-----------------:|
| 0 | \$ | id+id+id\$ | Shift |
| 0 3 | \$id | +id+id\$ | Shift |
| 0 3 4 | \$id+ | id+id\$ | Shift |
| 0 3 4 6 | \$id+id | +id\$ | Shift |
| 0 3 4 6 4 | \$id+id+ | id\$ | Shift |
| 0 3 4 6 4 6 | \$id+id+id | \$ | Reduce F → id |
| 0 3 4 6 4 5 | \$id+id+F | \$ | Reduce T → id + F |
| 0 3 4 7 | \$id+T | \$ | Reduce F → T |
| 0 3 4 5 | \$id+F | \$ | Reduce T → id + F |
| 0 2 | \$T | \$ | Reduce E → T |
| 0 1 | \$E | \$ | Accept |

注意在LR(0)時一個狀態中最多存在一個可Reduce的Production，杜絕了Reduce/Reduce Conflict，但仍然存在Shift/Reduce Conflict，如前面例子，若在中途步驟稍加修改(仍不違反DFA規則):
| Stack | Symbol | Input | Action |
|:------- |:------- | ----------:|:-----------------:|
| 0 | \$ | id+id+id\$ | Shift |
| 0 3 | \$id | +id+id\$ | Shift |
| 0 3 4 | \$id+ | id+id\$ | Shift |
| 0 3 4 6 | \$id+id | +id\$ | Reduce F → id |
| 0 3 4 5 | \$id+F | +id\$ | Reduce T → id + F |
| 0 2 | \$T | +id\$ | Reduce E → T |
| 0 1 | \$E | +id\$ | Error |

SLR
---
關於LR(0)中的Shift/Reduce Conflict，可以透過FOLLOW()來解決，改良過的LR(0)被稱為SLR(Simple LR)，改良後的規則如下:
* Shift: 當發現Input第一位為a，且A → α•aβ ∈ I~n~時，Input最左側放入Symbol，前往CLOSURE({\[A → α•aβ]})的狀態
* Reduce: 當A → a• ∈ I~n~且a ∈ FOLLOW(A)時，移除Stack最上方n個(n為a的Symbol個數)，前往到GOTO(I, A)的狀態，I為Stack最上方的狀態

利用SLR Parsing Table能較容易的進行狀態轉移，SLR Parsing Table的建構方式如下:
* 建構C = {I~0~, I~1~, ..., I~n~}，此為LR(0)的item集合
* 建構Action表格，對於所有Item I~i~ ∈ C 與Terminal a(或是\$)
* 若\[A → α•aβ] ∈ I~i~且GOTO(I~i~, a) = I~j~，則Action\[i, a] = "Shift J"
* 若\[A → α•] ∈ I~i~，則Action\[i, a] = "Reduce A → α"，a ∈ FOLLOW(A)
* 若\[S' → S•] ∈ I~i~，則Action\[i, $] = "Accept"
* 建構GOTO表格，對於所有Nonterminal A
* 若GOTO(I~i~, A) = I~j~，則GOTO[i, A] = j
* 如果產生Conflict，則該Grammar並非SLR(1)


若構建上述DFA的SLR Parsing Table，先將Production編號並找到FOLLOW():
(1) E → T
(2) E → id
(3) T → id + F
(4) F → id
(5) F → T

FOLLOW(E) = {$}
FOLLOW(T) = {id, $}
FOLLOW(F) = {id, $}

構建出來的Parsing Table如下:
| | Action | | | GOTO | | |
|:-----:|:------:|:---:|:---:|:----:|:---:|:---:|
| State | + | id | $ | E | T | F |
| 0 | | S3 | | 1 | 2 | |
| 1 | | | Acc | | | |
| 2 | | | R1 | | | |
| 3 | S4 | | R2 | | | |
| 4 | | S6 | | | 7 | 5 |
| 5 | | R3 | R3 | | | |
| 6 | S4 | R4 | R4 | | | |
| 7 | | R5 | R5 | | | |

利用Parsing Table模擬待測Input String的流程如下:
* 開始時，Stack放入0，代表從I~0~開始，Symbol放入\$，Input最右側放入\$
* 檢查\[I, a]並執行該格操作，I為Stack頂部，a為Input最左邊Symbol
* 若為Shift i: Stack放入i，a放入Symbol
* 若為Reduce j: 移除Symbol與Stack最上方n個(n為Production j的右側Symbol個數)，Symbol放入A，檢查新的\[I,A]，Stack放入GOTO值，A為Production左側Nonterminal

對照Parsing Table模擬id+id+id:
| Stack | Symbol | Input | Action |
|:----------- |:---------- | ----------:|:--------:|
| 0 | \$ | id+id+id\$ | S3 |
| 0 3 | \$id | +id+id\$ | S4 |
| 0 3 4 | \$id+ | id+id\$ | S6 |
| 0 3 4 6 | \$id+id | +id\$ | S4 |
| 0 3 4 6 4 | \$id+id+ | id\$ | S6 |
| 0 3 4 6 4 6 | \$id+id+id | \$ | R4 GOTO5 |
| 0 3 4 6 4 5 | \$id+id+F | \$ | R3 GOTO7 |
| 0 3 4 7 | \$id+T | \$ | R5 GOTO5 |
| 0 3 4 5 | \$id+F | \$ | R3 GOTO2 |
| 0 2 | \$T | \$ | R1 GOTO1 |
| 0 1 | \$E | \$ | Accept |