|
Somebody once said that one may prove the correctness of an algorithm, but not of a
program. One of the main goals of this book is to convince the reader that things are
not so bad.
A well-known programmer, C.A.R. Hoare, said that the beauty of a program is
not an additional benefit but a criterion that separates success from failure. If, while
solving problems in this book, you come to appreciate the beauty of a well-written
program with each part in its correct place, the author’s goal will have been reached.
Theoretically this book can be used to study programming without a computer:
one could write (correct) programs with pencil and paper. But in practice the ability
to run the programs is a challenge and a reward that makes programming a fun.
We have utilized the problem-solution format. Some chapters are collections of
problems having a common topic, while others are devoted to one specific algorithm
(e.g., chapter 16 covers LR(1)-parsing). The chapters are more or less independent,
but the concluding chapters are more difficult. Chapters 1–7 cover material usually
included in undergraduate courses while chapters 15–16 are more appropriate for a
graduate compiler course. In each chapter we have tried to give problems at different
levels starting with easy exercises.
Problems are usually provided with solutions, answers or hints. However, we
strongly recommend to read the solution only after the reader makes a good faith
attempt to solve it independently.
The book is restricted to “micro-programming” leaving aside another very important
topic: how to split the program into a manageable parts with nice interfaces
between them. (Probably this can be learned only by reading and modifying rather
large programs.)
Pascal is used as a programming language; though being outdated, it is reasonably
clear, so the readers familiar with any other procedural language (C, Modula,
Oberon, etc.) will encounter no difficulties. For the reader’s convenience, a short appendix
is added that lists basic differences between Pascal and C. It is intended to
help the reader who knows C to understand the program notation in the book (but
cannot replace textbooks on C).
|
|