Reference manual for JastAdd2 R20110506

Predefined AST class

Description

Java API for untyped traversal

ASTNode

The topmost node in the hierarchy.
Supports traversal at the relatively "untyped" level of ASTNode.
Children are numbered from 0 to getNumChild()-1.

class ASTNode extends Object
   implements Iterable {
   int getNumChild();
   ASTNode getChild(int);
   ASTNode getParent();
}

List

Used to implement lists.

class List extends ASTNode { }

Opt

Used to implement optionals.
Has 0 or 1 child.

class Opt extends ASTNode { }

Basic constructs

Java API for typed traversal

abstract A;

A is an abstract class.
A corresponds to a nonterminal

abstract class A extends ASTNode { }

B: A ::= ...;

B is a concrete subclass of A
B corresponds to a production of A

class B extends A { }

C: A ::= A B C;

C has three children of types A, B, and C.
The API supports typed traversal of the children.

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

D: A;

D has no children.
D corresponds to an empty production of A

class D extends A { }

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

E has a child of type A, an optional child of type B, a list of zero or more C children, and a token of type D.

class E extends A {
   A getA();
   boolean hasB();
   B getB();
   int getNumC();
   C getC(int);
   String getD();
   setD(String);
}

Naming children

F: A ::= Foo:A Bar:B;

It is possible to name children.

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

G: A ::=
  A
  First:B
  C 
  Second:B
  D;

Note! If there is more than one child of the same type, they must be named. Here there are two children of type B. They are distinguished with the names "First" and "Second".

class G extends A {
   A getA();
   B getFirst();
   C getC();
   B getSecond();
   D getD();
}

Typed tokens

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

A ::= <T>

Here, T is a token of the Java type String.
(The set method is intended to be used only by the parser, to set the token value. This is useful when you are using JavaCC with JJTree for parsing, since JJTree can construct the AST nodes for you, but you will need to set the token values explicitly using the set method.)

class A extends ASTNode {
   String getT();
   setT(String);
}

A ::= <T:String>

This is equivalent to the example above.

A ::= <T:int>

Here, T is a token of the Java primitive type int.

class A extends ASTNode {
   int getT();
   setT(int);
}

Class hierarchy

The class hierarchy can contain any number of levels.

For example:

abstract A;
abstract B: A;
C: B;
D: C;

abstract class A extends ASTNode { }
abstract class B extends A { }
class C extends B { }
class D extends C { }

Inheriting children

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

Children are inherited by subclasses

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

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

Subclasses can add children to those specified by the superclass.

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

... example to be added ...

Subclasses can repeat/override children ... (to be explained)

Nonterminal attributes (NTAs)

A ::= B C /D/

A has three children: a B child, a C child, and a D child. The D child is an NTA (nonterminal attribute): It is not created by the parser, but must be defined by an equation. See specifying NTAs.

abstract class A {
   B getB();
   C getC();
   D getD();
}

.ast construct

Java API

Example use

C ::= D*

class C extends ASTNode {
   ...
   List getDList();
}

C c = ...;
for (D d : getDList()) {
   // Access each d (list children).
}

AST class

Java API for creating AST nodes

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

class A extends ASTNode {
   A(B, C, Opt, List, String); //Arguments must not be null
}

ASTList

class ASTList extends ASTNode {
   ASTList()
   ASTList.add(ASTNode); // Returns the same ASTList object
}

ASTOpt

class ASTOpt extends ASTNode {
   ASTOpt()
   ASTOpt(ASTNode); // The argument may be null
}

Feature

Comment

intertype declaration of AST fields, methods, and constructors.

See the prettyprinting example above. The declarations are inserted into the corresponding AST classes by the AST weaver. Any modifiers (public, private, static, etc.), are interpreted in the context of the AST class. I.e., not as in AspectJ where the public/private modifiers relate to the aspect.

intertype declaration of attributes, equations, and rewrites

See the type checking example above. For more details, Attributes.

Note that access modifiers (public, private, etc.) are not supported for attributes. All declared attributes generate public accessor methods in the AST classes.

declare additional interfaces for AST classes

E.g., in an aspect you can write

WhileStmt implements LoopInterface;

This will insert an "implements LoopInterface" clause in the generated WhileStmt class.

declare classes and interfaces in an aspect

E.g., in an aspect you can write

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

This is equivalent to declaring the interface and class in separate ordinary Java files. The possibility to declare them inside an aspect is just for convenience.

refine a method declared in another aspect

(This feature is available in JastAdd version R20051107 and later.)

Often, it is useful to be able to replace or refine methods declared in another aspect. This can be done using a "refine" clause. In the following example, the aspect A declares a method m() in the class C. In the aspect B, the method is replaced, using a "refine" clause. This is similar to overriding a method in a subclass, but here the "overridden" method is in the same class, just defined in another aspect. Inside the body of the refined method, the original method can be called explicitly. This is similar to a call to super for overriding methods.

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

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

Note that the refine clause explicitly states which aspect is refined (A in this case). Additional aspects may further refine the method. For example, an aspect C can refine the method refined in B.

AspectJ code

JastAdd code

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(...);
      ...
   }
   ...
}

Synthesized attributes

syn T A.x();

x is a synthesized attribute in class A and of type T.
There must be equations defining x in A (if A is concrete) or in all concrete subclasses of A (if A is abstract).
Note! Synthesized attributes are conceptually equivalent to abstract virtual functions (without side-effects). The main difference is that their values may be cached (see below). They can be accessed in the same way as virtual functions. I.e., the declaration generates the following Java API:

T A.x();

eq A.x() = Java-expr;

The equation defines the value of the synthesized attribute x of AST nodes of type A.
The Java-expression that defines the value must be free from externally visible side-effects. The context of the expression is the class A, and any part of the class A's API may be used in the computation, including accesses to other attributes.
Note! Equations defining synthesized attributes are conceptually equivalent to virtual method implementations (without side-effects).

eq B.x() = Java-expr;

Suppose B is a subclass to A. This equation overrides the corresponding (default) equation for A.x().
Note! This is equivalent to overriding method implementations.

Shorthand for synthesized attributes

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

The declaration of a synthesized attribute and the (default) equation for it can be written in one clause. So the clause to the left is equivalent to:

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

Inherited attributes

inh T A.y();

y is an inherited attribute in class A and of type T. There must be equations defining y in all classes that have children of type A. If a class has several children of type A, there must be one equation for each of them.

Inherited attributes can be accessed in the same way as synthesized attributes. I.e., the declaration generates the following Java API:

T A.y();

Note! Inherited attributes differ from ordinary virtual functions in that their definitions (equations/method implementations) are located in the parent AST node, rather than in the node itself.

Note! The concept of inherited attributes in this Attribute Grammar sense is completely different from object-oriented inheritance. Both attribute grammars and object-orientation were invented in the late 60's and the use of the same term "inheritance" is probably a mere coincidence: In AGs, inheritance takes place between nodes in a syntax tree. In OO, inheritance takes place between classes in a class hierarchy.

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

This equation defines the value of the inherited attribute y() of the A child of a C node.
Note! The Java-expression executes in the context of C.
Note! The equation is similar to a method implementation.
Note! The equation actually applies to all inherited attributes y in the subtree rooted at A, provided that they declare the y attribute. See below under broadcast attributes.

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

Suppose D is a subclass of C. In this case, the equation overrides the previous one.
Note! This is analogous to overriding a virtual method implementation.

Method syntax

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

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

Lazy attributes
(cached attributes)

An attribute can be declared lazy in order to speed up the evaluation. An attribute that is declared lazy will automatically 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.

syn lazy A.x();

Here, the attribute x of class A is declared lazy.

Refine attribute

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

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 this example, the equation replaces the corresponding equation declared in the aspect S. The value from the original equation in S can be accessed by the expression S.B.x()

(This feature is available in JastAdd version R20051107 and later.)

Examples of refine eq on Google Code Search.

Parameterized attributes

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

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

Here, x is a parameterized synthesized attribute. The equation is similar to a method implementation and the argument values can be used in the computation of the resulting value.

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

Here, y is a parameterized inherited attribute. The equation executes in the context of C and can in addition access the arguments (a in this case).

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, namely broadcasting of an inherited attribute to 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();

Here, the equation defines an inherited attribute y() declared in the A child of a C node. This equation actually applies not only to the inherited y() attribute of the A child, but to all inherited y() attributes in the whole subtree of A. In order to for a node N in the subtree to access y(), the attribute must, however, be exposed by declaring y() as an inherited attribute of N.

inh T B.y();

Here, the attribute y() is exposed in B by declaring it as an inherited attribute there. If there is a B node that is in the subtree rooted at the A that is a child of a C node, then the equation above will apply.

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() = ...index...

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.

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.

Examples of rewrite on Google Code Search.

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 together. So, e.g., writing

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

... is equivalent to:

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 
}

... which is equivalent to

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

Circular attributes

Attributes can be circularly defined. I.e., 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".
If a lazy attribute is circular, but not declared as such, this will 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.

Examples of syn circular at Google Code Search.

Examples of inh circular at Google Code Search.

Newer syntax

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

• 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.
• Examples of syn nta at Google Code Search.
• Examples of inh nta at Google Code Search. (No matches on 2011-May-03)

Older syntax

In the older syntax, you introduce a nonterminal attribute 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 creation 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

A ::= B /C/;

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

A ::= B /C*/;

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