Dos Reis - Compiler Construction Using Java, JavaCC, and Yacc

CONTENTS

Compiler Construction Using Java, JavaCC, and Yacc

IEEE
computer society

Press Operating Committee

Chair
Linda Shafer
former Director, Software Quality Institute
The University of Texas at Austin

Editor-in-Chief
Alan Clements
Professor
University of Teesside

Board Members

Mark J. Christensen, Independent Consultant
James W. Cortada, IBM Institute for Business Value
Richard E. (Dick) Fairley, Founder and Principal Associate, Software Engineering
Management Associates (SEMA)
Phillip Laplante, Professor of Software Engineering, Penn State University
Evan Butterfield, Director of Products and Services
Kate Guillemette, Product Development Editor, CS Press

Copyright 2012 by the IEEE Computer Society, Inc.

Published by John Wiley & Sons, Inc., Hoboken, New Jersey. All rights reserved.

Published simultaneously in Canada.

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 Section 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, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com . 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/permission .

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representation or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services please contact our Customer Care Department within the United States at (800) 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, however, may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com .

Library of Congress Cataloging-in-Publication Data:

Dos Reis, Anthony J.
Compiler construction using Java, JavaCC, and Yacc / Anthony J. Dos Reis.
p. cm.
ISBN 978-0-470-94959-7 (hardback)
1. Compilers (Computer programs) 2. Java (Computer program language) I. Title.
QA76.76.C65D67 2011
005.453dc23 2011013211

oBook ISBN: 978-1-118-11276-2
ePDF ISBN: 978-1-118-11287-8
ePub ISBN: 978-1-118-11277-9
eMobi ISBN: 978-1-118-11288-5

To little sister

PREFACE

My principal goal in writing this book is to provide the reader with a clear exposition of the theory of compiler design and implementation along with plenty of opportunities to put that theory into practice. The theory, of course, is essential, but so is the practice.

• Provides numerous, well-defined projects along with test cases. These projects ensure that students not only know the theory but also know how to apply it. Instructors are relieved of the burden of designing projects that integrate well with the text.
• Project work starts early in the book so that students can apply the theory as they are learning it.
• The compiler tools (JavaCC, Yacc, and Lex) are optional topics.
• The entire book is Java oriented. The implementation language is Java. The principal target language is similar to Javas bytecode. The compiler tools generate Java code. The form of attributed grammar used has a Java-like syntax.
• The target languages (one is stack oriented like Javas bytecode; the other is register oriented) are very easy to learn but are sufficiently powerful to support advanced compiler projects.
• The software package is a dream come true for both students and instructors. It automatically evaluates a students compiler projects with respect to correctness, run time, and size. It is great for students: they get immediate feedback on their projects. It is great for instructors: they can easily and accurately evaluate a students work. With a single command, an instructor can generate a report for an entire class. The software runs on three platforms: Microsoft Windows, Linux, and the Macintosh OS X.
• Demonstrates how compiler technology is not just for compilers. In a capstone project, students design and implement grep using compiler technology.
• Includes a chapter on interpreters that fits in with the rest of the book.
• Includes a chapter on optimization that is just right for an introductory course. Students do not simply read about optimization techniquesthey implement a variety of techniques, such as constant folding, peephole optimization, and register allocation.
• The book uses a Java-like form of grammars that students can easily understand and use. This is the same form that JavaCC uses. Thus, students can make transition to JavaCC quickly and easily.
• Provides enough theory that the book can be used for a combined compiler/automata/formal languages course. The book covers most of the topics covered in an automata/formal languages course: finite automata, stack parsers, regular expressions, regular grammars, context-free grammars, context-sensitive grammars, unrestricted grammars, Chomskys hierarchy, and the pumping lemmas. Pushdown automata, Turing machines, computability, and complexity are discussed in supplements in the software package. The software package also includes a pushdown automaton simulator and Turing machine simulator.