[antlr-interest] AST - Ordering of sibling nodes

[Søren Boisen]

For reference, here is my solution, that seems to be working.

I created a simple base class for sorting (just to have as much Java
code in .java files as possible as opposed to having it floating
around in the grammar file):



public abstract class BaseSqlSorter extends TreeRewriter {

    private Map<Integer, Integer> sortValues = new HashMap<Integer,
Integer>(10);

    public BaseSqlSorter (TreeNodeStream input) {
        super(input);
        insertSortValues(sortValues);
    }

    public BaseSqlSorter (TreeNodeStream input, RecognizerSharedState state) {
        super(input, state);
        insertSortValues(sortValues);
    }

    protected abstract void insertSortValues (Map<Integer, Integer> map);

    public final class NodeComparator implements Comparator<ODataNode> {
        @Override
        public int compare (ODataNode n1, ODataNode n2) {
            Integer s1 = sortValues.get(n1.getType());
            Integer s2 = sortValues.get(n2.getType());

            assert s1 != null && s2 != null : "unrecognized token type(s): "
                    + n1.getType() + ", " + n2.getType();

            return s1.compareTo(s2);
        }
    }

    public void sortChildren (ODataNode uriNode) {
        List<ODataNode> children = new
ArrayList<ODataNode>(uriNode.getChildren());
        Collections.sort(children, new NodeComparator());

        ODataNode root = new ODataNode((Token) null);
        root.addChildren(children);

        input.replaceChildren(uriNode, 0, children.size()-1, root);
    }

}




And then I can create a very primitive rewrite tree grammar:

tree grammar SqlSorter;
options {
    tokenVocab = QueryParser;
    ASTLabelType = ODataNode;
    filter = true;
    output = AST;
    superClass = BaseSqlSorter;
}

@header {
<------- SNIP --------->
}

@members {
    protected void insertSortValues (Map<Integer, Integer> map) {
        map.put(SELECT, 25);
        map.put(RESOURCE, 50);
        map.put(FILTER, 75);
        map.put(ORDERBY, 100);
    }
}

topdown:    sortUriChildren ;

sortUriChildren
       :    ^(URI .*) {
           sortChildren($URI);
       } ;



This way I emulate what happens during normal tree rewrite operations,
so I should hopefully be pretty safe :)


/Søren


27. feb. 2012 11.10 skrev Søren Boisen <sboisen at mail.dk>:
> Hi there, I'm transforming a URL query language (OData) to SQL. In the
> query language the query operators can be specified in arbitrary
> sequence:
>
> uri     :   resource ('?' query)? EOF
>        ->  ^(URI resource query?) ;
>
> query   :   queryOp ('&' queryOp)*
>        ->  ^(QUERY queryOp+) ;
>
> queryOp :         expandQueryOp
>        |         orderByQueryOp
>        |         selectQueryOp
>        |         filterQueryOp ;
>
> <--------snip--------->
>
>
> However, in SQL I of course have to abide by a very specific ordering:
>
> selectClause
> fromClause
> whereClause
> orderByClause
>
> The question is, what's the best/easiest/simplest way of reordering
> the AST nodes, so they align with the SQL requirements?
> Currently I'm generating the SQL via string templates like so:
>
> uri     :   ^(URI clauses+=resource clauses+=queryOp*)
>        ->  query(clauses={$clauses}) ;
>
> resource:   ^(RESOURCE ID s=subResource*)
>             -> fromClause(entity={entity($ID)}, joins={$s.st}) ;
>
> queryOp :   ^(SELECT items=selectItem+)        ->
> selectClause(items={$items.st})
>                |   ^(FILTER expr)                               ->
> whereClause(condition={$expr.st})
>                |   ^(ORDERBY items=orderByItem+)   ->
> orderByClause(items={$items.st}) ;
>
> <--------snip--------->
>
> But this requires that the nodes are already sorted in the right order.
>
> /Søren