Project, Phase 3: Semantic Analysis

Assigned: Wednesday, March 14, 2001
Due: Monday, April 9, 2001

Summary: In this stage of the project, you will design and implement the portion of your compiler that is responsible for verifying that variables used in the program are defined and that the procedure calls, assignments, and record and pointer dereferences are types safe. Your semantic analyzer will take a parse tree and an output stream as parameters, scan through the tree, and report any errors to the stream.

Group Work: You should work in groups of size 3. You have been assigned to particular groups.

Code Reuse You may use any of the parsers created for this class (or you may create a new one).

Step 1: Build a Symbol Table System

Since many aspects of semantic analysis require a symbol table, your first order of business should be to not only build a Symbol Table class (which can tell whether or not variables are defined and which can give the type of a variable), but also to consider how to use multiple symbol tables for nested scopes. I would suggest that your initial design provide the opportunity for returning types, but not yet implement that functionality.

Step 2: Check Declarations

Add a procedure that will scan through the parse tree, checking whether all variables that are used are declared. You should expect to expand this procedure to do other kinds of semantic analysis.

The structure of this procedure is fairly straightforward. For every block, it should scan through the declarations to build a new symbol table. Next, it should scan through the body, checking to ensure that each identifier appears in an appropriate symbol table.

Step 3: Design Types

Before you move on to type checking, you should design classes for each kind of type your program will work with (basic types, subranges, enumerated, records, pointers, procedures, functions, etc.).

Step 4: Type Check

Update or rewrite your procedure from step 2 to type check the program. You may find it convenient to have the procedure return a type for appropriate portions of the parse tree (particularly expressions).

As in step 2, you will want to update the symbol table before scanning a block. This time, you should also put types in the symbol table.