第1页 / 共570页
第2页 / 共570页
第3页 / 共570页
第4页 / 共570页
第5页 / 共570页
第6页 / 共570页
第7页 / 共570页
第8页 / 共570页
虎书 (Tiger book) Modern Compiler Implementation in Java.pdf
Table of Contents
BackCover
Modern Compiler Implementation in Java, Second Edition
Preface
Part One: Fundamentals of Compilation
Chapter 1: Introduction
1.1 MODULES AND INTERFACES
1.2 TOOLS AND SOFTWARE
1.3 DATA STRUCTURES FOR TREE LANGUAGES
PROGRAM STRAIGHT-LINE PROGRAM INTERPRETER
EXERCISES
Chapter 2: Lexical Analysis
2.1 LEXICAL TOKENS
2.2 REGULAR EXPRESSIONS
2.3 FINITE AUTOMATA
2.4 NONDETERMINISTIC FINITE AUTOMATA
2.5 LEXICAL-ANALYZER GENERATORS
PROGRAM LEXICAL ANALYSIS
FURTHER READING
EXERCISES
Chapter 3: Parsing
3.1 CONTEXT-FREE GRAMMARS
3.2 PREDICTIVE PARSING
3.3 LR PARSING
3.4 USING PARSER GENERATORS
3.5 ERROR RECOVERY
PROGRAM PARSING
FURTHER READING
EXERCISES
Chapter 4: Abstract Syntax
4.1 SEMANTIC ACTIONS
4.2 ABSTRACT PARSE TREES
4.3 VISITORS
PROGRAM ABSTRACT SYNTAX
FURTHER READING
EXERCISES
Chapter 5: Semantic Analysis
5.1 SYMBOL TABLES
5.2 TYPE-CHECKING MiniJava
PROGRAM TYPE-CHECKING
EXERCISES
Chapter 6: Activation Records
HIGHER-ORDER FUNCTIONS
6.1 STACK FRAMES
PROGRAM FRAMES
FURTHER READING
EXERCISES
Chapter 7: Translation to Intermediate Code
7.1 INTERMEDIATE REPRESENTATION TREES
7.2 TRANSLATION INTO TREES
7.3 DECLARATIONS
PROGRAM TRANSLATION TO TREES
EXERCISES
Chapter 8: Basic Blocks and Traces
8.1 CANONICAL TREES
8.2 TAMING CONDITIONAL BRANCHES
FURTHER READING
EXERCISES
Chapter 9: Instruction Selection
TREE PATTERNS
OPTIMAL AND OPTIMUM TILINGS
9.1 ALGORITHMS FOR INSTRUCTION SELECTION
9.2 CISC MACHINES
9.3 INSTRUCTION SELECTION FOR THE MiniJava COMPILER
PROGRAM INSTRUCTION SELECTION
FURTHER READING
EXERCISES
Chapter 10: Liveness Analysis
10.1 SOLUTION OF DATAFLOW EQUATIONS
10.2 LIVENESS IN THE MiniJava COMPILER
PROGRAM CONSTRUCTING FLOW GRAPHS
PROGRAM LIVENESS
EXERCISES
Chapter 11: Register Allocation
11.1 COLORING BY SIMPLIFICATION
11.2 COALESCING
11.3 PRECOLORED NODES
11.4 GRAPH-COLORING IMPLEMENTATION
11.5 REGISTER ALLOCATION FOR TREES
PROGRAM GRAPH COLORING
FURTHER READING
EXERCISES
Chapter 12: Putting It All Together
PROGRAM PROCEDURE ENTRY/EXIT
PROGRAM MAKING IT WORK
Part Two: Advanced Topics
Chapter 13: Garbage Collection
13.1 MARK-AND-SWEEP COLLECTION
13.2 REFERENCE COUNTS
13.3 COPYING COLLECTION
13.4 GENERATIONAL COLLECTION
13.5 INCREMENTAL COLLECTION
13.6 BAKER'S ALGORITHM
13.7 INTERFACE TO THE COMPILER
PROGRAM DESCRIPTORS
PROGRAM GARBAGE COLLECTION
FURTHER READING
EXERCISES
Chapter 14: Object-Oriented Languages
14.1 CLASS EXTENSION
14.2 SINGLE INHERITANCE OF DATA FIELDS
14.3 MULTIPLE INHERITANCE
14.4 TESTING CLASS MEMBERSHIP
14.5 PRIVATE FIELDS AND METHODS
14.6 CLASSLESS LANGUAGES
14.7 OPTIMIZING OBJECT-ORIENTED PROGRAMS
PROGRAM MiniJava WITH CLASS EXTENSION
FURTHER READING
EXERCISES
Chapter 15: Functional Programming Languages
15.1 A SIMPLE FUNCTIONAL LANGUAGE
15.2 CLOSURES
15.3 IMMUTABLE VARIABLES
15.4 INLINE EXPANSION
15.5 CLOSURE CONVERSION
15.6 EFFICIENT TAIL RECURSION
15.7 LAZY EVALUATION
PROGRAM COMPILING FUNCTIONAL LANGUAGES
EXERCISES
Chapter 16: Polymorphic Types
16.1 PARAMETRIC POLYMORPHISM
16.2 POLYMORPHIC TYPE-CHECKING
16.3 TRANSLATION OF POLYMORPHIC PROGRAMS
16.4 RESOLUTION OF STATIC OVERLOADING
FURTHER READING
EXERCISES
Chapter 17: Dataflow Analysis
NO MAGIC BULLET
17.1 INTERMEDIATE REPRESENTATION FOR FLOW ANALYSIS
17.2 VARIOUS DATAFLOW ANALYSES
17.3 TRANSFORMATIONS USING DATAFLOW ANALYSIS
17.4 SPEEDING UP DATAFLOW ANALYSIS
17.5 ALIAS ANALYSIS
FURTHER READING
EXERCISES
Chapter 18: Loop Optimizations
REDUCIBLE FLOW GRAPHS
18.1 DOMINATORS
18.2 LOOP-INVARIANT COMPUTATIONS
18.5 LOOP UNROLLING
FURTHER READING
EXERCISES
Chapter 19: Static Single-Assignment Form
19.1 CONVERTING TO SSA FORM
19.2 EFFICIENT COMPUTATION OF THE DOMINATOR TREE
19.3 OPTIMIZATION ALGORITHMS USING SSA
19.5 THE CONTROL-DEPENDENCE GRAPH
19.6 CONVERTING BACK FROM SSA FORM
19.7 A FUNCTIONAL INTERMEDIATE FORM
FURTHER READING
EXERCISES
Chapter 20: Pipelining and Scheduling
20.1 LOOP SCHEDULING WITHOUT RESOURCE BOUNDS
20.2 RESOURCE-BOUNDED LOOP PIPELINING
20.3 BRANCH PREDICTION
FURTHER READING
EXERCISES
Chapter 21: The Memory Hierarchy
21.1 CACHE ORGANIZATION
21.2 CACHE-BLOCK ALIGNMENT
21.3 PREFETCHING
21.4 LOOP INTERCHANGE
21.5 BLOCKING
21.6 GARBAGE COLLECTION & THE MEMORY HIERARCHY
FURTHER READING
EXERCISES
Appendix A: MiniJava Language Reference Manual
A.2 GRAMMAR
A.3 SAMPLE PROGRAM
Bibliography
Index
Index_B
Index_C
Index_D-E
Index_F
Index_G
Index_H
Index_I
Index_J
Index_K
Index_L
Index_M
Index_N
Index_O
Index_P
Index_Q
Index_R
Index_S
Index_T
Index_U
Index_V
Index_W-X
Index_Y-Z
List of Figures
List of Tables
List of Examples
Team-Fly
Modern Compiler Implementation in Java, Second
Edition
by Andrew W.
Appel and Jens Palsberg
Cambridge University Press © 2002 (501 pages)
ISBN:052182060x
This textbook describes all phases of a compiler, and
thorough coverage of current techniques in code
generation and register allocation, and the compilation of
functional and object-oriented languages.
-
Introduction
- Lexical Analysis
Table of Contents
Modern Compiler Implementation in Java, Second Edition
Preface
Part One - Fundamentals of Compilation
Ch
apt
er
1
Ch
apt
er
2
Ch
apt
er
3
Ch
apt
er
4
Ch
apt
er
5
Ch
apt
er
6
Ch
apt
er
7
Ch
apt
er
8
- Translation to Intermediate Code
- Basic Blocks and Traces
- Activation Records
- Parsing
- Abstract Syntax
- Semantic Analysis
- Liveness Analysis
- Register Allocation
- Putting It All Together
- Garbage Collection
-
Instruction Selection
Ch
apt
er
9
Ch
apt
er
10
Ch
apt
er
11
Ch
apt
er
12
Part Two - Advanced Topics
Ch
apt
er
13
Ch
apt
er
14
Ch
apt
er
15
Ch
apt
er
16
Ch
apt
er
17
Ch
apt
er
18
Ch
apt
er
19
Ch
apt
er
20
- Loop Optimizations
- Polymorphic Types
- Dataflow Analysis
- Object-Oriented Languages
- Functional Programming Languages
- Static Single-Assignment Form
- Pipelining and Scheduling
- The Memory Hierarchy
- MiniJava Language Reference Manual
Ch
apt
er
21
Ap
pe
ndi
x
A
Bibliography
Index
List of Figures
List of Tables
List of Examples
Team-Fly
Team-Fly
Back Cover
This textbook describes all phases of a compiler: lexical analysis, parsing, abstract syntax, semantic actions,
intermediate representations, instruction selection via tree matching, dataflow analysis, graph-coloring register
allocation, and runtime systems. It includes good coverage of current techniques in code generation and register
allocation, as well as the compilation of functional and object-oriented languages, which is missing from most books.
The most accepted and successful techniques are described concisely, rather than as an exhaustive catalog of every
possible variant. Detailed descriptions of the interfaces between modules of a compiler are illustrated with actual
Java classes.
The first part of the book, Fundamentals of Compilation, is suitable for a one-semester first course in compiler
design. The second part, Advanced Topics, which includes the compilation of object-oriented and functional
languages, garbage collection, loop optimization, SSA form, instruction scheduling, and optimization for
cache-memory hierarchies, can be used for a second-semester or graduate course.
This new edition has been rewritten extensively to include more discussion of Java and object-oriented programming
concepts, such as visitor patterns. A unique feature in the newly redesigned compiler project in Java for a subset of
Java itself. The project includes both front-end and back-end phases, so that students can build a complete working
compiler in one semester.
About the Authors
Andrew W. Appel is Professor of Computer Science at Princeton University. He has done research and published
papers on compilers, functional programming languages, runtime systems and garbage collection, type systems, and
computer security; he is also the author of the book Compiling with Continuations. He is a designer and founder
of the Standard ML of New Jersey project. In 1998, Appel was elected a Fellow of the Association for Computing
Machinery for significant research contributions in the area of programming languages and compilers and for his
work as editor-in-chief (1993-7) of the ACM Transactions on Programming Languages and Systems, the
leading journal in the field of compilers and programming languages.
Hens Palsberg is Associate Professor of Computer Science at Purdue University. His research interests are
programming languages, compilers, software engineering, and information security. He has authored more than 50
technical papers in these areas and a book with Michael Schwartzbach, Object-Oriented Type Systems. In 1998,
he received the National Science Foundation Faculty Early Career Development Award, and in 1999, the Purdue
University Faculty award.
Team-Fly
Team-Fly
Modern Compiler
Implementation in Java, Second
Edition
Andrew W. Appel Princeton University
Jens Palsberg Purdue University
CAMBRIDGE
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 Alarcón 13, 28014 Madrid, Spain
Dock House, The Waterfront, Cape Town 8001, South Africa
http://www.cambridge.org
Copyright © 2002 Cambridge University Press
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 edition published 1998
Second edition published 2002
Typefaces Times, Courier, and Optima System LATEX[AU]
A catalog record for this book is available from the British Library.
Library of Congress Cataloging in Publication data
Appel, Andrew W., 1960-
Modern compiler implementation in Java /
Andrew W. Appel with Jens Palsberg.-
[2nd ed.]
p. cm.
Includes bibliographical references and index.
0-521-82060-X
1. Java (Computer program language) 2. Compilers (Computer programs) I. Palsberg,
Jens. II. Title.
QA76.73.J38 A65 2002
005.4 53-dc21
2002073453
ISBN 0 521 58274 1 Modern Compiler Implementation in ML (first edition, hardback)
ISBN 0 521 82060 X Modern Compiler Implementation in Java (hardback)
This textbook describes all phases of a compiler: lexical analysis, parsing, abstract syntax, semantic actions,
intermediate representations, instruction selection via tree matching, dataflow analysis, graphcoloring register
allocation, and runtime systems. It includes good coverage of current techniques in code generation and register
allocation, as well as the compilation of functional and object-oriented languages, which is missing from most books.
The most accepted and successful techniques are described concisely, rather than as an exhaustive catalog of every
possible variant. Detailed descriptions of the interfaces between modules of a compiler are illustrated with actual Java
classes.
The first part of the book, Fundamentals of Compilation, is suitable for a one-semester first course in compiler
design. The second part, Advanced Topics, which includes the compilation of object-oriented and functional
languages, garbage collection, loop optimization, SSA form, instruction scheduling, and optimization for
cache-memory hierarchies, can be used for a second-semester or graduate course.
This new edition has been rewritten extensively to include more discussion of Java and object-oriented programming
concepts, such as visitor patterns. A unique feature is the newly redesigned compiler project in Java for a subset of
Java itself. The project includes both front-end and back-end phases, so that students can build a complete working
compiler in one semester.
Andrew W. Appel is Professor of Computer Science at Princeton University. He has done research and published
papers on compilers, functional programming languages, runtime systems and garbage collection, type systems, and
computer security; he is also author of the book Compiling with Continuations. He is a designer and founder of the
Standard ML of New Jersey project. In 1998, Appel was elected a Fellow of the Association for Computing
Machinery for "significant research contributions in the area of programming languages and compilers" and for his
work as editor-in-chief (1993-97) of the ACM Transactions on Programming Languages and Systems, the
leading journal in the field of compilers and programming languages.
Jens Palsberg is Associate Professor of Computer Science at Purdue University. His research interests are
programming languages, compilers, software engineering, and information security. He has authored more than 50
technical papers in these areas and a book with Michael Schwartzbach, Object-oriented Type Systems. In 1998, he
received the National Science Foundation Faculty Early Career Development Award, and in 1999, the Purdue
University Faculty Scholar award.
Team-Fly
Team-Fly
Preface
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,
we have written them in Java. Another edition of this book is available that uses the ML language.
Implementation project The "student project compiler" that we have out-lined is reasonably simple, but is
organized to demonstrate some important techniques that are now in common use: abstract syntax trees to avoid
tangling syntax and semantics, separation of instruction selection from register allocation, copy propagation to give
flexibility to earlier phases of the compiler, and containment of target-machine dependencies. Unlike many "student
compilers" found in other textbooks, this one has a simple but sophisticated back end, allowing good register
allocation to be done after instruction selection.
This second edition of the book has a redesigned project compiler: It uses a subset of Java, called MiniJava, as the
source language for the compiler project, it explains the use of the parser generators JavaCC and SableCC, and it
promotes programming with the Visitor pattern. Students using this edition can implement a compiler for a language
they're familiar with, using standard tools, in a more object-oriented style.
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://uk.cambridge.org/resources/052182060X (outside North America);
http://us.cambridge.org/titles/052182060X.html (within North America).
Exercises Each chapter has pencil-and-paper exercises; those marked with a star are more challenging, two-star
problems are difficult but solvable, and the occasional three-star exercises are not known to have a solution.
Course sequence The figure shows how the chapters depend on each other.
•
相关推荐
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
