- Amazon Student members save an additional 10% on Textbooks with promo code TEXTBOOK10. Enter code TEXTBOOK10 at checkout. Here's how (restrictions apply)
Programming Language Processors in Java: Compilers and Interpreters Hardcover – Feb 4 2000
Special Offers and Product Promotions
Customers Who Bought This Item Also Bought
No Kindle device required. Download one of the Free Kindle apps to start reading Kindle books on your smartphone, tablet, and computer.
To get the free app, enter your e-mail address or mobile phone number.
From the Inside Flap
The subject of this book is the implementation of programming languages. Programming language processors are programs that process other programs. The primary examples of language processors are compilers and interpreters.
Programming languages are of central importance in computer science. They are the most fundamental tools of software engineers, who are completely dependent on the quality of the language processors they use. There is an interplay between the design of programming languages and computer instruction sets: compilers must bridge the gap between high-level languages and machine code. And programming language design itself raises strong feelings among computer scientists, as witnessed by the proliferation of language paradigms. Imperative and object-oriented languages are currently dominant in terms of actual usage, and it is on the implementation of such languages that this book focuses.
Programming language implementation is a particularly fascinating topic, in our view, because of its close interplay between theory and practice. Ever since the dawn of computer science, the engineering of language processors has driven, and has been vastly improved by, the development of relevant theories.
Nowadays, the principles of programming language implementation are very well understood. An experienced compiler writer can implement a simple programming language about as fast as he or she can type. The basic techniques are simple yet effective, and can be lucidly presented to students. Once the techniques have been mastered, building a compiler from scratch is essentially an exercise in software engineering.
A textbook example of a compiler is often the first complete program of its size seen by computer science students. Such an example should therefore be an exemplar of good software engineering principles. Regrettably, many compiler textbooks offend these principles. This textbook, based on a total of about twenty-five years' experience of teaching programming language implementation, aims to exemplify good software engineering principles at the same time as explaining the specific techniques needed to build compilers and interpreters.
The book shows how to design and build simple compilers and interpreters using the object-oriented programming language Java. The reasons for this choice are twofold. First, object-oriented methods have emerged as a dominant software engineering technology, yielding substantial improvements in software modularity, maintainability, and reusability. Secondly, Java itself has experienced a prodigious growth in popularity since its appearance as recently as 1994, and that for good technical reasons: Java is simple, consistent, portable, and equipped with an extremely rich class library. Soon we can expect all computer science students to have at least some familiarity with Java. This is the fourth of a series of books on programming languages:
- Programming Language Concepts and Paradigms
- Programming Language Syntax and Semantics
- Programming Language Processors
- Programming Language Processors in Java
Programming Language Concepts and Paradigms studies the concepts underlying programming languages, and the major language paradigms that use these concepts in different ways; in other words, it is about language design. Programming Language Syntax and Semantics shows how we can formally specify the syntax (form) and semantics (meaning) of programming languages. Programming Language Processors studies the implementation of programming languages, examining language processors such as compilers and interpreters, and using Pascal as the implementation language. Programming Language Processors in Java likewise studies the implementation of programming languages, but now using Java as the implementation language and object-oriented design as the engineering principle; moreover, it introduces basic techniques for implementing object-oriented languages.
This series attempts something that has not previously been achieved, as far as we know: a broad study of all aspects of programming languages, using consistent terminology, and emphasizing connections likely to be missed by books that deal with these aspects separately. For example, the concepts incorporated in a language must be defined precisely in the language's semantic specification. Conversely, a study of semantics helps us to discover and refine elegant and powerful new concepts, which can be incorporated in future language designs. A language's syntax underlies analysis of source programs by language processors; its semantics underlies object code generation and interpretation. Implementation is an important consideration for the language designer, since a language that cannot be implemented with acceptable efficiency will not be used.
The books may be read as a series, but each book is sufficiently self-contained to be read on its own, if the reader prefers.Content of this Book
Chapter 1 introduces the topic of the book. It reviews the concepts of high-level programming languages, and their syntax, contextual constraints, and semantics. It explains what a language processor is, with examples from well-known programming systems.
Chapter 2 introduces the basic terminology of language processors: translators, compilers, interpreters, source and target languages, and real and abstract machines. It goes on to study interesting ways of using language processors: interpretive compilers, portable compilers, and bootstrapping. In this chapter we view language processors as 'black boxes.' In the following chapters we look inside these black boxes.
Chapter 3 looks inside compilers. It shows how compilation can be decomposed into three principal phases: syntactic analysis, contextual analysis, and code generation. It also compares different ways of designing compilers, leading to one-pass and multi-pass compilation.
Chapter 4 studies syntactic analysis in detail. It decomposes syntactic analysis into scanning, parsing, and abstract syntax tree construction. It introduces recursive-descent parsing, and shows how a parser and scanner can be systematically constructed from the source language's syntactic specification.
Chapter 5 studies contextual analysis in detail, assuming that the source language exhibits static bindings and is statically typed. The main topics are identification, which is related to the language's scope rules, and type checking, which is related to the language's type rules.
Chapter 6 prepares for code generation by discussing the relationship between the source language and the target machine. It shows how target machine instructions and storage must be marshaled to support the higher-level concepts of the source language. The topics covered include data representation, expression evaluation, storage allocation, routines and their arguments, garbage collection, and the run-time organization of simple object-oriented languages.
Chapter 7 studies code generation in detail. It shows how to organize the translation from source language to object code. It relates the selection of object code to the semantics of the source language. As this is an introductory textbook, only code generation for a stack-based target machine is covered. (The more difficult topics of code generation for a register-based machine, and code transformations are left to more advanced textbooks.)
Chapter 8 looks inside interpreters. It gives examples of interpreters for both low-level and high-level languages.
Chapter 9 concludes the book. It places the implementation of a programming language in the context of the language's life cycle, along with design and specification. It also discusses quality issues, namely error reporting and efficiency.
There are several possible orders for studying the main topics of this book. The chapter on interpretation can be read independently of the chapters on compilation. Within the latter, the chapters on syntactic analysis, contextual analysis, and code generation can be read in any order.Examples and Case Studies
The methods described in this textbook are freely illustrated by examples. In Chapter 2, the examples are of language processors for real programming languages. In the remaining chapters, most examples are based on smaller languages, in order that the essential points can be conveyed without the reader getting lost in detail.
A complete programming language is a synthesis of numerous concepts, which often interact with one another in quite complicated ways. It is important that the reader understands how we cope with these complications in implementing a complete programming language. For this purpose we use the programming language Triangle as a case study. An overview of Triangle is given in Section 1.4. A reader already familiar with a Pascal-like language should have no trouble in reading Triangle programs. A complete specification of Triangle is given in Appendix B; this includes a formal specification of its syntax, but is otherwise informal.
We designed Triangle for two specific purposes: to illustrate how a programming language can be formally specified (in the companion textbook Programming Language Syntax and Semantics), and to illustrate how a programming language can be implemented. Ideally we would use a real programming language, such as Pascal or Java, for these purposes. In practice, however, real languages are excessively complicated. They contain many features that are tedious but unilluminating to specify and to implement. Although Triangle is a model language, it is rich enough to write interesting programs and to illustrate basic methods of specification and implementation. Finally, it can readily be extended in various ways (such as adding new types, new control structures, or packages), and such extensions are a basis for a variety of projects.Educational Software
A Triangle language processor is available for educational use in conjunction with this textbook. The Triangle language processor consists of: a compiler for Triangle, which generates code for TAM (Triangle Abstract Machine); an interpreter for TAM; and a disassembler for TAM. The tools are written entirely in Java, and will run on any computer equipped with a JVM (Java Virtual Machine).These vary from short exercises, through longer ones (marked *), up to truly demanding ones (marked **) that could be treated as projects.
A typical exercise is to apply the methods of the chapter to a very small toy language, or a minor extension of Triangle.
A typical project is to implement some substantial extension to Triangle. Most of the projects are gathered together at the end of Chapter 9; they require modifications to several parts of the Triangle compiler, and should be undertaken only after reading up to Chapter 7 at least.Readership
This book and its companions are aimed at junior, senior, and graduate students of computer science and information technology, all of whom need some understanding of the fundamentals of programming languages. The books should also be of interest to professional software engineers, especially project leaders responsible for language evaluation and selection, designers and implementors of language processors, and designers of new languages and extensions to existing languages.
The basic prerequisites for this textbook are courses in programming and data structures, and a course in programming languages that covers at least basic language concepts and syntax. The reader should be familiar with Java, and preferably at least one other high-level language, since in studying implementation of programming languages it is important not to be unduly influenced by the idiosyncrasies of a particular language. All the algorithms in this textbook are expressed in Java.
The ability to read a programming language specification critically is an essential skill. A programming language implementor is forced to explore the entire language, including its darker corners. (The ordinary programmer is wise to avoid these dark corners!) The reader of this textbook will need a good knowledge of syntax, and ideally some knowledge of semantics; these topics are briefly reviewed in Chapter 1 for the benefit of readers who might lack such knowledge. Familiarity with BNF and EBNF (which are commonly used in language specifications) is essential, because in Chapter 4 we show how to exploit them in syntactic analysis. No knowledge of formal semantics is assumed.
The reader should be comfortable with some elementary concepts from discrete mathematics sets and recursive functions as these help to sharpen understanding of, for example, parsing algorithms. Discrete mathematics is essential for a deeper understanding of compiler theory; however, only a minimum of compiler theory is presented in this book.
This book and its companions attempt to cover all the most important aspects of a large subject. Where necessary, depth has been sacrificed for breadth. Thus the really serious student will need to follow up with more advanced studies. Each book has an extensive bibliography, and each chapter closes with pointers to further reading on the topics covered by the chapter.Acknowledgments
Most of the methods described in this textbook have long since passed into compiler folklore, and are almost impossible to attribute to individuals. Instead, we shall mention people who have particularly influenced us personally.
For providing a stimulating environment in which to think about programming language issues, we are grateful to colleagues in the Department of Computing Science at the University of Glasgow, in particular Malcolm Atkinson, Muffy Calder, Quintin Cutts, Peter Dickman, Bill Findlay, John Hughes, John Launchbury, Hermano Moura, John Patterson, Simon Peyton Jones, Fermin Reig, Phil Trinder, and Phil Wadler. We have also been strongly influenced, in many different ways, by the work of Peter Buneman, Luca Cardelli, Edsger Dijkstra, Jim Gosling, Susan Graham, Tony Hoare, Jean Ichbiah, Mehdi Jazayeri, Robin Milner, Peter Mosses, Atsushi Ohori, Bob Tennent, Jim Welsh, and Niklaus Wirth.
We wish to thank the reviewers for reading and providing valuable comments on an earlier draft of this book. Numerous cohorts of undergraduate students taking the Programming Languages 3 module at the University of Glasgow made an involuntary but essential contribution by class-testing the Triangle language processor, as have three cohorts of students taking the Compilers module at the Robert Gordon University.
We are particularly grateful to Tony Hoare, editor of the Prentice Hall International Series in Computer Science, for his encouragement and advice, freely and generously offered when these books were still at the planning stage. If this book is more than just another compiler textbook, that is partly due to his suggestion to emphasize the connections between compilation, interpretation, and semantics.D.A.W.
Glasgow and Aberdeen
From the Back Cover
David A Watt and Deryck F Brown
Programming Language Processors in Java
Compilers and Interpreters
This book provides a gently paced introduction to techniques for implementing programming languages by means of compilers and interpreters, using the object-oriented programming language Java. The book aims to exemplify good software engineering principles at the same time as explaining the specific techniques needed to build compilers and interpreters.
* The book shows clearly how a simple compiler can be decomposed into a syntactic analyzer, a contextual analyzer, and a code generator, communicating via an abstract syntax tree.
* The book is accompanied by a complete working compiler and interpreter, provided via the Internet, and free of charge for educational use.
* The book contains numerous exercises, together with sample answers to selected exercises. It also contains a number of suggested projects, involving extensions to the accompanying compiler.
* All examples in the book are expressed in Java, and the compiler and interpreter are structured using object-oriented design patterns.
David Watt teaches algorithms and data structures, programming languages, and software design. Deryck Brown teaches compilers, object-oriented programming, operating systems, and software engineering.
Inside This Book(Learn More)
Top Customer Reviews
This book will not provide proofs or a lot in the way of choices for designing a compiler. This is good when you are starting out. The last thing you need if you actually want to learn about compiler design from front to back is a hundred different ways of doing the same thing. The text takes you through a small version of the "Triangle" language ("Mini-Triangle") - and the code for the entire Triangle language is available for download.
This book makes learning about compilers effortless for anyone with an OO background and a little knowledge of the most common algorithms learned in any into course on algorithms. If you can't learn from this text, then don't bother with any other.
The next book I'd recommend after reading this text is the Dragon Book. Then you can try on Advanced Compiler Design for size - which I am doing at present.
A great book to read along (or just before of after) this text is Programming Language Pragmatics. I read it in parallel. If I had to do it again, I'd probably read it first.
There -are- some real problems with it, though. The most obvious and central problem is that it's not a book by (or for) Java programmers. It feels very much as if the book was hastily rewritten from "Language Processors in Pascal" to "Language Processors in Java" after Java exploded in popularity, a year or two before the book was published. The mini-Triangle language is clearly a Pascal derivative, and many of the "pseudo-code" examples are really Pascal. Pascal may be a teaching language, but it looks completely alien to Java developers.
My biggest concern, and it's what prompted me to write this review, is that the Java code is truly awful. Yes, it uses the Visitor pattern (as one reviewer pointed out) to traverse the AST during semantic analysis, which is a reasonable strategy. But the code is just plain bad, and you don't want students learning bad habits. The code is utterly non-polymorphic; it's filled with long cascaded if-statements that check whether an AST node is an instanceof this or an instanceof that. They pass and return parameters of type Object, and callers perform dangerous narrowing typecasts. They freely pass and return null values that have special semantics (i.e. "if this parameter is null, then it means we have this kind of situation; otherwise it's the other kind").Read more ›
Ideal for me: I had given up on the field for the time being when I came across this book. I could not believe it. It was not what I was looking for because I had no idea it existed, but it quickly became apparent that it was ideal for my situation. My preferred language is Java and so this just helped to make the examples jump out of the page at me that little bit more.
Working through the book: I enjoyed working through the book and found it very readable and self-explanatory. The examples are excellent and reinforce every concept presented by the book. It stood out from everything I had read on the subject to this point (and since).
The case-study: The case study, which runs throughout the book, uses the programming language Triangle. It has obvious links to the previous incarnations of the book when the Pascal programming language was used. Triangle is a simpler version of Pascal but is still a reasonably realistic language to look at. I found it very useful to see how each aspect of the compiler would actually look in code for an example language. The language is compiled to an abstract machine called TAM. The details of this are included in the appendix and can be transferred to other machines with a bit of careful modification.
Structure of the book: The book starts off with the normal background and definitions in the first two chapters.Read more ›
Look for similar items by category
- Books > Computers & Technology > Hardware > Design & Architecture
- Books > Computers & Technology > Networking & Cloud Computing > Networks, Protocols & APIs
- Books > Computers & Technology > Programming > Java
- Books > Computers & Technology > Programming > Languages & Tools > Compiler Design
- Books > Computers & Technology > Programming > Languages & Tools > Compilers
- Books > Computers & Technology > Programming > Software Design, Testing & Engineering > Object-Oriented Design
- Books > Computers & Technology > Software
- Books > Qualifying Textbooks - Fall 2007 > Computers & Internet
- Books > Textbooks > Computer Science & Information Systems > Programming Languages