Definition. 左遞迴 [cs-000A]
Definition. 左遞迴 [cs-000A]
左遞迴是我們定義文法的時候會出現的一種形式，比如
翻譯成遞歸下降解析器時會有像下面這樣的程式
def expr : Parsec E :=
let l <- expr
match '+'
let r <- expr
return E.add l r
這時候 expr 顯然是一個非終止的發散函數，而因為遞迴的原因是運算式的左邊，所以被稱為左遞迴。這樣的 infix 運算形式在文法中很常見，所以我們需要方法來消除文法中的左遞迴。
Definition. Parser combinator [cs-000B]
Definition. Parser combinator [cs-000B]
解析器組合子（parser combinator）最早來自論文 A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time， 在現在的使用中因為不同語言特性跟 parser combinator 指涉的比較像是一種程式方法的情況下，本文中的 parser combinator 是單純指把 parser 跟 higher order function 結合的一種程式方法。這個方案最大的好處就是遞歸下降解析跟程式寫法一一對應，因此相當直覺。
消除左遞迴的方法 [cs-000C]
消除左遞迴的方法 [cs-000C]
現在你知道為什麼我們需要了解遞歸下降解析中消除左遞迴的方式，以下面文法來說
我們可能會將定義改成
這個解法在對應的 parser combinator 中看起來像是
mutual
def term := parse_int <|> parens expr
def expr : Parsec E :=
let l <- term
match '+'
let r <- term
return E.add l r
end擴展到 operator 優先序問題 [cs-000D]
擴展到 operator 優先序問題 [cs-000D]
上面的方法解決了左遞迴問題，但是要是有多個不同優先級的運算形式就會讓文法快速膨脹
這樣單調的修改在文法裡面確實很無聊，不過只要仔細觀察對應的 combinator，就會它們的型別發現這告訴了我們要怎麼利用 higher order function 來解決重複的問題！對 infix 運算形式（左結合）來說，通用的程式是
def infixL (op : Parsec (α → α → α)) (tm : Parsec α) : Parsec α := do
let l ← tm
match ← tryP op with
| .some f => return f l (← tm)
| .none => return l
這個 combinator 先解析左邊的 lower tm ，接著要是能夠解析 op 就回傳 op combinator 中存放的函數，否則就回傳左半邊的 tm 結果。使用上就像這樣
mutual
def factor : Parsec Expr
def expr : Parsec Expr :=
factor
|> infixL (parseString "*" *> return Expr.mul)
|> infixL (parseString "+" *> return Expr.add)
end
- 其中
parseString是個假設會進行 whitespace 過濾並 match 目標字串的 combinator Expr.mul跟Expr.add的型別被假設為Expr → Expr → Expr
這裡真正發生的就是使用組合子編碼了文法的層級，其中每個規則都被記錄成匿名函數，我們無需再另外命名。
處理優先度相同的運算子 [cs-000E]
處理優先度相同的運算子 [cs-000E]
因為有些運算子優先級相同，所以我們還需要再修改上面的函數來正確的支援這個概念；而且上面的程式為了避免複雜化，只解析一次 operator 加上 tm 就退出了，會導致實際上 1 + 2 * 3 * 4 這種算式的 * 4 部分沒有被解析。要解決這個問題，我們需要貪婪解析右半邊 op tm 的部分。綜上所述我們得到的程式碼是
def infixL (opList : List (Parsec (α → α → α))) (tm : Parsec α)
: Parsec α := do
let l ← tm
let rs ← many do
for findOp in opList do
match ← tryP findOp with
| .some f => return (f, ← tm)
| .none => continue
fail "cannot match any operator"
return rs.foldl (fun lhs (bin, rhs) => (bin lhs rhs)) l
首先我們有一串 operator 而非一個，其次在右邊能被解析成 op tm 時都進行解析，最後用 foldl 把結果轉換成壓縮後的 α
我希望這次有成功解釋怎麼從規則對應到 parser combinator，所以相似的規則可以抽出相似的 higher order function 來泛化，讓繁瑣的規則命名變成簡單的函數組合。這個技巧當然不會只有在這裡被使用，只要遇到相似形的文法都可以進行類似的抽換，相似的型別簽名可以導出通用化的關鍵。
Appendix. 其他 expression combinator [cs-000F]
Appendix. 其他 expression combinator [cs-000F]
在這裏提到的所有程式都實作在我幫 lean 寫的一個解析器擴充程式庫 https://git.sr.ht/~dannypsnl/parsec-extra 中
右結合的 infix
partial def infixR (opList : List (Parsec (α → α → α))) (tm : Parsec α)
: Parsec α := go #[]
where
go (ls : Array (α × (α → α → α))) : Parsec α := do
let lhs ← tm
for findOp in opList do
match ← tryP findOp with
| .some f => return ← go (ls.push (lhs, f))
| .none => continue
let rhs := lhs
return ls.foldr (fun (lhs, bin) rhs => bin lhs rhs) rhs
prefix op tm
def «prefix» (opList : List $ Parsec (α → α)) (tm : Parsec α)
: Parsec α := do
let mut op := .none
for findOp in opList do
op ← tryP findOp
if op.isSome then break
match op with
| .none => tm
| .some f => return f (← tm)
postfix op tm
def «postfix» (opList : List $ Parsec (α → α)) (tm : Parsec α)
: Parsec α := do
let e ← tm
let mut op := .none
for findOp in opList do
op ← tryP findOp
if op.isSome then break
match op with
| .none => return e
| .some f => return f e