CS 441 Assignment 2: Syntax

This assignment is due thursday Feb 22 at 10:30am.

Read Section 3.4 of EOPL for background.

Part 1: Parsing

You are to write a parser for a subset of Scheme. The concrete syntax of this subset and its corresponding abstract syntax is as follows:

 e ::= n                           (make-Const n)
     | #t                          (make-Const #t)
     | #f                          (make-Const #f)
     | ()                          (make-Const ())
     | (quote x)                   (make-Const x)
     | x                           (make-Var x)
     | (if e e e)                  (make-If test then else)
     | (lambda (x ...) e)          (make-Lam formals body)
     | (let ((x e) ...) e)         (make-Let bindings body)
     | (let* ((x e) ...) e)        (make-Let* bindings body)
     | (letrec ((x e) ...) e)      (make-Letrec bindings body)
     | (e e ...)                   (make-Ap fun args)

where n is a number, x is a variable, and ... means zero or more of the previous parenthesis-balanced item. In the abstract syntax, formals is a list of symbols; and bindings is a list of two-lists, where the car of each two list is a symbol and the cadr is an abstract expression. Use define-record to build procedures for constructing abstract syntax.

Part 2: Unparsing

In addition, you are to write an unparser that maps an abstract syntax record back into concrete syntax. The following identities should hold:

(unparse (parse e)) = e
(parse (unparse A)) = A

for A some abstract expression. (The appropriate notion of equality here is equal?.) Show with some examples in your test transcript that the functions satisfy these equations! You may find variant-case convenient for your unparser.

Part 3: Free and Bound

Define the functions free-vars and bound-vars that take an abstract expression and yield its sets of free and bound variables respectively. You may use this implementation of sets if you wish. Again, include some examples in your transcript.