Assignment 3:  Translation

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: 

  1. Translate the parse tree into a syntax tree: 
      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. 

  2. Translate the AST into an equivalent program in C: 
      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:

    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.

Putting the pieces together, the provided code includes the following: 
  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,

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
  10
and 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. 

Hints

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. 

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. 

Division of labor and writeup

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. 

Extra Credit Suggestions

  1. Extend the calculator language in other interesting ways.  You might, for example, implement arrays, for loops, nested scopes, or functions.  Several of these are likely to introduce new rules that you will want to check statically. 

  2. Implement simple forms of code improvement.  A good place to start would be constant folding, which performs arithmetic and logical operations on constants at compile time instead of generating code to perform them at run time.  More ambitiously, you might look for common subexpressions in separate expressions, which could be computed only once, and kept in a temporary. 

  3. Generate x86 assembly code instead of “Pidgin C.” 

  4. Write code to interpret the AST directly on a given input, rather than (or as an alternative to) translating to C. 

  5. Minimize the use of temporaries, subject to the Pidgin C rules above. 

  6. If you’re in 254, implement stack-based allocation of temporaries and overlap of variables with disjoint lifetimes. 

  7. Add syntax error recovery. 

Trivia Assignment

By end of day on Friday, October 14, each student should complete the T3 trivia assignment found on Blackboard. 

MAIN DUE DATE: 

Sunday October 30, by end of day; no extensions. 

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. 


Last Change:  12 October 2022 / Michael Scott's email address