|
|
Assignment 3: Interpretation
Your task in this assignment is to implement a complete interpreter
for an extended version of the calculator language, with
The main entry point of the provided code is (define parse (lambda (grammar program) ...This normally returns a syntax tree. You’ll want to print some trees out to see what they look like. If the program has syntax errors (according to the grammar), parse will print an error message and return
#f.
If the grammar itself is malformed, you may get unhelpful error messages
from the parser generator—it isn’t very robust.
The grammar takes the form of a list of productions, each of which is a 2-element list containing the LHS symbol and a list of the symbols on the RHS. The extended calculator language looks like this:
(define x-calc-gram
'(("P" ("SL" "$$"))
("SL" ("S" "SL") ())
("S" ("id" ":=" "E") ("read" "id") ("write" "E")
("if" "C" "SL" "end") ("while" "C" "SL" "end"))
("C" ("E" "rn" "E"))
("rn" ("==") ("!=") ("<") (">") ("<=") (">="))
("E" ("T" "TT"))
("T" ("F" "FT"))
("TT" ("ao" "T" "TT") ())
("FT" ("mo" "F" "FT") ())
("ao" ("+") ("-"))
("mo" ("*") ("/"))
("F" ("id") ("num") ("(" "E" ")"))
))
A program takes the form of a simple list:
(define sum-and-ave '(read a
read b
sum := a + b
write sum
write sum / 2
$$))
Note the difference: symbols in the grammar are quoted character
strings; symbols in the input are Scheme atoms.
|
Your work will proceed in two steps:
(define ASTize-P (lambda (P) ...
where P is a parse tree generated by function
parse.
The exact format of the AST is up to you.
You can get ideas from the text (Section 4.6), but what’s
there is incomplete; you’ll have to flesh it out.
(define interpret-AST (lambda (ast input) ...
where ast is a syntax tree generated by function
ASTize-P and input is a list of values to
be read by the interpreted program. The return value of
interpret-AST should be a list of the values
written by the interpreted program.
(define interpret
(lambda (grammar program input)
(interpret-AST (ASTize-P (parse grammar program)) input)))
To illustrate how if and while turn the
calculator language from a complete toy into a Turing-complete (if still
quite impractical) language, we have provided a program that calculates
the first n primes:
(define primes '(read n
cp := 2
while n > 0
found := 0
cf1 := 2
cf1s := cf1 * cf1
while cf1s <= cp
cf2 := 2
pr := cf1 * cf2
while pr <= cp
if pr == cp
found := 1
end
cf2 := cf2 + 1
pr := cf1 * cf2
end
cf1 := cf1 + 1
cf1s := cf1 * cf1
end
if found == 0
write cp
n := n - 1
end
cp := cp + 1
end
$$))
If you run
(interpret x-calc-gram primes '(10)) ; note that input is a listyou should see the output
(2 3 5 7 11 13 17 19 23 29)
For the (extended) calculator language there are no static semantic errors; everything is checked at run time. You should catch (and produce a reasonable error message for)
The initial source code is a little more than 500 lines of Scheme. You should read most of it carefully to understand how it works (you can skip the details of parse table construction if you like, though I think it’s kind of cool :-).
Your program should not take advantage of any imperative features (no functions or special forms with names ending in!).
You may use display for error messages and debugging; all
other output should result from the interpreter printing the return
values of your top-level functions.
You will want to pass the (remaining) input, the output so far, and the
current symbol table to and from the routines that walk the AST.
You can keep the current values of variables in the symbol table.
Note that the routine that evaluates a while statement will
need to be (tail) recursive.
We will be grading your assignment using the “Dr. Scheme”
interpreter: /u/cs254/bin/drscheme, set at the
“R5RS” language level. You can
download your own GUI
version of Dr. Scheme for Windows, MacOS, or Linux, but please be
sure to set the language level correctly, and check that your code works
correctly on the csug installation.
My (not necessarily great) implementation of ASTize-P is
just over 50 lines of code.
My version of interpret-AST is just over 130 lines.
You may find the following helpful.
As in all assignments this semester, you may work alone or in teams of
two. If you choose to work in pairs, I strongly encourage
you to read each others’ code, to make sure you have a full
understanding of semantic analysis.
Note that interpret-AST is harder to write than
ASTize-P;
a fair division of labor might be to have one team member write
ASTize-P and interpret-expr, and the other team
member write the rest of ASTize-P.
Be sure to follow all the rules on the Grading page. As with all assignments,
use the turn-in script:
~cs254/bin/TURN_IN. Put your write-up in a
README.txt or README.pdf file in the directory in
which you run the script. Be sure to describe any
features
of your code that the TA might not immediately notice.
for loops,
nested scopes,
or functions.
Several of these are likely introduce rules that you will want to
check statically.
Before the beginning of class on Thursday, October 1, send e-mail to
to cs254 containing answers to the following
questions:
(parse x-calc-gram P)?
'(read a
read b
read c
sum := ( ( a * b ) + ( b * c ) + ( c * a ) ) / 3
write sum
$$)
'(read a b
read c
sum := ( ( a * b ) + ( b * c ) + ( c * a ) ) / 3
write sum
$$)
while loop),
and prints the average of those additional numbers.
Verify the syntactic correctness of your program
using the provided parser generator.
| ( | n | ) = n! / (k! × (n−k)!) |
| k |
