CIS 606. Translator Design I

Programming Project 3

The third programming assignment is to augment your PSub predictive parser to perform the semantic analysis phase. Your first step should be to extend the original PSub grammar, as given in the handout for Project 2, by adding semantic actions to perform the following operations:

• For each variable declaration, enter the appropriate type in the identifier's symbol table entry. If the identifier has already been declared in the current scope, then signal an error; if the identifier has already been declared in another scope, a new symbol table entry should be created for the new declaration.
• For each procedure and function declaration, enter the appropriate type and check for redeclaration as above; also, create a new scope for the formal parameters and local variables of the subprogram.
• 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 parameters). You should allow integers to be coerced to reals when necessary.
• Check that assignment statements are well-typed, that procedure calls have the correct number and type of arguments, and that if, while, and until statements contain boolean test expressions.

Once you have annotated the original grammar, you should convert it into a translation scheme in LL(1) form. The resulting translation scheme should then be implemented by inserting appropriate actions into your recursive descent parser, as well as coding all the necessary data structures and auxiliary functions.

The main program should first initialize the symbol table with the standard Pascal functions, procedures, and constants (see table below), then call the modified ParseProgram() to process the input. Instead of printing out the parse trace as in Project 2, you should print out the contents of the symbol table (all visible identifiers, with their types and scopes) at the start of each function, procedure, and program body. If an error occurs (and by this point in compilation we should have detected all the errors that the compiler is able to detect) then you should print out a descriptive error message and quit, just as in Project 2.

Standard Pascal Identifiers (Global Scope)

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

This assignment will be due at the start of class on Wednesday, June 26. To be fair to the other students, I will not grant extensions; if your code 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 work for the grader!

As with all programming assignments, it will not be sufficient to simply produce code that works---it must also be adequately structured and documented. An important part of this phase is the design of the symbol table and type description data structures, so you should concentrate on providing a complete and convenient set of routines for creating and maintaining these.

You should submit a printout containing all the source code for your modified parser, main program, and auxiliary routines, plus the result of running the main program on the same example program from Projects 1 and 2 (which is still in the file /pub/CIS606/pp1input on the cis machines). You should also submit the annotated original grammar constructed in the first step above.