New in ANTLR 3.2
Lots of examples and more explanation in Language Implementation Patterns. The code is freely available at the book website. Dir
code/walking/patterns has a tree rewriting example using tree patterns.
Instead of specifying an entire tree grammar, a tree pattern matcher lets us focus on just those subtrees we care about. That's useful because different phases of a language application care about different parts of the tree. A tree pattern matcher also decouples the order in which we apply tree patterns from the tree patterns themselves. Unlike embedded walkers, visitors, and tree grammars, tree patterns don't specify how to walk the tree. ANTLR's new tree pattern matching engine dictates the tree traversal strategy. In its simplest form, a pattern matcher repeatedly tries to match patterns against subtrees. When it finds a match, the pattern matcher triggers an action or tree rewrite.
How to use tree pattern matching
Here is the interface to the tree filters. First, use the filter=true option in a tree grammar:
Run ANTLR on MyPatterns.g to get MyPatterns.java. Your test rig attaches the tree filter to a node stream just like a regular tree grammar. The only difference is that we call downup() instead of calling the start rule:
In the grammar, define rules to indicate what patterns to check on the way down and what patterns to check on the way up. For example, here is what it might look like if you're doing symbol table management:
How it works
Using TreeVisitor, we do a depth first walk of the tree, executing an action in the preorder position. To get a bottom-up visitor, we execute an action in the postorder position. If you look in org.antlr.runtime.tree.TreeFilter, you'll see:
The applyOnce() method is invoked by the visitor for each node; it tries to match the
topdown rule on the way down (node discovery) and rule
bottomup on the way back up (node finishing). Those
topdown_fptr type pointers are really pointers to rules that you must override:
Most of the time, a rule will not match the current subtree as we walk. To avoid issuing syntax errors and attempting error recovery, it bumps up the backtracking level (See the applyOnce() method). Upon failure, the invoked rule immediately returns. This method boils down to ``call a rule to match a tree, executing any embedded actions or rewrite rules.''
To do rewrites (see TreeRewriter), we usually need to apply rewrites multiple times on way up to catch all opportunities to rewrite:
If you don't like the strategy that I've implemented by default, you can trivially make your own by cutting and pasting from downup().
First, remember that we are not specify entire tree grammar. We are primarily looking for subtrees of interest. Tree grammars specify not only the patterns but how to visit the tree. With patterns, we use the dot (wildcard) a lot. The following pattern matches an add subtree anywhere in the tree:
Sometimes we do want to specify what the operands are. For example, the following pattern looks for x+x type editions where the operands are the same integers. It uses a predicate to make the patterns fail if they aren't the same:
When doing symbol table management, you will use rules to match the various definition subtrees. For example, here is a subtree pattern that matches a method declaration:
We do that rule on the way down to create a new scope. On the way back up though we only need to notice that it's a method declaration. we don't need to match any of the children because we don't need to do anything with that information:
Think of the tree rewriting patterns as tree pattern to tree pattern mappings. For example, here is how we would do some Boolean simplifications:
With predicates, we can check for multiply by zeroes:
The predicates prevent the alternatives from matching unless one of the integers has a 0 value.