Programming Project 3

The third programming assignment is to augment your Psub predictive parser to perform type checking. Your first step should be to extend the original PSub grammar, as given in the handout for project 2 (with the fix discussed in class of deleting the semicolons from the productions for var_decls and decl_list, and adding a semicolon at the end of the production for declaration), by adding semantic actions to perform the following operations:

• For each variable declaration, create a symbol table entry associating the identifier with its type. If the identifier has already been declared in the current scope, then signal an error. If an array is being declared, then you should also check that the array bounds are integers.
• For each subprogram declaration, create a symbol table entry associating the identifier with its type; also create a new scope and insert each of the formal parameters into the symbol table just as if they had been locally declared. Again, if the subprogram name has already been declared in the outer scope, then signal an error.
• For each expression, compute the result type; signal an error if any type mismatches are found (for example, if a function is called with the wrong number or type of arguments). You should allow integers to be implicitly coerced to reals when necessary.
• Check that assignment statements are well-typed (this includes checking that array indices are all integers), that procedure calls have the correct number and type of arguments, and that if, while, and until statements are followed by boolean test expressions.

Your semantic actions need not be written as fully-elaborated code---pseudo-code similar to the style used for examples in class will be fine.

Once you have annotated the original grammar with semantic actions, you should perform the same steps to convert it into LL(1) form that were required for project 2. The result should be a syntax-directed translation scheme whose code is ready to be merged in with your parser. This LL(1) translation scheme is the first component of your submission for this project.

The other major phase of this assignment is, naturally, to modify your parser to include the type-checking code. This will include implementing routines to manage the symbol table and manipulate type expressions, corresponding to the pseudo-code operations used in the translation scheme. You may remove the code which printed out the parse tree for project 2; for this project, your output should be to display the contents of the symbol table at the start of each block of code---that is, at the start of each section corresponding to the production for compound_statement. If an error occurs (and by this point in compilation we should have detected just about all the errors that the compiler is able to detect), then again you should simply print a descriptive error message and quit.

You will need to initialize your symbol table with a number of standard identifiers and their types; these identifiers should be available in the initial scope, although they may be redeclared by the user. Here is the list of standard Pascal functions, constants, and procedures which are appropriate to PSub:

identifier            | type
-------------------------------------------------------------------------
abs, sqr              | over(func(integer;integer),func(real;real))
arctan, cos, exp      | func(real;real)
ln, sin, sqrt         | func(real;real)
odd                   | func(integer;boolean)
ord                   | func(boolean;integer)
pred, succ            | over(func(boolean;boolean),func(integer;integer))
round, trunc          | func(real;integer)
eof, eoln             | func(;boolean)
false, true           | boolean
maxint                | integer
page, readln, writeln | proc()
read                  | over(proc(var_integer),proc(var_real))
write                 | over(proc(integer),proc(real),proc(boolean))

In addition to the LL(1) translation scheme, you should submit a printout containing the source code for your program, plus the result of running the type checker on the example program given in the first assignment (I have placed this program in the file /pub/cis606/pp1input on the cis machines).

This assignment will be due at the start of class on Monday, November 14. To be fair to the other students, I will not grant extensions; if your program is not working by the deadline, submit what you have and I will try to assign partial credit. You may work in pairs (but not in larger groups); in fact, I would encourage this method if you are comfortable working with someone else, as it means less for me to grade!

As with all programming assignments, it will not be sufficient to simply produce code that works---it must also be adequately structured and documented. You may use any programming language you like on any machine you prefer, as long as there is a reasonable chance that I will be able to read your code. The program should be written ``from scratch''; that is, I do not want you to use compiler-building tools such as the Unix program yacc (at least, not yet).