Assignment 3:  Interpretation

Your task in this assignment is to implement a complete interpreter for our extended calculator language (call it ECL), again with if statements, do/check statements, and both int and real types.  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 form 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.  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"; "SL"; "fi"]; ["do"; "SL"; "od"]; ["check"; "C"]
           ])
  ; ("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 (abstract syntax tree for a statement list) 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_prog, the second argument is the input string to be read by the interpreted program, and the return value is the program output (the concatenation of values from write statements), possibly ending with an error message. 

    You are required to catch the following semantic errors:

    • Use of an undeclared variable.
    • Redeclaration of a variable in the same scope.
    • Non-integer provided to float.
    • Non-real provided to trunc.
    • Type clash in binary expression, comparison, or assignment.
    • check statement not inside a loop.
    • Non-numeric input, unexpected end of input, int read when real is expected, or real read when int is expected.  (Unlike the scanner, the input processing mechanism assumes that numbers are separated by white space, so 12.34 on the input, when an int is expected, should be an immediate error.)
    • Division by zero.

    You should treat each statement list as a separate scope.  So a variable declared inside an if or do 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).  Note that while a declaration inside a do loop enters a name into the symbol table only once, the read or assignment that initializes that variable occurs on every iteration. 

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_run prog inp =
    interpret (ecg_ast prog) inp;;
If you are working in the ocaml interpreter, that last function is the one you’ll want to call to interpret small programs.  For larger programs, you’ll want to read the source from a file.  Toward that end, the provided code also includes a main function that runs when your interpreter is compiled with ocamlc, rather than being run inside the ocaml interpreter.  This function
  1. reads an ECL program from the file specified on the command line;
  2. reads input from stdin;
  3. runs the ECL program on the input.
So if you place the prime-generating program from
project 2 in file primes.ecl, you can type
  % ocamlc -o ecl str.cma interpreter.ml
  % ./ecl primes.ecl
  10
and see
  2 3 5 7 11 13 17 19 23 29
as output.  Note that input-processing mechanism is quite simplistic: it requires you to enter all input and type ^D before it does anything—it is not interactive (and in fact, if your program takes no input at all, you must still type ^D).  If you put the number 10 in a file named input, you could repeat the above run by typing
  % ./ecl primes.ecl < input

In addition to (incomplete) starter code, we are also providing an already-compiled solution to the assignment, which you can run to get a sense of the output we’re expecting—and in particular to see how you might respond to semantic errors.  You can find this solution in ~cs254/bin/ecl on the csug network. 

Because the solution was written quickly (and your instructor is definitely not a a perfect programmer), it’s possible that the provided solution and/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 interpreter does not have to produce exactly the same error messages as the provided solution (feel free to do better!), so long as it meets the requirements described on this page. 

Warning: your program must not take advantage of any imperative features in OCaml.  You may perform I/O and run the while loops 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 interpretation routines must be purely functional. 

Hints

The initial source code is about 1060 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 "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 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 interpreter.ml

The provided source includes code for several ECL programs (sum-and-ave, primes, gcd, sqrt).  You may want to put these into separate files, so they can be executed by the compiled version of your interpreter.  You will undoubtedly want to write additional tests. 

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 70 lines of code.  My version of the full set of interpret_ functions is about 150 lines, not counting the provided code for memory and values. 

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 interpret, 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 semantic rules that you will want to check. 

  2. Implement a separate pre-pass over the AST to enforce static semantics.  In particular, you should be able to find the first six kinds of errors above before your ECL program executes. 

  3. Implement simple forms of code improvement via transformations of the AST.  A good place to start would be constant folding, which collapses arithmetic and logical operations on constants in a pre-execution pass over the tree.  More ambitiously, you might look for common subexpressions in separate expressions, which could be computed only once, and kept in a temporary. 

  4. Write a routine to turn the AST into C code, so you can compile and then execute the output. 

  5. Add syntax error recovery. 

Grading Rubric

Trivia Assignment

Before the start of class on Wednesday, October 11, each student should complete the T3 trivia assignment found on Blackboard. 

MAIN DUE DATE: 

Wednesday October 25, by end of day; no extensions. 

Warning: start now!  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:  11 October 2023 / Michael Scott's email address