5.5 Symbol Table Handling

We already had a preliminary discussion about Symbol Tables in Chapter 3, Section 3.2. A Symbol Table exists throughout the compilation steps. Major operations required for a symbol table are:

• insertion,
• search,
• modify contents of a node,
• deletions are purely logical (depending on scope and visibility) and not physical,
• keywords are often stored in the symbol table before the compilation process begins, so that Scanner and Parser are able to trap them.

The Symbol Table is accessed at every stage of the compilation process:

Scanning: Insertion of new identifiers.

Parsing: Access to ensure that an operand exists.

Semantic analysis:

• Determination of types of identifiers from declarations,
• Type checking to ensure that operands are used in type-valid contexts,
• Checking scope, visibility violations.

Intermediate Representation generation: Memory allocation and relative address calculation for jumps etc.

Optimization: All memory accesses are through the Symbol Table.

Target code generation: Translation of relative addresses to absolute addresses in terms of word length, word boundary, etc.

Thus, the Symbol Table is a store house of context-sensitive and run-time information about every identifier in the source program. That is why sometimes it is called the Environment.

All accesses relating to an identifier require to first find the attributes of the identifier from the Symbol Table. In real-world compilers, it is usually organized as a hash table, which provides fast access. Compiler-generated temporary memory locations may also be stored in the symbol table.

The following attributes are stored in a Symbol Table for each identifier:

• type,
• size,
• scope/visibility information,
• base address,
• a pointer to the identifier name string.

5.5.1 Symbol Table in miniC

After addition of semantic actions for type setting in the yacc grammar of the miniC language as shown below:

decl:    dtype ‘:’ dlist ;
dtype:   IVAR | VAR | SVAR ;
dlist:   VAR	            { type($1) = type($<sym>0); }
       | dlist ‘,’ VAR      { type($3) = type($<sym>0); }
       ;

For the following declarations,

int    : a 
float  : f
string : s

we obtained the following Symbol Table dump:

[DEG](261){42652ee1} 
[E](261){402df854}
[PI](261){40490fdb}
[a](275){0}           <–––––––––+
[cos](262){8048blc}             |
[else](267){0}                  |
[f](261){0}           <–––+     |
                          |     |
[float](261){0}       <–––+     |
[for](265){0}                   |
[if](266){0}                    |
[int](275){0}         <–––––––––+ 
[s](276){0}           <–––+
[sin](262){8048c0c}       |
[string](276){0}      <–––+
[while](264){0}

For declaration of a function,

func ack(){
   return 1 
}

we obtained the following entry in the Symbol Table

[ack](268){8050d80}

due to the following type setting action in the grammar:

defn: FUNC procname { type($2) = FUNCTION;}
          ‘(’ ‘)’ stmt { } 
    | PROC procname { type($2) = PROCEDURE;}
          ‘(’ ‘)’ stmt { } 
    ;