OCaml中如何简洁编写递归Monadic解析器？求最优实现方案

我们要解析的表达式文法规则如下：

Exp := Mul
Mul := Add {'*' Add}
Add := Literal {'+' Literal}
Literal := number | '(' Exp ')'

在Haskell中，我们可以写出简洁的单子式解析器：

exp = mul
mul = do
   foo <- add
   bar <- many (char '*' >> add)
   return (foo, bar) -- 示例返回值
add = do
   foo <- literal
   bar <- many (char '+' >> literal)
   return (foo, bar) -- 示例返回值
literal = number <|> do
   _ <- char '('
   x <- exp
   _ <- char ')'
   return x

但在OCaml中尝试编写类似的递归绑定代码：

let rec exp = mul
and mul = (* ... 单子式实现 ... *)
and add = (* ... 单子式实现 ... *)
and literal = (* ... 单子式实现 ... *) 

会触发编译错误：

This kind of expression is not allowed as right-hand side of let rec

这是因为OCaml的严格求值特性，let rec仅允许右侧是可立即求值的构造器、函数或简单表达式，无法直接处理这种相互引用的非函数值绑定。

目前已知两种解决方案，但都不够简洁：

1. 显式传递状态参数，放弃单子式风格：

let rec exp input = mul input
and mul input = (* ... 显式处理input ... *)
and add input = (* ... 显式处理input ... *)
and literal input = (* ... 显式处理input ... *)

2. 给所有解析器标记lazy，冗余度高：

let rec exp = lazy (Lazy.force mul)
and mul = lazy (* ... 单子式实现 ... *)
and add = lazy (* ... 单子式实现 ... *)
and literal = lazy (* ... 单子式实现 ... *)

请问：是否存在更简洁（避免过多重复）的方法在OCaml中编写递归单子式解析器？如果没有，有没有手动编写简洁解析器的推荐方案？

1. 将解析器定义为函数，保留单子风格 #

OCaml的let rec ... and ...完全支持递归函数的相互引用，因此可以把解析器定义为接收输入状态并返回解析结果的函数，同时封装单子式的组合子（return、>>=、<|>等），这样既保持单子风格，又符合OCaml的语法限制。

首先定义基础的解析器类型和组合子：

type input = char list
type 'a parser = input -> ('a * input) option

(* 单子组合子 *)
let return x input = Some (x, input)
let bind p f input =
  match p input with
  | Some (x, rest) -> f x rest
  | None -> None
let (>>=) = bind

(* 选择组合子 *)
let (<|>) p q input =
  match p input with
  | Some _ as res -> res
  | None -> q input

(* 基础解析器 *)
let char c input =
  match input with
  | h::t when h = c -> Some (c, t)
  | _ -> None

(* 重复解析组合子 *)
let many p =
  let rec loop acc input =
    match p input with
    | Some (x, rest) -> loop (x::acc) rest
    | None -> Some (List.rev acc, input)
  in loop []

(* 假设number是解析整数的基础解析器 *)
let number input =
  match input with
  | h::t when Char.is_digit h -> Some (Char.code h - Char.code '0', t)
  | _ -> None

然后就可以用let rec ... and ...写出递归的单子式解析器：

let rec exp input = mul input
and mul input =
  add >>= fun foo ->
  many (char '*' >>= fun _ -> add) >>= fun bar ->
  return (foo, bar) input
and add input =
  literal >>= fun foo ->
  many (char '+' >>= fun _ -> literal) >>= fun bar ->
  return (foo, bar) input
and literal input =
  number <|> (
    char '(' >>= fun _ ->
    exp >>= fun x ->
    char ')' >>= fun _ ->
    return x
  ) input

这种写法仅需在每个解析器末尾加input参数，整体风格接近Haskell的单子式写法，且没有冗余的lazy包装。

2. 封装延迟求值辅助函数，简化lazy用法 #

如果不想把解析器写成函数，可以定义一个辅助函数来封装lazy的逻辑，减少重复代码：

(* 假设原来的单子解析器类型为parser_impl *)
type 'a parser = 'a Lazy.t parser_impl

let delay f = lazy (f ())

然后编写递归解析器时，仅需用delay包裹每个绑定的实现：

let rec exp = delay (fun () -> mul)
and mul = delay (fun () ->
  add >>= fun foo ->
  many (char '*' >>= fun _ -> add) >>= fun bar ->
  return (foo, bar)
)
and add = delay (fun () ->
  literal >>= fun foo ->
  many (char '+' >>= fun _ -> literal) >>= fun bar ->
  return (foo, bar)
)
and literal = delay (fun () ->
  number <|> (
    char '(' >>= fun _ ->
    exp >>= fun x ->
    char ')' >>= fun _ ->
    return x
  )
)

这种写法比手动写lazy (Lazy.force ...)简洁很多，仅需每个绑定加一层delay (fun () -> ...)。

3. 使用成熟的解析器组合子库 #

直接使用OCaml生态中的解析器组合子库（如Angstrom），这类库内部已经处理了递归绑定的延迟求值问题，可以像Haskell一样写出简洁的递归单子式解析器：

open Angstrom

let rec exp = mul
and mul =
  add >>= fun foo ->
  many (char '*' *> add) >>= fun bar ->
  return (foo, bar)
and add =
  literal >>= fun foo ->
  many (char '+' *> literal) >>= fun bar ->
  return (foo, bar)
and literal =
  int <|> (char '(' *> exp <* char ')')

Angstrom提供了丰富的组合子和优化，无需手动处理递归绑定的问题，是最简洁的方案。

内容的提问来源于stack exchange，提问作者Xiangzhi Liu