Parsing Techniques

A Practical Guide

2nd Edition

By Dick Grune , Ceriel J.H. Jacobs

Parsing Techniques Cover Image

This second edition of Grune and Jacobs’ brilliant work presents new developments and discoveries that have been made in the field of parsing, or syntax analysis. Parsing has been and continues to be an essential part of computer science and linguistics.

Full Description

  • ISBN13: 978-0-3872-0248-8
  • 688 Pages
  • User Level: Science
  • Publication Date: October 29, 2007
  • Available eBook Formats: PDF
  • eBook Price: $89.95
Buy eBook Buy Print Book Add to Wishlist

Related Titles

Full Description
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.
Table of Contents

Table of Contents

  1. Introduction.
  2. Grammars as a Generating Device.
  3. Introduction to Parsing.
  4. General Non
  5. Directional Parsing.
  6. Regular Grammars and Finite
  7. State Automata.
  8. General Directional Top
  9. Down Parsing.
  10. General Directional Bottom
  11. Up Parsing.
  12. Deterministic Top
  13. Down Parsing.
  14. Deterministic Bottom
  15. Up Parsing.
  16. Non
  17. Canonical Parsers.
  18. Generalized Deterministic Parsers.
  19. Substring Parsing.
  20. Parsing as Intersection.
  21. Parallel Parsing.
  22. Non
  23. Chonsky Grammars and Their Parsers.
  24. Error Handling.
  25. Practical Parser Writing and Usage.
  26. Annotated Bibliography.
  27. Hints and Solutions to Selected Problems.
  28. Author Index.
  29. Subject Index.
Errata

Please Login to submit errata.

No errata are currently published