Abstract
A substring recognizer for a language L determines whether a string s is a substring of a sentence in L, i.e., substring-recognize(s) succeeds if and only if ∃ v,w: vsw ∈ L. The algorithm for substring recognition presented here accepts general context-free grammars and uses the same parse tables as the parsing algorithm from which it was derived. Substring recognition is useful for non-correcting syntax error recovery and for incremental parsing. By extending the substring recognizer with the ability to generate trees for the possible contextual completions of the substring, we obtain a substring parser, which can be used in a syntax-directed editor to complete fragments of sentences.- Anthology ID:
- 1991.iwpt-1.25
- 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:
- 218–224
- Language:
- URL:
- https://aclanthology.org/1991.iwpt-1.25
- DOI:
- Cite (ACL):
- Jan Rekers and Wilco Koorn. 1991. Substring Parsing for Arbitrary Context-Free Grammars. In Proceedings of the Second International Workshop on Parsing Technologies, pages 218–224, Cancun, Mexico. Association for Computational Linguistics.
- Cite (Informal):
- Substring Parsing for Arbitrary Context-Free Grammars (Rekers & Koorn, IWPT 1991)
- PDF:
- https://preview.aclanthology.org/revert-3132-ingestion-checklist/1991.iwpt-1.25.pdf