Your task in this assignment is to implement a complete (if
simplistic) compiler for our extended calculator language (call it
ECL), again with if
statements, while
statements, and both int
and real
types. Your compiler (hereinafter referred to as the
“translator”) will be written in OCaml and will generate
a low-level subset of C.
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 translation.
You are of course welcome to adopt a different skeleton if you
prefer.
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),
parse
will print an error message (as a side effect)
and return a PT_error
value (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.
When get_parse_table
builds the parse table, the grammar is
augmented with a start production that mentions an explicit end of file
$$
. Later, 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", [ ["int"; "id"; ":="; "E"]; ["real"; "id"; ":="; "E"] ; ["id"; ":="; "E"]; ["read"; "TP"; "id"]; ["write"; "E"] ; ["if"; "C"; "then"; "SL"; "end"] ; ["while"; "C"; "do"; "SL"; "end"] ]) ; ("TP", [["int"]; ["real"]; []]) ; ("C", [["E"; "RO"; "E"]]) ; ("RO", [["=="]; ["<>"]; ["<"]; [">"]; ["<="]; [">="]]) ; ("E", [["T"; "TT"]]) ; ("TT", [["AO"; "T"; "TT"]; []]) ; ("T", [["F"; "FT"]]) ; ("FT", [["MO"; "F"; "FT"]; []]) ; ("F", [ ["id"]; ["i_num"]; ["r_num"]; ["("; "E"; ")"] ; ["trunc"; "("; "E"; ")"]; ["float"; "("; "E"; ")"] ]) ; ("AO", [["+"]; ["-"]]) ; ("MO", [["*"]; ["/"]]) ];;
A program is just a string:
let sum_ave_prog = " read int a; read int b; int sum := a + b; write sum; write float(sum) / 2.0;";;
Your work will proceed in two steps:
let rec ast_ize_prog (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_sl
type, though you are free to modify this if you prefer a different
format.
let translate_ast (ast:ast_sl) : int * int * string * string = ...where the argument is a syntax tree, as generated by function
ast_ize_prog
and the return value is a tuple containing two integers and two strings.
If the program represented by the AST is semantically correct, the
first of the returned strings should comprise equivalent C
code, the second string should be empty, and the integers should
indicate the amount of needed memory and temporary space (more on
this below).
If the AST has static semantic errors, the first string should be
empty and the second should be a sequence of helpful error
messages.
You should catch the following semantic errors:
float
.
trunc
.
You should treat each statement list as a separate scope.
So a variable declared inside an if
or
while
statement can have the same name as a variable
declared outside (and will hide the outer variable in the
remainder of the nested statement list).
If your translator finds no errors—and thus produces output code—that code should generate no compile-time error messages if fed to a C compiler. Moreover the compiled C program should correctly embody the dynamic semantics of the original ECL program.
let ecg_parse_table = get_parse_table ecg;; let ecg_ast prog = ast_ize_prog (parse ecg_parse_table prog);; let ecg_code prog = translate_ast (ecg_ast prog);;If working in the interpreter, that last function is the one you’ll want to call to look at the code generated for small programs. For larger programs, you’ll want to read from and write to files (or at least standard input and output). Toward that end, the provided code also includes the following:
let main () = let lines = ref [] in try (* This loop is imperative, but you're allowed to leave it as is. *) while true do lines := read_line () :: !lines; done with End_of_file -> let prog = String.concat "\n" (rev !lines) in let (max_addr, max_temp, code, errs) = ecg_code prog in if errs <> "" then Printf.eprintf " %s\n" errs else begin print_string prologue; Printf.printf " int64_t i[%d]; double *r = (double *) i;\n" (max_addr + 1); Printf.printf " int64_t ti[%d]; double *tr = (double *) ti;\n\n" (max_temp + 1); Printf.printf " %s\n}\n" code; end;; if !Sys.interactive then () else main ();;That last line queries the system variable
Sys.interactive
(the !
symbol is not a
unary minus—it’s a read of a mutable variable); this
variable indicates whether you’re in the interpreter or
not.
If not (i.e., if you’re running a compiled version of your
translator), then it executes function main
.
That function reads an ECL program from standard input, accumulating
it into the value prog
and feeding it to
ecg_code
.
If there are errors, they are printed (via eprintf
) to
standard error.
If the program is error-free, code is printed to standard output
instead.
To make the code complete, main
prepends a
“prologue
” string that defines utility
routines for ECL I/O, trunc
, float
, and
checked division.
It also prepends declarations for an array of “memory”
locations (accessible as i[
n]
and r[
n]
) and an array
of temporaries
(accessible as ti[
n]
and tr[
n]
)—as many
as ecg_code
said it needed.
The intent is that you should keep variables in the i
and r
locations and treat the ti
and
tr
locations as if they were the registers of an
imaginary target machine.
Note that the prologue code we have given you puts the
i
and r
arrays (and likewise the
ti
and tr
arrays)
on top of each other, reflecting the fact that in a real assembly
language memory is untyped.
On the x86, double
and int64_t
variables
in C are both 64 bits in length.
To receive full credit on the assignment, you will need to generate very low level “Pidgin C”— the rough equivalent of assembly language. Specifically,
i
,
r
, ti
, and tr
.
main
.
goto
s.
if
and while
condition must be
computed into a temporary explicitly, as must any
non-trivial arguments to trunc
and
float
, and any built-up expressions that are
themselves the operands of binary operators.
As an implementation strategy, I strongly suggest that you start by generating something, then progressively refine it to meet the requirements; more on this under “Hints” below.
In addition to (incomplete) starter code, we are also providing a
working solution to the assignment, which you can run to get a sense
of the output we’re expecting. You can find this
solution in ~cs254/bin/ecl
on the csug
network. If you put the primes-generating program from
project 2 into file primes.ecl
, you should be
able, at the command line, to type
cycle1> ecl < primes.ecl > primes.c cycle1> gcc -o primes primes.c cycle1> ./primes 10and see the output
2 3 5 7 11 13 17 19 23 29
Because I wrote my solution quickly in a compressed span of time (and I’m not any more perfect than the next person), it’s possible that the provided solution (or the starter code) has bugs. If you find one, please report it ASAP and I’ll try to release a fix. Note that your translator does not have to produce exactly the same code as the provided solution, so long as it meets the requirements described on this page.
Warning: your program should not take advantage of any
imperative features in OCaml. You may perform I/O
and run the while
loop in main
as
described above, and you can of course do whatever you want while
debugging, but the main logic of your final syntax tree construction
and translation routines must be purely functional.
OCaml code tends to be quite dense, and can be intimidating to a newcomer. Rather than try to code up a complete solution before you start debugging, I strongly recommend that you create a version that does something quickly, and then progressively refine it.
trunc
or float
call) to be assigned
directly into a variable, without going through a temporary
first.
I found this surprisingly tricky to get right. Both 254 and 454
students can receive full credit for being a bit more
profligate. So, for example, instead of
i[6] = i[3] * i[5]; r[3] = to_int(r[4]);you can generate
ti[0] = i[3] * i[5]; i[6] = ti[0]; tr[1] = to_int(r[4]); r[3] = tr[1];Feel free to implement the shorter version for extra credit.
i
and r
array slots) for variables that
are not simultaneously live—e.g., for x and y in the
following:
if a < b then real x := a / b; write x; end; if b < c then int y := trunc(b) * c; write y; end;Students in 254 can get full credit for giving every variable in the program a separate slot. Students in 454 need to overlap where possible for ful credit credit (and students in 254 can do so for extra credit). Everyone should try the simpler approach first.
The initial source code is about 1100 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. You’ll want to keep
reloading your source code (#use "ecl.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 we have given you uses functions (regexp
and split
) from the Str
library.
This library is not visible to either the interpreter or the compiler by
default.
In ocaml
, you will need to say
#load "str.cma";;before you
#use
your source code.
(Once is enough; you don’t have to re-#load
in order
to re-#use
.)
With ocamlc
, type the following at a shell prompt:
ocamlc -o ecl str.cma ecl.ml
We have provided code for several ECL programs
(sum-and-ave
, primes
, gcd
, sqrt
).
You will undoubtedly want to write more for purposes of debugging.
We will be grading your assignment using
/usr/bin/ocamlc
on the csug
machines. You can
download your own
copy 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 the full set of
ast_ize_
functions is
about 90 lines of code.
My version of the full set of translate_
functions is about
185 lines, not counting the symbol table code and the prologue string.
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.
The most obvious division of labor is for one team member to write
ast_ize_prog
and the other to write translate_ast
,
but the former is probably easier than the latter, so you may want to
consider other options.
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
, README.md
, or
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.
for
loops,
nested scopes, or functions.
Several of these are likely to introduce new rules that you will
want to check statically.
By end of day on Friday, October 14, each student should complete the T3 trivia assignment found on Blackboard.
Warning: start now! Many students didn’t start working on A2 soon enough, and ran into trouble. A3 is significantly harder than A2. When writing the sample solution, there were several times when I needed to stop, think for a day, and come back to it. You will need to do the same; don’t procrastinate.