UofT ECE 467 (2020 Fall)

Updates from Labs 1 and 2

Changed how types are tokenized (see lab 1 page)
Added tokens for augmented assignments (see lab 1 page)
Add a production expression := name so that variable names can be used in expressions (see lab 2 page)
Replace the nonterminal type with the token TOK_TYPE (see lab 2 page)
Modify the grammar rules for augmented assignments to use the new tokens (see lab 2 page)

Introduction

In this lab, you will be modifying your parser to produce an abstract syntax tree (AST). The base class for your tree nodes is provided in src/node.<hpp|cpp>. While an input program may conform to a language's grammar, it is not always a valid program. You will implement semantic analysis to verify the correctness of the input program. Finally, you will implement a simple form of constant propagation and dead code elimination. Your task in this lab will be to:

come up with meaningful tree nodes
update your production actions in parser.y to create your AST
use proper memory management with smart pointers (in particular, std::unique_ptr)
implement semantic analysis and report errors as described below
implement constant propagation and dead code elimination as described below

Lab Description

Location Tracking

Location tracking is a simple addition with Bison's built in location tracking. A helper function make_node has been provided in parser.y. You use it as such: make_node<LeafNode>(@$, constructor args...), which returns a std::unique_ptr<LeafNode>. The @$ represents the location of the production target in Bison. This helper function is so that all your leaf nodes do not need to take a location in their constructor (simplifies the code in node.<hpp|cpp>). Again, you can read more about location tracking in Bison in sections 3.5 and 10.1.5 of the manual.

Note: due to corner cases in how Bison propagates location information, we will only be verifying the location of local variable declarations, ints, floats, and bools. You should not have to modify anything to get these to work.

Semantic Analysis

Here, you will be verifying semantic properties of your AST in verify_ast in src/compiler.cpp to ensure that the input is a valid program. It is recommended that you implement a visitor pattern to traverse your tree. You should verify the following properties:

Error	Description
type_decl	types must be one of `bool, int, float`. Functions may have return type `void`
type_mismatch	operands of a binary or relational operator have the same type
type_arg	type of a function call argument/parameter does not match function declaration
type_bool	type of an if-statement, for-statement, while-statement, or ternary expression predicate must be `bool`
type_return	type of return expression matches function declaration
main_function	a `main` function exists, and has return type `int`
return_statement	void functions do not return expressions. Non-void functions have a return statement (with an expression) on control flow paths (excess return statements are ok)
duplicate_decl	duplicate function or variable declaration in the same scope

Optimizations

In the optimize pass in compiler.cpp, you should simplify binary, unary, and relational expressions whose operands are strictly constants (if you have int x = 3; int y = x * 4; you do not need to simplify this; but you should simplify int x = 3 * 4;). You should also eliminate dead code of the following form:

if-statement with constant predicate (eliminate the test, or eliminate the if-statement entirely)
ternary operator with constant predicate (replace with the corresponding operand)
while-statement with constant false predicate (eliminate the loop)

The optimize function should return a new tree. Again, it is recommended that you iterate your tree with a visitor. Note that constant propagation may give rise to additional opportunities for dead code elimination, which you must handle. In general, dead code elimination may also create opportunities for constant propagation, but requires more advanced analysis, which you do not need to handle.

Output

If semantic analysis detects an error, you should print a line [output] <error name>: <location>, where the error name is given in the table above. On success, optimize and print_ast from compiler.cpp will be called. It is recommended but not necessary to implement these using a visitor pattern. This will be verified manually, so choose a suitable format. Include the location of each node (node->location.begin.line and node->location.begin.column which are ints). For example:

binary expression (1, 1) {
	op: + // The "+" was a token in the parser/lexer,
	      // but isn't a node in the AST,
	      // so it doesn't have a location.
	left: binary expression (1, 1) {
		op: *
		left: int 3 (1, 1)
		right: int 4 (1, 5)
	}
	right: float 5.5 (1, 9)
}

Additionally, Your compiler will be run through Valgrind to catch memory bugs; i.e. run valgrind ./src/ece467c 3 <input-file.c>.

Other Notes

You should avoid global variables. While this will not be marked, generally speaking there should be no need for global variables in this code.

Test Cases

The following test cases are provided for you.

Submission

Same as Lab 1.

UofT ECE 467 (2020 Fall) - Lab 3

Navigation

References