|
|
Assignment 3: Interpretation
Your task in this assignment is to implement a complete interpreter
for an extended version of the calculator language, with
The provided code has two main entry points: parseTable :: Grammar -> ... parseTable g = ... parse :: ParseTable -> ... parse table program = ...The first of these routines returns a parse table, in the format expected as the first argument of the second routine. The second normally returns a parse tree. (You’ll want to print some parse trees out to see what they look like.) If the program has syntax errors (according to the grammar), parse will result in a Left value with
an error string.
(Left is half of the standard Either
type. Throughout the provided code, we use Either
to represent things that might be either an error
message—Left—or a useful structure of some
sort—Right].)
If the input grammar you provide is malformed, you may get unhelpful
run-time errors
from the parser generator—it isn’t very robust.
The grammar takes the form of a list of production sets, each of which is a pair containing the LHS symbol and k right-hand sides, each of which is itself a list of symbols. The extended calculator language looks like this:
extendedCalcGrammar =
[ ("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 of strings:
sumAndAve = [ "read", "a"
, "read", "b"
, "sum", ":=", "a", "+", "b"
, "write", "sum"
, "write", "sum"
, "/", "2"
, "$$"
]
You’ll probably find it easier to
extract this list from a single string using the words
function:
sumAndAve = words "read a read b sum := a + b write sum write sum / 2 $$" |
Your work will proceed in two steps:
toAstP :: ParseTree -> AST
toAstP p = ...
where p is a parse tree generated by function
parse.
We have provided a complete description of the AST type, though
you are free to modify this if you prefer a different
format.
interpretAst :: AST -> [String] -> Either String [String]
interpretAst ast input = ...
where ast is a syntax tree generated by function
toAstP and input is a list of values to
be read by the interpreted program. The return value of
interpretAst should be a either a Right value with a list of the values written by the interpreted program
or a Left value with an error string.
interpret :: ParseTable -> [String] -> [String] -> Either String [String]
interpret table program input = do
t <- parse table program
let ast = toAstP t
interpretAst ast 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 (Haskell's multi-line string literals are
unfortunately a little noisy):
primes = words "read n \n\
\cp := 2 \n\
\while n > 0 \n\
\ found := 0 \n\
\ cf1 := 2 \n\
\ cf1s := cf1 * cf1 \n\
\ while cf1s <= cp \n\
\ cf2 := 2 \n\
\ pr := cf1 * cf2 \n\
\ while pr <= cp \n\
\ if pr == cp \n\
\ found := 1 \n\
\ end \n\
\ cf2 := cf2 + 1 \n\
\ pr := cf1 * cf2 \n\
\ end \n\
\ cf1 := cf1 + 1 \n\
\ cf1s := cf1 * cf1 \n\
\ end \n\
\ if found == 0 \n\
\ write cp \n\
\ n := n - 1 \n\
\ end \n\
\ cp := cp + 1 \n\
\end \n\
\$$"
If you run
ghci> interpret (parseTable extendedCalcGrammar) primes ["10"]you should see the output
Right ["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 less than 600 lines of Haskell. 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 (you may have testing code in the typeIO a, but none of the interpreter will be).
You should make small test cases for debugging; there is no analog of
fprintf for middle-of-the-run output. Keep reloading
your file in ghci (:r) as you go along so you catch type
errors early.
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.
These values can be wrapped in the Environment data type as
is shown by the types given in the outline code.
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 recursive.
We will be grading your assignment using the “GHCi”
interpreter: /bin/ghci. You can
download your own
version of GHC for Windows, MacOS, or Linux, but please be
sure to check that your code works
correctly on the csug installation.
My (not necessarily great) implementation of toAstP is
just over 25 lines of code.
My version of interpretAst is around 100 lines.
You may find the following helpful.
As in most 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 interpretAst is harder to write than
toAstP;
a fair division of labor might be to have one team member write
toAstP and interpretExpr, and the other team
member write the rest of toAstP.
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 to introduce rules that you will want to
check statically.
Before the beginning of class on Tuesday, October 2, send e-mail to
to cs254@cs.rochester.edu containing answers to the following
questions:
parse (parseTable extendedCalcGrammar) p?
p = words "read a \n\
\read b \n\
\read c \n\
\sum := ( ( a * b ) + ( b * c ) + ( c * a ) ) / 3 \n\
\write sum \n\
\$$"
p = words "read a b \n\
\read c \n\
\sum := ( ( a * b ) + ( b * c ) + ( c * a ) ) / 3 \n\
\write sum \n\
\$$"
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 |
