Assignment 2: Static Checking (Part A)
In this assignment, you will implement a compiler phase that checks whether a Joos 1W program satisfies certain basic validity requirements. It is recommended that your design follow these four stages: abstract syntax tree building, environment building, type name resolution, and hierarchy checking.
Abstract Syntax Tree Building
A parse tree built using an unambiguous grammar typically contains many redundant nodes. By recursively traversing the parse tree, it is possible to build an abstract syntax tree with an analogous structure but fewer nodes. An abstract syntax tree simplifies later phases of the compiler by reducing the number of nodes and the number of different kinds of nodes that each phase needs to handle. When a compiler is implemented using a statically typed language, distinct types are typically defined for each possible kind of tree nodes, so that later compiler phases can use the type to document the tree nodes that they handle.
The environment building stage creates environments (containing classes, interfaces, fields, methods, local variables, and formal parameters) for each scope. Given a name of one of these entities, the environment should be able to locate the correct declaration of the entity.
After constructing all of the environments, the following requirements of the Joos 1W language must be checked:
- No two fields declared in the same class may have the same name.
- No two local variables with overlapping scope have the same name.
- No two classes or interfaces have the same canonical name.
The type linking stage connects each use of a named type (class or interface) to the declaration of the type. At this stage, only names that can be syntactically (according to JLS 6.5.1) determined to be names of types need to be linked. Some names are syntactically ambiguous, in the sense that type checking must be done before it can be determined whether they are names of types or of other entities (see JLS 6.5). These ambiguous names will be linked in a later assignment.
When linking type names, the following requirements of the Joos 1W language must be checked:
- No single-type-import declaration clashes with the class or interface declared in the same file.
- No two single-type-import declarations clash with each other.
- All type names must resolve to some class or interface declared in some file listed on the Joos command line.
- All simple type names must resolve to a unique class or interface.
- When a fully qualified name resolves to a type, no strict prefix of the fully qualified name can resolve to a type in the same environment.
- No package names—including their prefixes—of declared packages, single-type-import declarations or import-on-demand declarations that are used may resolve to types, except for types in the default, unnamed package.
- Every import-on-demand declaration must refer to a package
declared in some file listed on the Joos command line.
That is, the import-on-demand declaration must refer to a package
whose name appears as the
packagedeclaration in some source file, or whose name is a prefix of the name appearing in some
The fourth stage computes the inheritance relationships for classes, interfaces, methods, and fields, and checks that they conform to the various rules given in Chapters 8 and 9 of the Java Language Specification. Specifically, this stage should check that:
- A class must not extend an interface. (JLS 8.1.3)
- A class must not implement a class. (JLS 8.1.4)
- An interface must not be repeated in an implements clause or in an extends clause of an interface. (JLS 8.1.4)
- A class must not extend a final class. (JLS 184.108.40.206, 8.1.3)
- An interface must not extend a class. (JLS 9.1.2)
- The hierarchy must be acyclic. (JLS 8.1.3, 9.1.2)
- A class or interface must not declare two methods with the same signature (name and parameter types). (JLS 8.4, 9.4)
- A class must not declare two constructors with the same parameter types (JLS 8.8.2)
- A class or interface must not contain (declare or inherit) two methods with the same signature but different return types (JLS 220.127.116.11, 8.4, 8.4.2, 18.104.22.168, 22.214.171.124, 9.2, 9.4.1)
- A class that contains (declares or inherits) any abstract methods must be abstract. (JLS 126.96.36.199)
- A nonstatic method must not replace a static method (JLS 188.8.131.52)
- A method must not replace a method with a different return type. (JLS 184.108.40.206, 8.4, 8.4.2, 220.127.116.11, 18.104.22.168, 9.2, 9.4.1)
- A protected method must not replace a public method. (JLS 22.214.171.124)
- A method must not replace a final method. (JLS 126.96.36.199)
A common error in this assignment is that the compiler works correctly only when the source files are listed on the command line in a particular order, for example with all superclasses before their subclasses. When designing your compiler, be sure to consider that the source files could be listed in an arbitrary order. When testing your compiler, make sure that it still works correctly when the source files are reordered.
You are not asked to submit a report for this assignment. However, Assignment 4 will require a report covering Assignments 2, 3, and 4, so it is recommended that you start writing such a document. Your report will follow the guidelines.
As in Assignment 1,
you must hand in to Marmoset a
.zip archive containing
your source code. It should include everything required to build and run your project.
In particular, in addition to your source code, it should contain a
Makefile. Marmoset will run
make on this
to build your compiler. The
Makefile must generate an executable
(binary or shell script) called
Unlike in Assignment 1,
joosc in this and future assignments must be
able to accept multiple filenames as arguments. All of the files
listed on the
joosc command line—and only those files—are considered
part of the program being compiled.
joosc compiler should not look for classes in
.class files on the
CLASSPATH. Instead, it should read only those
Joos 1W source files listed on the command line. Thus, all classes,
including classes such as
java.lang.Object, must be available in
source form and must be specified on the
joosc command line. Unlike
javac, Joos does not care what directory a source file is in (i.e., it
does not require the directory structure of the source code to match
the package structure). However, the class declared in a file must
still have the same name as the filename.
For example, Java would require that the class
declared in the file
Object.java in the directory
whereas Joos only requires the file to be named
otherwise allows it to be in any directory.
For the purposes of this course, a minimalist version of the Java
standard library is provided. This library can be found in the
linux.student.cs environment in the directory
/u/cs444/pub/stdlib/2.0. Marmoset will include all files in this
library on the
joosc command line for every test, in addition to
other source file(s) specific to that test. The following versioning
scheme is used to make it possible to correct errors and/or to extend
the library for future assignments (although we aim to minimize the
number of changes that will be required). The 2 in the directory name
refers to Assignment 2, and the 0 is the first version of the library.
Any corrections to the Assignment 2 version of the library will appear
in the directories
2.2, etc., and the version of the library
for Assignment 3 will appear in the directory
As in Assignment 1,
joosc should process the Joos 1W files given on
the command line, produce appropriate diagnostic messages on standard
error, and exit with one of the following Unix return codes:
- 0: the input file is valid Joos 1W
- 42: the input file is not valid Joos 1W
- any other value: your compiler crashed
The archive should include all your test cases and test code that you used to test your program. Be sure to mention where these files are in your report. Do not include Marmoset public tests.
The archive should include a file named
a2.log showing the commit history
of your Git repository.
The archive should not include any extraneous non-source files. It should not include any files that ought to be automatically generated by building or running your compiler.
Your build process should not transmit data from/to the internet in any way.
We reserve the right to deduct points if your submission does not meet the requirements above.
The Marmoset tests for this assignment take several minutes to run. Do not submit more than one submission at a time to Marmoset. If Marmoset reports that your previous submission has not been tested yet, do not submit another one. Denial-of-service attacks on Marmoset will result in disciplinary action.