Debugging Angstrom (or parser combinators in general)

Learning
,
1

Hello.

I’m trying to debug a parser that I wrote, but I have no idea how to do it. Is there any resource that I can read upon on about how to debug a parser written with combinators?

My current issue is about (I think) a left recursive grammar, but not sure how to solve it. The grammar is simple lambda calculus with variables, lambdas, and applications. Currently I have

let alpha =
  take_while1 (fun c ->
    match c with
    | 'a' .. 'z' | 'A' .. 'Z' -> true
    | _ -> false)
;;
let parse_var = ws *> alpha >>| fun x -> IRVar x

let expr : ir_term t =
  fix (fun expr ->
    let lambda =
      lrstring "lambda" *> alpha
      >>= fun arg -> lrchar '.' *> expr >>| fun e -> IRAbs (arg, e)
    in
    let p1 = choice [ parens expr; lambda; parse_var ] in
    let appl = p1 >>= fun e1 -> ws *> p1 >>| fun e2 -> IRApp (e1, e2) in
    appl <|> p1)
  <* sc
  <* ws
;;

If you’re curious you can find definitions of helper functions in this post. The current code works fine with this input:

(lambda x. x) (lambda x. x x);

Problem arises when I have more than 2 lambdas nested

lambda s. lambda n. lambda m. n m s;

The result of this comes out as

(Ast.IRAbs ("s",                    
   (Ast.IRAbs ("n",
      (Ast.IRApp (
         (Ast.IRAbs ("m", (Ast.IRApp ((Ast.IRVar "n"), (Ast.IRVar "m"))))),
         (Ast.IRVar "s")))
      ))
   ))

Which is wrong… I have no idea why this happens, since it works fine with 2 lambdas nested.

2

One debugging strategy is to test it on smaller expressions to identify where it goes wrong. Have you tried parsing n m s? (without the surrounding lambdas)

3

Interesting, I actually haven’t tried it, and I just did and it gave an end_of_input error, which means parser wasn’t able to parse anything… The problem should be on the logic where I parse application then

4

I found the problem. The p1 parser in the code

let p1 = choice [ parens expr; lambda; parse_var ] in

that is used to parse individual parts of application cannot be an application itself, thus it doesn’t work with m n s.

If I include appl recursively, the parser runs infinitely. Is there a way to solve this?

5

I would recommend to replace recursion by iteration (many combinator).

6

I actually solved this using chainl1 combinator:

let chainl1 e op =
  let rec go acc =
    (lift2 (fun f x -> f acc x) op e >>= go) <|> return acc in
  e >>= fun init -> go init

Now I have

let atom = choice [ parens expr; lambda; parse_var ] in
chainl1 atom app

where

let app = ws *> return (fun x y -> IRApp (x, y))

I found the use of chainl1 in Monadic Parsing Combinator article (pg. 24), and implementation of chainl1 in README of Angstrom