User Tools

Site Tools


cc18:assignment_5

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

cc18:assignment_5 [2018/03/23 11:03] (current)
hossein created
Line 1: Line 1:
 +====== ​ Type checking ======
  
 +===== Introduction =====
 +
 +In this assignment you finish the semantic analysis phase of your compiler. ​ After this step, the front-end of your  [[cc17:​eminijava|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 [[cc17:​eminijava|eMiniJava]] program has the following properties:
 +  * It follows the eMiniJava concrete syntax.
 +  * It respects all the constraints mentioned in the [[cc18:​assignment_4|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 [[http://​en.wikipedia.org/​wiki/​Covariance_and_contravariance_(computer_science)|contravariance]] allowed).
 +    * The return type must match exactly (no [[http://​en.wikipedia.org/​wiki/​Covariance_and_contravariance_(computer_science)|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 [[cc17:​eminijava|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 [[cc17:​eminijava|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** ((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.))
 +
 +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 **e**1 and **e**2 are **T**1 and **T**2 respectively,​ we have for the type **T**s of **e**1 + **e**2:
 +
 +  * **T**1 = **TInt** and **T**2 = **TInt** -> **T**s = **TInt**
 +  * **T**1 = **TString** and **T**2 = **TInt** -> **T**s = **TString**
 +  * **T**1 = **TInt** and **T**2 = **TString** -> **T**s = **TString**
 +  * **T**1 = **TString** and **T**2 = **TString** -> **T**s = **TString**
 +
 +All other values for **T**1 and **T**2 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.
 +
 +<code java>
 +class A {}
 +class B {}
 +</​code>​
 +
 +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 ((Although what you are able to determine may not match the run-time types.)).
 +  * 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 **six** possible options. If the user does not provide a correct option, the compiler treats it the same as the --help option.
 +
 +  - ''​––help'':​ Prints a synopsis of options
 +  - ''​––pp'':​ Pretty-prints the input file to the standard output
 +  - ''​––lex'':​ Generates output from lexical analysis as described in [[cc18:​assignment_2|Assignment 2]].
 +  - ''​––ast'':​ Generates output from syntactic analysis as described in [[cc18:​assignment_3|Assignment 3]].
 +  - ''​––name'':​ Generates output from name analysis as described in [[cc18:​assignment_4|Assignment 4]]
 +  - ''​––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 4th 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. 
cc18/assignment_5.txt · Last modified: 2018/03/23 11:03 by hossein