Description
Question 1[50 points] In this question you will implement a parser for the language of algebraic expressions described in class. We use the following type de nition to capture expression trees:
type exptree = Var of char | Expr of char * exptree * exptree
The input will be just plain strings and the output has to be an exptree. The input strings consist of simple algebraic expressions with + and * and one-character symbols that are just lower-case letters. It is also possible to use parentheses in the input expressions. Blanks are not allowed in the input1. The parser itself will consist of three mutually recursive functions as explained in class. There is a template installed in the LearnO’Caml system with more details. I will put a le with examples on the course web page. I am interested in making sure that the parser works correctly on valid input strings, I won’t worry about dealing with bad strings and implementing error handling. I have not written the parser to detect all the possible problems. In the le called examples.ml you will see that not all bad strings are reported as bad strings, one simply gets the wrong parse tree. The most complicated part is the recursive procedure called primary which I have written for you. This is de ned together with expr and term as three mutually recursive functions.
Question 2[50 points] In this question you will implement a toy code generator for the very simple stack machine as explained in class. Use the output from the parser as input to the code generator. The code generator should just print the \machine instructions”. Use statements like
Printf.printf “LOAD %c\n” c
Printf.printf “ADD %c\n” c
Printf.printf “MUL %c\n” c
Printf.printf “STORE %i\n” tempstore
Printf.printf “ADD %i\n” tempstore
within your program to get this e ect.
1If you want to do something fancier please do so on your own but do not submit it!
1
