Parsing Techniques, A Practical Guide (2/e), by Dick Grune and Ceriel J.H. Jacobs
This book covers a huge range of parsing techniques – every parsing technique I’d heard of, and many more. Once Donald Knuth gets ready to produce volume 5 of The Art of Computer Programming, I bet he’ll draw on this book.
The authors begin by describing grammars and parsing, then work their way through a variety of techniques. They start with general non-directional parsers that access text in any order, then regular grammars. Then they cover top-down and bottom-up parsers, including non-deterministic/backtracking ones.
From there they cover parser methods you might find in a typical compiler class: top-down and bottom-up deterministic parsers such as LL and LR (and variants).
They look at a few other areas: substring parsing, parsing intersections of languages, parallel parsing, error handling, and more.
Their explanations of the various parsers are very clear, usually with helpful examples to show how they work.
The authors also take the time to explain intermediate concepts. For example, some parsers do better if they get avoid empty rules, or avoid unit rules (such as A -> B), or meet other restrictions. Rather than assume you’d know how to make the restriction, they provide an algorithm to systematically make the changes.
The book closes with a bibliography of 400+ references.
Parsing Techniques is not for everybody by any stretch. If you’re a researcher in parsers, you’d certainly value the algorithms, examples, and bibliography. If you’re a compiler implementer and need a new twist on things, I’d expect you’d find some cool tricks here. If you’re interested in algorithms, you’ll find dozens of them tackling the same problem.