Symbol table in compiler Design

Symbol table in compiler Design

1. Symbol Table

2. Symbol Table
•Whennamesarefound,theywillbeenteredintoasymbol
table,whichwillholdallrelevantinformationabout
identifiers,functionnames,objects,classes,interfaces,etc.
•Thisinformationwillbeusedlaterbythesemanticanalyzer
andthecodegenerator.
Lexical
Analyzer
Semantic
Analyzer
Code
Generator
Symbol
Table
Syntax
Analyzer

3. Usage of Symbol table by Various Phases of Compiler
•LexicalAnalysis:Createsnewentriesinthetableabouttoken.
•SyntaxAnalysis:Addsinformationregardingattributetype,scope,
dimension,lineofreference,etcinthetable.
•SemanticAnalysis:Usesavailableinformationinthetabletocheckfor
semanticsi.e.toverifythatexpressionsandassignmentsaresemantically
correct(typechecking)andupdateitaccordingly.
•IntermediateCodegeneration:Referssymboltableforknowinghowmuch
memoryandwhattypeisallocatedandtablehelpsinaddingtemporary
variableinformation.
•CodeOptimization:Usesinformationpresentinsymboltableformachine
dependentoptimization.
•TargetCodegeneration:Generatescodebyusingaddressinformationof
identifierpresentinthetable.

4. Symbol table
•Symboltable:Adatastructureusedbyacompilertokeeptrackof
semanticsofnames.
–Determinewhetherthevariableisdefinedalreadyornot.
–Determinethescope.
•Theeffectivecontextwhereanameisvalid.
–Whereitisstored:storageaddress.
–Typecheckingforsemanticcorrectnessdetermination.
•Operations:
–Find/Lookup/Search:Accesstheinformationassociatedwithgiven
name.
–Insert:addanameintothetable.
–Delete:removeanamewhenitsscopeisclosed.

5. 5
Symbol Table
•Compilerusessymboltabletokeeptrackofscope(block)andbindinginformation
aboutnames
•symboltableischanged(updated)everytime
–ifanewnameisdiscovered
–ifnewinformationaboutanexistingnameisdiscovered
•Symboltablemusthavemechanismto:
–addnewentries
–findexistinginformationefficiently
•Twocommonmechanism:
–linearlists,simpletoimplement,poorperformance
–hashtables,greaterprogramming,goodperformance
•Compilershouldbeabletogrowsymboltabledynamically
•Ifsizeisfixed,itmustbelargeenoughforthelargestprogram

6. Symbol table Information
Symboltablestores:
•Foreachtypename,itstypedefinition(eg.fortheCtype
declarationtypedefint*mytype,itmapsthenamemytypetoadata
structurethatrepresentsthetypeint*).
•Foreachvariablename,itstype.Ifthevariableisanarray,italsostores
dimensioninformation.Itmayalsostorestorageclass,offsetinactivation
recordetc.
•Foreachconstantname,itstypeandvalue.
•Foreachfunctionandprocedure,itsformalparameterlistanditsoutput
type.Eachformalparametermusthavename,type,typeofpassing(by-
referenceorby-value),etc.

7. Symbol table

8. •VariableName:
–Mustbepresenttoletotherphasesknowwhichisaparticularvariable
–Majorissueisvariabilityoflengthofname
–Twopopularapproaches
•Tosetafixedmaximumlengthforvariablename
•Tokeeponlyadescriptorinthevariablenamefieldandkeepthe
nameingeneralstringareareferencedbythisdescriptor
•Firstapproachgivesquicktableaccesswhiletheothersupportsefficient
storageofvariablenames
•Firstapproachisinefficientinshortnamedvariableswhilesecondhasslow
tableaccessduetoreferencing

10. Symbol Table Organization for Block Structured
Languages

11. Symbol Table Organization for Non
Block Structured Languages

12. Four Structures of Non Block Structured Languages
•Unordered list: (linked list/array)
–for a very small set of variables;
–coding is easy, but performance is bad for large number of variables.
•Ordered linear list:
–use binary search on arrays;
–insertion and deletion are expensive;
–coding is relatively easy.
•Binary search tree:
–O(log n) time per operation (search, insert or delete) for n variables;
–coding is relatively difficult.
•Hash table:
–most commonly used;
–very efficient provided the memory space is adequately larger than the
number of variables;
–performance maybe bad if unlucky or the table is saturated;
–coding is not too difficult.

15. Hash Table Efficiency
•For a given hash table capacity,
–If there are too many buckets, then many buckets will
not be used, leading to space inefficiency.
–If there are too few buckets, then there will be many
clashes, causing the searches to degenerate into
predominately sequential searches, leading to time
inefficiency.

19. Symbol tables in block-structured languages
Symboltablesinblock-structuredlanguages:
–1.manysmallsymboltables
–2.oneglobalsymboltable
1.manysmalltables(StackbasedImplementation)
–onesymboltableperscope.
–useastackoftables.
–Thesymboltableforthecurrentscopeisontopofthestack.
–Thesymboltablesforotherenclosingscopesareplacedunderthecurrent
one.
–Pushanewtablewhenanewscopeisentered.
–Popasymboltablewhenascopeisclosed.

20. Example
Multiple symbol tables in one stack
H:int
A:int
L:int
x:real
y:real
:
symbol table
stack
{
intH,A,L;
{
real x,y;
:
:
}
{
char A,C,M;
print(M);
H + A ..... ;
X + L ...... ;
}
}
symbol table

21. Example
Multiple symbol tables in one stack
H:int
A:int
L:int
symbol table
stack
{
intH,A,L;
{
real x,y;
:
:
}
{
char A,C,M;
print(M);
H + A ..... ;
X + L ...... ;
}
} Secondscope is
completed. So Pop
(remove) the symbol
table of x,y

22. Example
H:int
A:int
L:int
A:char
C:char
M:char
:
symbol table
stack
{
intH,A,L;
{
real x,y;
:
:
}
{
char A,C,M;
print(M);
H + A ..... ;
X + L ...... ;
}
}
This symbol table in inserted
after popping a symbol table
consisting of x,y
symbol table

23. many small tables
•Tosearchforaname,wecheckthesymboltablesonthestackfromtopto
bottom.
•Wemayneedtosearchmultipletables.
E.g.Aglobalnameisdefinedinthebottom-mostsymboltable.
•Spacemaybewastedifafixed-sizedhashtableisusedto
implementsymboltables.
-hashtabletoobig–wastethememoryspace
-hashtabletoosmall--collisions

24. 2. one global table
One Symbol Table with chaining
•Allnamesareinthesingleglobaltable.
•Whataboutthesamenameisdeclaredseveraltimes?
•Eachnameisgivenascopenumber.
•<name,scopenumber>shouldbeuniqueinthetable.
•Easytosearchaname.
•Newnamesareplacedatthefrontoflists.
•Tocloseascope,weneedtoremoveallentriesdefinedinthat
scope.

25. Example
Hash based Chaining
{
intH,A,L;
{
float x,y,H;
:
:
}
{
char A,C,M;
}
}
}
Scope
number
1
2
3
Scope
number
1
2
3

26. One Symbol Table with chaining
•Binary search tree with chaining.
•Use a doubly linked list to chain all entries with the same name.

28. Reference
•A.V. Aho, M.S. Lam, R. Sethi, J. D. Ullman,
Compilers Principles, Techniques and Tools,
Pearson Edition, 2013.
P. Kuppusamy -Lexical Analyzer