Article

Free access

A practical arbitrary look-ahead LR parsing technique

Authors:

Manuel E. Bermudez,

Karl M. SchimpfAuthors Info & Claims

SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler construction

Pages 136 - 144

https://doi.org/10.1145/12276.13325

Published: 01 July 1986 Publication History

PDF eReader

Abstract

We present a practical technique that provides an LR (0) parser with either fixed or arbitrary look-ahead. The construction algorithm is based on certain paths in the LR (0) state diagram, which must be restricted to a maximum length m. The technique determines the amount of look-ahead required, and the user is spared the task of guessing it. Instead, the user provides m. In situations where single symbol look-ahead is sufficient, the corresponding grammar class (called LAR (m )) is identical to the NQLALR (1) class. For practical grammars that require arbitrary look-ahead, the storage requirements typically do not exceed an amount linear in the size of the corresponding LR (0) parser. The technique is shown to work for a practical programming language grammar, and has been used to solve particular cases of the PL/1 keyword problem.

References

[1]

Anderson, T., Eve, J. and Horning, J. J., Efficient LR (1) parsers, Acta Informatica 2, 12-39, 1973.

Digital Library

Google Scholar

[2]

Baker, Theodore P., Extending Lookahead for LR parsers, Journal of Computer and System Science 22(2), 1982.

Crossref

Google Scholar

[3]

Bermudez, Manuel E., Regular Look-ahead and Look-back for LR Parsers Ph.D. Thesis, Computer and Information Sciences Board of Studies, University of California, Sant~a Cruz, June, 1984.

Digital Library

Google Scholar

[4]

Culik, C. and Cohen, R., LR-Regular Grammars - an Extension of LR (k) Grammars, Journal of Computer and System Sciences 7, pp. 66-96, 1973.

Digital Library

Google Scholar

[5]

DeRemer, Franklin L., Practical Translators for LR (k) languages, Ph.D. Thesis, Department of Electrical Engineering, M.I.T., Cambridge, Mass., 1969.

Google Scholar

[6]

DeRemer, Franklin L., Simple LR(k) grammars, CACM 14(7), pp. 453-460, July, 1971.

Digital Library

Google Scholar

[7]

DeRemer, F. L. and Pennello, T. J., Efficient Computation of LALR (1) Lookahead Sets, ACM TOPLAS 4(4), October 1982.

Digital Library

Google Scholar

[8]

Harrison, M., An introduction for Formal Language Theory, Addison-Wesley, Reading, Massachusetts, 1978.

Digital Library

Google Scholar

[9]

Knuth, D. E., On the translation of languages from left to right, Information and Control 8, pp. 607-639, 1965.

Crossref

Google Scholar

[10]

Kristensen, B.B. and Madsen, O.L., Methods for computing LALR (k)look-ahead, ACM Transn ctions on Programming Languages and Systems 3(1), pp. 60-82, January, 1981.

Digital Library

Google Scholar

[11]

LaLonde, W. R., An efficient LALR parser generator, Tech. Rep. 2, Computer Systems Research Group, Univ. of Toronto, 1971.

Google Scholar

[12]

Pager, D., A practical general method for constructing LR (k) parsers, Aeta Inforn~atica 7, 249-268, 1977.

Digital Library

Google Scholar

Cited By

View all

Seyfarth BBermudez M(2007)Suffix languages in Lr parsingInternational Journal of Computer Mathematics10.1080/0020716950880437055:3-4(135-153)Online publication date: 20-Mar-2007
https://doi.org/10.1080/00207169508804370
Bermudez M(1989)Lar(m, c, l) grammarsInternational Journal of Computer Mathematics10.1080/0020716890880372628:1-4(27-45)Online publication date: Jan-1989
https://doi.org/10.1080/00207168908803726
Bermudez M(1988)A unifying model for lookahead LR parsingProceedings. 1988 International Conference on Computer Languages10.1109/ICCL.1988.13038(18-24)Online publication date: 1988
https://doi.org/10.1109/ICCL.1988.13038
Show More Cited By

Recommendations

A practical arbitrary look-ahead LR parsing technique

We present a practical technique that provides an LR (0) parser with either fixed or arbitrary look-ahead. The construction algorithm is based on certain paths in the LR (0) state diagram, which must be restricted to a maximum length m. The technique ...
LR(k)-parsing of Coupled-Context-Free Grammars
COLING '94: Proceedings of the 15th conference on Computational linguistics - Volume 1

Coupled-Context-Free Grammars are a generalization of context-free grammars obtained by combining nonterminals to parentheses which can only be substituted simultaneously. Referring to the generative capacity of the grammars we obtain an infinite ...
Parsing extended LR(k) grammars

An extended LR(k) (ELR(k)) grammar is a context free grammar in which the right sides of the productions are regular expressions and which can be parsed from left to right with k symbol look-ahead. We present a practical algorithm for producing small ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

SIGPLAN '86: Proceedings of the 1986 SIGPLAN symposium on Compiler construction

July 1986

275 pages

ISBN:0897911970

DOI:10.1145/12276

Editor:
Richard L Wexelblat
Philips Laboratories, Briarcliff Manor, NY

ACM SIGPLAN Notices Volume 21, Issue 7
July 1986
275 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/13310
Editor:
Richard L. Wexelblat
Philips Laboratories, Briarcliff Manor, NY
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1986

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SCC86

Sponsor:

SIGPLAN

SCC86: SIGPLAN Symposium on Compiler Construction

June 25 - 27, 1986

California, Palo Alto, USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
828
Total Downloads

Downloads (Last 12 months)126
Downloads (Last 6 weeks)17

Reflects downloads up to 16 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Seyfarth BBermudez M(2007)Suffix languages in Lr parsingInternational Journal of Computer Mathematics10.1080/0020716950880437055:3-4(135-153)Online publication date: 20-Mar-2007
https://doi.org/10.1080/00207169508804370
Bermudez M(1989)Lar(m, c, l) grammarsInternational Journal of Computer Mathematics10.1080/0020716890880372628:1-4(27-45)Online publication date: Jan-1989
https://doi.org/10.1080/00207168908803726
Bermudez M(1988)A unifying model for lookahead LR parsingProceedings. 1988 International Conference on Computer Languages10.1109/ICCL.1988.13038(18-24)Online publication date: 1988
https://doi.org/10.1109/ICCL.1988.13038
Seite B(1987)A YACC extension for LRR grammar parsingTheoretical Computer Science10.1016/0304-3975(87)90082-X52:1-2(91-143)Online publication date: 1987
https://doi.org/10.1016/0304-3975(87)90082-X
Parr TQuong R(1996)LL and LR translators need k>1 lookaheadACM SIGPLAN Notices10.1145/226060.22606631:2(27-34)Online publication date: 1-Feb-1996
https://dl.acm.org/doi/10.1145/226060.226066
Ancona MBartolozzi APaci MProvvedi S(1992)Practical optimizations of LR(k) parsing tablesEleventh Annual International Phoenix Conference on Computers and Communication [1992 Conference Proceedings]10.1109/PCCC.1992.200607(569-576)Online publication date: 1992
https://doi.org/10.1109/PCCC.1992.200607
Harford AHeuring VMain M(1992)A new parsing method for Non-LR(1) grammarsSoftware—Practice & Experience10.1002/spe.438022050522:5(419-437)Online publication date: 1-May-1992
https://dl.acm.org/doi/10.1002/spe.4380220505
Bermudez MSchimpf K(1990)Practical arbitrary lookahead LR parsingJournal of Computer and System Sciences10.1016/0022-0000(90)90037-L41:2(230-250)Online publication date: Oct-1990
https://doi.org/10.1016/0022-0000(90)90037-L
Salomon DCormack G(1989)Scannerless NSLR(1) parsing of programming languagesACM SIGPLAN Notices10.1145/74818.7483324:7(170-178)Online publication date: 21-Jun-1989
https://dl.acm.org/doi/10.1145/74818.74833
Salomon DCormack G(1989)Scannerless NSLR(1) parsing of programming languagesProceedings of the ACM SIGPLAN 1989 conference on Programming language design and implementation10.1145/73141.74833(170-178)Online publication date: 21-Jun-1989
https://dl.acm.org/doi/10.1145/73141.74833

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A practical arbitrary look-ahead LR parsing technique

LR(k)-parsing of Coupled-Context-Free Grammars

Parsing extended LR(k) grammars