使用 Ocaml Opal 的递归 Lisp 解析器

Question

我正在尝试使用 OCaml Opal 编写一个简单的 Lisp 解析器：

这是我的 AST：

type atom = Num of int | Ident of string [@@deriving show]
type sexp = Atom of atom | ListSexp of sexp list [@@deriving show]

这是解析器：

open Opal
open Ast

let integer = many1 digit => implode % int_of_string => fun n -> Atom (Num n)
let ident = many alpha_num => implode => fun i -> Atom (Ident i)
let parens = between (token "(") (token ")")
let atom = integer <|> ident
let expr = parens (sep_by atom space)

let parse_expr input =
  match parse expr input with
  | Some ans -> List.iter (fun a -> Printf.printf "%s" (show_sexp a)) ans
  | None -> print_endline "ERROR!"

当我尝试解析时，这工作正常

Parser.parse_expr (LazyStream.of_string "(5 3 abc)")

但是，我尝试的下一件事是通过天真地修改我的

expr

函数来递归地解析 S 表达式：

let rec expr = parens (sep_by (atom <|> expr) space)

这会产生一个错误：

8 | let rec expr = parens (sep_by (atom <|> expr) space)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Error: This expression has type char input -> (sexp list * char input) option
       but an expression was expected of type
         char input -> (sexp * char input) option
       Type sexp list is not compatible with type sexp 

这似乎没问题，因为

atom

函数返回

char input -> (sexp * char input) option

而

expr

函数返回

char input -> (sexp list * char input) option

。

但我不知道如何解决这个问题。有想法吗？

Answer 1

您需要将

sexp lisp

包装在

ListSexp

构造函数中，以便它可以是

sexp

类型，否则您将有两个冲突的类型，

sexp

，它是

Atom

或

ListSexp

，以及

 sexp list

。

您测试了以下内容，它有效：

let rec expr input = 
  (parens (sep_by (expr <|> atom) space) => fun l -> ListSexp l) input

但我认为表达式并不总是列表，用 EBNF 表示法我会写：

EXPR := ATOM | "(" EXPR* ")"

那么也许可以用这样的东西代替？

let rec expr input =
  (parens (sep_by expr space) => (fun l -> ListSexp l) <|> atom) input