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:

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:


  1. Does the phrase "multiple bindings of the same identifier in a single with expression" mean multiple bindings of the same identifier within a single with expression's list of bindings or multiple bindings of the same identifier within the entire with 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.