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 ( )

2 Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. 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.

3 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. 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).

4 Chapter5introducestheprincipalideasinsyn tax-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).

5 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)

6 ' 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?

7 :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+.

8 3i, *isalexemethatismappedintothetokenh ( )afterlexicalanalysisasthesequenceoftoke nshid;1ih=ihid;2ih+ihid;3ih ih60i( )Inthisrepresentation,thetokennames=,+,a nd areabstractsymbolsfortheassignment,addit ion,andmultiplicationoperators, ,forthelexeme60weshouldmakeupatokenlikeh number;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.

9 ,manycompil-ersgenerateanexplicitlow-lev elormachine-likeintermediaterepresentati on, ,weconsideranintermediateformcalledthree -addresscode, (60)t2=id3*t1t3=id2+t2id1=t3( ) , ,theseinstructions xtheorderinwhichoperationsaretobedone;th emultiplicationprecedestheadditioninthes ourceprogram( ).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 ( )

10 Loadsthecontentsofaddressid3intoregister R2,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'.