A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition), страница 5

Vidyut Samanta helped tremendously with both the text and the softwarefor the new edition of the book. We would also like to thank Leonor Abraido-Fandino, ScottAnanian, Nils Andersen, Stephen Bailey, Joao Cangussu, Maia Ginsburg, Max Hailperin,David Hanson, Jeffrey Hsu, David MacQueen, Torben Mogensen, Doug Morgan, RobertNetzer, Elma Lee Noah, Mikael Petterson, Benjamin Pierce, Todd Proebsting, Anne Rogers,Barbara Ryder, Amr Sabry, Mooly Sagiv, Zhong Shao, Mary Lou Soffa, Andrew Tolmach,Kwangkeun Yi, and Kenneth Zadeck.10Part One: Fundamentals of CompilationChapter ListChapter 1: IntroductionChapter 2: Lexical AnalysisChapter 3: ParsingChapter 4: Abstract SyntaxChapter 5: Semantic AnalysisChapter 6: Activation RecordsChapter 7: Translation to Intermediate CodeChapter 8: Basic Blocks and TracesChapter 9: Instruction SelectionChapter 10: Liveness AnalysisChapter 11: Register AllocationChapter 12: Putting It All Together11Chapter 1: IntroductionA compiler was originally a program that "compiled" subroutines [a link-loader].

When in1954 the combination "algebraic compiler" came into use, or rather into misuse, the meaningof the term had already shifted into the present one.Bauer and Eickel [1975]OVERVIEWThis book describes techniques, data structures, and algorithms for translating programminglanguages into executable code. A modern compiler is often organized into many phases, eachoperating on a different abstract "language." The chapters of this book follow the organizationof a compiler, each covering a successive phase.To illustrate the issues in compiling real programming languages, we show how to compileMiniJava, a simple but nontrivial subset of Java.

Programming exercises in each chapter callfor the implementation of the corresponding phase; a student who implements all the phasesdescribed in Part I of the book will have a working compiler. MiniJava is easily extended tosupport class extension or higher-order functions, and exercises in Part II show how to do this.Other chapters in Part II cover advanced techniques in program optimization.

Appendix Adescribes the MiniJava language.The interfaces between modules of the compiler are almost as important as the algorithmsinside the modules. To describe the interfaces concretely, it is useful to write them down in areal programming language. This book uses Java - a simple object-oriented language.

Java issafe, in that programs cannot circumvent the type system to violate abstractions; and it hasgarbage collection, which greatly simplifies the management of dynamic storage allocation.Both of these properties are useful in writing compilers (and almost any kind of software).This is not a textbook on Java programming. Students using this book who do not know Javaalready should pick it up as they go along, using a Java programming book as a reference.Java is a small enough language, with simple enough concepts, that this should not be difficultfor students with good programming skills in other languages.1.1 MODULES AND INTERFACESAny large software system is much easier to understand and implement if the designer takescare with the fundamental abstractions and interfaces.

Figure 1.1 shows the phases in a typicalcompiler. Each phase is implemented as one or more software modules.12Figure 1.1: Phases of a compiler, and interfaces between them.Breaking the compiler into this many pieces allows for reuse of the components. For example,to change the target machine for which the compiler produces machine language, it suffices toreplace just the Frame Layout and Instruction Selection modules. To change the sourcelanguage being compiled, only the modules up through Translate need to be changed. Thecompiler can be attached to a language-oriented syntax editor at the Abstract Syntax interface.The learning experience of coming to the right abstraction by several iterations of thinkimplement-redesign is one that should not be missed.

However, the student trying to finish acompiler project in one semester does not have this luxury. Therefore, we present in this bookthe outline of a project where the abstractions and interfaces are carefully thought out, and areas elegant and general as we are able to make them.Some of the interfaces, such as Abstract Syntax, IR Trees, and Assem, take the form of datastructures: For example, the Parsing Actions phase builds an Abstract Syntax data structureand passes it to the Semantic Analysis phase. Other interfaces are abstract data types; theTranslate interface is a set of functions that the Semantic Analysis phase can call, and theTokens interface takes the form of a function that the Parser calls to get the next token of theinput program.DESCRIPTION OF THE PHASESEach chapter of Part I of this book describes one compiler phase, as shown in Table 1.2Chapter PhaseTable 1.2: Description of compiler phases.Description2Break the source file into individual words, or tokens.Lex13Chapter PhaseTable 1.2: Description of compiler phases.Description3ParseAnalyze the phrase structure of the program.4SemanticActionsBuild a piece of abstract syntax tree corresponding to each phrase.5SemanticAnalysisDetermine what each phrase means, relate uses of variables to theirdefinitions, check types of expressions, request translation of eachphrase.6Frame Layout Place variables, function-parameters, etc.

into activation records(stack frames) in a machine-dependent way.7TranslateProduce intermediate representation trees (IR trees), a notation thatis not tied to any particular source language or target-machinearchitecture.8CanonicalizeHoist side effects out of expressions, and clean up conditionalbranches, for the convenience of the next phases.9InstructionSelectionGroup the IR-tree nodes into clumps that correspond to the actionsof target-machine instructions.10Control FlowAnalysisAnalyze the sequence of instructions into a control flow graph thatshows all the possible flows of control the program might followwhen it executes.10DataflowAnalysisGather information about the flow of information through variablesof the program; for example, liveness analysis calculates the placeswhere each program variable holds a still-needed value (is live).11RegisterAllocationChoose a register to hold each of the variables and temporary valuesused by the program; variables not live at the same time can sharethe same register.12Code Emission Replace the temporary names in each machine instruction withmachine registers.This modularization is typical of many real compilers.

But some compilers combine Parse,Semantic Analysis, Translate, and Canonicalize into one phase; others put InstructionSelection much later than we have done, and combine it with Code Emission. Simple14compilers omit the Control Flow Analysis, Data Flow Analysis, and Register Allocationphases.We have designed the compiler in this book to be as simple as possible, but no simpler. Inparticular, in those places where corners are cut to simplify the implementation, the structureof the compiler allows for the addition of more optimization or fancier semantics withoutviolence to the existing interfaces.1.2 TOOLS AND SOFTWARETwo of the most useful abstractions used in modern compilers are contextfree grammars, forparsing, and regular expressions, for lexical analysis. To make the best use of theseabstractions it is helpful to have special tools, such as Yacc (which converts a grammar into aparsing program) and Lex (which converts a declarative specification into a lexical-analysisprogram).

Fortunately, such tools are available for Java, and the project described in this bookmakes use of them.The programming projects in this book can be compiled using any Java compiler. The parsergenerators JavaCC and SableCC are freely available on the Internet; for information see theWorld Wide Web pagehttp://uk.cambridge.org/resources/052182060X (outside North America);http://us.cambridge.org/titles/052182060X.html (within North America).Source code for some modules of the MiniJava compiler, skeleton source code and supportcode for some of the programming exercises, example MiniJava programs, and other usefulfiles are also available from the same Web address.