A Variant of Earley Parsing
<|reference_start|>A Variant of Earley Parsing: The Earley algorithm is a widely used parsing method in natural language processing applications. We introduce a variant of Earley parsing that is based on a ``delayed'' recognition of constituents. This allows us to start the recognition of a constituent only in cases in which all of its subconstituents have been found within the input string. This is particularly advantageous in several cases in which partial analysis of a constituent cannot be completed and in general in all cases of productions sharing some suffix of their right-hand sides (even for different left-hand side nonterminals). Although the two algorithms result in the same asymptotic time and space complexity, from a practical perspective our algorithm improves the time and space requirements of the original method, as shown by reported experimental results.<|reference_end|>
@article{nederhof1998a,
    title={A Variant of Earley Parsing},
    author={Mark-Jan Nederhof (University of Groningen) and Giorgio Satta
  (Universita di Padova)},
    journal={AI*IA 97: Advances in Artificial Intelligence, 5th Congress of the
  Italian Association for Artificial Intelligence, LNAI 1321, Springer Verlag,
  pages 84-95, 1997.},
    year={1998},
    archivePrefix={arXiv},
    eprint={cmp-lg/9808017},
    primaryClass={cmp-lg cs.CL}
}