Skip to content

Research at St Andrews

Hybrid grammars for parsing of discontinuous phrase structures and non-projective dependency structures

Research output: Research - peer-reviewArticle


Open Access permissions



Kilian Gebhardt, Mark Jan Nederhof, Heiko Vogler

School/Research organisations


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.


Original languageEnglish
Pages (from-to)465-520
JournalComputational Linguistics
Issue number3
Early online date15 Sep 2017
StatePublished - Sep 2017

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. A probabilistic model of Ancient Egyptian writing

    Nederhof, M. J. & Rahman, F. 2017 In : Journal of Language Modelling. 5, 1, p. 131-163

    Research output: Research - peer-reviewArticle

  2. A derivational model of discontinuous parsing

    Nederhof, M. J. & Yli-Jyra, A. 2017 Language and Automata Theory and Applications: 11th International Conference, LATA 2017, Umeå, Sweden, March 6-9, 2017, Proceedings. Drewes, F., Martin-Vide, C. & Truthe, B. (eds.). Cham: Springer, p. 299-310 (Lecture Notes in Computer Science (Theoretical Computer Science and General Issues); vol. 10168)

    Research output: ResearchConference contribution

  3. Transition-based dependency parsing as latent-variable constituent parsing

    Nederhof, M. J. 12 Aug 2016 Proceedings of the SIGFSM Workshop on Statistical NLP and Weighted Automata. Berlin: Association for Computational Linguistics, 11 p.

    Research output: ResearchConference contribution

  4. A short proof that O2 is an MCFL

    Nederhof, M. J. 7 Aug 2016 54th Annual meeting of the Association for Computational Linguistics: Proceedings of the Conference. Berlin: Association for Computational Linguistics, 10 p.

    Research output: ResearchConference contribution

  5. Non-self-embedding linear context-free tree grammars generate regular tree languages

    Nederhof, M. J., Teichmann, M. & Vogler, H. 2016 In : Journal of Automata Languages Combinatorics. 21, 3, p. 203-246

    Research output: Research - peer-reviewArticle

Related by journal

  1. Splittability of bilexical context-free grammars is undecidable

    Nederhof, M. J. & Satta, G. Dec 2011 In : Computational Linguistics. 37, 4, p. 867-879 13 p.

    Research output: Research - peer-reviewArticle

  2. A general technique to train language models on language models

    Nederhof, M. J. Jun 2005 In : Computational Linguistics. 31, 2, p. 173-185 13 p.

    Research output: Research - peer-reviewArticle

ID: 249016829