|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||
List based trees.
See:
Description
| Interface Summary | |
|---|---|
| Main.yyInput | must be implemented by a scanner object to supply input to the parser. |
| Visitor | what a visitor must do. |
| Class Summary | |
|---|---|
| Main | recognizes and serializes a table of code generation rules. |
| Main.Jag | manages information about one jag. |
| Main.VArrayList | flags that more subtrees are permitted in a match. |
| Rule | describes a subtree situation and contains the action index; provides static method implementing rule search. |
| Scanner | scanner for jag. |
| Temp | implements indices for a stack of runtime words. |
| Exception Summary | |
|---|---|
| Main.yyException | thrown for irrecoverable syntax errors and stack overflow. |
| NoRuleException | thrown if no rule can be found. |
This is the homepage of jag, a Java preprocessor supporting
the visitor pattern and inheritance-based pattern matching
for List based trees.
jag was designed to simplify the implementation of visitors in Java and to move from an interface- to a rule-oriented architecture. jag reads a table of patterns to be recognized in a tree and actions to be executed at the appropriate points in the tree. The actions can, among other things, decide whether and how to visit subtrees.
jags ultimate ancestor is Wilcox' template coder which was developed around 1970 as part of Cornells implementation of PL/I. The key difference is that jag only uses classes to specify patterns.
jag is implemented with jay and JLex
as a preprocessor emitting visitors as Java code. The result
requires a small runtime system that participates in action
selection. Earlier implementations were self-contained interpreters,
but compilation has the advantage that powerful actions can be
written in Java while the selection mechanism still remains very
transparent. Preprocessing, however, is much more difficult to
implement.
jag is a relatively simple preprocessor that facilitates
the coding of a visitor with a pattern-based table search.
jag performs a few semantic checks, e.g., it only permits
one table entry per class and does not permit references to
subtrees that were not mentioned in a pattern. The Scanner
is a bit tricky: states are introduced to use different regular
expressions to analyze rules, actions, and printing shorthands.
jag is still an experimental tool. It has been used to present the principles of reasonably efficient code generation for typical machine architectures in a compact fashion, for type checking, and tree transformation and interpretation.
jag visitors operate on trees. Leaves may belong to
arbitrary classes but all other nodes must implement the List interface. As an example, here is a simple visitor
that displays a binary tree with Double and
Long leaves in postfix notation:
import jag.Visitor;
import java.util.List;
public class Postfix implements Visitor {
%%
List: List List { {$1}; {$2}; {$0}; } // binary: visit subtrees and then root
| List { {$1}; {$0}; } // unary: visit subtree and then root
| Double { `" "+$1.floatValue()`; } // leaf: display value
| Long { `" "+$1.longValue()`; };
Add: { `" add"`; };
Mul: { `" mul"`; };
Sub: { `" sub"`; };
Div: { `" div"`; };
Mod: { `" mod"`; };
Minus: { `" minus"`; };
%%
}
The example assumes that the branch nodes of the tree use classes
such as Add which implement List. This
is easy to arrange with pj.
The preprocessor jag operates as a filter. The example can be compiled as follows:
$ java -jar jag.jar < Postfix.jag > Postfix.java
$ javac -classpath jag-go.jar Postfix.java
To perform a visit the root node of a tree is sent to a visitor generated with jag, for example:
new Postfix().visit(tree);
Input to jag consists of three parts, separated by lines
with %%. The first part must start a class which implements
Visitor. The second part contains the table with
patterns and actions which jag will convert into the methods
required by the Visitor interface. The third part
contains Java code and must close the class started in the first
part. White space is mostly immaterial, comments range from //
to the end of a line.
A table entry consists of a class name and a sequence of patterns and actions separated by |. When a tree node is visited, the class of the node, a superclass, or an implemented interface, each with increasing distance from the class, are looked up in the table. The order of table entries in the table does not influence the lookup.
A pattern consists of a list of zero or more class names. The action following the pattern is executed if the classes of the list of direct descendants of the tree node are assignable to the list of classes in the pattern. Patterns are searched sequentially within the table entry, i.e., patterns with more specific classes must be placed near the beginning of the table entry for a node class.
null in place of a class name in a pattern means that the node cannot have a descendant in this position. Clearly, a reference to this descendant cannot appear in the corresponding action.
If the pattern is followed by three periods, it will match a tree node which has more descendants then those specified explicitly in the pattern.
An action is Java code enclosed in braces. The special syntax described next may be used in an action to simplify producing output and to reference or visit descendants of the matched tree node. If there is no action following a pattern, the search for a matching table entry continues by considering another class related to the tree node, i.e., the present pattern sequence is abandoned and a more general root class or interface with a new pattern sequence is looked up.
| ` object ` | is replaced by out().print(object), i.e., this simplifies printing. jag generates an instance variable out initialized to null and a method out() to return out or System.out by default. out can be assigned to and out() can be overwritten to redirect printing. |
| $n | references the nth descendant of the tree node; the reference is cast to the corresponding class name in the pattern. |
| $0 | references the tree node itself, cast to the class name of the table entry. |
| {$n} | calls visit() to visit the nth descendant of the tree node. This notation provides convenient access to the object that the method returns. There is also the notation $n; which does, however, terminate the call with a semicolon; it's use is deprecated. |
| {$0} | calls visit0() for the tree node, to execute the action for a class related to the tree node which is specified with an empty pattern. In a sense this is a visit to the tree node as if it had no descendants. As the postfix example above shows, this can vastly simplify the design of a visitor. Again, there is the deprecated notation $0; for a call discarding the result. |
| $$ | can be assigned to to set the result of the action which is in turn returned by the aforementioned calls to visit() or visit0(). This is useful for visitors which evaluate trees or create new trees. |
jag generates out, out(), and the
methods specified in the Visitor interface:
/** print action stream. Can be replaced to reroute output.
*/
protected transient java.io.PrintStream out;
/** returns print action stream. Defaults to System.out.
*/
protected java.io.PrintStream out () { ... }
/** visits an object. This is a facade for the class search.
*/
public Object visit (Object object) throws Exception { ... }
/** visits an object, ignoring possible descendants.
*/
public Object visit0 (Object object) throws Exception { ... }
/** callback from successful pattern search.
*/
public Object visit (int _action, Object _object) throws Exception {
Object _result = null; // $$
switch (_action) {
...
case 13: // line number of action in input to jag
visit(((java.util.List)_object).get(0)); // {$1};
visit0(_object); // {$0};
break;
...
default:
throw new Error(_action+": unexpected action index");
}
return _result;
}
/** maps class to array of Rule.
*/
protected final java.util.HashMap _rules = new java.util.HashMap();
{ _rules.put(VM.Node.class, new jag.Rule[]{ // VM.Node: VM.Node VM.Node
new jag.Rule(new Class[]{VM.Node.class,VM.Node.class}, false, 12),
new jag.Rule(new Class[]{VM.Node.class}, false, 13) // | VM.Node
});
...
}
The switch contains the actions, accessed by input line
number. _rules contains the data for the table search
which is implemented in the runtime support class Rule.
There should be at most one action per line and names should not
start with _.
A call to visit(someNode) starts a traversal
or continues it recursively and returns the result of the
corresponding action; NoRuleException is thrown if
no suitable rule can be found.
visit0(someNode) has the same effect but
searches as if someNode has no subtrees. Both
methods are covers for a static method Rule.visit
which implements the actual search and calls the Visitor
back with visit(action, someNode).
List be removed, as in
Dump?
jay and pj?
jay the n is
not always in a known region.
jag and XSLT be merged?
|
|||||||||
| PREV PACKAGE NEXT PACKAGE | FRAMES NO FRAMES | ||||||||