CODEWITHSUNDEEP
scalaparser-combinatorsleft-recursion
Martin Studer
Martin Studer

Reputation: 2321

Scala PackratParsers (parser combinators) and left-associativity

I'm using Scala's PackratParsers (parser combinators) with a left-recursive grammar of the following form

lazy val expr: PackratParser[Expr] = (
    ...
  | expr ~ (":" ~ expr).+ ^^ {
      case expr ~ rest => (expr /: rest)(combineBinary)
    }
  | ...
)

def combineBinary(acc: Expr, next: String ~ Expr) = next match {
  case op ~ expr => FunctionCall(op, acc, expr)
}

I would like the binary operator ":" to be left-associative such that expressions of the form x1:x2:...:xn will be parsed as (((x1:x2):x3):...:xn), i.e. leading to an AST of the form FunctionCall(":", FunctionCall(":", FunctionCall(":", x1, x2), x3), ...).

Surprisingly, with a PackratParsers grammar as defined above, the resulting AST is still right-associative. Why is that the case and what can be done to change that?

I found this discussion about Scala parser combinators and operator associativity but it doesn't seem to give an answer to my problem here.

Upvotes: 2

Views: 804

Answers (1)

Valentin Tihomirov
Valentin Tihomirov

Reputation: 1

tl; dr I do not know how packrat can save you from two big issues that you have. It did save me from stackoverflow but I did not have such blatant left recusion.

I mean that your recursion expr + expr should never terminate. I understand that you have some base of induction somewhere, i.e. expr = expr + expr | term.

Now, you can easily make right associativity by term + expr | term for right associative because when last term is found, you are deep under + recursion. Similarly, you make left associativity expr + term | term. Left associative causes left recursion and you are never at the final term. Even packrat does not save from it. I do not understand how you get your results. Mine 

object EP extends JavaTokenParsers with PackratParsers {
    def expr: Parser[_] = expr ~ ("+" ~> expr) | ident /*^^ {
          case ident ~ rest => (ident /: rest){case (acc, e) => acc + s" + (${e.toString})"}
    } | ident*/
}
List("a", "a + b", "a + b + c+ d") foreach {input => 
    println("left: " +  EP.parseAll(EP.expr, input))
}

stack overflows. It saved me once but I did not have such blatant left recusion. And, I do not know how can it save you from the second issue that you ask.

Anyway, you have to eliminate the recursion changing expr + term | term to

def left: Parser[_] = ident ~ appendix 
def appendix = "+" ~> left | ""

But this is however the right recursion again because we see the ident is the first node again.

Solution: You therefore simply use what all people do: use rep parser, which provides you a list, iterable from the left:

def right: Parser[_] = ident ~ ("+" ~> right) ^^ {case head ~ tail => s"Right($head, $tail)"} | ident 
lazy val left: Parser[_] = ident ~ rep("+" ~> ident) ^^ 
    {case head ~ tail => (head /: tail){case (acc, expr) => s"Left($acc, $expr)"}}

println("right => " + parseAll(right, "a + b + c+ d"))
println("left => " + parseAll(left, "a + b + c+ d"))

produces

right => [1.13] parsed: Right(a, Right(b, Right(c, d)))
left => [1.13] parsed: Left(Left(Left(a, b), c), d)

Upvotes: 1

Related Questions