Substring Parsing for Arbitrary Context-Free Grammars

Jan Rekers, Wilco Koorn


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
Venues:
IWPT | WS
SIG:
SIGPARSE
Publisher:
Association for Computational Linguistics
Note:
Pages:
218–224
Language:
URL:
https://aclanthology.org/1991.iwpt-1.25
DOI:
Bibkey:
Copy Citation:
PDF:
https://aclanthology.org/1991.iwpt-1.25.pdf