Modern Compiler Implementation In Java. Second Edition
Team-FlyModern Compiler Implementation in Java, SecondEditionby Andrew W.ISBN:052182060xAppel and Jens PalsbergCambridge University Press 2002 (501 pages)This textbook describes all phases of a compiler, andthorough coverage of current techniques in codegeneration and register allocation, and the compilation offunctional and object-oriented languages.Table of ContentsModern Compiler Implementation in Java, Second EditionPrefacePart One - Fundamentals of CompilationChapt- Introductioner1Chapt- Lexical Analysiser2Chapt- Parsinger3Chapt- Abstract Syntaxer4Chapt- Semantic Analysiser5Chapt- Activation Recordser6Chapt- Translation to Intermediate Codeer7Chapt- Basic Blocks and Traceser8
Chapt- Instruction Selectioner9Chapt- Liveness Analysiser10Chapt- Register Allocationer11Chapt- Putting It All Togetherer12Part Two - Advanced TopicsChapt- Garbage Collectioner13Chapt- Object-Oriented Languageser14Chapt- Functional Programming Languageser15Chapt- Polymorphic Typeser16Chapt- Dataflow Analysiser17Chapt- Loop Optimizationser18Chapt- Static Single-Assignment Former19Chapt- Pipelining and Schedulinger20
Chapt- The Memory Hierarchyer21Appendi - MiniJava Language Reference ManualxABibliographyIndexList of FiguresList of TablesList of ExamplesTeam-Fly
Team-FlyBack CoverThis 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 registerallocation, and runtime systems. It includes good coverage of current techniques in code generation and registerallocation, 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 everypossible variant. Detailed descriptions of the interfaces between modules of a compiler are illustrated with actualJava classes.The first part of the book, Fundamentals of Compilation, is suitable for a one-semester first course in compilerdesign. The second part, Advanced Topics, which includes the compilation of object-oriented and functionallanguages, garbage collection, loop optimization, SSA form, instruction scheduling, and optimization forcache-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 programmingconcepts, such as visitor patterns. A unique feature in the newly redesigned compiler project in Java for a subset ofJava itself. The project includes both front-end and back-end phases, so that students can build a complete workingcompiler in one semester.About the AuthorsAndrew W. Appel is Professor of Computer Science at Princeton University. He has done research and publishedpapers on compilers, functional programming languages, runtime systems and garbage collection, type systems, andcomputer security; he is also the author of the book Compiling with Continuations. He is a designer and founderof the Standard ML of New Jersey project. In 1998, Appel was elected a Fellow of the Association for ComputingMachinery for significant research contributions in the area of programming languages and compilers and for hiswork as editor-in-chief (1993-7) of the ACM Transactions on Programming Languages and Systems, theleading journal in the field of compilers and programming languages.Hens Palsberg is Associate Professor of Computer Science at Purdue University. His research interests areprogramming languages, compilers, software engineering, and information security. He has authored more than 50technical 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 PurdueUniversity Faculty award.Team-Fly
Team-FlyModern CompilerImplementation in Java, SecondEditionAndrew W. Appel Princeton UniversityJens Palsberg Purdue UniversityCAMBRIDGEUNIVERSITY PRESSPUBLISHED BY THE PRESS SYNDICATE OF THE UNIVERSITY OF CAMBRIDGEThe Pitt Building, Trumpington Street, Cambridge, United KingdomCAMBRIDGE UNIVERSITY PRESSThe Edinburgh Building, Cambridge CB2 2RU, UK40 West 20th Street, New York, NY 10011-4211, USA477 Williamstown Road, Port Melbourne, VIC 3207, AustraliaRuiz de Alarcón 13, 28014 Madrid, SpainDock House, The Waterfront, Cape Town 8001, South Africahttp://www.cambridge.orgCopyright 2002 Cambridge University PressThis book is in copyright. Subject to statutory exceptionand to the provisions of relevant collective licensing agreements,no reproduction of any part may take place withoutthe written permission of Cambridge University Press.First edition published 1998Second edition published 2002Typefaces 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., 1960Modern compiler implementation in Java /Andrew W. Appel with Jens Palsberg.[2nd ed.]p. cm.Includes bibliographical references and index.0-521-82060-X1. Java (Computer program language) 2. Compilers (Computer programs) I. Palsberg,Jens. II. Title.QA76.73.J38 A65 2002005.4 53-dc212002073453ISBN 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 registerallocation, and runtime systems. It includes good coverage of current techniques in code generation and registerallocation, 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 everypossible variant. Detailed descriptions of the interfaces between modules of a compiler are illustrated with actual Javaclasses.The first part of the book, Fundamentals of Compilation, is suitable for a one-semester first course in compilerdesign. The second part, Advanced Topics, which includes the compilation of object-oriented and functionallanguages, garbage collection, loop optimization, SSA form, instruction scheduling, and optimization forcache-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 programmingconcepts, such as visitor patterns. A unique feature is the newly redesigned compiler project in Java for a subset ofJava itself. The project includes both front-end and back-end phases, so that students can build a complete workingcompiler in one semester.Andrew W. Appel is Professor of Computer Science at Princeton University. He has done research and publishedpapers on compilers, functional programming languages, runtime systems and garbage collection, type systems, andcomputer security; he is also author of the book Compiling with Continuations. He is a designer and founder of theStandard ML of New Jersey project. In 1998, Appel was elected a Fellow of the Association for ComputingMachinery for "significant research contributions in the area of programming languages and compilers" and for hiswork as editor-in-chief (1993-97) of the ACM Transactions on Programming Languages and Systems, theleading journal in the field of compilers and programming languages.Jens Palsberg is Associate Professor of Computer Science at Purdue University. His research interests areprogramming 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, hereceived the National Science Foundation Faculty Early Career Development Award, and in 1999, the PurdueUniversity Faculty Scholar award.Team-Fly
Team-FlyPrefaceThis book is intended as a textbook for a one- or two-semester course in compilers. Students will see the theorybehind different components of a compiler, the programming techniques used to put the theory into practice, and theinterfaces 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 isorganized to demonstrate some important techniques that are now in common use: abstract syntax trees to avoidtangling syntax and semantics, separation of instruction selection from register allocation, copy propagation to giveflexibility to earlier phases of the compiler, and containment of target-machine dependencies. Unlike many "studentcompilers" found in other textbooks, this one has a simple but sophisticated back end, allowing good registerallocation 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 thesource language for the compiler project, it explains the use of the parser generators JavaCC and SableCC, and itpromotes programming with the Visitor pattern. Students using this edition can implement a compiler for a languagethey'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 forthe exercises can be found at http://uk.cambridge.org/resources/052182060X (outside North .html (within North America).Exercises Each chapter has pencil-and-paper exercises; those marked with a star are more challenging, two-starproblems 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.
A one-semester course could cover all of Part I (Chapters 1-12), with students implementing the projectcompiler (perhaps working in groups); in addition, lectures could cover selected topics from Part II. An advanced or graduate course could cover Part II, as well as additional topics from the current literature.Many of the Part II chapters can stand independently from Part I, so that an advanced course could betaught to students who have used a different book for their first course. In a two-quarter sequence, the first quarter could cover Chapters 1-8, and the second quarter could coverChapters 9-12 and some chapters from Part II.Acknowledgments Many people have provided constructive criticism or helped us in other ways on this book.Vidyut Samanta helped tremendously with both the text and the software for the new edition of the book. We wouldalso like to thank Leonor Abraido-Fandino, Scott Ananian, Nils Andersen, Stephen Bailey, Joao Cangussu, MaiaGinsburg, 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, AmrSabry, Mooly Sagiv, Zhong Shao, Mary Lou Soffa, Andrew Tolmach, Kwangkeun Yi, and Kenneth Zadeck.Team-Fly
Team-FlyPart One: Fundamentals ofCompilationChapter ListChapter 1: Introduction Chapter 2: Lexical Analysis Chapter 3: Parsing Chapter 4: Abstract Syntax Chapter 5:Semantic Analysis Chapter 6: Activation Records Chapter 7: Translation to Intermediate Code Chapter 8: BasicBlocks and Traces Chapter 9: Instruction Selection Chapter 10: Liveness Analysis Chapter 11: Register AllocationChapter 12: Putting It All TogetherTeam-Fly
Team-FlyChapter 1: IntroductionA compiler was originally a program that "compiled" subroutines [a link-loader]. When in 1954 the combination"algebraic compiler" came into use, or rather into misuse, the meaning of the term had already shifted into the presentone.Bauer and Eickel [1975]OVERVIEWThis book describes techniques, data structures, and algorithms for translating programming languages intoexecutable code. A modern compiler is often organized into many phases, each operating on a different abstract"language." The chapters of this book follow the organization of a compiler, each covering a successive phase.To illustrate the issues in compiling real programming languages, we show how to compile MiniJava, a simple butnontrivial subset of Java. Programming exercises in each chapter call for the implementation of the correspondingphase; a student who implements all the phases described in Part I of the book will have a working compiler.MiniJava is easily extended to support class extension or higher-order functions, and exercises in Part II show how todo this. Other chapters in Part II cover advanced techniques in program optimization. Appendix A describes theMiniJava language.The interfaces between modules of the compiler are almost as important as the algorithms inside the modules. Todescribe the interfaces concretely, it is useful to write them down in a real programming language. This book usesJava - a simple object-oriented language. Java is safe, in that programs cannot circumvent the type system to violateabstractions; and it has garbage 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 Java already should pick itup as they go along, using a Java programming book as a reference. Java is a small enough language, with simpleenough concepts, that this should not be difficult for students with good programming skills in other languages.Team-Fly
Team-Fly1.1 MODULES AND INTERFACESAny large software system is much easier to understand and implement if the designer takes care with thefundamental abstractions and interfaces. Figure 1.1 shows the phases in a typical compiler. Each phase isimplemented as one or more software modules.Figure 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 targetmachine for which the compiler produces machine language, it suffices to replace just the Frame Layout andInstruction Selection modules. To change the source language being compiled, only the modules up through Translateneed to be changed. The compiler can be attached to a language-oriented syntax editor at the Abstract Syntaxinterface.The learning experience of coming to the right abstraction by several iterations of think-implement-redesign is onethat should not be missed. However, the student trying to finish a compiler project in one semester does not have thisluxury. Therefore, we present in this book the outline of a project where the abstractions and interfaces are carefullythought out, and are as 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 data structures: Forexample, the Parsing Actions phase builds an Abstract Syntax data structure and passes it to the Semantic Analysisphase. Other interfaces are abstract data types; the Translate interface is a set of functions that the SemanticAnalysis phase can call, and the Tokens interface takes the form of a function that the Parser calls to get the nexttoken of the input program.DESCRIPTION OF THE PHASESEach chapter of Part I of this book describes one compiler phase, as shown in Table 1.2Table 1.2: Description of compiler phases.
ChapterPhaseDescription2LexBreak the source file into individualwords, or tokens.3ParseAnalyze the phrase structure of theprogram.4Semantic ActionsBuild a piece of abstract syntax treecorresponding to each phrase.5Semantic AnalysisDetermine what each phrase means,relate uses of variables to theirdefinitions, check types ofexpressions, request translation ofeach phrase.6Frame LayoutPlace variables, function-parameters,etc. into activation records (stackframes) in a machine-dependent way.7TranslateProduce intermediaterepresentation trees (IR trees), anotation that is not tied to anyparticular source language ortarget-machine architecture.8CanonicalizeHoist side effects out of expressions,and clean up conditional branches,for the convenience of the nextphases.9Instruction SelectionGroup the IR-tree nodes into clumpsthat correspond to the actions oftarget-machine instructions.
10Control Flow AnalysisAnalyze the sequence of instructionsinto a control flow graph that showsall the possible flows of control theprogram might follow when itexecutes.10Dataflow AnalysisGather information about the flow ofinformation through variables of theprogram; for example, livenessanalysis calculates the places whereeach program variable holds astill-needed value (is live).11Register AllocationChoose a register to hold each of thevariables and temporary values usedby the program; variables not live atthe same time can share the sameregister.12Code EmissionReplace the temporary names in eachmachine instruction with machineregisters.This modularization is typical of many real compilers. But some compilers combine Parse, Semantic Analysis,Translate, and Canonicalize into one phase; others put Instruction Selection much later than we have done, andcombine it with Code Emission. Simple compilers omit the Control Flow Analysis, Data Flow Analysis, and RegisterAllocation phases.We have designed the compiler in this book to be as simple as possible, but no simpler. In particular, in those placeswhere corners are cut to simplify the implementation, the structure of the compiler allows for the addition of moreoptimization or fancier semantics without violence to the existing interfaces.Team-Fly
Team-Fly1.2 TOOLS AND SOFTWARETwo of the most useful abstractions used in modern compilers are contextfree grammars, for parsing, and regularexpressions, for lexical analysis. To make the best use of these abstractions it is helpful to have special tools, such asYacc (which converts a grammar into a parsing program) and Lex (which converts a declarative specification into alexical-analysis program). Fortunately, such tools are available for Java, and the project described in this book makesuse of them.The programming projects in this book can be compiled using any Java compiler. The parser generators JavaCCand SableCC are freely available on the Internet; for information see the World Wide Web pagehttp://uk.cambridge.org/resources/052182060X (outside North .html (within North America).Source code for some modules of the MiniJava compiler, skeleton source code and support code for some of theprogramming exercises, example MiniJava programs, and other useful files are also available from the same Webaddress. The programming exercises in this book refer to this directory as MINIJAVA/ when referring to specificsubdirectories and files contained therein.Team-Fly
Team-Fly1.3 DATA STRUCTURES FOR TREELANGUAGESMany of the important data structures used in a compiler are intermediate representations of the program beingcompiled. Often these representations take the form of trees, with several node types, each of which has differentattributes. Such trees can occur at many of the phase-interfaces shown in Figure 1.1.Tree representations can be described with grammars, just like programming languages. To introduce the concepts,we will show a simple programming language with statements and expressions, but no loops or if-statements (this iscalled a language of straight-line programs).The syntax for this language is give
Chapter 1: Introduction A compiler was originally a program that "compiled" subroutines [a link-loader]. When in 1954 the combination "algebraic compiler" came into use, or rather into misuse, the meaning of the term had already shifted into the present one. Bauer and Eickel [1975] OVERVIEW
3. _ is a software that interprets Java bytecode. a. Java virtual machine b. Java compiler c. Java debugger d. Java API 4. Which of the following is true? a. Java uses only interpreter b. Java uses only compiler. c. Java uses both interpreter and compiler. d. None of the above. 5. A Java file with
java.io Input and output java.lang Language support java.math Arbitrary-precision numbers java.net Networking java.nio "New" (memory-mapped) I/O java.rmi Remote method invocations java.security Security support java.sql Database support java.text Internationalized formatting of text and numbers java.time Dates, time, duration, time zones, etc.
Java Version Java FAQs 2. Java Version 2.1 Used Java Version This is how you find your Java version: Start the Control Panel Java General About. 2.2 Checking Java Version Check Java version on https://www.java.com/de/download/installed.jsp. 2.3 Switching on Java Console Start Control Panel Java Advanced. The following window appears:
The Java Virtual Machine: Java Virtual Machine (JVM) is the heart of entire Java program execution process. First of all, the .java program is converted into a .class file consisting of byte code instructions by the java compiler at the time of compilation. Remember, this java compiler is outside the JVM. This .class file is given to the JVM.
–‘java’ command launches Java runtime with Java bytecode An interpreter executes a program by processing each Java bytecode A just-in-time compiler generates native instructions for a target machine from Java bytecode of a hotspot method 9 Easy and High Performance GPU Programming for Java Programmers Java program (.
Java programs, thus maximizing efficiency. It is important to select the right compiler before writing a Java program since the compiler affects the performance the most in Java Virtual Machine [8]. The efficiency of the compiler affects both the instruction count and average cycles
Chapter 1 Introduction & Explanation 1.1 What Is This Document? This document is a companion to the textbook Modern Compiler Design by David Galles. The textbook covers compiler design theory, as well as implementation details for writing a compiler using JavaCC and Java.
applicability of Java to Computational Fluid Dynamics (CFD), we have implemented the NAS Parallel Benchmarks in Java. The performance and scalability of the benchmarks point out the areas where improvement in Java compiler technology and in Java thread implementation would position Java closer to Fortran in the competition for CFD applications.
