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
Editor:
Masaru Tomita
Venue:
IWPT
SIG:
SIGPARSE
Publisher:
Carnegy Mellon University
Note:
Pages:
286–296
Language:
URL:
https://aclanthology.org/W89-0230
DOI:
Bibkey:
Cite (ACL):
Nariyoshi Yamai, Tadashi Seko, Noboru Kubo, and Toru Kawata. 1989. An Effective Enumeration Algorithm of Parses for Ambiguous CFL. In Proceedings of the First International Workshop on Parsing Technologies, pages 286–296, Pittsburgh, Pennsylvania, USA. Carnegy Mellon University.
Cite (Informal):
An Effective Enumeration Algorithm of Parses for Ambiguous CFL (Yamai et al., IWPT 1989)
Copy Citation:
PDF:
https://aclanthology.org/W89-0230.pdf