Processing...
An Optimal Tabular Parsing Algorithm
1994-05-26
9405025 | cmp-lg
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 algorithms, 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 opportunity 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 parsing, 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.