Parsing Techniques: A Practical Guide (Monographs in Computer Science) (Hardcover)

~ Dick Grune (Author), Ceriel J. H. Jacobs (Author)
Key Phrases: connectionist parsers, definite clause, parsing technology, Lecture Notes, Deterministic Bottom-Up Parsing, Computer Science (more...)

Editorial Reviews

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

Product Details

• Hardcover: 662 pages
• Publisher: Springer; 2nd edition (November 28, 2007)
• Language: English
• ISBN-10: 038720248X
• ISBN-13: 978-0387202488
• Product Dimensions: 9.3 x 6.3 x 1.4 inches
• Shipping Weight: 2.3 pounds (View shipping rates and policies)
• Average Customer Review: 5.0 out of 5 stars  See all reviews (4 customer reviews)
• Amazon.com Sales Rank: #141,088 in Books (See Bestsellers in Books)

  Popular in these categories: (What's this?)

  #5 in	Books > Computers & Internet > Software > Natural Language Processing
  #25 in	Books > Computers & Internet > Computer Science > Software Engineering > Design Tools & Techniques
  #82 in	Books > Computers & Internet > Software > Word Processors & Editors

Customer Reviews

Most Helpful Customer Reviews

25 of 25 people found the following review helpful:

5.0 out of 5 stars The clearest, most comprehensive survey of the field, January 26, 2008

By	Joshua Haberman (Seattle, WA USA) - See all my reviews (REAL NAME)

I have spent the last six months of my life learning as much as I can about parsing. I own half a shelf of compiler books, and I have flipped through the pages of half a shelf more.

No other book approaches the clarity and comprehensiveness of this book.

When you try to read most literature about parsing, authors tend to throw around a lot of terms without explaining them. What exactly is a "deterministic" parser, a "canonical" parser, a "directional" parser? Grune and Jacobs explain every one of these distinctions lucidly, and put all known algorithms in context of how they compare to the rest of the field. How do the algorithms compare in what languages they can parse, how fast they are, and how much of the work can be done ahead of time? The book addresses all of these trade-offs, but doesn't stop at asymptotic complexity: in chapter 17 (the comparative survey), they note that general parsers may be a factor of ten or so slower than deterministic methods, even though both are linear. This high-level overview and comparative survey are something I was desperately seeking, and I've found nothing comparable to them anywhere.

There is also a lot of important background information that other authors tend to assume you know: for example, did you know that when authors say "LL" they almost always mean "strong LL" unless they specifically say "full LL?" Are you totally clear on the difference between strong LL, simple LL, and full LL? If you're not sure, Grune and Jacobs will give you all the explanation you need to fully understand.

This book strikes a perfect balance between breadth and depth. All significant algorithms are covered, most with enough detail to fully understand and implement them, but Grune and Jacobs punt on less practical material like proofs or rigorous formal descriptions. That information is never more than a citation away though, thanks to the 417-entry annotated bibliography, which gives you not only references to source material but a paragraph or two describing their key results.

I couldn't be happier about adding this book to my bookshelf of compiler books -- it quickly became the book I refer to most often, and I thank Grune and Jacobs for this superb guide to this vast and diverse field of computer science.

7 of 8 people found the following review helpful:

5.0 out of 5 stars This edition is NOT available on-line, January 22, 2008

By	Robert L. Knighten (The Dalles, Oregon United States) - See all my reviews (REAL NAME)

The first edition is available at Grune's web site but this very much expanded second edition is not.

5 of 7 people found the following review helpful:

5.0 out of 5 stars make it approachable, October 7, 2002

By	Dhiren (India) - See all my reviews

This review is from: Parsing Techniques: A Practical Guide (Ellis Horwood Series in Computers and Their Applications) (Hardcover)

After searching all over for a way to understand the translation field and looking the dragon book and all, this is a great find. I am a practicing software engineer with training in electronics (good old forgotten days) and did not like math classes. This book is a great way to make this topic approachable for a practicing industry developer. Admittedly is a difficult read but if you want to understand something it needs the effort. If you cannot read the # * + etc in the other compiler books this books makes it comprehendible.