Compilers: Principles, Techniques, and Tools

1 CompilersSecond EditionPrinciples, Techniques, & ToolsThis page intentionally left blank CompilersSecond EditionPrinciples, Techniques, & ToolsAlfred V. AhoColumbia UniversityMonica S. LamStanford UniversityRavi SethiAvayaJeffrey D. UllmanStanford UniversityPublisher Greg Tobin Executive Editor Michael Hirsch Acquisitions Editor Matt Goldstein Project Editor Katherine Harutunian Associate Managing Editor Jeffrey Holcomb Cover Designer Joyce Cosentino Wells Digital Assets Manager Marianne Groth Media Producer Bethany Tidd Senior Marketing Manager Michelle Brown Marketing Assistant Sarah Milmore Senior Author Support/ Technology Specialist Joe Vetere Senior Manufacturing Buyer Carol Melville Cover Image Scott Ullman of Strange Tonic Productions ( )Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks.

2 Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps. This interior of this book was composed in of Congress Cataloging-in-Publication Data Compilers : principles, techniques, and Tools / Alfred V. Aho .. [et al.]. -- 2nd ed. p. cm. Rev. ed. of: Compilers, principles, techniques, and Tools / Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. 1986. ISBN 0-321-48681-1 (alk. paper) 1. Compilers (Computer programs) I. Aho, Alfred V. II. Aho, Alfred V. Compilers, principles, techniques, and Tools . 2007 '53--dc22 2006024333 Copyright 2007 Pearson Education, Inc. All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording, or otherwise, without the prior written permission of the publisher. Printed in the United States of America.

3 For information on obtaining permission for use of material in this work, please submit a written request to Pearson Education, Inc., Rights and Contracts Department, 75 Arlington Street, Suite 300, Boston, MA 02116, fax your request to 617-848-7047, or e-mail at 1 2 3 4 5 6 7 8 9 10 CW 10 09 08 07 06 PrefaceInthetimesincethe1986editionofthi sbook,theworldofcompilerdesignhaschanged signi , ndbugsinsoftware,andmostimportantly, \front-end"technology|grammars,regularex pressions,parsers,andsyntax-directedtran slators| , ,orevenmaintain, ,theory, , rsthalfinanundergraduatecourseandtheseco ndhalfofthebook|stressingcodeoptimizatio n| , ,regularexpressions, nite-statemachines, ,top-down(recursive-descent,LL)andbottom -up(LRanditsvariants).Chapter5introduces theprincipalideasinsyntax-directedde , ,generationofcodefromexpressionsandbasic blocks, ,including owgraphs,data- owframeworks, , ,aliasing,anddata- ,Harvard, ,asenior/ rst-yeargraduatecourseonprogram-minglang uagesandtranslatorshasbeenregularlyo eredusingmaterialfromthe ,musicsynthesis,com-putergraphics,gaming , ,Lex,andYaccandthesyntax-directedtransla tiontechniquesdiscussedinchapterstwoand , ,aone-quarterintroductorycoursecoversrou ghlythemate-rialinChapters1through8, , ,Java-basedsystemcalledJoeqforimplementi ngdata- \computer-sciencesophistication,"includi ngatleastasecondcourseonprogramming, , ,orstudentsnotenrolledinaclassmayenrolli nan\omnibusclass"thatallowsthemtodotheho meworksasatutorial(withoutaninstructor-c reatedclass).

4 Gradiancequestionslooklikeordinaryquesti ons, ,youareallowedtotryagain, nderrataaswelearnofthem, eringofcompiler-relatedcoursesasweteacht hem,includinghomeworks,solutions, :viiiPREFACED omenicoBianculli,PeterBosch,MarcioBuss,M arcEaddy,StephenEdwards,VibhavGarg,KimHa zelwood,GauravKc,WeiLi,MikeSmith,ArtStam ness,KrystaSvore,OlivierTardieu, , ,Monicawouldliketothankhercolleaguesonth eSUIFcom-pilerteamforan18-yearlessononco mpiling:GeraldAigner,DzintarsAvots,Saman Amarasinghe,JenniferAnderson,MichaelCarb in,GeraldCheong,AmerDiwan,RobertFrench,A nwarGhuloum,MaryHall,JohnHennessy,DavidH eine,Shih-WeiLiao,AmyLim,BenjaminLivshit s,MichaelMartin,DrorMaydan,ToddMowry,Bri anMurphy,Je reyOplinger,KarenPieper,Mar-tinRinard,Ol atunjiRuwase,ConstantineSapuntzakis,Patr ickSathyanathan,MichaelSmith,StevenTjian g,Chau-WenTseng,ChristopherUnkel,JohnWha ley,RobertWilson,ChristopherWilson, , , , ,StanfordCAJune, ,Patterns, ' ' , rstpos, (1) (0) (1) (1) (1) \Dangling-Else" ' xSDT' ' ' 'sforL-AttributedDe ' ' ' ' ,Continue-, ' neandNona (SOR)

5 ' erOver ' ' ' ' , ,beforeaprogramcanberun,it , ,machinear-chitecture,languagetheory,alg orithms, ,weintroducethedi erentformsoflanguagetranslators,giveahig hleveloverviewofthestructureofatypicalco mpiler, ,acompilerisaprogramthatcanreadaprogrami nonelan-guage|thesourcelanguage|andtrans lateitintoanequivalentprograminanotherla nguage|thetargetlanguage; :AcompilerIfthetargetprogramisanexecutab lemachine-languageprogram,itcanthenbecal ledbytheusertoprocessinputsandproduceout puts; ,aninterpreterappearstodirectlyexecuteth eoperationsspeci edinthesourceprogramoninputssuppliedbyth euser, ,however,canusuallygivebettererrordiagno sticsthanacompiler, :Javalanguageprocessorscombinecompilatio nandinterpreta-tion, tofthisarrangementisthatbytecodescompile dononemachinecanbeinterpretedonanotherma chine, ,someJavacompil-ers,calledjust-in-timeco mpilers, :AhybridcompilerInadditiontoacompiler,se veralotherprogramsmayberequiredtocreatea nexecutabletargetprogram, , ,calledmacros, , ,sotherelocatablemachinecodemayhavetobel inkedtogetherwithotherrelocatableobject lesandlibrary ,wherethecodeinone lemayrefertoalocationinanother :Whatisthedi erencebetweenacompilerandaninterpreter?

6 :Whataretheadvantagesof(a)acompilerovera ninterpreter(b)aninterpreteroveracompile r? :Whatadvantagesaretheretoalanguage-proce ssingsysteminwhichthecompilerproducesass emblylanguageratherthanmachinelanguage? leslibrary lestargetmachinecodeLinker/Loaderrelocat ablemachinecodeAssemblertargetassemblypr ogramCompilermodi , ,thenitmustprovideinformativemessages, , ; ,weseethatitoperatesasasequenceofphases, ,severalphasesmaybegroupedtogether, , :Phasesofacompilerentiresourceprogram, , , ,thelexicalanalyzerproducesasoutputatoke noftheformhtoken-name;attribute-valueith atitpassesontothesubsequentphase, ,the rstcomponenttoken-nameisanabstractsymbol thatisusedduringsyntaxanalysis, ,supposeasourceprogramcontainstheassignm entstatementposition=initial+rate*60( ) ;1i,whereidisanabstractsymbolstandingfor identi erholdsinformationabouttheidenti er, , , ;2i, +isalexemethatismappedintothetokenh+ ;3i, *isalexemethatismappedintothetokenh ( )afterlexicalanalysisasthesequenceoftoke nshid;1ih=ihid;2ih+ihid;3ih ih60i( )Inthisrepresentation,thetokennames=,+,a nd areabstractsymbolsfortheassignment,addit ion,andmultiplicationoperators, ,forthelexeme60weshouldmakeupatokenlikeh number.

7 4i, +rate*60 LexicalAnalyzerhid;1ih=ihid;2ih+ihid;3ih ih60irateid1=id2+t1 CodeGeneratorLDFR2,id3t1=id3* ,R2,# ,id2 ADDFR1,R1,R2 STFid1,R1t3=id2+t2t2=id3*t1t1=inttofloat (60)IntermediateCodeGeneratorSemanticAna lyzerSyntaxAnalyzer3 initial2 position1+=hid;1i+hid;2i60intto oathid;3i hid;2i hid;1i=hid; ( ) +rate* withhid; ;3irepresentstheidenti makesitexplicitthatwemust + ,labeled=,indicatesthatwemuststoretheres ultofthisadditionintothelocationfortheid enti , , , ,manyprogram-minglanguagede nitionsrequireanarrayindextobeaninteger; thecompilermustreportanerrorifa ,abinaryarithmeticoperatormaybeappliedto eitherapairofintegersortoapairof oating-pointnumberandaninteger,thecompil ermayconvertorcoercetheintegerintoa ,initial,andratehavebeendeclaredtobe oating-pointnumbers, isappliedtoa ,theintegermaybeconvertedintoa ,noticethattheoutputofthesemanticanalyze rhasanextranodefortheoperatorintto oat,whichexplicitlyconvertsitsintegerarg umentintoa ,acompilermayconstructoneormoreintermedi aterepresentations, ; ,manycompil-ersgenerateanexplicitlow-lev elormachine-likeintermediaterepresentati on, ,weconsideranintermediateformcalledthree -addresscode, (60)t2=id3*t1t3=id2+t2id1=t3( ) , ,theseinstructions xtheorderinwhichoperationsaretobedone;th emultiplicationprecedestheadditioninthes ourceprogram( ).

8 Sec-ond, ,some\three-addressinstructions"likethe rstandlastinthesequence( ),above, , , ow-of-controlconstructs, ,butotherobjectivesmaybedesired,suchassh ortercode, ,astraightforwardalgorithmgeneratesthein termediatecode( ), oatingpointcanbedoneonceandforallatcompi letime,sotheintto oatoperationcanbeeliminatedbyreplacingth einteger60bythe ,t3isusedonlyoncetotransmititsvaluetoid1 sotheoptimizercantransform( )intotheshortersequencet1=id3* +t1( )Thereisagreatvariationintheamountofcode optimizationdi ,theso-called\optimizingcompilers,"asign i , , ,usingregistersR1andR2,theintermediateco dein( )mightgettranslatedintothemachinecodeLDF R2,id3 MULFR2,R2,# ,id2 ADDFR1,R1,R2 STFid1,R1( )The rstoperandofeachinstructionspeci ( )loadsthecontentsofaddressid3intoregiste rR2,thenmultipliesitwith #signi ,thevalueinregisterR1isstoredintotheaddr essofid1,sothecodecorrectlyimplementsthe assignmentstatement( ). , ,itstype,itsscope(whereintheprogramitsva luemaybeused),andinthecaseofprocedurenam es,suchthingsasthenumberandtypesofitsarg uments,themethodofpassingeachargument(fo rexample,byvalueorbyreference), ,with ,activitiesfromseveralphasesmaybegrouped togetherintoapassthatreadsaninput leandwritesanoutput ,thefront-endphasesoflexicalanalysis,syn taxanalysis,semanticanalysis, ,wecanproducecompilersfordi erentsourcelanguagesforonetargetmachineb ycombiningdi ,wecanproducecompilersfordi erenttargetmachines,bycombiningafrontend withbackendsfordi ,likeanysoftwaredeveloper,canpro tablyusemodernsoftwaredevelopmentenviron mentscontainingtoolssuchaslanguageeditor s,debuggers,versionmanagers,pro lers,testharnesses, , ccomponents, rstelectroniccomputersappearedinthe1940' sandwereprogrammedinmachinelanguagebyseq uencesof0'sand1'.

9 Movedatafromonelocationtoanother,addthec ontentsoftworegisters,comparetwovalues, ,thiskindofprogrammingwasslow,tedious, , rststeptowardsmorepeople-friendlyprogram minglanguageswasthedevelopmentofmnemonic assemblylanguagesintheearly1950' , ,macroinstructionswereaddedtoassemblylan guagessothataprogrammercouldde 'swiththedevelopmentofFortranforscienti ccomputation,Cobolforbusinessdataprocess ing, ,businessappli-cations, ,manymorelanguageswerecreatedwithinnovat ivefeaturestohelpmakeprogrammingeasier,m orenatural, , , ,second-generationtheassemblylanguages,a ndthird-generationthehigher-levellanguag eslikeFortran,Cobol,Lisp,C,C++,C#, capplicationslikeNOMAD forreportgeneration,SQLfordatabasequerie s, cationoflanguagesusesthetermimperativefo rlanguagesinwhichaprogramspeci eshowacomputationistobedoneanddeclarativ eforlanguagesinwhichaprogramspeci ,C++,C#, 'slanguages, , ++,C#,Java, \gluingtogether" \scripts."Awk,JavaScript,Perl,PHP,Python ,Ruby, , 's, , ectiveonusers' , ,manymodernlanguage-processingsystemshan dleseveralsourcelan-guagesandtargetmachi neswithinthesameframework;thatis,theyser veascollectionsofcompilers, , ;thus,compilerwritersmustevaluatetradeo saboutwhatproblemstotackleandwhatheurist icstousetoapproachtheproblemofgenerating e , , :Indicatewhichofthefollowingterms:a)impe rativeb)declarativec)vonNeumannd)object- orientede)functionalf)third-generationg) fourth-generationh) :1)C2)C++3)Cobol4)Fortran5)Java6)Lisp7)M L8)Perl9)Python10) :takeaproblem,formulateamathematicalabst ractionthatcapturesthekeycharacteristics , ,andthesolutionmustbevalidatedandre cationofthelanguage;thesetofsourceprogra msisin niteandanyprogramcanbeverylarge, uenceovernotjustthecompilerstheycreate.

10 However, ,whilebalancingtheneedforgeneralityandpo weragainstsimplicityande nite-statemachinesandregularexpressions, (keywords,identi ers,andsuch) , ,treesareanimportantmodelforrepresenting thestructureofprogramsandtheirtranslatio nintoobjectcode, \optimization"incompilerdesignreferstoth eattemptsthatacom-pilermakestoproducecod ethatismoree cientthantheobviouscode.\Op-timization"i sthusamisnomer, , , ,ortheirperformancesu (com-puterswithchipsthathavelargenumbers ofprocessorsonthem), ,ifnotimpossible,tobuildarobustcompilero utof\hacks."Thus, ,startinginChapter9,howmodelssuchasgraph s,matrices, ,puretheoryaloneisinsu , , : Theoptimizationmustbecorrect,thatis,pres ervethemeaningofthecompiledprogram, Theoptimizationmustimprovetheperformance ofmanyprograms, Thecompilationtimemustbekeptreasonable,a nd Theengineeringe !Optimizingcompilersaresodi culttogetrightthatwedaresaythatnooptimiz ingcompileriscompletelyerror-free!Thus, , , , , , , ,aprogramis ,butmoreimportantly,unoptimizedprogramsa reeasiertodebug, ; , ,acompilerisacomplexsystem; nitenumberofprogramoptimizationsthatweco uldimplement,andittakesanontrivialamount ofe orttocreateacorrectande ,implementingonlythosethatleadtothegreat estbene ,instudyingcompilers,welearnnotonlyhowto buildacompiler, ,andmanypeopleusethetechnol-ogylearnedby studyingcompilersinschool,yethavenever,s trictlyspeaking,written(evenpartof) , , nesaprogrammingabstraction:theprogrammer expressesanalgorithmusingthelanguage, ,higher-levelprogram-minglanguagesareeas iertoprogramin,butarelesse cient,thatis, ,inprinciple,producemoree ,lower-levelprogramsarehardertowriteand| worsestill|lessportable,morepronetoerror s, ,thuso settingtheine , ectiveregister-allocationtechniqueswered eveloped, ,programsthatusetheregisterkeywordmaylos ee ciency, , 's;manyofthenewprojectsstartedinthe90'sc hoseC++.