英文:
Recursive Lisp parser with Ocaml Opal
问题
我正在尝试使用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)")时，这个解析器工作得很好。
然而，我尝试递归地解析S表达式，通过简单地修改我的expr函数为：
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。
但我不确定如何修复这个问题。有什么想法吗？
英文:
I'm trying to write a simple Lisp parser with OCaml Opal:
This is my AST:
type atom = Num of int | Ident of string [@@deriving show]
type sexp = Atom of atom | ListSexp of sexp list [@@deriving show]
And this is the parser:
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!"
This works ok when I try to parse Parser.parse_expr (LazyStream.of_string "(5 3 abc)")
However, the next thing I tried is to parse S-Expressions recursively by naively modifying my expr function to:
let rec expr = parens (sep_by (atom <|> expr) space)
And this produces an error:
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
This seems ok since atom function returns char input -> (sexp * char input) option while expr function returns char input -> (sexp list * char input) option.
But I'm not sure how can to fix this. Ideas?
答案1
得分: 2
你需要将 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
英文:
You need to wrap sexp lisp in a ListSexp constructor so that it can be of type sexp, otherwise you have two conflicting types, sexp which is either an Atom or a ListSexp, and sexp list.
You tested the following, and it works:
let rec expr input =
(parens (sep_by (expr <|> atom) space) => fun l -> ListSexp l) input
But I think an expression is not always a list, in EBNF notation I would write:
EXPR := ATOM | "(" EXPR* ")"
So maybe something like this instead?
let rec expr input =
(parens (sep_by expr space) => (fun l -> ListSexp l) <|> atom) input
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论