How to write recursive parsers? about cats-parse HOT 5 CLOSED

1. you don't need the defer(recurse) since recurse is already a value, the defer isn't doing anything.
2. op first has to parse recurse so that's your infinite loop.
3. I think your real question is how do you parse infix (or suffix operators).

A pattern I like is:

val nonOps: Parser[Expr] = subexp | lit
val operator: Parser[Expr => Expr] =
  (stringIn("+" :: "-" :: "*" :: "/" :: Nil), nonOps)
    .mapN { (op, right) =>
      { expr: Expr => Op(expr, op, right) }
    }

val result = Parser[Expr] = (nonOps ~ operator.rep0).map { case (init, ops) => ops.foldLeft(init) { (i, fn) => fn(i) }

result

So, you break the operator parsing apart. You have to be a bit more sophisticated if you want to get precedence correct.

from cats-parse.

What about having a deref[A](x: Reference[Parser[A]]): Parser[A] that derefs a parser in a Reference upon execution? If so we can first declare a list of References and then reassign the contents of them (where we can freely cross reference).

from cats-parse.

How is that different than defer?

The issue is that you still have to be careful to make some progress before doing recursion. Otherwise you set up an infinite loop.

from cats-parse.

Oh sorry - didn't read the API thoroughly. I think maybe we can explain how to deal with left recursion in README?

from cats-parse.

@johnynek Thanks for the response. That did answer my question but revealed that I need to learn a lot more about the complexities of parsers. I'll close this issue.

from cats-parse.