عنوان

Parsing schemata :

(Number (ISBN

3642644511

(Number (ISBN

9783642644511

Number

b539751

Title Proper

Parsing schemata :

General Material Designation

[Book]

Other Title Information

a framework for specification and analysis of parsing algorithms

First Statement of Responsibility

Klaas Sikkel

Edition Statement

Softcover reprint of the original 1. ed. 1997

Place of Publication, Distribution, etc.

Berlin

Name of Publisher, Distributor, etc.

Springer Berlin

Date of Publication, Distribution, etc.

2013

Specific Material Designation and Extent of Item

XVI, 365 s. : illustrations

Series Title

Texts in theoretical computer science

Text of Note

An EATCS series

Text of Note

Foreword.- Acknowledgements.- I. Exposition.- 1. Introduction.- 1.1 The structure of language.- 1.2 Parsing.- 1.3 Parsing schemata.- 1.4 Overview.- 2. The primordial soup framework.- 2.1 Primordial soup.- 2.2 Restricted versions of the primordial soup.- 2.3 Extensions and related formalisms.- 2.4 From primordial soup to parsing schemata.- II. Foundation.- 3. Tree-based parsing schemata.- 3.1 Context-free grammars.- 3.2 Some small extensions to context-free grammars.- 3.3 Deduction systems.- 3.4 Enhanced deduction systems.- 3.5 Tree-based parsing schemata.- 3.6 Conclusion.- 4. Item-based parsing schemata.- 4.1 Quotient deduction systems.- 4.2 Quotients of enhanced deduction systems.- 4.3 Quotient parsing schemata.- 4.4 Item-based parsing schemata.- 4.5 The relation between Sections 4.3 and 4.4.- 4.6 Examples of parsing schemata.- 4.7 Conclusion.- 5. Refinement and generalization.- 5.1 Mappings between deduction systems.- 5.2 Refinement: a formal approach.- 5.3 Some examples of refinement.- 5.4 Generalization.- 5.5 Conclusion.- 6. Filtering.- 6.1 Redundancy elimination.- 6.2 Static filtering.- 6.3 Dynamic filtering.- 6.4 Step contraction.- 6.5 The family of Earley-like parsing schemata.- 6.6 A summary of relations between parsing schemata.- 6.7 Conclusion.- III. Application.- 7. An introduction to unification grammars.- 7.1 Unification-based parsing schemata: a preview.- 7.2 The example grammar UG1.- 8. Parsing schemata for unification grammars.- 8.1 Feature structures.- 8.2 Feature lattices.- 8.3 Composite feature structures.- 8.4 Composite feature lattices.- 8.5 Unification grammars.- 8.6 Composition of decorated trees.- 8.7 Parsing schemata for unification grammars.- 8.8 The example revisited.- 8.9 Other grammar formalisms.- 8.10 Related approaches.- 8.11 Conclusion.- 9. Topics in unification grammar parsing.- 9.1 Feature graph unification.- 9.2 Nondestructive graph unification.- 9.3 Further improvements.- 9.4 Disjunctive feature structures.- 9.5 Restriction.- 9.6 Default restrictors.- 9.7 Two-pass parsing.- 9.8 Conclusion.- 10. Left-Corner chart parsing.- 10.1 Chart parsers.- 10.2 Left-Corner chart parsing.- 10.3 Correctness of the LC chart parser.- 10.4 An LC chart parser with simplified items.- 10.5 The relation between pLC, sLC, and LC.- 10.6 Conclusion.- 11. Head-Corner chart parsing.- 11.1 Context-free Head Grammars.- 11.2 A predictive Head-Corner chart parser.- 11.3 Correctness of the HC chart parser.- 11.4 HC chart parsing in cubic time.- 11.5 Correctness of sHC.- 11.6 Complexity analysis of sHC.- 11.7 The relation between pHC, sHC, and dVH.- 11.8 HC parsing of unification grammars.- 11.9 Related approaches.- 11.10 Conclusion.- 12. Generalized LR parsing.- 12.1 Preliminaries.- 12.2 LR parsing.- 12.3 Generalized vs. deterministic LR parsing.- 12.4 Tomita's algorithm.- 12.5 A formal definition of Tomita's algorithm.- 12.6 Pros and cons of Tomita's algorithm.- 12.7 An annotated version of Tomita's algorithm.- 12.8 Parsing Schemata for LR(0) and SLR(l).- 12.9 Conclusion.- 13. Parallel Bottom-up Tomita parsing.- 13.1 The PBT parsing schema.- 13.2 A PBT parser.- 13.3 A more efficient PBT parser.- 13.4 The construction of a distributed parse list.- 13.5 A formal definition of the PBT algorithm.- 13.6 Empirical results.- 13.7 Related approaches.- 13.8 Conclusion.- 14. Boolean circuit parsing.- 14.1 Preliminary concepts.- 14.2 Recognizing networks.- 14.3 Parsing networks.- 14.4 Some further issues.- 14.5 Rytter's algorithm.- 14.6 Correctness of Rytter's algorithm.- 14.7 A parsing network for Rytter's algorithm.- 14.8 Conditional parsing systems.- 14.9 Related approaches.- 14.10 Conclusion.- 15. Conclusions.- 15.1 Some general remarks.- 15.2 Research contributions of this book.- 15.6 Ideas for future research.

Text of Note

Parsing, the syntactic analysis of language, has been studied extensively in computer science and computational linguistics.

Class number

Book number

Klaas Sikkel

Klaas Sikkel

Electronic name

[Book]

Y