(5/5)

Project 3: Type Checking

The goal of this project is to give you experience in Hindley-Milner type checking.

We begin by introducing the grammar of our language which is based on the previous project with additional constructs. Then we will discuss the semantics of our language and type checking rules. Finally, we will go over a few examples and formalize the expected output.

1. Lexical Specification

Here is the list of tokens that your lexical analyzer should recognize (the new tokens are listed first):

2. Grammar

Here is the grammar for our input language:

3. Language Semantics

3.1. Types

The language has three built-in types: int, real, and bool.

3.2. Variables

Programmers can declare variables either explicitly or implicitly.

• Explicit variables are declared in an var_list of a var_decl.

• A variable is declared implicitly if it is not declared explicitly but it appears in the program body.

Example

Consider the following program written in our language:

This program has four variables declared: x , y , z , and w , with x and y explicitly declared and z and

w implicitly declared.

3.3. Type System

Our language uses structural equivalence for checking type equivalence. Implicit types will be inferred from the usage (in a simplified form of Hindley-Milner type inference).

Here are all the type rules/constraints that your type checker will enforce (constraints are labeled for reference):

• C1: The left hand side of an assignment should have the same type as its right hand side.

• C2: The operands of a binary operator (GTEQ, PLUS, MINUS, MULT, DIV, GREATER, LESS , LTEQ , EQUAL and NOTEQUAL) should have the same type (it can be any type).

• C3: The operand of a unary operator (NOT) should be of type bool.

• C4: Condition of if and while statements should be of type bool.

• C5: The expression that follows the switch keyword in switch_stmt should be of type int.

• The type of expression binary_operator op1 op2 is the same as the type of op1 and

op2 if operator is PLUS, MINUS, MULT, or DIV. Note that op1 and op2 must have the same type due to C2.

• The type of expression binary_operator op1 op2 is bool if operator is GREATER, LESS, GTEQ, LTEQ, EQUAL, or NOTEQUAL.

• The type of unary_operator op is bool.

• NUM constants are of type int.

• REALNUM constants are of type real.

• true and false values are of type bool.

4. Output

There are two scenarios:

• There is a type error in the input program

• There are no type errors in the input program

4.1. Type Error

If any of the type constraints (listed in the Type System section above) is violated in the input program, then the output of your program should be:

Where <line_number> is replaced with the line number that the violation occurs and <constraint> should be replaced with the label of the violated type constraint (possible values are C1 through C5). Note that you can assume that anywhere a violation can occur it will be on a single line.

(5/5)

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of