Semantic Analysis

In this phase of the project, you are required to create and manipulate symbol tables, and detect semantic errors as well as bring together the various issues of semantic analysis discussed in the class.

Due date

No due date for this project.

Project Summary

Your task is to write a static semantic analyzer that

•  creates a symbol table for the source program;

•  augments the abstract syntax tree (produced by the parser) with appropriate semantic information;

•  checks that the source program abides by some of the semantic rules of the MINI-JAVA language, and reports any violations.

Scoping Rules

The scope of a name is the region of the program in which the name can be used. MINI-JAVA has just three levels of scoping. Variables (including formal parameters) declared within a method are local and can only be used within the declaring method. Variables and methods declared in a class are local to that class. They are directly accessible from the point of declaration to the end of the class, as well as from the bodies of methods (of that class) that do not redeclare the same name.  The same variable name can be declared in other methods without a conflict. All methods declared within a class can reference the objects declared in the class, including methods.

Objects (including declarations and method names) declared in one class can be used by objects of other classes provided the proper class name is attached, e.g. System.println, MyClass.Sort etc.

The lifetime of object declarations within a method is limited to the execution of the method (i.e.  the values are discarded upon exit), while objects declared in a class last for the lifetime of the program.

Static Semantics

The following static checks must be performed.

1.  All names declared within the same block (i.e., method or class) must be unique.

There will be two flavors of look into the symbol table.

1.  When processing a new declaration, you will want to perform a lookup operation restricted to the current block of declarations (i.e., the names declared locally within this block thus far) to determine whether the symbol is multi-declared.

2.  When processing the use of a name, you will want to perform a lookup over all currently accessible names starting with the local declarations, and if not found, continuing to the non-locals.

Thus two lookup procedures are needed, and the symbol table must be organized to include block infor- mation such that the local declarations are found first.

One way to approach this is to maintain the symbol table as a stack that always contains the set of accessible declarations with respect to the current block being processed during symbol table creation and syntax tree augmentation. The stack will grow and shrink by the number of local declarations as processing enters and leaves a block, respectively, and the latest instance of a variable declaration in the currently accessible blocks will always be the one closest to the top of the stack.

However, since the complete symbol table is needed for the code generation phase, the symbol table entries can not be deleted during this phase.  In order to retain symbol table entries which are no longer active (i.e., accessible) with respect to the current block being processed, the symbol table stack can be maintained as a separate data structure with reference into the permanent symbol table structure.

For example, a stack of records can be maintained where each record contains a boolean marker, an id, and a pointer to the entry for that id in the symbol table.  When the semantic analyzer begins to process the declarations of a new procedure definition, an OpenBlock routine pushes a record (true, undefined, undefined) onto the stack to indicate the beginning of a new block.  Processing of subsequent declarations within that procedure includes pushing records of (false,id,pointer) onto the stack.

Note that the procedure name should be entered into the symbol table before calling OpenBlock to signal the start of a new block because the procedure name is actually defined where it is declared.

When the limited form of the lookup is called, it scans the stack from the top until it finds the desiredid or the last true marker that was pushed onto the stack (indicating that the identifieris not yet declared in the current block).

After processing all the statements within a procedure definition, the CloseBlock routine pops all records since the last true marker, and then pops the true marker.

The following symbol table utility routines have been written for you and are available from class web- page.

STInit()

Called before any other symbol table routine to initialize the symbol table, current nesting level, etc.

InsertEntry(ID:integer) return STIndex

Add an entry to current symbol table for identifier ID (unique index into string table), returning indexof entry in symbol table. This entry has no attributes initially. ID should not have been defined since last OpenBlock.

LookUP(ID:integer) return STIndex

Return most recently added instance of ID in symbol table, or NullST (i.e.  0) if none.

LoopUpHere(ID:integer) return STIndex

Return most recently added instance of ID in symbol table since last OpenBlock. Return NullST (i.e. 0) if none.

LookUPField(ID:integer) return STIndex

Return the symbol table entry of record field ID. ST indicates where the search starts in the symbol table. Return NullST if none.

OpenBlock()

Start a new block of symbols in the symbol table.

CloseBlock()

Restore the symbol table to the set of STIndices prevailing before the last Open- Block.

IsAttr(ST:STIndex; AttrNum:integer) return boolean

Return true iff ST has attribute numbered AttrNum.  For a newly-defined symbol, ST, it is false for all attributes.

GetAttr(ST:STIndex; AttrNum: integer) return integer, boolean or ILTree

Return value of attribute AttrNum of ST; value may be integer, boolean or ILTree. SetAttr(ST:STIndex; AttrNum: integer; V: integer, boolean or ILTree

Makes GetAttr(..)=V and IsAttr(ST,AttrNum) true.

procedure STPrint()

Print all symbols and attributes in the symbol table.

Syntax Tree Augmentation

You are required to traverse the syntax tree you built in the second project and augment the syntax tree. Your syntax trees have to be changed to incorporate the following:

1.  Converting leaves of type IDNode which represent the int type to leaves INTEGERTNode (if this was not done already).  You can modify to your tree manipulation routines of the second project for this change only.

2.  Converting all other leaves of the type IDNode to leaves of type STNode.

3.  Replacing the integer value stored in each IDNode by a unique pointer into the symbol table.  Each occurrence of an id is replaced with a reference to the symbol table entry containing the necessary semantic information for that id.  This may also require minor modifications to your tree to handle

STNodes