Prof. Dr. Walt Detmar Meurers
Improving the Efficiency of Parsing with Discontinuous Constituents


Mike Daniels and Walt Detmar Meurers


Proceedings of NLULP'02.


We discuss a generalization of Earley's algorithm to grammars licensing discontinuous constituents of the kind proposed by the so-called linearization approaches in Head-Driven Phrase Structure Grammar. We show how to replace the standard indexing on the string position by bitmasks that act as constraints over possible coverage bitvectors. This improves efficiency of edge access and reduces the number of edges by constraining prediction to those grammar rules which are compatible with known word order properties. The resulting parsing algorithm does not have to process the righthand side categories in the order in which they cover the string, and so a head-driven strategy can be obtained simply by reordering the righthand side categories of the rules. The resulting strategy generalizes head-driven parsing in that it also permits the ordering of non-head categories.



Electronically available file formats:

  • .ps (405.628 bytes)
  • .ps.gz (187.713 bytes)
  • .pdf (188.887 bytes)



Bibtex entry:

    author =       {Mike Daniels and W. Detmar Meurers},
    title =        {Improving the Efficiency of Parsing with Discontinuous
    editor =       {Shuly Wintner},
    booktitle =    {Proceedings of NLULP'02: The 7th International Workshop 
    on Natural Language Understanding and Logic Programming},
    publisher =    {Roskilde Universitetscenter}
    address =      {Copenhagen},
    series =       {Datalogiske Skrifter},
    number =       92,
    url =          {},
    pages =        {49--68},
    year =         2002