A practical method for constructing LR (k) processors

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A practical method for constructing LR (k) processors

Full text

Pdf (1.26 MB)

Source

Communications of the ACM archive
Volume 12 , Issue 11 (November 1969) table of contents

Pages: 613 - 623

Year of Publication: 1969

ISSN:0001-0782

Author

A. J. Korenjak

RCA Labs., Princeton, NJ

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 5, Downloads (12 Months): 22, Citation Count: 19

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/363269.363281 What is a DOI?

ABSTRACT

A practical method for constructing LR(k) processors is developed. These processors are capable of recognizing and parsing an input during a single no-backup scan in a number of steps equal to the length of the input plus the number of steps in its derivation. The technique presented here is based on the original method described by Knuth, but decreases both the effort required to construct the processor and the size of the processor produced. This procedure involves partitioning the given grammar into a number of smaller parts. If an LR(k) processor can be constructed for each part (using Knuth's algorithm) and if certain conditions relating these individual processors are satisfied, then an LR(k) processor for the entire grammar can be constructed for them. Using this procedure, an LR(1) parser for ALGOL has been obtained.

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	Jay Clark Earley, An efficient context-free parsing algorithm, 1968
	2	Jerome Feldman , David Gries, Translator writing systems, Communications of the ACM, v.11 n.2, p.77-113, Feb. 1968 [doi>10.1145/362896.362902]
	3	GINSBURG, S., ANn GREIBACH, S. A. Deterministic context-free languages. Inform. Contr. 9 (Dec. 1966), 620-648.
	4	KNUTH, D. E. On the translation of languages from left to right. Inform. Contr. 8 (Dec. 1965), 607-639.
	5	KORENJAK, A. J. Deterministic language processing. Thesis, Princeton, U., Princeton, N. J., Sept. 1967.
	6	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]
	7	SRINIVASAN, C. V. An introduction to CDLI, a computer description language. Scientific Rep. No. 1, Contract No. AF19 (628)4789, RCA Laboratories, Princeton, N. J., Sept. 1967.

CITED BY 19

	Alfred V. Aho , Jeffrey D. Ullman, The care and feeding of LR(k) grammars, Proceedings of the third annual ACM symposium on Theory of computing, p.159-170, May 03-05, 1971, Shaker Heights, Ohio, United States
	Franklin L. DeRemer, Simple LR(k) grammars, Communications of the ACM, v.14 n.7, p.453-460, July 1971
	Joseph Bates , Alon Lavie, Recognizing substrings of LR(k) languages in linear time, ACM Transactions on Programming Languages and Systems (TOPLAS), v.16 n.3, p.1051-1077, May 1994
	Ivan M. Havel , Michael A. Harrison, On the Parsing of Deterministic Languages, Journal of the ACM (JACM), v.21 n.4, p.525-548, Oct. 1974
	W. Douglas Findley , V. Santhanam, A practical algorithm for generating LR parsers maintaining immediate error detection (abstract), Proceedings of the 1986 ACM fourteenth annual conference on Computer science, p.491, February 1986, Cincinnati, Ohio, United States
	Jacques Loeck, An algorithm for the construction of bounded-context parsers, Communications of the ACM, v.13 n.5, p.297-307, May 1970
	Alfred V. Aho , Jeffrey D. Ullman, A technique for speeding up LR(k) parsers, Proceedings of the fourth annual ACM symposium on Theory of computing, p.251-263, May 01-03, 1972, Denver, Colorado, United States
	Pierpaolo Degano , Stefano Mannucci , Bruno Mojana, Efficient incremental LR parsing for syntax-directed editors, ACM Transactions on Programming Languages and Systems (TOPLAS), v.10 n.3, p.345-373, July 1988
	David Bruce Lomet, A Formalization of Transition Diagram Systems, Journal of the ACM (JACM), v.20 n.2, p.235-257, April 1973
	Wilf R. LaLonde, On directly constructing LR(k) parsers without chain reductions, Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages, p.127-133, January 19-21, 1976, Atlanta, Georgia
	Helen Meng , Po-Chui Luk , Kui Xu , Fuliang Weng, GLR parsing with multiple grammars for natural language queries, ACM Transactions on Asian Language Information Processing (TALIP), v.1 n.2, p.123-144, June 2002
	Mario Schkolnick, Labelled precedence parsing, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.33-40, October 01-03, 1973, Boston, Massachusetts
	David Pager, The lane tracing algorithm for constructing LR(k) parsers, Proceedings of the fifth annual ACM symposium on Theory of computing, p.172-181, April 30-May 02, 1973, Austin, Texas, United States
	A. V. Aho , S. C. Johnson, LR Parsing, ACM Computing Surveys (CSUR), v.6 n.2, p.99-124, June 1974
	Tatsuya Hayashi, On the construction of LR(k) analyzers, Proceedings of the 1971 26th annual conference, p.538-553, January 1971
	J. J. Horning , W. R. Lalonde, Empirical comparison of LR(k) and precedence parsers, ACM SIGPLAN Notices, v.5 n.11, November 1970
	Alan J. Demers, Generalized left corner parsing, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.170-182, January 17-19, 1977, Los Angeles, California
	Anja Belz, Learning grammars for different parsing tasks by partition search, Proceedings of the 19th international conference on Computational linguistics, p.1-7, August 24-September 01, 2002, Taipei, Taiwan
	J. D. Ullman, Applications of language theory to compiler design, Proceedings of the November 16-18, 1971, fall joint computer conference, November 16-18, 1971, Las Vegas, Nevada