Paper: An Optimal Tabular Parsing Algorithm

ACL ID P94-1017
Title An Optimal Tabular Parsing Algorithm
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1994

In this paper we relate a number of parsing algorithms which have been developed in very different areas of parsing theory, and which include deterministic algo- rithms, tabular algorithms, and a parallel algorithm. We show that these algorithms are based on the same underlying ideas. By relating existing ideas, we hope to provide an op- portunity to improve some algorithms based on features of others. A second purpose of this paper is to answer a question which has come up in the area of tabular pars- ing, namely how to obtain a parsing algorithm with the property that the table will contain as little entries as possible, but without the possibility that two entries represent the same subderivation.