Abstract
A user of an LALR(k) parser generator system may have difficulties in understanding how a given LALR(k) conflict is generated. This is especially difficult if the conflict does not correspond to an LR(k) conflict.
A practical method for giving informative diagnostics on LALR(k) conflicts is presented. The diagnostics distinguish between those LALR(k) conflicts that correspond to LR(k) conflicts and those that do not. As a side effect the user is thus informed whether or not his grammar is in fact LR(k) despite not being LALR(k).
The method is based on an algorithm for testing LR(k)-ness using the LR(0) machine supplied with LALR(k) lookahead sets. This algorithm is presented and its correctness is proved.
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. and Ullman, J. D.:The Theory of Parsing, Translation and Compiling, Vol. I and II, Prentice-Hall, Englewood Cliffs, N.J., 1973.
DeRemer, F. L.:Practical Translators for LR (k)Languages, Ph. D. Diss., MIT, Cambridge, Mass., 1969.
DeRemer, F. L.:Simple LR (k)grammars, Comm. ACM 14:7, 453–460, 1971.
DeRemer, F. L. and Pennello, T. J.:Efficient computation of LALR (1)look-ahead-sets, SIGPLAN Notices, 14:8, 176–187, 1979.
Eriksen, S. H., Jensen, B. B., Kristensen, B. B. and Madsen, O. L.:The BOBS-System, Computer Science Department, Aarhus University, 1973 (Revised version DAIMI PB-71, 1979).
Hunt, H. B., Szymanski, T. G. and Ullman, J. D.:On the complexity of LR (k)testing, Comm. ACM 18:12, 707–716, 1975.
Knuth, D. E.:On the translation of languages from left to right, Info. Contr., 8, 6, 607–639, 1965.
Kristensen, B. B. and Madsen, O. L.:Methods for computing LALR (k)look-ahead, ACM Transactions on Programming Languages and Systems, Vol. 3, No. 1, January 1981, pp. 60–82.
Kristensen B. B. and Madsen, O. L.:Methods for LR (k)testing, (Informative Diagnostics on LALR (k) Conflicts) Computer Science Department, Aarhus University, 1979, DAIMI PB-106.
Kristensen, B. B. and Madsen, O. L.:A general algorithm for solving a set of recursive equations (exemplified by LR-theory), Computer Science Department, Aarhus University, DAIMI PB-110, February 1980.
Pager, D.:The lane-tracing algorithm for constructing LR (k)parsers and ways of enhancing its efficiency, Inf. Sci. 12, 19–42, 1977.
Pager, D.:A practical general method for constructing LR (k)parsers, ACTA Informatica 7, 249–268, 1977.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Kristensen, B.B., Madsen, O.L. Diagnostics on LALR(k) conflicts based on a method for LR(k) Testing. BIT 21, 270–293 (1981). https://doi.org/10.1007/BF01941463
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01941463