Parsing Techniques: A Practical Guide

Front Cover
Springer Science & Business Media, Oct 29, 2007 - Computers - 662 pages

Parsing, also referred to as syntax analysis, has been and continues to be an essential part of computer science and linguistics. Today, parsing techniques are also implemented in a number of other disciplines, including but not limited to, document preparation and conversion, typesetting chemical formulae, and chromosome recognition.

This second edition presents new developments and discoveries that have been made in the field. Parsing techniques have grown considerably in importance, both in computational linguistics where such parsers are the only option, and computer science, where advanced compilers often use general CF parsers. Parsing techniques provide a solid basis for compiler construction and contribute to all existing software: enabling Web browsers to analyze HTML pages and PostScript printers to analyze PostScript. Some of the more advanced techniques are used in code generation in compilers and in data compression.

In linguistics, the importance of formal grammars was recognized early on, but only recently have the corresponding parsing techniques been applied. Also their importance as general pattern recognizers is slowly being acknowledged. This text Parsing Techniques explores new developments, such as generalized deterministic parsing, linear-time substring parsing, parallel parsing, parsing as intersection, non-canonical methods, and non-Chomsky systems.

To provide readers with low-threshold access to the full field of parsing techniques, this new edition uses a two-tiered structure. The basic ideas behind the dozen or so existing parsing techniques are explained in an intuitive and narrative style, and problems are presented at the conclusion of each chapter, allowing the reader to step outside the bounds of the covered material and explore parsing techniques at various levels. The reader is also provided with an extensive annotated bibliography as well as hints and partial solutions to a number of problems. In the bibliography, hundreds of realizations and improvements of parsing techniques are explained in a much terser, yet still informal, style, improving its readability and usability.

The reader should have an understanding of algorithmic thinking, especially recursion; however, knowledge of any particular programming language is not required.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Selected pages

Contents

1 Introduction
1
2 Grammars as a Generating Device
5
3 Introduction to Parsing
61
4 General NonDirectional Parsing
103
5 Regular Grammars and FiniteState Automata
137
6 General Directional TopDown Parsing
165
7 General Directional BottomUp Parsing
199
8 Deterministic TopDown Parsing
234
12 Substring Parsing
399
13 Parsing as Intersection
425
14 Parallel Parsing
443
15 NonChomsky Grammars and Their Parsers
472
16 Error Handling
521
17 Practical Parser Writing and Usage
545
18 Annotated Bibliography
575
A Hints and Solutions to Selected Problems
644

9 Deterministic BottomUp Parsing
263
10 NonCanonical Parsers
342
11 Generalized Deterministic Parsers
381

Other editions - View all

Common terms and phrases

Popular passages

Page 10 - A, B, AA, AB, BA, BB, AAA, AAB, ABA, ABB, BAA, BAB, BBA, BBB, AAAA.