Package jag

This is the homepage of jag, a Java preprocessor supporting the visitor pattern and inheritance-based pattern matching for 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.
 

Package jag Description

This is the homepage of jag, a Java preprocessor supporting the visitor pattern and inheritance-based pattern matching for List based trees.

Overview

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.

Operation

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 Format

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.

Action Items

` 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.

Code Architecture

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).

Projects

Downloads

Version:
1.0.4, December 2004.
Author:
Axel T. Schreiner.