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)
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.
Parsing Techniques - Second Edition / Dick Grune /
dick@dickgrune.com
|