new book on parsing

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
--

Return to the comp.compilers page.
Search the comp.compilers archives again.