# 【Compiler】 Ch4. Syntax Analysis

* 在學會了scanner如何實作之後，我們已經得到了一系列的tokens，這代表傳進來的字至少電腦都看得懂。
* 接下來我們要判斷這些tokens語法是否正確，字雖然分開看都看得懂，但合在一起就不一定了。
* 一般做語法解析有三種方式：
* Universal parsing methods
* 較複雜，這邊不會教。
* Top-down
* Bottom-up
* 這一章我們就要使用下面兩種方法來完成Syntax Analysis。

## Context-Free Grammars

* 在做語法分析的時候，我們習慣使用Context-Free Grammars來描述語言。
* 使用語法可以精準的對語法規範。
* 添加新的語法也很容易。
* 為什麼不使用和Lexical一樣使用Regular Languages?
* Regular Languages雖然很好懂，但它能描述的語言範圍太小。
* 例如$\{^n\}^n$這個語言不在regular language的範圍內。

### Prove a language is regular or not

* 如果一個語言是regular，那就畫出它的NFA或是直接找到regular expressions，就可以證明它是regular。
* 如果不是的話可以使用Pumping Lemma證明。
---
* 如果A是 regular language，那麼任意在符合A的字串s = xyz, |s| $\geq$ n符合：
* $xy^iz \in A, i \geq 0$
* |y| > 0
* |xy| $\leq$ n
* 範例：證明$L = \{0^n1^n | n ≥ 0\}$ 不是regular。
* y有三種可能：
1. 只有`0`
* y變2倍之後`0`和`1`數量就不同了，新的字串不符合L。
2. 只有`1`
* 同上
3. 有`0`又有`1`
* y變2倍之後，新字串變成`0` `1`交錯，不符合L。

## Pushdown Automata

* Pushdown Automata是一個較複雜的狀態機，除了之前Finite Automata的東西之外，它多了一個stack去儲存上一個輸入。
* 為什麼不使用一般的Finite Automata？
* 因為我們的語法改為Context-Free Grammars，變得複雜了，因此狀態機也要變得複雜。
* 可以用NFA、DFA表達就表示有Regular Expressions、反過來說不能用Regular表示就沒有NFA、DFA。
* 數學表達法：$M=(K, \sum , \Gamma , \delta , q_0, Z_0, F)$
* K: 總狀態的集合
* $\sum$: 輸入字母集
* $\Gamma$: stack的字母集
* $\delta$: 狀態轉移關係的集合
* $\delta$(0, a, 0) = {1}，表示在狀態0看到a且stack是0的時候往狀態1跑。
* $q_0$: 起始狀態(屬於K)
* $Z_0$: 初始stack內的符號(屬於$\Gamma$)
* F: 結束狀態的集合
---
練習題
建立語言$L = \{0^n1^n|n\geq 0\}$ 的Pushdown Automata。

答案
M = ({q0 , q1}, {0, 1}, {0, 1}, δ, q0 , є, ψ)
δ(q0 , 0, є) = (q0 , 0)
δ(q0 , 0, 0) = (q0 , 00)
δ(q0 , 1, 0) = (q1 , є)
δ(q1 , 1, 0) = (q1 , є)

---
練習題
建立語言$L = \{wcw^R | w ∈ \{0, 1\}^*\}$ 的Pushdown Automata。
(R表示反轉)

答案
M = ({q0, q1}, {0, 1, c}, {R, G, B}, δ, q0, R, ψ)
δ(q0 , 0, R) = (q0 , BR)
δ(q0 , 0, G) = (q0 , BG)
δ(q0 , 0, B) = (q0 , BB)
δ(q0 , 1, R) = (q0 , GR)
δ(q0 , 1, G) = (q0 , GG)
δ(q0 , 1, B) = (q0 , GB)
δ(q0 , c, R) = (q1 , R)
δ(q0 , c, G) = (q1 , G)
δ(q0 , c, B) = (q1 , B)
δ(q1 , 0, B) = (q1 , є)
δ(q1 , 1, G) = (q1 , є)
δ(q1 , є, R) = (q1 , є)

## Parse Trees

* 一棵Parse Tree可以表示我們如何從起始符號一路derives成目標句子。
* 給定Parse Tree或是Derivations都可以得知該文法如何定義語言。
* 範例：E → E + E | E * E | (E) | −E | id
* w = − (id + id)
* Derivation:
E ⇒ −E
⇒ − (E)
⇒ − (E + E )
⇒ − (id + E )
⇒ − (id + id)
* Parse Tree:

### Ambiguity

* 句子的Parse Tree在左優先或右優先(leftmost or rightmost)的前提下各自只會有一棵唯一樹。
* 但是在不給定優先度的時候，同一個句子可能有很多棵Parse Tree，這種情形我們稱該文法為Ambiguity的文法。
* 範例：E → E + E | E * E | (E) | −E | id
* w = id + id * id
* 可以得到兩種過程：
* E ⇒ E + E
⇒ id + E
⇒ id + E * E
⇒ id + id * E
⇒ id + id * id
* E ⇒ E * E
⇒ E + E * E
⇒ id + E * E
⇒ id + id * E
⇒ id + id * id
* 這種情形就是你的compiler不知道要先做加法還是乘法，有兩種解決方法：
1. 給定優先度
2. 重寫文法

### Eliminating Ambiguity

* 範例：if else匹配
* 原文法：
stmt → if expr then stmt
stmt → if expr then stmt else stmt
stmt → other
* 輸入：if E1 then if E2 then S1 else S2
* 擁有以下兩種Parse Tree，表示該文法為Ambiguity

- 改寫為新文法：
stmt → matched_stmt
　　　| unmatched_stmt
matched_stmt → if expr then matched_stmt else matched_stmt
　　　| other
unmatched_stmt → if expr then stmt
　　　| if expr then matched_stmt else unmatched_stmt

### Left Recursion

* 另一個文法上的問題是Left Recursion。
* 試想有一文法$A \overset{+}{\Rightarrow} A \alpha$
* 例如：$A\rightarrow A\alpha | \beta$
* 進行Derivation時，我們通常是用DFS的概念，如果第一項不能推導出輸入，則我們再選擇第二項
* 假設現在輸入為$\beta \alpha \alpha$
* 我們從起始符號A開始推導
* $A\rightarrow A\alpha$
* $A\alpha \rightarrow A\alpha \alpha$
* $A\alpha \alpha \rightarrow A\alpha \alpha \alpha$
* ...
* 我們知道要該輸入只要選擇$\beta$就能成功，但是因為無限迴圈造成compiler當機。

### Eliminating Left Recursion

* 要解決Left Recursion最簡單的方法就是改寫文法
* 原文法：A → Aα | β
* 新文法：
* A → β A’
* A’ → α A’ | є
* 雖然導致文法看起來變得很不直覺，但可以表示完全一樣的語言且消除Left Recursion的問題。
---
練習
改寫以下文法以消除Left Recursion
E → E + T | T
T → T * F | F
F → (E ) | id

答案
E → TE’
E’ → +TE’ | є
T → FT’
T’ → *FT’ | є
F → (E ) | id

---
* 有時候Left Recursion要經過多層的derives才會出現。
* 範例：
* S → A a | b
* A → A c | S d | є
* 解決方法是將符號替換代入：
* A → A c | A a d | bd | є
* 再用一般的方法消除：
* S → A a | b
* A → bdA’ | A’
* A → cA’ | adA’ | є

## Top-Down Parsing

* 前面講了那麼多，就是為了實作出Top-Down Parsing。
* Top-Down Parsing的概念前面其實已經提過了，就是找到一個leftmost derivation可以變成輸入字串。
* 但這樣的方法有個缺點，就是你的文法一旦變得複雜之後，每一種可能都要跑一遍，就可能要即大量的運算時間才能判斷輸入是否符合文法。
* 如果我們可以根據輸入直接判斷要選哪種derivation就可以大幅加快速度。
* 使用Predictive Parser。

### Predictive Parser
* 藉由先偷看下一個輸入來判斷現在應該要選哪個derivation。
* 我們需要先找出每個符號的開頭(FIRST)可能是那些字元。
* 範例：
* type → simple | ^id | array [ simple ] of type
* simple → integer | char | num dotdot num
* 那麼FIRST(simple) = integer和char和num
* FIRST(type) = FIRST(simple)和 ^ 和 array
* 因此我們的Parser今天如果看到 ^ 就知道要選擇type → ^id去derive。
---
* 其實也可以直接透過文法建出狀態圖來得到Predictive Parser要解釋有點困難，直接看圖應該就很好理解。
* 範例：
* E → TE’
* E’ → +TE’ | є
* T → FT’
* T’ → *FT’ | є
* F → (E ) | id
* 每經過一條nontermial的邊的時候，就要先跳到它的圖，跑到結束狀態再回來。
* 有兩條路走的時候就根據輸入來決定路線。
* 假設輸入w = id + id * id，則過程為：
1. 0到1，跳至T的圖7
2. 7到8，跳至F的圖14
3. 輸入為id，選擇14到17，輸入剩+ id * id
4. 回到T的圖8，8到9，跳至T'的圖10
5. 輸入不是*，選擇10到13
6. 回到T的圖9，回到E的圖1，1到2，跳至E'的圖3
7. 輸入為+，選擇3到4，輸入剩id * id
8. 4到5，跳至T的圖7
9. 7到8，跳至F的圖14
10. 輸入為id，選擇14到17，輸入剩* id
11. 回到T的圖8，8到9，跳至T'的圖10
12. 輸入是*，選擇10到11，輸入剩id
13. 11到12，跳至F的圖14
14. 輸入是id，選擇14到17，輸入為空
15. 回到T'的圖12，12到13，跳到T'的圖10
16. 輸入不是*，選擇10到13
17. 回到T'的圖13，回到T的圖9，回到E'的圖5，5到6，跳到E'的圖3
18. 輸入不是+，選擇3到6
19. 回到E'的圖6，回到E的圖2
20. 確認輸入為空，代表該輸入匹配該語法

### Nonrecursive Predictive Parser
* 上面的Predictive Parser雖然看起來蠻容易完成的，但是可以看到步驟非常多(況且這還是很簡單的語法)。
* 我們必須避免掉parse過程中不停cursive檢查語法的問題，這時候就要使用Nonrecursive Predictive Parser。
* Nonrecursive Predictive Parser的概念很簡單，我們建立一個table和一個stack，我們只要根據現在stack頂端和輸入的字，就可以在table中找到要使用的derivation。

---
* 範例：與剛剛的使用一樣的例子
* E → TE’
* E’ → +TE’ | є
* T → FT’
* T’ → *FT’ | є
* F → (E ) | id
* w = id + id * id
* Parsing table: 
* 初始化：在stack放入`$`當作結束符號，然後放入起始符號E開始parse；輸入字串的尾端也放入`$`當作輸入結束。
* 過程：
---
* 然而，我們到底要怎麼得到這個神奇的Parsing table呢？

#### FIRST and FOLLOW

* 我們只要得到文法的FIRST和FOLLOW，就可以產生出Parsing Table了，因此我們要先學會怎麼從文法得到FIRST和FOLLOW。
* FIRST(A)指所有可能出現在A開頭的terminals
* FOLLOW(A)指所有可能接在A後面的terminals
* A是nonterminal，得到的結果都是terminals
* 一樣用上面的文法當作例子：
* E → TE’
* E’ → +TE’ | є
* T → FT’
* T’ → *FT’ | є
* F → (E ) | id
* FIRST(A)應該比較簡單，就是把A右邊的第一個字x拿出來
* 如果x是terminal就加入x
* 例如上面的E’ → +TE’ | є，就將+加入FIRST(E’)
* 如果x是nonterminal就加入FIRST(x)
* 例如上面的E → TE’，就將FIRST(T)加入FIRST(E)
* 則我們得到：
* FIRST(E) = FIRST(T) = FIRST(F) = {(, id}
* FIRST(E’) = {+, є}
* FIRST(T’) = {*, є}
---
* FOLLOW比較麻煩一點點，我們必須觀察每一個derivation中的nonterminal後面有接什麼東西。
* 狀況一：A → αBβ，將FIRST(β) − {є} 加入至 FOLLOW(B)
* β在B的後面，所以β的FIRST就是B的FOLLOW。
* 狀況二：A → αB，將FOLLOW(A) 加入至 FOLLOW(B)
* A可以變成αB(B在A的最後面)，因此A後面接的東西也是B後面接的東西。
* 狀況三：A → αBβ 且 є ∈ FIRST(β)，將FOLLOW(A) 加入至 FOLLOW(B)
* 雖然B不是A的結尾，但因為β可以變成空字串，因此又變成狀況二了。
* 總之就是要注意є的可能，它會讓你要考慮的東西變多。
* 根據上面我們得到：
* FOLLOW(E) = FOLLOW(E’) = {), $}
* FOLLOW(T) = FOLLOW(T’) = {+, ), $}
* FOLLOW(F) = {+, *, ), $}

#### Construction of Predictive Parsing Table

* 得到FIRST和FOLLOW的之後，我們將Production按照規則放入table中，就可以完成Parsing Table了。
* Table M上面的row是terminal，左邊的column是nonterminal。
* 演算法：
1. 跑所有production P = A → α
2. 如果找到 a ∈ FIRST(α)，將P放入M[A, a]
3. 如果找到 є ∈ FIRST(α)，將P放入M[A, b]，b = FOLLOW(A)
4. 如果找到 є ∈ FIRST(α) and $ ∈ FOLLOW(A)，將P放入M[A, $]
5. 其餘在M裡面空白的地方都是error
> 建議自己在紙上求一次FIRST、FOLLOW、TABLE，確定自己學會。

---
* 再來一個範例，你可能會發現一些問題。
* 文法：
* S → iEtSS’ | a
* S’ → eS | є
* E → b
* 先求FIRST
* FIRST(S) = i, a
* FIRST(S’) = e, є
* FIRST(E) = b
* 再求FOLLOW
* FOLLOW(S) = FOLLOW(S’) = e, $
* FOLLOW(S’) = e, $
* FOLLOW(E) = t
* 得到table: 
* 是否有發現什麼地方怪怪的？
* 有一格同時出現兩個Production了！

### LL(1) Grammars

* 如果想要保證你的parsing table不會出現多個元素在同一格，就必須使用LL(1)的文法，什麼是LL(1)？
* 第一個`L`代表input從left開始讀取。
* 第二個`L`代表derivation是leftmost。
* 最後的`1`代表我們將提前看1個輸入字元來判斷。
* 這樣的文法必須擁有以下特性：
* 不會發生ambiguous
* 不會發生left recursive
* 所有productions A → α | β
* α 和 β 不能推導出同樣的terminal當作開頭
* α 和 β 最多只能有其中一個推導出є
* 如果β可以變空字串，α不能推導出任何是FOLLOW(A)的terminal當作開頭
* 看起來頗複雜，所以就先跳過，不用太在意XD

## Bottom-Up Parsing

* 另一種Parsing的方法是Bottom-Up，我們不是將起始符號S推導至input，而是將input做reduce，如果最後可以變成起始符號S，代表該input符合文法。
* 一個productions A → ab中
* 左邊展開為右邊叫做reduce
* 右邊縮減為左邊叫做derive
* 這種Parsing又稱做Shift-Reduce Parsing，因為我們會不斷使用Shift和Reduce這兩個動作來進行Parse。
* 現在來詳細說明動作。

### Stack Implementation of Shift-Reduce Parsing

* 我們在做parse之前，需要先有一個stack用來存放symbol。
* 然後我們總共有幾個動作：
* shift: 把下一個input放入stack
* reduce: 把stack裡面的symbol用nonterminal取代
* accept: 宣告成功(該input符合該文法)
* error: 宣告失敗(該input不符合該文法)

---
* 範例
* (1) E → E + E
* (2) E → E * E
* (3) E → (E)
* (4) E → id
* w = id + id * id
* 然而，因為沒有規定shift和reduce的優先度，語法可能有好幾種結果:
* 在第`6`步的時候，stack = E + E，這時候可以進行shift也可以進行reduce。

### LR Parsers

* 我們想要更有系統地來完成Shift-Reduce Parsing，稱做LR(k) Parser。
* `L`代表input從left開始讀取。
* `R`代表代表derivation是rightmost。
* `k`代表我們提前看input中的k個字元來判斷。
* 我們先以LR(0)為主，也就是沒有提前看input的部分。
* 優點：
* 幾乎可以識別所有context-free grammars。
* 支援predictive parsers用於加速。
* 偵測錯誤的速度很快。
* 缺點：
* 建立parser很麻煩。
* 一般實務上使用程式協助產生。
* LR Parser的重點在於有一個Parsing Table，告訴我們什麼狀態遇到什麼輸入時應該執行什麼動作。
* 在學會建立Parsing Table之前，我們先學會如何使用它。

---
* 範例：
* (1) E → E + T
* (2) E → T
* (3) T → T * F
* (4) T → F
* (5) F → (E )
* (6) F → id
* w = id * id + id $
* 我們還需要一個stack存放symbol和狀態，初始為stack s = $ 0
* stack一定是一個符號配一個狀態
* $是結尾符號，0是狀態0
* 給予table: 
* 左側為狀態、上面為symbol。
* 使用：查看input和stack頂端的狀態，去對照table的指示。
* 指示會是一個英文字加上一個數字i。
* 如果table的指示是s開頭，表示執行shift。
* 將該input放入stack，並將i放入stack當下一個狀態。
* 如果table的指示是r開頭，代表執行reduce。
* 將stack內的symbol按照第i條production轉換為nonterminal，然後再次查表。
* 查看轉換出來的nonterminal和現在的state，放入新的狀態。
* 結果：
* 可能看文字不太好懂，上圖有附上完整過程，請多練習。

---
* 接下來要學習如何建立table，有以下幾種建立LR parsing table的方法：
* Simple LR (SLR)
* Canonical LR (LR)
* Lookahead LR (LALR)
* 不同的方法可以辨識的語法不同，所需的cost也不同。

### SLR

* 將一個點加入production裡面得到的東西稱做item：
* 例如：production A → XYZ
* A → ⋅XYZ
* A → X⋅YZ
* A → XY⋅Z
* A → XYZ⋅
* 例如：production A → є yields
* A → ⋅
* 點就代表現在解析語法的進度，藉由對這些item進行某些運算可以幫助我們得到table，現在請先對item有些概念。

* 我們以下的操作中，會稍微改寫一下文法：
* 如果原本的起始符號是S，我們會加入新的符號S’當作起始符號，並且加入production S’ → S以維持文法的正確。
* 這個動作稱作Augmented grammar，能夠幫助accept的檢測。

#### Closure Operation

* 第一個要介紹的運算動作是Closure，概念和CH3.的closure有些類似。
* 設I是一個item的集合，則closure(I)也是一個item的集合，它從I建立出來：
1. 將所有I裡面的item加入到closure(I)。
2. 如果A → α⋅Bβ存在於closure(I)之中，且存在B → γ這個production，將B → ⋅γ加入到closure(I)。
3. 重複至沒有新的item可以被加入。

---
* 範例：
* E’ → E
* E → E + T
* E → T
* T → T * F
* T → F
* F → (E)
* F → id
* 求closure({E’ → E })
1. 將自己本身先加入
* E’ → ⋅E
2. 將E在左邊的productions也加入
* E → ⋅ E + T
* E → ⋅ T
3. E加入過了因此跳過；將T在左邊的productions加入
* T → ⋅ T * F
* T → ⋅ F
4. T加入過了因此跳過；將F在左邊的productions加入
* F → ⋅(E)
* F → ⋅ id }

#### Goto Operation

* 第二個是Goto，該運算需要用到Closure。
* 設I是items的集合、X是一個文法中的symbol，則goto(I,X)是在 `A → α⋅Xβ` 存在於I的前提之下，所有item`A → αX⋅β`的closure。
* 簡單來說就是如果輸入符號就是點的下一個符號，點就可以往前。
* 記得最後要做closure。

---
* 範例：
* E’ → E
* E → E + T
* E → T
* T → T * F
* T → F
* F → (E)
* F → id
* 求goto({E’ → E ⋅, E → E ⋅ + T }, +)
* 點的下一步是`+`的是E → E ⋅ + T，因此做closure({E → E + ⋅ T})。
* 記得將點往下移。
* closure ({E → E + ⋅T }) =
* E → E + ⋅T
* T → ⋅ T * F
* T → ⋅ F
* F → ⋅(E)
* F → ⋅ id

#### Set-of-Items Construction

* 學會Closure和Goto之後，我們離建立SRL的parser table已經只差一點了。
* 接下來我們要使用Closure和Goto將item們分組，分好之後一個一個的組別就會是之後table的狀態。
* 演算法：
1. 設C = { closure(S’→ ⋅S) }
2. C裡面每個item集合 I 和該文法每個symbol X 做 goto(I, X)
3. 如果goto的結果不在C之中，將其加入C
4. 直到每個items集合都被加入C

---
* 警告，接下來雖然看起來很多，但其實不難，耐住性子慢慢看就懂了。
* 範例：
* E’→ E
* E → E + T
* E → T
* T → T * F
* T → F
* F → (E)
* F → id
* I0 = closure(E’→ E)
* E’→ ⋅E
* E → ⋅ E + T
* E → ⋅ T
* T → ⋅ T * F
* T → ⋅ F
* F → ⋅(E )
* F → ⋅ id
* goto(I0, E) =
* E’ → E ⋅
* E → E ⋅ + T
* 新的item set，設為I1
* goto(I0, T) =
* E → T ⋅
* T → T ⋅ * F
* 新的item set，設為I2
* goto(I0, F) =
* T → F ⋅
* 新的item set，設為I3
* goto(I0, “(“) =
* F → (⋅ E )
* E → ⋅ E + T
* E → ⋅ T
* T → ⋅ T * F
* T → ⋅ F
* F → ⋅(E )
* F → ⋅ id
* 新的item set，設為I4
* goto(I0, id) =
* F → id ⋅
* 新的item set，設為I5
* I0跑完了，接著就跑I1。
* 接下來就不打了，直上一圖流：

#### Constructing an SLR Parsing Table

* 學了那麼多的運算，我們現在終於可以開始建立Parsing Table了。
* 演算法：
1. 設C = {I0, I1, ..., In} 所有的item集合。
2. 對於每個狀態Ii
1. 如果存在A → α⋅aβ ∈ Ii 且 goto(Ii, a) = Ij，則 action[i, a] = shift j
* 如果藉由輸入轉移到其他狀態，做shift
2. 如果存在A → α⋅ ∈ I，則 action[i, a] = reduce A → α ∀a ∈ FOLLOW(A)
* 如果點在最後面，在遇到FOLLOW的符號時做reduce
3. 如果存在S’ → S⋅ ∈ I，則action[i, $] = accept
* 如果是起始符號的結尾，在遇到結尾符號時宣告accept
3. 如果 goto(Ii , A) = Ij，則goto[i, A] = j
* 如果是輸入nonterminal時進行轉移，就放置於goto的地方(table右邊)
4. 找到包含S’ → ⋅S這個item的state當作起始狀態
* 可以的話，請花點時間試試看，自行根據文法推出FOLLOW、Set-of-Items，最後得到Parsing Table。

---
* 再來一個範例，你可能會發現一些問題。
* (0) S’ → S
* (1) S → L = R
* (2) S → R
* (3) L → *R
* (4) L → id
* (5) R → L
* 這邊我們就直接上圖了，不多花時間在解釋如何找狀態：
* 接著，我們關注在`goto(I0, L)裡面的R → L⋅` 以及`goto(I2, "=") = I6`這兩行上面。
* 將這兩行填入table中，你會發現變成這樣：
* 注意到同一個格子出現了兩個元素！
* 我們在更仔細觀察I2：
* S → L ⋅ = R
* R → L ⋅
* 如果輸入是 L = R，會因為`R → L ⋅`而導致reduce成 R = R。
* R應該在右邊，因此這個SLR發生錯誤了。
* 這時候就代表我們需要更多資訊去處理這個問題。

#### LR(1)

* 現在我們不使用SLR，因為它無法辨識某些語言(即便它很簡單)。現在我們改成使用LR(1)。
* item的樣子變為`[A →α ⋅ β, a]`
* a是我們預先讀入的輸入，稱做lookahead。
* lookahead其實只有在β = є的時候有用。
* 出問題的地方是reduce，而reduce只有點在最後面才會出現。
* [A →α ⋅, a] 只會在symbol為a的地方進行reduce。
* 和前面的方法比較，前面是所有FOLLOW(A)都會reduce。

#### Set-of-Items Construction Ver. LR

* 將原本的item們分組加上lookahead。
* 大致上步驟都一樣(使用goto)，但是closure的部分需要加上lookahead。
* 原本是看到A → α⋅Bβ且擁有B → γ就將B → ⋅γ加入
* 更改為看到[A → α⋅Bβ, a]且擁有 B → γ 就將 [B → ⋅γ, b]加入。
* 其中b是FIRST(βa)
* goto的操作則是直接保留lookahead即可。
* 好像有點難理解，我們實際跑一次範例看看會比較清楚。

---
* 範例：
* S’ → S
* S → CC
* C → cC
* C → d
* I0 = closure({[S’ → S, $]})
* 一開始lookahead為$。
* S’ → ⋅S, $
* 先將自己加入。
* S → ⋅ CC, $
* 將S開頭的加入，lookahead是FIRST(є$) = $
* є是因為`S’ → ⋅S`中，S後面沒東西。
* C → ⋅ cC, c/d
* 將C開頭的加入，lookahead是FIRST(C) = c, d
* C → ⋅ d, c/d
* 同上
* 簡單來說，lookahead就是點移動之後再後面一個symbol的FIRST，若是空的就放原本的lookhead。
* 剩下的狀態一樣直接一圖流附上：

#### Construction of the LR Parsing Table

* 再來建表的部分就很簡單啦，因為99%都和前面一樣。
* 差別只有在點在最後面的時候：
* 原本是在所有FOLLOW的地方都做reduce。
* 現在是在所有lookahead的地方做reduce。
* 剛剛那題的表格，大家可以建好之後比較看看有沒有錯誤：

### LALR

* 剛剛的SLR有一點點的缺點，就是它的狀態數太多了。
* 仔細觀察剛剛那題，你會發現I3和I6、I4和I7的前面都長得一模一樣，只差在後面的lookahead。
* 前面重複的部分稱呼為core。
* 那麼，我們是不是可以藉著合併這些狀態達到狀態縮減呢？
* 使用Lookahead LR (LALR)。

#### Construction of the LALR Parsing Table

* 建立LALR的Parsing Table很簡單，我們只需要直接將LR table中所有core相同的狀態合併就好了。
* 怎麼合？就真的直接合：
* 不是我要偷懶，這個我也不知道要怎麼講，就真的合在一起而已。
* 合併後的好處是狀態變少；壞處是會變得較晚發現錯誤，但一定還是會發現。
* 壞處的影響不太，因此LALR很常使用。
* 如果LR找不到一樣的core，那該文法還算是LALR嗎？
* 算是，只是table和LR長得一模一樣。
* LALR包含LR。

### Conflicts

* 當你合併之後，是有可能出現衝突的。
* 不會出現shift-reduce衝突，因為兩者的core必定不同。
* 但可能出現reduce-reduce衝突。
* 舉個簡單的例子：
* S’ → S
* S → aAd | bBd | aBe | bAe
* A → c
* B → c
* 建好table之後，合併時你會發現同一個格子出現兩個動作。
* 

---
* 所有的ambiguous文法都會產生衝突(shift-reduce或是reduce-reduce)導致LR失敗，但是這樣的文法很好用、很直覺。
* 因此，比較好的做法並不是改寫文法，而是想辦法處理衝突。
* 給予優先度是個好做法。

---
* 例子：
* (0) E’ → E
* (1) E → E + E
* (2) E → E * E
* (3) E → (E)
* (4) E → id
* 這是很常見的運算式文法，我們習慣上會希望乘法優先於加法。
* 這是其中出現E + E 和 E * E的部分：
* I7:
E → E + E ⋅
E → E ⋅ + E
E → E ⋅ * E
* I8:
E → E * E ⋅
E → E ⋅ + E
E → E ⋅ * E
* 則最後的table應該長這樣：
* 乘法優先度較高，因此I8總是reduce而I7遇到`*`則是會先shift。

---
* 下一個例子也是很常見的文法：
* (0) S’ → S
* (1) S → iSeS
* (2) S → iS
* (3) S → a
* 也就是我們程式中的if else文法。
* 這個文法的衝突在於else不知道要和誰匹配，所以同時出現reduce和shift。
* 習慣上我們選擇比較近的if去匹配，因此是shift優先。
* 不知道為什麼是shift可以看下圖的I4，shift才會把else給shift進stack中。
* 

### Operator-Precedence Parsing

* 最後介紹的這個parser是一個特別的parser，它專門用於處理operator的文法。
* 在這裡operator grammars定義為：不能有任何production的右側出現є或是兩個鄰近的nonterminals。
* 例如：
* E → E + E | E - E | E * E | E / E | (E ) | -E | id
* 就是一個operator grammar。
* E → EAE | (E ) | -E | id
* A → + | - | * | /
* 就不是一個operator grammar。
* 優點是很簡單、容易實作。
* 缺點有以下幾個：
* 負號很麻煩，因為減號和負號長得一模一樣。
* 少數明明就符合文法的句子它不會accept。
* 適用的文法很少。

---
* Operator-Precedence Parsing擁有三種優先度關係：
* a <⋅ b
* b 優先於 a
* a ≐ b
* a和b優先度相等
* a ⋅> b
* a 優先於 b
* 我們將所有Operator的優先度畫成一個對應表格：
* 然後在輸入進來時，我們只須按照表格將符號插入到句子之間就好了。
* 演算法：
* 從左邊開始掃描輸入，直到遇到第一個⋅>
* 然後往回掃描所有≐，直到遇到<⋅
* 將<⋅ ⋅> 之間的所有內容reduce
---
* 範例 w = id + id * id
* $ <⋅ id ⋅> + <⋅ id ⋅> * <⋅ if ⋅> $
* 先將箭頭按照表格放入
* $ <⋅ id ⋅> + <⋅ id ⋅> * <⋅ id ⋅> $
* $ <⋅ E + <⋅ id ⋅> * <⋅ id ⋅> $
* $ <⋅ E + <⋅ E * <⋅ id ⋅> $
* $ <⋅ E + <⋅ E * E ⋅> $
* $ <⋅ E + E ⋅> $
* $ E $

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