Summary
The concept of incremental parsing is briefly introduced. An algorithm which augments an LR parser with the capability of reanalyzing a limited part of a modified program is illustrated. The algorithm operates on a sequence of configurations representing the parse of the old input and finds the smallest part of the sequence which must be recomputed to obtain the parse of the new input.
The implementation is discussed: a suitable data structure and a version of the algorithm which operates upon it are introduced; finally the problem of realizing efficient incremental parsers is faced, showing a modification to the basic algorithm which enable the reanalysis to be performed in linear time.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aho, A.V., Ullman, J.D.: Theory of parsing, translation and compiling, Vols. 1 and 2. Englewood Cliffs, N.J.: Prentice Hall 1972–73
Anderson, T., Eve, J., Horning, J.J.: Efficient LR(1) parsers. Acta Informat. 2, 12–39 (1973)
Ghezzi, C., Mandrioli, D.: Incremental parsing. Politecnico di Milano, Istituto di Elettrotecnica ed Elettronica, Internal Report IEEPM n. 76–15 (1976) (submitted for publication)
Ghezzi, C., Mandrioli, D.: Augmenting parsers to support incrementality. Politecnico di Milano, Istituto di Elettrotecnica ed Elettronica, Internal Report IEEPM n. 77–6 (1977) (submitted for publication)
Snowdon, R.A.: PEARL: an interactive system for the preparation and validation of structured programs. In: Program test methods (W.C. Hetzel, ed.), pp. 57–72. Englewood Cliffs, N.J.: Prentice Hall 1973
Wilcox, T.R., Davis, A.M., Tindall, M.M.: The design and implementation of a table driven, interactive diagnostic programming system. Comm. ACM 19, 609–617 (1976)
Yonke, M.: A knowledgeable language independent system for program construction and modification. ISI-USC-RR-75-42, 1975
Author information
Authors and Affiliations
Additional information
Work supported by C.N.R., Italy
Rights and permissions
About this article
Cite this article
Celentano, A. Incremental LR parsers. Acta Informatica 10, 307–321 (1978). https://doi.org/10.1007/BF00265676
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00265676