LR parsing has become a widely used method of syntax analysis; this
is largely due to the availability of parser generators and compiler-
compilers based on LR techniques. However, the readily available ac
counts of the theory of these techniques are either superficial or are
weighed down with tedious mathematical detail of a merely technical
nature. At the same time, much of the knowledge of practical matters
concerning the implementation and use of LR parsers is scattered in
journals or known only through experience. This book has been written
to bring together an accessible account of LR theory and a description
of the implementation techniques used in conjunction with LR parsers.
It is aimed primarily at users of LR parsers who believe that it is unde
sirable to use complex tools without understanding how they work.
The book does not quite fall neatly into two parts called 'Theory' and
'Practice', but most of the theory is to be found in Chapters 2 to 5,
while Chapters 6 to 10 are mainly concerned with practical matters.
Chapter 4 contains the theoretical core, and is based on Heilbrunner's
account of LR theory, which uses parsing automata and item grammars
to prove that LR parsers do indeed work, and that the widely used parser
construction techniques are correct. In addition, the theory allows the
class of grammars which can be parsed by LR techniques to be related to
other interesting grammar classes, and certain complexity results to be
derived in a straightforward way. This approach to the theory provides
an account of LR parsers more closely in line with the informal notion of
a bottom up parser using lookahead to make its parsing decisions, than
a more traditional method based on 'valid items' and 'viable prefixes'.
The elements of formal language and automata theory required for an
understanding of LR theory are introduced in Chapter 2, and there is an
appendix on relations and reflexive transitive closure computations. No
prior familiarity with this material is assumed, but some mathematical
ability and a little knowledge of set theory and its notation is required.
Detailed proofs of most of the important results are included, but these
may be omitted on a first reading, if necessary.