Finished tree grammar AST construction - ANTLR 3

	ANTLR 3	Log In \| Sign Up
	Finished tree grammar AST construction

Browse Space

View
Info

Added by Terence Parr, last edited by Kay Röpke on Jul 27, 2007 (view change)

Well, I was wrong. Building ASTs from tree grammars was not as easy as I thought. There were a lot of little changes everywhere and Kay Roepke and I had to examine all of the interfaces to figure out where each method best fit. Previous entry Rewrite Tree Node Stream Design was way too simple. There are lots complications, but I have it working nicely. I added a whole bunch of unit tests. The rewrites even work with the new heterogeneous tree node stuff. I make copious notes in the README.txt file, but I'm not sure if the other target developers can see into my dev branch. Anyway, we'll have to say this for a 3.1 release.

The basic idea is that, given no instructions to the contrary, ANTLR tree grammars will build a copy of the input tree; nodes for node. Just turn on output=AST:

grammar TP;
options {output=AST;}
a : ID ;

Now, that is pretty inefficient if all you want to do is tweak a small subtree within a very large tree. Use the rewrite mode and then rewrite rules alter the tree matched for that alternative. No implicit tree construction is done. Only rewrite rules alter the tree. Rewrites do, however, set the return tree for that rule.

grammar TP;
options {output=AST;}
file : ... ;
...
/** Alter the ASSIGN node to be SET */
assign : ^(ASSIGN ID INT) -> ^(SET ID INT) ;

Comments (Hide)

Is this in the current Antlrworks version?

Posted by Joshua Scholar at Aug 06, 2007 01:43

Nope. It will be in 3.1; might do an early access soon.

Posted by Terence Parr at Aug 06, 2007 09:40

If I understand correctly, then you can run this code now, but it wastes time and memory copying the tree, and the new version will change the tree in place.

Is that correct?

Also when do you expect 3.1 to come out?

Posted by Joshua Scholar at Aug 06, 2007 12:23

Actually, no tree building from tree grammar at the moment. 3.1 will have it with two modes: build new and rewrite existing.

Posted by Terence Parr at Aug 06, 2007 12:45

Could you expand on this a bit? How would I set up a rewrite? Would I have to write a tree grammar that describes the entire tree and then only include rewrite rules for those parts of the tree that I want to modify? Or, do I only write rules that describe enough of the tree so that I rewrite only the parts that I want to?

I'm interested in how I would make use of this to transform lang A AST to lang B AST, using a series of N transformations. Would I have to have a tree grammar that completely describes my tree at each of the N stages?

Posted by Kevin Braun at Aug 16, 2007 07:08

At the moment, you'd still need whole tree unless you use the TreeWizard to find subtrees and then pass to a grammar rule. Messy. Am planning on a new syntax to list a series of rules like Andy Tripp does.

Posted by Terence Parr at Aug 16, 2007 09:11

Perhaps I understand uncorrectly: if I build a language A AST(not simple AST), I want to transform to language B AST, antlr3.0.1 don't support, i can't use tree walker or rewrite rule to do it automatically, I must write code myself? Is that true?

If it's true, when antlr3.1 comes out?

3ks a lot

Posted by rpgyang at Apr 04, 2008 04:49

true. 3.1 should be out in a month or so.

Posted by Terence Parr at Apr 04, 2008 08:47

ANTLR 3.0.1 bug fix release