Chapter 8: Storage Management

7.7 REPRESENTING THE SCOPE INFORMATION IN THE SYMBOL TABLE

Every name possesses a region of validity within the source program, called the "scope" of that name . The rules governing the scope of names in a block-structured language are as follows :

1. A name declared within a block B is valid only within B .

2. If block B 1 is nested within B 2, then any name that is valid for B 2 is also valid for B 1, unless the identifier for that name is re-declared in B 1.

These scope rules require a more complicated symbol table organization than simply a list of associations between names and attributes. One technique that can be used is to keep multiple symbol tables, one for each active block, such as the block that the compiler is currently in. Each table is list of names and their associated attributes, and the tables are organized into a stack. Whenever a new block is entered, a new empty table is pushed onto the stack for holding the names that are declared as local to this block. And when a declaration is compiled, the table on the stack is searched for a name. If the name is not found, then the new name is inserted. When a reference to a name is translated, each table is searched, starting from the top table on the stack, ensuring compliance with static scope rules. For example, consider following program structure. The symbol table organization will be as shown in Figure 7.6.

 Program main Var x,y : integer : Procedure P : Var x,a : boolean; Procedure q Var x,y,z : real; Begin . . end begin : end begin : end 

Figure 7.6: Symbol table organization that complies with static scope information rules.

Another technique can be used to represent scope information in the symbol table. We store the nesting depth of each procedure block in the symbol table and use the [procedure name, nesting depth] pair as the key to accessing the information from the table. A nesting depth of a procedure is a number that is obtained by starting with a value of one for the main and adding one to it every time we go from an enclosing to an enclosed procedure. This number is basically a count of how many procedures are there in the referencing environment of the procedure.

For example, refer to the program code structure above. The symbol table's contents are shown in Table 7.1.

Table 7.1: Symbol Table Contents Using a Nesting Depth Approach

X	1	real
Y	1	real
Z	1	real
q	3	proc
a	3	Boolean
X	3	Boolean
P	2	proc
Y	2	integer
X	2	integer