Symbol TaBle (Compiler Design)

Symbol table:
It is a data structure used by compiler to keep track of semantics of names.After syntax tree have been constructed, the compiler
must check whether the input program is type-correct (called type checking and part of the semantic analysis). During type checking, a compiler
checks whether the use of names (such as variables, functions, type names) is consistent with their
definition in the program. Consequently, it is necessary to remember declarations so that we can detect
inconsistencies and misuses during type checking. This is the task of a symbol table
some question which a symbol table can answer for a compiler are:
1:what is its type:Data type
2:When it is used:scope
3:where it is stored:storage address
IMPLEMENTATION OF SYMBOL TABLE
The data structure for a particular implementation of a symbol table is sketched in figure below . In figure below, a
separate array ‘arr_lexemes’ holds the character string forming an identifier. The string is terminated by an
end-of-string character, denoted by EOS, that may not appear in identifiers. Each entry in symbol-table array
‘arr_symbol_table’ is a record consisting of two fields, as “lexeme_pointer”, pointing to the beginning of a
lexeme, and token. Additional fields can hold attribute values. In figure below, the 0th entry is left empty,
because lookup return 0 to indicate that there is no entry for a string. The 1st, 2nd, 3rd, 4th, 5th, 6th, and 7th entries
are for the ‘a’, ‘plus’ ‘b’ ‘and’, ‘c’, ‘minus’, and ‘d’ where 2nd, 4th and 6th entries are for reserve keyword.

FIGURE SHOWING IMPLEMENTATION OF SYMBOL TABLE
Operations that can be performed on symbol table are :
1:search
2:insert
3:delete
Some possible Implementation of Symbol table:
1:unordered list
2:ordered list
3:tree
4:hash table
Contents in a symbol table
Possible entries in a symbol table:
1: Name: a string.
2:Attribute:
*Reserved word
*Variable name
*Type name
*Procedure name
*Constant name
···
•
•
•
•
2:Data type.
3:Storage allocation, size, . . .
4:Scope information: where and when it can be used
How it handle block structure programming??
Nested blocks mean nested scopes.
Two major ways for implementation:
• Approach 1: multiple symbol tables in one stack.
• Approach 2: one symbol table with chaining
Approach 1:Multiple symbol tables in one stack
1:An individual symbol table for each scope.
2:Use a stack to maintain the current scope.
3:Search top of stack first.
4:If not found, search the next one in the stack.
5:Use the first one matched.
Note: a popped scope can be destroyed in a one-pass compiler, but it
must be saved in a multi-pass compiler.
Approach 2:One symbol table with chaining
1:A single global table marked with the scope information.
2:Each scope is given a unique scope number.
3:Incorporate the scope number into the symbol table.
/*these approach can be compared as Impicit Vs expilict*/
/*if u had any problem regarding the approaches used feel free 2 ask */