Search code examples
scalaparsingparser-generator

parsing recursive structures in scala

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 ;)

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. :-)