Simple LR(k) grammars

ABSTRACT

A class of context-free grammars, called the “Simple LR(k)” or SLR(k) grammars is defined. This class has been shown to include weak precedence and simple precedence grammars as proper subsets. How to construct parsers for the SLR(k) grammars is also shown. These parser-construction techniques are extendible to cover all of the LR(k) grammars of Knuth; they have been implemented and by direct comparison proved to be superior to precedence techniques, not only in the range of grammars covered, but also in the speed of parser construction and in the size and speed of the resulting parsers.

REFERENCES

• 1: Cheatham, T. E. Jr. The Theory and Construction of Compilers. Massachusetts Computer Associates, Inc., Wakefield, Mass., 1967.
• 2: DeRemer, F. L. Practical translation for LR(k) languages. Ph.D. thesis. MIT, Cambridge, Mass. Sept., 1969.
• 3: DeRemer, F. L. Simple LR(k) grammars: Definition and implementation. CEP Rep. 2, 4 (Sept. 1970), U. of Calif., Santa Cruz.
• 4: De Remer, F. L. Minimal LR(k) parsers (In preparation).
• 5: De Remer, F. L. Error recovery using LR(k) techniques (In preparation).
• 6: Jay Earley, An efficient context-free parsing algorithm, Communications of the ACM, v.13 n.2, p.94-102, Feb 1970 [doi>10.1145/362007.362035]
• 7: Homing, J. J., and Lalonde, W. R. Empirical comparison of LR(k) and precedence parsers. Tech. Rep. CSRG-1, Computer Syst. Res. Gr., U. of Toronto, Canada, undated (rec. Sept. 1970).
• 8: John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
• 9: J. D. Ichbiah , S. P. Morse, A technique for generating almost optimal Floyd-Evans productions for precedence grammars, Communications of the ACM, v.13 n.8, p.501-508, Aug. 1970 [doi>10.1145/362705.362712]
• 10: A. J. Korenjak, A practical method for constructing LR (k) processors, Communications of the ACM, v.12 n.11, p.613-623, Nov. 1969 [doi>10.1145/363269.363281]
• 11: Knuth, D. E. On the translation of languages from left to right. Inf. Contr. 8 (Oct. 1965), 607-639.
• 12: McKeeman, W. M., Horning, J. J., and Wortman, D. B. A Complier Generator. Prentice-Hall, Englewood Cliffs, N.J., 1970.
• 13: J. W. Backus , F. L. Bauer , J. Green , C. Katz , J. McCarthy , A. J. Perlis , H. Rutishauser , K. Samelson , B. Vauquois , J. H. Wegstein , A. van Wijngaarden , M. Woodger , P. Naur, Revised report on the algorithm language ALGOL 60, Communications of the ACM, v.6 n.1, p.1-17, Jan. 1963 [doi>10.1145/366193.366201]
• 14: Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL and it formal definition: Part 1, Communications of the ACM, v.9 n.1, p.13-25, Jan. 1966 [doi>10.1145/365153.365162]
• 15: Reddy, D. R., and McKeeman, W. M. Computer programming: An introduction to PL. Prelimin. Rep., Stanford U., Stanford, Calif., 1969.
• 16: Arthur Evans, Jr., PAL—a language designed for teaching programming linguistics, Proceedings of the 1968 23rd ACM national conference, p.395-403, August 27-29, 1968 [doi>10.1145/800186.810604]

INDEX TERMS

Keywords:
LR(k) grammar, context-free grammar, deterministic pushdown automaton, finite-state machine, parser, parsing algorithm, precedence grammar, syntactic analysis