I have a prototype working for the automatic parse tree construction and automatic visitor generation. Imagine we have the following simple grammar:
grammar T;
s : i=ifstat ;
ifstat : 'if' '(' INT ')' ID '=' ID ';' ;
The usual startup code looks like:
TLexer t = new TLexer(new ANTLRFileStream(args[0])); CommonTokenStream tokens = new CommonTokenStream(t); TParser p = new TParser(tokens); p.s(); // invoke the start rule, s
To make it create a parse tree, all we have to do is set a flag in the parser and then ask for the rule context object. The rule context object is actually a node in the parse tree, implementing interface ParseTree:
... p.setBuildParseTrees(true); TParser.sContext tree = p.s(); System.out.println(tree.toStringTree(p));
So, given the following input:
if(3)a=x;
we would see something like the following:
(s (ifstat if ( 3 ) a = x ;))
It prints s as the root node and ifstat as the 1st child and then all tokens as children of ifstat node.
Ok, so what else can we do with the parse tree other than print it out? We want to listen in on the various enter and exit rule events, as well as potentially listening in on token visitation events. ANTLR generates 2 more files than it does now in v3: a listener and a blank listener that implements that interface:
public interface TListener extends ParseTreeListener {
void enterRule(TParser.sContext ctx);
void exitRule(TParser.sContext ctx);
void enterRule(TParser.ifstatContext ctx);
void exitRule(TParser.ifstatContext ctx);
}
The blank implementation is something convenient to override:
public class BlankTListener implements TListener {
public void enterRule(TParser.sContext ctx) { }
public void exitRule(TParser.sContext ctx) { }
public void enterRule(TParser.ifstatContext ctx) { }
public void exitRule(TParser.ifstatContext ctx) { }
public void enterEveryRule(ParserRuleContext ctx) { }
public void exitEveryRule(ParserRuleContext ctx) { }
public void visitToken(Token token) { }
}
Note that if you want to track what happens as the visitor enters every single rule, you can override method enterEveryRule instead of putting code in every single enterRule variation. To visit the tree, just create a ParseTreeVisitor, pass in a listener, and tell the visitor to visit:
ParseTreeVisitor visitor = new ParseTreeVisitor();
TListener listener = new BlankTListener() {
public void enterEveryRule(ParserRuleContext ctx) {
System.out.println("enter rule "+TParser.ruleNames[ctx.ruleIndex]);
}
public void exitRule(TParser.sContext ctx) { // specific to rule s
System.out.println("exit rule s");
}
};
visitor.visit(listener, tree);
This seems like a pretty simple but powerful mechanism. It also is well within the comfort zone of the average programmer because they are providing callbacks instead of embedding actions within a grammar. The other benefit of this is that programmers can call the visitor multiple times without it reparsing the input.
It seems like a lot of extra code to generate in these extra 2 files, but I guess it can be totally ignored if you don't want it. It's great to have all of this infrastructure generated automatically.
Ok, been doing some thinking and playing around and also talking to Sam Harwell / Oliver Zeigermann.
The first modification I've made is to turn parse tree construction on or off with a simple Boolean, rather than having to regenerate the parser with -debug. Also, the parsers fire methods enterMethod/exitMethod with the rule index all the time now since it is so convenient to have these. No more needing -trace and regenerating to get debug output.
The parse tree is useful for debugging because it records a complete trace of how the input was matched by the grammar. Because it can be automatically generated, it is also a convenient way for newbies and experts alike to get something up and running quickly. It nicely isolates their actions from the grammar itself, which can then be reused for other projects without regenerating and recompiling it.
Basic parse tree listeners
ANTLR can generate a visitor that walks a parse tree, triggering methods of a listener. The most brain-dead listener looks like this:
interface ParseTreeListener {
void visitToken(Token token);
void enterRule(ParserRuleContext ctx);
void exitRule(ParserRuleContext ctx);
}
With the enter/exit methods, programmers can specify what to do on the way down and on the way up the tree. By using a listener mechanism, I can hide all of the details of a visitor within the ANTLR runtime library. It's too easy to forget that visitor methods must check their children. In this way, listeners just manage the event, not the walking of the tree.
Parse tree implementation
The amazing thing is that I really didn't have to implement parse trees because we create RuleContext objects for every rule invocation. These objects contain the parameters, return values, labels, and any local variables you specify in the rule. These can act like a parse tree if we simply track them and add a list of children. We only need to create a leaf node pointing at token objects. To add properties to that particular node, just add a new local. For example, consider rule r:
r[int x] returns [int y]
locals [int z]
: name=ID
;
we get the following context object:
public static class r_ctx extends ParserRuleContext {
public int x; // <-- parameter
public int y; // <-- return value
public int z; // <-- local variable
public Token name; // <-- token label
public r_ctx(RuleContext parent, int state) { super(parent, state); }
public r_ctx(RuleContext parent, int state, int x) {
super(parent, state);
this.x = x;
}
}
Interface ParseTree defines two sub interfaces
public interface RuleNode extends ParseTree {
RuleContext getRuleContext();
}
public interface TokenNode extends ParseTree {
Token getToken();
}
The visitor
We want the visitor mechanism itself to be in the ANTLR library. We might have multiple strategies for walking the tree, distinct from firing events from the tree. The following recursive depth first implementation fires the basic events in ParseTreeListener and any rule specific events that the programmer has defined in their listener:
public class ParseTreeVisitor {
public void visit(ParseTreeListener listener, ParseTree t) {
if ( t instanceof ParseTree.TokenNode) {
visitToken(listener, (ParseTree.TokenNode) t);
return;
}
ParseTree.RuleNode r = (ParseTree.RuleNode)t;
enterRule(listener, r);
int n = r.getChildCount();
for (int i = 0; i<n; i++) {
visit(listener, r.getChild(i));
}
exitRule(listener, r);
}
protected void visitToken(ParseTreeListener listener, ParseTree.TokenNode t) {
listener.visitToken(t.getToken());
}
/** The discovery of a rule node, involves sending two events:
* the generic enterRule and a RuleContext-specific event.
* First we trigger the generic and then the rule specific.
* We to them in reverse order upon finishing the node.
*/
protected void enterRule(ParseTreeListener listener, ParseTree.RuleNode r) {
ParserRuleContext ctx = (ParserRuleContext)r.getRuleContext();
listener.enterRule((ParserRuleContext)r.getRuleContext());
ctx.enterRule(listener);
}
protected void exitRule(ParseTreeListener listener, ParseTree.RuleNode r) {
ParserRuleContext ctx = (ParserRuleContext)r.getRuleContext();
ctx.exitRule(listener);
listener.exitRule(ctx);
}
}
We want ANTLR to generate an interface like the following that has the rule specific events:
interface TListener extends ParseTreeListener {
void enterRule(s_ctx ctx);
void exitRule(s_ctx ctx);
void enterRule(ifstat_ctx ctx);
void exitRule(ifstat_ctx ctx);
}
ANTLR always generate this interface in case it's needed
So, to specify what to do upon discovering any rule, programmers would override the visitor's enterRule() method. To respond only to the discovery of a specific rule, they would implement a method from the grammar specific interface. For example, imagine the following simple parser grammar:
grammar T;
s : i=ifstat ;
ifstat : 'if' '(' INT ')' ID '=' ID ';' ;
That would result in RuleContext objects with visitor double-dispatch methods in them (normally I don't like these, but they're automatically generated in this case):
public static class s_ctx extends ParserRuleContext {
public ifstat_ctx i;
public s_ctx(RuleContext parent, int state) {
super(parent, state);
}
public void enterRule(TListener listener) { listener.enterRule(this); }
public void exitRule(TListener listener) { listener.exitRule(this); }
}
Naturally, we can easily generate a blank listener implementation of TListener so programmers only have to implement the events they care about:
TListener listener = new BlankTListener() {
public void enterRule(s_ctx ctx) { ... }
...
};
Then, to use the visitor on a particular parse tree root, we can do the following.
startRule_ctx root = ... ; ParseTreeVisitor visitor = new ParseTreeVisitor(); visitor.visit(listener, root);
Listener event return values
Listeners can track whatever state information they want as fields of that listener object. But, what if they want to compute information and have that percolate back up to the root of the tree? Instead of having a return value from the various listener methods and have the visitor pass them back up, the listener methods can simply alter the parse tree nodes. Normally, this is a bad idea because side effects free code is much easier to maintain and read and so on. But, in this case, the nodes are actually rule context objects that store all of the variables and labels defined in rule. If your listener methods need to compute values used by listener methods triggered higher up in the tree, they can save the values in a field stored in the rule context object. Locals, parameters, return values, and labels and get stored in that context. The parse tree is like a freeze-dried version of the entire stack frame used during the parse. Storing return values in the nodes is simply freeze-drying all of the return values. More often than not, however, the result of the visitor is kept in the state of the listener object, which can easily be returned to the invoking code. It also has the benefit of not modifying the trees at all. That would be my recommendation. We can always simulate return values with a map: Map<RuleContext, Object>.
Looking back at my previous post on the visitors and trees, I noticed that I can't put listener events anywhere but the right-hand side of the outermost alternatives. This would be illegal:
expr : left=mexpr (op='+' right=mexpr -> visitAdd)* ;
It looks nice, but does not make any sense. The visitor only walks the tree after the entire parse. Triggering event inside a parsing loop has no meaning. To truly deal well with expression trees, I recommend using abstract syntax tree is not parse trees. I suppose the tail recursion could be used here to trigger an event upon each add operation.
Dealing with multiple alternatives
Rules with multiple alternatives should have a different event for each alternative, but using automatically generated names like alt1(), alt2(), etc. is a bad idea because a change in the grammar will silently break the listener. That means we need to do something like I was talking about previously and specify the name of the event in the listener. Something like this (NEW SYNTAX):
atom : INT # anInt
| ID # anID
| array=ID '[' index=expr ']' # anArrayIndex
;
ANTLR can collect all of these names and trigger discover and finish methods for them. I don't think it's as useful to limit ourselves to just a single event that occurs after we've processed a rule's nodes. For example, what if you want to do something before the visitor reaches the index of the array reference? We need a listener method for the start and stop of the alternative. Notice that I changed the name from the previous incarnation from visitInt to anInt. This way, ANTLR can generate methods like enter_anInt(), etc. We say what the parser has matched, rather than the specific name of a listener or visitor. Having a discover and finish for alternatives with a single token reference doesn't make much sense but we could ignore one or the other method.
These names can also be used on single alternative rules as well to isolate name changes in the grammar from causing compilation errors in the listener. It would prevent runtime errors for ANTLR targets based upon dynamically typed languages.
This '#' allows AST rewrites with -> and visitors for parse trees.
Summarizing discussion from people on the interest list.
Editor
Likes
- the editor works pretty well to help with auto indenting etc to make things look pretty and provide easy to read formatting.
Dislikes
- editor is quirky
- forward and backward arrows don't always work
- undo is character by character
- a number of people pointed out the inefficient and sluggish error checking and syntax highlighting. there are little user benefits for key-stroke-by-keystroke checking while the user is typing, 2) the constant checking is unnecessary usually and really slows down typing performance. emphasis on fixing this feature. NetBeans, for example, only sends off a check event IF the user has stopped typing for 0.5 seconds (they call this the parsing and indexing loop).
- near the end of a line, the cursor seems to shift slightly so that it's not between characters.
- rule/token name completion should automatically select the top choice so you can just hit return
Desired features
- add ability to see matching closing/opening parenthesis/braces etc.
- the "find" functionality should work in the console and other Windows
- code completion for $x.attribute
- using reflection, if the target allows, to code completion on the field/methods of an object like "$user." for some label user.
- code complete the options
Visualizations
people like the visualizations: syntax diagrams (with ambiguous passed highlighting), AST, parse tree.
dislikes
- Resolving ambiguities in the syntax diagrams is not always obvious; tempting but doesn't seem to help unless you already know what the problem is
- Don't use A..B notation in trees or syntax diagrams; For parser it makes no sense.
Debugger
- A user reports that he prefers to debug and the like via Java code
- A user reports that he likes the debugger, but can't use it with his large project with all of his build scripts. perhaps this means we need to make the remote debug thing more obvious?
Interpreter
- for prototyping, quick check parsers working
- The "run" but should be more obvious.
- inconsistent that you type in the input on the left for the interpreter, but not for the debugger
- the interpreter should ignore the actions if there are any and do the best job you cannot input (e.g., it might not work if there predicates)
Exporting/generating
- export syntax highlighted html; example HTML from grammar. (If you click a defining rule name, you'll be taken to the ANTLRWorks graphical presentation of the rule)
- Export PDF of a selected rule and all invoke rules or all of the rules.
- Most of my students generate antlr code in the same folder as the grammar, so it might be nice if the output path was the empty string by default. Others may prefer it the way it is.
- Make it easier to generate -debug output with a menu option rather than having to change preferences.
Overall GUI
- A user reports: I think of the interpreter and debugger as modes. Modes don't belong on tabs.
- Would be nice to design this new version has a set of widgets that cooperate so that people can take pieces of it and inject into other development environments or whatever
- Allow the visualization window to "Pin" to the bottom, like most IDE's do, effectively allowing it to auto hide.
Misc
- console spews continuous error messages
- clear the console when you generate or run any other kind of analysis.
- More documentation; maybe that's a book thing
- Preferences can only be set once a grammar is open. Preferences should be able to be set regardless of having a grammar open.
- tool tips about what the various stuff is; e.g., what is an UP token?
- It would be nice if the preferences window followed the standard paradigm of an Apply, Ok, and Cancel buttons. If no settings need to be changed, the apply button is greyed out.
What I did not hear people talk about
I've only heard from a small number of people at this point, less than 24 hours after my initial post, but no one mentioned:
- Refactoring
- displaying decision DFA (well, one person mentioned to say that sometimes it gets stuck)
- only one person mentioned showing the generated code
- group/ungroup rules, rule collapsing