Start of topic | Skip to actions

Write a parser and interpreter for the WAE language 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 binary arithmetic operators and multi-armed `with`

.

In place of having separate rules for + and -, define a single syntactic rule for all binary arithmetic operators. Parse these into a `binop`

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 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).

`with`

Each identifier bound by the with expression is bound only in its body. There will be zero or more identifiers bound by each with expression. If there are multiple bindings of the same identifier in a single with 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 DrScheme software installed on the lab machines is not of a correct version. Instead, you can set up a local copy of the software in your home dir. To set up the software, please follow these instructions.

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!

Your parser and interpreter must detect errors (syntax-related as well as semantic-related) and explicitly signal them by calling (error ...). We will consider an error raised internally by Scheme to be a bug in your code.

For example, Scheme signals a "divide by zero" error if you attempt to evaluate (/ 1 0). Since we use Scheme's division function to implement division in CFWAE, you may be tempted to leave it to Scheme to signal division by zero errors for you. However, you must signal the error yourself by explicitly testing for division by zero before calling Scheme's division procedure. If you are not sure if an error raised by your program constitutes a bug, search the Help Desk for test/exn. test/exn tests for errors, but only succeeds on errors that you explicitly signal.

The syntax of the WAE language with these additional features can be captured using EBNF notation:

<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 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 `calc`

, which consumes an abstract syntax expression (as returned by the parse function) and returns a Scheme 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!

This is an individual assignment, each student is expected to hand in their own solution.. Follow the Handin Guidelines.

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.

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) (...))

-- SanderVermolen - 03 Nov 2009

I | Attachment | Action | Size | Date | Who | Comment |
---|---|---|---|---|---|---|

InstallatieDrScheme.pdf | manage | 119.7 K | 06 Nov 2009 - 09:49 | SanderVermolen |

Revisions: | r1.4 | > | r1.3 | > | r1.2 | Page history | Backlinks

Copyright © 2003-2018, Software Engineering Research Group, Delft University of Technology, The Netherlands