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 wellwritten
program with each part in its correct place, the author's goal will have been
reached.
We have utilized the problem-solution format. Some sections are collections
of problems having a common topic, while others are devoted to one specific
algorithm (e.g., Section 14 covers LR(1)-parsing). The sections are more or less
independent, but the concluding sections are more difficult. Sections 1-7 cover
material usually included in undergradute courses while Sections 13-14 are more
appropriate for a graduate compiler course. In each section 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 that the reader look at the solutions only after making a
good faith attempt to solve the problems independently.
Pascal is used as a programming language to write program examples; however,
readers familiar with some other procedural language (C, Modula, Oberon,
etc.) will encounter no difficulties.
Most of the problems, of course, are well known. References are rare, but this
does not mean that the problem or algorithm is new. However, we hope that in
some cases the algorithm or the proof is explained better than what is found in
other sources.
This book is addressed both to the ambitious student who wants to test and
improve his/her skills and to the instructor looking for problems for his/her class.