# Rewriting left recursive grammars

I had a parser which parsed boolean expressions correctly by having higher precedence items encoded in separate terms which somehow came together and worked.

However I’m now trying to encode a more thorough grammar which is given in left recursive format. This has the problem of stack overflow. For example in this very slimmed down version:

``````  def formula: Parser[Boolean] = (
formula ~ "&&" ~ formula ^^ {case f1 ~ "&&" ~ f2 => f1 && f2 }
| truthValue
)

def truthValue: Parser[Boolean]  = (
"true" ^^ (_ => true)
| "false" ^^ (_ => false)
)
``````

the formula will keep going down into itself until it blows up.

Therefore following the algorithm given on https://en.wikipedia.org/wiki/Left_recursion “Removing Direct Recursion”, I end up with this:

``````  def formula: Parser[Boolean] = term~formula'

def formula' = (
"&&"~formula'
| "" // epsilon
)
``````

However, I find it hard to apply the ^^ operator since, for example the “&&”~formula’ item has no idea of what has come before it so how do I do the case f1 ~ “&&” ~ f2 element?

There is probably an easier way to solve this problem, but I’m trying to keep to the grammar as much as possible. Swapping `truthValue` and `formula` around leads to it terminating too early.

Many thanks,

The transformed version looks wrong. Where’s `truthValue`? In any case, you can encode whatever data you have in each production and then combine it properly on the way up. Untested (and it’s been a few years since I last used Scala parser combinators):

`````` def formula: Parser[Boolean] = term ~ formula' ^^ { case f1 ~ p => p(f1) }

def formula': Parser[Boolean => Boolean] = (
"&&"~formula' ^^ { case "&&" ~ f2 => (f1 => f1 && f2)}
| "" ^^^ identity // epsilon
)
``````

great thanks - I’ve managed to solve it by changing the defs in the left recursive grammars to lazy vals and keeping `PackratParser` mixed in but your solution shows how to solve the problem using the classic rewriting rules which I couldn’t manage.

I’ve come across another problem - the grammar I am implementing has two rules which are

`string~"="~string`

or

`term`

which itself eventually goes down to

`string~"="~string`.

It is possible when the parser comes across the first `string~"="~string` to do a lookup of the first string in a map or set object in the ^^ method. If the string is not found, then it tells the parser `string~"="~string` has failed, and to continue trying to match `term`?

i.e

`(string<~"=")~string` ^^ { case s1~s2 => if (mySet.contains(s1)) new SomeClass(s2) else this parsing run has failed, try to match it under term}