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 lan

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 代写COMP4233 25S binary operatorbit 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
   -> EOF
   -> int
   | +
   | *
   | ( )
   | id
   | let id = in
   | fun id ->
   |
   | if then else
   | bool
   | <=
   | ^
   | []
   | ::
   Note that -> 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 = v in –> {v / }
   (let = v in ){v / } –>
   if = then (let = )
   else (let = {v / }
   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%