Modern Compiler Implementation in C

【实例简介】
Modern Compiler Implementation in C 可参考：COMPILING WITH CONTINUATIONS （csdn）
Modern compiler Implementation in c ANDREW W. APPEL Princeton university with MAIA GINSBURG L CAMBrIDge V UNIVERSITY PRESS PUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGE The Pitt Building, Trumpington Street, Cambridge, United Kingdom CAMBRIDGE UNIVERSITY PRESS The Edinburgh building, Cambridge CB2 2RU, UK 40 West 20th Street. New York ny 10011-4211 USA 477 Williamstown Road. Port Melbourne. viC 3207. Australia Ruiz de alarcon 13, 28014 Madrid, spain Dock House, The Waterfront, Cape Town 8001, South Africa http://www.cambridge.org Informationonthistitlewww.cambridge.org/9780521583909 C Andrew W. Appel and Maia Ginsburg 1998 This book is in copyright. Subject to statutory exception and to the provisions of relevant collective licensing agreements, no reproduction of any part may take place without the written permission of Cambridge University Press First published 1998 Revised and expanded edition of Modern Compiler Implementation in C: Basic Techniques Reprinted with corrections, 1999 First paperback edition 2004 Typeset in Times, Courier, and Optima A catalogue record for this book is available from the british Library Library of Congress Cataloguing-in-Publication data Appel, Andrew W,1960- Modern compiler implementation in C Andrew W. Appel with Maia Ginsburg -Rev and expanded ed Includes bibliographical references(p. 528-536) and index IsBN 0 521 58390 X(hardback) 1. C( Computer program language)2. Compilers(Computer programs I Ginsburg, Maia. II. Title QA76.73.C15A631998 005453-dc21 97-031089 CIP IsbN0521 58390X hardback IsBn 0 521 60765 5 paperback Contents Preface PartI Fundamentals of Compilation 1 Introduction 1.1 Modules and interfaces 4 1. 2 Tools and software 1.3 Data structures for tree languages 2 Lexical Analysis 16 2.1 Lexical tokens 17 2.2 Regular expressions 2.3 Finite automata 21 2.4 Nondeterministic finite automata 24 2.5 Lex: a lexical analyzer generator 30 arsing 39 3.1 Context-free grammars 41 3.2 Predictive parsing 46 3.3 LR parsing 56 3.4 USing parser generators 3.5 Error recovery 76 4 Abstract Syntax 88 4.1 Semantic actions 88 4.2 Abstract parse trees 92 5 Semantic Analysis 103 5.1 Symbol tables 103 5.2 Bindings for the Tiger compiler 112 CONTENTS 5.3 Type-checking expressions 115 5.4 Type-checking declarations 118 6 Activation records 125 6.1 Stack frames 127 6.2 Frames in the Tiger compiler 135 7 Translation to Intermediate Code 150 7.1 Intermediate representation trees 151 7.2 Translation into trees 154 7. 3 Declarations 170 8 Basic blocks and traces 176 8.1 Canonical trees 177 8.2 Taming conditional branches 185 9 Instruction Selection 191 9.1 Algorithms for instruction selection 194 9.2 CISC machines 202 9.3 Instruction selection for the Tiger compiler 205 10 Liveness Analysis 218 10.1 Solution of dataflow equations 220 10.2 Liveness in the Tiger compiler 229 11 Register Allocation 235 11.1 Coloring by simplification 236 11.2 Coalescing 239 11.3 Precolored nodes 243 11.4 Graph coloring implementation 248 11.5 Register allocation for trees 257 12 Putting It All Together 265 Part Ii Advanced Topics 13 Garbage Collection 273 13. 1 Mark-and-sweep collection 273 13.2 Reference counts 278 CONTENTS 13. 3 Copying collection 280 13. 4 Generational collection 285 13.5 Incremental collection 287 13.6 Baker's algorithm 290 13.7 Interface to the compiler 291 14 Object-Oriented Languages 299 14.1 Classes 14.2 Single inheritance of data fields 302 14.3 Multiple inheritance 304 14. 4 Testing class membershi 306 14.5 Private fields and methods 310 14.6 Classless languages 310 14.7 Optimizing object-oriented programs 311 15 Functional Programming Languages 315 15.1 A simple functional language 316 15.2 Closures 318 15.3 Immutable variables 319 15.4 Inline expansion 326 15.5 Closure conversion 332 15.6 Efficient tail recursion 335 15. 7 Lazy evaluation 337 16 Polymorphic Types 350 16.1 Parametric polymorphism 351 16.2 Type inference 359 16.3 Representation of polymorphic variables 369 16.4 Resolution of static overloading 378 7 Dataflow Analysis 383 17.1 Intermediate representation for flow analysis 384 17.2 Various dataflow analyses 387 17.3 Transformations using dataflow analysis 392 17.4 Speeding up dataflow analysis 393 17.5 Alias analysis 402 18 Loop Optimizations 410 18.1 Dominators 413 VII CONTENTS 18.2 Loop-invariant computations 418 18. 3 Induction variables 419 18.4 Array-bounds checks 425 18.5 Loop unrolling 429 19 Static Single-AsSignment Form 433 19.1 Converting to ssa form 436 19.2 Efficient computation of the dominator tree 44 44 19.3 Optimization algorithms using ssa 451 19.4 Arrays, pointers, and memory 457 19.5 The control-dependence graph 459 19.6 Converting back from SSA form 462 19.7 A functional intermediate form 464 20 Pipelining and Scheduling 474 20. 1 Loop scheduling without resource boun 478 20.2 Resource-bounded loop pipelining 482 20.3 Branch prediction 21 The Memory Hierarchy 498 21.1 Cache organization 499 21.2 Cache-block alignment 502 21.3 Prefetching 504 21.4 Loop interchange 510 21.5 Blocking 511 21.6 Garbage collection and the memory hierarch 514 Appendix: Tiger Language Reference Manual 518 A1 Lexical issues 518 A 2 Declarations 518 A3 Variables and expressions 521 A 4 Standard library 525 A.5 Sample Tiger programs 526 Biblio h graphy 528 ex 537 Preface Over the past decade, there have been several shifts in the way compilers are built. New kinds of programming languages are being used: object-oriented languages with dynamic methods, functional languages with nested scope and first-class function closures; and many of these languages require garbage collection. New machines have large register sets and a high penalty for mem ory access, and can often run much faster with compiler assistance in schedul ing instructions and managing instructions and data for cache locality This book is intended as a textbook for a one or two-semester course in compilers. Students will see the theory behind different components of a compiler, the programming techniques used to put the theory into practice, and the interfaces used to modularize the compiler. To make the interfaces and programming examples clear and concrete, I have written them in the C programming language. Other editions of this book are available that use the Java and ml language Implementation project. The"student project compiler"that I have outlined is reasonably simple, but is organized to demonstrate some important tech- niques that are now in common use: abstract syntax trees to avoid tangling syntax and semantics, separation of instruction selection from register alloca tion, copy propagation to give flexibility to earlier phases of the compiler, and containment of target-machine dependencies. Unlike many"student compil- ers" found in textbooks, this one has a simple but sophisticated back end allowing good register allocation to be done after instruction selection Each chapter in Part I has a programming exercise corresponding to one module of a compiler Software useful for the exercises can be found at http://www.cs.princeton.edu/appel/modern/c 【实例截图】
【核心代码】