5/5 - (1 vote)

Your goal is to finish an incomplete parser and write a type checker for a given language. The input to your project will be a program and the output will be either error messages if there is a type mismatch or a success message if there is no type mismatch. Your type checker will enforce semantic checks on the input program, and will be described in the following.

Grammar Description

program  decl bodydecl  type_decl_section var_decl_sectiontype_decl_section  TYPE type_decl_listtype_decl_section  type_decl_list  type_decl type_decl_listtype_decl_list  type_decltype_decl  id_list COLON type_name SEMICOLONtype_name  REALtype_name  INTtype_name  BOOLEANtype_name  STRINGtype_name  LONGtype_name  IDvar_decl_section  VAR var_decl_listvar_decl_section  var_decl_list  var_decl var_decl_listvar_decl_list  var_declvar_decl  id_list COLON type_name SEMICOLONid_list  ID COMMA id_listid_list  IDbody  LBRACE stmt_list RBRACEstmt_list  stmt stmt_liststmt_list  stmtstmt  while_stmtstmt  assign_stmtstmt  do_stmtstmt  switch_stmtwhile_stmt  WHILE condition bodyassign_stmt  ID EQUAL expr SEMICOLONdo_stmt  DO body WHILE condition SEMICOLONswitch_stmt  SWITCH ID LBRACE case_list RBRACEcase_list  case case_listcase_list  casecase  CASE NUM COLON bodyexpr  term PLUS exprexpr  term MINUS exprexpr  termterm  factor MULT termterm  factor DIV termterm  factorfactor  LPAREN expr RPARENfactor  NUMfactor  REALNUMfactor  IDcondition  IDcondition  primary relop primaryprimary  IDprimary  NUMprimary  REALNUMrelop  GREATERrelop  GTEQrelop  LESSrelop  NOTEQUALrelop  LTEQ

The tokens used in the grammar description are:

TYPE = TYPECOLON = :SEMICOLON = ;REAL = REALINT = INTBOOLEAN = BOOLEANSTRING = STRINGLONG = LONGVAR = VARCOMMA = ,LBRACE = {RBRACE = }WHILE = WHILEEQUAL = =DO = DOSWITCH = SWITCHCASE = CASEPLUS = +MINUS = -MULT = *DIV = /LPAREN = (RPAREN = )GREATER = >GTEQ = >=LESS = <LTEQ = <=NOTEQUAL = <>ID = letter(letter | digit)*NUM = 0 | (digit digit*)REALNUM = NUM . digit*

Language Semantics

As can be seen from the grammar, in this language types are first declared, then variables are declared, then the body of the program follows.

Types

The language has five built-in types: INT, REAL, BOOLEAN, STRING, and LONG.

Programmers can declare types either explicitly or implicitly.

Explicit types are names that are not built-in types and that have their first appearance in the program as part of the id_list of a type_decl.
Implicit types are not built-in types and not explicit user-declared types. Implicit types have their first appearance as a type_name in a var_decl.

Example

Consider the following program written in our language:

TYPE  a : INT;  b : a;VAR  x : b;  y : c;{  y = x;}

There are three types declared by the programmer in this example, a, b, and c, where a and b are explicit types and c is an implicit type.

Variables

Programmers can declare variables either explicitly or implicitly.

Explicit variables are declared in an id_list of a var_decl.
Implicit variables are declared if it is not declared explicitly but it appears in the program body.

Example

Consider the following program written in our language:

TYPE  a : INT;  b : a;VAR  x : b;  y : c;{  y = x;  z = 10;  w = z * 5;}

This program has four variables declared: x, y, z, and w, with x and y explicitly declared and z and w implicitly declared. Note that the implicitly declared variables z and w also have an implicitly declared type.

Type System

Our language uses structural equivalence for checking type equivalence.

Implicit types (in variable declarations or on implicitly declared variables) 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:

Assignment cannot be made between variables of different types
Operations (PLUS, MINUS, MULT, and DIV) cannot be applied to operands of different types (but can be applied to operands of the same type, including STRING and BOOLEAN)
Relational operators (relop) cannot be applied to operands of different types (but can be applied to operands of the same type, including STRING and BOOLEAN)
The result of p1 relop p2 is of type BOOLEAN (assuming that both p1 and p2 are the same type)
condition should be of type BOOLEAN
The type of an expr is the same as the type of its operands
The variable that follows the SWITCH keyword in switch_stmt should be of type INT
NUM constants are of type INT
REALNUM constants are of type REAL

Incomplete Parser

The parser given on the submission site is incomplete, as it is missing an implementation for while_stmt, condition, do_stmt, switch_stmt, case_list, and case.

As described in the evaluation section, you must implement parsing for while_stmt, condition, and do_stmt, while switch_stmt, case_list, and case are extra credit (though note that to receive full extra credit, you must implement all of the type checks in addition to the parsing cases.

Semantic Error Output

Your program will check for the following semantic errors (with type checking being one of those semantic errors) and output the correct output when it encounters that error. Note that there will only be at most one error per test case.

Type name declared more than once

If a type name is declared more than once, either implicitly or explicitly, then the output of your program should be:

ERROR CODE 0 <type_name>

Where <type_name> is replaced with the name that is declared more than once.

Type re-declared as variable

If a type name is redeclared as a variable, either implicitly or explicitly, then the output of your program should be:

ERROR CODE 1 <type_name>

Where <type_name> is replaced with the name of the type that is re-declared as a variable.

Variable declared more than once

If a variable name is declared more than once, either implicitly or explicitly, then the output of your program should be:

ERROR CODE 2 <variable_name>

Where <variable_name> is replaced with the name of the variable that is declared more than once.

Type Mismatch

If there is a type mismatch in the program, then the output of your program should be:

ERROR CODE 3 <line_number>

Where <line_number> is replaced with the line number that the type mismatch occurs on. Note that you can assume that anywhere a type error can occur will be on a single line.

Variable re-declared as type name

If a variable is re-declared as a type name, either implicitly or explicitly, then the output of your program should be:

ERROR CODE 4 <variable_name>

Where <variable_name> is replaced with the name of the variable that is re-declared as a type.

No semantic errors

If there are no semantic errors in the program, then your output should be the following:

All systems go!

Examples

Given the following:

TYPE  a,b,c,b : INT;VAR  x : a;{  x = 10;}

The output will be the following:

ERROR CODE 0 b

Given the following:

TYPE  a : INT;VAR  x : INT;  b, a : STRING;{  x = 10;}