How to to create / specify the AST input for testing a tree grammar with ANTLRWorks?

Question

Background: I have created an ANTLR grammar. I am able to test and debug it with ANTLRWorks and have verified that the parser creates the AST that I had in my mind. Now, I want to write a tree grammar for the AST, parse the tree and debug the tree grammar with ANTLRWorks.

Question: I want to test and debug a tree grammar with ANTLRWorks. I thus want to parse the AST that has been created by the parser. How do I specify the AST as input when testing the tree grammar with ANTLRWorks?

P.S. I have studied the question / answer at Does anyone know of a way to debug tree grammars in ANTLRWorks but it doesn't answer my question. Although accepted by the OP, he made a similar comment.

Bart Kiers Bart Kiers · Accepted Answer · 2012-01-19T22:32:34

How do I specify the AST as input when testing the tree grammar with ANTLRWorks?

You don't need to provide the AST yourself, only the parser that produces the AST.

Given the following grammar that produces an AST:

grammar ASTDemo;

options { 
  output=AST;
}

tokens {
  ROOT;
  U_MIN;
}

parse
 : expression EOF -> ^(ROOT expression)
 ;

expression
 : addition
 ;

addition
 : multiplication (('+' | '-')^ multiplication)*
 ;

multiplication
 : unary (('*' | '/')^ unary)*
 ;

unary
 : '-' atom -> ^(U_MIN atom)
 | atom
 ;

atom
 : ID
 | NUMBER
 | '(' expression ')' -> expression
 ;

ID     : ('a'..'z' | 'A'..'Z')+;
NUMBER : '0'..'9'+ ('.' '0'..'9'*)?;
SPACE  : (' ' | '\t' | '\r' | '\n')+ {skip();};

The following would be a tree grammar for the AST produced by grammar above:

tree grammar ASTDemoWalker;

options {
  output=AST;
  tokenVocab=ASTDemo;
  ASTLabelType=CommonTree;
}

parse
 : ^(ROOT expression)
 ;

expression
 : ^('+' expression expression)
 | ^('-' expression expression)
 | ^('*' expression expression)
 | ^('/' expression expression)
 | ^(U_MIN expression)
 | atom
 ;

atom
 : ID
 | NUMBER
 ;

Be sure to put both ASTDemo.g and ASTDemoWalker.g in the same folder. Open both grammars in ANTLRWorks and generate the lexer & parser from ASTDemo.g first by pressing CTRL+SHIFT+G and then generate the tree walker by opening ASTDemoWalker.g and pressing CTRL+SHIFT+G.

Now, from the ASTDemoWalker.g editor panel, fire up the debugger by pressing CTRL+D and paste the following source in the text area:

42 * ((a + 3) / -3.14)

and press OK.

You can now step through the debugging process and at the end, you can see both what AST the parser generated:

enter image description here

and how the tree walker walked over said AST:

enter image description here

If you now make an "accidental" mistake in the tree grammar, say, instead of ^('*' expression expression) you define ^('*' expression). If you debug the tree grammar again, you will see it fail after passing the 42 node:

enter image description here

In the AST there is another node after the 42 node, while the tree walker expected only 1 single node (42) after the * root node.

Of course, this is an easy grammar, but even if you're familiar with ANTLR, it's sometimes a pain in the @$& to track down errors in a tree grammar! :)

How to to create / specify the AST input for testing a tree grammar with ANTLRWorks?

1 Answers