Natural Language Parsing Systems

Robust Parsing Using Multiple Construction-Specific Strategies.- 1 Introduction.- 2 Construction-Specific Flexible Parsing.- 2.1 Problems with a Rigid Uniform Grammar.- 2.2 The Need for Case Constructions.- 3 The Representation of Ambiguity and Focused Interaction.- 3.1 Focused Error Recovery.- 3.2 Representing Case-Filler Ambiguity.- 3.3 Representing Structural Ambiguity.- 4 Limited-Domain Language Definition.- 4.1 Compiling Descriptions into Linear Patterns.- 4.2 Direct Interpretation of Case Descriptions.- 5 Parsing Data Base Queries and Updates.- 5.1 The Non-Uniformity Problem.- 5.2 Unifying Update and Query Representations.- 5.3 Benefits of the Construction-Specific Approach.- 6 The CASPAR Parser.- 6.1 The Two CASPAR Strategies.- 6.2 Error-Tolerant Parsing.- 6.3 The CASPAR Algorithm.- 7 The DYPAR Parser.- 7.1 The Objectives of the DYPAR Approach.- 7.2 Parsing Strategies in DYPAR.- 7.3 A Sample DYPAR Dialogue.- 8 Combining the Strengths of CASPAR and DYPAR.- 8.1 A Multi-Strategy Algorithm.- 8.2 Flexible Error-Recovery Mechanisms.- 8.3 Advantages of the Multi-Strategy Approach.- 8.4 A Review of Principal Parsing Strategies.- 9 Conclusion.- References.- Parsing with Logical Variables.- 1 Introduction.- 2 Definite Clause Grammars.- 2.1 The DCG Notation.- 2.2 Interpreting DCG Rules as Definite Clauses.- 2.3 An Example in More Detail.- 3 Comparing DC and ATN Grammars.- 4 Replacing ATN Registers with ATN Variables.- 5 Conclusions.- References.- Knowledge-Based Parsing.- 1 Introduction.- 1.1 Overview.- 1.2 Fundamental Assumptions.- 1.3 Declarative Knowledge Representation in an Integrated Knowledge Base.- 1.4 System Overview.- 1.5 Knowledge Representation Techniques.- 1.6 Core Knowledge and the Kernel Language.- 1.7 Metalanguage Conventions and Symbols.- 2 Core Knowledge and Representations.- 2.1 Uniform Representation and Intensional Constructs.- 2.2 Predefined Categories, Objects, Relations, Functions.- 2.2.1 Predefined Categories.- 2.2.2 Predefined Objects.- 2.2.3 Predefined Relations.- 2.2.4 Predefined Functions.- 2.3 The Reading Function.- 2.4 The Representational Mapping.- 2.4.1 Introduction.- 2.4.2 Base Cases.- 2.4.3 Propositions and Structured Objects.- 2.4.4 Participants in Propositions or Relations; Components of Structured Objects.- 2.5 Kernel Language.- 2.5.1 Predefined Terms.- 2.5.2 Syntactic Rewrite Rules.- 2.5.3 Semantic Rewrite Rules.- 2.6 Use in Language Processing.- 3 Increasing the System's Language Capability Through Its Language Capability.- 3.1 Motivation.- 3.2 Defining More-General Rule Forms.- 3.3 Parsing Strategy.- 3.4 Interpretation of the Input Rule Statement.- 4 Language Use-Mention Distinction.- 5 Summary.- Appendix: Chronological Summary of Input to the System as Presented in This Chapter.- References.- Using Declarative Knowledge for Understanding Natural Language.- 1 Introduction.- 2 The Knowledge.- 2.1 Lexicographic Knowledge.- 2.1.1 The Words.- 2.1.2 The Ending Sequences.- 2.1.3 The Conjugations.- 2.2 Syntactic Knowledge.- 2.2.1 Syntactic Markers.- 2.2.2 Graphs.- 2.2.3 The "Traits".- 2.2.4 The Agreement Rules.- 2.2.5 The Conjunctions.- 2.2.6 Comparison Between This Formalism and ATN Grammars.- 2.3 The Semantic Knowledge.- 2.3.1 The Pattern Part of a Meaning.- 2.3.2 The Action Part of a Meaning.- 2.3.3 Meaning of the Symbols Which Are Not Words.- 2.4 Pragmatic Knowledge.- 3 The Interpreter.- 3.1 An Interpreter for Lexicographic Knowledge.- 3.2 The Main Interpreter.- 3.2.1 Building the Structure.- 3.2.2 Using the Graphs Representing the Conjunctions.- 3.2.3 Achieving the Building of the Structure.- 3.2.4 Pruning the Structure.- 3.3 The Interpreter of Pragmatic Knowledge.- 3.4 The Implementation.- 4 Discussion.- 5 Conclusion.- References.- Weighted Parsing.- 1 The Need for Weighting.- 2 A Digression: Regulation Processes.- 3 Aspects of System Control.- 4 Types of Weighting.- 4.1 Endogenous Weighting.- 4.2 Exogenous Weighting.- 4.2.1 Absolute Exogenous Weighting.- 4.2.2 Relative Exogenous Weighting.- 5 The Application of Weighting in an MT-System.- 6 Examples of the Application of Weighting.- 6.1 Weights in the Control Structure.- 6.1.1 Production Systems.- 6.2 Weights in Linguistic Structures.- 6.3 Learning Systems.- 7 Computation of Weights.- 7.1 Weights and Sublanguage.- 7.2 Weights and Partial Parsers.- 8 Evaluation of Weights.- References.- A Distributed Word-Based Approach to Parsing.- 1 Introduction.- 2 Background Motivations.- 2.1 Linguistics.- 2.2 Psychology.- 2.3 Computer Science.- 3 The Parsing System.- 3.1 Model Organization.- 3.2 Control Mechanisms: Expert Suspension and Resumption.- 3.2.1 Restart Demons.- 3.2.2 Timeouts.- 3.3 Message and Memory Objects: Expert Interaction Data.- 3.3.1 Control Signals.- 3.3.2 Concept Structures.- 3.3.3 Signal and Concept Filters.- 3.4 Word Expert Structure.- 4 Example: "The man throws in the towel".- 5 Word Expert Definition.- 5.1 Overview of Expert Functions.- 5.2 Lexical Interaction Language.- 5.2.1 AWAIT.- 5.2.2 PEEKW and READW.- 5.2.3 SEND.- 5.3 Sense Discrimination Language.- 5.3.1 Syntax and Control Signals.- 5.3.2 Semantics and Concept Structures.- 5.3.3 Questions About Incoming Messages.- 5.3.4 Control Flow.- 5.4 Memory Interaction.- 5.4.1 Interaction Requirements.- 5.4.2 VIEW.- 5.4.3 BINDC.- 6 Summary and Conclusions.- References.- Parsing by Means of Uppsala Chart Processor (UCP).- 1 Introduction.- 2 Background.- 2.1 General Syntactic Processor.- 2.2 The Development of the Chart.- 2.2.1 The Chart and Morphographemic Rewriting.- 2.2.2 The Chart and Dictionary Search.- 2.2.3 The Chart and Syntactic Analysis.- 2.3 The Active Chart.- 3 Uppsala Chart Processor.- 3.1 The Format of the Grammatical Descriptions.- 3.2 Dictionary Search.- 3.2.1 Influencing the Dictionary Search Process.- 3.3 Morphological Analysis.- 3.3.1 Predictive Segmentation into Tentative Morphs.- 3.3.2 The Application of Morphotactic Rules.- 3.3.3 Derivational Analysis.- 3.4 Syntactic Analysis.- 3.4.1 The Analysis of a Clause.- 3.4.2 The Infinitive Clause.- 3.4.3 Coordinated Expressions.- 3.4.4 Rule-Driven and Data-Driven Processing.- 3.5 A Summary of the UCP Formalism.- 3.5.1 The Linguistic Operators.- 3.6 Implementation.- 4 Applications.- 4.1 A General Parser for Swedish.- 4.2 Medical Text Comprehension.- 4.3 A Morphological Analyzer for Automatic Keyword Indexing.- 5 Summary of Experience with UCP.- References.- Preliminary Analysis of a Breadth-First Parsing Algorithm: Theoretical and Experimental Results.- 1 An Introduction to Chart Parsing.- 1.1 Enumeration Order.- 1.1.1 Depth-First vs. Breadth-First.- 1.1.2 Top-Down vs. Bottom-Up.- 1.2 N-ary Branching.- 1.3 Dotted-Grammars and ATN States.- 1.4 Example with Dotted-Rules.- 2 Taking Advantage of Restricted Grammars.- 2.1 Time n2 Grammars.- 2.1.1 Grammar 'aAa': an Example of Bounded Direct Ambiguity.- 2.2 'Grammar AA': an Example of Unbounded Direct Ambiguity.- 2.3 Examples from Psycholinguistic Literature.- 2.3.1 Noun-Noun Modification.- 2.3.2 Prepositional Phrase Attachment and Conjunction.- 2.3.3 Reduced Relative Clauses.- 2.4 Taking Advantage of Bounded Direct Ambiguity.- 2.5 Time n Grammars.- 2.5.1 Taking Advantage of Useless Phrases.- 2.6 Representation Issues.- 2.6.1 Diagonal Entries.- 2.7 Compilation vs. Interpretation.- 3 Transformations and Lexical Rules.- 3.1 Features.- 3.1.1 Overriding Features in Exceptional Cases.- 3.1.2 Representation of Features.- 3.1.3 The Features in EQSP.- 3.1.4 Transformational Context.- 3.1.5 Adjunct Contexts.- 3.2 NP-Movement.- 3.3 Wh-Movement.- 3.3.1 Gazdar's Formulation of Wh-Movement.- 3.3.2 Wh-Movement in EQSP.- 3.3.3 Adjacent Filler-Gaps: a Special Case.- 3.3.4 Complement Clauses, Relative Clauses, and Questions.- 3.4 Conjunction.- 3.4.1 The General Mechanism.- 3.4.2 Idiosyncratic Cases.- 3.4.3 Conjunction and the Size of the Grammar.- 4 Experimental Results.- 4.1 A Comparison of the LADDER and MALHOTRA Corpuses.- 4.2 Synthetic Sentences.- 4.2.1 Catalan Numbers.- 4.2.2 Fibonacci Numbers.- 4.2.3 Worst Case for Number of Parses.- 4.3 Analysis of CPU Time.- 5 Conclusion.- Appendix I Results with the MALHOTRA Corpus.- Appendix II Results with the LADDER-TODS Collection.- References.- Syntax Directed Translation in the Natural Language Information System PLIDIS.- 1 Some Notation and Basic Definitions.- 1.1 Notation.- 1.2 Trees.- 2 Tree Directed Grammars.- 2.1 Structural Constraints.- 2.2 Tree Directed Grammars.- 3 Tree Transducers.- 3.1 Top-Down Tree Transducers.- 3.2 Some Extensions of yT-Transducers.- 4 Tree Directed Grammars and Tree Transducers.- 4.1 Downward Oriented Tree Directed Grammars.- 4.2 Loop-Free and Linear Restricted TDGs.- References.