# Debugging Angstrom (or parser combinators in general)

**URL:** <https://discuss.ocaml.org/t/debugging-angstrom-or-parser-combinators-in-general/13741>\
**Category:** Learning\
**Tags:** angstrom, parsing\
**Created:** [December 29, 2023, 7:34am UTC](https://discuss.ocaml.org/t/debugging-angstrom-or-parser-combinators-in-general/13741 "2023-12-29T07:34:32Z")\
**Posts on this page:** 6\
**Page:** 1

<div class="post-metadata">

**Author:** ![m-spitfire](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/m-spitfire/32/4965_2.png) [@m-spitfire](https://discuss.ocaml.org/u/m-spitfire)\
**Post date:** [December 29, 2023, 7:34am UTC](https://discuss.ocaml.org/t/debugging-angstrom-or-parser-combinators-in-general/13741/1 "2023-12-29T07:34:32Z")

</div>

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

```ocaml
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](https://discuss.ocaml.org/t/parsing-simple-recursive-expressions-with-angstrom/13734). The current code works fine with this input:

```auto
(lambda x. x) (lambda x. x x); 

```

Problem arises when I have more than 2 lambdas nested

```auto
lambda s. lambda n. lambda m. n m s; 

```

The result of this comes out as

```auto
(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.

---

<div class="post-metadata">

**Author:** ![art-w](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/art-w/32/4728_2.png) [@art-w](https://discuss.ocaml.org/u/art-w)\
**Post date:** [December 29, 2023, 9:05am UTC](https://discuss.ocaml.org/t/debugging-angstrom-or-parser-combinators-in-general/13741/2 "2023-12-29T09:05:13Z")

</div>

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)

---

<div class="post-metadata">

**Author:** ![m-spitfire](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/m-spitfire/32/4965_2.png) [@m-spitfire](https://discuss.ocaml.org/u/m-spitfire)\
**Post date:** [December 29, 2023, 9:21am UTC](https://discuss.ocaml.org/t/debugging-angstrom-or-parser-combinators-in-general/13741/3 "2023-12-29T09:21:22Z")

</div>

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

---

<div class="post-metadata">

**Author:** ![m-spitfire](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/m-spitfire/32/4965_2.png) [@m-spitfire](https://discuss.ocaml.org/u/m-spitfire)\
**Post date:** [December 29, 2023, 9:27am UTC](https://discuss.ocaml.org/t/debugging-angstrom-or-parser-combinators-in-general/13741/4 "2023-12-29T09:27:21Z")

</div>

I found the problem. The `p1` parser in the code

```auto
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?

---

<div class="post-metadata">

**Author:** ![Kakadu](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/kakadu/32/1204_2.png) [@Kakadu](https://discuss.ocaml.org/u/Kakadu)\
**Post date:** [December 29, 2023, 9:33am UTC](https://discuss.ocaml.org/t/debugging-angstrom-or-parser-combinators-in-general/13741/5 "2023-12-29T09:33:24Z")

</div>

> [@m-spitfire](#):
>
> If I include appl recursively, the parser runs infinitely. Is there a way to solve this?

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

---

<div class="post-metadata">

**Author:** ![m-spitfire](https://sea2.discourse-cdn.com/flex020/user_avatar/discuss.ocaml.org/m-spitfire/32/4965_2.png) [@m-spitfire](https://discuss.ocaml.org/u/m-spitfire)\
**Post date:** [December 29, 2023, 9:45am UTC](https://discuss.ocaml.org/t/debugging-angstrom-or-parser-combinators-in-general/13741/6 "2023-12-29T09:45:18Z")

</div>

I actually solved this using `chainl1` combinator:

```auto
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

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

```

where

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

```

I found the use of `chainl1` in [Monadic Parsing Combinator](https://www.cs.nott.ac.uk/~pszgmh/monparsing.pdf) article (pg. 24), and implementation of `chainl1` in [README of Angstrom](https://github.com/inhabitedtype/angstrom)