In Marcus (1980), deterministic parsers were introduced. We make no ar­ guments about the linguistic issues D-theory parsers are meant to address, their relation to other parsing formalisms or the notion of determinism in general.

1 Parsing Technologies, and Why We Need Them.- 1.1 Parsing Technologies.- 1.2 About this book.- 2 Fully Incremental Parsing.- 2.1 Introduction.- 2.2 The Change-Update Loop.- 2.3 Reparsing.- 2.4 The Affected and Regenerated Sets.- 2.5 The Disturbance Set.- 2.6 Primitive Changes.- 2.7 Formal Properties.- 2.8 Implementation.- 2.9 Conclusions.- 3 Increasing the Applicability of LR Parsing.- 3.1 Introduction.- 3.2 Hidden left recursion and LR parsing.- 3.3 Correctness of ?-LR parsing.- 3.4 Calculation of items.- 3.5 Memory requirements.- 3.6 Conclusions.- 4 Towards a Formal Understanding of the Determinism Hypothesis in D-Theory.- 4.1 Introduction.- 4.2 D-Theory and the Determinism Hypothesis.- 4.3 Formalization.- 4.4 Consequences for the D-Theory Parsers.- 4.5 Conclusion.- 5 Varieties of Heuristics in Sentence Parsing.- 5.1 Kinds of grammar and their characteristics.- 5.2 Varieties of heuristic components in parsing sentences.- 5.3 Staged design for parsing sentences.- 5.4 Conclusion.- 6 Parsing as Dynamic Interpretation of Feature Structures.- 6.1 Introduction: the status of feature structures.- 6.2 Feature structures as formal-language expressions.- 6.3 Feature structures in the GEL language.- 6.4 Parsing as model-theoretic interpretation.- 6.5 Conclusions and future work.- 7 Proof Theory for HPSG Parsing.- 7.1 Introduction.- 7.2 An Overview of HPSG.- 7.3 Binary-branching HPSG.- 7.4 Deduction for HPSG.- 7.5 Implementation.- 7.6 Lexical entries.- 7.7 Performance.- 7.8 Conclusions.- 8 Efficient Parsing of Compiled Typed Attribute-Value Logic Grammars.- 8.1 Compiling Type Definitions.- 8.2 Compiling Basic Operations.- 8.3 Compiling Descriptions.- 8.4 Compiling Grammars and Programs.- 8.5 Extensional Types.- 8.6 Inequations.- 8.7 Type Constraints.- 8.8 Conclusion.- 9Predictive Head-Corner Chart Parsing.- 9.1 Introduction.- 9.2 Chart parsing.- 9.3 Left-corner chart parsing.- 9.4 Head-Corner chart parsing.- 9.5 Complexity analysis and further optimizations.- 9.6 Extension with feature structures.- 9.7 Related approaches.- 9.8 Conclusions.- 10 GLR* — An Efficient Noise-Skipping Parsing Algorithm for Context-Free Grammars.- 10.1 Introduction.- 10.2 The GLR* Parsing Algorithm.- 10.3 The Beam Search Heuristic.- 10.4 Parsing of Spontaneous Speech Using GLR*.- 10.5 Conclusions and Future Research Directions.- 11 Evaluation of the Tagged Text Parser, A Preliminary Report.- 11.1 Overview.- 11.2 Introduction to Tagged Text Parser.- 11.3 The TTP Time-out Mechanism.- 11.4 Parser Evaluation with Parseval.- 11.5 Evaluation of TTP.- 11.6 Conclusions.- 12 Learning to Parse with Transformations.- 12.1 Introduction.- 12.2 Transformation-based, Error-driven Learning.- 12.3 Learning Phrase Structure.- 12.4 Results.- 12.5 Sample Output.- 12.6 Assigning Nonterminal Labels.- 12.7 Conclusions.- 13 Estimation of Verb Subcategorization Frame Frequencies based on Syntactic and Multidimensional Statistical Analysis.- 13.1 Introduction.- 13.2 Method.- 13.3 Experiment on Wall Street Journal Corpus.- 13.4 Statistical Analysis.- 13.5 Conclusion and Future Direction.- 14 Monte Carlo Parsing.- 14.1 Introduction.- 14.2 The Data-Oriented Parsing Framework.- 14.3 DOP as a Stochastic Tree-Substitution Grammar.- 14.4 Parsing and Disambiguation in DOP.- 14.5 Experiments with DOP.- 14.6 Conclusions.- 15 Stochastic Lexicalized Tree-Insertion Grammar.- 15.1 Motivation.- 15.2 LTIG.- 15.3 Stochastic LTIG.- 15.4 Parsing SLTIG.- 15.5 Training an SLTIG.- 15.6 Conclusion.- 16 The Interplay of Syntactic and Semantic Node Labels in Parsing.- 16.1 State of the Art Demands.- 16.2Partial Parsing.- 16.3 Semantic Grammars.- 16.4 Parsing to Objects.- 16.5 Defining Parsing Rules Schematically.- 16.6 A Parsing Example.- 16.7 Form Rules.- 16.8 Concluding Remarks.- 17 Integration of Morphological and Syntactic Analysis based on GLR Parsing.- 17.1 Introduction.- 17.2 Morphological Analysis of Japanese.- 17.3 Generating An LR Table.- 17.4 Algorithm.- 17.5 A worked example.- 17.6 Conclusion.- 18 Structural Disambiguation in Japanese by Case Structure Evaluation based on Examples in a Case Frame Dictionary.- 18.1 Introduction.- 18.2 Selecting a Proper Case Frame.- 18.3 Structural Disambiguation using Case Structure Score.- 18.4 Experiment.- 18.5 Conclusions.- 19 Flowgraph Parsing.- 19.1 Introduction and Motivation.- 19.2 Notation and Definitions.- 19.3 Chart Parsing of Context-free Flowgraphs.- 19.4 Complexity Analysis.- 19.5 Dealing With Attributes.- 19.6 Dealing With Tie-Point Relationships.- 19.7 Chart Parsing of Structure-Sharing Flowgraphs.- 19.8 Conclusions.- 20 Predictive Parsing for Unordered Relational Languages.- 20.1 Introduction.- 20.2 Atomic Relational Grammars.- 20.3 Parsing Preliminaries.- 20.4 Preliminaries to a Parser.- 20.5 Earley-style Recognition for ARGs.- 20.6 Parse trace.- 20.7 Conclusion.