Parsing Techniques A Practical Guide
User Manual:
Open the PDF directly: View PDF
Page Count: 669 [warning: Documents this large are best viewed by clicking the View PDF Link!]
- Preface
- Contents
- Introduction
- Grammars as Generating Device
- Languages as Infinite Sets
- Formal Grammars
- Chomsky Hierarchy of Grammars & Languages
- Actually generating Sentences from Grammar
- To shrink or not to shrink
- Grammars that produce the Empty Language
- Limitations of CF & FS Grammars
- CF & FS Grammars as Transition Graphs
- Hygiene in Context-free Grammars
- Set Properties of Context-free & Regular Languages
- Semantic Connection
- Metaphorical Comparison of Grammar Types
- Conclusion
- Problems
- Intro to Parsing
- Parse Tree
- 2 Ways to parse Sentence
- Non-Deterministic Automata
- Recognition & Parsing for Type 0 to Type 4 Grammars
- Overview of Context-free Parsing Methods
- "Strength" of Parsing Technique
- Representations of Parse Trees
- When are we done Parsing?
- Transitive Closure
- Relation btw Parsing & Boolean Matrix Multiplication
- Conclusion
- Problems
- General Non-Directional Parsing
- Unger Parsing Method
- CYK Parsing Method
- CYK Recognition with General CF Grammars
- CYK Recognition with Grammar in Chomsky Normal Form
- Transforming CF Grammar into Chomsky Normal Form
- Eliminating ε-Rules
- Eliminating Unit Rules
- Cleaning up the Grammar
- Finally, to Chomsky Normal Form
- The Example revisited
- CYK Parsing with Chomsky Normal Form
- Undoing the Effect of CNF Transformation
- Short Retrospective of CYK
- Getting Parse-Forest Grammars from CYK Parsing
- Tabular Parsing
- Conclusion
- Problems
- Regular Grammars & FSA
- General Directional Top-Down Parsing
- General Directional Bottom-Up Parsing
- Parsing by Searching
- Earley Parser
- Basic Earley Parser
- Scanner, Completer & Predictor
- Constructing Parse Tree
- Space & Time Requirements
- Relation btw Earley & CYK Algorithms
- Handling ε-Rules
- Completer/Predictor Loop
- Modifying the Predictor
- Determining Nullability
- Exploiting Look-ahead
- Prediction Look-ahead
- Reduction Look-ahead
- Discussion
- Left & Right Recursion
- Chart Parsing
- Conclusion
- Problems
- Deterministic Top-Down Parsing
- Deterministic Bottom-Up Parsing
- Simple Handle-finding Techniques
- Precedence Parsing
- Bounded-Right-Context Parsing
- LR Methods
- LR(0)
- LR(1)
- LALR(1)
- SLR(1)
- Conflict Resolvers
- Further Developments of LR Methods
- Parse Tree Grammar from LR
- Left & Right Contexts of Parsing Decisions
- Exploiting Left & Right Contexts
- LR(k) as Ambiguity Test
- Conclusion
- Problems
- Non-Canonical Parsers
- Generalized Deterministic Parsers
- Substring Parsing
- Parsing as Intersection
- Parallel Parsing
- Non-Chomsky Grammars & Parsers
- Error Handling
- Practical Parser Writing & Usage
- Biblio
- Hints & Solutions
- Index