Introduction / 1: |
Formal Grammars and Natural Languages / 1.1: |
Parsing Beyond CFGs / 1.2: |
What This Book Is Not About / 1.3: |
Overview of the Book / 1.4: |
Grammar Formalisms for Natural Languages / 1.4.1: |
Parsing: Preliminaries / 1.4.2: |
Tree Adjoining Grammars / 1.4.3: |
MCFG and LCFRS / 1.4.4: |
Range Concatenation Grammars / 1.4.5: |
Automata / 1.4.6: |
Some Basic Definitions / 1.5: |
Languages / 1.5.1: |
Context-Free Grammars / 1.5.2: |
Trees / 1.5.3: |
Context-Free Grammars and Natural Languages / 2: |
The Generative Capacity of CFGs / 2.1.1: |
CFGs and Lexicalization / 2.1.2: |
Mild Context-Sensitivity / 2.1.3: |
Grammar Formalisms Beyond CFG / 2.2: |
Linear Indexed Grammars / 2.2.1: |
Linear Context-Free Rewriting Systems / 2.2.3: |
Multicomponent Tree Adjoining Grammars / 2.2.4: |
Multiple Context-Free Grammars / 2.2.5: |
Summary / 2.2.6: |
Parsing as Deduction / 3: |
Motivation / 3.1.1: |
Items / 3.1.2: |
Deduction Rules / 3.1.3: |
Implementation Issues / 3.2: |
Dynamic Programming / 3.2.1: |
Chart Parsing and Tabulation / 3.2.2: |
Hypergraphs / 3.2.3: |
Properties of Parsing Algorithms / 3.3: |
Soundness and Completeness / 3.3.1: |
Complexity / 3.3.2: |
Valid Prefix Property / 3.3.3: |
Introduction to Tree Adjoining Grammars / 3.4: |
Definition of TAG / 4.1.1: |
Formal Properties / 4.1.2: |
Linguistic Principles for TAG / 4.1.3: |
Extended Domain of Locality and Factoring of Recursion / 4.1.4: |
Constituency and Dependencies / 4.1.5: |
Equivalent Formalisms / 4.2: |
Tree-Local MCTAG / 4.2.1: |
Combinatory Categorial Grammars / 4.2.2: |
Parsing Tree Adjoining Grammars / 4.3: |
A CYK Parser for TAG / 5.1: |
The Recognizer / 5.1.1: |
An Earley Parser for TAG / 5.1.2: |
Inference Rules / 5.2.1: |
Extending the Algorithm to Substitution / 5.2.4: |
The Parser / 5.2.5: |
Properties of the Algorithm / 5.2.6: |
Prefix Valid Earley Parsing / 5.2.7: |
An LR Parser for TAG / 5.3: |
Construction of the Automation / 5.3.1: |
Multiple Context-Free Grammars and Linear Context-Free Rewriting Systems / 5.3.3: |
Introduction to MCFG, LCFRS and Simple RCG / 6.1: |
Applications / 6.1.1: |
Set-Local Multicomponent TAG / 6.2: |
Minimalist Grammars / 6.2.2: |
Finite-Copying LFG / 6.2.3: |
Parsing MCFG, LCFRS and Simple RCG / 6.3: |
CYK Parsing of MCFG / 7.1: |
The Basic Algorithm / 7.1.1: |
The Naïve Algorithm / 7.1.2: |
The Active Algorithm / 7.1.3: |
The Incremental Algorithm / 7.1.4: |
Prediction Strategies / 7.1.5: |
Simplifying Simple RCGs / 7.2: |
Eliminating Useless Rules / 7.2.1: |
Eliminating ?-Rules / 7.2.2: |
Ordered Simple RCG / 7.2.3: |
Binarization of the Rules / 7.2.4: |
An Incremental Earley Parser for Simple RCG / 7.3: |
The Algorithm / 7.3.1: |
Filters / 7.3.2: |
Introduction to Range Concatenation Grammars / 7.4: |
Definition of RCG / 8.1.1: |
Relations to Other Formalisms / 8.1.2: |
Literal Movement Grammars / 8.2.1: |
CFG, TAG and MCFG / 8.2.2: |
Parsing Range Concatenation Grammars / 8.3: |
Basic RCG Parsing / 9.1: |
CYK Parsing with Passive Items / 9.1.1: |
Non-directional Top-Down Parsing / 9.1.2: |
Directional Top-Down Parsing / 9.1.3: |
Optimizations / 9.1.4: |
Parsing with Constraint Propagation / 9.2: |
Range Constraints / 9.2.1: |
CYK Parsing with Active Items / 9.2.2: |
Earley Parsing / 9.2.3: |
Embedded Push-Down Automata / 9.3: |
Definition of EPDA / 10.1.1: |
EPDA and TAG / 10.1.2: |
Bottom-Up Embedded Push-Down Automata / 10.1.3: |
?-Order EPDA / 10.1.4: |
Two-Stack Automata / 10.2: |
General Definition / 10.2.1: |
Strongly-Driven Two-Stack Automata / 10.2.2: |
Thread Automata / 10.3: |
Idea / 10.3.1: |
General Definition of TA / 10.3.2: |
Constructing a TA for a TAG / 10.3.3: |
Constructing a TA for an Ordered SRCG / 10.3.4: |
Hierarchy of Grammar Formalisms / 10.4: |
List of Acronyms / Appendix B: |
Solutions |
References |
Index |
Introduction / 1: |
Formal Grammars and Natural Languages / 1.1: |
Parsing Beyond CFGs / 1.2: |