Parsing Techniques: A Practical Guide, 2nd Edition (Monographs In Computer Science) Guide (2nd Edition)
parsing-techniques--a-practical-guide--2ed
User Manual:
Open the PDF directly: View PDF
Page Count: 677 [warning: Documents this large are best viewed by clicking the View PDF Link!]
- Contents
- Preface to the Second Edition
- Preface to the First Edition
- 1. Introduction
- 2. Grammars as a Generating Device
- 2.1 Languages as Infinite Sets
- 2.2 Formal Grammars
- 2.3 The Chomsky Hierarchy of Grammars and Languages
- 2.4 Actually Generating Sentences froma Grammar
- 2.5 To Shrink or Not To Shrink
- 2.6 Grammars that Produce the Empty Language
- 2.7 The Limitations of CF and FS Grammars
- 2.8 CF and FS Grammars as Transition Graphs
- 2.9 Hygiene in Context-Free Grammars
- 2.10 Set Properties of Context-Free and Regular Languages
- 2.11 The Semantic Connection
- 2.12 A Metaphorical Comparison of Grammar Types
- 2.13 Conclusion
- 3. Introduction to Parsing
- 3.1 The Parse Tree
- 3.2 Two Ways to Parse a Sentence
- 3.3 Non-Deterministic Automata
- 3.4 Recognition and Parsing for Type 0 to Type 4 Grammars
- 3.5 An Overview of Context-Free Parsing Methods
- 3.6 The "Strength" of a Parsing Technique
- 3.7 Representations of Parse Trees
- 3.8 When are we done Parsing?
- 3.9 Transitive Closure
- 3.10 The Relation between Parsing and Boolean Matrix Multiplication
- 3.11 Conclusion
- 4. General Non-Directional Parsing
- 4.1 Unger's Parsing Method
- 4.2 The CYK Parsing Method
- 4.2.1 CYK Recognition with General CF Grammars
- 4.2.2 CYK Recognition with a Grammar in Chomsky Normal Form
- 4.2.3 Transforming a CF Grammar into Chomsky Normal Form
- 4.2.4 The Example Revisited
- 4.2.5 CYK Parsing with Chomsky Normal Form
- 4.2.6 Undoing the Effect of the CNF Transformation
- 4.2.7 A Short Retrospective of CYK
- 4.2.8 Getting Parse-Forest Grammars from CYK Parsing
- 4.3 Tabular Parsing
- 4.4 Conclusion
- 5. Regular Grammars and Finite-State Automata
- 5.1 Applications of Regular Grammars
- 5.2 Producing from a Regular Grammar
- 5.3 Parsing with a Regular Grammar
- 5.4 Manipulating Regular Grammars and Regular Expressions
- 5.5 Manipulating Regular Languages
- 5.6 Left-Regular Grammars
- 5.7 Minimizing Finite-State Automata
- 5.8 Top-Down Regular Expression Recognition
- 5.9 Semantics in FS Systems
- 5.10 Fast Text Search Using Finite-State Automata
- 5.11 Conclusion
- 6. General Directional Top-Down Parsing
- 7. General Directional Bottom-Up Parsing
- 8. Deterministic Top-Down Parsing
- 9. Deterministic Bottom-Up Parsing
- 9.1 Simple Handle-Finding Techniques
- 9.2 Precedence Parsing
- 9.3 Bounded-Right-Context Parsing
- 9.4 LR Methods
- 9.5 LR(0)
- 9.6 LR(1)
- 9.7 LALR(1)
- 9.8 SLR(1)
- 9.9 Conflict Resolvers
- 9.10 Further Developments of LR Methods
- 9.11 Getting a Parse Tree Grammar from LR Parsing
- 9.12 Left and Right Contexts of Parsing Decisions
- 9.13 Exploiting the Left and Right Contexts
- 9.14 LR(k) as an Ambiguity Test
- 9.15 Conclusion
- 10. Non-Canonical Parsers
- 11. Generalized Deterministic Parsers
- 12. Substring Parsing
- 13. Parsing as Intersection
- 14. Parallel Parsing
- 15. Non-Chomsky Grammars and Their Parsers
- 16. Error Handling
- 16.1 Detection versus Recovery versus Correction
- 16.2 Parsing Techniques and Error Detection
- 16.2.1 Error Detection in Non-Directional Parsing Methods
- 16.2.2 Error Detection in Finite-State Automata
- 16.2.3 Error Detection in General Directional Top-Down Parsers
- 16.2.4 Error Detection in General Directional Bottom-Up Parsers
- 16.2.5 Error Detection in Deterministic Top-Down Parsers
- 16.2.6 Error Detection in Deterministic Bottom-Up Parsers
- 16.3 Recovering from Errors
- 16.4 Global Error Handling
- 16.5 Regional Error Handling
- 16.6 Local Error Handling
- 16.7 Non-Correcting Error Recovery
- 16.8 Ad Hoc Methods
- 16.9 Conclusion
- 17. Practical Parser Writing and Usage
- 18. Annotated Bibliography
- A. Hints and Solutions to Selected Problems
- Author Index
- Subject Index