Ronald Mak - Writing Compilers and Interpreters: A Software Engineering Approach

Writing Compilers and Interpreters: A Modern Software Engineering Approach Using Java, Third Edition Published by
Wiley Publishing, Inc.
10475 Crosspoint Boulevard
Indianapolis, IN 46256
www.wiley.com Copyright 2009 by Ronald Mak Published by Wiley Publishing, Inc., Indianapolis, Indiana Published simultaneously in Canada ISBN: 978-0-470-17707-5 Manufactured in the United States of America 10 9 8 7 6 5 4 3 2 1 No part of this publication may be reproduced, stored in a retrieval system or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning or otherwise, except as permitted under Sections 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 646-8600. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at http://www.wiley.com/go/permissions . Limit of Liability/Disclaimer of Warranty: The publisher and the author make no representations or warranties with respect to the accuracy or completeness of the contents of this work and specifically disclaim all warranties, including without limitation warranties of fitness for a particular purpose. No warranty may be created or extended by sales or promotional materials. The advice and strategies contained herein may not be suitable for every situation. This work is sold with the understanding that the publisher is not engaged in rendering legal, accounting, or other professional services.

If professional assistance is required, the services of a competent professional person should be sought. Neither the publisher nor the author shall be liable for damages arising herefrom. The fact that an organization or Web site is referred to in this work as a citation and/or a potential source of further information does not mean that the author or the publisher endorses the information the organization or Web site may provide or recommendations it may make. Further, readers should be aware that Internet Web sites listed in this work may have changed or disappeared between when this work was written and when it is read. For general information on our other products and services please contact our Customer Care Department within the United States at (877) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002. Wiley also publishes its books in a variety of electronic formats.

Some content that appears in print may not be available in electronic books. Library of Congress Control Number: 2009931754 Trademarks: Wiley and the Wiley logo are trademarks or registered trademarks of John Wiley & Sons, Inc. and/or its affiliates, in the United States and other countries, and may not be used without written permission. Java is a registered trademark of Sun Microsystems, Inc. All other trademarks are the property of their respective owners. is not associated with any product or vendor mentioned in this book. is not associated with any product or vendor mentioned in this book.

This book is dedicated to all programmers who accept the challenge of writing very complex software successfully. About the Author Ronald Mak wrote the earlier editions of this very successful book, as well as The Martian Principles for Successful Enterprise Systems: 20 Lessons Learned from NASAs Mars Exploration Rover Mission (also published by Wiley) and Java Number Cruncher: The Java Programmers Guide to Numerical Computing (Prentice Hall). He develops advanced software systems for organizations from startups to NASA. Currently a research staff member at the IBM Almaden Research Center, he also teaches compiler writing and software engineering at San Jos State University. He has degrees in the mathematical sciences and in computer science from Stanford University, and he lives in San Jos, CA with two cats.

Credits Executive Editor Carol Long Project Editor Tom Dinse Technical Editor Chris Tseng Production Editor Daniel Scribner Copy Editor Christopher Jones Editorial Director Robyn B.

Siesky Editorial Manager Mary Beth Wakefield Production Manager Tim Tate Vice President and Executive Group Publisher Richard Swadley Vice President and Executive Publisher Barry Pruett Associate Publisher Jim Minatel Project Coordinator, Cover Lynsey Stanford Compositor Craig J. Woods, Happenstance Type-O-Rama Proofreader Publication Services, Inc. Indexer Ron Strauss Cover Image Punchstock Acknowledgments Carol Long, Executive Acquisitions Editor at Wiley, first contacted me a couple of years ago to persuade me to do this third edition. She stayed on top of my efforts to complete it. Tom Dinse, Senior Development Editor, did a great job making sure I uploaded my chapter manuscripts on time and coordinated all the editing work. Tom was a pleasure to work with.

My students of CS 153, Concepts of Compiler Design, in the Department of Computer Science at San Jos State University (California) used early manuscripts of the chapters and pointed out problems to me. I realize most of them may never write a compiler during their careers, but I hope they benefited from learning how to work together in small programming teams to design and develop some very complex software. Thanks to Phil Edwards, my former colleague at the Lawrence Livermore National Laboratory, who read several of the early chapters and helped me clear up some confusing statements. Finally, special thanks to my technical editor, computer science professor Dr. Chris Tseng at San Jos State University. He read all the chapters, ran all the programs, and his suggestions and comments helped me improve the text.

Large, complex programs such as compilers and interpreters are challenging to get right. The programs in this book are for educational purposes only and are not production quality. I accept the blame for any bugs they contain. However, neither I nor Wiley Publishing can be responsible for any damages these programs may cause if you use them for any other purposes. Introduction This book is about writing compilers and interpreters. The emphasis is on writing because this book writes a very large amount of code.

This is your book if you want to learn how to write an interpreter, a compiler, an interactive source-level debugger, and an integrated development environment (IDE) with a graphical user interface (GUI). All the code is in Java, which I explain in detail. This book is not about the theory behind compiler writing. I leave that to the textbooks. If you want to learn the theory right now, then this is not your book. However, I hope that after working your way through this books programs, youll be inspired to learn about their theoretical underpinnings.

The first edition of this book used C as the implementation language, the second edition used C++, and this third edition uses Java. While I kept the basic organization, philosophy, and approach of the earlier editions, this edition is a complete rewrite. What Youll Learn in this Book The interpreter and the compiler that you learn to write in this book processes programs written in a high-level language. Youll write an interpreter that can execute programs. After you add the debugger, youll be able to interact with the interpreter as it executes a program by setting breakpoints, displaying the call stack, viewing and modifying values of variables, and single-stepping the programs execution statement-by-statement. Add the IDE and youll do all that with mouse clicks as you watch a programs execution animated on the screen.