An Effective Enumeration Algorithm of Parses for Ambiguous CFL

Nariyoshi Yamai, Tadashi Seko, Noboru Kubo, Toru Kawata


Abstract
An efficient algorithm that enumerates parses of ambiguous context-free languages is described, and its time and space complexities are discussed. When context-free parsers are used for natural language parsing, pattern recognition, and so forth, there may be a great number of parses for a sentence. One common strategy for efficient enumeration of parses is to assign an appropriate weight to each production, and to enumerate parses in the order of the total weight of all applied production. However, the existing algorithms taking this strategy can be applied only to the problems of limited areas such as regular languages; in the other areas only inefficient exhaustive searches are known. In this paper, we first introduce a hierarchical graph suitable for enumeration. Using this graph, enumeration of parses in the order of acceptablity is equivalent to finding paths of this graph in the order of length. Then, we present an efficient enumeration algorithm with this graph, which can be applied to arbitrary context-free grammars. For enumeration of k parses in the order of the total weight of all applied productions, the time and space complexities of our algorithm are 0(n3 + kn2) and 0(n3 + kn), respectively.
Anthology ID:
W89-0230
Volume:
Proceedings of the First International Workshop on Parsing Technologies
Month:
August
Year:
1989
Address:
Pittsburgh, Pennsylvania, USA
Venues:
IWPT | WS
SIG:
SIGPARSE
Publisher:
Carnegy Mellon University
Note:
Pages:
286–296
Language:
URL:
https://www.aclweb.org/anthology/W89-0230
DOI:
Bib Export formats:
BibTeX MODS XML EndNote
PDF:
http://aclanthology.lst.uni-saarland.de/W89-0230.pdf