Crafting a Compiler

【实例简介】
超清晰，非扫描 CHARLES N.FISCHER,RON K.CYTRON,RICHARD J.LwBLANC.Jr共同编写的有关编译器的经典教材，国外计算机科学使用的教材。
Editor-in-Chief: Michael hirsch Acquisitions Editor: Matt Goldstein Editorial assistant: Chelsea bell Managing editor: Jeff Holcomb Director of Marketing: Margaret Waples Marketing manager: Erin Davis Marketing Coordinator: Kathryn ferranti Media Producer: Katelyn boller Senior manufacturing buyer: Carol melville Senior Media Buyer: Ginny Michaud Art Director: Linda knowles Cover Designer: Elena Sidorova Printer/Binder: Hamilton Printing co Cover Printer: Lehigh Phoenix hagerstown Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and Addison-Wesley was aware of a trademark claim, the designations have been printed in initial caps or all caps The programs and applications presented in this book have been included for their instructional value They have been tested with care, but are not guaranteed for any particular purpose. The publisher does not offer any warranties or representations, nor does it accept any liabilities with respect to the programs or applications Library of Congress Cataloging-in-Publication Data Fischer. Charles N Crafting a compiler /Charles N. Fischer, Ron K. Cytron, Richard J. LeBlanc, Jr p cm.--( Crafting a compiler with C) Includes bibliographical references and index ISBN978-0-13-606705-4(alk. paper) 1. Compilers(Computer programs)I Cytron, Ron K. Ronald Kaplan), 1958-IL LeBlanc, Richard J (Richard Joseph),1950-IlI. Title QA76.76.C65F572009 005453-dc22 2009038265 Copyright c 2010 Pearson Education, Inc. publishing as addison- Wesley. all rights reserved Manufactured in the United States of America. This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying recording, or likewise. To obtain permission(s)to use material from this work, please submit a written request to Pearson Education, Inc, Permissions Department, 501 Boylston Street, Suite 900, Boston Massachusetts. 02116 10987654321-HA-1312111009 Addison-Wesley is an imprint of PEARSON ISBN10:0-13-606705-0 www.pearsonhighered.com ISBN13:978-0-13-606705-4 Preface Much has changed since Crafting a Compiler, by Fischer and LeBlanc, was published in 1988. While instructors may remember the 52-inch floppy disk of software that accompanied that text, most students today have neither seen nor held such a disk. Many changes have occurred in the programming languages that students experience in class and in the marketplace. In 1991 the book was available in two forms, with algorithms presented in either C or Ada While c remains a popular language, Ada has become relatively obscure and did not achieve its predicted popularity. The C++ language evolved from C with the addition of object-oriented features. J was developed as a simpler object-oriented language, gaining popularity because of its security and ability to be run within a Web browser. The College Board Advanced Placement curriculum moved from Pascal to C++ to Java While much has changed, students and faculty alike continue to study and teach the subject of compiler construction. Research in the area of compilers and programing language translation continues at a brisk pace, as compilers are tasked with accommodating an increasing diversity of architectures and programming languages. Software development environments depend on compilers interacting successfully with a variety of software toolchain compo nents such as syntax-informed editors, performance profilers, and debuggers All modern software efforts rely on their compilers to check vigorously for errors and to translate programs faithfully Some texts experience relatively minor changes over time, acquiring per haps some new exercises or examples. This book reflects a substantive revision of the material from 1988 and 1991. While the focus of this text remains on teaching the fundamentals of compiler construction, the algorithms and ap- proaches have been brought into modern practice Coverage of topics that have faded from practical use(e.g,attribute grammars)has been minimized or removed altogether Algorithms are presented in a pseudocode style that should be familiar to students who have studied the fundamental algorithms of our discipline Preface Pseudocode enables a concise formulation of an algorithm and a rational discussion of the algorithm's purpose and construction The details of implementation in a particular language have been rele gated to the Crafting a Compiler Supplement which is available online http://www.pearsonhighered.com/fischer/ Parsing theory and practice are organized to facilitate a variety of peda gogical approaches Some may study the material at a high level to gain a broad view of top down and bottom-up parsing. Others may study a particular approach in greater detail The front- and back-end phases of a compiler are connected by the ab stract syntax tree(Ast), which is created as the primary artifact of pars- ing. Most compilers build an AST, but relatively few texts articulate its construction and use The visitor pattern is introduced for traversing the ast during semantic analysis and code generation Laboratory and studio exercises are available to instructors Instructors can assign some components as exercises for the students while other components are supplied from our course-support Web site Some texts undergo revision by the addition of more graduate-level material While such information may be useful in an advanced course, the focus of Crafting a Compiler remains on the undergraduate-level study of compiler con- struction. A graduate course could be offered using Chapters 13 and 14, with the earlier portions of the text serving as reference material Text and reference As a classroom text, this book is oriented toward a curriculum that we have developed over the past 25 years. The book is very flexible and has been adopted for courses ranging from a three-credit upper-level course taught in a ten-week quarter to a six-credit semester-long graduate course. The text is accessible to any student who has a basic background in programming, algorithms, and data structures. The text is well suited to a single semester or quarter offering because its flexibility allows an instructor to craft a syllabus according to his or her interests. Author-sponsored solutions are available for those components that are not studied in detail. It is feasible to write portions of a compiler from parsing to code generation in a single semester Preface This book is also a valuable professional reference because of its complete coverage of techniques that are of practical importance to compiler construc- tion. Many of our students have reported, even some years after their grad- uation, of their successful application of these techniques to problems they encounter in their work Instructor resources TheWebsiteforthisbookcanbefoundathttp://www.pearsonhighered com/fischer/. The material posted for qualified instructors includes sample laboratory and project assignments, studio(active-learning) sessions, libraries of code that can be used as class-furnished solutions, and solutions to selected exercises For access to these materials qualified instructors should contact their localPearsonRepresentativebyvisitinghttp://www.pearsonhighered.com bysendingemailtocomputing@aw.com,orbyvisitingthePearsonInstructor ResourceCenterathttp://www.pearsonhighered.com/irc/ Student resources THebooksWebsiteathttp://www.pearsonhighered.com/fischer/contains working code for examples used throughout the book, including code for the toy language ac that is introduced in Chapter 2. The site also contains tutorial notes and a page with links to various compiler-construction tools Access to these materials may be guarded by a password that is distributed with the book or obtained from an instructor Project Approach This book offers a comprehensive coverage of relevant theoretical topics in compiler construction. However, a cohesive implementation project is typi cally an important aspect of planning a curriculum in compiler construction Thus the book and the online materials are biased in favor of a sequence of exploratory exercises, culminating in a project, to support learning this mate ria Lab exercises, studio sessions, and course projects appear in the crafting a Compiler supplement, and readers are invited to send us other materials or links for posting at our Web site. The exercises parallel the chapters and progression of material presented in the text. For example, Chapter 2 introduces the toy Preface language ac to give an overview of the compilation process. The Web site contains full, working versions of the scanner parser, semantics analyzer, and code generator for that language. These components will be available in a variety of source programming languages The Web site also offers material in support of developing a working compiler for a simple language modeled after Java. This allows instructors to assign some components as exercises while other components are provided to fill in any gaps. Some instructors may provide the entire compiler and ask students to implement extensions. Polishing and refining existing components can also be the basis of class projects Pseudocode and guides A significant change from the Fischer and Leblanc text is that algorithms are no longer presented in any specific programming language such as C or Ada. Instead, algorithms are presented in pseudocode using a style that should be familiar to those who have studied even the most fundamental algorithms [CLRSo1]. Pseudocode simplifies the exposition of an algorithm by omitting unnecessary detail. However, the pseudocode is suggestive of constructs used in real programming languages, so implementation should be straightforward. An index of all pseudocode methods is provided as a guide at the end of this book The text makes extensive use of abbreviations(including acronyms)to simplify exposition and to help readers acquire the terminology used in com iler construction. Each abbreviation is fully defined automatically at its first PI reference in each chapter. For example, AST has already been used in this pref- ace, as an abbreviation of abstract syntax tree, but context-free grammar(CFG has not. For further help, an index of all abbreviations appears as a guide at the end of the book. The full index contains abbreviations and indicates where they are referenced throughout the book. Terms such as guide are shown in boldface. Each reference to such terms is included in the full index USing this Book An introductory course on compiler construction could begin with Chapters 1 2, and 3. For parsing technique, either top-down( Chapter 5)or bottom-up Chapter 6)could be chosen, but some instructors will choose to cover both Material from Chapter 4 can be covered as necessary to support the parsing techniques that will be studied. Chapter 7 articulates the ASt and presents the visitor pattern for its traversal. Some instructors may assign AST-management utilities as a lab exercise, while others may use the utilities provided by the Preface Web site. Various aspects of semantic analysis can then be covered at the instructors discretion in Chapters 8 and 9. a quarter-based course could end here, with another quarter continuing with the study of code generation, as described next Chapter 10 provides an overview of the java Virtual Machine VM), which should be covered if students will generate JVM code in their project Code generation for such virtual machines is covered in Chapter l1. Instructors who prefer students to generate machine code could skip Chapters 10 and 11 and cover Chapters 12 and 13 instead. An introductory course could includ material from the beginning of chapter 14 on automatic program optimization Further study could include more detail of the parsing techniques covered Chapters 4, 5, and 6. Semantic analysis and type checking could be studied in greater breadth and depth in Chapters 8 and 9. Advanced concepts such as static single assignment (SSA) Form could be introduced from Chapters 10 and 14. Advanced te d transformati lud ing data flow frameworks, could be drawn from Chapter 14. Chapters 13 and 14 could be the basis for a gradute compiler course, with earlier chapters providing useful reference material Chapter descriptions Chapter 1 Introduction The text begins with an overview of the compilation process. The concepts of constructing a compiler from a collection of components are emphasized An overview of the history of compilers is presented and the use of tools for enerating compiler components is introduced Chapter 2 A Simple compiler The simple language ac is presented, and each of the compiler's components is discussed with respect to translating ac to another language, dc. These components are presented in pseudocode and complete code can be found in the Crafting a Compiler supplement Chapter 3 Scanning-Theory and Practice The basic concepts and techniques for building the lexical analysis components of a compiler are presented. This discussion includes the development of hand- coded scanners as well as the use of scanner-generation tools for implementing table-driven lexical analyzers hapter 4 Grammars and Parsing This chapter covers the fundamentals of formal language concepts, includ ing context-free grammars, grammar notation, derivations, and parse trees Grammar-analysis algorithms are introduced that are used in Chapters 5 and 6 Preface Chapter 5 Top-Down Parsing Top-down parsing is a popular technique for constructing relatively simple parsers. This chapter shows how such parsers can be written using explicit code or by constructing a table for use by a generic top-down parsing engine Syntactic error diagnosis, recovery, and repair are discussed Chapter 6 Bottom-up parsing Most compilers for modern programming languages use one of the bottom up parsing techniques presented in this chapter. Tools for generating such parsers automatically from a context-free grammar are widely available. The hapter describes the theory on which such tools are built, including a sequence of increasingly sophisticated approaches to resolving conflicts that hamper parser construction for some grammars. Grammar and language ambiguity are thoroughly discussed, and heuristics are presented for understanding and resolving ambiguous grammars Chapter 7 Syntax-Directed Translation This marks the mid-point of the book in terms of a compiler's components Prior chapters have considered the lexical and syntactic analysis of programs a goal of those chapters is the construction of an AST. In this chapter, the AST is introduced and an interface is articulated for constructing, managing, and traversing the AST. This chapter is pivotal in the sense that subsequent chapters depend on understanding both the ast and the visitor pattern that facilitates traversal and processing of the AST. The Crafting a Compiler Supple ment contains a tutorial on the visitor pattern, including examples drawn from common experiences Chapter8 Symbol Tables and Declaration Processing This chapter emphasizes the use of a symbol table as an abstract component that can be utilized throughout the compilation process. A precise interface is defined for the symbol table and various implementation issues and ideas are presented. This discussion includes a study of the implementation of nested scopes The semantic analysis necessary for processing symbol declarations is in troduced, including types, variables, arrays, structures, and enumerations. An introduction to type checking is presented, including object-oriented classes, subclasses and superclasses Chapter9 Semantic Analysis Additional semantic analysis is required for language specifications that are not easily checked while parsing. Various control structures are examined including conditional branches and loops. The chapter includes a discussion of exceptions and the semantic analysis they require at compile-time Preface Chapter 10 Intermediate representations This chapter considers two intermediate representations areare widely used by compilers. The first is the JVM instruction set and bytecode format, which has become the standard format for representing compiled Java programs For readers who are interested in targeting the JVM in a compiler project, Chapters 10 and 11 provide the necessary background and techniques. The other representation is SSA Form, which is used by many optimizing com pilers. This chapter defines SSA Form, but its construction is delayed until Chapter 14, where some requisite definitions and algorithms are presented Chapter 11 Code Generation for a Virtual machine This chapter considers code generation for a virtual machine (VM). The ad vantages of considering such a target is that many of the details of runtime support are subsumed by the VM. For example, most VMs offer an unlimited number of registers, so that the issue of register allocation, albeit interesting, can be postponed until the fundamentals of code generation are mastered The VM's instruction set is typically at a higher level than machine code. For example, a method call is often supported by a single vm instruction while the same call would require many more instructions in machine code While an eager reader interested in generating machine code may be tempted to skip Chapter 11, we recommend studying this chapter before attempting code generation at the machine-code level. The ideas from this chapter are easily applied to Chapters 12 and 13, but they are easier to under stand from the perspective of a VM Chapter 12 Runtime Support Much of the functionality embedded in a VM is its runtime support (e. g its support for managing storage). This chapter discusses various concepts and implementation strategies for providing the runtime support needed for modern programming languages. Study of this material can provide an un derstanding of the construction of a VM. For those who write code generators for a target architecture( Chapter 13), runtime support must be provided, so the study of this material is essential to creating a working compiler The chapter includes discussion of storage that is statically allocated, stack allocated, and heap allocated. References to nonlocal storage are considered along with implementation structures such as frames and displays to support such references Chapter 13 Target Code generation This chapter is similar to Chapter 11, except that the target of code generation is a relatively low-level instruction set when compared with a vM. The chapter includes a thorough discussion of topics that arise in such code generation including register allocation, management of temporaries, code scheduling instruction selection, and some basic peephole optimization 【实例截图】
【核心代码】