Analysis of Tomita’s Algorithm for General Context-Free Parsing

James R. Kipps


Abstract
A variation on Tomita’s algorithm is analyzed in regards to its time and space complexity. It is shown to have a general time bound of 0(n ̃𝜌+1), where n is the length of the input string and 𝜌 is the length of the longest production. A modified algorithm is presented in which the time bound is reduced to 0(n3). The space complexity of Tomita’s algorithm is shown to be proportional to n2 in the worst case and is changed by at most a constant factor with the modification. Empirical results are used to illustrate the trade off between time and space on a simple example. A discussion of two subclasses of context-free grammars that can be recognized in 0(n2) and O(n) is also included.
Anthology ID:
W89-0220
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:
193–202
Language:
URL:
https://aclanthology.org/W89-0220
DOI:
Bibkey:
Cite (ACL):
James R. Kipps. 1989. Analysis of Tomita’s Algorithm for General Context-Free Parsing. In Proceedings of the First International Workshop on Parsing Technologies, pages 193–202, Pittsburgh, Pennsylvania, USA. Carnegy Mellon University.
Cite (Informal):
Analysis of Tomita’s Algorithm for General Context-Free Parsing (Kipps, IWPT 1989)
Copy Citation:
PDF:
https://aclanthology.org/W89-0220.pdf