[antlr-interest] Re: trees with payloads??

micheal_jor open.zone at virgin.net
Wed Nov 10 16:19:07 PST 2004



--- In antlr-interest at yahoogroups.com, Terence Parr <parrt at c...> wrote:
> Hi,
> 
> [i posted this email to http://www.antlr.org/blog/antlr3/trees.tml ]
> 
> After Loring bitched at me on the phone yesterday <snicker>, I'm 
> beginning to think he's right:  if separating the node data from the 
> navigation is the right concept, then trees should be a single 
> implementation that simply carry a "payload" object defined by the 
> user.  This is like Sun's MutableTreeNode.

<SNIP>

> grammar P;
> 
> AST {
> 	Token token; // probably a default field
> 	String blort;
> 	...
> }
> 
> Then ANTLR would generate P_AST type for use when building trees.  For 
> heterogeneous trees

<SNIP>

> If we allow field specifications, that is better than specifying a type 
> name maybe:
> 
> tokens {
> 	ID<String name, int n>;
> 	...
> }
> 
> Whatever.  A random idea.

I wasn't planning on discussing this yet so I haven't had a chance to
think through the integration and grammar syntax issues but since you
guys won't keep....

I've been thinking about incorporating aspects of the TreeDL approach
within ANTLR. Basically, we will have our CoolNavigatorAST type that
handles navigation properly and has setObjectData()/setNodeData()
method. The "node data" is a System.Object (or void*)
pointer/reference to whatever the user decides. This is the type we
use as default.

Now, in grammars users can optionally add entries to describe custom
tree nodes (including attributes) that ANTLR will generate. These
would either be subclasses of CoolNavigatorAST or the very similar
CoolNavigatorWithoutNodeDataStuffAST (users presumably won't need the
generic data slots since they can specify custom attributes).

Using your grammar example above as a starting point:

grammar P;

AST
{
    abstract node Expression
    {
    }

    node BinaryExpression : Expression
    {
        attribute binop : enum OpEnum { PLUS, MINUS, MULT, DIVIDE };
        child     left  : Expression;
        child     right : Expression;
    }
}

tokens
{
   PLUS<AST=BinaryExpression>
   MINUS<AST=BinaryExpression>
}

additiveExpr
  :  multiplicativeExpr 
    ( ( p:PLUS^  { #p.operator = OpEnum.PLUS;  } 
      | m:MINUS^ { #m.operator = OpEnum.MINUS; } 
      ) 
      multiplicativeExpr
    )*

The "additiveExpr" rule will generate a node of type BinaryExpression.
Haven't figured out an automatic way to specify the value of the
"operator" field. Or indeed how the two expressions get assigned as
either left or right  :-(

Actually I think my use of "tokens" here is in error. My general
inclination is to leave it to the user to specify tree construction
manually if they decide to use the custom node feature. E.g.

additiveExpr creates [BinaryExpression e]
  :  e.left=multiplicativeExpr 
    ( ( PLUS^  { e.operator = OpEnum.PLUS;  } 
      | MINUS^ { e.operator = OpEnum.MINUS; } 
      ) 
      e.right=multiplicativeExpr
    )*

Of course "creates" would/should probably be "returns" as is the case now.

> As a bonus to the payload strategy, we can enhance the tree 
> functionality later w/o forcing alterations in people's application; 
> their payload objects still fit in our nodes.

This still applies here too.

> This all comes at the cost of an additional object creation (payload 
> creation + node creation).

No additional object creation here.

> Side note: Mitchell suggested Tokens and Tree nodes should have not 
> only fixed fields like this, but the ability to dynamically acquire 
> "attributes"; this would basically be a hashmap.  It cuts down on a 
> bazillion subclasses.  It would be useful when parsing xml for example. 
>   The TAG token could have a list of tag attributes w/o creating 
> subclasses etc...

If the user wants this functionality in their AST class, they can
specify it. Perhaps we can support a "propertybag" atribute type. This
will create a HashMap (or other dictionary object) and two methods
getField(string key) and setField(string key, object data). Perhaps a
restriction that a node can only have one propertybag is required
(including any inherited bags).

    node XmlElement
    {
        propertybag  fields;
        child        left     : Expression;
        child        right    : Expression;
    }

Cheers,

Micheal
ANTLR/C#






 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
    http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
    antlr-interest-unsubscribe at yahoogroups.com

<*> Your use of Yahoo! Groups is subject to:
    http://docs.yahoo.com/info/terms/
 





More information about the antlr-interest mailing list