---
# System prepended metadata

title: 【Compiler】 Ch4. Syntax Analysis
tags: [compiler, note]

---

# 【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 , є)
![](https://i.imgur.com/EIxTP4y.png)

---
練習題
建立語言$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 , є)
 ![](https://i.imgur.com/wugn1Py.png)

## 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:
        ![](https://i.imgur.com/AWYdgzl.png)

### 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
![](https://i.imgur.com/BVu2MVG.png)

- 改寫為新文法：
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
![](https://i.imgur.com/KfFcxev.png)
* 每經過一條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: ![](https://i.imgur.com/rSZnerB.png)
* 初始化：在stack放入`$`當作結束符號，然後放入起始符號E開始parse；輸入字串的尾端也放入`$`當作輸入結束。
* 過程：![](https://i.imgur.com/u6MXb35.png)
---
* 然而，我們到底要怎麼得到這個神奇的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: ![](https://i.imgur.com/swOtGDt.png)
* 是否有發現什麼地方怪怪的？
    * 有一格同時出現兩個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的優先度，語法可能有好幾種結果:![](https://i.imgur.com/hbQUSlB.png)
    * 在第`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: ![](https://i.imgur.com/qERqb9a.png)
    * 左側為狀態、上面為symbol。
* 使用：查看input和stack頂端的狀態，去對照table的指示。
    * 指示會是一個英文字加上一個數字i。
    * 如果table的指示是s開頭，表示執行shift。
        * 將該input放入stack，並將i放入stack當下一個狀態。
    * 如果table的指示是r開頭，代表執行reduce。
        * 將stack內的symbol按照第i條production轉換為nonterminal，然後再次查表。
        * 查看轉換出來的nonterminal和現在的state，放入新的狀態。
* 結果：![](https://i.imgur.com/tpiMSx2.png)
    * 可能看文字不太好懂，上圖有附上完整過程，請多練習。

---
* 接下來要學習如何建立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。
* 接下來就不打了，直上一圖流：![](https://i.imgur.com/gOxK8P4.png)

#### 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
* 這邊我們就直接上圖了，不多花時間在解釋如何找狀態：![](https://i.imgur.com/KJWpcuy.png)
* 接著，我們關注在`goto(I0, L)裡面的R → L⋅` 以及`goto(I2, "=") = I6`這兩行上面。
* 將這兩行填入table中，你會發現變成這樣：![](https://i.imgur.com/9sz0zg8.png)
    * 注意到同一個格子出現了兩個元素！
* 我們在更仔細觀察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。
* 剩下的狀態一樣直接一圖流附上：![](https://i.imgur.com/SUGttCR.png)

#### Construction of the LR Parsing Table

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

### LALR

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

#### Construction of the LALR Parsing Table

* 建立LALR的Parsing Table很簡單，我們只需要直接將LR table中所有core相同的狀態合併就好了。
    * 怎麼合？就真的直接合：![](https://i.imgur.com/R5LyclC.png)
    * 不是我要偷懶，這個我也不知道要怎麼講，就真的合在一起而已。
* 合併後的好處是狀態變少；壞處是會變得較晚發現錯誤，但一定還是會發現。
    * 壞處的影響不太，因此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之後，合併時你會發現同一個格子出現兩個動作。
    * ![](https://i.imgur.com/uY6MUYQ.png)

---
* 所有的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應該長這樣：![](https://i.imgur.com/4v30n81.png)
    * 乘法優先度較高，因此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中。
* ![](https://i.imgur.com/Ya382PB.png)

### 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的優先度畫成一個對應表格：![](https://i.imgur.com/loDAJry.png)
* 然後在輸入進來時，我們只須按照表格將符號插入到句子之間就好了。
* 演算法：
    * 從左邊開始掃描輸入，直到遇到第一個⋅>
    * 然後往回掃描所有≐，直到遇到<⋅
    * 將<⋅ ⋅> 之間的所有內容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`