A.W. Appel - Modern Compiler Implementation in C (798423)
Текст из файла
Modern CompilerImplementationin CBasic TechniquesANDREW W. APPELPrinceton Universitywith MAIA GINSBURGPreliminary edition of Modern Compiler Implementation in CPUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGEThe Pitt Building, Trumpington Street, Cambridge CB2 1RP, United KingdomCAMBRIDGE UNIVERSITY PRESSThe Edinburgh Building, Cambridge CB2 2RU, United Kingdom40 West 20th Street, New York, NY 10011-4211, USA10 Stamford Road, Oakleigh, Melbourne 3166, Australiac Andrew W. Appel and Maia Ginsburg, 1997This book is in copyright. Subject to statutory exceptionand to the provisions of relevant collective licensing agreements,no reproduction of any part may take place withoutthe written permission of Cambridge University Press.First published 1997Printed in the United States of AmericaTypeset in Times, Courier, and OptimaLibrary of Congress Cataloguing-in-Publication data applied forA catalog record for this book is available from the British Library0-521-58275-X0-521-58775-10-521-58387-X0-521-58654-20-521-58389-60-521-58653-4Modern Compiler Implementation in ML: Basic Techniques (hardback)Modern Compiler Implementation in ML: Basic Techniques (paperback)Modern Compiler Implementation in Java: Basic Techniques (hardback)Modern Compiler Implementation in Java: Basic Techniques (paperback)Modern Compiler Implementation in C: Basic Techniques (hardback)Modern Compiler Implementation in C: Basic Techniques (paperback)ContentsPrefaceixPart I Fundamentals of Compilation1 Introduction1.1 Modules and interfaces1.2 Tools and software1.3 Data structures for tree languages34572 Lexical Analysis2.1 Lexical tokens2.2 Regular expressions2.3 Finite automata2.4 Nondeterministic finite automata2.5 Lex: a lexical analyzer generator1617182124313 Parsing3.1 Context-free grammars3.2 Predictive parsing3.3 LR parsing3.4 Using parser generators39414656674 Abstract Syntax4.1 Semantic actions4.2 Abstract parse trees8080845 Semantic Analysis5.1 Symbol tables5.2 Bindings for the Tiger compiler5.3 Type-checking expressions9494103106vCONTENTS5.4 Type-checking declarations1096 Activation Records6.1 Stack frames6.2 Frames in the Tiger compiler1161181267 Translation to Intermediate Code7.1 Intermediate representation trees7.2 Translation into trees7.3 Declarations1401411441608 Basic Blocks and Traces8.1 Canonical trees8.2 Taming conditional branches1661671759 Instruction Selection9.1 Algorithms for instruction selection9.2 CISC machines9.3 Instruction selection for the Tiger compiler18018319219410 Liveness Analysis10.1 Solution of dataflow equations10.2 Liveness in the Tiger compiler20620821611 Register Allocation11.1 Coloring by simplification11.2 Coalescing11.3 Graph coloring implementation11.4 Register allocation for trees22222322623124012 Putting It All Together248Part II Advanced Topics13 Garbage Collection13.1 Mark-and-sweep collection13.2 Reference counts13.3 Copying collection13.4 Generational collectionvi257257262264269CONTENTS13.513.613.7Incremental collectionBaker’s algorithmInterface to the compiler27127427514 Object-oriented Languages14.1 Classes14.2 Single inheritance of data fields14.3 Multiple inheritance14.4 Testing class membership14.5 Private fields and methods14.6 Classless languages14.7 Optimizing object-oriented programs28328328628829029329429515 Functional Programming Languages15.1 A simple functional language15.2 Closures15.3 Immutable variables15.4 Inline expansion15.5 Closure conversion15.6 Efficient tail recursion15.7 Lazy evaluation29930030230330931531832016 Dataflow Analysis16.1 Intermediate representation for flow analysis16.2 Various dataflow analyses16.3 Transformations using dataflow analysis16.4 Speeding up dataflow analysis16.5 Alias analysis33333433734134335117 Loop Optimizations17.1 Dominators17.2 Loop-invariant computations17.3 Induction variables17.4 Array bounds checks17.5 Loop unrolling359362365369374378Appendix: Tiger Language Reference ManualA.1 Lexical issuesA.2 Declarations381381381viiCONTENTSA.3 Variables and expressionsA.4 Standard libraryviii384388Bibliography389Index393PrefaceOver the past decade, there have been several shifts in the way compilers arebuilt.
New kinds of programming languages are being used: object-orientedlanguages with dynamic methods, functional languages with nested scope andfirst-class function closures; and many of these languages require garbagecollection. New machines have large register sets and a high penalty formemory access, and can often run much faster with compiler assistance inscheduling instructions and managing instructions and data for cache locality.This book is intended as a textbook for a one-semester or two-quarter coursein compilers.
Students will see the theory behind different components of acompiler, the programming techniques used to put the theory into practice,and the interfaces used to modularize the compiler. To make the interfacesand programming examples clear and concrete, I have written them in the Cprogramming language. Other editions of this book are available that use theJava and ML languages.The “student project compiler” that I have outlined is reasonably simple,but is organized to demonstrate some important techniques that are now incommon use: Abstract syntax trees to avoid tangling syntax and semantics,separation of instruction selection from register allocation, sophisticated copypropagation to allow greater flexibility to earlier phases of the compiler, andcareful containment of target-machine dependencies to one module.This book, Modern Compiler Implementation in C: Basic Techniques, isthe preliminary edition of a more complete book to be published in 1998,entitled Modern Compiler Implementation in C.
That book will have a morecomprehensive set of exercises in each chapter, a “further reading” discussionat the end of every chapter, and another dozen chapters on advanced materialnot in this edition, such as parser error recovery, code-generator generators,byte-code interpreters, static single-assignment form, instruction schedulingixPREFACEand software pipelining, parallelization techniques, and cache-locality optimizations such as prefetching, blocking, instruction-cache layout, and branchprediction.Exercises. Each of the chapters in Part I has a programming exercise corresponding to one module of a compiler. Unlike many “student project compilers” found in textbooks, this one has a simple but sophisticated back end,allowing good register allocation to be done after instruction selection. Software useful for the programming exercises can be found athttp://www.cs.princeton.edu/˜appel/modern/There are also pencil and paper exercises in each chapter; those marked with astar * are a bit more challenging, two-star problems are difficult but solvable,and the occasional three-star exercises are not known to have a solution.Acknowledgments.
Several people have provided constructive criticism, coursetested the manuscript, or helped in other ways in the production of this book.I would like to thank Stephen Bailey, David Hanson, Elma Lee Noah, ToddProebsting, Barbara Ryder, Amr Sabry, Zhong Shao, Mary Lou Soffa, AndrewTolmach, and Kwangkeun Yi.xPART ONEFundamentals ofCompilation1IntroductionA compiler was originally a program that “compiled”subroutines [a link-loader]. When in 1954 the combination “algebraic compiler” came into use, or rather intomisuse, the meaning of the term had already shifted intothe present one.Bauer and Eickel [1975]This book describes techniques, data structures, and algorithms for translatingprogramming languages into executable code. A modern compiler is oftenorganized into many phases, each operating on a different abstract “language.”The chapters of this book follow the organization of a compiler, each coveringa successive phase.To illustrate the issues in compiling real programming languages, I showhow to compile Tiger, a simple but nontrivial language of the Algol family,with nested scope and heap-allocated records.
Programming exercises in eachchapter call for the implementation of the corresponding phase; a studentwho implements all the phases described in Part I of the book will have aworking compiler. Tiger is easily modified to be functional or object-oriented(or both), and exercises in Part II show how to do this. Other chapters in PartII cover advanced techniques in program optimization.
Appendix A describesthe Tiger language.The interfaces between modules of the compiler are almost as important asthe algorithms inside the modules. To describe the interfaces concretely, it isuseful to write them down in a real programming language. This book usesthe C programming language.3CanonicalizeInstructionSelectionAssemTranslateIR TreesSemanticAnalysisIR TreesTablesTranslateParsingActionsAbstract SyntaxReductionsParseEnvironmentsFrameLinkerMachine LanguageAssemblerRelocatable Object CodeCodeEmissionAssembly LanguageRegisterAllocationRegister AssignmentDataFlowAnalysisInterference GraphControlFlowAnalysisFlow GraphFrameLayoutFIGURE 1.1.1.1TokensLexAssemSource ProgramCHAPTER ONE. INTRODUCTIONPhases of a compiler, and interfaces between them.MODULES AND INTERFACESAny large software system is much easier to understand and implement ifthe designer takes care with the fundamental abstractions and interfaces.Figure 1.1 shows the phases in a typical compiler.
Each phase is implementedas one or more software modules.Breaking the compiler into this many pieces allows for reuse of the components. For example, to change the target-machine for which the compilerproduces machine language, it suffices to replace just the Frame Layout and Instruction Selection modules. To change the source language being compiled,only the modules up through Translate need to be changed. The compilercan be attached to a language-oriented syntax editor at the Abstract Syntaxinterface.The learning experience of coming to the right abstraction by several iterations of think–implement–redesign is one that should not be missed.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
