A Variant of Earley Parsing
| dc.creator | Nederhof, Mark-Jan | |
| dc.creator | Satta, Giorgio | |
| dc.date | 1998-08-31 | |
| dc.date.accessioned | 2026-07-07T02:36:22Z | |
| dc.date.available | 2026-07-07T02:36:22Z | |
| dc.description | 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. | |
| dc.description | 12 pages, 1 Postscript figure, uses psfig.tex and llncs.sty | |
| dc.identifier | https://arxiv.org/abs/cmp-lg/9808017 | |
| dc.identifier | http://arxiv.org/abs/cmp-lg/9808017 | |
| dc.identifier | AI*IA 97: Advances in Artificial Intelligence, 5th Congress of the Italian Association for Artificial Intelligence, LNAI 1321, Springer Verlag, pages 84-95, 1997. | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/15892 | |
| dc.subject | Computation and Language | |
| dc.title | A Variant of Earley Parsing | |
| dc.type | text |