1. Homepage
  2. Programming
  3. CSE340 Project 3: Type Checking

CSE340 Project 3: Type Checking

Engage in a Conversation
ASUCSE340Principles of Programming LanguagesC++美国Hindley-Milner type checking

CSE340 Project 3: Type Checking CourseNana.COM


CourseNana.COM


CourseNana.COM

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

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. CourseNana.COM

1. Lexical Specification CourseNana.COM

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

INT = "int"
REAL = "real" BOOL = "bool" TRUE = "true" FALSE = "false" IF = "if"
WHILE = "while" SWITCH = "switch" CASE = "case" NOT = "!" CourseNana.COM

PLUS = "+"
MINUS = "-"
MULT = "*"
DIV = "/"
GREATER = ">"
LESS = "<"
GTEQ = ">="
LTEQ = "<="
NOTEQUAL = "<>"
LPAREN = "("
RPAREN = ")"
NUM = (pdigit digit*) + 0 REALNUM = NUM "." digit digit* PUBLIC = "public" CourseNana.COM

PRIVATE = "private" EQUAL = "="
COLON = ":"
COMMA = "," SEMICOLON = ";" LBRACE = "{" CourseNana.COM

RBRACE = "}"
ID = letter (letter + digit)* CourseNana.COM


CourseNana.COM

2. Grammar CourseNana.COM

Here is the grammar for our input language: CourseNana.COM

1   program-> global_vars body CourseNana.COM

2   global_vars-> ε CourseNana.COM

3   global_vars-> var_decl_list CourseNana.COM

4   var_decl_list-> var_decl CourseNana.COM

5   var_decl_list-> var_decl var_decl_list CourseNana.COM

6   var_decl-> var_list COLON type_name SEMICOLON CourseNana.COM

7   var_list-> ID CourseNana.COM

8   var_list-> ID COMMA var_list CourseNana.COM

9   type_name-> INT CourseNana.COM

10 type_name-> REAL CourseNana.COM

11 type_name-> BOOL CourseNana.COM

12 body-> LBRACE stmt_list RBRACE CourseNana.COM

13 stmt_list-> stmt CourseNana.COM

14 stmt_list-> stmt stmt_list CourseNana.COM

15 stmt-> assignment_stmt CourseNana.COM

16   stmt -> if_stmt CourseNana.COM

17   stmt -> while_stmt CourseNana.COM

18   stmt -> switch_stmt CourseNana.COM

19   assignment_stmt -> ID EQUAL expression SEMICOLON CourseNana.COM

20 expression -> primary CourseNana.COM

21 expression -> binary_operator expression expression CourseNana.COM

22   expression -> unary_operator expression CourseNana.COM

23   unary_operator -> NOT CourseNana.COM

24   binary_operator -> PLUS | MINUS | MULT | DIV CourseNana.COM

25   binary_operator -> GREATER | LESS | GTEQ | LTEQ | EQUAL | NOTEQUAL CourseNana.COM

26 primary-> ID CourseNana.COM

27 primary-> NUM CourseNana.COM

28 primary-> REALNUM CourseNana.COM

29 primary-> TRUE CourseNana.COM

30 primary-> FALSE CourseNana.COM

31 if_stmt-> IF LPAREN expression RPAREN body CourseNana.COM

32 while_stmt-> WHILE LPAREN expression RPAREN body CourseNana.COM

33 switch_stmt-> SWITCH LPAREN expression RPAREN LBRACE case_list RBRACE CourseNana.COM

34 case_list-> case CourseNana.COM

35 case_list-> case case_list CourseNana.COM

36 case-> CASE NUM COLON body CourseNana.COM

3. Language Semantics 3.1. Types CourseNana.COM

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

3.2. Variables CourseNana.COM

Programmers can declare variables either explicitly or implicitly. Explicit variables are declared in an var_list of a var_decl . CourseNana.COM

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

Example CourseNana.COM

Consider the following program written in our language: CourseNana.COM

1   x: int; CourseNana.COM

2   y: bool; CourseNana.COM

3   { CourseNana.COM

4   y = x; CourseNana.COM

5   z = 10; CourseNana.COM

6   w = * z 5; CourseNana.COM

7   } CourseNana.COM

This program has four variables declared: x , y , z , and w , with x and y explicitly declared and z and w implicitly declared. CourseNana.COM

3.3. Type System CourseNana.COM

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). CourseNana.COM

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

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

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) CourseNana.COM

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

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 CourseNana.COM

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 CourseNana.COM

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

The type of expression 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 CourseNana.COM

4. Output CourseNana.COM

There are two scenarios: CourseNana.COM

There is a type error in the input program There are no type errors in the input program CourseNana.COM

4.1. Type Error CourseNana.COM

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: CourseNana.COM

  TYPE MISMATCH <line_number> <constraint> CourseNana.COM

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. CourseNana.COM

4.2. No Type Error CourseNana.COM

If there are no type errors in the input program, then you should output type information for all variables in the input program in the order they appear in the program. There are two cases: CourseNana.COM

If the type of the variable is determined to be one of the builtin types, then output one line in the following format: CourseNana.COM

1           <variable>: <type> # CourseNana.COM

where <variable> should be replaced by the variable name and <type> should be replaced by the type of the variable. CourseNana.COM

If the type of the variable could not be determined to be one of the builtin types, then you need to list all variables that have the same type as the target variable and mark all of them as printed (so as to not print a separate entry for those later). You should output one line in the following format: CourseNana.COM

1           <variable_list>: ? # CourseNana.COM

where <variable_list> is a comma-separated list of variables that have the same type in the order they appear in the program. CourseNana.COM

5. Examples CourseNana.COM

Given the following: CourseNana.COM

1   a, b: int; CourseNana.COM

2      { CourseNana.COM

3   a = < b 2; CourseNana.COM

4   } CourseNana.COM

The output will be the following: CourseNana.COM

  TYPE MISMATCH 3 C1 CourseNana.COM

This is because the type of < b 2is bool, buta is of type int which is a violation of C1. CourseNana.COM

Given the following: CourseNana.COM

1   a, b: int; CourseNana.COM

2      { CourseNana.COM

3   a = + b 2.5; CourseNana.COM

4      } CourseNana.COM

The output will be the following: CourseNana.COM

  TYPE MISMATCH 3 C2 CourseNana.COM

This is because the type of b is int and the type of 2.5 is real which means in the expression + b 2.5 , C2 is violated CourseNana.COM

Given the following: CourseNana.COM

1   a, b: int; CourseNana.COM

2      { CourseNana.COM

3   a = b; CourseNana.COM

4      } CourseNana.COM

The output will be the following: CourseNana.COM

1     a: int # CourseNana.COM

2     b: int # CourseNana.COM

Given the following: CourseNana.COM

1      { CourseNana.COM

2      a = b; CourseNana.COM

3      } CourseNana.COM

The output will be the following: CourseNana.COM

a, b: ? # CourseNana.COM

 6. Requirements CourseNana.COM

You should use C/C++, no other programming languages are allowed. CourseNana.COM

You should submit your code on the course submission website, no other submission forms will be accepted. CourseNana.COM

Also submit the output file obtained from the server CourseNana.COM

7. Evaluation CourseNana.COM

The submissions are evaluated based on the automated test cases on the submission website. Your grade will be proportional to the number of test cases passing. If your code does not compile on the submission website, you will not receive any points. CourseNana.COM

Here is the breakdown of points for tests in different categories:
Test cases with assignment statements (no
if , while or switch ): 50 points Test cases with assignment, if and while statements (no switch ): 30 points Test cases with all types of statements: 20 points CourseNana.COM

Get in Touch with Our Experts

WeChat (微信) WeChat (微信)
Whatsapp WhatsApp
ASU代写,CSE340代写,Principles of Programming Languages代写,C++代写,美国代写,Hindley-Milner type checking代写,ASU代编,CSE340代编,Principles of Programming Languages代编,C++代编,美国代编,Hindley-Milner type checking代编,ASU代考,CSE340代考,Principles of Programming Languages代考,C++代考,美国代考,Hindley-Milner type checking代考,ASUhelp,CSE340help,Principles of Programming Languageshelp,C++help,美国help,Hindley-Milner type checkinghelp,ASU作业代写,CSE340作业代写,Principles of Programming Languages作业代写,C++作业代写,美国作业代写,Hindley-Milner type checking作业代写,ASU编程代写,CSE340编程代写,Principles of Programming Languages编程代写,C++编程代写,美国编程代写,Hindley-Milner type checking编程代写,ASUprogramming help,CSE340programming help,Principles of Programming Languagesprogramming help,C++programming help,美国programming help,Hindley-Milner type checkingprogramming help,ASUassignment help,CSE340assignment help,Principles of Programming Languagesassignment help,C++assignment help,美国assignment help,Hindley-Milner type checkingassignment help,ASUsolution,CSE340solution,Principles of Programming Languagessolution,C++solution,美国solution,Hindley-Milner type checkingsolution,