Reference Manual for JastAdd 2.2.0

Click here to read the JastAdd 2.1.13 manual.

Index

• Syntax overview
• Abstract Syntax
  • Predefined AST classes
  • Basic constructs, Naming, Tokens, Inheritance, NTAs
  • Lists & Opts, Building, Using JJTree
• Aspects
  • Aspect files (.jadd and .jrag files)
  • Supported AOP features, Differences from AspectJ, Idiom for aspect variables
• Attributes
  • Synthesized, inherited, method syntax, lazy/caching, refine
  • Parameterized, broadcasting, circular, NTAs, collections
• Rewrites
• Command line syntax

Quick syntax overview

AST Specification Syntax

Syntax for AST class declarations in .ast files:

Aspect declarations

Syntax for attribute declarations in .jrag and .jadd files:

Abstract syntax

Abstract grammars are specified in .ast files and are used to generate a Java class hierarchy. The classes in an abstract grammar are referred to as AST classes. The AST classes are used by the parser to build Abstract Syntax Trees (ASTs).

Predefined AST classes

The AST classes include user declared classes in the abstract grammar, as well as a few predefined AST classes that are implicitly generated. The predefined AST classes are described in the table below.

ASTNode

public ASTNode<T extends ASTNode> implements Cloneable {
  int getNumChild();
  ASTNode getChild(int index);
  ASTNode getParent();
  Iterable<T> astChildren();
  Iterator<T> astChildIterator();
}

List

public List<T extends ASTNode> extends ASTNode<T> implements Iterable<T> {
}

Opt

public Opt<T extends ASTNode> extends ASTNode<T> {
}

See also "About Lists and Opts".

Abstract syntax constructs

The table below documents the syntax used to declare user declared AST classes in .ast files.

Basic constructs

abstract A;

abstract class A extends ASTNode { }

B: A ::= ...;

class B extends A { }

C: A ::= A B C;

class C extends A {
  A getA();
  B getB();
  C getC();
}

D: A;

class D extends A { }

E1 ::= A;

class E1 {
  A getA();
}

E2 ::= [B];

class E2 {
  boolean hasB();
  B getB();
}

E3 ::= C*;

class E3 {
  int getNumC();
  C getC(int);
  List<C> getCList();
}

E4 ::= <D>;

class E4 {
  String getD();
  void setD(String);
}

A ::= /D/;

class A {
  D getD();
}

Naming children

F ::= Foo:A Bar:B;

class F {
  A getFoo();
  B getBar();
}

G ::= Thing:B*;

class G {
  int getNumThing();
  B getThing(int);
  List<B> getThingList();
}

H ::= [Foo:X];

class H {
  boolean hasFoo();
  X getFoo();
}

Typed tokens

Tokens are implictly String typed. But you can also give a token an explicit type:

A ::= <T>;

class A {
  String getT();
  void setT(String);
}

A ::= <T:String>;

A ::= <T:int>;

class A {
  int getT();
  void setT(int);
}

A ::= <Ref:B>;

class A {
  B getRef();
  void setRef(B);
}

Inheriting children

AST class children are inherited by subtypes.

abstract A ::= B C;
D: A;
E: A;

abstract class A extends ASTNode {
  B getB();
  C getC();
}
class D extends A { }
class E extends A { }

A ::= B C;
D: A ::= F;

class A extends ASTNode {
  B getB();
  C getC();
}
class D extends A {
  F getF();
}

A ::= B C;
D: A ::= C F B;

List and Opt components

JastAdd generates accessor methods to access optional and list components. The generated methods can be used instead of accessing the Opt and List container directly. The generated accessor methods are listed in the table below. The Opt and List nodes can be accessed by getXOpt() and getXList(), if needed.

A ::= [B];

class A {
  boolean hasB();
  B getB();
  Opt<B> getBOpt();
}

A a = ...;
if (a.hasB()) {
  B b = a.getB();
  ...
}

C ::= D*;

class C {
  int getNumD();
  D getD(int index);
  List<D> getDList();
}

C c = ...;
for (D d : c.getDList()) {
    ...
}

Building AST nodes

Use the following constructor API to build the AST. Typically you build the AST in the action routines of your parser. But you can of course also create an AST by coding it explicitly, e.g., in a test case. If you use JavaCC and JJTree, see below.

A ::= B C [D] E* <G>;

A(B, C, Opt<D>, List<E>, String)

A ::= A /B/ C;

A(A, C)

The predefined AST classes Opt and List have some default constructors to help with building trees:

List<T>

Opt<T>

The List node constructor that takes no arguments can be used together with the add method which returns the list itself, so you can chain multiple list additions after creating a new node, like this:

A1 a = ...;
A2 a = ...;
List<A> list = new List<A>().add(a1).add(a2);

Below is an example of building an AST based on the grammar

A ::= B*;
B ::= C;
C ::= <ID>;

An example AST for this grammar can be built like this:

A = new A(new List<B>(new B(new C("foo")), new B(new C("bar"))));

Building ASTs using JJTree

If you use JJTree, the tree building code is generated by JJTree. You can use the "#X" notation in the JJTree specification to guide the node creation.

JJTree maintains a stack of created nodes. The "#X" notation means:

1. Create a new object of type X.
2. Pop the nodes that were created during this parse method and insert them as children to the new X node.
3. Push the new X node.

You need to explicitly create List and Opt nodes. When the parsing structure does not fit the abstract tree, e.g. when parsing expressions, you need to use some additional tricks. You also need to set token values explicitly.

Aspects

JastAdd aspects support intertype declarations for AST classes. An intertype declaration is a declaration that appears in an aspect file, but that actually belongs to an AST class. The JastAdd system reads the aspect files and weaves intertype declarations into the target AST classes.

The kinds of intertype declarations that can occur in an aspect include ordinary Java declarations like methods and fields, and attribute grammar declarations like attributes, equations, and rewrites.

An aspect file can contain import declarations and one or more aspects, e.g.:

import java.lang.util.*;
aspect A {
  abstract public void Stmt.m();
  public void WhileStmt.m() { ... }
  public void IfStmt.m() { ... }
  ...
}
aspect B {
  private boolean Stmt.count = 0;
}

The aspect syntax is similar to that of AspectJ, but in contrast JastAdd aspects are not real language constructs. The JastAdd system simply reads the aspect files and inserts the intertype declarations into the appropriate AST classes. For example, the method m() and its implementations are inserted into classes Stmt, WhileStmt, and IfStmt. And the declaration of the field count is inserted into the class Stmt. Import declarations are inserted into all AST classes for which there are intertype declarations in the aspect. So, the import of java.lang.util.* is inserted into Stmt.java, WhileStmt.java, and IfStmt.java. For a more detailed discussion on the similarities and differences between JastAdd aspects and AspectJ, see below.

The aspect names, e.g., A and B above, do not show up in the woven Java code, other than in generated documentation comments for woven attributes and intertype declarations. Aspect names are used for refine declarations.

Aspect names are a way to indicate the purpose of the aspect. A common idiom for naming aspects is to have one aspect per aspect file, and give the aspect the same name as the filename sans the extension.

JADD and JRAG files

An aspect file can have the suffix .jadd or .jrag. The JastAdd system does not differ between these two types of files, but we recommend the following use:

• Use .jrag files for declarative aspects, i.e., where you add attributes, equations, and rewrites to the AST classes
• Use .jadd files for imperative aspects, i.e., where you add ordinary fields and methods to the AST classes

It is perfectly fine to not follow this convention, i.e., to mix both imperative and declarative features in the same aspect, but we try to follow the convention in our examples in order to enhance the readability of a system.

Example imperative aspect (JADD)

Here is an example imperative aspect that adds pretty printing behavior to some AST classes. Typically, this file would be named PrettyPrint.jadd:

aspect PrettyPrint {
  void WhileStmt.pp() {
    System.out.format("while %s do %s%n", getExp().pp(), getStmt().pp());
  }
  void IfStmt.pp() { ... }
  void Exp.pp() { ... }
}

Example declarative aspect (JRAG)

Here is an example declarative aspect that adds type checking to some AST classes. Typically, this file would be named TypeCheck.jrag:

import TypeSystem.Type;
aspect TypeCheck {
  syn Type Exp.actualType();
  eq LogicalExp.actualType() = Type.boolean();
  eq IdUse.actualType() = decl().getType();
  ...
  inh Type Exp.expectedType();
  eq WhileStmt.getExp().expectedType() = Type.boolean();
  syn boolean Exp.typeError() = !(actualType().equals(expectedType());
}

Supported AOP features

WhileStmt implements LoopInterface;

interface I { ... }
class C { ... }

aspect A {
  void C.m() { ... }
}

aspect B {
  refine A void C.m() { // Similar to overriding.
    ...
    refined(); // Similar to call to super.
    ...
  }
}

aspect A {
  void C.m() { ... }
}

aspect B {
  refine A void C.m() { // similar to overriding
    ...
    AspectFile.C.m();
    ...
  }
}

Similarities and differences from AspectJ

The aspect concept in JastAdd was developed in parallel to the AspectJ development, and we have gradually adopted the AspectJ syntax, for features that are similar. The important similarity between JastAdd aspects and AspectJ aspects is the intertype declarations. In addition, JastAdd aspects support attribute grammar features which AspectJ does not. Note, however, that JastAdd supports intertype declarations only for the AST classes, not for classes in general as AspectJ does. There are many other features of AspectJ that are not supported in JastAdd, for example:

• Fields and methods private to an aspect are not supported.
• Declaration of additional parent classes is not supported.
• Dynamic features like AspectJ's pointcuts or advice are not supported.

Idiom for private fields and methods

As mentioned, JastAdd does not support fields and methods that are private to an aspect. As a workaround idiom, such fields and methods can be implemented as (non-private) static fields and methods in class ASTNode. As an example, consider the pretty printer. We might want to parameterize the pretty printer methods so that it can pretty print to any PrintStream object, not only on System.out. Here is how you could write this in AspectJ and the corresponding JastAdd implementation:

aspect PrettyPrinter {
  private PrintStream ppStream = null;
  public void prettyprint(ASTNode n, PrintStream s) {
    ppStream = s;
    n.pp("");
    ppStream = null;
  }
  void ASTNode.pp(String indent) { }
  void WhileStmt.pp(String indent) {
    ...
    ppStream.println(...);
    ...
  }
  ...
}

aspect PrettyPrinter {
  static PrintStream ASTNode.ppStream = null;
  public void ASTNode.prettyprint(PrintStream s) {
    ppStream = s;
    pp("");
    ppStream = null;
  }
  void ASTNode.pp(String indent) { }
  void WhileStmt.pp(String indent) {
    ...
    ppStream.println(...);
    ...
  }
  ...
}

Attributes

Attributes are specified in JastAdd aspect files.

Different kinds of attributes are documented in the following sections.

Synthesized attributes

syn T A.x();

T A.x();

eq A.x() = Java-expr;

eq B.x() = Java-expr;

syn T A.x() = Java-expr;

syn T A.x();
eq A.x() = Java-expression;

Inherited attributes

Inherited attributes propagate information down in the AST. When an inherited attribute is evaluated, the evaluation code first searches upward in the AST for a node that can compute the inherited attribute. The equation may be on the parent of the current node, or an ancestor, even the root of the tree.

inh T A.y();

T A.y();

eq C.getA().y() = Java-expr;

eq D.getA().y() = Java-expr;

Method syntax

It is possible to write the computation of an attribute value as a method body instead of as a single expression. This may be convenient when the computation is complex. Inside the method body it is possible to use ordinary imperative Java code with local variables, assignments, loops, etc. However, the net result of the computation must not have any side-effects. (Currently, JastAdd does not check the absence of such side-effects, but future versions might do so.)

Example of a method body in a synthesized attribute:

syn T A.x() {
  ...
  return Java-expr;
}

Cached attributes

An attribute can be declared lazy in order to speed up subsequent evaluations of the attribute. An attribute that is declared lazy will have its value is cached after the first access to it. The next time the attribute is accessed, the cached value is returned directly. We recommend that attributes that are expensive to compute and that are accessed multiple times should be declared lazy. For example, declaration bindings and type attributes are good candidates for caching. JastAdd has facilities for automatically computing good cache configurations based on profiling, but this is not yet documented here.

Example lazy attribute declaration:

syn lazy A.x();

Another way to change the caching behaviour of attributes is to use a separate cache declaration:

uncache A.x();

cache A.x();

Cache declarations take precedence over the lazy keyword, but conflicting cache declarations for a single attribute will cause JastAdd to report an error as there is no way to select the proper caching strategy.

Refining attributes

Equations defined in one aspect can be refined in another aspect, in the same way as methods can be refined, see JastAdd aspect files. In the example below, the equation replaces the corresponding equation declared in the aspect named S:

refine S eq B.x() = Java-expr;

The value of the original equation in S can be accessed by the expression S.B.x(). Older JastAdd code accessed the original equation by using the expression refined().

Parameterized attributes

Attributes can have parameters. This is a bit unusual for attribute grammars, but a natural generalization when attributes are viewed as virtual functions.

syn T A.x(int a);
eq A.x(int a) {
  return Java-expr;
}

inh T A.y(int a);
eq C.getA().y(int a) {
  return Java-expr;
}

Broadcasting inherited attributes

Often, an inherited attribute is used in a number of places in a subtree. If basic inherited attributes are used, the value needs to be copied explicitly using inherited attributes in all the intermediate nodes. For convenience, JastAdd supports another technique called broadcasting, where an inherited attribute is available in every node of a complete subtree. An equation defining an inherited attribute actually broadcasts the value to the complete subtree of the child. By using this technique, no explicit copy attributes are needed.

eq C.getA().y() = ...;
inh T A.y();

inh T B.y();

Overruling broadcast definitions

A broadcast definition of an attribute a() applies to all nodes in a subtree rooted by N. If, however, there is a node in the subtree which has another equation that defines a() for a child M, that equation will take precedence for defining a() in M and its subtree.

Differentiating between children in a list

When defining an inherited attribute of a child node that is an element of a list, it is sometimes useful to know which index the child node has. This can be done as follows:

C ::= E*;
eq C.getE(int index).y() = expr;

Here, a C node has a list of E children. When defining the y() attribute of a given (subtree of an) E child, the value might depend on the index of the child. For example, if the E nodes are actual arguments of a procedure, we might want to pass down the expected type of each argument.

The example equation shows how to declare the index as a parameter of the getE() method, and to access the index in the equation body.

Circular attributes

Attributes can be circularly defined, meaning that the value of the attribute can depend (indirectly) on itself. Circular attributes are evaluated iteratively, starting with a start value given in the declaration of the attribute. The evaluation stops when the value equals that for the previous iteration.

Circular attributes are always cached. They do not need to be declared "lazy".

It is an error if a lazy attribute is circular, but not declared as such. With the visitCheck and componentCheck options this can be detected at runtime, and an exception will be generated. To be sure that the evaluation of circular attributes will converge, the values should be arranged into lattices of finite height, the bottom values should be used as starting values, and each equation on the cycle should be monotonic with respect to the lattices.

syn T A.x(int a) circular [bv];
eq A.x(int a) = rv;

Here, the attribute x is a circular attribute. The starting value is bv (a Java expression).

The equation defines x as having the value computed by the Java expression rv. Note that rv may depend (directly or indirectly) on x.

If an attribute A.x() that was not declared circular becomes part of a circular evaluation, for example by adding an extension aspect, then it is essential that the original attribute is never cached. This can ensured using the uncache declaration described above:

uncache A.x();

Attribute systems with circular attributes are well defined if at least one attribute on every possible circular dependency cycle is declared circular and the other attributes on all cycles are either also declared circular or declared uncached as above.

Nonterminal attributes

Nonterminal attributes (NTAs) are nodes in the AST. Whereas normal AST nodes are built by the parser, the NTAs are viewed as attributes and are defined by equations.

• NTAs can be inherited or synthesized.
• The value in the equation should be a freshly built AST subtree. It should be complete in the sense that all its children should also be freshly created nodes (i.e., they are not allowed to be initialized to null).
• The NTA can itself have attributes that can be accessed like normal attributes.
• If the NTA has inherited attributes, there must be equations for those attributes in some ancestor, as for normal children.

Declaration Syntax

syn nta C A.anNTA() = new C();

Older syntax

In the older syntax, a nonterminal attribute is added as follows:

• Declare the NTA in the ast file, see also NTAs in the abstract syntax.
• Declare the NTA as an attribute in a jrag file. It can be declared as a synthesized or an inherited attribute. The name of the attribute should be the same as in the AST traversal API, e.g., getX if the NTA is called X.
• Add equations defining the NTA. The defining value should be a new AST of the appropriate type, created using the AST building API.

Note that if the NTA is a list or an optional node, you need to create the appropriate AST with a List or an Opt node as its root. See examples below.

Simple synthesized NTA

In an .ast file:

A ::= B /C/;

In a .jrag file:

syn C A.getC() = new C();

The NTA C is declared in the .ast file. It is then declared as a synthesized attribute getC() in the .jrag file. The equation is provided directly in the declaration and creates a new C node.

List NTA

In an .ast file:

A ::= B /C*/;

In a .jrag file:

syn C A.getCList() =
    new List()
        .add(new C())
        .add(new C());

The list NTA C is declared in the .ast file. It is then declared as a synthesized attribute getCList() (the same name as in the implementation level traversal API) in the .jrag file. The equation is provided directly in the declaration and creates a List node to which is added a number of C nodes (two in this example).

Collection attributes

Collection attributes have composite values that are defined by so called contributions that each add a small piece to the composite value. The contributions may be located in any nodes in the AST.

Declaration syntax

The syntax for declaring a collection attribute looks like this:

coll T A.c() [fresh] with m root R;

The individual parts of the declaration above are:

1. T is the type of the attribute. Usually T is a subtype of java.lang.Collection.
2. A is AST class on which the attribute is evaluated.
3. The .c() part declares the attribute name, in this case c.
4. (optional) [fresh] tells JastAdd how the intermediate collection result is initialized. The Java expression fresh creates an empty instance of the result type. This part is optional if T is a concrete type with a default constructor, if it is omitted the default constructor of the type T is used, i.e. new T().
5. (optional) with m specifies the name of a method to be used for updating the intermediate collection object. This part is optional and the default method add is used if no update method is specified. The update method must fulfill these requirements:
   • The method m, should be a one-argument method of T.
   • The method m should mutate the T object by adding one object to it.
   • The method m should be commutative, in the sense that the order of calling m for different contributions should yield the same resulting T value.
6. (optional) The root R part declares the collection root type. The collection mechanism starts by finding the nearest ancestor node of type R for the A node which the collection attribute is evaluated on. The subtree rooted at that nearest R ancestor is searched for contributions to A.c(), this means that the collection is scoped to the subtree of R, and contributions outside that tree are not visible.

Contribution declaration

When JastAdd evaluates a collection attribute it first performs a "survey" of the AST, searching for contributions to the given collection attribute. Contributions are added by using contribution statements like below:

N1 contributes value-exp
    when cond-exp
    to N2.a()
    for N2-ref-exp;

Let's look at each part of the above template statement:

• N1 is the type of AST nodes that provide this particular contribution to the target collection attribute.
• value-exp is a Java expression that evaluates to an object to be added to the intermediate collection of the target collection attribute.
• (optional) when cond-exp is an optional contribution condition: the contribution is only added to the target collection attribute if the Java expression cond-exp evaluates to true.
• N2 is the node type where the target collection attribute is declared.
• .a() is the name of the target collection attribute.
• (optional) for N2-ref-exp gives a Java expression, N2-ref-exp, which evaluates to a reference to the AST node that owns the collection attribute this contribution is contributing to. This is the target expression, and it can be omitted if the target node is identical to the collection root node.

One can optionally contribute one contribution to multiple target nodes by using this syntax:

N1 contributes value-exp
    when cond-exp
    to N2.a()
    for each N2-ref-set;

where N2-ref-set is a Java expression that evaluates to an Iterable<N2> containing references for the set of contribution target nodes.

It is possible to contribute multiple values in a single contribution by using this syntax:

N1 contributes each value-exp
    when cond-exp
    to N2.a()
    for each N2-ref-set;

Note the each before value-exp. This syntax works if value-exp has the type Iterable<E> where E is the element type of the collection attribute. For example, if the collection attribute is declared as coll LinkedList<String> ... then value-exp should have the type Iterable<String>.

Rewrites

JastAdd has a mechanism for replacing AST nodes by a rewritten version of the node whenever the node is first accessed. Rewrites are declared using rewrite rules, described below.

Unconditional rewrite rule

rewrite A {
  to B {
    ...
    return exp;
  }
}

An A node will be replaced by the node specified in the Java expression exp. This will happen as soon as the A node is accessed (by a get() method from its parent), so if you traverse the tree you will only be able to access the final rewritten nodes.

A and B must be AST classes.

The exp must be of type B.

Let the set S be the superclasses of A (including A) that occur on right-hand sides of productions in the abstract syntax. B must be a subclass of all classes in S. This guarantees that replacing an A node by a B node does not break the rules in the abstract syntax.

The code in the body of the rewrite may access and rearrange the nodes in the subtree rooted at A, but not any other nodes in the AST. Furthermore, the code may not have any other side effects.

Conditional rewrite rule

rewrite A {
  when ( condition )
    to B {
      ...
      return exp;
    }
}

The conditional rewrite works in the same way as the unconditional one, but performs the replacement only if the boolean expression condition is true. The condition may access anything in the AST, e.g., attributes, other tree nodes and their attributes, etc.

Iterative rewriting

After a node has been replaced according to a rewrite rule, all conditional rewrite rules are checked again, and a new rewrite may be performed. This is iterated until no rule conditions hold.

Order of rewriting

At each iteration of rewriting, the rule conditions are evaluated in a certain order. The first condition that is true is used for rewriting in that iteration. The order in which rule condition evaluation occurs is the following:

• conditions in superclasses are evaluated before conditions in subclasses
• conditions within an aspect file are evaluated in lexical order
• conditions in different aspect files are evaluated in the order the files are listed in the jastadd command.

Confluency

If the order of rewriting of a node does not effect the final result, the rules are said to be confluent. This is highly desirable, since it makes the specification more readable to not have to take lexical order of rules into account. However, JastAdd cannot check that the rules are confluent. In cases where several conditions for a node are true at the same time, we recommend that you contemplate the rules and try to find out if they could be non-confluent. In that case, we recommend you to refine the conditions so that only one can apply at a time. This makes your specification independent of lexical order. Note that it is often useful to have several different rules that apply at the same time for a given node, but which are confluent.

Shorthand notation

If you have several conditional rewrite rules, you may write them inside the same rewrite block. So, e.g., writing

rewrite A {
  when ( condition-1 )
  to B {
    ...
    return exp-1
  }
  when ( condition-2 )
  to C {
    ...
    return exp-2
  }
}

rewrite A {
   when condition-1
   to B {
      ...
      return exp-1
   }
}
rewrite A {
  when condition-2
  to C {
    ...
    return exp-2
  }
}

Sometimes you don't need a block for computing the resulting node. It may be sufficient with an expression. In that case, you may simply write the expression instead of the block, e.g., as follows:

rewrite A {
   when ( condition-1 )
   to B exp-1
   when ( condition-2 )
   to C exp-2
}

rewrite A {
   when ( condition-1 )
   to B { return exp-1 }
   when ( condition-2 )
   to C { return exp-2 }
}

Running JastAdd from the command line

Synopsis

java -jar jastadd2.jar [options] <source files>

Source file arguments are names of .ast, .jrag and .jadd files. At least one .ast file must be provided, otherwise JastAdd will not generate any code. Some of the available options are listed below.

Options

More details about JastAdd options can be printed by passing the --help option to JastAdd.

Here is a short summary of available options:

Example

The following command generates classes according to the AST description in Toy.ast. The generated classes are placed in the package ast. The specifications in the Jrag and Jadd files are translated and woven into the generated classes.

java -jar jastadd2.jar --package=ast Toy.ast \
    NameAnalysis.jrag TypeAnalysis.jrag PrettyPrinter.jadd

ANT task

The options above are also available in an ANT task. The names for the options are the same as above, and for flag options like --beaver you specify beaver="true", for other multi-value options you specify the option value you want, for example grammar="GGG" as above.