[antlr-interest] ANTLR 3 output=AST for tree parser?

[Mark Bednarczyk]

Hi Kay,
	I'm jumping in here a bit late, but tree rewritting is implemented
in b6. I'm using it in my grammar heavily.

I also have the 1.5 grammar compiled and working as well. 

I'm building my own grammar based on 1.5 and using lots of rewrites in the
parser, then in the tree walkers. The output out of normal grammar "grammar
MyGrammar" can be "output=AST" or "output="template". In a Tree walker (i.e.
"tree grammar MyGrammar") can only be "output=template".

Here is proof. First rule rewrites the "typeParameters" production to
produce a new type of tree. It inserts a new type of virtual token,
GENERIC_TYPE as a root to be for all the typeParameters which could be
primitives or an identifier. Then the tableDeclaration rewrites the rule to
another TABLE_DEF rooted tree where the "modifiers" are optionally included,
id and table body which produces a SLIST rooted tree of statements allowed
within my special type of a table I'm writing here. Both GENERIC_TYPE and
TABLE_DEF tokens are only defined in "tokens" section and are not produced
by the lexer. I use them for my own AST so that later compilation stages
using tree walkers can easily match on those roots and virtual tokens to
perform further processing.

grammar Npl;
options {
	k=2;
	backtrack=true;
	memoize=true;
	output=AST;
}

typeParameters
	:	'<' typeParameter (',' typeParameter)* '>'
		-> ^(GENERIC_TYPE typeParameter*)
	;

tableDeclaration
	:	modifiers 'table' id typeParameters? tableBody  
		-> ^(	TABLE_DEF id 
				modifiers 
				typeParameters?
				tableBody)
	;


Here is a dump of the AST it produces based on this input:
	public table abc {
		Option1(1),
		Option2(2) = "option2"
	}

AST:
(TABLE_DEF 
	(ID abc) 
	(MODIFIERS public) 
	(GENERIC_TYPE int)
	(SLIST 
		(TABLE_CONST 
			(ID Option1	( 1 ))
			(TABLE_CONST_DESC)) 
		(TABLE_CONST 
			(ID Option2 ( 2 )) 
			(TABLE_CONST_DESC "option2"))))
Hope this helps,

Cheers,
mark....

> -----Original Message-----
> From: antlr-interest-bounces at antlr.org 
> [mailto:antlr-interest-bounces at antlr.org] On Behalf Of Kay Roepke
> Sent: Sunday, February 25, 2007 8:09 PM
> To: Werner Lehmann
> Cc: ANTLR Interest; FranklinChen at cmu.edu
> Subject: Re: [antlr-interest] ANTLR 3 output=AST for tree parser?
> 
> 
> On Feb 26, 2007, at 1:52 AM, Werner Lehmann wrote:
> 
> > for a few hours now I have been trying to get a tree parser out of 
> > Terence's Java 1.5 grammar. I thought I was doing something wrong 
> > being not very experienced with ANTLR. Is it true that ASTs are not 
> > yet supported?
> 
> ASTs are supported, the thing that doesn't work is tree 
> rewriting (i.e. having a tree parser output another tree by 
> using rewrite rules in the tree grammar). There are a couple 
> of examples in the examples- v3.tar.gz as well as in the Wiki 
> on how to use tree output.
> 
> > I need to update my Java 1.4 parser (based on ANTLR 2.7.6) to Java
> > 1.5 and it seemed to be a good idea to use ANTLR3 and this 
> new grammar 
> > but maybe not so. By the way, the separate examples download has a 
> > more recent version of Java.g. The version available from 
> the grammars 
> > list on the site is older and produces uncompilable code 
> which pushed 
> > me off track for some time.
> >
> > If ANTLR3 would not yet provide an AST should I then use the Java
> > 1.5 grammar created by Michael Studman or Michael Stahl (any 
> > experience with either)?
> 
> I haven't used any of the Java grammars, but looking at Ter's 
> it shows that that grammar simply isn't building trees. You 
> could add the tree operators and/or rewrite rules yourself, 
> and then write tree grammars to work with your tree. As tree 
> building often depends on the thing you want to accomplish, 
> that's probably the best way of doing it anyway.
> 
> > FranklinChen at cmu.edu wrote:
> >> I noticed that output=AST for tree parsers in 3.0b6 isn't working 
> >> yet.  When will this be available?  I have large ANTLR 2 projects 
> >> that make extensive use of multiple passes gradually 
> transforming an 
> >> AST until the final pass generates output, and I would like to 
> >> convert them to ANTLR 3.
> 
> As mentioned above, this isn't scheduled for 3.0 final, 
> AFAIK. Ter wanted to finalize the stuff there is right now 
> before adding new features.
> I'd think that tree rewriting would come in 3.1 if there is a 
> good way of unambiguously defining the process. I vividly 
> remember going through the template output stuff with Ter a 
> while ago, and that was hard enough to give right semantics to...
> 
> HTH,
> -k
> --
> Kay Röpke
> http://classdump.org/
> 
> 
> 
>