Overview The article we have been reading by Warren on compiling with Prolog (David H.D. Warren, Logic Programming and Compiler Writing, Software Practice and Experience, vol 10, pp 97-125) shows examples of compiling arithmetic expressions by parsing them into intermediate code syntax trees (represented as Prolog terms) and then translating those trees into a pseudo-assembly code. This assignment will involve (i) building a predictive parser in Prolog, patterned after the one in the Warren paper, for a simple programming language involving assignments and simple expressions with scalar and aggregate variables (e.g., arrays, structs), (ii) type checking programs in this simple language, and (iii) issuing a message that declares a program to be well-typed or, if the program is not well-typed, issuing error messages that delineate those program statements (or expressions) that cause type errors.
A word of caution: the published Warren article has many typos, despite the fact that it is an important paper. Please consult this errata sheet as you read the paper to avoid confusion.
Description We will be working with a simple procedural language that contains scalar variables, arrays and structs (similar to C). All variables are declared with types and operations involving them (e.g., assignment, addition, subtraction, concatenation) are only legal if the types are compliant with the types expected by the operation. The language does allow some type coercion; that is, one can assign an integer constant to a variable declared of type double with the appropriate type conversion happening automatically.
The following grammar describes the programming language you will be compiling. Because we are emphasizing type checking in this assignment, we will just be dealing with straight-line code and if statements. Note that we are not performing code generation in the assignment.
There are many ways to decompose this assignment into separate tasks each with a set of Prolog rules. Think about the overall organization of the type checking algorithm you will use BEFORE starting to code the Prolog and feel free to reuse parts of the Warren parser (suitably altered for our language).
Do not worry about your compiler being invertible! You can copy the following routine to use to create the input to your compiler, a scanner with some notes about its use. This input routine puts the language tokens provided to it in a string into a Prolog list. This code was written by a previous 515 student, so alter it as needed. A copy of the Warren parser, a part of the Warren code generator, and the Warren symbol table are all now available for your perusal and use (if necessary).
We have assembled some useful notes on how to run a Prolog program, how to use trace and other debugger commands, and other useful built-in predicates. We also have a file about how to print in Prolog.
What to turn in.
Initial test data is available here. Feel free to create more of your own test programs, but make sure to comment them to help in the grading. The final submission of your program will be tested on paul with additional test data. Grading will be based on correctness and quality of code produced.
You will turn in a tar file called proj1.tar that includes
your translation scheme
all your *.pl files with 1 sentence comment describing the functionality of each predicate
any extra tests constructed to show off the strengths of your code
a text README file that describes each file turned in and also gives any special instructions about running your program
We will be using the hand-in program on paul (see instructions on the programming assignments page).
Last edited by BGR at 4:06pm October 7, 2005