I write a ocaml program that parse an arithmetic expression by parser combinator.
type 'a parser = char list -> ('a * (char list)) list
let return (x: 'a): 'a parser = fun input -> [x, input]
let fail: 'a parser = fun _ -> []
let ( >>= ) (p: 'a parser) (f : 'a -> 'b parser): 'b parser =
fun input -> List.map (fun (x, i) -> f x i) (p input) |> List.flatten
let ( ||| ) (p: 'a parser) (q: 'a parser) =
fun input -> (p input) @ (q input)
let token: (char parser) = function
| x::xs -> [x, xs]
| [] -> []
let char(c: char): (char parser) =
token >>= fun x ->
if x = c then return x else fail
let digit: (char parser) =
token >>= fun x ->
if x >= '0' && x <= '9' then return x else fail
let rec many(p: 'a parser): 'a list parser =
(p >>= fun x ->
many p >>= fun xs ->
(return (x::xs)))
||| (return [])
let number =
many digit >>= fun x ->
return (List.fold_left (fun l r -> l * 10 + (int_of_char r - int_of_char '0')) 0 x)
type expr = Add of (expr * expr)
| Sub of (expr * expr)
| Mul of (expr * expr)
| Div of (expr * expr)
| Neg of expr
The code above works well.
let rec expression: expr parser =
term >>= fun l ->
(char '+' ||| char '-') >>= fun op ->
term >>= fun r ->
if op = '+' then return (Add (l, r)) else return (Sub (l, r))
and term: expr parser =
factor >>= fun l ->
(char '*' ||| char '/') >>= fun op ->
factor >>= fun r ->
if op = '*' then return (Mul (l, r)) else return (Div (l, r))
and factor: expr parser =
expression
||| (char '(' >>= fun _ ->
expression >>= fun e ->
char ')' >>= fun _ ->
return e)
||| (char '-' >>= fun _ ->
factor >>= fun e ->
return (Neg e))
But there is an error in this piece of code
Error: This kind of expression is not allowed as right-hand side of `let rec'
This page(link) says: "the compiler only allows three possible constructs to show up on the righthand side of a let rec: a function definition, a constructor, or the lazy keyword."
I think type parser is a function instead of a value, why this happened?
