A Drop-in Replacement for LR(1) Table-Driven Parsing

Michael Oudshoorn


This paper presents a construction method for a deterministic one-symbol look-ahead LR parser which allows non-terminals in the parser look-ahead. This effectively relaxes the requirement of parsing the reverse of the right-most derivation of a string/sentence. This is achieved by replacing the deterministic push down automata of LR parsing by a two-stack automata. The class of grammars accepted by the two-stack parser properly contains the LR(k) grammars. Since the modification to the table-driven LR parsing process is relatively minor and mostly impacts the creation of the goto and action tables, a parser modified to adopt the two-stack process should be comparable in size and performance to LR parsers.


LR Parsing; Parsing Algorithm

Full Text:



Aho, A.V. and Ullman, J.D., The Theory of Parsing, Translation and Compiling, Volume. 1, Prentice-Hall, Englewood Cliffs, N.J., 1972.

Aho, A.V. and Johnson, S.C., “LR Parsing,” Computing Surveys, 6(2):99-124, June 1974.

Aho, A.V., Lam, M., Sethi, R., and Ullman, J.D., Compilers: Principles, Techniques and Tools, 2nd edition, Addison-Wesley, 2006.

Ancona, M., Dodero, G., Gianuzzi, V., and Morgavi, M., “Efficient Construction of LR(k) States and Tables”, ACM Transactions on Programming Languages and Systems, 13(1)150-178, January 1991.

Barnes, J.G.P., Programming in Ada 2012, Cambridge, Cambridge Press, 2014.

Bermudez, M.E. and Schimpf, K.M., “A Practical Arbitrary Look-Ahead LR Parsing Technique”, ACM SIGPLAN Notices, 21(7):136-144, July 1986.

Cardelli, L., Donahue, J., Glassman, L., Jordan, M., Kalsow, B. and Nelson, G., “Modula-3 Language Definition”, ACM SIGPLAN Notices, 27(8):42-82, 1992.

Chen, X. and Pager, D.. “Full LR(1) Parser Generator Hyacc and Study on the Performance of LR(1) algorithms”. In Proceedings of The Fourth International C* Conference on Computer Science and Software Engineering (C3S2E '11). Association for Computing Machinery, New York, NY, USA, 83–92, 2011.

Culik, K. and Cohen, R., “LR-Regular Grammars – an Extension of LR(k) Grammars”, Computer and System Science, 7:66-96, 1973.

DeRemer, F. and Pennello, T., “Efficient Computation of LALR(1) Look-Ahead Sets”, ACM Transactions on Programming Languages and Systems, 4(4):615-649, October 1982.

DeRemer, F.L., “Simple LR(k) Grammars”, Communications of the ACM, 14(7):453-460, July 1971.

Fischer, C.N., Cytron, R.K. and LeBlanc, R.J.,Jr., Crafting a Compiler, 1st edition, Addison-Wesley Publishing Company, 2010.

Harford, A.G., Heuring, V.P., and Main, M. G., “A New Parsing Method for Non-LR(1) Grammars”, Software – Practice and Experience, 22(5):419-437, Wiley, May 1992.

Harris, L.A., “SLR(1) and LALR(1) Parsing for Unrestricted Grammars”, Acta Informatica, 24:191-209, 1987.

Holub, A.I., Compiler Design in C, Prentice-Hall, Englewood Cliffs, N.J., 1990.

Hopcroft, J.E. and Ullman, J.D., Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979.

Horning, J.J., “LR Grammars and Analyzers” in Compiler Construction, an Advanced Course, 2nd edition, F. L. Bauer and J. Eikel (eds), pp. 85-107, Springer,1976.

Hudak, P., Jones, S.P., and Wadler, P.L., (eds), “Report on the Functional Programming Language Haskell, version 1.2”, ACM SIGPLAN Notices, 27(5), May 1992.

Jensen, K. and Wirth, N., “Pascal – User Manual and Report”, 2nd edition, Lecture Notes in Computer Science No. 18, Springer, New York, 1975.

Johnson, S.C., “YACC: Yet Another Compiler-Compiler”, Computer Science Technical Report 32, Bell Laboratories, Murray Hill, NJ, 1975.

Kernighan, B.W. and Ritchie, D.M., The C Programming Language, 2nd edition, Prentice-Hall, Englewood Cliffs, N.J., 1988.

Knuth, D.E., “On the Translation of Languages From Left to Right”, Information and Control, 8(6):607-639, 1965.

Lesk, M.E. and Schmidt, E., “Lex-a Lexical Analyzer Generator” in UNIX Programmer's Manual 2, AT&T Bell Labs., Murray Hill, N.J., 1975.

Marlow, S., et al. Haskell 2010 Language Report, Available online https://www.haskell/org/(May 2011), 2010.

Mason, T. and Brown, D. Lex & Yacc, O’Reilly & Associates, 1990.

McPeak, S., and Necula, G. C. “Elkhound: A fast, practical GLR parser generator.” Proceedings of Compiler Construction, pp. 73-88, 2004. Retrieved from https://escholarship.org/uc/item/8559j464.

Naur, P., (ed), “Report on the Algorithmic Language ALGOL 60”, Communications of the ACM, 3(5):299-314, 1960. Revised in Communications of the ACM, 6:1-20, 1963.

Richards, M. and Whitby-Strevens, C., BCPL - the Language and its Compiler, Cambridge University Press, 1981.

Seite, B., “A YACC Extension for LRR Grammar Parsing”, Theoretical Computer Science, 52:91-143, 1987.

Sippu, S. and Soisalon-Soininen, E., Parsing Theory, Volume II: LR(k) and LL(k) Parsing, Springer, Berlin, 1990.

Spector,D., “Efficient Full LR(1) Parser Generation”, SIGPLAN Notices, 23(12):143-150, December 1988.

Taft, S. Tucker. et al. Ada 2012 Reference Manual. Language and Standard Libraries International Standard ISO/IEC 8652/2012 (E) . 1st ed. 2013. Berlin, Heidelberg: Springer Berlin Heidelberg, 2013. Web.

Turnbull, C.J.M. and Lee, E.S., “Generalized Deterministic Left to Right Parsing”, Acta Informatica, 12:187-207, 1979.

Wirth, N., “What Can we do About the Unnecessary Diversity of Notation for Syntactic Definitions”, Communications of the ACM, 20(11):822-823, November 1977.

Wirth, N., Programming in Modula-2, 2nd edition, Springer-Verlag, New York, 3rd edition, 1985.

DOI: https://dx.doi.org/10.21622/ace.2021.01.2.047


  • There are currently no refbacks.

Copyright (c) 2021 Michael Oudshoorn

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

Advances in Computing and Engineering
E-ISSN: 2735-5985
P-ISSN: 2735-5977

Published by:

Academy Publishing Center (APC)
Arab Academy for Science, Technology and Maritime Transport (AASTMT)
Alexandria, Egypt