Symbol-Table concept in compiler design pdf for reference

NOTES

1. SymbolTable

2. SymbolTable
The data structure that is created and
maintained by the compilers for information
storing regarding the occurrence of various
entities like names of variables, functions,
objects,classes
Symbol table is used by both the analysis
and the synthesis parts of acompiler

3. SymbolTable
A symbol table may serve the following
purposes depending upon the languagein
hand:
To store the names of all entities in astructured
form at oneplace
To verify if a variable has beendeclared
To implement type checking, by verifying
assignments and expressions in the sourcecode
are semanticallycorrect
To determine the scope of a name(scope
resolution)

4. Information Stored in Symbol
Table
The following possible informationabout
identifiers are stored in symboltable
The name (as astring)
Attribute:Reservedword,Variablename,Type
name, Procedure name, Constantname
The datatype
The blocklevel
Its scope (global, local, orparameter)
Its offset from the base pointer (for local variables
and parameters only)

5. Implementation
Symbol table can be implementedas
UnorderedList
Linear (sorted or unsorted)list
Binary SearchTree
Hashtable
Among all, symbol tables are mostly
implemented as hash tables, where the
source code symbol itself is treated as a key
for the hash function and the return value is
the information about thesymbol.

6. EntryFormat
A symbol table maintains an entry foreach
name in the followingformat:
<symbol name, type,attribute>
For example, if a symbol table has tostore
information about the following variable
declaration:
static intinterest;
then it should store the entry suchas:
<interest, int,static>

7. Operations
A symbol table, either linear or hash,should
provide the followingoperations.
insert()
This operation is more frequently used byanalysis
phase where tokens are identified and names are
stored in thetable.
This operation is used to add information in the
symbol table about unique names occurring inthe
sourcecode.
The format or structure in which the names arestored
depends upon the compiler inhand.

8. Operations
An attribute for a symbol in the source code isthe
information associated with thatsymbol.
This information contains the value, state, scope, andtype
about thesymbol.
The insert() function takes the symbol and its
attributes as arguments and stores the informationin
the symboltable.
Forexample:
inta;
should be processed by the compileras:
insert(a,int);

9. Operations
lookup()
lookup() operation is used to search a name inthe
symbol table todetermine:
if the symbol exists in thetable.
if it is declared before it is beingused.
if the name is used in thescope.
if the symbol isinitialized.
if the symbol declared multipletimes.
The basic format should match thefollowing:
lookup(symbol)

10. Operations
This method returns 0 (zero) if the symbol doesnot
exist in the symbol table. If the symbol exists in the
symbol table, it returns its attributes stored in the
table.

11. ScopeManagement
A compiler maintains multiple block levelsof
symbol tables:
Level 0: A null hash table at level0
Level 1: Keyword in the hash table at level1
Level 2: Global symbol table which canbe
accessed by all theprocedures
Level 4: Scope symbol tables that are created
for each scope in theprogram

12. ScopeManagement
Symbol tables are arranged
in hierarchical structure as
shown in the examplebelow:

13. Structure of the SymbolTable
We will implement the symbol table as a
linked list of hash tables, one hash tablefor
each blocklevel.
Level3 Level1Level2
Hashtable
of
Locals
Hashtable
of
Globals
Hashtable
of
Keywords
Level0
null

14. Structure of the SymbolTable
Initially, we create a null hash table at level0.
Level0
null

15. Structure of the SymbolTable
Then we increase the block level andinstall
the keywords in the symbol table at level1.
Level1
Hashtable
of
Keywords
Level0
null

16. Structure of the SymbolTable
Then we increase the block level andinstall
the globals at level2.
Level1Level2
Hashtable
of
Globals
Hashtable
of
Keywords
Level0
null

17. Structure of the SymbolTable
When we enter a function, we create a level3
hash table and store parameters and local
variablesthere.
Level3 Level1Level2
Hashtable
of
Locals
Hashtable
of
Globals
Hashtable
of
Keywords
Level0
null

18. Structure of the SymbolTable
When we leave the function, the hash tableof
local variables is deleted from thelist.
Level1Level2
Hashtable
of
Globals
Hashtable
of
Keywords
Level0
null

19. Locating aSymbol
If we enter another function, a new level3
hash table iscreated.
Level3 Level1Level2
Hashtable
of
Locals
Hashtable
of
Globals
Hashtable
of
Keywords
Level0
null

20. Locating aSymbol
When we look up an identifier, we beginthe
search at the head of thelist.
Level3 Level1Level2
Hashtable
of
Locals
Hashtable
of
Globals
Hashtable
of
Keywords
Level0
null

21. Locating aSymbol
If it is not found there, then the search
continues at the lowerlevels.
Level3 Level1Level2
Hashtable
of
Locals
Hashtable
of
Globals
Hashtable
of
Keywords
Level0
null

22. Locating aSymbol
Keywords are found in the level 1 hashtable.
Level3 Level1Level2
Hashtable
of
Locals
Hashtable
of
Globals
Hashtable
of
Keywords
Level0
null

23. class Foo {
int value;
int test() {
int b =3;
return value +b;
}
void setValue(int c) {
value = c;
{intd=c;
c=c+d;
value=c;
}
}
scope ofvalue
scope ofb
Symbol tableexample
23
}
class Bar{
intvalue;
void setValue(int c){
value =c;
}
}
scope ofc
scope of c
scope ofvalue
scope ofd
block1

24. Symbol Kind Type Properties
value field int …
test method ->int
setValue method int ->void
(Foo)
…
Symbol table examplecont.
24
Symbol Kind Type Properties
b var int …
Symbol Kind Type Properties
c var int …
Symbol Kind Type Properties
d var int …
(Test) (setValue)
(block1)

25. Checking scoperules
Symbol Kind Type Properties
value field int …
test method ->int
setValue method int ->void
(Foo)
25
Symbol Kind Type Properties
b var int …
Symbol Kind Type Properties
c var int …
Symbol Kind Type Properties
d var int …
(Test) (setValue)
(block1)
voidsetValue(intc){
value=c;
{intd=c;
c=c+d;
value=c;
}
}
lookup(value)

26. Symbol Kind Type Properties
value field int …
test method ->int
setValue method int ->void
(Foo)
(Test) (setValue)
Error!
Catching semanticerrors
26
Symbol Kind Type Properties
b var int …
Symbol Kind Type Properties
c var int …
Symbol Kind Type Properties
d var int …
(block1)
void setValue(int c){
value =c;
{ int d = c;
c = c +d;
myValue =c;
}
}
lookup(myValue)

27. HashTables
A hash table is a list in which each memberis
accessed through akey.
The key is used to determine where to store
the value in thetable.
The function that produces a locationfrom
the key is called the hashfunction.
For example, if it were a hash table ofstrings,
the hash function might compute the sum of
the ASCII values of the first 5 characters of
the string, modulo the size of thetable.

28. HashTables
The numerical value of the hashed keygives
the location of themember.
Thus, there is no need to search for the
member; the hashed key tells where itis
located.
For example, if the string were"return",
then the key would be (114 + 101 + 116 +
117 + 114) % 100 =62.
Thus, "return"would be located in position
62 of the hashtable.

29. Clashes andBuckets
Clearly, there is the possibility of a clash:two
members have the same hashedkey.
In that case, the hash table creates a list,
called a “bucket,” of those values in thetable
with that samelocation.
When that location comes up, the listis
searched.
However, it is generally a very short list,
especially if the table size has beenchosen
well.

30. Hash TableEfficiency
The two parameters that determinehow
efficiently the hash table performsare
The capacity of the table, i.e., the total amount of
memoryallocated.
The number of buckets, or equivalently, thesize
of abucket.
Clearly, the size of a bucket times the
number of buckets equals the capacity ofthe
table.

31. Hash TableEfficiency
For a given hash tablecapacity,
If there are too many buckets, then many buckets
will not be used, leading to spaceinefficiency.
If there are too few buckets, then there will be
many clashes, causing the searches to
degenerate into predominately sequential
searches, leading to timeinefficiency.

32. End of Chapter #13