similar to the one discussed in detail in the text. Development of such a compiler could rely entirely
on traditional hand-crafted techniques, or could rely entirely on a tool-based approach (both
approaches have been successfully used at our university). If a hand-crafted approach were used,
Chapters 12 and 13 could be omitted; Chapter 12 is largely a reference manual in any event, and
could be left to the students to study for themselves as the need arose. Similarly, Chapter 3 falls into
the category of background reading.
At our university we have also used an extended version of the Clang compiler as developed in the
text (one incorporating several of the extensions suggested as exercises) as a system for students to
study concurrent programming per se, and although it is a little limited, it is more than adequate for
the purpose. We have also used a slightly extended version of the assembler program very
successfully as our primary tool for introducing students to the craft of programming at the
assembler level.
Limitations
It is, perhaps, worth a slight digression to point out some things which the book does not claim to
be, and to justify some of the decisions made in the selection of material.
In the first place, while it is hoped that it will serve as a useful foundation for students who are
already considerably more advanced, a primary aim has been to make the material as accessible as
possible to students with a fairly limited background, to enhance the background, and to make them
somewhat more critical of it. In many cases this background is still Pascal based; increasingly it is
tending to become C++ based. Both of these languages have become rather large and complex, and
I have found that many students have a very superficial idea of how they really fit together. After a
course such as this one, many of the pieces of the language jigsaw fit together rather better.
When introducing the use of compiler writing tools, one might follow the many authors who
espouse the classic lex/yacc approach. However, there are now a number of excellent LL(1) based
tools, and these have the advantage that the code which is produced is close to that which might be
hand-crafted; at the same time, recursive descent parsing, besides being fairly intuitive, is powerful
enough to handle very usable languages.
That the languages used in case studies and their translators are relative toys cannot be denied. The
Clang language of later chapters, for example, supports only integer variables and simple
one-dimensional arrays of these, and has concurrent features allowing little beyond the simulation
of some simple textbook examples. The text is not intended to be a comprehensive treatise on
systems programming in general, just on certain selected topics in that area, and so very little is said
about native machine code generation and optimization, linkers and loaders, the interaction and
relationship with an operating system, and so on. These decisions were all taken deliberately, to
keep the material readily understandable and as machine-independent as possible. The systems may
be toys, but they are very usable toys! Of course the book is then open to the criticism that many of
the more difficult topics in translation (such as code generation and optimization) are effectively
not covered at all, and that the student may be deluded into thinking that these areas do not exist.
This is not entirely true; the careful reader will find most of these topics mentioned somewhere.
Good teachers will always want to put something of their own into a course, regardless of the
quality of the prescribed textbook. I have found that a useful (though at times highly dangerous)
technique is deliberately not to give the best solutions to a problem in a class discussion, with the
optimistic aim that students can be persuaded to "discover" them for themselves, and even gain a
sense of achievement in so doing. When applied to a book the technique is particularly dangerous,
but I have tried to exploit it on several occasions, even though it may give the impression that the
author is ignorant.
Another dangerous strategy is to give too much away, especially in a book like this aimed at
courses where, so far as I am aware, the traditional approach requires that students make far more
of the design decisions for themselves than my approach seems to allow them. Many of the books
in the field do not show enough of how something is actually done: the bridge between what they
give and what the student is required to produce is in excess of what is reasonable for a course
which is only part of a general curriculum. I have tried to compensate by suggesting what I hope is
a very wide range of searching exercises. The solutions to some of these are well known, and
available in the literature. Again, the decision to omit explicit references was deliberate (perhaps
dangerously so). Teachers often have to find some way of persuading the students to search the
literature for themselves, and this is not done by simply opening the journal at the right page for
them.
Acknowledgements
I am conscious of my gratitude to many people for their help and inspiration while this book has
been developed.
Like many others, I am grateful to Niklaus Wirth, whose programming languages and whose
writings on the subject of compiler construction and language design refute the modern trend
towards ever-increasing complexity in these areas, and serve as outstanding models of the way in
which progress should be made.
This project could not have been completed without the help of Hanspeter Mössenböck (author of
the original Coco/R compiler generator) and Francisco Arzu (who ported it to C++), who not only
commented on parts of the text, but also willingly gave permission for their software to be
distributed with the book. My thanks are similarly due to Richard Cichelli for granting permission
to distribute (with the software for Chapter 14) a program based on one he wrote for computing
minimal perfect hash functions, and to Christopher Cockburn for permission to include his
description of tonic sol-fa (used in Chapter 13).
I am grateful to Volker Pohlers for help with the port of Coco/R to Turbo Pascal, and to Dave
Gillespie for developing p2c, a most useful program for converting Modula-2 and Pascal code to
C/C++.
I am deeply indebted to my colleagues Peter Clayton, George Wells and Peter Wentworth for many
hours of discussion and fruitful suggestions. John Washbrook carefully reviewed the manuscript,
and made many useful suggestions for its improvement. Shaun Bangay patiently provided
incomparable technical support in the installation and maintenance of my hardware and software,
and rescued me from more than one disaster when things went wrong. To Rhodes University I am
indebted for the use of computer facilities, and for granting me leave to complete the writing of the
book. And, of course, several generations of students have contributed in intangible ways by their
reaction to my courses.
The development of the software in this book relied heavily on the use of electronic mail, and I am
grateful to Randy Bush, compiler writer and network guru extraordinaire, for his friendship, and for
his help in making the Internet a reality in developing countries in Africa and elsewhere.
But, as always, the greatest debt is owed to my wife Sally and my children David and Helen, for
their love and support through the many hours when they must have wondered where my priorities
lay.
Pat Terry
Rhodes University
Grahamstown
Trademarks
Ada is a trademark of the US Department of Defense.
Apple II is a trademark of Apple Corporation.
Borland C++, Turbo C++, TurboPascal and Delphi are trademarks of Borland
International Corporation.
GNU C Compiler is a trademark of the Free Software Foundation.
IBM and IBM PC are trademarks of International Business Machines Corporation.
Intel is a registered trademark of Intel Corporation.
MC68000 and MC68020 are trademarks of Motorola Corporation.
MIPS is a trademark of MIPS computer systems.
Microsoft, MS and MS-DOS are registered trademarks and Windows is a trademark of
Microsoft Corporation.
SPARC is a trademark of Sun Microsystems.
Stony Brook Software and QuickMod are trademarks of Gogesch Micro Systems, Inc.
occam and Transputer are trademarks of Inmos.
UCSD Pascal and UCSD p-System are trademarks of the Regents of the University of
California.
UNIX is a registered trademark of AT&T Bell Laboratories.
Z80 is a trademark of Zilog Corporation.
COMPILERS AND COMPILER
GENERATORS
an introduction with C++
© P.D. Terry, Rhodes University, 1996
e-mail p.terry@ru.ac.za
The Postscript ® edition of this book was derived from the on-line versions available at
http://www.scifac.ru.ac.za/compilers/, a WWW site that is occasionally updated, and which
contains the latest versions of the various editions of the book, with details of how to download
compressed versions of the text and its supporting software and courseware.
The original edition of this book, published originally by International Thomson, is now out of
print, but has a home page at http://cs.ru.ac.za/homes/cspt/compbook.htm. In preparing the on-line
edition, the opportunity was taken to correct the few typographical mistakes that crept into the first
printing, and to create a few hyperlinks to where the source files can be found.
Feel free to read and use this book for study or teaching, but please respect my copyright and do not
distribute it further without my consent. If you do make use of it I would appreciate hearing from
you.
CONTENTS
Preface
Acknowledgements
1 Introduction
1.1 Objectives
1.2 Systems programs and translators
1.3 The relationship between high-level languages and translators
2 Translator classification and structure
2.1 T-diagrams
2.2 Classes of translator
2.3 Phases in translation
2.4 Multi-stage translators
2.5 Interpreters, interpretive compilers, and emulators
3 Compiler construction and bootstrapping
3.1 Using a high-level host language
3.2 Porting a high-level translator
3.3 Bootstrapping
3.4 Self-compiling compilers
3.5 The half bootstrap
3.6 Bootstrapping from a portable interpretive compiler
3.7 A P-code assembler
4 Machine emulation
4.1 Simple machine architecture
4.2 Addressing modes
4.3 Case study 1 - a single-accumulator machine
4.4 Case study 2 - a stack-oriented computer
5 Language specification
5.1 Syntax, semantics, and pragmatics
5.2 Languages, symbols, alphabets and strings
5.3 Regular expressions
5.4 Grammars and productions
5.5 Classic BNF notation for productions
5.6 Simple examples
5.7 Phrase structure and lexical structure
5.8
-productions
5.9 Extensions to BNF
5.10 Syntax diagrams
5.11 Formal treatment of semantics
6 Simple assemblers
6.1 A simple ASSEMBLER language
6.2 One- and two-pass assemblers, and symbol tables
6.3 Towards the construction of an assembler
6.4 Two-pass assembly
6.5 One-pass assembly
7 Advanced assembler features
7.1 Error detection
7.2 Simple expressions as addresses
7.3 Improved symbol table handling - hash tables
7.4 Macro-processing facilities
7.5 Conditional assembly
7.6 Relocatable code
7.7 Further projects
8 Grammars and their classification
8.1 Equivalent grammars
8.2 Case study - equivalent grammars for describing expressions
8.3 Some simple restrictions on grammars
8.4 Ambiguous grammars
8.5 Context sensitivity
8.6 The Chomsky hierarchy
8.7 Case study - Clang
9 Deterministic top-down parsing
9.1 Deterministic top-down parsing
9.2 Restrictions on grammars so as to allow LL(1) parsing
9.3 The effect of the LL(1) conditions on language design
10 Parser and scanner construction
10.1 Construction of simple recursive descent parsers
10.2 Case studies
10.3 Syntax error detection and recovery
10.4 Construction of simple scanners
10.5 Case studies
10.6 LR parsing
10.7 Automated construction of scanners and parsers
11 Syntax-directed translation
11.1 Embedding semantic actions into syntax rules
11.2 Attribute grammars
11.3 Synthesized and inherited attributes
11.4 Classes of attribute grammars
11.5 Case study - a small student database
12 Using Coco/R - overview
12.1 Installing and running Coco/R
12.2 Case study - a simple adding machine
12.3 Scanner specification
12.4 Parser specification
12.5 The driver program
13 Using Coco/R - Case studies
13.1 Case study - Understanding C declarations
13.2 Case study - Generating one-address code from expressions
13.3 Case study - Generating one-address code from an AST
13.4 Case study - How do parser generators work?
13.5 Project suggestions
14 A simple compiler - the front end
14.1 Overall compiler structure
14.2 Source handling
14.3 Error reporting
14.4 Lexical analysis
14.5 Syntax analysis
14.6 Error handling and constraint analysis
14.7 The symbol table handler
14.8 Other aspects of symbol table management - further types
15 A simple compiler - the back end
15.1 The code generation interface
15.2 Code generation for a simple stack machine
15.3 Other aspects of code generation
16 Simple block structure
16.1 Parameterless procedures
16.2 Storage management
17 Parameters and functions
17.1 Syntax and semantics
17.2 Symbol table support for context sensitive features
17.3 Actual parameters and stack frames
17.4 Hypothetical stack machine support for parameter passing
17.5 Context sensitivity and LL(1) conflict resolution
17.6 Semantic analysis and code generation
17.7 Language design issues
18 Concurrent programming
18.1 Fundamental concepts
18.2 Parallel processes, exclusion and synchronization
18.3 A semaphore-based system - syntax, semantics, and code generation
18.4 Run-time implementation
Appendix A: Software resources for this book
Appendix B: Source code for the Clang compiler/interpreter
Appendix C: Cocol grammar for the Clang compiler/interpreter
Appendix D: Source code for a macro assembler
Bibliography
Index
Compilers and Compiler Generators © P.D. Terry, 2000
1 INTRODUCTION
1.1 Objectives
The use of computer languages is an essential link in the chain between human and computer. In
this text we hope to make the reader more aware of some aspects of
Imperative programming languages - their syntactic and semantic features; the ways of
specifying syntax and semantics; problem areas and ambiguities; the power and usefulness of
various features of a language.
Translators for programming languages - the various classes of translator (assemblers,
compilers, interpreters); implementation of translators.
Compiler generators - tools that are available to help automate the construction of translators
for programming languages.
This book is a complete revision of an earlier one published by Addison-Wesley (Terry, 1986). It
has been written so as not to be too theoretical, but to relate easily to languages which the reader
already knows or can readily understand, like Pascal, Modula-2, C or C++. The reader is expected
to have a good background in one of those languages, access to a good implementation of it, and,
preferably, some background in assembly language programming and simple machine architecture.
We shall rely quite heavily on this background, especially on the understanding the reader should
have of the meaning of various programming constructs.
Significant parts of the text concern themselves with case studies of actual translators for simple
languages. Other important parts of the text are to be found in the many exercises and suggestions
for further study and experimentation on the part of the reader. In short, the emphasis is on "doing"
rather than just "reading", and the reader who does not attempt the exercises will miss many, if not
most, of the finer points.
The primary language used in the implementation of our case studies is C++ (Stroustrup, 1990).
Machine readable source code for all these case studies is to be found on the IBM-PC compatible
diskette that is included with the book. As well as C++ versions of this code, we have provided
equivalent source in Modula-2 and Turbo Pascal, two other languages that are eminently suitable
for use in a course of this nature. Indeed, for clarity, some of the discussion is presented in a
pseudo-code that often resembles Modula-2 rather more than it does C++. It is only fair to warn the
reader that the code extracts in the book are often just that - extracts - and that there are many
instances where identifiers are used whose meaning may not be immediately apparent from their
local context. The conscientious reader will have to expend some effort in browsing the code.
Complete source for an assembler and interpreter appears in the appendices, but the discussion
often revolves around simplified versions of these programs that are found in their entirety only on
the diskette.
1.2 Systems programs and translators
Users of modern computing systems can be divided into two broad categories. There are those who
never develop their own programs, but simply use ones developed by others. Then there are those
who are concerned as much with the development of programs as with their subsequent use. This
latter group - of whom we as computer scientists form a part - is fortunate in that program
development is usually aided by the use of high-level languages for expressing algorithms, the use
of interactive editors for program entry and modification, and the use of sophisticated job control
languages or graphical user interfaces for control of execution. Programmers armed with such tools
have a very different picture of computer systems from those who are presented with the hardware
alone, since the use of compilers, editors and operating systems - a class of tools known generally
as systems programs - removes from humans the burden of developing their systems at the
machine level. That is not to claim that the use of such tools removes all burdens, or all possibilities
for error, as the reader will be well aware.
Well within living memory, much program development was done in machine language - indeed,
some of it, of necessity, still is - and perhaps some readers have even tried this for themselves when
experimenting with microprocessors. Just a brief exposure to programs written as almost
meaningless collections of binary or hexadecimal digits is usually enough to make one grateful for
the presence of high-level languages, clumsy and irritating though some of their features may be.
However, in order for high-level languages to be usable, one must be able to convert programs
written in them into the binary or hexadecimal digits and bitstrings that a machine will understand.
At an early stage it was realized that if constraints were put on the syntax of a high-level language
the translation process became one that could be automated. This led to the development of
translators or compilers - programs which accept (as data) a textual representation of an algorithm
expressed in a source language, and which produce (as primary output) a representation of the
same algorithm expressed in another language, the object or target language.
Beginners often fail to distinguish between the compilation (compile-time) and execution (run-time)
phases in developing and using programs written in high-level languages. This is an easy trap to fall
into, since the translation (compilation) is often hidden from sight, or invoked with a special
function key from within an integrated development environment that may possess many other
magic function keys. Furthermore, beginners are often taught programming with this distinction
deliberately blurred, their teachers offering explanations such as "when a computer executes a read
statement it reads a number from the input data into a variable". This hides several low-level
operations from the beginner. The underlying implications of file handling, character conversion,
and storage allocation are glibly ignored - as indeed is the necessity for the computer to be
programmed to understand the word read in the first place. Anyone who has attempted to program
input/output (I/O) operations directly in assembler languages will know that many of them are
non-trivial to implement.
A translator, being a program in its own right, must itself be written in a computer language, known
as its host or implementation language. Today it is rare to find translators that have been
developed from scratch in machine language. Clearly the first translators had to be written in this
way, and at the outset of translator development for any new system one has to come to terms with
the machine language and machine architecture for that system. Even so, translators for new
machines are now invariably developed in high-level languages, often using the techniques of
cross-compilation and bootstrapping that will be discussed in more detail later.
The first major translators written may well have been the Fortran compilers developed by Backus
and his colleagues at IBM in the 1950’s, although machine code development aids were in
existence by then. The first Fortran compiler is estimated to have taken about 18 person-years of
effort. It is interesting to note that one of the primary concerns of the team was to develop a system
that could produce object code whose efficiency of execution would compare favourably with that
which expert human machine coders could achieve. An automatic translation process can rarely
produce code as optimal as can be written by a really skilled user of machine language, and to this
day important components of systems are often developed at (or very near to) machine level, in the
interests of saving time or space.
Translator programs themselves are never completely portable (although parts of them may be), and
they usually depend to some extent on other systems programs that the user has at his or her
disposal. In particular, input/output and file management on modern computer systems are usually
controlled by the operating system. This is a program or suite of programs and routines whose job
it is to control the execution of other programs so as best to share resources such as printers,
plotters, disk files and tapes, often making use of sophisticated techniques such as parallel
processing, multiprogramming and so on. For many years the development of operating systems
required the use of programming languages that remained closer to the machine code level than did
languages suitable for scientific or commercial programming. More recently a number of successful
higher level languages have been developed with the express purpose of catering for the design of
operating systems and real-time control. The most obvious example of such a language is C,
developed originally for the implementation of the UNIX operating system, and now widely used in
all areas of computing.
1.3 The relationship between high-level languages and translators
The reader will rapidly become aware that the design and implementation of translators is a subject
that may be developed from many possible angles and approaches. The same is true for the design
of programming languages.
Computer languages are generally classed as being "high-level" (like Pascal, Fortran, Ada,
Modula-2, Oberon, C or C++) or "low-level" (like ASSEMBLER). High-level languages may
further be classified as "imperative" (like all of those just mentioned), or "functional" (like Lisp,
Scheme, ML, or Haskell), or "logic" (like Prolog).
High-level languages are claimed to possess several advantages over low-level ones:
Readability: A good high-level language will allow programs to be written that in some ways
resemble a quasi-English description of the underlying algorithms. If care is taken, the coding
may be done in a way that is essentially self-documenting, a highly desirable property when
one considers that many programs are written once, but possibly studied by humans many
times thereafter.
Portability: High-level languages, being essentially machine independent, hold out the
promise of being used to develop portable software. This is software that can, in principle
(and even occasionally in practice), run unchanged on a variety of different machines -
provided only that the source code is recompiled as it moves from machine to machine.
To achieve machine independence, high-level languages may deny access to low-level
features, and are sometimes spurned by programmers who have to develop low-level machine
dependent systems. However, some languages, like C and Modula-2, were specifically
designed to allow access to these features from within the context of high-level constructs.
Không có nhận xét nào:
Đăng nhận xét