article

Free access

Regular right part grammars and their parsers

Author:

Wilf R. LaLondeAuthors Info & Claims

Communications of the ACM, Volume 20, Issue 10

Pages 731 - 741

https://doi.org/10.1145/359842.359853

Published: 01 October 1977 Publication History

PDF eReader

Abstract

This paper introduces an alternative to context-free grammars called regular right part (RRP) grammars, which resemble PASCAL syntax diagrams. Formally, RRP grammars have production right parts, which are nondeterministic finite state machines (FSMs), and, as a special case, regular expression, since these can be converted to FSMs. RRP grammars describe the syntax of programming languages more concisely and more understandably than is possible with CF grammars. Also introduced is a class of parsers, RRP LR(m, k) parsers, which includes the CF LR(k) parsers and provides the same advantages. Informally, an RRP LR(m, k) parser can determine the right end of each handle by considering at most k symbols to the right of the handle and the left end, after the right end has been found, by considering at most m symbols to the left of the handle. A mechanism for determining the left end is required because there is no bound on the length of the handle.

References

[1]

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

Digital Library

Google Scholar

[2]

DeRemer, F.L., and LaLonde, W.R. A proposal to develop and implement an advanced translator writing system. U. of California, Santa Cruz, Calif., 1971-75.

Google Scholar

[3]

DeRemer, F.L. Extended LR(k) grammars and their parsers, U. of California, Santa Cruz, Calif., 1970.

Google Scholar

[4]

Earley, J. An efficient context free parsing algorithm. Ph.D. Th., Carnegie-Mellon U., Pittsburgh, Pa., 1968; also Comm. ACM 13, 2 (Feb. 1970), 94-102.

Digital Library

Google Scholar

[5]

Floyd, R. A grammatical description of AlgolW. In Sites, R.L., Tech. Rept. STAN-CS-71-230, Comptr. Sci. Dept., Stanford U., Stanford, Calif., 1972, pp. 128-139.

Google Scholar

[6]

Gries, D. Compiler Construction for Digital Computers. Wiley, New York, 1971.

Digital Library

Google Scholar

[7]

Jensen, K., and Wirth, N. PASCAL User Manual and Report. Springer-Verlag, New York, Second Ed., 1975.

Digital Library

Google Scholar

[8]

Knuth, D.E. On the translation of languages from left to right. Inform. Contr. 8 (Oct. 1965), 607-639.

Crossref

Google Scholar

[9]

LaLonde, W.R. Practical LR analysis of regular right part grammars. Ph.D. Th., U. of Waterloo, Waterloo, Ont., Oct. 1975.

Digital Library

Google Scholar

[10]

Woods, W.A. Transition network grammars for natural language analysis. Comm. ACM 13, 10 (Oct. 1970), 591-606.

Digital Library

Google Scholar

Cited By

View all

Steimann FFreitag MFischer BBurgueño LCazzola W(2022)The Semantics of PluralsProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3567512.3567516(36-54)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3567512.3567516
Chiang DDrewes FGildea DLopez ASatta G(2018)Weighted dag automata for semantic graphsComputational Linguistics10.1162/COLI_a_0030944:1(119-186)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1162/COLI_a_00309
Breveglieri LCrespi Reghizzi SGoldwurm M(2010)Efficient recognition of trace languages defined by repeat-until loopsInformation and Computation10.1016/j.ic.2010.03.001208:8(969-981)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.ic.2010.03.001
Show More Cited By

Regular right part grammars and their parsers
1. Software and its engineering
  1. Software notations and tools
2. Theory of computation
  1. Formal languages and automata theory

Recommendations

Generating parsers for affix grammars

Affix grammars are two-level grammars which are similar to van Wijngaarden's two-level grammars used in the definition of Algol 68. Affix grammars are shown by Koster to be equal in power to van Wijngaarden grammars. They are much more suited to parsing ...
Constructing LR parsers for regular right part grammars

Regular right part (RRP) grammars differ from context free (CF) grammars by virtue of the fact that the production right parts are nondeterministic finite automatons (FAs). LR(k) parsers for RRP grammars are linear time parsers which can determine the ...
The restriction language for computer grammars of natural language

Over the past few years, a number of systems for the computer analysis of natural language sentences have been based on augmented context-free grammars: a context-free grammar which defines a set of parse trees for a sentence, plus a group of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Communications of the ACM Volume 20, Issue 10

Oct. 1977

93 pages

ISSN:0001-0782

EISSN:1557-7317

DOI:10.1145/359842

Editor:
Robert L. Ashenhurst
Univ. of Chicago, Chicago, IL

Issue’s Table of Contents

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 1977

Published in CACM Volume 20, Issue 10

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
626
Total Downloads

Downloads (Last 12 months)100
Downloads (Last 6 weeks)22

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Steimann FFreitag MFischer BBurgueño LCazzola W(2022)The Semantics of PluralsProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3567512.3567516(36-54)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3567512.3567516
Chiang DDrewes FGildea DLopez ASatta G(2018)Weighted dag automata for semantic graphsComputational Linguistics10.1162/COLI_a_0030944:1(119-186)Online publication date: 1-Mar-2018
https://dl.acm.org/doi/10.1162/COLI_a_00309
Breveglieri LCrespi Reghizzi SGoldwurm M(2010)Efficient recognition of trace languages defined by repeat-until loopsInformation and Computation10.1016/j.ic.2010.03.001208:8(969-981)Online publication date: 1-Aug-2010
https://dl.acm.org/doi/10.1016/j.ic.2010.03.001
Hemerik K(2009)Towards a Taxonomy for ECFG and RRPG ParsingProceedings of the 3rd International Conference on Language and Automata Theory and Applications10.1007/978-3-642-00982-2_35(410-421)Online publication date: 31-Mar-2009
https://dl.acm.org/doi/10.1007/978-3-642-00982-2_35
Thiemann PNeubauer MAntoy SAlbert E(2008)Macros for context-free grammarsProceedings of the 10th international ACM SIGPLAN conference on Principles and practice of declarative programming10.1145/1389449.1389465(120-130)Online publication date: 15-Jul-2008
https://dl.acm.org/doi/10.1145/1389449.1389465
Brüggemann-Klein AWood D(2005)Deterministic regular languagesSTACS 9210.1007/3-540-55210-3_182(173-184)Online publication date: 2-Jun-2005
https://doi.org/10.1007/3-540-55210-3_182
Brüggemann-Klein AWood D(2003)On predictive parsing and extended context-free grammarsComputer Science in Perspective10.5555/865449.865456(69-87)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.5555/865449.865456
Leonard EHeitmeyer C(2003)Program Synthesis from Formal Requirements Specifications Using APTSHigher-Order and Symbolic Computation10.1023/A:102307210455316:1-2(63-92)Online publication date: 1-Mar-2003
https://dl.acm.org/doi/10.1023/A%3A1023072104553
Brüggemann-Klein AWood D(2003)On Predictive Parsing and Extended Context-Free GrammarsImplementation and Application of Automata10.1007/3-540-44977-9_24(239-247)Online publication date: 24-Jun-2003
https://doi.org/10.1007/3-540-44977-9_24
Brüggemann-Klein AWood D(2003)On Predictive Parsing and Extended Context-Free GrammarsComputer Science in Perspective10.1007/3-540-36477-3_6(69-87)Online publication date: 28-Feb-2003
https://doi.org/10.1007/3-540-36477-3_6
Show More Cited By

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.

Abstract

References

Cited By

Recommendations

Generating parsers for affix grammars

Constructing LR parsers for regular right part grammars

The restriction language for computer grammars of natural language

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations