编译原理与实践（中英双语版）课件 Chapter 6 Symbol Table Manager and Type Checking

Chapter6

SymbolTableManager

andTypeChecking

somesymbolsmustbecollectedandbeputtogetherintotables—SymbolTable.Therearetwofunctionsinsymboltable,thefirstoneistohelpcheckifthesemanticiscorrect,thesecondoneistoassistgeneratingthecode.Tosumup,thischapterwouldintroducethefunctions,content,structureandoperationofsymboltable.

26.1TheFunctionsofSymbolTables

Thefunctionsofsymboltableare:

（1）

Storeinformation

（2）TypesChecking

（3）DataAddress3Storeinformation:

Beforestoreinformation,wefirstlyshoulddividedthedataintodifferenttypes,thenputthemintothecorrespondedtables.Sometimesinformationisstoredintableduringlexicalanalysis,sometimesitisdoneinsemanticanalysis..

Ifthedataisanidentifier,itwouldbestoredinanidentifiertable，elseifthedataisaconstant,itwillbeputintoaconstanttable.

4TypesCheckingAcompilerusesasymboltabletokeeptrackofthetypeandbindinginformationaboutnames.Thesymboltableissearchedeverytimebyanamethatisencounteredinthesourcetext.Ifanewnameornewinformationaboutanexistingnameisdiscovered,thetableischanged.

5DataAddress:Whenadatawasstored,thedata’saddressinthetablewasalsorecordedasanattributeofthetable.Intheperiodofcodegenerationincompiler,thedataaddresscanbeobtainedfromthesymboltableandcanbeuseddirectly..

66.2TheAttributeofSymbolTable

Symboltableiscreatedaccordingtosymbol’sname,sothekeywordofthesymboltableissymbol’sname.Exceptnameattribute,therearealsosixattributesofasymbolinsymboltableusingforsemanticchecking..

7Thesixattributesofasymbolasfollow:AttributeofkindAttributeofdimensionorsizeAttributeofparameterAttributeofaddressAttributeoflevelinprogramAttributeoflinepositioninsourceprogram8AttributeofkindKindcandescribethecharacteristicsofasymbol.Everysymbolhasitsowntype,suchasconstant,variableandprocedure..AttributeofdimensionorsizeIfanidentifierisanameofanarray,thenweshouldstorethedimensionandboundaryofidentifiervalueasanattributeofit..

9Attributeofparameter

Ifanidentifierisanameofaprocedure,theparametersoftheprocedureshouldberecordedasanattribute..

AttributeofaddressInsourceprogram,anidentifieroraconstantareoftenrelatedwithaunitaddresstoaccomplishsomeoperation.Sotheaddressesofthemareputinsymboltableasanattribute..

10AttributeoflevelinprogramSymbolinprogramorsubprogram,thelevelofitspositioninprogramshouldbewrittenasanattributeinsymboltable.Insomesourcelanguages,identifierscanhavesamenameindifferentlevelofprogram,soattributeoflevelinprogramcouldhelprecognizethem..AttributeoflinepositioninsourceprogramSometimesthelinepositionofsymbolinsourceprogramisneededtobestoredasanattributeinsymboltableinordertoobtainthecorrectsemanticchecking..11AttributeofconstantvalueIfthesymbolisaconstant,thenthevalueofitshouldbeenstoredasavalueattributeinsymboltable..

Attributesabovearenotalltheattributesasymboltablehas,somesymbolsusedforspecialmayhasparticularattributes.Tosumup,thefunctionofsymboltableisforcheckingupifthesemanticinsourceprogramiscorrect.12Example6.1Thedefinitionofconstantsis:Constpi=3.14r=10Itssymboltableis:NameKindValuepireal3.14rint10NamepirKindrealint

Value3.141013Example6.2

Thedefinitionofvariablesis:Vari,j:integer;x,y:real;ItssymboltableisNameKindAddressiint

100jint102xreal104yreal10814Example6.3

Thedefinitionofprocedureis:ProcedureMax；Varh,l:integer;2insizeattributemeanstherearetwoparametersintheprocedureNameKindLevelAddressSizeMaxHlProcedureintint0113083003062156.3TheDesignofSymbolTableThissection,webegintodiscussthestorageandthescopeofsymbolsinvariouspartsofaprogram.Thenwestudyhowtodesignthestructureofasymbolattributeinlocalsymboltable..

16Inordertoobtainhighrunningefficientandsavethestorageofsymboltable,weshouldtakeintoaccountalotofthings.Firstly,whatarethefeaturesofprogramlanguage?Howmanypartsareinprogram?Whichoneshouldbecheckedbysemantic?Secondly,weshoulddiscusstherunningenvironment,,

17forexample,targetmachineperformance,whatkindoftargetcodeitwillproduce.Thirdly,weshouldthinkoftheoperationsystemthatofferthewayofstorageandmanagement.Finally,howmanypassesandhowmanytablesaccordingtothepassesweshouldpayattentionto.Tosumup,ifwewanttodesignasymboltable,weshouldtakeallthoseelementsintoaccountinordertobuildareasonablesymboltable..

18Therearetwostepstobuildthesymboltable:(1)Buildtheattributeofsymboltable.(2)Designtheorganizationofsymboltable.Thefirstonewewilldiscussinthissection,thesecondonewouldbeintroducedinnextsection.Inthepartofattributeofsymboltable,wemainlyintroducetheattributeofname,attributeoftypeandtheidentifierofarraytype.

1920(1)Theattributeofname

Therearethreewaystostoreidentifier’snameinsymboltable.thefirstwayisshownbyTable6.1,itmeansweputthenamewithalllettersinnameattribute,thenamelengthis10thatisadefinite.ThesecondwayisexpressedinFig6.1(a),lettersofnamearestoredinchaintable,namely,innameattributetherearelengthofthenameandthenameaddressofconnecttable.21ThethirdwayisdenotedbyFig.6.1(b),youcanonlyseenameaddressinnameattribute,thenamelengthandnamelettersarewritteninitschaintable..

Ifalengthofidentifier’snameis2bites,usingsymboltableinfirstwaytostoreitneeds8bites,ontheotherhandstoringitbysymboltableinsecondorthirdwaywouldsavethespace,butitspendsalotofsearchingtime.Totally,usingwhichwayisuptoyou..

22(2)TheattributeoftypeTherearealsothreewaystorepresentthetypeattribute..

Thefirstwayisputtingthetypedirectlyintothetypeattribute,showninTable6.1..

Thesecondwayiscreatinga4bitestablethatisshowninFig.6.2,thefirstbiteinTable6.2is1,thetypeisinteger,thesecondbiteis1,itisreal,thethirdbite1meanslogictypeandfourthonerepresentcharactertype..

ThethirdwaytostorethetypeisshowninFig6.3,inthisway,thereareonlythreebitesthatcanrepresentthefourbitestypebythesecondway.23

24

25(3)ArraytypeinsymboltableDifferentidentifierneeddifferentattributetostoreitsinformation.forexample,anidentifierofarraytypeneedstobedescribeditsdimension,scopeetc.,aprocedureidentifiershouldsavethenumberofitsparameters,theirtypeiftheyarerecursive.Weoftenusechaintabletostoresomespecialattributesandthechaintableaddresswouldbeasanattributeinsymboltable..266.4TheStructureofSymbolTable

6.4.1.Theoperationofsymboltable

Theoperationofsymboltableincludessearch,find,insert,deletingandupdate.Asastructuredefinitionprogram,therearetwowaystodotheoperation:

27(1)Ifasymboltableisunordered,theoperationofinsertissimple.Becauseitdoesnotneedtofindadefiniteinsertposition,butitshouldbesearchedinthesymboltabletobesureifthereisnosamesymbol,therunningtimeofsearchisnotlittle..

28(2)Ifasymboltableisordered,weshouldfirstsearchtheinsertpositioninsymboltable,secondlytodotheinsertoperation,soitneedsdoubletimetodotheinsertoperationthandoitinfirstway..

29Asanostructuredefinitionprogram,anysymbolisconsideredtobethefirsttimetoinsertanditmustbesearchedbyallofsymboltabletomakesureifitisreallyusedfirstly.Onlywhenthereisnosamesymbolinsymboltable,theinsertoperationcouldbedone..

30Asasubprogram,itisallowedsameidentifierindifferentsubprogram,butthereisnomeaningifwedon’tdefinewhichsubprogramtheidentifierbelongsto.Itneedstwomoreoperationexceptinsertandsearchoperations:createchainsymboltableinsubprogramentranceanddeletingchainsymboltableinthesubprogramexit..

31(1)Intheentranceofsubprogram,weshouldbuildachainsymboltabletostoresomeidentifierinformationfor:.

forexample,createchainsymboltable1forsubprogram1,buildchainsymboltable2forsubprogram2,……setupchainsymboltablenforsubprogramn,andsoon.Whensearchanidentifierinsubprogramn,weshouldsearchitbeginfromchaintablen,ifthereisnothesymbolinit,searchitinchaintablen-1untillchaintable1

(2)Insubprogramexit,thechainsymboltableshouldbedeletedtoreleasethespace..326.4.2.ThestructureofsymboltableWhichkindofsymbolstructureyouwilldesignorchoosemostlydependsonstoringefficiencyandoperationspeed.Therearemanysymbolstructuretables,suchasunorderedsymboltable,orderedsymboltable,stacksymboltable,treesymboltableandhashsymboltable.Nextwewillintroducethreetypicalsymbolstructures:unorderedsymboltable,orderedsymboltableandstacksymboltable..

331Unorderedsymboltable

Unorderedsymboltableisbuiltaccordingtotheorderofidentifiersappearing.unorderedsymboltableissuitabletolittlescalesymboltable.Table6.1isakindofunorderedsymboltable..

342Orderedsymboltable

Ifidentifiersareorderedbyitsfirstletterindictionary,thesymboltableisorderedsymboltable.Therearethreestepstobuildorderedsymboltable.

.

Step1.Dothesearchoperationinordertofinditspositioninsymboltable.Step2.Movesomeidentifiers’nameandattributesinsymboltable..

Step3.Insertidentifiersatthepositioninsymboltable.353．Stacksymboltable

arrayorprocedureidentifiersoftenusechaintabletostoretheirspecialattributes.thechaintableaddresswouldbeasanattributeinsymboltable..

Example6.2canexplainit.36Example6.4

Aprogramwithprocedure.37Thestacksymboltableoftheprogramisbelow.38Duringcompilingtherearethreeoperationsinstacksymboltable,theyareinsert,searchandrelease.Theoperationofinsert:

Whenmainprogram(level0)iscompiled,identifiersandconstantsarepushedintostackbytheirappearingorder.Address1meansstackstartaddressanditisalsothebottomaddressofthisstack,address4representstopaddressoflevel0.Similarly,startaddressoflevel1is5,startaddressoflevel2is8,andthetopaddressofstackis10..39Theoperationofsearch:Searchinganidentifierisbeginningfromtheorderofstacktopaddress,level2,level1andlevel0.Iftheidentifierisnotfounduntilbottomaddressofthisstack,thesemanticcheckisnotcorrectandshouldreturnerrorinformation.Theoperationofrelease:Whenretreatfromaprocedure,theidentifiersoftheprocedureshouldbereleasedandthetopaddressofstackwillchange.Forinstance,procedureqreleasesfromthestack,thetopaddressofthestackischangefrom10to7.406.5Typechecking

SemanticChecksincludestaticanddynamiccheck..

Staticmeansthatitdoescheckingduringcompilation,,

Dynamiccheckisdoneduringrun-time.

41Typecheckingisoneofthesestaticcheckingoperations.Somesystemsalsousedynamictypechecking..Aprogramminglanguageisstrongly-typed,ifeveryprogramitscompileracceptswillexecutewithouttype..

errors.Inpractice,so