是否可以在 OCaml 中编写递归单子解析器？ [已关闭]

Question

假设我们要解析这样的表达式：

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

在 Haskell 中，我们可以编写一个像这样的解析器

exp = mul
mul = do
   foo <- add
   bar <- many (char '*' >> add)
   return -- something
add = do
   foo <- literal
   bar <- many (char '-' >> literal)
   return -- something
literal = number <|> do
   _ <- char '('
   x <- exp
   _ <- char ')'
   return x

但是在ocaml中，“相同”的代码是这样的：

let rec exp = mul
and mul = (* ... *)
and add = (* ... *)
and literal = (* ... *) 

会导致编译错误

这种表达式不允许作为 let rec 的右侧

我明白这是因为ocaml中急切的评估。现在我想出了两个解决方案，但都不像 Haskell 那样干净。

let rec exp input = mul input (* the first one is to write the state as param explicitly, which is not monadic *)
and (* ... *)

let rec exp = lazy (Lazy.force mul) (* the second one is to mark every parser as lazy, which produces a lot of verbose code *)
and (* ... *)

因此，我想知道是否有一种干净的（即不要重复太多）方法在ocaml中编写递归monadic解析器？如果没有，是否有一些推荐的方法来手动编写干净的解析器？

Answer 1

计算开始时的暴露是干净还是混乱，这确实是一个品味问题。因此，您的第一个解决方案对我来说似乎大部分都很好，因为它只是清楚地说明计算仅在提供输入后才开始。

尽管如此，大多数 OCaml 解析器组合器库还将公开一个

fix

 组合器来帮助表达这些递归定义。 例如，以埃：

open Angstrom
let number = map ~f:int_of_string @@ take_while1 (function '0'..'9' -> true | _ -> false)
let exp = fix (fun exp ->
  let literal = number <|> (char '(' *> exp <* char ')') in
  let mul =
    let* left = literal in
    let+ rest = many (char '*' *> literal) in
    List.fold_left ( * ) left rest
  in
  let add =
    let* left = mul in
    let+ rest = many (char '+' *> mul) in
    List.fold_left ( + ) left rest
  in
  add
)

最后，按照 EBNF 语法编写此类解析器的更自然的方法可能是使用 menhir：

%token <int> INT
%token PLUS MUL LPAR RPAR EOF
%start <int> expr

%%

expr:
| t = term EOF { t }

simple_expr:
| i=INT { i }
| LPAR e=expr RPAR { e }

term:
| f=factor o=option(PLUS t=term {t}) { f + Option.value ~default:0 o }

factor:
| s=simple_expr o=option(MUL f=factor {f}) { s * Option.value ~default:1 o }

虽然有点长，但保证实现指定的语法（并且在语法不明确的情况下会发出警告）。