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 lexerand 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: natnat” and “fun: natboolnat”.
- 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 systematicallyevaluate function calls, you can search -reduction for asolution.
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 COMP31**_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.
請加QQ：99515681 或郵箱：99515681@qq.com WX：codehelp
