CS 405/505 ASSIGNMENT #10

Due Thursday, December 15, 2005, 5:00 P.M. ¹

1. Design and implement symbol table management routines to store all of the identifiers used in a program. Specifically, you should have operations to 1) add an identifier to the symbol table, 2) look up an identifier in the symbol table to see if it is there or not, returning the denotable value if it is, and 3) print the symbol table. The symbol table will contain the names of identifiers, whether the identifier denotes a variable or a subprogram, as well as other attributes. These attributes are as follows:
   • Variable identifier - there will be three attributes: 1) the type (integer or array) of the variable, 2) whether the variable is a formal parameter or not (this can also be handled by partitioning the symbol table into discernible units, one for the formal parameters and one for the regular variables), and 3) the value of the variable (not assigned until run-time).
   • Subprogram identifier - there will be two attributes: 1) the subprogram's local symbol table containing all the identifiers within the subprogram's scope, including formal parameters, and 2) the intermediate code for the subprogram represented as a syntax tree.
   Details of the symbol table should be modeled after the environment domain in the denotational semantics of MicroCOBOL.
2. Output the local symbol table for each subprogram as well as that of the mail program. You may output this after parsing each program unit or at the end of the program.
3. Design and implement an interpreter for MicroCOBOL programs. The interpreter should traverse the syntax tree and execute the statements of the program. The denotational semantics of MicroCOBOL will assist you in constructing the interpreter. Your implementation should exactly follow the semantics. The interpreter will consist of the following components:

   1. Construct a set of interpretation routines for each general root symbol in the syntax trees. For example, you need a routine to interpret the IF statement, one for arithmetic operators, etc. Each interpretation routine will perform the actions specified in the semantics. For example, an IF statement will evaluate the condition and then either the THEN or ELSE part depending on whether the condition is true.
   2. Some run-time type checking will be required, for example to determine if an array reference is out of bounds. All such type checking is fully specified in the semantics. In the case of any errors, your interpreter need only print an appropriate error message and halt.
   3. The result of executing a program is the list of values output by DISPLAY statements. You should output this when execution terminates.
   4. In summary, your output should consist of the source program, local symbol tables and syntax trees for each program unit, and final output of the program being interpreted. If you implement your interpreter correctly, you should get the same output as the COBOL interpreter gives for the test programs (although the COBOL interpreter will execute programs which your interpreter will not).

   Suggestion: Develop this incrementally over the following steps.

   • Make your interpreter work first for expressions other than arrays.
   • Add array referencing to expressions.
   • Next handle statements other than CALL.
   • Then handle subprogram calls.