Incremental LL(1) Parsing in Language-Based Editors

John J. Shilling


Abstract
This paper introduces an efficient incremental LL(1) parsing algorithm for use in language-based editors that use the structure recognition approach. It features very fine grained analysis and a unique approach to parse control and error recovery. It also presents incomplete LL(1) grammars as a way of dealing with the complexity of full language grammars and as a mechanism for providing structured editor support for task languages that are only partially structured. The semantics of incomplete grammars are presented and it is shown how incomplete LL(1) grammars can be transformed into complete LL(1) grammars. The algorithms presented have been implemented in the fred language-based editor
Anthology ID:
1991.iwpt-1.6
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:
41–51
Language:
URL:
https://aclanthology.org/1991.iwpt-1.6
DOI:
Bibkey:
Cite (ACL):
John J. Shilling. 1991. Incremental LL(1) Parsing in Language-Based Editors. In Proceedings of the Second International Workshop on Parsing Technologies, pages 41–51, Cancun, Mexico. Association for Computational Linguistics.
Cite (Informal):
Incremental LL(1) Parsing in Language-Based Editors (Shilling, IWPT 1991)
Copy Citation:
PDF:
https://aclanthology.org/1991.iwpt-1.6.pdf