You must do this assignment solo. We know that some of you are not yet comfortable with Racket; for that reason, we will weight this assignment very, very low in the overall score. Doing poorly on it will not at all damage your course grade. But, you should exploit this opportunity to become familiar with the style of programming you will do in the rest of the semester.
Rudimentary Interpreter
Write a parser and interpreter for the WAE language ([1]) we discussed in class. The textbook 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.
Once you’ve written and tested the parser and interpreter for WAE, extend the language with these features:
- 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 (Racket 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
Each identifier bound by the
with
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’s bindings list, your interpreter should halt with an error message. An example:{with {{x 2} {y 3}} {with {{z {+ x y}}} {+ x z}}}
will evaluate to
7
, while{with {{x 2} {x 3}} {+ x 2}}
will halt with an error message.
The syntax of the WAE language with these additional features can be captured using EBNF notation ([2]):
<WAE> ::= <num> | {+ <WAE> <WAE>} | {- <WAE> <WAE>} | {* <WAE> <WAE>} | {/ <WAE> <WAE>} | {with {{<id> <WAE>}*} <WAE>} | <id> where an <id> is not +, -, *, /, or with.
You should turn in a single Racket 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 calc
,
which consumes an abstract syntax expression (as returned by the
parse
function) and returns a Racket number.
You must include a contract for every function that you write and include test cases that amply exercise all of the code you’ve written. We will not give full credit to untested functionality, even if it is correct! Refer to the syllabus for style requirements.
[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 deferred substitution,
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
textbook).
[2] The textbook 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.
Racket's (match ...)
Syntax
If you're pretty comfortable
with Racket, or are feeling particularly adventurous, check out the
(match ...)
syntax in the
Racket Docs.
It could make your parser prettier and easier to write.
Note that this a power user feature and is not required. If
you find yourself getting frustrated using the cond/case
syntax to
parse the input, take a look. If you're still shaky on Racket in general, skip
it for now.
Support Code
Your code must adhere to the following templates, without any changes:
(define-type Binding [binding (name symbol?) (named-expr WAE?)]) (define-type WAE [num (n number?)] [binop (op procedure?) (lhs WAE?) (rhs WAE?)] [with (lob (listof Binding?)) (body WAE?)] [id (name symbol?)]) ;; parse : s-exp -> WAE ;; Consumes an s-expression and generates the corresponding WAE (define (parse sexp) (...)) ;; calc : WAE -> number ;; Consumes a WAE representation of an expression and computes ;; the corresponding numerical result (define (calc expr) (...))
Handin
From the directory containing the files for this assignment, execute
/course/cs173/bin/cs173handin rinterp