[antlr-interest] Right recursive rule and creating the AST in reverse order

[Luis Pureza]

Hi,

I'm writing a grammar to parse a language similar to C#'s LINQ*. For example:

from obj in list
where obj.attribute > 200
select obj.attribute * 100

Notice that, unlike regular SQL, the FROM clause appears before the
SELECT and WHERE clauses.

To parse this I've written the following rules:


query: FROM ID IN expr queryRest
        ;

queryRest: SELECT expr queryRest
              | WHERE expr queryRest
              |
              ;

Note that queryRest is right-recursive because I allow an arbitrary
number of WHERE and SELECT clauses.

My main issue is that I want the AST to have the form (SELECT ...
(WHERE (FROM ...))) and not (FROM ... (WHERE (SELECT ...))). That is,
I want the last operation (select in this case) to be the root node.
I've found a way to do this by creating the (FROM ID) subtree and
passing it down to queryRest, which will then complete it. However, as
you may imagine, the code gets horrible pretty quickly.

Another way (which I haven't tried) would be to generate the unwanted
tree and then reverse it using a custom walker. I'll try this next,
but first I'd like to ask if you know a better way.

Thank you!

Luís Pureza

* I know there is a grammar for C# 4.0 but, as far as I can tell, the
grammar does not generate an AST.