3.4 Rudimentary Interpreter
You can complete this assignment in any language. I recommend Java.
No matter what language you use, you must turn in all the source code and have a single program that when run, runs any tests for the program. If you are using a language like C, I suggest writing tests like
printf("%s: %s should be %s\n", |
"f(x)", |
f(x), |
expected); |
rather than using a complicated testing system, but whatever you use is fine as long as you justify and explain why the testing is sufficient.
In this assignment, you will implement a basic calculator programming language.
The grammar for the language is:
| WAE | = | number | ||
| | | (+ WAE WAE) | |||
| | | (- WAE WAE) | |||
| | | (* WAE WAE) | |||
| | | (/ WAE WAE) | |||
| | | (with ([id WAE]) WAE) | |||
| | | id |
where number is a natural number and id is a sequence of alphabetic characters, but not with.
Write a function named parse that accepts a string representation of a program and returns a data structure representation of the program.
A test case might look like:
printf("%s: %s should be %s\n", |
"parse(\"x\")", |
parse("x"), |
id("x")); |
You should write test cases for all legal and illegal types of expressions. Here are some legal examples: 5 and (+ 1 2). Here are some illegal examples: (+ 1 2 3) and (with [x 1] x).
Write a function named calc that accepts a data structure representation of a program and returns a number, or errors.
You are free to represent errors however is convenient in the language you chose. I suggest using exceptions.
You must implement with expressions using substitution and not environments, but it is not sufficient to only test your subst function to demonstrate the correctness of with.
You should write test cases for all legal parse tests and more to demonstrate that substitution works correctly. Here are some examples:
printf("%s: %s should be %s\n", |
"calc(parse(\"5\"))", |
calc(parse("5")), |
5); |
printf("%s: %s should be %s\n", |
"calc(parse(\"(+ 4 1)\"))", |
calc(parse("(+ 4 1)")), |
5); |
printf("%s: %s should be %s\n", |
"calc(parse(\"(with ([x 5]) x)\"))", |
calc(parse("(with ([x 5]) x)")), |
5); |