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:
- 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)
- PDF:
- https://preview.aclanthology.org/emnlp-22-attachments/W89-0220.pdf