COMP 3010 Translation (A3) Dr. Wilkes – Spring 2020 Page 1 of 6 Assignment 3: Translation COMP 3010 – Organization of Programming Languages March 2020 [Note: This assignment is adapted from the original version authored by Prof. Michael Scott.] Problem description 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 (which we will call the “translator”) will be written in OCaml and will generate C code. We are providing you with a complete parser generator and driver (in the file “parser.ml”) that build an explicit parse tree. The provided code also includes the skeleton (stubs) of a possible solution (in the file “translator.ml”) that converts the parse tree to an abstract syntax tree (AST), and then recursively “walks” the AST to produce the translation into C. The provided parser code has two main entry points: get_parse_table : grammar -> parse_table = … parse : parse_table -> string -> parse_tree = … The first of these functions returns a parse table, in the format expected as the first argument of the second function. The second function returns a parse tree. (Two example parse trees are included as text files in the code directory provided for the assignment.) 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).1 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. 1 If the input grammar provided to the parser generator is malformed, it may produce unhelpful run-time errors—it isn’t very robust. COMP 3010 Translation (A3) Dr. Wilkes – Spring 2020 Page 2 of 6 The format of the grammar for 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 in “translator.ml”. 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 COMP 3010 Translation (A3) Dr. Wilkes – Spring 2020 Page 3 of 6 that are assigned to (or read) but never used in the program. 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 (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 COMP 3010 Translation (A3) Dr. Wilkes – Spring 2020 Page 4 of 6 For the sake of convenience, we recommend that your output program always begin with definitions of two helper functions: #include #include 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 give a warning if the input program assigns to any variable that is never used. (You do not have to detect whether the program contains a variable 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 semantic 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. • unexpected end of input (attempt to read when there’s nothing there) • non-numeric input (the extended calculator language accepts only integers) • use of an uninitialized variable—one to which a value has not yet been assigned (read-ing counts as assignment) • divide by zero (Note: C’s automatically generated “floating exception” is not very helpful; ideally you want an error message such as “divide by zero at line 23”. You should write your code so that if you were tracking line numbers, you could easily include the line number in the error message. That is, your generated code should check explicitly to make sure that denominators are not equal to zero (even though your error message does not have to include the line number.) Suggestions 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 “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. COMP 3010 Translation (A3) Dr. Wilkes – Spring 2020 Page 5 of 6 In “translator.ml”, we have provided code for the sum-and-average and primes- generating calculator programs. You will undoubtedly want to write more calculator programs for purposes of debugging. We will be grading your assignment using the OCaml interpreter in the Ubuntu VM. You can download your own copy of Ocaml for Windows, MacOS, or Linux, but please be sure to allow ample time to check that your code works correctly on the VM 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. Besides the resources mentioned already during class, you may find the following helpful: • OCaml system documentation—Includes the language definition; manuals for the interpreter, compilers, and debugger; standard library references; and other resources: • Tutoria
ls on various aspects of the language: • OCaml for the Skeptical—An alternative, arguably more accessible introduction to the language from the University of Chicago: • Developing Applications with Objective Caml—A book-length online introduction to functional programming and everything OCaml: • Real World OCaml, 2nd Edition—A free online version of a popular print book on OCaml; we recommend Chapter 1 (“A Guided Tour”) as a good overall introduction, and the rest of the book is an excellent reference with lots of examples: Division of labor and submission procedure You may work alone on this project, or in teams of two or three. Be sure your write-up (README file) describes any features of your code that the TA might not immediately notice – for example, how to run your code (e.g., in the interpreter, or creating a stand-alone executable). If you choose to work in pairs/triples, we strongly encourage you to read each other’s code, to make sure you have a full understanding of semantic analysis. The most obvious division of labor for a 2-person team is for one team member to write ast_ize_P (and its associated functions), and the other to write translate (and its associated functions), but other divisions are fine as well. COMP 3010 Translation (A3) Dr. Wilkes – Spring 2020 Page 6 of 6 To turn in your code, use the following procedure, which will be the same for all assignments this semester: 1. Your code should be in a directory called “_OPL_A3” (for example, “TomWilkes_OPL_A3”). Put your write-up in a README.txt or README.pdf file in the same directory as your code. 2. In the parent directory of your A3 directory, create a tarball (.tar.gz) or Zip file that contains your A3 directory (e.g., “TomWilkes_OPL_A3.tar.gz”). 3. In the page for Assignment 3 on Blackboard, use the Submit button to upload your tarball or Zip file. When you submit, give the name(s) of your partner(s) (if applicable) in the submission comments field.
