第1页 / 共830页
第2页 / 共830页
第3页 / 共830页
第4页 / 共830页
第5页 / 共830页
第6页 / 共830页
第7页 / 共830页
第8页 / 共830页
Modern Compiler Design 2nd Edition(英文原版-编译原理).pdf
Cover
Modern Compiler Design
Preface
The bibliography
The structure of the book
Use as a course book
Acknowledgments
Abridged Preface to the First Edition (2000)
The audience
Acknowledgments
Contents
Chapter 1 Introduction
1.1 Why study compiler construction?
1.1.1 Compiler construction is very successful
1.1.1.1 Proper structuring of the problem
1.1.1.2 Judicious use of formalisms
1.1.1.3 Use of program-generating tools
1.1.2 Compiler construction has a wide applicability
1.1.3 Compilers contain generally useful algorithms
1.2 A simple traditional modular compiler/interpreter
1.2.1 The abstract syntax tree
1.2.2 Structure of the demo compiler
1.2.3 The language for the demo compiler
1.2.4 Lexical analysis for the demo compiler
1.2.5 Syntax analysis for the demo compiler
1.2.6 Context handling for the demo compiler
1.2.7 Code generation for the demo compiler
1.2.8 Interpretation for the demo compiler
1.3 The structure of a more realistic compiler
1.3.1 The structure
1.3.2 Run-time systems
1.3.3 Short-cuts
1.4 Compiler architectures
1.4.1 The width of the compiler
1.4.2 Who’s the boss?
1.5 Properties of a good compiler
1.6 Portability and retargetability
1.7 A short history of compiler construction
1.7.1 1945–1960: code generation
1.7.2 1960–1975: parsing
1.7.3 1975–present: code generation and code optimization; paradigms
1.8 Grammars
1.8.1 The form of a grammar
1.8.2 The grammatical production process
1.8.3 Extended forms of grammars
1.8.4 Properties of grammars
1.8.5 The grammar formalism
1.8.5.1 The definition of a grammar
1.8.5.2 Definition of the language generated by a grammar
1.9 Closure algorithms
1.9.1 A sample problem
1.9.2 The components of a closure algorithm
1.9.3 An iterative implementation of the closure algorithm
1.10 The code forms used in this book
1.11 Conclusion
Summary
Further reading
Exercises
Part I From Program Text
to Abstract Syntax Tree
Chapter 2 Program Text to Tokens— Lexical Analysis
2.1 Reading the program text
2.1.1 Obtaining and storing the text
2.1.2 The troublesome newline
2.2 Lexical versus syntactic analysis
2.3 Regular expressions and regular descriptions
2.3.1 Regular expressions and BNF/EBNF
2.3.2 Escape characters in regular expressions
2.3.3 Regular descriptions
2.4 Lexical analysis
2.5 Creating a lexical analyzer by hand
2.5.1 Optimization by precomputation
2.5.1.1 Naive precomputation
2.5.1.2 Compressing the tables
2.6 Creating a lexical analyzer automatically
2.6.1 Dotted items
2.6.1.1 Character moves
2.6.1.2 ε -moves
2.6.1.3 A sample run
2.6.2 Concurrent search
2.6.3 Precomputing the item sets
2.6.4 The final lexical analyzer
2.6.5 Complexity of generating a lexical analyzer
2.6.6 Transitions to Sω
2.6.7 Complexity of using a lexical analyzer
2.7 Transition table compression
2.7.1 Table compression by row displacement
2.7.1.1 Finding the best displacements
2.7.2 Table compression by graph coloring
2.8 Error handling in lexical analyzers
2.9 A traditional lexical analyzer generator—lex
2.10 Lexical identification of tokens
2.11 Symbol tables
2.12 Macro processing and file inclusion
2.12.1 The input buffer stack
2.12.1.1 Back-calls
2.12.1.2 Parameters of macros
2.12.2 Conditional text inclusion
2.12.3 Generics by controlled macro processing
2.13 Conclusion
Summary
Exercises
Chapter 3 Tokens to Syntax Tree— Syntax Analysis
3.1 Two classes of parsing methods
3.1.1 Principles of top-down parsing
3.1.2 Principles of bottom-up parsing
3.2 Error detection and error recovery
3.3 Creating a top-down parser manually
3.3.1 Recursive descent parsing
3.3.2 Disadvantages of recursive descent parsing
3.4 Creating a top-down parser automatically
3.4.1 LL(1) parsing
3.4.1.1 LL(1) parsing with nullable alternatives
3.4.2 LL(1) conflicts as an asset
3.4.3 LL(1) conflicts as a liability
3.4.3.1 Making a grammar LL(1)
3.4.3.2 Undoing the semantic effects of grammar transformations
3.4.3.3 Automatic conflict resolution
3.4.4 The LL(1) push-down automaton
3.4.5 Error handling in LL parsers
3.4.5.1 The acceptable-set method
3.4.5.2 A fully automatic acceptable-set method based on continuations
3.4.5.3 Finding the alternative with the shortest production
3.4.6 A traditional top-down parser generator—LLgen
3.4.6.1 An example with a transformed grammar
3.4.6.2 Constructing a correct parse tree with a transformed grammar
3.5 Creating a bottom-up parser automatically
3.5.1 LR(0) parsing
3.5.1.1 Precomputing the item set
3.5.2 The LR push-down automaton
3.5.3 LR(0) conflicts
3.5.4 SLR(1) parsing
3.5.5 LR(1) parsing
3.5.6 LALR(1) parsing
3.5.7 Making a grammar (LA)LR(1)—or not
3.5.7.1 Resolving shift-reduce conflicts automatically
3.5.7.2 Resolving reduce-reduce conflicts automatically
3.5.8 Generalized LR parsing
3.5.8.1 The basic GLR algorithm
3.5.8.2 Optimizations for GLR parsers
3.5.9 Making a grammar unambiguous
3.5.10 Error handling in LR parsers
3.5.10.1 Recovery without modifying the stack
3.5.10.2 Recovery with stack modification
3.5.11 A traditional bottom-up parser generator—yacc/bison
3.6 Recovering grammars from legacy code
3.7 Conclusion
Summary
Further reading
Exercises
Part II Annotating
the Abstract Syntax Tree
Chapter 4 Grammar-based Context Handling
4.1 Attribute grammars
4.1.1 The attribute evaluator
4.1.2 Dependency graphs
4.1.3 Attribute evaluation
4.1.3.1 A dynamic attribute evaluator
4.1.3.2 Cycle handling
4.1.4 Attribute allocation
4.1.5 Multi-visit attribute grammars
4.1.5.1 Multi-visits
4.1.5.2 Attribute partitionings
4.1.5.3 Ordered attribute grammars
4.1.5.4 The ordered attribute grammar for the octal/decimal example
4.1.6 Summary of the types of attribute grammars
4.2 Restricted attribute grammars
4.2.1 L-attributed grammars
4.2.1.1 L-attributed grammars and top-down parsers
4.2.1.2 L-attributed grammars and bottom-up parsers
4.2.2 S-attributed grammars
4.2.3 Equivalence of L-attributed and S-attributed grammars
4.3 Extended grammar notations and attribute grammars
4.4 Conclusion
Summary
Summary—Attribute grammars
Summary—L- and S- attributed grammars
Further reading
Exercises
Chapter 5 Manual Context Handling
5.1 Threading the AST
5.2 Symbolic interpretation
5.2.1 Simple symbolic interpretation
5.2.2 Full symbolic interpretation
5.2.3 Last-def analysis
5.3 Data-flow equations
5.3.1 Setting up the data-flow equations
5.3.2 Solving the data-flow equations
5.4 Interprocedural data-flow analysis
5.5 Carrying the information upstream—live analysis
5.5.1 Live analysis by symbolic interpretation
5.5.2 Live analysis by data-flow equations
5.6 Symbolic interpretation versus data-flow equations
5.7 Conclusion
Summary
Further reading
Exercises
Part III Processing
the Intermediate Code
Chapter 6 Interpretation
6.1 Interpreters
6.2 Recursive interpreters
6.3 Iterative interpreters
6.4 Conclusion
Summary
Further reading
Exercises
Chapter 7 Code Generation
7.1 Properties of generated code
7.1.1 Correctness
7.1.2 Speed
7.1.3 Size
7.1.4 Power consumption
7.1.5 About optimizations
7.2 Introduction to code generation
7.2.1 The structure of code generation
7.2.2 The structure of the code generator
7.3 Preprocessing the intermediate code
7.3.1 Preprocessing of expressions
7.3.2 Preprocessing of if-statements and goto statements
7.3.3 Preprocessing of routines
7.3.4 Procedural abstraction
7.4 Avoiding code generation altogether
7.5 Code generation proper
7.5.1 Trivial code generation
7.5.1.1 Threaded code
7.5.1.2 Partial evaluation
7.5.2 Simple code generation
7.6 Postprocessing the generated code
7.6.1 Peephole optimization
7.6.1.1 Creating replacement patterns
7.6.1.2 Locating and replacing instructions
7.6.1.3 Evaluation of peephole optimization
7.6.2 Procedural abstraction of assembly code
7.7 Machine code generation
7.8 Conclusion
Summary
Further reading
Exercises
Chapter 8 Assemblers, Disassemblers, Linkers, and Loaders
8.1 The tasks of an assembler
8.1.1 The running program
8.1.2 The executable code file
8.1.3 Object files and linkage
8.1.4 Alignment requirements and endianness
8.2 Assembler design issues
8.2.1 Handling internal addresses
8.2.2 Handling external addresses
8.3 Linker design issues
8.4 Disassembly
8.4.1 Distinguishing between instructions and data
8.4.2 Disassembly with indirection
8.4.3 Disassembly with relocation information
8.5 Decompilation
8.6 Conclusion
Summary
Further reading
Exercises
Chapter 9 Optimization Techniques
9.1 General optimization
9.1.1 Compilation by symbolic interpretation
9.1.2 Code generation for basic blocks
9.1.2.1 From AST to dependency graph
9.1.2.2 From dependency graph to code
9.1.2.3 Code optimization in the presence of pointers
9.1.3 Almost optimal code generation
9.1.4 BURS code generation and dynamic programming
9.1.4.1 Bottom-up pattern matching
9.1.4.2 Bottom-up pattern matching, efficiently
9.1.4.3 Instruction selection by dynamic programming
9.1.4.4 Pattern matching and instruction selection combined
9.1.4.5 Adaptation of the BURS algorithm to different circumstances
9.1.5 Register allocation by graph coloring
9.1.5.1 The register interference graph
9.1.5.2 Heuristic graph coloring
9.1.6 Supercompilation
9.1.7 Evaluation of code generation techniques
9.1.8 Debugging of code optimizers
9.2 Code size reduction
9.2.1 General code size reduction techniques
9.2.1.1 Traditional optimization techniques
9.2.1.2 Useless code removal
9.2.1.3 Tailored intermediate code
9.2.1.4 Code compression
9.2.1.5 Tailored hardware instructions
9.2.2 Code compression
9.2.2.1 General compression techniques
9.2.2.2 Applying general techniques to code compression
9.2.2.3 Special techniques for code compression
9.2.3 Discussion
9.3 Power reduction and energy saving
9.3.1 Just compiling for speed
9.3.2 Trading speed for power
9.3.3 Instruction scheduling and bit switching
9.3.4 Register relabeling
9.3.5 Avoiding the dynamic scheduler
9.3.6 Domain-specific optimizations
9.3.7 Discussion
9.4 Just-In-Time compilation
9.5 Compilers versus computer architectures
9.6 Conclusion
Summary
Further reading
Exercises
Part IV Memory Management
Chapter 10 Explicit and Implicit Memory Management
10.1 Data allocation with explicit deallocation
10.1.1 Basic memory allocation
10.1.2 Optimizations for basic memory allocation
10.1.3 Compiler applications of basic memory allocation
10.1.3.1 Linked lists
10.1.3.2 Extensible arrays
10.1.4 Embedded-systems considerations
10.2 Data allocation with implicit deallocation
10.2.1 Basic garbage collection algorithms
10.2.2 Preparing the ground
10.2.2.1 Compiler assistance to garbage collection
10.2.2.2 Specifying pointer layout of chunks
10.2.2.3 Specifying the pointer layout of the program data area
10.2.2.4 Some simplifying assumptions
10.2.3 Reference counting
10.2.4 Mark and scan
10.2.4.1 Marking
10.2.4.2 Scanning and freeing
10.2.4.3 Pointer reversal—marking without using stack space
10.2.5 Two-space copying
10.2.6 Compaction
10.2.7 Generational garbage collection
10.2.8 Implicit deallocation in embedded systems
10.3 Conclusion
Summary
Further reading
Exercises
Part V From Abstract Syntax Tree to Intermediate Code
Chapter 11 Imperative and Object-Oriented Programs
11.1 Context handling
11.1.1 Identification
11.1.1.1 Scopes
11.1.1.2 Overloading
11.1.1.3 Imported scopes
11.1.2 Type checking
11.1.2.1 The type table
11.1.2.2 Type equivalence
11.1.2.3 Coercions
11.1.2.4 Casts and conversions
11.1.2.5 Kind checking
11.1.3 Discussion
11.2 Source language data representation and handling
11.2.1 Basic types
11.2.2 Enumeration types
11.2.3 Pointer types
11.2.3.1 Bad pointers
11.2.3.2 Pointer scope rules
11.2.4 Record types
11.2.5 Union types
11.2.6 Array types
11.2.7 Set types
11.2.8 Routine types
11.2.9 Object types
11.2.9.1 Feature 1: Inheritance
11.2.9.2 Feature 2: Method overriding
11.2.9.3 Feature 3: Polymorphism
11.2.9.4 Feature 4: Dynamic binding
11.2.9.5 Feature 5: Multiple inheritance
11.2.9.6 Feature 6: Dependent multiple inheritance
11.2.9.7 Optimizations for method invocation
11.2.10 Interface types
11.3 Routines and their activation
11.3.1 Activation records
11.3.2 The contents of an activation record
11.3.3 Routines
11.3.4 Operations on routines
11.3.5 Non-nested routines
11.3.6 Nested routines
11.3.6.1 Calling a nested routine
11.3.6.2 Passing a nested routine as a parameter
11.3.6.3 Returning a nested routine as a value
11.3.6.4 Jumping out of a nested routine
11.3.6.5 Partial parameterization
11.3.6.6 Discussion
11.3.7 Lambda lifting
11.3.8 Iterators and coroutines
11.4 Code generation for control flow statements
11.4.1 Local flow of control
11.4.1.1 Boolean expressions in flow of control
11.4.1.2 Selection statements
11.4.1.3 Repetition statements
11.4.2 Routine invocation
11.4.2.1 Routine identification—what to call
11.4.2.2 Routine calls—how to call it
11.4.2.3 Non-local gotos
11.4.3 Run-time error handling
11.4.3.1 Detecting a run-time error
11.4.3.2 Handling a run-time error
11.5 Code generation for modules
11.5.1 Name generation
11.5.2 Module initialization
11.5.2.1 Avoiding multiple initializations
11.5.2.2 Detecting circular dependencies
11.5.3 Code generation for generics
11.5.3.1 Instantiation through expansion
11.5.3.2 Instantiation through dope vectors
11.6 Conclusion
Summary
Summary—Context handling
Summary—Data representation and routines
Summary—Code generation
Further reading
Exercises
Chapter 12 Functional Programs
12.1 A short tour of Haskell
12.1.1 Offside rule
12.1.2 Lists
12.1.3 List comprehension
12.1.4 Pattern matching
12.1.5 Polymorphic typing
12.1.6 Referential transparency
12.1.7 Higher-order functions
12.1.8 Lazy evaluation
12.2 Compiling functional languages
12.2.1 The compiler structure
12.2.2 The functional core
12.3 Polymorphic type checking
12.4 Desugaring
12.4.1 The translation of lists
12.4.2 The translation of pattern matching
12.4.3 The translation of list comprehension
12.4.4 The translation of nested functions
12.5 Graph reduction
12.5.1 Reduction order
12.5.2 The reduction engine
12.6 Code generation for functional core programs
12.6.1 Avoiding the construction of some application spines
12.7 Optimizing the functional core
12.7.1 Strictness analysis
12.7.1.2 Code generation for strict arguments
12.7.2 Boxing analysis
12.7.3 Tail calls
12.7.4 Accumulator transformation
12.7.5 Limitations
12.8 Advanced graph manipulation
12.8.1 Variable-length nodes
12.8.2 Pointer tagging
12.8.3 Aggregate node allocation
12.8.4 Vector apply nodes
12.9 Conclusion
Summary
Summary—The front-end
Summary—Graph reduction
Further reading
Exercises
Chapter 13 Logic Programs
13.1 The logic programming model
13.1.1 The building blocks
13.1.2 The inference mechanism
13.2 The general implementation model, interpreted
13.2.1 The interpreter instructions
13.2.2 Avoiding redundant goal lists
13.2.3 Avoiding copying goal list tails
13.3 Unification
13.3.1 Unification of structures, lists, and sets
13.3.2 The implementation of unification
13.3.3 Unification of two unbound variables
13.4 The general implementation model, compiled
13.4.1 List procedures
13.4.2 Compiled clause search and unification
13.4.3 Optimized clause selection in the WAM
13.4.4 Implementing the “cut” mechanism
13.4.5 Implementing the predicates assert and retract
13.5 Compiled code for unification
13.5.1 Unification instructions in the WAM
13.5.2 Deriving a unification instruction by manual partial evaluation
13.5.3 Unification of structures in the WAM
13.5.4 An optimization: read/write mode
13.5.5 Further unification optimizations in the WAM
13.6 Conclusion
Summary
Further reading
Exercises
Chapter 14 Parallel and Distributed Programs
14.1 Parallel programming models
14.1.1 Shared variables and monitors
14.1.2 Message passing models
14.1.3 Object-oriented languages
14.1.4 The Linda Tuple space
14.1.5 Data-parallel languages
14.2 Processes and threads
14.3 Shared variables
14.3.1 Locks
14.3.2 Monitors
14.4 Message passing
14.4.1 Locating the receiver
14.4.2 Marshaling
14.4.3 Type checking of messages
14.4.4 Message selection
14.5 Parallel object-oriented languages
14.5.1 Object location
14.5.2 Object migration
14.5.3 Object replication
14.6 Tuple space
14.6.1 Avoiding the overhead of associative addressing
14.6.2 Distributed implementations of the tuple space
14.7 Automatic parallelization
14.7.1 Exploiting parallelism automatically
14.7.2 Data dependencies
14.7.3 Loop transformations
14.7.4 Automatic parallelization for distributed-memory machines
14.8 Conclusion
Summary
Further reading
Exercises
Appendix A Machine Instructions
Appendix B Hints and Solutions to Selected Exercises
References
Index
Dick Grune • Kees van Reeuwijk • Henri E. BalModern Compiler DesignSecond EditionCeriel J.H. Jacobs • Koen Langendoen
Dick Grune
Vrije Universiteit
Amsterdam, The Netherlands
Kees van Reeuwijk
Vrije Universiteit
Amsterdam, The Netherlands
Henri E. Bal
Vrije Universiteit
Amsterdam, The Netherlands
Ceriel J.H. Jacobs
Vrije Universiteit
Amsterdam, The Netherlands
Koen Langendoen
Delft University of Technology
Delft, The Netherlands
Additional material to this book can be downloaded from http://extras.springer.com.
-9
er:
2012941168
ISBN 978-1-4614-4699-
6 (eBook)
-
1 4614
4698
1 4614-4699-6
ISBN 978- -
DOI 10.1007/978- -
Springer New York Heidelberg Dordrecht London
Library of Congress Control Numb
© Springer Science+Business Media New York 2012
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. Duplication of this publication or parts thereof is permitted only unde
r the provisions of the
Copyright 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 tru
e and accurate at the date of
publication, 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.
Printed on acid-free paper
Springer is part of Springer Science+Business Media (www.springer.com)
s publication
t from the relevant
PrefaceTwelveyearshavepassedsincethefirsteditionofModernCompilerDesign.Formanycomputersciencesubjectsthiswouldbemorethanalifetime,butsincecom-pilerdesignisprobablythemostmaturecomputersciencesubject,itisdifferent.Anadultpersondevelopsmoreslowlyanddifferentlythanatoddlerorateenager,andsodoescompilerdesign.Thepresentbookreflectsthat.Improvementstothebookfallintotwogroups:presentationandcontent.The‘lookandfeel’ofthebookhasbeenmodernized,butmoreimportantlywehaverearrangedsignificantpartsofthebooktopresenttheminamorestructuredmanner:largechaptershavebeensplitandtheoptimizingcodegenerationtechniqueshavebeencollectedinaseparatechapter.Basedonreaderfeedbackandexperiencesinteachingfromthisbook,bothbyourselvesandothers,materialhasbeenexpanded,clarified,modified,ordeletedinalargenumberofplaces.Wehopethatasaresultofthisthereaderfeelsthatthebookdoesabetterjobofmakingcompilerdesignandconstructionaccessible.Thebookaddsnewmaterialtocoverthedevelopmentsincompilerdesignandconstructionoverthelasttwelveyears.Overallthestandardcompilingtechniquesandparadigmshavestoodthetestoftime,butstillnewandoftensurprisingopti-mizationtechniqueshavebeeninvented;existingoneshavebeenimproved;andoldoneshavegainedprominence.Examplesofthefirstare:proceduralabstraction,inwhichroutinesarerecognizedinthecodeandreplacedbyroutinecallstoreducesize;binaryrewriting,inwhichoptimizationsareappliedtothebinarycode;andjust-in-timecompilation,inwhichpartsofthecompilationaredelayedtoimprovetheperceivedspeedoftheprogram.Anexampleofthesecondisatechniquewhichextendsoptimalcodegenerationthroughexhaustivesearch,previouslyavailablefortinyblocksonly,tomoderate-sizebasicblocks.Andanexampleofthethirdistailrecursionremoval,indispensableforthecompilationoffunctionallanguages.ThesedevelopmentsaremainlydescribedinChapter9.Althoughsyntaxanalysisistheonebutoldestbranchofcompilerconstruction(lexicalanalysisbeingtheoldest),eveninthatareainnovationhastakenplace.Generalized(non-deterministic)LRparsing,developedbetween1984and1994,isnowusedincompilers.ItiscoveredinSection3.5.8.Newhardwarerequirementshavenecessitatednewcompilerdevelopments.Themainexamplesaretheneedforsizereductionoftheobjectcode,bothtofitthecodeintosmallembeddedsystemsandtoreducetransmissiontimes;andforlowerpowerv
viPrefaceconsumption,toextendbatterylifeandtoreduceelectricitybills.Dynamicmemoryallocationinembeddedsystemsrequiresabalancebetweenspeedandthrift,andthequestionishowcompilerdesigncanhelp.ThesesubjectsarecoveredinSections9.2,9.3,and10.2.8,respectively.Withagecomeslegacy.Thereismuchlegacycodearound,codewhichissooldthatitcannolongerbemodifiedandrecompiledwithreasonableeffort.Ifthesourcecodeisstillavailablebutthereisnocompileranymore,recompilationmuststartwithagrammarofthesourcecode.Forfiftyyearsprogrammersandcompilerdesignershaveusedgrammarstoproduceandanalyzeprograms;nowlargelegacyprogramsareusedtoproducegrammarsforthem.TherecoveryofthegrammarfromlegacysourcecodeisdiscussedinSection3.6.Ifjustthebinaryexecutableprogramisleft,itmustbedisassembledorevendecompiled.Forfiftyyearscom-pilerdesignershavebeencalledupontodesigncompilersandassemblerstoconvertsourceprogramstobinarycode;nowtheyarecalledupontodesigndisassemblersanddecompilers,torollbacktheassemblyandcompilationprocess.TherequiredtechniquesaretreatedinSections8.4and8.5.ThebibliographyTheliteraturelisthasbeenupdated,butitsusefulnessismorelimitedthanbefore,fortworeasons.Thefirstisthatbythetimeitappearsinprint,theInternetcanpro-videmoreup-to-dateandmoreto-the-pointinformation,inlargerquantities,thanaprintedtextcanhopetoachieve.Itisourcontentionthatanybodywhohasunder-stoodalargerpartoftheideasexplainedinthisbookisabletoevaluateInternetinformationoncompilerdesign.Thesecondisthatmanyofthepaperswerefertoareavailableonlytothosefortunateenoughtohaveloginfacilitiesataninstitutewithsufficientbudgettoobtainsubscriptionstothelargerpublishers;theyarenolongeravailabletojustanyonewhowalksintoauniversitylibrary.Bothphenomenapointtoparadigmshiftswithwhichreaders,authors,publishersandlibrarianswillhavetocope.ThestructureofthebookThisbookisconceptuallydividedintotwoparts.Thefirst,comprisingChapters1through10,isconcernedwithtechniquesforprogramprocessingingeneral;itin-cludesachapteronmemorymanagement,bothinthecompilerandinthegeneratedcode.Thesecondpart,Chapters11through14,coversthespecifictechniquesre-quiredbythevariousprogrammingparadigms.Theinteractionsbetweenthepartsofthebookareoutlinedintheadjacenttable.Theleftmostcolumnshowsthefourphasesofcompilerconstruction:analysis,contexthandling,synthesis,andrun-timesystems.Chaptersinthiscolumncoverboththemanualandtheautomaticcreation
Prefaceviiofthepertinentsoftwarebuttendtoemphasizeautomaticgeneration.Theothercolumnsshowthefourparadigmscoveredinthisbook;foreachparadigmanex-ampleofasubjecttreatedbyeachofthephasesisshown.Thesechapterstendtocontainmanualtechniquesonly,allautomatictechniqueshavingbeendelegatedtoChapters2through9.inimperativeandobject-orientedprograms(Chapter11)infunctionalprograms(Chapter12)inlogicprograms(Chapter13)inparallel/distributedprograms(Chapter14)Howtodo:analysis(Chapters2&3)−−−−−−−−contexthandling(Chapters4&5)identifieridentificationpolymorphictypecheckingstaticrulematchingLindastaticanalysissynthesis(Chapters6–9)codeforwhile-statementcodeforlistcomprehensionstructureunificationmarshalingrun-timesystems(nochapter)stackreductionmachineWarrenAbstractMachinereplicationThescientificmindwouldlikethetabletobeniceandsquare,withallboxesfilled—inshort“orthogonal”—butweseethatthetoprightentriesaremissingandthatthereisnochapterfor“run-timesystems”intheleftmostcolumn.Thetoprightentrieswouldcoversuchthingsasthespecialsubjectsintheprogramtextanalysisoflogiclanguages,butpresenttextanalysistechniquesarepowerfulandflexibleenoughandlanguagessimilarenoughtohandlealllanguageparadigms:thereisnothingtobesaidthere,forlackofproblems.Thechaptermissingfromtheleftmostcolumnwoulddiscussmanualandautomatictechniquesforcreatingrun-timesystems.Unfortunatelythereislittleornotheoryonthissubject:run-timesystemsarestillcraftedbyhandbyprogrammersonanintuitivebasis;thereisnothingtobesaidthere,forlackofsolutions.Chapter1introducesthereadertocompilerdesignbyexaminingasimpletradi-tionalmodularcompiler/interpreterindetail.Severalhigh-levelaspectsofcompilerconstructionarediscussed,followedbyashorthistoryofcompilerconstructionandintroductionstoformalgrammarsandclosurealgorithms.Chapters2and3treattheprogramtextanalysisphaseofacompiler:theconver-sionoftheprogramtexttoanabstractsyntaxtree.Techniquesforlexicalanalysis,lexicalidentificationoftokens,andsyntaxanalysisarediscussed.Chapters4and5coverthesecondphaseofacompiler:contexthandling.Sev-eralmethodsofcontexthandlingarediscussed:automatedonesusingattributegrammars,manualonesusingL-attributedandS-attributedgrammars,andsemi-automatedonesusingsymbolicinterpretationanddata-flowanalysis.
viiiPrefaceChapters6through9coverthesynthesisphaseofacompiler,coveringbothin-terpretationandcodegeneration.Thechaptersoncodegenerationaremainlycon-cernedwithmachinecodegeneration;theintermediatecoderequiredforparadigm-specificconstructsistreatedinChapters11through14.Chapter10concernsmemorymanagementtechniques,bothforuseinthecom-pilerandinthegeneratedprogram.Chapters11through14addressthespecialproblemsincompilingforthevariousparadigms–imperative,object-oriented,functional,logic,andparallel/distributed.Compilersforimperativeandobject-orientedprogramsaresimilarenoughtobetreatedtogetherinonechapter,Chapter11.AppendixBcontainshintsandanswerstoaselectionoftheexercisesinthebook.Suchexercisesaremarkedbyafollowedthepagenumberonwhichtheanswerappears.AlargersetofanswerscanbefoundonSpringer’sInternetpage;thecorrespondingexercisesaremarkedbywww.Severalsubjectsinthisbookaretreatedinanon-traditionalway,andsomewordsofjustificationmaybeinorder.Lexicalanalysisisbasedonthesamedotteditemsthataretraditionallyreservedforbottom-upsyntaxanalysis,ratherthanonThompson’sNFAconstruction.Weseethedotteditemastheessentialtoolinbottom-uppatternmatching,unifyinglexicalanalysis,LRsyntaxanalysis,bottom-upcodegenerationandpeep-holeop-timization.Thetraditionallexicalalgorithmsarejustlow-levelimplementationsofitemmanipulation.Weconsiderthedifferenttreatmentoflexicalandsyntaxanaly-sistobeahistoricalartifact.Also,thedifferencebetweenthelexicalandthesyntaxlevelstendstodisappearinmodernsoftware.Considerableattentionisbeingpaidtoattributegrammars,inspiteofthefactthattheirimpactoncompilerdesignhasbeenlimited.Yettheyaretheonlyknownwayofautomatingcontexthandling,andwehopethatthepresenttreatmentwillhelptolowerthethresholdoftheirapplication.Functionsasfirst-classdataarecoveredinmuchgreaterdepthinthisbookthanisusualincompilerdesignbooks.AfteragoodstartinAlgol60,functionslostmuchstatusasmanipulatabledatainlanguageslikeC,Pascal,andAda,althoughAda95rehabilitatedthemsomewhat.Theimplementationofsomemodernconcepts,forexamplefunctionalandlogiclanguages,iterators,andcontinuations,however,requiresfunctionstobemanipulatedasnormaldata.Thefundamentalaspectsoftheimplementationarecoveredinthechapteronimperativeandobject-orientedlanguages;specificsaregiveninthechaptersonthevariousotherparadigms.Additionalmaterial,includingmoreanswerstoexercises,andalldiagramsandallcodefromthebook,areavailablethroughSpringer’sInternetpage.UseasacoursebookThebookcontainsfartoomuchmaterialforacompilerdesigncourseof13lecturesoftwohourseach,asgivenatouruniversity,soaselectionhastobemade.An
Prefaceixintroductory,moretraditionalcoursecanbeobtainedbyincluding,forexample,Chapter1;Chapter2upto2.7;2.10;2.11;Chapter3upto3.4.5;3.5upto3.5.7;Chapter4upto4.1.3;4.2.1upto4.3;Chapter5upto5.2.2;5.3;Chapter6;Chapter7upto9.1.1;9.1.4upto9.1.4.4;7.3;Chapter10upto10.1.2;10.2upto10.2.4;Chapter11upto11.2.3.2;11.2.4upto11.2.10;11.4upto11.4.2.3.AmoreadvancedcoursewouldincludeallofChapters1to11,possiblyexclud-ingChapter4.ThiscouldbeaugmentedbyoneofChapters12to14.Anadvancedcoursewouldskipmuchoftheintroductorymaterialandconcen-trateonthepartsomittedintheintroductorycourse,Chapter4andallofChapters10to14.AcknowledgmentsWeowemanythankstothefollowingpeople,whosupplieduswithhelp,remarks,wishes,andfoodforthoughtforthisSecondEdition:IngmarAlting,JoséFortes,BertHuijben,JonathanJoubert,SaraKalvala,FrankLippes,PaulS.Moulson,Pras-antK.Patra,CarloPerassi,MarcoRossi,MoolySagiv,GertJanSchoneveld,AjaySingh,EvertWattel,andFreekZindel.Theirinputrangedfromsimplecorrectionstodetailedsuggestionstomassivecriticism.SpecialthanksgotoStefanieScherzinger,whosethoroughandthoughtfulcriticismofouroutlinecodeformatinducedustoimproveitconsiderably;anyremainingimperfectionsshouldbeattributedtostub-bornnessonthepartoftheauthors.ThepresentationoftheprogramcodesnippetsinthebookprofitedgreatlyfromCarstenHeinz’slistingspackage;wethankhimformakingthepackageavailabletothepublic.WearegratefultoAnnKostant,MelissaFearon,andCourtneyClarkofSpringerUS,who,throughfastandcompetentwork,haveclearedmanyobstaclesthatstoodinthewayofpublishingthisbook.Wethankthemfortheireffortandpleasantcooperation.WemournthedeathofIrinaAthanasiu,whodidnotlivelongenoughtolendherexpertiseinembeddedsystemstothisbook.WethanktheFaculteitderExacteWetenschappenoftheVrijeUniversiteitfortheirsupportandtheuseoftheirequipment.Amsterdam,DickGruneMarch2012KeesvanReeuwijkHenriE.BalCerielJ.H.JacobsDelft,KoenG.Langendoen
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
