3.分開Lexical 與 Syntax的理由

• 簡單：兩者的工作內容不同，分開降低複雜度
• 效率：分開使Lexical 可優化
• 可移動性：Lexical 與IO及記憶體讀取有關，屬於platform dependent，而parser並無

4.lexical analyzer

• 讀入各種lexeme並賦予這些lexeme一個token ID。
• lexeme是拆分後的字詞
• 每次只讀入一個字元，利用一個 state machine\table去確認是否合法
• state table：人工建立表，建立lexeme集合，並比對表來確認合法與否
• state machine：定義規則，並遵循規則lexeme才合法
• 比如在C語言，變數首字不能為數字
• token是一個抽象概念的集合，比如識別字集合、加法符號集合

 5.Parsing

• 當成功拆分字串中的字為字詞，並將所有字詞歸類為對應的抽象概念後，便能開始分析字詞出現的順序與文法是否符合標準。Parsing便是分析文法的行為。
• 因往往無法馬上挑出正確的Paring tree，Parsing 的過程是相當緩慢的，一個沒優化的Parser通常要O (n^3)的時間。
• Recursive-Descent Parsing：使用遞迴，對於一個非終結字元，不斷窮舉可替換規則。
• 可分為Top Down 與 Bottom up的parsing
• Top Down ：由根至葉，將已定義的規則由上至下擴增(把左項擴增為右項)
• Bottom up ：由葉至根，用以定義的規則從下往上化簡(把右項化簡成左項)

• LL Parser ：Top Down 實做的Parser

對讀入的字串，從最左邊看到最右邊，並先挑選最左邊的非終結字元做代換。
不過，這樣會產生 Recursive的問題，如 A → A + B，因為A總是在最左側，導致A不斷的被替換，即是A不斷的呼叫自己。在實做上，可以透過修正語法來解決這個問題，比方將位於最左側與不位於最左側的非終結字元分開處理。

A → Aα1 | … | Aαm | β1 | β2 | … | βn 

↓

A → β1A’ | β2A’ | … | βnA’
A’ → α1A’ | α2A’ | … | αmA’ | ε

兩者可產生出相同的葉，因為原式最終在前的必定是 β1 | β2 | … | βn ，餘下α1 | … | αmA。
然而，因為A'存在ε (空字串)，可以避免無窮迴圈的問題。

再從效率上來看，假設代換規則後第一個字的集合為F，比方：

A → aB | bAb | Bb

B → cB | d

A可換為：aB | bAb | (cBb | db) ，得到第一個字的集合F：{a},{b},{c,d}，再比方：

A → aB | BAb
B → aB | b

A可換為：aB | (aAb | bAb) ，得到第一個字的集合F：{a},{a,b}

我們發現，第一個情形三個集合沒有任何交集(disjointness)，而第二個情形卻產生的交集a，從遍歷一棵樹的角度來看，我們應希望各個規則沒有交集，也就是第一種情形，這樣在尋找規則上更加明確，從而降低走錯路的機率。可透過Left factoring減少各個規則間的交集。

• LR Parser ：Bottom up 實做的Parser

對讀入的字串，從最左邊看到最右邊，每次從Leaf走回去時，優先挑選最右邊的節點。