Parsing Techniques - Second Edition
Dick Grune and Ceriel J.H. Jacobs
VU University Amsterdam, The Netherlands
Published (2008) by Springer US, ISBN 978-1-4419-1901-4
Originally published by Ellis Horwood, Chichester, England, 1990; ISBN 0 13 651431 6
Description
This 622-page book treats parsing in its own right, in greater depth than is found in most computer science and linguistics books. It offers a clear, accessible, and thorough discussion of many different parsing techniques with their interrelations and applicabilities, including error recovery techniques. Unlike most books, it treats (almost) all parsing methods, not just the popular ones.
No advanced mathematical knowledge is required; the book is based on an intuitive and engineering-like understanding of the processes involved in parsing, rather than on the set manipulations often used in implementation.
The book features the following chapters:
- Introduction
- Grammars as a Generating Device
- Introduction to Parsing
- General Non-Directional Parsing (Unger, CYK)
- Regular Grammars and Finite-State Automata
- General Directional Top-Down Parsing
- General Directional Bottom-Up Parsing
- Deterministic Top-Down Parsing (LL(1), LL(k), LL-regular)
- Deterministic Bottom-Up Parsing (LR(0), LR(1), LR(k), LALR(1), SLR(1), LR-regular)
- Non-Canonical Parsers (LC, Partitioned LL, NSLR(1), LR(k, ∞), Partitioned LR)
- Generalized Deterministic Parsers (GLR, GLL, GLC)
- Substring Parsing (linear-time substring using GLR)
- Parsing as Intersection (Parsing of FSAs, Parse Trees)
- Parallel Parsing (GLR, Process-configuration, Connectionist, Boolean Circuit, Rytter)
- Non-Chomsky Grammars and Their Parsers (VW, TAG)
- Error Handling (FOLLOW-set, Continuation)
- Practical Parser Writing and Usage
- Annotated Bibliography (400+ entries)
Complete Literature References and Additional Information
A Web page with additional material can be reached by clicking here. It contains three items:
- Complete Literature References: The printed book contains only the about 400 literature references that are referred to in the book itself, all of them with annotations. The complete list of literature references comprises about 1700 entries of which around 1100 are annotated. It consists of augmented versions of the Table of Contents, Chapter 18, the Authors' Index, and the Subject Index, each reflecting in its way the added entries.
- Code for many parsers from the book, plus various other related programs.
- Some papers referred to in the book or the complete literature references that are not easily accessible otherwise.
There is also a small Errata page.
About the authors
Dick Grune is a retired lecturer of Programming Languages and Compiler Construction at the VU University Amsterdam, and is a coauthor of the text books Programming Language Essentials, Parsing Techniques - A Practical Guide, and Modern Compiler Design.
Ceriel Jacobs has been working on numerous programming projects since the beginning of the 1980s. He is a coauthor of the text books Parsing Techniques - A Practical Guide, and Modern Compiler Design.