The book presents a wide range of recent research results about parsing schemata, introducing formal frameworks and theoretical results while keeping a constant focus on applicability to practical parsing problems. The first part includes a general...
mehr
The book presents a wide range of recent research results about parsing schemata, introducing formal frameworks and theoretical results while keeping a constant focus on applicability to practical parsing problems. The first part includes a general introduction to the parsing schemata formalism that contains the basic notions needed to understand the rest of the parts. Thus, this compendium can be used as an introduction to natural language parsing, allowing postgraduate students not only to get a solid grasp of the fundamental concepts underlying parsing algorithms, but also an understanding of the latest developments and challenges in the field. Researchers in computational linguistics will find novel results where parsing schemata are applied to current problems that are being actively researched in the computational linguistics community (like dependency parsing, robust parsing, or the treatment of non-projective linguistics phenomena). This book not only explains these results in a more detailed, comprehensive and self-contained way, and highlights the relations between them, but also includes new contributions that have not been presented. Intro -- Contents -- Preface -- List of Figures -- Introduction and Preliminaries -- 1. Introduction -- 1.1 Motivation -- 1.2 Background -- 1.2.1 Parsing natural language -- 1.2.2 Robustness in grammar-driven parsers -- 1.2.3 Parsing schemata -- 1.3 Outline of the book -- 1.3.1 Contributions -- 1.3.2 Structure of the book -- 1.3.2.1 Part 1 -- 1.3.2.2 Part 2 -- 1.3.2.3 Part 3 -- 1.3.2.4 Part 4 -- 1.3.2.5 Part 5 -- 2. Preliminaries -- 2.1 Context-free grammars -- 2.2 Parsing algorithms and schemata -- 2.3 The formalism of parsing schemata -- 2.3.1 Deduction systems -- 2.3.2 Parsing systems and parsing schemata -- 2.3.3 Correctness of parsing schemata -- 2.3.4 Relations between parsing schemata -- 2.4 Advantages of parsing schemata -- Compiling and Executing Parsing Schemata -- 3. A compiler for parsing schemata -- 3.1 Motivation and goals -- 3.1.1 Design goals -- 3.1.2 Related work -- 3.2 System architecture -- 3.3 Generated code -- 3.4 Reading schemata -- 3.5 The code generation process -- 3.5.1 Element types -- 3.5.2 Deduction step classes -- 3.5.3 Deduction step code generation -- 3.5.4 Search specifications -- 3.6 Indexing -- 3.6.1 Static analysis and index descriptors -- 3.6.2 Generation of indexing code -- 3.6.3 Deduction step indexing -- 3.7 Discussion -- 4. Practical complexity of constituency parsers -- 4.1 Parsing natural language with CFGs -- 4.2 Parsing with TAGs -- 4.2.1 Tree-adjoining grammars -- 4.2.2 Substitution and adjunction -- 4.2.3 Properties of TAG -- 4.3 Parsing schemata for TAG -- 4.4 Parsing schemata for the XTAG English grammar -- 4.4.1 Grammar conversion -- 4.4.2 Feature structure unification -- 4.4.3 Tree filtering -- 4.4.3.1 Example -- 4.5 Comparing several parsers for the XTAG grammar -- 4.6 Parsing with artificially-generated TAGs -- 4.7 Overhead of TAG parsing over CFG parsing -- 4.8 Discussion.