Definition. 左遞迴 [cs-000A]

左遞迴是我們定義文法的時候會出現的一種形式，比如

Expr \to Expr + Expr

翻譯成遞歸下降解析器時會有像下面這樣的程式

def expr : Parsec E :=
  let l <- expr
  match '+'
  let r <- expr
  return E.add l r

這時候 expr 顯然是一個非終止的發散函數，而因為遞迴的原因是運算式的左邊，所以被稱為左遞迴。這樣的 infix 運算形式在文法中很常見，所以我們需要方法來消除文法中的左遞迴。

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]

現在你知道為什麼我們需要了解遞歸下降解析中消除左遞迴的方式，以下面文法來說

Expr \to Expr + Expr \\ \mid Int \\ \mid Expr

我們可能會將定義改成

Expr \to Term + Term \\ Term \to Int \mid Expr

這個解法在對應的 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]

上面的方法解決了左遞迴問題，但是要是有多個不同優先級的運算形式就會讓文法快速膨脹

Expr \to Term + Term \\ Term \to Factor * Factor \\ Factor \to Int \mid Expr

這樣單調的修改在文法裡面確實很無聊，不過只要仔細觀察對應的 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]

因為有些運算子優先級相同，所以我們還需要再修改上面的函數來正確的支援這個概念；而且上面的程式為了避免複雜化，只解析一次 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]

在這裏提到的所有程式都實作在我幫 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