编译原理与实践（中英双语版）课件 第1-5章 Introduction - Bottom-Up Parsing

编译原理与实践

CompilerPrincipleand

Implementation中英双语版1Chapter1IntroductionZhangJing,Yu

SiLiang

CollegeofComputerScience&TechnologyHarbinEngineeringUniversityCompilersCompilersarecomputerprogramsthattranslateonelanguagetoanother..SourceprogramTargetProgramCompilerSourceProgramTargetProgramFig1.1Acompiler图1.1一个编译器3Itsinputisaprogramwritteninitssourcelanguage.Usually,thesourcelanguageisahigh-levellanguage(C,C++,etc).Itproducesanequivalentprogramwritteninitstargetlanguage.Thetargetlanguageisobjectcode

(machinecode)forthetargetmachine.4Simpleexample:

Thesourceprogramofacompilerisasfollows.I:=I0+L*2(1.1)

Targetprogram:theoutputofcompilerisanequivalentmachinecodeofitssourceprogram.Itlookslikethese..

MOVFid3,R2(1.2)MULF#2.0,R2MOVFid2,R1ADDFR2,R1MOVFR1,id15Analysisofthesourceprogram

Generally,theanalysisofcompilerincludesLexicalAnalyzer,SyntaxAnalyzer,SemanticAnalyzer,IntermediateCodeGenerator,CodeOptimizerandCodeGenerator..

Inlexicalanalysis,charactersaregroupedintotokens;;

Syntaxanalyzerchangesagroupoftokenintogrammaticalphrases,itisoftencalledparsingtree;Insemanticanalyzer,grammaticalphrasesarecheckedbysemanticerrorsandtypeinformationareadded;;

6Theintermediatecodegeneratorisaprogramwhichiseasytoproduceprogramfromsemanticanalyzerandiseasytotranslateintothetargetprogram;;Codeoptimizationphaseattemptstoimprovetheintermediatecode;;Aintermediatecodeinstructionsareeachtranslatedintoasequenceofmachineinstructions,itisthetaskofcodegenerator..

ThephasesofcompilerareshownbyFig.1.2.

7Lexicalanalysis

Lexicalanalysisisalsocalledscanner.Itisaprogramwhichrecognizespatternsintext.Scannersmaybehandwrittenorbeautom-aticallygeneratedbyalexicalanalysisgeneratorfromdescriptionsofthepatternstoberecognized..Theexampleisanassignmentstatement:I:=I0+L*2

8

Lexicalanalyzercananalysisitintoagroupoftokens:“I”,“:=”,“I0”,“+”,“L”,“*”,“2”.Namely,theyaretheidentifier,theassignmentsymbol,theidentifier,theplus,theidentifier,themultiplicationandthedigital.

Note:Duringthelexicalanalysis,theblankswhichseparatethecharactersofthesetokenswouldnormallybeeliminated..

9

SyntaxAnalyzer

SyntaxAnalyzerisalsocalledparser.Itgroupstokensofthesourceprogramintogrammaticalphrases;Itisalsoaprogramwhichdeterminesifitsinputissyntacticallyvalidanddeterminesitsstructure..

Parsersmaybehandwrittenormaybeautomaticallygeneratedbyaparsergeneratorfromdescriptionsofvalidsyntacticalstructures.

10

Usually,thegrammaticalphrasesofthesourceprogramarerepresentedbyaparsingtree.Forexample:I:=I0+L*2

TheparsingtreeofitisshownbyFig.1.3.11Fromthisparsingtree,wecanseethegrammaticalphrasesincludeexpressionsandstatements.Thedefinitionofexpressionisasfollows::1.Anyanidentifierisanexpression,suchasI,L,I02.Anyadigitalisanexpression,suchas23.Ifexpression1andexpression2areexpressions,thenexpression1*expression2isanexpression,suchasL*2expression1+expression2isanexpression,suchasI0+L*2(expression1)isanexpression12Ontheotherhand,wecansimilarlydefinestatementrecursively.Thatis::Ifidentifier1isanidentifier,andexpression2isanexpression,thenidentifier1:=expression2

Ifexpression1isanexpressionand

expression2isanexpression,soWhile(expression1)dostatement2

If(expression1),thenstatement2

13Sometimes,wecancompresstheparsingtreeintosyntaxtree,wheretheoperatorsappearastheinteriornodes,andtheoperandsofanoperatoraretheoperator’schildren,showninFig.1.4.WeshalldiscussthisinmoredetailinChapter4..

14SemanticAnalyzer

Thesemanticanalysisanalyzestheparsingtreeforsemanticerrors,gathersinformationtypeandchecksinformationtype.Thesyntaxtreeisusedtoidentifyiftheoperatorsandoperandsarecorrect.Inaddition,manyprogramlanguagesneedtoreportandcorrectanerrortype,thisneedtostorethenameandtypeofvariablesandotherobjectsinasymboltable.Theinformationtypecanbecheckedbymeansofthesymboltable.Theoutputofthesemanticanalysisphaseisanannotatedparsingtree,i.e.addingthetypeofobjectsbasedonparsingtree,wenameitassemantictree.Thisphaseofsemanticanalysisisoftencombinedwiththeparser..15Attributegrammarsareusedtodescribethestaticsemanticsofaprogram.Forexample,supposewehavedeclaredallidentifiersasrealtypeshowninFig.1.5,anddigital2isaninteger.Firstly,semanticanalyzergathersandstoresthetypeinformationofallidentifiersanddigitalsinasymboltable;thenchecksthetypeofthem,itrevealsthat*multipliesareal(L)byaninteger(2);sothesemanticanalyzercreatesanewnode“real”;finally,itconvertsthedigital2intoarealtypeandbuildsasemantictree..

16IntermediateCodeGenerator

WhencompileranalysisreachesthephaseofIntermediateCodeGenerator,compilerhasanalyzedsourcelanguageintoaseriesoftokens,andbuiltaparseorsyntaxtreeandsemantictree,storedinformationtypeinsymboltableandgeneratedtheerrorinformation.Inordertoobtainmachinecodeofsourceprogram,somecompilersgenerateanintermediaterepresentation,it’saprogramforanabstractmachine.Thephaseofcreatingtheintermediaterepresentationiscalledintermediatecodegenerator.Thefunctionofintermediatecodegeneratorisforeasyproducingandtranslatingthesourceprogramintothetargetprogram..

17

Thereareseveralformsofintermediatecode,thetypicaloneis“three-addresscode”,whichissimilartotheassemblylanguage.Three-addresscodeisasequenceofinstructions;eachhavingatmostthreeparts.Weshallexplainthree-addresscodeandotherintermediateexactrepresentationinChapter7..

Thesourceprogramin(1.1)canbewritteninthree-addresscode:temp1:=real(2)(1.3)temp2:=L*temp1temp3:=I0+temp2I:=temp318CodeOptimizer

Intermediatecodeisnotafaster-runningcode,soacodeoptimizercanimproveit.ForexamplewecanchangetheIntermediatecode(1.3)intocodeoptimization(1.4).

temp1:=L*2(1.4)

I:=I0+temp1

Thismeansthatcodeoptimizercandecreasethenumberofinstructionsandincreasetherunningspeedofthetargetprogram.Therearemanytypeofoptimizers,thesearecoveredinChapter8.19CodeGenerator

Thefunctionofthisphaseistocreatetargetcode.Targetcodemeansmachinecodeorassemblycode.Thefeatureofmachinecodeisthatitneedsmemorylocationforeachofthevariablesusedbytheprogram,andregisteroftheassignmentofvariables.Thecodeof(1.4)mightbetranslatedintoaseriesofmachineinstructions,suchas

MOVFL,R2(1.5)MULF#2.0,R2MOVFI0,R1ADDFR2,R1MOVFR1,I20

Themachineinstructionsmean:.

(1)TheFinaboveinstructions(1.5)meansthatthedigitalisthetypeoffloatingpointnumber..

(2)ThefunctionofMOVistoputthecontentsoftheaddressLintoregister2..

(3)MULsignifiesmultiplicationofR2by2.0,andthensendstheresulttoR2.ADDpresentsaddingR2andR1together,andthenstorestheresultinR1..

(4)#means2.0isaconstant..

Chapter9givesadetaileddiscussionofcodegeneration.Intheabovephaseofcompiler,therearetwoimportantpartsincompiler,theyaresymboltableanderrortable,thedetailsareasfollows..21

Errorhandlers

Therearemanyerrorinformationfoundandneedtobecorrectedinthephaseofcompiler.Forexample,inlexicalphasesomecharacterscan’tbeformedintoanytokenofalanguage.Duringsyntaxphase,therearesomeerrorsthatdonotabidebyanysyntaxstructurerulesofalanguage.Insemanticphase,someerrorsappearinincorrecttypeonbothsidesofassignment.Forexample,ontheonehand,thetypeofvariableinassignmentisintegerandontheotherhand,theconstantisthetypeoffloat.It’srightinsyntacticstructure,butitisincorrectinsemanticmeaning.Soweneedtheerrorhandlersineveryphaseofcompiler.22

Symboltable

Aftertheanalysisoflexicalofcompiler,sourceprogramisturnedintotokensandispreparedforbeinganalyzedbynextphase.Thepointisthatthesetokensshouldbestoredinsomeplaceforuseatanytime.Wheretostorethesetokens??

Symboltableisadatastructureoradatabase.Ithastwofunctions,thefirstoneisthestoragefunction,itstorestheinformationoftoken,suchasthename,typeandothercharacterofidentifier;thesecondfunctionistocheckorretrievethisinformation..

23

Forexample,inthephaseofsemanticanalysisandintermediatecodegeneration,itneedstocheckthetypeofidentifierandtogenerateproperoperations..Inaddition,theactionsofstoringsomeinformationinsymboltableandcheckingtheinformationinsomephaseexistinallthephasesofcompiler.ItiscoveredindetailinChapter5..

24Conclusion

Thissectionfurtherdiscussessomecompilerconcepts.Itisnotnecessaryforallthecompilerstoconsistofallsixphase,somecompilersonlyhavethreephases.Inthisbook,wemainlyintroducethecommoncompilerstructure(sixphases)showninFig.1.6.Everyphaseofacompilerwillbediscussedindetailinthefollowingchapters..

25

Compilersarenotparticularlydifficultprogramstounderstandonceyouarefamiliarwiththestructureofacompilerinageneralway.Thepointisthatnotanyofthephasesofacompilerishardtounderstand;but,therearesomanyphasesthatyouneedtoabsorbandmakesenseofthem.Table1.1isthedescriptionofeachofthecompilerphases.

Table1.1Descriptionofcompilerphases 表1.1编译器组成阶段的说明2627Thepassofcompiler

Compilerisacomplexprogram.Whenasourceprogramiscompiled,itoftenneedsseveralpassestofinishallphasesofcompiler.Sowenamethedistinctchunkpass.Itisapartofthecompilationprocessanditcommunicateswithoneanotherviatemporaryfile.Thetypicalstructureisafour-passcompiler,itisshowninFig.1.6..

28

Thefirst

passispreprocessor.Itsfirsttaskistostripcommentsfromthesourcecode,suchas{,}orbegin,end.Secondtaskistohandlevarioushousekeepingtaskswithwhichyoudon’twanttoburdenthecompilerproper,forexample,thehousekeepingis#include<global.h>inthesourceprogramlanguageC.Thesecondpassistheheartofcompiler,itconsistoflexicalanalysis,parser,semanticanalyzer,andintermediatecodegenerator..

29

Theinputissourcelanguage,andoutputisintermediatelanguage.Thethirdpassistheoptimizer,whichimprovesthequalityoftheintermediatecode.Finally,thefourthpass,ittranslatestheoptimizercodeintorealassemblylanguageorsomeotherformofbinary,executablecode..30

Note:

Therearemanydifferentpassesofacompiler.Notallcompilershavefourpasses.Somehavetwopasses,othersgenerateassemblylanguageinthethirdpass,andsomecompileronlyhasonepass.Manycompilersdonotusepreprocessors,orhaveintermediatelanguage,butgeneratethemachinecodedirectly..31

Compilerexample1

Sofarwehavedescribedallthecompilerphasesandsometheoryknowledgeaboutit.But,whatisacompilerprogram?Howtobuildacompilerfromasimpleexpression?Wegivesomepartsofatypicalcompilerprogramandexplainthecompilerphasethatconsistsoflexicalanalysis(Lex),parseranalyzer(Yacc)andcodegeneration(ANSICcodegenerator).

LexandYacccangenerateprogramfragmentsthatsolvethetaskofreadingthesourceprogramanddiscoveringitsstructure..

32

Lex

iswellsuitedforsegmentinginputinpreparationforaparsingroutineandhelpswriteprogramswhosecontrolflowisdirectedbyinstancesofregularexpressionsintheinputstream.Lextablemadeupofregularexpressionsandcorrespondingprogramfragmentsistranslatedtoaprogramthatreadsaninputstream,copyittoanoutputstreamandpartitiontheinputintostringsthatmatchthegivenexpressions.What’smore,Lexcangeneratetherecognitionoftheexpressionsandstringstocorrespondingprogramfragmentsthatareexecuted.33TheYaccspecifiesthestructuresofhisinputandrecognizeeachstructure.Yaccchangessuchaspecificationintoasubroutinethathandlestheinputprocess;usually,itusesthesubroutinetomakeitconvenientandappropriatetohandletheflowofcontrol..Note:ThefollowingcompilercodeisprovidedbyJeremyBennettandhehaspermittedtoaddhiscodetothisbook.Wesincerelythankhimforhiskindsupport.Ifyouwishtoreadthecompletecompilersourcecode,pleaseaccesstheJeremyBennett’swebsiteat/..

34Thelexicalanalysis

Letusfirstdiscusstheconceptoftoken.Tokenisaninputsymbol,whichisusedbothfordigitalsandidentifiers;sothetokensaremadeupofasequenceofcharactersintherange‘0-9’,‘a-z’,‘A-Z’.Thefollowinglexicalprogramisonlyapartofthewholelexicalanalysis.Itstartsfrominputsystem,gettingcharactersfromstandardinput,andthenisolatingtokens.Thedetailedlexicalanalysisisasfollows..

35Itstartsfromthedefinitionofsyntaxanalyzer,whichistoobtainthedefinitionoftypectype.handoftheroutineparseprogram..scanner.c(LEXscannerforthevccompiler)36

373839404142TheParser

Intheparserphasenocodeisgenerated,itjustanalyzetheinputtokens,i.e.parsetheinput.Eachsubroutinecorrespondstotheleftofonesentenceandintheoriginalgrammarthatbearsthesamename,anditmustmatchthegrammarexactly.ThefollowingparserpartincludestheroutinetomakeanIFstatement,aWHILEloopandexpressionnode.parser.c(YACCparserforthevccompiler)43444546Codegeneration

Movingontothecodegeneration,thegoalofthisphaseistobuildacompilergiventhattheprogramsinthephaseofparserhavebeenstrictlyrecognizedwithoutanyerror,heretheerrormeansthattheinputisanillegalsentenceinthegrammar.However,beforegeneratingcode,firstyouneedtobuildthebar-bonesrecognizer..

Forexample:

a:=bopc47

Weneedcreatesometemporaryvariablesandmaintaininternallybythecompiler.ThestepofgeneratingCodeisasfollows.First,createamechanismforallocatingtemporaries.Infact,thetemporariesshouldberecycled,thatistheyshouldbereusedaftertheyarenolongerneededinthecurrentsubexpression.Second,determinethenameofthetemporarythatusesargumentsandreturnvalues.So,thissectionofcodegeneratorconsistsofgeneratingcodeforabinaryoperator,generatingcodeforacopyinstruction,generatingcodeforaninstructionwhichloadstheargumentintoaregister,andthenwriteitontothenewstackframe,includingthestandardcallsequenceandthestandardreturnsequence..

48cg.c(ANSICcodegeneratorforthevccompiler)495051525354Compilerexample2forusingFlextoolThestepsofrunningtheLextoolare:1.DownloadthesourcecodeofFlextoolfromthewebsitebelow.

/gnuwin32/flex-2.5.4a-1-in.zip55Someotherwebsitesofcompilersourcecodeareshownbelow/object/cg_compiler_code.html/dox/scanner_8c-source.html.au/~comp380/calculator/scanner.c/dox/scanner_8c-source.html/resume/code/sqlwork-5.0/scanner.c.html/math/faculty/eric/cs473/pascal/phase1/scanner.chttp://bt-win2k-server.fh-regensburg.de/jobst/co/Modellcompiler/C/SCANNER.C.htmlhttp://clri6f.gsi.de/gnu/gnuplot-3.5/scanner.c/lex_yacc_page//lexparse.html562.EntertheDOSoperatingsystem.(startmenu→accessory→commandprompt)3.Createatextfile:lex.txt,thetextfilecontentareasbelow574.Usingthecommandofrename:renamelex.txt

lex.l5.UsethecompiledcommandtoproducetheCcompiledfilelexyy.c:flexlex.l

6.UsethecommandofTCtocompilelexyy.cintolexyy.exe:tc

lexyy.c7.PressthekeyF9toproducefileoflexyy.exe8.Doubleclickonthefilelexyy.exetoruntheflextool.TheresultofLEXscannertoolisshownbyFig1.7.58Chapter2

GrammarandFormalLanguage

Thegoalofthischapteristohelpreaderstoreviewsomebasicknowledgeofmathematicsthatisrelatedwiththetheoryofcompiler,andunderstandthemathematicssymboliclanguage—formallanguage.Inspecific,weshalltalkabouttheconceptsofstring,grammar,parsertree,formallanguageandsoon.Alltheconceptsarethebasicknowledgeforreaderandwillbenefitthemtogothroughthefollowingchapters.

60String

1.Alphabet

–finitecharacterset,anditisnon-emptyset.Forexample,A=｛a,b,c,…,z｝,B=｛0,1｝,AandBarealphabets.2.StringStringisasequenceofcharacters,emptystringcanberepresentedbyε,Usuallysmalllettersrepresentstring.

61Forexample,IfthereisalphabetA=｛a,b,c｝,Thecharactersofitarea,b,c.Thestringsarea,b,c,ab,ac,aa,abc,…AlphabetB=｛0，1｝,thecharacterscorrespondtoitare0,1Thestringsare0，1，00，01，10，11，000，…，01000，…Note:Ifthecharacterorderisnotsame,thestringisdifferentaswell.Forexample,string“ab”and“ba”arenotsame.001and010aredifferentstring..623.StringLengthThelengthofstringisthenumberofcharacters.Thestringisx,thelengthofstringis|x|.TakealphabetBforexample,|01|=2，|000|=3，|01000|=5,Thelengthofnullstring,|ε|=04.ConnectionofstringTherearestringsxandy,writedownyafterx,namely,“xy”,wecall“xy”astheconnectionofstringxandy..Iftherearex=abc

，y=de,thenxy=abcde，yx=deabcNote:εx=xε=x635.PowerofstringIfxisstring,thenx2=xxx3=xxx …… xn=xx…x=xn-1x=xxn-1xnisthenpowerofxx0=εThereisx=aTb,sothepowerofxandlengthofitareasfollows.x0=ε |x0|=0x1=aTb |x1|=3x2=aTbaTb |x2|=6x3=aTbaTbaTb |x3|=9646.Headandtailofstringz=xyisstring,theheadofzisx,thetailofzisy.ify≠ε,wecallthexistrueheadofz.Similarly,ifx≠ε,yisthetailofzanditistruetail..Thereisstringofu=abc,sotheheadsofuareε、a、ab、abc,trueheadofitareε、a、ab,thetailsofuareε、c、bc、abc,truetailsofitareε、c、bc..657.ProductofstringAandBAandBarestrings,theproductofthemisAB=｛xy|(x∈A)∧(y∈B)｝

ThismeansthatABisthesetwherexbelongstoAandybelongstoB.

TherearesetA=｛a,b｝,B=｛0,1｝,so,AB=｛a0,a1,b0,b1｝Note:

｛ε｝A=A｛ε｝=A668.PowersetofstringAissetofstring,thepowerofthesetAisA0=｛ε｝

A1=A …… An=AA…A=AAn-1=An-1AThereisA=｛a,b｝,thenA0=｛ε｝

A2=｛a,b｝｛a,b｝=｛aa,ab,ba,bb｝

A3=｛aaa,aab,aba,abb,baa,bab,bba,bbb｝

LengthofA2is4(namely,22=4),whilelengthofA3is8(namely,23=8)679.Positiveclosureofstringset

ThepositiveclosureofstringsetcanbewrittenasA+=A1∪A2∪…∪An∪…

IfA=｛a,b｝,thenA+=｛a,b｝∪｛aa,ab,ba,bb｝∪…=｛a,b,aa,ab,ba,bb,aaa,…,bbb,…｝

10.ClosureofstringsetTheclosureofstringsetAiswrittenasA*A*=A0∪A+=｛ε｝∪A+IfA=｛a,b｝,soA*=｛ε,a,b,aa,ab,ba,bb,aaa,…,bbb,…｝68GrammarandFormallanguage

Weknowthatcompilingprocedureincludesscanner,parser,semanticanalyzerandsoon.Howdotheywork?Whatistheprincipleofthem?Isthereanyrulebetweenthem?Thereisaveryimportantruleorgrammarthathelpstoanalyzetheprocedureofcompiling,thatis,formallanguage.Formallanguageiscompletelydescribedandrigidlygovernedbyrules.Thissectionwewillintroducethebasicconceptsofrule,grammarandlanguage..

691．Rule

Ruleisangroup（U，x）,oftenitiswrittenasU::=x（orU→x）

.WhileUistherule’sleft,andstringx(notnull)istherule’sright,that’stosay,therule’sleftisdefinedorformedbytheright.Inaddition,leftandrightsideofruleareconnectedby“::=”or“→”,actually,theruleiscalledBackusNaurForm（BNF）..Thefollowingareallrules.S::=0S1 S::=01 U::=TbT::=a702.GrammarG［Z］

Grammar[Z]isasetwhichisnotnullandisfinite.Zistheidentifiedsymbol(orthestartsymbol)anditmustappearontheleftofrule,allthecharactersinsetwhichappearinrulesarecalledvocabularyofV..71Example2.1.G［S］=｛S::=0S1，S::=01｝

Thisgrammarincludestworules,thevocabularyV=｛S,0,1｝Example2.2.G［U］=｛U::=Tb，T::=a｝

So,V=｛U,T,a,b｝，theidentifiedsymbolinthegrammarisU.Example2.3.G[Z]={Z::=D,Z::=ZD,D::=0|1|…|9}V={Z,D,0,1,…9}，thestartsymbolinthegrammarisZ.72Note:RulesD::=0|1|…|9aresamewithD::=0D::=1D::=2…

D::=9“|”abovemeansachoiceamongalternatives.733.NonterminalsymbolThesymbolappearingonleftofruleiscallednonterminalsymbol,thesetconsistingofallthenonterminalsymbolsisVN.Inexamples2.1,2.2and2.3,theirVNareasfollowsVN=｛S｝

VN=｛U,T｝

VN=｛Z,D｝744.Terminalsymbol

ThesetofcharactersthatdoesnotbelongtoVNareterminalsymbol,anditiswrittenasVT,foraboveexamples,VTareasfollows,VT=｛0,1｝

VT=｛a,b｝

VT=｛0,1,…,9｝

Note:VocabularyVisdefinedas:V=VN∪VT755.Thedefinition

of

grammarAgrammarisafinitenonemptysetofrules,anditisdefinedasa4-tuple:G=（VN,VT,P,S）

While,VNisnonterminalsymbol,VTisterminalsymbol，Pissetofrules，Sisthestartsymbol.

Example2.3canbewrittenas:G[Z]=（VN,VT,P,Z）

VN=｛Z,D｝

VT=｛0,1,…9｝

P:Z::=DZ::=ZDD::=0|1|…|976Tillnow,wehavelearntwhatgrammarisandhowtorepresentgrammar,nextwewanttounderstandorjudgeifastringistheresultofagrammar..

Takethestring“12”forexampletojudgeifitisthestringofexample2.3..

Z⇒ZD⇒DD⇒1D⇒12So