Systematic way to generate ANTLR tree grammar?

Question

I have a little bit large ANTLR parser grammar file and want to make a tree grammar for it. But, as far as I know this work of tree grammar generation can't be done automatically, i.e., I should generate it manually by copying parser grammar, removing some unnecessary code, etc. I want to know if there is a systematic way to generate a tree grammar file from a parser grammar file.

P.S. I read an article that insists that 'Manual Tree Walking Is Better Than Tree Grammars'. Is this reliable information? If so, would it be better for me to make a manual tree walker than writing an ANTLR tree grammar file? And then, how do I make a manual tree walker with my ANTLR parser grammar file(it makes an AST using rewrite rules)?

Thanks in advance.

Answer 1

sky wrote:

I want to know if there is a systematic way to generate a tree grammar file from a parser grammar file

You've already described the systematic way to do this: copy the parser/production rules in the tree grammar and only leave the rewrite rules in it. This will probably handle the larger part of your rules, but with other parser rules (using inline AST rewrite rules), it might look slightly different. Because of that, there is no automatic way to generate a tree grammar.

sky wrote:

P.S. I read an article that insists that 'Manual Tree Walking Is Better Than Tree Grammars'. Is this reliable information?

Yes, it is. Note that Terence Parr (creator of ANTLR) posted the article on the ANTLR wiki himself, so that says the author of it (Andy Tripp) raises valid points.

sky wrote:

If so, would it be better for me to make a manual tree walker than writing an ANTLR tree grammar file?

As Andy mentioned in his conclusion: "The decision about whether to use a "Tree Grammar" approach to translation vs. just "doing it by hand" is a matter of taste.". So, if you think writing tree grammar is too much hassle, go the manual way. It's up to you: there is no best way here.

sky wrote:

And then, how do I make a manual tree walker with my ANTLR parser grammar file(it makes an AST using rewrite rules)?

Your parser will create an AST, which by default is of type CommonTree (API-doc). You can use that tree to get the children, the parent, the type of the token etc.: all you need to manually walk the tree.

EDIT

Note that in the next version of ANTLR (version 4) it will (most likely) be possible to automatically generate a tree walker given a combined- or parser grammar.

See:

• https://web.archive.org/web/20130620232750/http://www.antlr.org/wiki/display/~admin/ANTLR+v4+plans
• https://web.archive.org/web/20130927174157/http://www.antlr.org/wiki/display/~admin/2011/09/05/Auto+tree+construction+and+visitors
• https://web.archive.org/web/20130927175520/http://www.antlr.org/wiki/display/~admin/2011/09/08/Sample+v4+generated+visitor