Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP3173 23F

Project Implementation

Phase 3 Semantic Analysis

This phase is optional. The groups who implement this phase will receive at most 20% bonus of this project. But, the total mark will be capped at 100%.

In phase 1 & 2, you have already implemented a lexer and a parser to check lexical errors and syntax errors. In the next phase, you will do the semantic analysis on the source program. Semantic analysis can be type checking and expression evaluation.

Type system

To check types of the source program you need

- Define a type system for the grammar.

- Implement the type system as a program.

Here are some tips for the type system.

- This language has three types.

- “nat”, natural number

o declared by variable declaration “nat”, or

o obtained by arithmetic expressions, like “1 + 2”.

- “bool”, Booleans

o declared by variable declaration “bool”,

o obtained by Boolean expressions, like “T & T”, or

o obtained by relational comparison, like “2 < 1”.

- “fun”, functions

o declared by function declaration “fun”.

o Note that not all functions are of the same type. For example, some possible functions can be “fun: nat→nat” and “fun: nat×bool→nat”.

- A part of the type system is already discussed in Assignment 3. You can use the solutions directly.

- Typing functions can be very tricky for recursive functions. Function declarations are produced by the grammar rule (Rule 3)

F -> fun id A -> C

A naïve type rule can be

addtype(id.entry, A.type -> C.type)

This type rule works fine for non-recursive functions but fails on recursions. In recursion functions, “C” is an expression about “id”. So, “id.type” depends on “C.type”, which depends on “id.type” itself! For the students who are interested, check Hindley-Milner algorithm for a solution.

Evaluation

Recall that a piece of source code in our language consists of zero, or one, or multiple function declarations, and followed by a single arithmetic expression. Thus, we can implement an interpreter for this language. The interpreter simply evaluates the arithmetic expression in the source code. To implement an interpreter, you need to define a set of syntax-directed definitions (similar to the type system), which calculate the values of the arithmetic expression.

Evaluations can sometimes be not easy when the expression contains function calls. To systematically evaluate function calls, you can

search β-reduction for a solution.

Implementation

When you implement the type checker or the interpreter, you need to slightly modify the code from Phase 1 & 2 to make it fit. For example, the type checker needs an extra piece of storage for every node in the parse tree to hold the type for the expression. Thus, there is no restrictions on the modifications. You have your own choice.

Mark Distribution

- 5% for type checking without recursion functions

- 5% for type checking recursion functions

- 5% for evaluation without function calls

- 5% for evaluation with function calls

Submission requirements

Each team need to clearly indicate the contribution of each team member in a txt file. To submit your work, you need to pack all files (source code and contribution txt) in a package. Rename the package as COMP3173_23F_SectionXX_TeamYY, where XX is your section number and YY is your team number. Only team leaders need to upload the package to iSpace.