Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars

Full text

Pdf (1.36 MB)

Source

Journal of the ACM (JACM) archive
Volume 23 , Issue 3 (July 1976) table of contents

Pages: 511 - 533

Year of Publication: 1976

ISSN:0004-5411

Authors

M. D. Mickunas	Department of Computer Science, Digital Computer Laboratory, University of Illinois at Urbana-Champaign, Urbana, IL
R. L. Lancaster	Computer Science Department, Bowling Green State University, Bowling Green, OH
V. B. Schneider	Department of Computer Sciences, Mathematical Sciences Building, Purdue University, West Lafayette, IN

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 0, Downloads (12 Months): 40, Citation Count: 3

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321958.321972 What is a DOI?

ABSTRACT

A method is presented for directly transforming an arbitrary LR(k) grammar to an equivalent LR(1) grammar. It is further shown that the method transforms an arbitrary prefix-free LR(k) grammar to an equivalent LR(0) grammar. It is argued that the method is efficient and offers some advantages over traditional “look-ahead” parsing methods. Finally, it is demonstrated that the method can be used to transform an LR(1) grammar to an equivalent SLR(1) grammar, which in turn can be easily transformed to an equivalent (1, 1) bounded right-context grammar.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	A. V. Aho , P. J. Denning , J. D. Ullman, Weak and Mixed Strategy Precedence Parsing, Journal of the ACM (JACM), v.19 n.2, p.225-243, April 1972 [doi>10.1145/321694.321697]
	2	Alfred V. Aho , Jeffrey D. Ullman, Theory of Parsing, Translation and Compiling, Prentice Hall Professional Technical Reference, 1973
	3	DRMER, F L. Practical translators for LR(k) languages Doctoral DiNs , M I T , Cambridge, Mass, Sept. 1969
	4	Franklin L. DeRemer, Simple LR(k) grammars, Communications of the ACM, v.14 n.7, p.453-460, July 1971 [doi>10.1145/362619.362625]
	5	Robert W. Floyd, Syntactic Analysis and Operator Precedence, Journal of the ACM (JACM), v.10 n.3, p.316-333, July 1963 [doi>10.1145/321172.321179]
	6	Robert W. Floyd, Bounded context syntactic analysis, Communications of the ACM, v.7 n.2, p.62-67, Feb. 1964 [doi>10.1145/363921.363927]
	7	GELLER, M.M, AND HARRISON, M A Characterizations of LR(0) languages (extended abstract) Proc. of the 14th Ann Symp on Switching and Automata Theory, Iowa City, I a , Oct. 1973, pp. 103-108 (sponsored by IEEE, New York)
	8	GINSBURG, S , AND GREIBACH, S A. Deterministic context-free languages. Inform. and Contr. 9 (1966), 620-648.
	9	Susan Lois Graham, Precedence languages and bounded right context languages, 1971
	10	GRAHAM, S L. On bounded right context languages and grammars. SIAM J. Comput. (1974), 224-254.
	11	James N. Gray , Michael A. Harrison, On the Covering and Reduction Problems for Context-Free Grammars, Journal of the ACM (JACM), v.19 n.4, p.675-698, Oct. 1972 [doi>10.1145/321724.321732]
	12	HARRISON, M.A. On the parsing of deterministic languages. Inv:ted presentation, ACM Comput. Sci. Conf, Columbus, Ohio, 1973 (oral presentatmn)
	13	HARRISON, M.A, AND HVEL, I.M. Strict determmmtlc grammars J Comput and Syst. Scls. 7 (1973), 237-277
	14	John E. Hopcroft , Jeffrey D. Ullman, Formal languages and their relation to automata, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1969
	15	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]
	16	KNUTH, D.E On the translation of languages from left to right. Inform. and Contr. 8 (1965), 607-639.
	17	LALONDE, W R An efficmnt LALR parser generator Tech. Rep CSRG-2, U of Toronto, Toronto, Ont , Canada, 1971
	18	L. Presser , J. McAfee, An Algorithm for the Design of Simple Precedence Grammars, Journal of the ACM (JACM), v.19 n.3, p.385-395, July 1972 [doi>10.1145/321707.321708]
	19	MICKUNAS, M.D User's manual for the PUCSD parser generating system. Tech Rep, Purdue U., West Lafayette, Ind., Aug. 1973.
	20	Marshall Dennis Mickunas, Techniques for compressing bounded-context acceptors, 1973
	21	MICKUNAS, M D., AND SCHNEIDER, V.B. On the ability to cover LR(k) grammars with LR(1), SLR(1), and (1, 1) bounded-context grammars Proc of the 14th Ann Symp. on Switching and Automata Theory, Iowa City, I a , Oct 1973, pp. 109-121 (sponsored by IEEE, New York).
	22	M. D. Mickunas , V. B. Schneider, A parser-generating system for constructing compressed compilers, Communications of the ACM, v.16 n.11, p.669-676, Nov. 1973 [doi>10.1145/355611.362536]
	23	REYNOLDS, J.C., AND HASKELL, R. Grammatical coverings Unpublished manuscript, 1970
	24	SCHNEIDER, V.B. A system for designing fast programminglanguage translators Proc.AFIPS 1969 SJCC, Vol. 34, AFIPS Press, Montvale, N J., pp. 777-792.
	25	Niklaus Wirth , Helmut Weber, EULER: a generalization of ALGOL, and its formal definition: Part II, Communications of the ACM, v.9 n.2, p.89-99, Feb. 1966 [doi>10.1145/365170.365202]

CITED BY 3

	Yeu-hsiung Liang, A parsing method on l-1 bounded context parsing, Proceedings of the 18th annual Southeast regional conference, March 24-26, 1980, Tallahassee, Florida
	Kou-Chung Tai, Noncanonical SLR(1) Grammars, ACM Transactions on Programming Languages and Systems (TOPLAS), v.1 n.2, p.295-320, Oct. 1979
	V. Schneider, Compiler textbook bibliographies considered harmful, ACM SIGPLAN Notices, v.25 n.8, p.72-74, Aug. 1990