A.W. Appel, J. Palsberg - Modern Compiler Implementation in Java (Second Edition)

Modern Compiler Implementation in Java, Second Editionby Andrew W. Appel and Jens PalsbergISBN:052182060xCambridge University Press © 2002 (501 pages)This textbook describes all phases of a compiler, and thoroughcoverage of current techniques in code generation and registerallocation, and the compilation of functional and object-orientedlanguages.Back 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 register allocation, and runtime systems. It includes goodcoverage of current techniques in code generation and register allocation, as well as thecompilation of functional and object-oriented languages, which is missing from most books.The most accepted and successful techniques are described concisely, rather than as anexhaustive catalog of every possible variant.

Detailed descriptions of the interfaces betweenmodules of a compiler are illustrated with actual Java classes.The first part of the book, Fundamentals of Compilation, is suitable for a one-semester firstcourse in compiler design. The second part, Advanced Topics, which includes the compilationof object-oriented and functional languages, garbage collection, loop optimization, SSA form,instruction scheduling, and optimization for cache-memory hierarchies, can be used for asecond-semester or graduate course.This new edition has been rewritten extensively to include more discussion of Java andobject-oriented programming concepts, such as visitor patterns. A unique feature in the newlyredesigned compiler project in Java for a subset of Java itself.

The project includes both frontend and back-end phases, so that students can build a complete working compiler in onesemester.About the AuthorsAndrew W. Appel is Professor of Computer Science at Princeton University. He has doneresearch and published papers on compilers, functional programming languages, runtimesystems and garbage collection, type systems, and computer security; he is also the author ofthe book Compiling with Continuations. He is a designer and founder of the Standard ML ofNew Jersey project. In 1998, Appel was elected a Fellow of the Association for ComputingMachinery for “significant research contributions in the area of programming languages andcompilers” and for his work as editor-in-chief (1993-7) of the ACM Transactions onProgramming Languages and Systems, the leading journal in the field of compilers andprogramming languages.Hens Palsberg is Associate Professor of Computer Science at Purdue University.

His researchinterests are programming languages, compilers, software engineering, and informationsecurity. He has authored more than 50 technical papers in these areas and a book withMichael Schwartzbach, Object-Oriented Type Systems. In 1998, he received the NationalScience Foundation Faculty Early Career Development Award, and in 1999, the Purdue1Modern Compiler Implementation in Java,Second EditionAndrew 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 dataAppel, 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-dc2122002073453ISBN 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 goodcoverage of current techniques in code generation and register allocation, as well as thecompilation of functional and object-oriented languages, which is missing from most books.The most accepted and successful techniques are described concisely, rather than as anexhaustive catalog of every possible variant. Detailed descriptions of the interfaces betweenmodules of a compiler are illustrated with actual Java classes.The first part of the book, Fundamentals of Compilation, is suitable for a one-semester firstcourse in compiler design.

The second part, Advanced Topics, which includes the compilationof object-oriented and functional languages, garbage collection, loop optimization, SSA form,instruction scheduling, and optimization for cache-memory hierarchies, can be used for asecond-semester or graduate course.This new edition has been rewritten extensively to include more discussion of Java andobject-oriented programming concepts, such as visitor patterns. A unique feature is the newlyredesigned compiler project in Java for a subset of Java itself. The project includes both frontend and back-end phases, so that students can build a complete working compiler in onesemester.Andrew W.

Appel is Professor of Computer Science at Princeton University. He has doneresearch and published papers on compilers, functional programming languages, runtimesystems and garbage collection, type systems, and computer security; he is also author of thebook Compiling with Continuations. He is a designer and founder of the Standard ML of NewJersey project. In 1998, Appel was elected a Fellow of the Association for ComputingMachinery for "significant research contributions in the area of programming languages andcompilers" and for his work as editor-in-chief (1993-97) of the ACM Transactions onProgramming Languages and Systems, the leading journal in the field of compilers andprogramming languages.Jens Palsberg is Associate Professor of Computer Science at Purdue University.

His researchinterests are programming languages, compilers, software engineering, and informationsecurity. He has authored more than 50 technical papers in these areas and a book withMichael Schwartzbach, Object-oriented Type Systems. In 1998, he received the NationalScience Foundation Faculty Early Career Development Award, and in 1999, the PurdueUniversity Faculty Scholar award.3Table of ContentsModern Compiler Implementation in Java, Second Edition ...................................................... 2Table of Contents .......................................................................................................................

4Preface........................................................................................................................................ 9Part One: Fundamentals of Compilation..................................................................................

11Chapter List .......................................................................................................................... 11Chapter 1: Introduction ............................................................................................................ 12OVERVIEW......................................................................................................................... 121.1 MODULES AND INTERFACES.................................................................................. 12DESCRIPTION OF THE PHASES .................................................................................

131.2 TOOLS AND SOFTWARE........................................................................................... 151.3 DATA STRUCTURES FOR TREE LANGUAGES ..................................................... 15PROGRAM STRAIGHT-LINE PROGRAM INTERPRETER .......................................... 19PROGRAM STRAIGHT-LINE PROGRAM INTERPRETER .......................................... 21Chapter 2: Lexical Analysis ..................................................................................................... 24OVERVIEW......................................................................................................................... 242.1 LEXICAL TOKENS ......................................................................................................

242.2 REGULAR EXPRESSIONS.......................................................................................... 252.3 FINITE AUTOMATA ................................................................................................... 28RECOGNIZING THE LONGEST MATCH ................................................................... 292.4 NONDETERMINISTIC FINITE AUTOMATA ...........................................................

30CONVERTING A REGULAR EXPRESSION TO AN NFA......................................... 31CONVERTING AN NFA TO A DFA............................................................................. 332.5 LEXICAL-ANALYZER GENERATORS .................................................................... 35JAVACC .......................................................................................................................... 36SABLECC........................................................................................................................ 37PROGRAM LEXICAL ANALYSIS ................................................................................... 37FURTHER READING......................................................................................................... 38EXERCISES.........................................................................................................................