'
CSCI 555 (Functional Programming) Assignment 6
Spring 2007
CSci 555: Functional Programming
Spring Semester 2007
Assignment #6
Due Friday, 4 May 2007
The purpose of this assignment is to develop an interpreter for the
simple language described below. Syntactically, the language is
similar to the language Lisp.
Syntax. The following extended BNF grammar describes
the commands that a user can enter into the interpreter. Nonterminal
symbols are shown in uppercase. Terminal symbols are in lowercase.
The symbols |, [ ], ^*, and ::= are part of the extended BNF
metalanguage. The ^* is the superscript asterisk character denoting
zero or more repetitions of the element (i.e., star-closure). The
start symbol is COMMAND.
COMMAND ::= EXPR | ASSIGN | quit
ASSIGN ::= ( set VAR EXPR )
EXPR ::= VAL
| VAR
| ( OPTR EXPR EXPR )
OPTR ::= + | - | * | /
VAL ::= [ - ] UNSIGNED
UNSIGNED ::= DIGIT DIGIT^*
VAR ::= ALPHA ALPHANUM^*
- Each COMMAND is a separate line of text typed in response
to an interpreter prompt. The input to the interpreter during a
session is a sequence of COMMANDs ending with a
quit command.
- In the grammar, EXPR represents an expression to be
evaluated, VAR represents a variable name, and VAL
represents an optionally signed value.
- A DIGIT is one of the numerals 0, 1,
..., 9. An ALPHA is either an uppercase or lowercase
alphabetic character. An ALPHANUM is either an
ALPHA or a DIGIT.
- UNSIGNEDs and VARs extend as far to the right
as possible. That is, "1234abc+" (which is not a legal
command) would consist of the UNSIGNED "1234",
followed by the VAR "abc", followed by the operator
symbol "+".
- Spaces may occur anywhere in the COMMAND line except
within the UNSIGNEDs, VARs, OPTRs, and the
keywords set and quit.
Semantics.
A value is assigned to a syntactic element as follows:
- An UNSIGNED c denotes a nonnegative "integer"
value; it has the value denoted by the string of DIGITs
c interpreted as a decimal constant in the usual format. A
VAL denotes an integer value that may be either positive or
negative. That is, the value of the string of digits "37" is
the integer 37 and the value of the string "-98" represents
the integer -98.
Note: In the Haskell program described below, you will need a
user-defined type to encode these integer values instead of using the
built-in primitive type Int.
- A VAR v denotes a variable named v; it
has the value associated with the variable v in the current
environment. If variable v does not occur in the current
environment, then the value of v is undefined.
An environment is a mapping from variable names to their
values; it can be represented as a list of pairs (two-tuples) in which
the first component is a variable name and the second component is the
variable's current value.
- An EXPR is an arithmetic expression with the form
(op l r); it has the value computed by
applying the operation op to the values of the left and right
operand expressions, l and r, respectively. The
arithmetic operator symbols have their usual meanings.
- An ASSIGN is an assignment command with the form
(set v exp), where v is a
(possibly undefined) variable and exp is an expression. The
command has the same value as the expression exp. The
command also changes (i.e., "sets") the value of the variable
v in the environment to have the value of the expression
exp.
- The quit command terminates evaluation of commands by
the interpreter.
Tasks.
Implement the following Haskell functions:
- eval com env evaluates the command string com
with respect to environment env and returns a pair
(val,env') where:
- val is a value from an appropriate user-defined type.
When the string com is successfully evaluated, val
should encode the integer value of the expression. When an evaluation
error occurs (e.g., the command is not valid syntactically or a
variable within the expression has an undefined value), val
should encode an appropriate error indicator.
- env' is the new environment after execution of command
com. If com is an EXPR, then env'
is the same as env. If com is an ASSIGN of
the form (set v exp), then env' is
the same as env except that the value of variable v
is now mapped to the value of expression exp. A set
of a previously undefined variable causes a new entry to be added to
env'.
Here are a few examples. The constructors Ok and
Err are shown for illustration purposes. You may define your
own type and appropriate messages.
- eval "(+ x (* 3 y))" [("x",5),("y",2)]
evaluates to (Ok 11,[("x",5),("y",2)])
- eval "(set x (+ x (* -3 y)))" [("x",5),("y",2)]
evaluates to (Ok -1,[("x",-1),("y",2)])
- eval "(set x (+ x (* -3 y)))" [("x",5)]
evaluates to (Err "Undefined variable",[("x",5)])
Hint: It should be possible to use a simple recursive descent parser
to recognize the COMMAND syntax.
- interpret e implements an interpreter for the language
described above.
The interpreter should implement the algorithm stated below in
imperative pseudo-code.
Let env be the current environment, initially same as the argument e
Prompt user for a COMMAND
Read COMMAND line com (from stdin)
While com not equal to "quit"
Execute eval com env to get return (val,env')
If an error occurred
Display an appropriate error message
Else
Display the integer value of the expression
Update env to be same as env'
Prompt user for next COMMAND
Read COMMAND line com
Test your functions appropriately and thoroughly. Please format
and document your program source code appropriately.
When this assignment is complete, submit a paper listing of your
program source code and the screen outputs from executing the program.
Be sure that all items submitted are clearly labeled with your name
and the assignment number.
Also submit your program files on Blackboard.
UP to CSCI 555 assignments document?
Copyright © 2007, H. Conrad Cunningham
Last modified: Sat May 3 2007