parsing recursive structures in scala
parser-generator, parsing, scala
Solution
Well, recursion has to be delimited somehow. In this case, you could do this:
def combinedPredicate = predicate ~ rep( ("and" | "or" ) ~ predicate )
def predicate = "(" ~ combinedPredicate ~ ")" | simplePredicate
def simplePredicate = ...
So it will never stack overflow because, to recurse, it first has to accept a character. This is the important part -- if you always ensure recursion won't happen without first accepting a character, you'll never get into an infinite recursion. Unless, of course, you have infinite input. :-)
Problem
I'm trying to contruct a parser in scala which can parse simple SQL-like strings. I've got the basics working and can parse something like: ``` select id from users where name = "peter" and age = 30 order by lastname ``` But now I wondered how to parse nested and classes, i.e. ``` select name from users where name = "peter" and (age = 29 or age = 30) ``` The current production of my 'combinedPredicate' looks like this: ``` def combinedPredicate = predicate ~ ("and"|"or") ~ predicate ^^ { case l ~ "and" ~ r => And(l,r) case l ~ "or" ~ r => Or(l,r) } ``` I tried recursively referencing the combinedPredicate production within itself but that results in a stackoverflow. btw, I'm just experimenting here... not implementing the entire ansi-99 spec ;)