Ebook: Parsing Schemata: A Framework for Specification and Analysis of Parsing Algorithms
Author: Klaas Sikkel
- Genre: Computers // Algorithms and Data Structures
- Tags: Algorithm Analysis and Problem Complexity, Programming Languages Compilers Interpreters, Artificial Intelligence (incl. Robotics)
- Series: Texts in Theoretical Computer Science. An EATCS Series
- Year: 1997
- Publisher: Springer
- Language: English
- pdf
Parsing, the syntactic analysis of language, has been studied extensively in computer science and computational linguistics. Computer programs and natural languages share an underlying theory of formal languages and require efficient parsing algorithms. This introduction reviews the theory of parsing from a novel perspective. It provides a formalism to capture the essential traits of a parser that abstracts from the fine detail and allows a uniform description and comparison of a variety of parsers, including Earley, Tomita, LR, Left-Corner, and Head-Corner parsers. The emphasis is on context-free phrase structure grammar and how these parsers can be extended to unification formalisms. The book combines mathematical rigor with high readability and is suitable as a graduate course text.
Content:
Front Matter....Pages I-XVI
Front Matter....Pages 1-1
Introduction....Pages 3-17
The primordial soup framework....Pages 19-36
Front Matter....Pages 37-37
Tree-based parsing schemata....Pages 39-57
Item-based parsing schemata....Pages 59-83
Refinement and generalization....Pages 85-100
Filtering....Pages 101-122
Front Matter....Pages 123-123
An introduction to unification grammars....Pages 125-135
Parsing schemata for unification grammars....Pages 137-172
Topics in unification grammar parsing....Pages 173-200
Left-Corner chart parsing....Pages 201-220
Head-Corner chart parsing....Pages 221-252
Generalized LR parsing....Pages 253-288
Parallel Bottom-up Tomita parsing....Pages 289-310
Boolean circuit parsing....Pages 311-344
Conclusions....Pages 345-348
Back Matter....Pages 349-365
Content:
Front Matter....Pages I-XVI
Front Matter....Pages 1-1
Introduction....Pages 3-17
The primordial soup framework....Pages 19-36
Front Matter....Pages 37-37
Tree-based parsing schemata....Pages 39-57
Item-based parsing schemata....Pages 59-83
Refinement and generalization....Pages 85-100
Filtering....Pages 101-122
Front Matter....Pages 123-123
An introduction to unification grammars....Pages 125-135
Parsing schemata for unification grammars....Pages 137-172
Topics in unification grammar parsing....Pages 173-200
Left-Corner chart parsing....Pages 201-220
Head-Corner chart parsing....Pages 221-252
Generalized LR parsing....Pages 253-288
Parallel Bottom-up Tomita parsing....Pages 289-310
Boolean circuit parsing....Pages 311-344
Conclusions....Pages 345-348
Back Matter....Pages 349-365
....