ceriel@cs.vu.nl (Ceriel Jacobs) (12/03/90)
This note is to announce a book on parsing that some of you may find
interesting: "Parsing techniques: a practical guide", by Dick Grune
and Ceriel J.H. Jacobs, published by Ellis Horwood Limited. The ISBN
is 0-13-651431-6.
Parsing (also known as syntactic analysis) is traditionally used for
programming languages and natural languages, but is also a powerful
pattern matching technique. This book offers a clear, accessible,
and thorough discussion of many different parsing techniques with
their interrelations and applicabilities, including error recovery
techniques; the book also features an extensive, annotated
bibliography.
Parsing is treated in its own right, in greater depth than is usually
found in most compiler construction books. No advanced mathematical
knowledge is required, and the authors emphasize the intuitive and
engineering-like understanding of the processes involved in parsing,
rather than the set manipulations used in practice.
The book will be of value to all those who use a computer to recover
non-apparent structure in linearized data - computer scientists,
linguists, geologists and musicologists among others.
Contents:
Preface
1. Introduction
1.1 Parsing as a craft
1.2 The approach used
1.3 Outline of the contents
1.4 The annotated bibliography
2. Grammars as a generating device
2.1 Languages as infinite sets
2.2 Formal grammars
2.3 The Chomsky hierarchy of grammars and languages
2.4 VW grammars
2.5 Actually generating sentences from a grammar
2.6 To shrink or not to shrink
2.7 A characterization of the limitations of CF and FS grammars
2.8 Hygiene in grammars
2.9 The semantic connection
2.10 A metaphorical comparison of grammar types
3. Introduction to parsing
3.1 Various kinds of ambiguity
3.2 Linearization of the parse tree
3.3 Two ways to parse a sentence
3.4 Non-deterministic automata
3.5 Recognition and parsing for Type 0 to Type 4 grammars
3.6 An overview of parsing methods
4. General non-directional methods
4.1 Unger's parsing method
4.2 The CYK parsing method
5. Regular grammars and finite-state automata
5.1 Applications of regular grammars
5.2 Producing from a regular grammar
5.3 Parsing with a regular grammar
6. General directional top-down methods
6.1 Imitating left-most productions
6.2 The pushdown automaton
6.3 Breadth-first top-down parsing
6.4 Eliminating left-recursion
6.5 Depth-first (backtracking) parsers
6.6 Recursive descent
6.7 Definite Clause grammars
7. General bottom-up parsing
7.1 Parsing by searching
7.2 Top-down restricted breadth-first bottom-up parsing (Earley)
8. Deterministic top-down methods
8.1 Replacing search by table look-up
8.2 LL(1) grammars
8.3 LL(k) grammars
8.4 Extended LL(1) grammars
9. Deterministic bottom-up parsing
9.1 Simple handle-isolating techniques
9.2 Precedence parsing
9.3 Bounded-context parsing
9.4 LR methods
9.5 LR(1)
9.6 LALR(1) parsing
9.7 Further developments of LR methods
9.8 Tomita's parser
9.9 Non-canonical parsers
9.10 LR(k) as an ambiguity test
10. Error handling
10.1 Detection versus recovery versus correction
10.2 Parsing techniques and error detection
10.3 Recovering from errors
10.4 Global error handling
10.5 Ad hoc methods
10.6 Regional error handling
10.7 Local error handling
10.8 Suffix parsing
11. Comparative survey
11.1 Considerations
11.2 General parsers
11.3 Linear-time parsers
12. A simple general context-free parser
12.1 Principles of the parser
12.2 The program
12.3 Parsing in polynomial time
13. Annotated bibliography
13.1 Miscellaneous literature
13.2 Unrestricted PS and CS grammars
13.3 Van Wijngaarden grammars and affix grammars
13.4 General context-free parsers
13.5 LL parsing
13.6 LR parsing
13.7 Left-corner parsing
13.8 Precedence and bounded-context parsing
13.9 Finite-state automata
13.10 Natural language handling
13.11 Error handling
13.12 Transformations on grammars
13.13 General books on parsing
13.14 Some books on computer science
Author index
Index
--
Ceriel Jacobs, Dept. of Mathematics and Computer Science, Vrije Universiteit,
De Boelelaan 1081a, 1081 HV Amsterdam, The Netherlands
Voice: +31 20 5485577 Email: ceriel@cs.vu.nl Fax: +31 20 427705
--
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers. Meta-mail to compilers-request.