Abstract
The valid prefix property (VPP), the capability of a left to right parser to detect errors as soon as possible, often goes unnoticed in parsing CFGs. Earley’s parser for CFGs (Earley, 1968; Earley, 1970) maintains the valid prefix property and obtains an O(n3)-time worst case complexity, as good as parsers that do not maintain such as the CKY parser (Younger, 1967; Kasami, 1965). Contrary to CFGs, maintaining the valid prefix property for TAGs is costly. In 1988, Schabes and Joshi proposed an Earley-type parser for TAGs. It maintains the valid prefix property at the expense of its worst case complexity (O(n9)-time). To our knowledge, it is the only known polynomial time parser for TAGs that maintains the valid prefix property. In this paper, we explain why the valid prefix property is expensive to maintain for TAGs and we introduce a predictive left to right parser for TAGs that does not maintain the valid prefix property but that achieves an O(n6)-time worst case behavior, O(n4)-time for unambiguous grammars and linear time for a large class of grammars.- Anthology ID:
- 1991.iwpt-1.4
- Volume:
- Proceedings of the Second International Workshop on Parsing Technologies
- Month:
- February 13-25
- Year:
- 1991
- Address:
- Cancun, Mexico
- Editors:
- Masaru Tomita, Martin Kay, Robert Berwick, Eva Hajicova, Aravind Joshi, Ronald Kaplan, Makoto Nagao, Yorick Wilks
- Venue:
- IWPT
- SIG:
- SIGPARSE
- Publisher:
- Association for Computational Linguistics
- Note:
- Pages:
- 21–30
- Language:
- URL:
- https://aclanthology.org/1991.iwpt-1.4
- DOI:
- Cite (ACL):
- Yves Schabes. 1991. The Valid Prefix Property and Left to Right Parsing of Tree-Adjoining Grammar. In Proceedings of the Second International Workshop on Parsing Technologies, pages 21–30, Cancun, Mexico. Association for Computational Linguistics.
- Cite (Informal):
- The Valid Prefix Property and Left to Right Parsing of Tree-Adjoining Grammar (Schabes, IWPT 1991)
- PDF:
- https://preview.aclanthology.org/revert-3132-ingestion-checklist/1991.iwpt-1.4.pdf