【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符合：
- $x y^{i} z \in A, i \geq 0$
- |y| > 0
- |xy|
  $\leq$ n
範例：證明
$L = {0^{n} 1^{n} | n \geq 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, Γ, δ, q_{0}, Z_{0}, F)$
- K: 總狀態的集合
- $\sum$ : 輸入字母集
- $Γ$ : stack的字母集
- $δ$ : 狀態轉移關係的集合
  - $δ$ (0, a, 0) = {1}，表示在狀態0看到a且stack是0的時候往狀態1跑。
- $q_{0}$ : 起始狀態(屬於K)
- $Z_{0}$ : 初始stack內的符號(屬於
  $Γ$ )
- F: 結束狀態的集合

練習題
建立語言

L = {0^{n} 1^{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 , є)

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

練習題
建立語言

L = {w c w^{R} | w \in {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 , є)

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

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:
  Image Not Showing Possible Reasons
  The image file may be corrupted
  The server hosting the image is unavailable
  The image path is incorrect
  The image format is not supported
  Learn More →

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
Image Not Showing Possible Reasons
- The image file may be corrupted
- The server hosting the image is unavailable
- The image path is incorrect
- The image format is not supported
Learn More →

改寫為新文法：
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 α$
- 例如：
  $A \to A α | β$
進行Derivation時，我們通常是用DFS的概念，如果第一項不能推導出輸入，則我們再選擇第二項
假設現在輸入為
$β α α$
我們從起始符號A開始推導
- $A \to A α$
- $A α \to A α α$
- $A α α \to A α α α$
- …
我們知道要該輸入只要選擇
$β$ 就能成功，但是因為無限迴圈造成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的前提之下，所有itemA → α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, 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 $