[antlr-interest] Right recursive rule and creating the AST in reverse order
John B. Brodie
jbb at acm.org
Sun Aug 8 11:59:57 PDT 2010
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; } ;
More information about the antlr-interest
mailing list