[antlr-interest] Interesting trick for forcing position of child nodes in ASTs.

Robin Davies rerdavies at rogers.com
Thu Jun 28 16:32:36 PDT 2007


Just thought I'd share this idea. I've been working on converting an AST to a heterogenous AST using a custom tree adaptor, and I came up with the following idea to greatly simplify handling of subnodes.

At first I thought the approach given below was a bit inelegant; but after thinking about it, given the lispy-ness of the current AST implementation, this doesn't seem so terrible wrong. 

One of the things I find difficult about the current AST implementation is that AST child nodes are appended without regard to the structure of the rule that generated them. That means that, for AST rules like

    foo:  bar1* bar2? bar3* -> ^(FOO bar1* bar2? bar3*) 

anything that walks the AST tree can't rely on positional information in the AST to differentiate between bar1's and bar2's and bar3's. Given a foo AST node with 12 children, there's no trivial way to decide the type of each of the child nodes without deep knowledge of the parse tree for bar1, bar2, and bar3. This may be alright when using tree parsers, but, for non-tree-parser based tree-walkers, deciding how many bar1's bar2's and bar3's there are can be decidedly difficult.

Here's a way to enforce positional information in the AST:

    tokens 
    {
        LIST;  // artficial AST node for grouping lists of zero or more nodes.
        OPTIONAL; // artifical AST node for marking optional nodes.

        FOO;
    }

    foo
        : bar1* bar2? bar3* bar4
            ->  ^(FOO  ^(LIST bar1*) ^(OPTIONAL bar2?) ^(LIST bar3*) bar4 )
        ;

Now, tree walkers can positionally identify the child nodes as follows (C# code):

    ITree fooNode;
    // Do something for each of the bar1* children of foo;
    // All bar1 nodes are children of a ^(LIST) node at position 0.
    ITree bar1Nodes = fooNode.GetChild(0);     
    for (int i = 0; i < bar1Nodes.ChildNodes; ++i)
    {
        ITree aBar1Node = bar1Nodes.GetChild(i);
        DoSomething(aBar1Node );
    }
    
    // Do something for an optionally present bar2 node
    // If there is a bar2 node, it will be a child an ^(OPTIONAL) node in positoin 1.
    ITree bar2NodeOpt = fooNode.ChildNode(1);     
    if (bar2NodeOpt.ChildCount != 0) {
        ITree bar2Node = bar2NodeOpt.GetChild(0);
        DoSomething(bar2Node);
    }
    // and so for for bar3* nodes.
    // bar3 nodes are children of a ^(LIST) node at position 2.
    ITree bar2Nodes = fooNode.GetChild(2);
    ... etc.
    // bar4 is always present. So it's a direct child in position 3.
    ITree bar4Node = fooNode.GetChild(3);
        
        



    
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20070628/0ce37192/attachment.html 


More information about the antlr-interest mailing list