In this page: Due date | Overview | Specifications | Handing in | Grading criteria
For this assignment you will write a type checker for base programs represented as abstract-syntax trees. Your main task will be to write type checking methods for the nodes of the AST. In addition you will need to:
P5.java (an extension of P4.java).typeErrors.base and test.base
to test your new code.The files are:
ast.javabase.cupbase.jlexErrMsg.javaMakefileP5.javaSym.javaDuplicateSymNameException.javaSymTable.javaEmptySymTableException.javaType.java
Here is p5.zip file.
It is recommended to start your project with it.
The type checker will determine the type of every expression represented in the abstract-syntax tree and will use that information to identify type errors. In the base language we have the following types:
integer, logical, void (as function return types only),
strings, tuple types, and function types
A tuple type includes the name of the tuple (i.e., when it was
declared/defined).
A function type includes the types of the parameters and the return type.
The operators in the base language are divided into the following categories:
The type rules of the base language are as follows:
logical operators and conditions:
Only logical expressions can be used as operands of logical operators or in
the condition of an if or while statement.
The result of applying a logical operator to logical operands is
logical.
arithmetic and relational operators:
Only integer expressions can be used as operands of these operators.
The result of applying an arithmetic operator to integer operand(s) is integer.
The result of applying a relational operator to integer operands is logical.
equality operators:
Only integer expressions, logical expressions, or string literals can be
used as operands of these operators.
Furthermore, the types of both operands must be the same.
The result of applying an equality operator is logical.
assignment operator:
Only integer or logical expressions can be used as operands of an assignment operator.
Furthermore, the types of the left-hand side and right-hand side must be the same.
The type of the result of applying the assignment operator is the type of the
right-hand side.
write and read:
Only an integer or logical expression or a string literal can be
printed by write.
Only an integer or logical identifer can be read by read.
Note that the identifier can be a field of a tuple type (accessed
using : ) as long as the field is an integer or a logical.
function calls:
A function call can be made only using an identifier with function type
(i.e., an identifier that is the name of a function).
The number of actuals must match the number of formals.
The type of each actual must match the type of the corresponding formal.
function returns:
A void function may not return a value.
A non-void function may not have a return statement without a value.
A function whose return type is integer may only return an integer;
a function whose return type is logical may only return a logical.
Note: some compilers give error messages for non-void functions that
have paths from function start to function end with no return statement.
For example, this code would cause such an error:
integer f{} [
write << "hello".
]
However, finding such paths is beyond the capabilities of our base compiler, so don't worry about this kind of error.
You must implement your type checker by writing appropriate member methods for the
different subclasses of ASTnode.
Your type checker should find all of the type errors described in the following table;
it must report the specified position of the error and it must give exactly
the specified error message.
(Each message should appear on a single line, rather than how it is formatted in the
following table.)
| Type of Error | Error Message | Position to Report |
|---|---|---|
Writing a function;
e.g., "write << f", where f is a function name.
|
Write attempt of function name |
1st character of the function name. |
Writing a tuple name;
e.g., "write << P", where P is the name of a tuple type.
|
Write attempt of tuple name |
1st character of the tuple name. |
Writing a tuple variable;
e.g., "write << p", where p is a variable declared to be of a tuple type.
|
Write attempt of tuple variable |
1st character of the tuple variable. |
Writing a void value (note: this can only happen if there is an attempt to write the return value from a void function);
e.g., "write << f()", where f is a void function.
|
Write attempt of void |
1st character of the function name. |
Reading a function;
e.g., "read >> f", where f is a function name.
|
Read attempt of function name |
1st character of the function name. |
Reading a tuple name;
e.g., "read >> P", where P is the name of a tuple type.
|
Read attempt of tuple name |
1st character of the tuple name.
|
Reading a tuple variable;
e.g., "read >> p", where p is a variable declared to be of a tuple type.
|
Read attempt of tuple variable |
1st character of the tuple variable. |
Calling something other than a function;
e.g., "x().", where x is not a function name.
Note: In this case, you should not type-check the actual parameters.
|
Call attempt on non-function |
1st character of the variable name. |
| Calling a function with the wrong number of arguments. Note: In this case, you should not type-check the actual parameters. | Function call with wrong # of args |
1st character of the function name. |
| Calling a function with an argument of the wrong type. Note: you should only check for this error if the number of arguments is correct. If there are several arguments with the wrong type, you must give an error message for each such argument. | Actual type does not match formal type |
1st character of the first identifier or literal in the actual parameter. |
Returning from a non-void function with a plain return statement
(i.e., one that does not return a value).
|
Return value missing |
0,0 |
Returning a value from a void function. |
Return with value in |
1st character of the first identifier or literal in the returned expression. |
Returning a value of the wrong type from a non-void function. |
Return value wrong type |
1st character of the first identifier or literal in the returned expression. |
Applying an arithmetic operator (+, -, *, /)
to an operand with type other than integer.
Note: this includes the ++ and -- operators.
|
Arithmetic operator used with non-integer operand |
1st character of the first identifier or literal in an operand that is an expression of the wrong type. |
Applying a relational operator (<, >, <=, >=)
to an operand with type other than integer.
|
Relational operator used with non-integer operand |
1st character of the first identifier or literal in an operand that is an expression of the wrong type. |
Applying a logical operator (~, &, |)
to an operand with type other than logical.
|
Logical operator used with non-logical operand |
1st character of the first identifier or literal in an operand that is an expression of the wrong type. |
Using a non-logical expression as the condition of an if. |
Non-logical expression used in if condition |
1st character of the first identifier or literal in the condition. |
Using a non-logical expression as the condition of a while. |
Non-logical expression used in while condition |
1st character of the first identifier or literal in the condition. |
Applying an equality operator (==, ~=) to operands of two
different types (e.g., "j == true", where j is of type
integer), or assigning a value of one type to a variable of another type
(e.g., "j = true", where j is of type integer).
|
Mismatched type |
1st character of the first identifier or literal in the left-hand operand. |
Applying an equality operator (==, ~=) to void
function operands (e.g., "f() == g()", where f and g
are functions whose return type is void).
|
Equality operator used with calls |
1st character of the first function name. |
Comparing two functions for equality, e.g., "f == g" or "f ~= g",
where f and g are function names.
|
Equality operator used with function names |
1st character of the first function name. |
Comparing two tuple names for equality;
e.g., "A == B" or "A ~= B", where A and B
are the names of tuple types.
|
Equality operator used with tuple names |
1st character of the first tuple name. |
Comparing two tuple variables for equality;
e.g., "a == b" or "a ~= b", where a and a
are variables declared to be of tuple types.
|
Equality operator used with tuple variables |
1st character of the first tuple variable. |
Assigning a function to a function;
e.g., "f = g.", where f and g are function names.
|
Assignment to function name |
1st character of the first function name. |
Assigning a tuple name to a tuple name;
e.g., "A = B.", where A and B are the names of
tuple types.
|
Assignment to tuple name |
1st character of the first tuple name. |
Assigning a tuple variable to a tuple variable;
e.g., "a = b.", where a and b are variables
declared to be of tuple types.
|
Assignment to tuple variable |
1st character of the first tuple variable. |
A single type error in an expression or statement should not trigger multiple error messages.
For example, assume that P is the name of a tuple type,
p is a variable declared to be of tuple type P,
and f is a function that has one integer parameter and returns a logical.
Each of the following should cause only one error message:
write << P + 1 $ P + 1 is an error; the write is OK
(true + 3) * 4 $ true + 3 is an error; the * is OK
true & (false | 3) $ false | 3 is an error; the & is OK
f("a" * 4). $ "a" * 4 is an error; the call is OK
1 + p(). $ p() is an error; the + is OK
(true + 3) == x $ true + 3 is an error; the == is OK
$ regardless of the type of x
One way to accomplish this is to use a special ErrorType for expressions that
contain type errors.
In the second example above, the type given to (true + 3) should be ErrorType,
and the type-check method for the multiplication node should not report
"Arithmetic operator with non-integer operand" for the first operand.
But note that the following should each cause two error messages
(assuming the same declarations of f as above):
true + "hello" $ one error for each of the non-integer operands of the +
1 + f(true) $ one for the bad arg type and one for the 2nd operand of the +
1 + f(1, 2) $ one for the wrong number of args and one for the 2nd operand of the +
return 3+true. $ in a void function: one error for the 2nd operand to +
$ and one for returning a value
To provide some help with this issue,
here is an example input file, along
with the corresponding error messages.
(Note: This is not meant to be a complete test of the type checker;
it is provided merely to help you understand some of the messages you need to report,
and to help you find small typos in your error messages.
If you run your program on the example file and put the output into a new file,
you can use the Linux utility diff to compare your file of error messages with
the one supplied here.
This will help both to make sure that your code finds the errors it is supposed to find,
and to uncover small typos you may have made in the error messages.)
You will need to modify P5.java.
The main program, P5.java, will be similar to P4.java, except that if
it calls the name analyzer and there are no errors, it will then call the type checker.
You will need to write two input files to test your code:
typeErrors.base should contain code with errors detected by the
type checker.
For every type error listed in the table above, you should include an instance
of that error for each of the relevant operators, and in each part of a program
where the error can occur (e.g., in a top-level statement, in a statement
inside a while loop, etc.).
test.base should contain code with no errors that exercises all of
the type-check methods that you wrote for the different AST nodes.
This means that it should include (good) examples of every kind of statement
and expression.
Note that your typeErrors.base should cause error messages to be output,
so to know whether your type checker behaves correctly, you will need to know what
output to expect.
As usual, you will be graded in part on how thoroughly your input files test your program. Make sure that you submit the input files you used to test your program.
Here are few words of advice about various issues that come up in the assignment:
For this assignment you are free to make any changes you want to the code in
ast.java. For example, you may find it helpful to make small changes
to the class hierarchy, or to add new fields and/or methods to some classes.
As for name analysis, think about which AST nodes need to have type-check methods. For example, for type checking, you do not need to visit nodes that represent declarations, only those that represent statements.
Please read the following handing in instructions carefully.
Turn in the following files to the appropriate assignment in Gradescope (note: these should be the only files changed/needed to run with the provided materials):
ast.javaP5.javatypeErrors.basetest.basePlease ensure that you do not turn in any sub-directories or put your Java files in any packages.
If you are working in a pair, make sure both partners are indicated when submitting to Gradescope.
General information on program grading criteria can be found on the Assignments page.
For more advice on Java programming style, see these style and commenting standards (which are essentially identical to the standards used in CS200 / CS300 / CS400).