Assignment 3:  Translation

Your task in this assignment is to implement a complete (if simplistic) compiler for the extended version of the calculator language, again with if and do/check statements.  Your compiler (hereinafter referred to as the “translator”) will be written in OCaml and will generate 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",  [ ["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: 

  1. Translate the parse tree into a syntax tree: 
      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_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 rec translate (ast:ast_sl) : string * string = ...
    where the argument is a syntax tree, as generated by function ast_ize_P and the return value is a tuple containing a pair of strings.  The first string, which will usually be empty, indicates (as a nicely-formatted, human-readable error message) the names of any variables that are assigned to (or read) but never used in the program.  (For extra credit, indicate the lines on which the assignment(s)/read(s) occur.)  This is as close as we get to static semantic error checking in this very tiny language. 
Putting the pieces together, you might write: 
  let ecg_parse_table = get_parse_table ecg;;
  let (my_warnings, my_C_prog) =
    translate (ast_ize_P (parse ecg_parse_table my_prog));;

Note: your OCaml program should not take advantage of any imperative language 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 translation should be purely functional. 

As noted in the previous assignment, the addition of if and do/check to the calculator language gives it significant computing power.  If we let primes_prog be a string containing the primes-generating program from that assignment (also included in the starter code) and then type

  print_string (snd (translate (ast_ize_P (parse ecg_parse_table primes_prog))));;
you should see, on standard output, a C program which, when compiled, run, and fed the input 10, prints
  2
  3
  5
  7
  11
  13
  17
  19
  23
  29

For the sake of convenience, we recommend that your output program always begin with definitions of two helper functions:

  #include <stdio.h>
  #include <stdlib.h>

  int getint() {
    ... // returns an integer from standard input or
        // prints an appropriate error message and dies.
  }

  void putint(int n) {
    ... // prints an integer and a linefeed to standard output.
  }

As noted above, your translator is required to print a warning if the input program assigns to any variable that is never used.  (You do not have to notice if the program contains a use that will never be executed—only the lack of any use at all.) 

The C program you generate is required to catch the following dynamic errors, any of which will cause it to terminate early (with a helpful error message).  Note that some of these errors are not caught by default in C.  Your program will have to include extra code to catch them. 

Hints

The initial source code is about 635 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 utop wrapper.  You’ll want to keep reloading your source code (#use "translator.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 str.cma translator.ml

We have provided code for the sum-and-average and primes-generating calculator programs.  You will undoubtedly want to write more for purposes of debugging. 

We will be grading your assignment using the OCaml interpreter in /usr/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 csug installation. 

As a rough guess, you should be able to write a complete implementation of ast_ize_P, translate, and everything they call in less than 150 lines of code. 

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_P and the other to write translate, but other divisions are fine as well. 

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 (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 grammar in other interesting ways.  You might, for example, implement separate integer and floating-point types, arrays, for loops, nested scopes, or functions.  Several of these are likely to introduce rules that you will want to check statically. 

  2. Write code to interpret the AST directly on a given input, rather than translating to C. 

  3. Add syntax error recovery. 

Trivia Assignment

By the end of the day on Wednesday, October 4, each student should complete the T3 trivia assignment found on Blackboard.  Students attending the Grace Hopper Celebration get an automatic extension to Sunday October 8. 

MAIN DUE DATE: 

Tuesday October 17, at 11:59 pm. 
Students attending the Grace Hopper Celebration (or partnering with an attendee) get an automatic extension to Friday October 20. 
Last Change:  13 October 2017 / Michael Scott's email address