عنوان

Parsing schemata :

شابک

3642644511

شابک

9783642644511

شماره

b539751

عنوان اصلي

Parsing schemata :

نام عام مواد

[Book]

ساير اطلاعات عنواني

a framework for specification and analysis of parsing algorithms

نام نخستين پديدآور

Klaas Sikkel

وضعيت ويراست

Softcover reprint of the original 1. ed. 1997

محل نشرو پخش و غیره

Berlin

نام ناشر، پخش کننده و غيره

Springer Berlin

تاریخ نشرو بخش و غیره

2013

نام خاص و کميت اثر

XVI, 365 s. : illustrations

عنوان فروست

Texts in theoretical computer science

متن يادداشت

An EATCS series

متن يادداشت

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.

متن يادداشت

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

شماره رده

نشانه اثر

مستند نام اشخاص تاييد نشده

Klaas Sikkel

مستند نام اشخاص تاييد نشده

Klaas Sikkel

نام الکترونيکي

نوع ماده

[Book]

تكميل شده

Y