CS 3304
Programming Assignment 2

Given: July 28, 1997 Due: August 7, 1997

This assignment is worth 100 points. The assignment is due on Thursday, August 7, 1997, at 5:00 PM. NO LATE PROGRAMS WILL BE ACCEPTED.

The Assignment

You are to implement in Scheme a parser and evaluator for a simple expression language. The language is defined by this grammar:

The terminals of this grammar are

An expression must be a Scheme string. The parser and evaluator execute in three stages:

1. Parse an expression and return a parse tree;
2. Convert a parse tree to an expression tree; and
3. Take an expression tree and a list of bindings for variables; return the result.

The three stages are described further below.

Parse Trees

A parse tree can be represented as an S-expression:

• The S-expression for a terminal symbol is just the string consisting of that symbol;
• The S-expression for an interior node is a list whose car is the nonterminal and whose cdr is a list of the children of that node.

For example, the S-expression for the expression x is the string "x". The S-expression for (x+y) is

(expr (term (factor "(" (expr (expr (term (factor (id "x")))) "+"
(term (factor (id "y")))) ")")))

You are to implement a Scheme procedure

(parse e)

that takes an expression e as parameter and returns the parse tree for e if e is a syntactically correct expression. It returns () otherwise.

The easiest way to parse this grammar is to use recursive descent parsing, a kind of top-down parsing. See Section 3.4. The traditional problem with top-down parsing for this grammar is that two of the rules are left-recursive, making finite lookahead impossible if the input is scanned left to right. However, if the input is scanned right to left, recursive descent parsing works just fine. Here is a basic Scheme procedure for getting the next token in a right-to-left scan:

;;
;;      next-token procedure --- returns the next token in a string
;;              and the remainder of a string
;;
;;      (next-token e) returns the next token in string e
;;              (which must be one of: "x", "y", "z", "(", ")", "+", "*")
;;              as the car of a list and the remainder of the string
;;              as the second element of the list
;;              returns () otherwise
;;
(define (next-token e)
   (cond
     ((not (string? e)) ())
     ((= (string-length e) 0) ())
     (else (begin
     (define e-length (string-length e))
     (define token (substring e (- e-length 1) e-length))
     (define rest (substring e 0 (- e-length 1)))
     (cond
        ((not (or
          (string=? token "x")
          (string=? token "y")
          (string=? token "z")
          (string=? token "(")
          (string=? token ")")
          (string=? token "+")
          (string=? token "*")
        )) ())
        (else (cons token (cons rest ())))
     )
     ))
  )
)

Following the paradigm of recursive descent parsing, you will also need Scheme procedures for each of the nonterminals: , , , and . The job of the expr procedure, for example, is to find a sum of terms in the remaining input. More specifically, the invocation

(expr r)

returns a 2-element list

(t s)

where t is a parse tree for the longest suffix of r that matches an and s is the portion of r that remains. For example,

(expr "z*(x+y")

returns

((expr (expr (term (factor (id "x")))) "+" (term (factor (id "y")))) "z*(")

Additional material on recursive descent parsing will be discussed in class.

Expression Trees

An expression tree eliminates the nonterminals from the parse tree and leaves only the evaluation structure of an expression. For example, the expression tree for x is "x", while the expression tree for (x+y) is (+ "x" "y").

You are to implement a Scheme procedure

(parse->expression t)

that takes a parse tree t as parameter and returns the expression tree for t. You may assume that t is a correctly structured parse tree. If you want to check the correctness of t, then your procedure should return () if it is not a proper parse tree.

As an example,

(parse->expression (parse "((x+y)*(y+z*x))"))

should return

(* (+ "x" "y") (+ "y" (* "z" "x")))

Evaluation

You are to implement a Scheme procedure

(evaluate-expression t b)

that takes an expression tree t and a list b of three numbers as parameters. The three numbers are the values to bind to the variables x, y, and z. The procedure returns the result of evaluating the expression tree under the given bindings. You may assume that the parameters are in the expected form. If you want to check the parameters, then your procedure should return () if the parameters are not correctly structured.

As an example, the result of

(evaluate-expression (parse->expression (parse "((x+y)*(y+z*x))"))
'(2 5 7))

should be

133

Guidelines and Limitations

As with the first programming assignment, your procedures must be implemented in a functional programming style. Hence, you should use recursion rather than iteration; the do construction is not allowed. You should also avoid assignment operations; hence set!, setcar!, setcdr!, and string-set! are not allowed.

You may find define useful to name the results returned by a recursive call. You may also find begin useful for sequencing.

Your implementation is to be organized in a file named expression.lisp. The header at the beginning of the file should identify the assignment and should give your name. Every Scheme procedure should be preceded by comments explaining its purpose, calling sequence, and implementation.

You should develop a set of test strings for parse that test syntactically correct and syntactically incorrect strings. Also, use the syntactically correct expressions to give you parse trees and expression trees to test parse->expression and evaluate-expression. Put your tests in a file named expression.test. Capture all the results of your tests running under the Scheme interpreter in a file expression.trace.

Submission

Email the three files expression.lisp, expression.test, and expression.trace to

ohiuddin@csgrad.cs.vt.edu

with a carbon copy to

cs3304sm@ei.cs.vt.edu

Ideally, the files will be attached to a single email message. Alternately, they may be mailed in three separate email messages. In the subject line, include the phrase

CS 3304 Second Programming Assignment

Evaluation

Programs will be evaluated on programming style (20% for documentation and prettyprinting) and on successful execution (80%). Execution will be tested using a suite of test cases that the GTA will develop. Some of these test cases will be more elaborate than the examples given in this assignment. None of this test suite will be posted on the course web pages.

END OF ASSIGNMENT\HSPACE*

About this document ...

This document was generated using the LaTeX2HTML translator Version 96.1 (Feb 5, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 -t CS 3304 Programming Assignment 2 program2.

The translation was initiated by cs3304sm class account on Mon Jul 28 16:25:49 EDT 1997