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

Article

Free access

On directly constructing LR(k) parsers without chain reductions

Author:

Wilf R. LaLondeAuthors Info & Claims

POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages

Pages 127 - 133

https://doi.org/10.1145/800168.811546

Published: 01 January 1976 Publication History

Abstract

A chain production is a production of the form A→M where A is a nonterminal and M is either a terminal or nonterminal. Pager in [Pag5] has presented an algorithm which removes all chain reductions from LR(1) parsers after they have been constructed.

In this paper, we present an algorithm for directly constructing LR(k) parsers with arbitrary subsets of the chain productions, called the useless chain productions, optimized out. If this subset is empty, the algorithm is a standard one [And 1, Kn]. If this subset consists of all chain productions, the result is a parser with all chain reductions optimized away. The algorithm, as in [Pag5], also eliminates from the parsers all nonterminals which occur as the left part of useless chain productions. This latter optimization along with the chain reduction optimization significantly decreases the storage space and execution times of the parsers.

This provides an efficient solution of the open problem posed by Aho and Ullman [A&U2] for all LR(k) grammars.

References

[1]

A.V. Aho and J.D. Ullman, The Theory of Parsing, Translation, and Compiling. Prentice-Hall, Englewood Cliffs, N.J., 1973

Digital Library

[2]

A.V. Aho and J.D. Ullman, "Optimization of LR(k) Parsers", J. Computer and System Sciences, Vol. 6, Dec 72, pp. 573-602.

Digital Library

[3]

A.V. Aho and J.D. Ullman, "A Technique for Speeding Up LR(k) Parsers", Siam J. Comp., Vol 2, June 73, pp. 106-127.

[4]

T. Anderson, "Syntactical Analysis of LR(k) Languages", Ph.D. Thesis, Univ. of Newcastle Upon Tyne, Computing Lab.

[5]

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

Digital Library

[6]

F.L. DeRemer, "Practical Translators for LR(k) Languages", Tech. Report MAC TR-65, Project MAC, Mass. Inst. of Tech., Cambridge, Oct 69.

Digital Library

[7]

F.L. DeRemer, "Simple LR(k) Grammars", CACM, Vol. 14, July 71, pp. 453-460.

Digital Library

[8]

J. Earley, "An Efficient Context-Free Parsing Algorithm", Ph.D. Thesis, Carnegie-Mellon Univ., Pittsburgh, PA. also see CACM 13:2, Feb 70, pp. 94-102.

Digital Library

[9]

M.L. Joliat, "On The Reduced Matrix Representation of LR(k) Parser Tables", Tech. Report CSRG-28, Computer Systems Research Group, Univ. of Toronto, Oct 73.

[10]

D.E. Knuth, "On the Translation of Languages from Left to Right", Inf. Contr. vol. 8, Oct 65, pp. 607-639.

[11]

A.J. Korenjak, "A Practical Method for Constructing LR(k) Processors", CACM, Vol. 12, Nov 69, pp. 613-623.

Digital Library

[12]

W.R. LaLonde, "An Efficient LALR Parser Generator", Tech. Report CSRG-2, Computer Systems Research Group, Univ. of Toronto, Toronto, 1971.

[13]

D. pager, "A Solution to an Open Problem by Knuth", Inf. Contr., Vol. 17, Dec 70, pp. 4 62-473.

[14]

D. Pager, On Combining Compatible States in LR(k) Parsing", Tech. Report PE 257, Information Sciences Program, Univ. of Hawaii, Honolulu, July 72.

[15]

D. Pager, "A Compaction Algorithm for Combining the Symbol-action Lists of an LR(k) Parser", Tech. Report PE 259, Univ. of Hawaii, July 72.

[16]

D. Pager, On the Decremental Approach to Left-to-right Parsers", to appear in Siam J. Computing.

[17]

D. Pager, On Eliminating Unit/Productions from LR(k) Parsers", Tech. Report from the Information Sciences Program, Univ. of Hawaii, Honolulu.

Cited By

Sippu SSoisalon-Soininen E(2005)On constructing LL(k) parsersAutomata, Languages and Programming10.1007/3-540-09510-1_47(585-595)Online publication date: 25-May-2005
https://doi.org/10.1007/3-540-09510-1_47
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
Fenchel REstrin G(1982)Self-Descrbing Systems Using Integral HelpIEEE Transactions on Systems, Man, and Cybernetics10.1109/TSMC.1982.430880012:2(162-167)Online publication date: 1982
https://doi.org/10.1109/TSMC.1982.4308800
Show More Cited By

Index Terms

On directly constructing LR(k) parsers without chain reductions
1. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages
  2. Semantics and reasoning
    1. Program reasoning
      1. Parsing

Recommendations

Elimination of single productions from LR parsers in conjunction with the use of default reductions
POPL '77: Proceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages

One of the most attractive techniques in optimizing LR parsers is to eliminate reductions by semantically insignificant productions of the form A → X (single productions), where X is a nonterminal or a terminal; such a modification can lead to substantial ...
LR parsers for natural languages
ACL '84/COLING '84: Proceedings of the 10th International Conference on Computational Linguistics and 22nd annual meeting on Association for Computational Linguistics

MLR, an extended LR parser, is introduced, and its application to natural language parsing is discussed. An LR parser is a shift-reduce parser which is deterministically guided by a parsing table. A parsing table can be obtained automatically from a ...
On different LL and LR parsers used in LLLR parsing

The LLLR parser can be constructed for any LR grammar.The LLLR parser produces the left parse of the input string without backtracking.The canonical LL or the LALL parser can be used as the backbone parser.Small canonical or LALR parsers are used for LL ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

POPL '76: Proceedings of the 3rd ACM SIGACT-SIGPLAN symposium on Principles on programming languages

January 1976

224 pages

ISBN:9781450374774

DOI:10.1145/800168

Copyright © 1976 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1976

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Acceptance Rates

POPL '76 Paper Acceptance Rate 20 of 90 submissions, 22%;

Overall Acceptance Rate 824 of 4,130 submissions, 20%

Upcoming Conference

POPL '25

Sponsor:
sigplan

The 52nd Annual ACM SIGPLAN Symposium on Principles of Programming Languages

January 19 - 25, 2025

Denver , CO , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
346
Total Downloads

Downloads (Last 12 months)27
Downloads (Last 6 weeks)4

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Sippu SSoisalon-Soininen E(2005)On constructing LL(k) parsersAutomata, Languages and Programming10.1007/3-540-09510-1_47(585-595)Online publication date: 25-May-2005
https://doi.org/10.1007/3-540-09510-1_47
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
Fenchel REstrin G(1982)Self-Descrbing Systems Using Integral HelpIEEE Transactions on Systems, Man, and Cybernetics10.1109/TSMC.1982.430880012:2(162-167)Online publication date: 1982
https://doi.org/10.1109/TSMC.1982.4308800
Tokuda T(1981)Eliminating unit reductions from LR(k) parsers using minimum contextsActa Informatica10.1007/BF0026453815:4(447-470)Online publication date: 1-Aug-1981
https://dl.acm.org/doi/10.1007/BF00264538
Soisalon-Soininen E(1980)On the space optimizing effect of eliminating single productions from LR parsersActa Informatica10.1007/BF0028854214:2(157-174)Online publication date: 1-Aug-1980
https://dl.acm.org/doi/10.1007/BF00288542
Soisalon-Soininen EGraham RHarrison MSethi R(1977)Elimination of single productions from LR parsers in conjunction with the use of default reductionsProceedings of the 4th ACM SIGACT-SIGPLAN symposium on Principles of programming languages10.1145/512950.512967(183-193)Online publication date: 1-Jan-1977
https://dl.acm.org/doi/10.1145/512950.512967

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 Publication

Media

Figures

Other

Tables

View Table of Contents