More Web Proxy on the site http://driver.im/

article

Free access

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

Authors:

M. D. Mickunas,

R. L. Lancaster,

V. B. SchneiderAuthors Info & Claims

Journal of the ACM (JACM), Volume 23, Issue 3

Pages 511 - 533

https://doi.org/10.1145/321958.321972

Published: 01 July 1976 Publication History

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

[1]

AHO, A V, DENNING, P J., AND ULLMAN, J.D Weak and mixed strategy precedence parsing. J ACM 19, 2 (April 1972), 225-243.

[2]

AHo, A.V, AND ULLMAN, J.D. The Theory of Parszng, Translatwn, and Comphng, Vol. Prentice-Hall, Englewood Cliffs, N.J, 1973.

[3]

DRMER, F L. Practical translators for LR(k) languages Doctoral DiNs, M I T, Cambridge, Mass, Sept. 1969

[4]

DEREMR, F.L Simple LR(k) grammars. Comm. ACM 14, 7 (July 1971), 453---460.

[5]

FLOYD, R W Syntactic analysis and operator precedence J. ACM 10, 3 (July 1963), 316-333

[6]

FLOYD, R.W. Bounded-context syntactic analysis Comm. ACM 7, 2 (Feb 1964), 62-67

[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]

GRAHAM, S.L. Precedence languages and bounded right context languages Doctoral DiNs, Stanford U, Stanford, Calif., July 1971

[10]

GRAHAM, S L. On bounded right context languages and grammars. SIAM J. Comput. (1974), 224-254.

[11]

GRAY, J N, AND HARRISON, M.A On the covering and reduction problems for context-free grammars, J. ACM 19, 4 (Oct. 1972), 675-698

[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]

HOPCROFT, J.E., AND ULLMAN, J D. Formal Languages and Their Relatzon to Automata Addison-Wesley, Reading, Mass., 1969

[15]

ICHBIAH, J.D, AND MORSE, S P A technique for generating almost optimal Floyd-Evans productions for precedence grammars. Comm ACM 13, 8 (Aug. 1970), 501-508.

[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]

McAFEE, J., AND PRESSER, L. An algorithm for the design of simple precedence grammars J ACM 19, 3 (July 1972), 385-395.

[19]

MICKUNAS, M.D User's manual for the PUCSD parser generating system. Tech Rep, Purdue U., West Lafayette, Ind., Aug. 1973.

[20]

MICKUNAS, M.D Techmques for compressing bounded-context aceeptors. Doctoral DiNs., Purdue U, West Lafayette, Ind, May 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]

MICKUNAS, M D, XND SCHNEIDER, V.B. A parser-generating system for constructing compressed compilers Comm ACM i6, 11 (Nov. 1973), 669-676

[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]

WIRTH, N, AND WEBER, H. EULER: a generalization of ALGOL and its formal defimtlon: Parts I, II. Comm. ACM 9, 1, 2 (Jan, Feb. 1966), 13-23, 25, 89-99f

Cited By

Bertsch ENederhof MSchmitz S(2013)On LR parsing with selective delaysProceedings of the 22nd international conference on Compiler Construction10.1007/978-3-642-37051-9_13(244-263)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-37051-9_13
Chen XPager DDesai BAbran AMudur S(2011)Full LR(1) parser generator Hyacc and study on the performance of LR(1) algorithmsProceedings of The Fourth International C* Conference on Computer Science and Software Engineering10.1145/1992896.1992907(83-92)Online publication date: 16-May-2011
https://dl.acm.org/doi/10.1145/1992896.1992907
Nijholt A(2005)Cover results and normal formsMathematical Foundations of Computer Science 197710.1007/3-540-08353-7_163(420-429)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08353-7_163
Show More Cited By

Index Terms

Transforming LR(k) Grammars to LR(1), SLR(1), and (1,1) Bounded Right-Context Grammars
1. Software and its engineering
  1. Software notations and tools
    1. Formal language definitions
2. Theory of computation
  1. Formal languages and automata theory
    1. Formalisms
      1. Rewrite systems
    2. Grammars and context-free languages

Recommendations

Simple LR(k) grammars

A class of context-free grammars, called the “Simple LR(k)” or SLR(k) grammars is defined. This class has been shown to include weak precedence and simple precedence grammars as proper subsets. How to construct parsers for the SLR(k) grammars is also ...
Noncanonical SLR(1) Grammars

Two noncanonical extensions of the simple LR(1) (SLR(1)) method are presented, which reduce not only handles but also other phrases of sentential forms. A class of context-free grammars called leftmost SLR(1) (LSLR(1)) is defined by using lookahead ...
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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 23, Issue 3

July 1976

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321958

Issue’s Table of Contents

Copyright © 1976 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 1976

Published in JACM Volume 23, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
1,025
Total Downloads

Downloads (Last 12 months)174
Downloads (Last 6 weeks)31

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bertsch ENederhof MSchmitz S(2013)On LR parsing with selective delaysProceedings of the 22nd international conference on Compiler Construction10.1007/978-3-642-37051-9_13(244-263)Online publication date: 16-Mar-2013
https://dl.acm.org/doi/10.1007/978-3-642-37051-9_13
Chen XPager DDesai BAbran AMudur S(2011)Full LR(1) parser generator Hyacc and study on the performance of LR(1) algorithmsProceedings of The Fourth International C* Conference on Computer Science and Software Engineering10.1145/1992896.1992907(83-92)Online publication date: 16-May-2011
https://dl.acm.org/doi/10.1145/1992896.1992907
Nijholt A(2005)Cover results and normal formsMathematical Foundations of Computer Science 197710.1007/3-540-08353-7_163(420-429)Online publication date: 24-May-2005
https://doi.org/10.1007/3-540-08353-7_163
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
Schneider V(1990)Compiler textbook bibliographies considered harmfulACM SIGPLAN Notices10.1145/87416.8745725:8(72-74)Online publication date: 1-Aug-1990
https://dl.acm.org/doi/10.1145/87416.87457
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: 1-May-1987
https://dl.acm.org/doi/10.1016/0304-3975%2887%2990082-X
Wyrostek P(1986)Precedence technique is not worse than SLR(1)Acta Informatica10.1007/BF0026786423:4(361-392)Online publication date: 1-Jul-1986
https://dl.acm.org/doi/10.1007/BF00267864
Liang YMiles E(1980)A parsing method on l-1 bounded context parsingProceedings of the 18th annual Southeast regional conference10.1145/503838.503850(88-97)Online publication date: 24-Mar-1980
https://dl.acm.org/doi/10.1145/503838.503850
Nijholt A(1980)A survey of normal form covers for context free grammarsActa Informatica10.1007/BF0026425714:3(271-294)Online publication date: 1-Sep-1980
https://dl.acm.org/doi/10.1007/BF00264257
Tai K(1979)Noncanonical SLR(1) GrammarsACM Transactions on Programming Languages and Systems10.1145/357073.3570831:2(295-320)Online publication date: 1-Oct-1979
https://dl.acm.org/doi/10.1145/357073.357083
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

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

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents