Recursive Lisp parser with Ocaml Opal

Question

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?

a value of type sexp is either an Atom or a ListSexp, you produce Atom values for numbers and identifiers, but then you return sexp list directly, which is not of type sexp — coredump
– coredump, Commented Jul 31, 2023 at 12:22
You mean like this: let expr = parens (sep_by atom space) => fun l -> ListSexp l. I tried, but how to apply the function recursively on this? I got: ` 8 | let rec expr = parens (sep_by (atom <|> expr) space) => fun l -> ListSexp l ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ Error: This kind of expression is not allowed as right-hand side of let rec' error — Branislav Lazic
– Branislav Lazic, Commented Jul 31, 2023 at 12:23
@coredump Oh wow! Actually, I made it work. This: let rec expr input = (parens (sep_by (expr <|> atom) space) => fun l -> ListSexp l) input compiles and parses expressions recursively. You can make that an answer. — Branislav Lazic
– Branislav Lazic, Commented Jul 31, 2023 at 12:29

coredump · Accepted Answer · 2023-07-31 13:07:28Z

2

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

edited Jul 31, 2023 at 13:07

answered Jul 31, 2023 at 12:45

coredump

39.4k7 gold badges47 silver badges85 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Branislav Lazic Over a year ago

Yes. The second approach is better. The correct function would be: let rec expr input = (parens (sep_by expr space) => (fun l -> ListSexp l) <|> atom) input

Collectives™ on Stack Overflow

Recursive Lisp parser with Ocaml Opal

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related