The PicoJava language is designed to be able to illustrate the essential parts of name resolution and type analysis for object-oriented languages.

PicoJava supports single inheritance of classes. Classes can also be nested inside each other (like inner classes in Java). Name resolution thus has to deal with a combination of inheritance and nesting.

A PicoJava class can contain variables and statements. These constructs suffice to be able to illustrate important type checking problems, e.g., dealing with type hierarchies in assignment.

PicoJava variables can be accessed using qualified access. This illustrates the interdependences between name resolution and type analysis.

Note that PicoJava is only intended as a language for illustrating typical static semantics problems. It would need to be complemented with many additional language features in order to be able to express meaningful executable programs. For example, there are no methods in PicoJava, and no "new" expressions. These can easily be added, but do not contribute to illustrating the fundamental issues in static semantics mentioned above.

The following example programs illustrate a legal and an illegal picojava program:

• examples/legal.pj
• examples/illegal.pj

The Compiler tool

The tool Compiler is built using the AST classes generated by JastAdd. Run it with the following command:

   java -cp tools/beaver-rt.jar:. Compiler PicoJava-program
      

Implementation overview

Scanning and parsing is implemented using the third-party tools Flex and Beaver. The main program is written in Java. The rest of the tool (name resolution, type analysis, error checking, etc.) is implemented using JastAdd. Tests are implemented using the JUnit framework.

The implementation is structured into the following files:

Main program

• Compiler.java: Simply parses the input file and prints error messages. All the static-semantics is performed implicitly as needed when the error-checking computation accesses the AST and its attributes.

Scanning and Parsing

• picojava.flex: Input to flex. See tests/ScannerTests.java for examples of legal and illegal tokens.
• picojava.parser: Input to beaver. Uses semantic actions to construct the AST. See tests/ParserTests.java for small examples of syntactially legal and illegal programs. Example programs can be found in the other test cases as well.

Abstract Syntax

• picojava.ast: Defines the abstract syntax as classes.

Static Semantics

• NameResolution.jrag: Defines name resolution for the PicoJava language. Uses reference attributes to bind accessed names to their declarations. Also illustrates parameterized attributes and broadcasting.
• TypeAnalysis.jrag: Uses reference attributes to bind each expression to a type object. Also illustrates double dispatching, rewrites, and circular attributes.
• PredefinedTypes.jrag: Uses nonterminal attributes to add predefined types like boolean and class Object to the AST.
• NullObjects.jrag: Uses the Null design pattern to simplify type comparisons for undeclared accesses.

Checking errors

• ErrorCheck.jadd: An imperative aspect that prints out error messages based on the information computed in the NameResolution and TypeAnalysis aspects.

A PicoJava program consists of a block with declarations and statements in it.

There are two main kinds of declarations: classes and variables.

A class can optionally inherit from another class.

A variable has a type which is either a class type or the primitive predefined type boolean.

A class has a body which is a block. Note that classes can be nested since a class can be declared inside the body of another class.

The statements in a block can be assignments or while statements.

Variables in other objects can be accessed using ordinary qualified access (dot-notation).

The abstract syntax is defined in picojava.ast.

Predefined types are handled by inserting explicit declarations for them into the AST, as children of the Program root node. This is implemented by a list nonterminal attribute, whose value is defined by an equation. The AST nodes for the predefined types are thus not created by the parser, they are instead created automatically by the attribute evaluator.

The nonterminal attribute is defined in PredefinedTypes.jrag as a synthesized attribute, and its defining equation creates a type declaration for "boolean, and also an object of type UnknownDecl which is used for missing declarations and types.

In order to be able to refer to the object representing "boolean", a reference attribute named "booleanType" is broadcast using an inherited attribute and exposed at various places where it is needed.

The name resolution is defined in the aspect NameResolution.jrag. For each Access node, an attribute decl() is defined which refers to the appropriate Decl node. If there is no matching declaration, the decl() attribute will be the UnknownDecl, applying the Null design pattern.

The decl() attribute constitutes the API of the name resolution module that is useful for other aspects to access. For example, the type checker can use the decl() attribute in order to find the type of an Access.

• Usual nesting applies: Names declared in an outer block are visible also in inner blocks, unless shadowed by a declaration of the same name in the inner block.
• Order of declaration is irrelevant within a block. This is slightly different from ordinary Java where the order is irrelevant only for methods and classes, but not for variables. In PicoJava, a variable declared inside a block is visible also to statements above it in the block body.

Basic name resolution is implemented by two attributes:

• Synthesized attributes localLookup(String) which are defined for constructs that contain declarations, e.g., Block. This attribute searches through the local declarations to find one with a given name. The position of the access is not taken into account, so the order of declaration is irrelevant within a block.
• Inherited attributes lookup(String) which return the visible declaration of a given name. IdUse calls lookup(String) to find its declaration. Constructs that control scope rules define the lookup attribute for their children, typically by delegating to localLookup attributes, and to their own lookup attribute defined by the context. A Block defines lookup(String) by delegating first to its own localLookup (searching through local declarations), and then to its own lookup. This way ordinary nesting is implemented.

• Inheritance: Names declared in a class are visible also in subclasses.
• Combining inheritance and nesting: For a class nested inside a block, the declarations in the superclasses will shadow declarations in the outer block that have the same name.

• To implement inheritance, each ClassDecl has a synthesized attribute remoteLookup(String) which looks through the declarations of the class and (if needed) declarations in the superclasses. This attribute is intended for handling lookup from accesses inside subclasses and from qualified accesses.
• To combine inheritance with nesting, each ClassDecl defines lookup(String) to first look in the superclass chain (using the remoteLookup(String) attribute), before looking in the surrounding context.

Test cases for inheritance are found in tests/InheritanceNameResolutionTests.java.

To implement qualified access, a Dot redefines lookup(String) for its right-hand identifier. Instead of searching in the context, a remote lookup is done on the object's type.

Test cases for qualified access are found in tests/DotNameResolutionTests.java

The main goal of type analysis is to find the type of each expression.

The type analysis is defined in the aspect TypeAnalysis.jrag.

The API of the type analysis module consists of the following attributes

• Expressions and declarations have a type() attribute that is a reference to the appropriate type declaration. If there is no such appropriate declaration, the type() attribute will be the UnknownDecl, applying the Null design pattern.
• Type declarations have a parameterized attribute subtypeOf(TypeDecl) which compares the two types.
• Expressions have a boolean attribute isValue() which is true if the expression denotes a value i.e., something that can be stored in a variable.
• Classes have a boolean attribute hasCycleOnSuperclassChain() that is true if there is a cycle somewhere on the superclass chain.
• Classes have a ClassDecl attribute superClass that refers to the superclass declaration if it exists and is appropriate, e.g., without any cycles on the superclass chain, otherwise this attribute is null.

Test cases for the type analysis are found in tests/TypeAnalysisTests.java.

The subtype relation is implemented using the parameterized attribute subtypeOf(TypeDecl). The implementation is done via double dispatching. I.e., for each subclass X of TypeDecl, another attribute supertypeOfX(TypeDecl) is introduced which is called in X's implementation of subtypeOf, reversing the argument and the receiver.

The double dispatching provides an open way of implementing the comparison: New kinds of TypeDecls can be introduced without having to change the TypeAnalysis.jrag module. For example, to add the Null object UnknownDecl, its type comparison with other TypeDecls could be added completely inside the module NullObjects.jrag.

When the parser constructs the initial AST, it cannot know the declarations of the accessed identifiers, so it constructs Use nodes for all accessed identifiers. After name resolution, however, the declaration is known. It is useful to then replace the Use node with more specialized nodes: VarUse or TypeUse, depending on if the declaration is a variable or a type declaration. This is specified by two context-dependent rewrite rules in the type analysis module.

The replacement of Use nodes by VarUse or TypeUse, simplifies other computations and supports extensibility. We can see this in the computation of the isValue() attribute. Without the rewrite, this attribute would have to be defined by testing the type of the decl() attribute (using instanceof). If we later on extend the language with more kinds of declarations, the definition of the isValue() attribute might need to be changed. But with the rewriting solution, we can simply add a rewrite for the corresponding new kind of use, and add an isValue() equation for that class.

We apply the Null design pattern to missing declarations and other situations where there are static-semantic errors. I.e., instead of representing a missing declaration as null, it is represented by a singleton UnknownDecl object. UnknownDecl is also used for representing inappropriate accesses, e.g., accessing a variable name where a class name is expected.

The UnknownDecl should be compatible with everything in order to not generate meaningless error messages. So it is defined to be both a supertype and a subtype of other types. Thanks to the double dispatching discussed above, it is possible to define this completely within the NullObjects.jrag module, rather than having to change the Type Resolution module.

The singleton UnknownDecl object is created by an NTA equation and placed in the list of predefined declarations in the root of the AST. A reference to the object is broadcast through the AST, and exposed at the various places in the AST where it is needed.

Errorchecking is implemented by an imperative module ErrorCheck.jadd. The API contains a method errors() for the Program (root) node. This method simply traverses the AST and collects error messages in a Collection object that is returned, using the attributes in the API:s of the static-semantics modules.

Test cases for the error checking are found in tests/ErrorCheckTests.java.