Your task in this assignment is to implement a complete interpreter
for an extended version of the calculator language, again with
You will write your interpreter in OCaml.
We are providing you with a parser generator and
driver that build an explicit parse tree.
The provided code also includes the skeleton of a possible solution
that converts the parse tree to a syntax tree and then recursively
“walks” that tree to effect the interpretation.
You are of course welcome to adopt a different skeleton if you
Since this one has been excised from a complete working solution,
however, you may find it a good place to start.
The provided code has two main entry points:
get_parse_table : grammar -> parse_table = ... parse : parse_table -> string -> parse_tree = ...The first of these routines returns a parse table, in the format expected as the first argument of the second routine. The second returns a parse tree. (You’ll want to print some of these trees to see what they look like.) If the program has syntax errors (according to the grammar),
parsewill print an error message (as a side effect) and return a
PT_errorvalue (it does not do error recovery). 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.
get_parse_table builds the parse table, the grammar is
augmented with a start production that mentions an explicit end of file
parse will remove this production
from the resulting parse tree.
The extended calculator language looks like this:
let ecg : grammar = [ ("P", [["SL"; "$$"]]) ; ("SL", [["S"; "SL"]; ]) ; ("S", [ ["id"; ":="; "E"]; ["read"; "id"]; ["write"; "E"] ; ["if"; "R"; "SL"; "fi"]; ["do"; "SL"; "od"]; ["check"; "R"] ]) ; ("R", [["E"; "ET"]]) ; ("E", [["T"; "TT"]]) ; ("T", [["F"; "FT"]]) ; ("F", [["id"]; ["num"]; ["("; "E"; ")"]]) ; ("ET", [["ro"; "E"]; ]) ; ("TT", [["ao"; "T"; "TT"]; ]) ; ("FT", [["mo"; "F"; "FT"]; ]) ; ("ro", [["=="]; ["<>"]; ["<"]; [">"]; ["<="]; [">="]]) ; ("ao", [["+"]; ["-"]]) ; ("mo", [["*"]; ["/"]]) ];;
A program is just a string:
let sum_ave_prog = "read a read b sum := a + b write sum write sum / 2";;
Your work will proceed in two steps:
let rec ast_ize_P (p:parse_tree) : ast_sl = ...where the single argument is a parse tree generated by function
parse. We have provided a complete description of the
ast_sltype, though you are free to modify this if you prefer a different format.
let rec interpret (ast:ast_sl) (full_input:string) : string = ...where the first argument is a syntax tree, as generated by function
ast_ize_P, the second argument is the input string to be read by the interpreted program, and the return value is the concatenated program output, possibly ending with an error or warning message.
let ecg_parse_table = get_parse_table ecg;; let ecg_run prog inp = interpret (ast_ize_P (parse ecg_parse_table prog)) inp;;
Note: your program should not take advantage of any
imperative features. You may create testing code that uses
print_string and related functions, and you may keep the
code that prints an error message if the input program in the extended
calculator language contains a syntax
error, but the main logic of your syntax tree construction and
interpretation should be purely functional.
If integers were unbounded, the addition of
do/check to the calculator language would make it Turing
complete, if still quite impractical.
(For the record, with bounded integers, we'd actually need unbounded
arrays or their equivalent to emulate a Turing Machine.)
To illustrate the expressive power of the notation, here is a
program that calculates the first n primes:
let primes_prog = " read n cp := 2 do check n > 0 found := 0 cf1 := 2 cf1s := cf1 * cf1 do check cf1s <= cp cf2 := 2 pr := cf1 * cf2 do check pr <= cp if pr == cp found := 1 fi cf2 := cf2 + 1 pr := cf1 * cf2 od cf1 := cf1 + 1 cf1s := cf1 * cf1 od if found == 0 write cp n := n - 1 fi cp := cp + 1 od";;If you type
ecg_run primes_prog "10";;you should see the output
2 3 5 7 11 13 17 19 23 29
You are required to catch the following dynamic errors, any of which will cause the program to terminate early:
The initial source code is about 730 lines of OCaml. 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 :-).
For most of the assignment, it will probably be easiest to use the
ocaml interpreter or its
You’ll want to keep
reloading your source code (
#use "interpreter.ml") as you
go along, so you catch syntax and type errors early.
On occasion, you may also want to try compiling your program with
ocamlc, to create a stand-alone executable.
Note that the code have given you uses functions (
split) from the
This library is not visible to either the interpreter or the compiler by
ocaml, you will need to say
#load "str.cma";;before you
#useyour source code. (Once is enough; you don’t have to re-
#loadin order to re-
ocamlc, type the following at a shell prompt:
ocamlc str.cma interpreter.ml
We have provided a few small test cases in function
You will undoubtedly want more for purposes of debugging.
You will want to pass the (remaining) input, the output so far, and the
current “memory” (mapping from names to values) to and from
most of the routines that walk the AST.
Note that the routine that evaluates a
do statement will
need to be recursive (in fact, it should be tail recursive).
We will be grading your assignment using the version of the
/u/cs254/bin/ocaml. You can
download your own
copy for Windows, MacOS, or Linux, but please be
sure to allow ample time to check that your code works
correctly on the
My (not necessarily great) implementation of the full set of
ast_ize_ functions is
about 65 lines of code.
My version of the full set of
interpret_ functions is
another 65 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.
interpret is harder to write than
a fair division of labor might be to have one team member write
interpret_expr, and the other team
member write the rest of
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.pdf file in the directory in
which you run the script (only one
README required per
team). Be sure to describe any features
of your code that the TAs might not immediately notice.
forloops, nested scopes, or functions. Several of these are likely to introduce rules that you will want to check statically.
By the end of the day on Thursday, October 6, send e-mail to
email@example.com containing answers to the following
parse ecg_parse_table p;;?
let p = " read a read b read c sum := ((a*b)+(b*c)+(c*a))/3 write sum";;
let p = " read a b read c sum := ((a*b)+(b*c)+(c*a))/3 write sum";;
doloop), 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)!)|