Hybrid Grammars for Parsing of Discontinuous Phrase Structures and Non-Projective Dependency Structures
Open Access
- 1 September 2017
- journal article
- Published by MIT Press in Computational Linguistics
- Vol. 43 (3) , 465-520
Abstract
We explore the concept of hybrid grammars, which formalize and generalize a range of existing frameworks for dealing with discontinuous syntactic structures. Covered are both discontinuous phrase structures and non-projective dependency structures. Technically, hybrid grammars are related to synchronous grammars, where one grammar component generates linear structures and another generates hierarchical structures. By coupling lexical elements of both components together, discontinuous structures result. Several types of hybrid grammars are characterized. We also discuss grammar induction from treebanks. The main advantage over existing frameworks is the ability of hybrid grammars to separate discontinuity of the desired structures from time complexity of parsing. This permits exploration of a large variety of parsing algorithms for discontinuous structures, with different properties. This is confirmed by the reported experimental results, which show a wide variety of running time, accuracy, and frequency of parse failures.Keywords
This publication has 62 references indexed in Scilit:
- On the Generative Power of Multiple Context-Free Grammars and Macro GrammarsIEICE Transactions on Information and Systems, 2008
- CCGbank: A Corpus of CCG Derivations and Dependency Structures Extracted from the Penn TreebankComputational Linguistics, 2007
- The Equivalence of Bottom-Up and Top-Down Tree-to-Graph TransducersJournal of Computer and System Sciences, 1998
- Attribute grammar paradigms—a high-level methodology in language implementationACM Computing Surveys, 1995
- On multiple context-free grammarsTheoretical Computer Science, 1991
- Relating logic programs and attribute grammarsThe Journal of Logic Programming, 1985
- Cross-Serial Dependencies in Dutch1982
- IO and OI. IJournal of Computer and System Sciences, 1977
- Semantic evaluation from left to rightCommunications of the ACM, 1976
- Mappings and grammars on treesTheory of Computing Systems, 1970