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

[John B. Brodie]

Greetings!

passing the FROM tree down the rule set doesn't seem too bad to me.

DISCLAIMER: i can barely spell C# and certainly know nothing whatsoever
about LINQ --- so i probably have mis-understood something crucial.

On Sun, 2010-08-08 at 19:10 +0100, Luis Pureza wrote:
> 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.
> 

i guess complexity is all in the eyes of the beholder, but this:

query : fromPart queryRest[$fromPart.tree] -> queryRest ;
fromPart : FROM^ ID IN! expr ;

queryRest[CommonTree f] : queryOperator^ expr queryRest[$f] | (->{$f}) ;
queryOperator : SELECT | WHERE ;

doesn't really seem so bad to me....

hope this helps (i have attached a complete example grammar with test
rig -- in Java, sorry -- so you can see the full story of my
suggestion).

   -jbb

-------------- next part --------------
grammar Test;

options {
   output = AST;
   ASTLabelType = CommonTree;
}

@members {
   private static final String [] x = new String[] {
      "from obj in list\n"+
      "where obj.attribute > 200\n"+
      "select obj.attribute * 100"
   };

   public static void main(String [] args) {
      for( int i = 0; i < x.length; ++i ) {
         try {
            System.out.println("about to parse:`"+x[i]+"`");
            TestLexer lexer = new TestLexer(new ANTLRStringStream(x[i]));
            CommonTokenStream tokens = new CommonTokenStream(lexer);

            TestParser parser = new TestParser(tokens);
            TestParser.start_return p_result = parser.start();

            CommonTree ast = p_result.tree;
            if( ast == null ) {
               System.out.println("resultant tree: is NULL");
            } else {
               System.out.println("resultant tree: " + ast.toStringTree());
            }
            System.out.println();
         } catch(Exception e) {
            e.printStackTrace();
         }
      }
   }
}

start : query EOF!;

query : fromPart queryRest[$fromPart.tree] -> queryRest ;
fromPart : FROM^ ID IN! expr ;

queryRest[CommonTree f] : queryOperator^ expr queryRest[$f] | (-> {$f}) ;
queryOperator : SELECT | WHERE ;

expr : primary (operator^ expr)? ;
operator : '>' | '=' | '*' ;

primary : ID | NUMBER ;

FROM : 'from' ;
IN : 'in' ;
SELECT : 'select' ;
WHERE : 'where' ;

NUMBER : DIGIT+ ;
ID : IDENTIFIER ('.' IDENTIFIER)*;

fragment IDENTIFIER : LETTER (LETTER|DIGIT)+ ;

fragment LETTER : 'a'..'z' | 'A'..'Z' ;
fragment DIGIT : '0' .. '9' ;

WS : (' '|'\t'|'\n'|'\r')+ { $channel = HIDDEN; } ;