User Tools

Site Tools


cc17:assignment_5

This is an old revision of the document!


Type checking

Introduction

In this assignment you finish the semantic analysis phase of your compiler. After this step, the front-end of your Extended MiniJava compiler is completed. This means that your compiler is now capable of rejecting all invalid programs, and accepting all valid programs. In the final phase you will be able to turn these valid programs into assembly code that runs on the JVM, just like javac. This is a great achievement!

If you have any questions about this assignment please do not hesitate to ask the instructor.

Type checking

A valid eMiniJava program has the following properties:

  • It follows the eMiniJava concrete syntax.
  • It respects all the constraints mentioned in the Name Analysis phase.
  • Method overriding respects some typing constraints:
    • The overriding method must have exactly as many arguments as the overridden one.
    • The types of the parameters in the overriding and overridden methods must match exactly (no contravariance allowed).
    • The return type must match exactly (no covariance allowed, contrary to Java).
  • All expressions typecheck and have the expected type (the returned expression matches the declared return type, for instance).
  • All statements typecheck.

Your goal in this assignment is to enforce all the constraints not enforced already by the previous phases.

Note: The language and the type rules presented in the course may differ from the rules of Extended MiniJava. If there are any differences, please use the description on the current page for your implementation, and not the rules in the lecture. Of course, feel free to clarify with the instructor if you have any changes.

Types

The following primary types exist in eMiniJava (note that we prefix them with T to differentiate them from the tree nodes with the same name, for instance):

  • TInt
  • TBoolean
  • TInt[]
  • TString 1)

Additionnally, we have object types:

  • TClass[name]

We define a subtyping relation on these types. All primary types are subtypes of themselves and of no other type. For instance:

  • TInt <: TInt

All object types are subtypes of themselves and the special “Object” object type. The subtyping relation is also transitive.

  • TClass[name] <: TClass[name] and TClass[name] <: TClass[Object]
  • TClass[B] <: TClass[A] and TClass[C] <: TClass[B] implies TClass[C] <: TClass[A]

With this in mind, we give some of the non-trivial typing constraints. This is naturally not an exhaustive list of what you should implement, but we expect you to be able to deduce the other rules unambiguously yourself (if in doubt about a rule, please ask the instructor).

Overloaded "+"

The “+” operator can represent integer addition, or string concatenation. If the types of e1 and e2 are T1 and T2 respectively, we have for the type Ts of e1 + e2:

  • T1 = TInt and T2 = TIntTs = TInt
  • T1 = TString and T2 = TIntTs = TString
  • T1 = TInt and T2 = TStringTs = TString
  • T1 = TString and T2 = TStringTs = TString

All other values for T1 and T2 should result in type errors.

Comparison operator

The “==” operator is also overloaded. Expression e1==e2 is type correct if and only if one of the following two cases apply:

  • e1 and e2 are both primitive types, and these types are equal
  • e1 and e2 are both classes (in which case they can be different classes)

Note that it is not type correct to compare a primitive type to a class type.

Note that strings and arrays of integers are considered primitive!

Consider the following code.

class A {}
class B {}

Let e1:T1 and e2:T2. Then the following table summarizes some of the cases.

T1 T2 type checks?
int int yes
String String yes
String A no
A int no
A B yes
A int[] no
int int[] no

Method calls

The dereferenced object must be of an object type, and its class must declare the method called. The number of arguments must of course match the number of parameters. The arguments passed must be subtypes of the declared parameters (matching one-by-one).

Assignment

Assignment of an expression of type T can only be done to a variable of type S such that T <: S.

Assignment to array elements can only be done through an array variable, and the index must be an integer expression. The assigned value must be an integer.

This

this is always considered to carry the object type corresponding to the class where it occurs.

Returned expression

The returned expression must be of a subtype of the declared return type.

println Statement

We will consider println calls to be valid if the argument is an integer, a Boolean or a string. The type of a println expression is void.

Suggested implementation

Here are the steps we suggest you take:

  • Modify your analyzer such that it attaches types to the various symbols. Since symbols are shared, this has the advantage that you can recover the proper type from any occurence of the symbol.
  • Modify your analyzer so that it enforces the overriding type constraints on methods.
  • Implement your typechecker. Make sure you attach the types to the expression subtrees (this will be required for code generation, to differentiate between the versions of the overloaded operators, for instance).
  • While you typecheck expressions, attach the proper symbols to the occurences of method calls (since you can now determine the class from which they are called 2).
  • Test, test, test!

Interface

Since we are not imposing any code structure for your programs, it is extremely important for your compiler to exactly follow a fixed interface as described here. This allows us to uniformly run and test all the projects from different groups of students. Command-line is the primary interface for your users to interact with your compiler. A general form for the command-line interface is as follows:

emjc [options] <source file>

For this phase of assignment, there are five possible options. If the user does not provide a correct option, the compiler treats it the same as the –help option.

  1. ––help: Prints a synopsis of options
  2. ––pp: Pretty-prints the input file to the standard output
  3. ––lex: Generates output from lexical analysis as described in Assignment 2.
  4. ––ast: Generates output from syntactic analysis as described in Assignment 3.
  5. ––name: Generates output from name analysis as described in Assignment 4
  6. ––type: Generates output from type analysis

After executing the compiler with the option ––type for the source file filename.emj the compiler either accepts the program as a good eMiniJava program with printing out the following line:

Valid eMiniJava Program

Or, it prints out a set of errors (such as unknown identifier). Like the previous phases the format of an error message is the following:

<line>:<column> error:<description>

where <line> and <column> indicate the beginning position of the error, and <description> details the error.

It is very important that your compiler does not stop at the first type error.

Deadline and Deliverables

The deadline of the this assignment is April 21st at 11:59pm (https://mycourses.rit.edu). Please upload all your files as a single zip file. You should include a readme.txt file in your package to describe how your source code can be compiled and built. Ideally your project should include a user-friendly compiling technique with Makefile, Ant or similar tools.

When grading, we are serious about simple programming errors. You are writing a compiler to check the programs of other people, so your compiler should not have simple errors itself! Your compiler should never crash for an incorrect input. We expect your compiler to give a comprehensive error when the user does not provide a valid input to it.

1)
We consider String to be a primary type, unlike in Java where it is a proper class. No methods can be called on Strings, for instance.
2)
Although what you are able to determine may not match the run-time types.
cc17/assignment_5.1492102789.txt.gz · Last modified: 2017/04/13 12:59 by hossein