使用OCaml Opal实现递归Lisp解析器遇类型不兼容问题求助

问题根源 #

你遇到的类型错误是因为expr原本返回的是解析sexp list的解析器，而递归组合时atom <|> expr要求两边都是返回单个sexp的解析器，类型不兼容导致报错。

修复步骤 #

1. 调整expr的返回类型，统一为单个sexp
   把括号内解析出的sexp list用ListSexp构造器包装成单个sexp，让expr和atom的类型对齐：

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

   这样expr的类型就变成了char input -> (sexp * char input) option，和atom完全一致，可以正常用<|>组合。

2. 修正parse_expr的处理逻辑
   现在expr返回的是单个sexp，不再是列表，所以要修改打印逻辑：

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

3. 修复ident的潜在问题
   原来的many alpha_num会匹配空字符串，导致解析出空标识符，改成many1 alpha_num确保标识符至少有一个字符：

   let ident = many1 alpha_num => implode => fun i -> Atom (Ident i)
   

测试验证 #

现在解析嵌套表达式比如：

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

会输出正确的嵌套S表达式结构，类型错误彻底解决。

内容的提问来源于stack exchange，提问作者Branislav Lazic