C311 Assignment 4 -- Interpreters

Due Monday, February 5, at 9 AM

Submit via email

In this assignment, you are asked to build a series of interpreters. Each part of the assignment should be done cumulatively, building on the interpreter in the previous part. The input to the interpreter is an expression in Scheme syntax (see the examples) so you need to write a parser for expressions in Scheme syntax. In the end you should have just one interpreter, which is equipped to handle the test inputs from all parts of this assignment.
  1. Parser
    Write a parser for Scheme syntax using the BNF grammar given below. This output of this parser is used as the input to eval-exp. 
    <exp>       ::= <integer-literal>
              | <varref>
              | ( <operator> <operands> )
<operator>  ::= <exp>
<operands>  ::= <exp>*
<varref>    ::= <var>

  2. EOPL Exercise 5.1.2 (modified)
    Impelement the interpreter, eval-exp, and test it using run . 
    > (run '(+ 1 2))
3
> (run '(add1 (add1 3)))
5
> (run '(* (- (+ 1 2) 1) 2))
4
  3. EOPL Exercise 5.1.3 

    > (run '(minus 3))
-3
> (run '(minus (minus 4)))
4
  4. EOPL Exercise 5.2.1

    Use the list syntax and remember to modify your parser. A true value is one that is not numerically equal to 0. 

    > (run '(if (+ 1 2) 1 2))
1
> (run '(if (- 1 1) (- 1 0) (* 20 5)))
100
> (run '(if + 1 2))
1
  5. EOPL Exercise 5.2.2 

    > (run '(equal 3 3))
1
> (run '(zero (sub1 5)))
0
> (run '(if (greater 2 3) 5 6))
6

    Submission

    Write your answers to the exercises in a file (with comments, following the proper indentation rules), and send that file to

    c311@lakshmi.cs.indiana.edu
    with the subject line
    4
    Assuming you've saved your homework in the file ``asgn.ss'' in the current directory, one way to submit is with the command:
    Mail -s "4" c311@lakshmi.cs.indiana.edu < asgn.ss
    If you use the define-record stuff, include the expression 
    (load "define-record")
    in your submission.

    Back to the c311 page

    ehilsdal@cs.indiana.edu