Rudimentary Interpreter FAQ
Write a parser and interpreter for the WAE language [1] we've discussed in class. The lecture notes can be of great assistance in this part of the assignment; they provide the beginnings of a parser, an abstract syntax datatype and an interpreter. Then extend the language with the features described below:
- Binary arithmetic operators
In place of having separate rules for
+
and-
, define a single syntactic rule for all binary arithmetic operators. Parse these into abinop
datatype variant. Define a table that maps operator names (symbols) to actual functions (Scheme procedures) that perform the corresponding operation. Having a single rule like this, accompanied by a table, makes your language easier to extend: once you have modified your parser and interpreter once to support binary operators, you won't need to touch either one to add any number of new ones. To demonstrate this, define multiplication and division (using*
and/
to represent them in the language's concrete syntax). - Multi-armed
with
Implement a multi-armed
with
. Each identifier bound by thewith
expression is bound only in its body. There will be zero or more identifiers bound by eachwith
expression. If there are multiple bindings of the same identifier in a singlewith
expression, your interpreter should halt with an error message. An example:{with {{x 2} {y 3}} {with {{z {+ x y}}} {+ x z}}
which will evaluate to7
.
The syntax of the WAE language with these additional features can be captured using EBNF [2] notation:
<WAE> ::= <num> | {+ <WAE> <WAE>} | {- <WAE> <WAE>} | {* <WAE> <WAE>} | {/ <WAE> <WAE>} | {with {{<id> <WAE>}*} <WAE>} | <id>
You should turn in a single Scheme program containing all of the
code needed to run your parser and interpreter. Implement the function
parse
, which consumes an expression in the language's
concrete syntax and returns the abstract syntax representation of that
expression. Also implement the function interp
, which
consumes an abstract syntax expression (as returned by the
parse
function) and returns a number.
Please include a contract for every function that you write and include test cases that amply exercise all of the code you've written.
[1] Remember, the WAE language has numbers, two arithmetic operators
(+
, -
), identifiers and with
expressions. Of course, to handle identifiers and with
expressions you'll have to implement substitution. (You do not have to
implement caching substitution as discussed in lecture 2003-09-12 but
you are free to do so.) Finally, both the concrete syntax and abstract
syntax are specified by the WAE language's BNF (which can be found in
the lecture notes).
[2] The 2003-09-05 lecture notes introduced you to BNF. An extension of this notation, called EBNF (Extended Backus-Naur Form), provides three additional operators:
-
?
means that one or more symbols to its left can appear zero or one times. -
*
means that one or more symbols to its left can be repeated zero or more times. -
+
means that one or more symbols to its left can appear one or more times.
FAQ
-
Does the phrase "multiple bindings of the same identifier in a single
with
expression" mean multiple bindings of the same identifier within a singlewith
expression's list of bindings or multiple bindings of the same identifier within the entirewith
expression?We mean multiple bindings of the same identifier in a single
with
expression's list of bindings. In other words, the code{with {{x 3}} {with {{x 4}} x}}
is fine whereas the code{with {{x 3} {x 4}} x}
should cause the interpreter to halt.