Assignment 3:  Interpretation

Your task in this assignment is to implement a complete interpreter for an extended version of the calculator language, again with if and do/check statements.  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 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. Walk the syntax tree to determine its behavior on a given input: 
      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. 
Putting the pieces together, the provided code includes the following: 
  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 if and 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
                cf2 := cf2 + 1
                pr := cf1 * cf2
            cf1 := cf1 + 1
            cf1s := cf1 * cf1
        if found == 0
            write cp
            n := n - 1
        cp := cp + 1
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:

For this particular (extended calculator) language, there are no static semantic errors; everything is checked at run time. 


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 utop wrapper.  You’ll want to keep reloading your source code (#use "") 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 (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

We have provided a few small test cases in function main.  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 interpreter in /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 csug installation. 

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. 

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.  Note that interpret is harder to write than ast_ize_P; a fair division of labor might be to have one team member write ast_ize_P and interpret_expr, and the other team member write the rest of interpret.

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 a routine to turn the AST into C code, so you can compile and then execute the output. 

  3. Generate warning messages at the end of execution for any values that were assigned into a variable and then never used. 

  4. Add syntax error recovery. 

Trivia Assignment

By the end of the day on Thursday, October 6, send e-mail to to containing answers to the following questions: 

  1. Are you working alone or in a team?  If a team, who is your partner? 

  2. For the following programs p, what is the output of 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";;

  3. Write a program in the calculator language that reads a number n, reads n additional numbers (this will need a do loop), and prints the average of those additional numbers.  Verify the syntactic correctness of your program using the provided parser generator. 

  4. Write an OCaml function that given inputs n and k computes the binomial coefficient
    ( n )  =  n! / (k! × (nk)!)
    You will probably want to write a separate (recursive) factorial function. 


Tuesday October 18, at 11:59 pm; no extensions. 
Last Change:  05 October 2016 / Michael Scott's email address