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.

Assignment Requirements

1. Write a syntax directed translation scheme with code attributes that correspond to your type checking for each of the statements in our grammar. Explain the properties of the code attributes you need to define in order to type check a program in the given language.

2. Write a Warren-style Prolog parser for this language. Your compiler should parse a program and type check the program according to our typing rules. If the program does not type check, then there should be error messages generated for each type error. You should make sure that enough information is included in these messages for the user to fix their errors. WARNING: you can spend lots of time on fancy error checking and recovery. Get the main functionality of the assignment working with simple error checking before getting 'fancy'.

3. Suggestion: the best way to tackle the assignment is probably to concentrate first on the statements which involve only simple scalar variables. Then add in scalars of aggregate type (e.g., structure fields and array elements). Finally, add in the arrays and structures, which have their own assignment statements as aggregates. (Each of these functionalities will earn you credit separately.)

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