COMP4233代做、代写Python/Java程序

日期：2025-05-30 10:52

COMP4233 25S

Programming Assignment

Introduction

In Lecture 11, we implement an integer calculator, which consists of

- int : the only data type for integers

- + : binary operator for integer addition

- * : binary operator for integer multiplication

- ( ) : parentheses for force parsing

- parser and evaluator of the expressions in this language.

In Lab 11, we extend the language by let expression, identifiers and its evaluator in the

substitution model. This upgrade implements a naming system for the language.

Syntax

In this programming assignment, you need to further extend the language with following

features.

1. if … then … else … : the “if” expression, which can branch computations under

some conditions.

2. fun … -> … : function definitions, which can also be with let to name them.

To make if statement work properly, we also need

3. a new data type bool, the guard in if;

4. constants in bool are either true or false;

5. Boolean binary operator ^, boolean conjunction;

6. bool can be constructed from the relational operator <=, integer “less or equal to”.

We want to add a little bit more complex structure into our language, which are

7. a new data type list with only one constant list [] – the empty list; and

8. lists can be constructed by binary operator ::, which is right associative.

Combining everything above, the entire grammar is

<prog> -> <expr> EOF

<expr> -> int

| <expr> + <expr>

| <expr> * <expr>

| ( <expr> )

| id

| let id = <expr> in <expr>

| fun id -> <expr>

| <expr> <expr>

| if <expr> then <expr> else <expr>

| bool

| <expr> <= <expr>

| <expr> ^ <expr>

| []

| <expr> :: <expr>

Note that <expr> -> <expr> <expr> is the syntax for function application.

For the precedence of operators, we only specify + is lower than *. Others will be guaranteed

by parentheses. For example, ambiguous expressions like fun a -> a 1 will be excluded

from testcases. This expression has to be either fun a -> (a 1) or (fun a -> a) 1.

Typing

To make your life easy, type system is excluded from this project. Thus, expressions with

type errors, like 1 + true are excluded from testcases.

Evaluation

The evaluation for operators simply follows their behaviors in mathematics. Students should

understand them easily. But if a student insists true ^ true --> false, marks will be

remove. Goliath does not want to argue.

The evaluation for let expression is implemented by substitution model and already given in

Lab 11.

let <x> = v in <expr> --> <e>{v / <x>}

(let <x> = v in <expr>){v / <y>} -->

if <x> = <y> then (let <x> = <expr>)

else (let <x> = <expr>{v / <y>}

Students should figure out the substitutions for functions, function applications, and lists by

themselves, which is interesting and not difficult. Furthermore, we also guarantee that

function arguments are of distinct names. Expressions like let x = z in (fun z -> x)

are excluded from testcases. The following substitution is naïve and not correct.

let x = z in (fun z -> x)

--> (fun z -> x) {z / x}

--> fun z -> x {z / x}

--> fun z -> z

-/->

Output

To printout an AST, two functions string_of_val and string_of_bop are defined in

main.ml. You can also apply these functions to see if your implementation works normally.

Example

Here is one example,

let x=(fun a -> (if (a <= 1) then true else false)) in ((x 1) :: [])

is parsed into

and evaluated as

let x=(fun a -> (if (a <= 1) then true else false)) in ((x 1) :: [])

--> ((x 1) :: []){fun a -> .. /x}

--> ((x 1){fun a -> .. /x} :: []{fun a -> .. /x}

--> ((x{fun a -> .. /x} 1{fun a -> .. /x}) :: []{fun a -> .. /x})

--> (((fun a -> ..) 1{fun a -> .. /x}) :: []{fun a -> .. /x})

--> (((fun a -> ..) 1) :: []{fun a -> .. /x})

--> (((fun a ->(if (a<=1) then true else false) 1) :: [])

--> ((if (a <= 1) then true else false){1/a} :: [])

--> ((if (a <= 1){1/a} then true{1/a} else false{1/a}) :: [])

--> ((if (a{1/a} <= 1{1/a}) then true{1/a} else false{1/a}) :: [])

--> ((if (1 <= 1{1/a}) then true{1/a} else false{1/a}) :: [])

--> ((if (1 <= 1) then true{1/a} else false{1/a}) :: [])

--> ((if true then true{1/a} else false{1/a}) :: [])

--> (true{1/a} :: [])

--> (true :: [])

-/->

Submission

ast.ml and lexer.mll are given in the package. You only need to implement

parser.mly and main.ml. You don’t need to change anything else, including file names.

Grade distribution

- Submission 5%

- Compilation 5%

- parsing if statements 15%

- evaluating if statements 10%

- parsing functions and function applications 15%

- evaluating functions and function applications 10%

- parsing & evaluating relational operator <= 10%

- parsing & evaluating Boolean conjunction ^ 10%

- parsing lists 10%

- evaluating lists 10%

Select the features that you have implemented in check_list.md by [x].