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,