Modern Compiler Design 2nd Edition - Free

1 Dick Grune Kees van Reeuwijk Henri E. BalModern Compiler DesignSecond EditionCeriel Jacobs Koen Langendoen ISBN 978- ---9 ISBN 978-1-4614-4699-DOI - Library of Congress Control Numb Printed on acid-free paper Springer is part of Springer Science+Business Media ( ) er: This work is subject to copyright. All rights are reserved by the Publisher, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilms or in any other physical way, and transmission or information storage and retrieval, electronic adaptation, computer software, or by similar or dissimilar methodology now known or hereafter developed. Exempted from this legal reservation are brief excerpts in connection with reviews or scholarly analysis or material supplied specifically for the purpose of being entered and executed on a computer system, for exclusive use by the purchaser of the work.

2 Duplication of this publication or parts thereof is permitted only undeCopyright Law of the Publisher s location, in its current version, and permission for use must always be obtained from Springer. Permissions for use may be obtained through RightsLink at the Copyright Clearance Center. Violations are liable to prosecution under the respective Copyright Law. The use of general descriptive names, registered names, trademarks, service marks, etc. in thi does not imply, even in the absence of a specific statement, that such names are exemp protective laws and regulations and therefore free for general use. While the advice and information in this book are believed to be trupublication, neither the authors nor the editors nor the publisher can accept any legal responsibility for any errors or omissions that may be made. The publisher makes no warranty, express or implied, with respect to the material contained herein. r the provisions of thes publicationt from the relevante and accurate at the date ofSpringer New York Heidelberg Dordrecht London1 46146 (eBook)1 4614-4699-64698 Springer Science+Business Media New York 2012 2012941168 Dick GruneVrije UniversiteitAmsterdam, The NetherlandsVrije UniversiteitAmsterdam, The NetherlandsVrije UniversiteitAmsterdam, The NetherlandsVrije UniversiteitAmsterdam, The NetherlandsKees van ReeuwijkHenri E.

3 BalCeriel JacobsKoen LangendoenDelft University of TechnologyDelft, The NetherlandsAdditional material to this book can be downloaded from years have passed since the first Edition ofModern Compiler computer science subjects this would be more than a life time, but since com-piler Design is probably the most mature computer science subject, it is adult person develops more slowly and differently than a toddler or a teenager,and so does Compiler Design . The present book reflects to the book fall into two groups: presentation and content. The look and feel of the book has been modernized, but more importantly we haverearranged significant parts of the book to present them in a more structured manner:large chapters have been split and the optimizing code generation techniques havebeen collected in a separate chapter . Based on reader feedback and experiences inteaching from this book, both by ourselves and others, material has been expanded,clarified, modified, or deleted in a large number of places.

4 We hope that as a resultof this the reader feels that the book does a better job of making Compiler designand construction book adds new material to cover the developments in Compiler Design andconstruction over the last twelve years. Overall the standard compiling techniquesand paradigms have stood the test of time, but still new and often surprising opti-mization techniques have been invented; existing ones have been improved; and oldones have gained prominence. Examples of the first are: procedural abstraction, inwhich routines are recognized in the code and replaced by routine calls to reducesize; binary rewriting, in which optimizations are applied to the binary code; andjust-in-time compilation, in which parts of the compilation are delayed to improvethe perceived speed of the program. An example of the second is a technique whichextends optimal code generation through exhaustive search, previously available fortiny blocks only, to moderate-size basic blocks.

5 And an example of the third is tailrecursion removal, indispensable for the compilation of functional languages. Thesedevelopments are mainly described in chapter syntax analysis is the one but oldest branch of Compiler construction(lexical analysis being the oldest), even in that area innovation has taken (non-deterministic) LR parsing, developed between 1984 and 1994, isnow used in compilers. It is covered in Section hardware requirements have necessitated new Compiler developments. Themain examples are the need for size reduction of the object code, both to fit the codeinto small embedded systems and to reduce transmission times; and for lower powervviPrefaceconsumption, to extend battery life and to reduce electricity bills. Dynamic memoryallocation in embedded systems requires a balance between speed and thrift, and thequestion is how Compiler Design can help. These subjects are covered in , , and , age comes legacy. There is much legacy code around, code which is soold that it can no longer be modified and recompiled with reasonable effort.

6 If thesource code is still available but there is no Compiler any more, recompilation muststart with a grammar of the source code. For fifty years programmers and compilerdesigners have used grammars to produce and analyze programs; now large legacyprograms are used to produce grammars for them. The recovery of the grammarfrom legacy source code is discussed in Section If just the binary executableprogram is left, it must be disassembled or even decompiled. For fifty years com-piler designers have been called upon to Design compilers and assemblers to convertsource programs to binary code; now they are called upon to Design disassemblersand decompilers, to roll back the assembly and compilation process. The requiredtechniques are treated in Sections and bibliographyThe literature list has been updated, but its usefulness is more limited than before,for two reasons. The first is that by the time it appears in print, the Internet can pro-vide more up-to-date and more to-the-point information, in larger quantities, than aprinted text can hope to achieve.

7 It is our contention that anybody who has under-stood a larger part of the ideas explained in this book is able to evaluate Internetinformation on Compiler second is that many of the papers we refer to are available only to thosefortunate enough to have login facilities at an institute with sufficient budget toobtain subscriptions to the larger publishers; they are no longer available to justanyone who walks into a university library. Both phenomena point to paradigmshifts with which readers, authors, publishers and librarians will have to structure of the bookThis book is conceptually divided into two parts. The first, comprising Chapters 1through 10, is concerned with techniques for program processing in general; it in-cludes a chapter on memory management, both in the Compiler and in the generatedcode. The second part, Chapters 11 through 14, covers the specific techniques re-quired by the various programming paradigms. The interactions between the partsof the book are outlined in the adjacent table.

8 The leftmost column shows the fourphases of Compiler construction:analysis,context handling,synthesis, andrun-timesystems. Chapters in this column cover both the manual and the automatic creationPrefaceviiof the pertinent software but tend to emphasize automatic generation. The othercolumns show the four paradigms covered in this book; for each paradigm an ex-ample of a subject treated by each of the phases is shown. These chapters tend tocontain manual techniques only, all automatic techniques having been delegated toChapters 2 through imperativeand object-orientedprograms( chapter 11)in functionalprograms( chapter 12)in logicprograms( chapter 13)in parallel/distributedprograms( chapter 14)How to do:analysis(Chapters 2 & 3) contexthandling(Chapters 4 & 5)identifieridentificationpolymorphictyp e checkingstatic rulematchingLinda staticanalysissynthesis(Chapters 6 9)code forwhile-statementcode for listcomprehensionstructureunificationmar shalingrun-timesystems(no chapter )stackreductionmachineWarrenAbstr actMachinereplicationThe scientific mind would like the table to be nice and square, with all boxesfilled in short orthogonal but we see that the top right entries are missingand that there is no chapter for run-time systems in the leftmost column.

9 The topright entries would cover such things as the special subjects in the program textanalysis of logic languages, but present text analysis techniques are powerful andflexible enough and languages similar enough to handle all language paradigms:there is nothing to be said there, for lack of problems. The chapter missing fromthe leftmost column would discuss manual and automatic techniques for creatingrun-time systems. Unfortunately there is little or no theory on this subject: run-timesystems are still crafted by hand by programmers on an intuitive basis; there isnothing to be said there, for lack of 1 introduces the reader to Compiler Design by examining a simple tradi-tional modular Compiler /interpreter in detail. Several high-level aspects of compilerconstruction are discussed, followed by a short history of Compiler construction andintroductions to formal grammars and closure 2 and 3 treat the program text analysis phase of a Compiler : the conver-sion of the program text to an abstract syntax tree.

10 Techniques for lexical analysis,lexical identification of tokens, and syntax analysis are 4 and 5 cover the second phase of a Compiler : context handling. Sev-eral methods of context handling are discussed: automated ones using attributegrammars, manual ones using L-attributed and S-attributed grammars, and semi-automated ones using symbolic interpretation and data-flow 6 through 9 cover the synthesis phase of a Compiler , covering both in-terpretation and code generation. The chapters on code generation are mainly con-cerned with machine code generation; the intermediate code required for paradigm-specific constructs is treated in Chapters 11 through 10 concerns memory management techniques, both for use in the com-piler and in the generated 11 through 14 address the special problems in compiling for the variousparadigms imperative, object-oriented, functional, logic, and for imperative and object-oriented programs are similar enough to betreated together in one chapter , chapter B contains hints and answers to a selection of the exercises in thebook.