LR Parsing

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

LR Parsing

Full text

Pdf (1.85 MB)

Source

ACM Computing Surveys (CSUR) archive
Volume 6 , Issue 2 (June 1974) table of contents

Pages: 99 - 124

Year of Publication: 1974

ISSN:0360-0300

Authors

A. V. Aho	Bell Laboratories, Murray Hill, New Jersey
S. C. Johnson	Bell Laboratories, Murray Hill, New Jersey

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 135, Citation Count: 36

Additional Information:

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

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	A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.1-21, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512928]
	3	AHO, A. V , AND PETERSON, T G "A minimum distance error-correcting parser for contextfree languages." SIAM J. Computing 1, 4 (1972) 305-312
	4	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	5	AHO, h. V., AND ULLMAN, J. D. "Optimization of LR(k) parsers." J. Computer and System Sciences 6, 6 (1972b), 573-602.
	6	Alfred V. Aho , Jeffrey D. Ullman, The Theory of Parsing, Translation, and Compiling, Prentice Hall Professional Technical Reference, 1972
	7	AHO, A. V , AND ULLMAN, J. }_). "A techmque for speeding up LR(k) parsers " SIAM J. Computing 2, 2 (1973b), 106-127.
	8	ANDERSON, T. Syntactic analys~s of LR(k) languages. PhD Thesis, Univ Newcastle-upon- Tyne, Northumberland, England (1972)
	9	ANDERSON, T, EVE, J., AND HORNING, J J. "Efficmnt LR(1) parsers." Acta Informatica 2 (1973), 12-39.
	10	DEMERS, A. "Ehmination of single productions and merging nontermlnal symbols of LR(1) grammars " Technical Report TR-127, Computer Science Laboratory, Dept of Electmcal Engineering, Princeton Univ., Princeton, N.J, July 1973.
	11	F. L. Deremer, PRACTICAL TRANSLATORS FOR LR(K) LANGUAGES, Massachusetts Institute of Technology, Cambridge, MA, 1969
	12	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]
	13	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]
	14	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]
	15	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]
	16	Susan L. Graham , Steven P. Rhodes, Practical syntactic error recovery in compilers, Proceedings of the 1st annual ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.52-58, October 01-03, 1973, Boston, Massachusetts [doi>10.1145/512927.512932]
	17	GaiES, D Compiler Conslructzon for D~g~tal Computers. Wiley, New York, 1971
	18	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]
	19	JAMES, L R. "A syntax directed error recovery method." Technical Report CSRG-13, Compurer Systems Research Group, Univ Toronto, Toronto, Canada, 1972.
	20	Marc Louis Joliat, On the reduced matrix representation of lr(k) parser tables., 1973
	21	KNVTH, D E "On the translatmn of languages from left to right " Information and Control 8, 6 (1965), 607-639
	22	KNUTH, D. E "Top down syntax analysis." Acta Informatzca 1, 2 (1971), 97-110
	23	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]
	24	LALONDE, W R., LEE, E S., AND HORNING, J. J "An LALR(k) parser generator." Proc. IFIP Congress 71 TA-3, North-Holland Publishing Co., Amsterdam, the Netherlands (1971), pp. 153-157.
	25	Ronald Paul Leinius, Error detection and recovery for syntax directed compiler systems, 1970
	26	P. M. Lewis , D. J. Rosenkrantz , R. E. Stearns, Attributed translations(Extended Abstract), Proceedings of the fifth annual ACM symposium on Theory of computing, p.160-171, April 30-May 02, 1973, Austin, Texas, United States [doi>10.1145/800125.804047]
	27	P. M. Lewis, II , R. E. Stearns, Syntax-Directed Transduction, Journal of the ACM (JACM), v.15 n.3, p.465-488, July 1968 [doi>10.1145/321466.321477]
	28	McGRvT~a, T. "An approach to automating syntax error detection, recovery, and correction for LR(k) grammars." Master's Thesis, Naval Postgraduate School, Monterey, Calif, 1972
	29	MCKEEMAN, W. M, HORNING, J J., AND WORT- MAN, D. B A Compiler Generator. Prentice- Hall, Englewood Cliffs, N J., 1970.
	30	PAGLR, D. "A solution to an open problem by Knuth." Informatwn and Control 17 (1970), 462-473.
	31	PAGER, D. "On the incremental approach to leftto-right parsing " Technical Report PE 238, Information Scmnces Program, Univ. Hawaii, Honolulu, Hawan, 1972a.
	32	PAGER, D "A fast left-to-right parser for context-free grammars." Technical Report PE 240, Informatmn Scmnces Program, Untv. Hawaii, Honolulu, Hawaii, 1972b
	33	PAGF~R, D. "On eliminating unit productions from LR(k) parsers." Technmal Report, Information Scmnces Program Univ Hawaii, Honolulu, Hawaii, 1974
	34	PI.~TERSON, T G. "Syntax error detection, correction and recovery in parsers." PhD Thesis, Stevens institute of Technology, Hoboken, N. J, 1972
	35	Niklaus Wirth, PL360, a Programming Language for the 360 Computers, Journal of the ACM (JACM), v.15 n.1, p.37-74, Jan. 1968 [doi>10.1145/321439.321442]
	36	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 36

	Eljas Soisalon-Soininen, Elimination of single productions from LR parsers in conjunction with the use of default reductions, Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.183-193, January 17-19, 1977, Los Angeles, California
	Mona E. Lovato , Michael F. Kleyn, Parser visualizations for developing grammars with yacc, ACM SIGCSE Bulletin, v.27 n.1, p.345-349, March 1995
	Henry D. Shapiro , M. Dennis Mickunas, A new approach to teaching a first course in compiler construction, ACM SIGCSE Bulletin, v.8 n.1, p.158-166, February 1976
	Thomas J. Pennello , Frank DeRemer, A forward move algorithm for LR error recovery, Proceedings of the 5th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.241-254, January 23-25, 1978, Tucson, Arizona
	Brian W. Kernighan , Lorinda L. Cherry, A system for typesetting mathematics, Communications of the ACM, v.18 n.3, p.151-157, March 1975
	Alan M. Davis , Walter J. Rataj, Requirements language processing for the effective testing of real-time systems, ACM SIGSOFT Software Engineering Notes, v.3 n.5, p.61-66, November 1978
	Frank DeRemer , Thomas Pennello, Efficient Computation of LALR(1) Look-Ahead Sets, ACM Transactions on Programming Languages and Systems (TOPLAS), v.4 n.4, p.615-649, Oct. 1982
	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
	M. Dennis Mickunas , John A. Modry, Automatic error recovery for LR parsers, Communications of the ACM, v.21 n.6, p.459-465, June 1978
	Mariano P. Consens , Tova Milo, Optimizing queries on files, ACM SIGMOD Record, v.23 n.2, p.301-312, June 1994
	Kai Koskimies, A specification language for one-pass semantic analysis, ACM SIGPLAN Notices, v.19 n.6, p.179-189, June 1984
	A. V. Aho , S. C. Johnson , J. D. Ullman, Deterministic parsing of ambiguous grammars, Communications of the ACM, v.18 n.8, p.441-452, Aug. 1975
	M. Dennis Mickunas , Richard M. Schell, Parallel Compilation In A Multiprocessor Environment (Extended Abstract), Proceedings of the 1978 annual conference, p.241-246, December 04-06, 1978, Washington, D.C., United States
	Stuart M. Shieber, Sentence disambiguation by a shift-reduce parsing technique, Proceedings of the 21st annual meeting on Association for Computational Linguistics, June 15-17, 1983, Cambridge, Massachusetts
	Michael Niv, A psycholinguistically motivated parser for CCG, Proceedings of the 32nd annual meeting on Association for Computational Linguistics, p.125-132, June 27-30, 1994, Las Cruces, New Mexico
	Norman K. Sondheimer , Ralph M. Weischedel, A rule-based approach to ill-formed input, Proceedings of the 8th conference on Computational linguistics, September 30-October 04, 1980, Tokyo, Japan
	Santanu Paul , Atul Prakash, Generating programming language-based pattern matchers, Proceedings of the 1993 conference of the Centre for Advanced Studies on Collaborative research: software engineering, October 24-28, 1993, Toronto, Ontario, Canada
	Masaru Tomita, LR parsers for natural languages, Proceedings of the 22nd annual meeting on Association for Computational Linguistics, p.354-357, July 02-06, 1984, Stanford, California
	Tsuneko Nakazawa, An extended LR parsing algorithm for grammars using feature-based syntactic categories, Proceedings of the fifth conference on European chapter of the Association for Computational Linguistics, p.69-74, April 09-11, 1991, Berlin, Germany
	R. L. Johnson , S. Krauwer , M. A. Rosner , G. B. Varile, The design of the kernel architecture for the Eurotra software, Proceedings of the 22nd annual meeting on Association for Computational Linguistics, p.226-235, July 02-06, 1984, Stanford, California
	Mathew N. Matelan, MPACT: microprocessor application to control-firmware translator, ACM SIGDA Newsletter, v.5 n.1, p.13-41, March 1975
	Rafael Corchuelo , José A. Pérez, , Antonio Ruiz , Miguel Toro, Repairing syntax errors in LR parsers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.24 n.6, p.698-710, November 2002
	Masaru Tomita, An efficient augmented-context-free parsing algorithm, Computational Linguistics, v.13 n.1-2, p.31-46, January-June 1987
	Harry Bunt , John Carroll , Giorgio Satta, Development in parsing technology: from theory to application, New developments in parsing technology, Kluwer Academic Publishers, Norwell, MA, 2004
	Mark Green, A survey of three dialogue models, ACM Transactions on Graphics (TOG), v.5 n.3, p.244-275, July 1986
	Peter N. van den Bosch, A bibliography on syntax error handling in context free languages, ACM SIGPLAN Notices, v.27 n.4, p.77-86, April 1992
	Sylvain Marquis , Thomas R Dean , Scott Knight, Packet decoding using context sensitive parsing, Proceedings of the 2006 conference of the Center for Advanced Studies on Collaborative research, October 16-19, 2006, Toronto, Ontario, Canada
	Robert Glück , Masahiko Kawabe, A Method for Automatic Program Inversion Based on LR(0) Parsing, Fundamenta Informaticae, v.66 n.4, p.367-395, December 2005
	Serge Abiteboul , Sophie Cluet , Tova Milo, Querying and Updating the File, Proceedings of the 19th International Conference on Very Large Data Bases, p.73-84, August 24-27, 1993
	Ad J. van de Goor , Aad Offerman , Ivo Schanstra, Towards a Uniform Notation for Memory Tests, Proceedings of the 1996 European conference on Design and Test, p.420, March 11-14, 1996
	M. Share, Resolving ambiguities in the parsing of translation grammars, ACM SIGPLAN Notices, v.23 n.8, p.103-109, August 1988
	B. W. Lampson , J. J. Horning , R. L. London , J. G. Mitchell , G. J. Popek, Report on the programming language Euclid, ACM SIGPLAN Notices, v.12 n.2, p.1-79, February 1977
	Norman Ramsey, Pragmatic aspects of reusable program generators, Journal of Functional Programming, v.13 n.3, p.601-646, May 2003
	Robert C. Gammill , Herbert J. Shukiar, An interactive system for aiding management decision making, Proceedings of the June 13-16, 1977, national computer conference, June 13-16, 1977, Dallas, Texas
	Masaru Tomita, An efficient context-free parsing algorithm for natural languages, Proceedings of the 9th international joint conference on Artificial intelligence, p.756-764, August 18-23, 1985, Los Angeles, California
	Stuart M. Shieber, Sentence disambiguation by a shift-reduce parsing technique, Proceedings of the Eighth international joint conference on Artificial intelligence, p.699-703, August 08-12, 1983, Karlsruhe, West Germany