research-article

Open access

Restricting grammars with tree automata

Authors:

Michael D. Adams,

Matthew MightAuthors Info & Claims

Proceedings of the ACM on Programming Languages, Volume 1, Issue OOPSLA

Article No.: 82, Pages 1 - 25

https://doi.org/10.1145/3133906

Published: 12 October 2017 Publication History

PDF eReader

Abstract

Precedence and associativity declarations in systems like yacc resolve ambiguities in context-free grammars (CFGs) by specifying restrictions on allowed parses. However, they are special purpose and do not handle the grammatical restrictions that language designers need in order to resolve ambiguities like dangling else, the interactions between binary operators and functional if expressions in ML, and the interactions between object allocation and function calls in JavaScript. Often, language designers resort to restructuring their grammars in order to encode these restrictions, but this obfuscates the designer's intent and can make grammars more difficult to read, write, and maintain.

In this paper, we show how tree automata can modularly and concisely encode such restrictions. We do this by reinterpreting CFGs as tree automata and then intersecting them with tree automata encoding the desired restrictions. The results are then reinterpreted back into CFGs that encode the specified restrictions. This process can be used as a preprocessing step before other CFG manipulations and is well behaved. It performs well in practice and never introduces ambiguities or LR(k) conflicts.

References

[1]

Ali Afroozeh, Mark van den Brand, Adrian Johnstone, Elizabeth Scott, and Jurgen Vinju. Safe Specification of Operator Precedence Rules, pages 137–156. Springer, Cham, 2013. ISBN 978-3-319-02654-1.

Crossref

Google Scholar

[2]

Hubert Comon, Max Dauchet, Rémi Gilleron, Florent Jacquemard, Denis Lugiez, Christof Löding, Sophie Tison, and Marc Tommasi. Tree automata techniques and applications, October 2007. URL http://www.grappa.univ- lille3.fr/tata .

Google Scholar

[3]

ECMA 2011. Standard ECMA-262: ECMAScript Language Specification. Ecma International, 5.1 edition, June 2011. URL http://www.ecma- international.org/publications/files/ECMA- ST/Ecma- 262.pdf .

Google Scholar

[4]

ISO/IEC 9899:TC3: Programming languages – C. ISO/IEC JTC1/SC22/WG14, September 2007. URL http://www.open- std.org/ JTC1/SC22/WG14/www/docs/n1124.pdf .

Google Scholar

[5]

Nils Klarlund, Niels Damgaard, and Michael I. Schwartzbach. Yakyak: parsing with logical side constraints. In Grzegorz Rozenberg and Wolfgang Thomas, editors, Developments in Language Theory, Foundations, Applications, and Perspectives, Aachen, Germany, 6-9 July 1999, pages 286–301. World Scientific, 1999. ISBN 981-02-4380-4.

Google Scholar

[6]

Paul Klint and Eelco Visser. Using filters for the disambiguation of context-free grammars. Technical Report P9426, University of Amsterdam, December 1994.

Google Scholar

[7]

Donald E. Knuth. On the translation of languages from left to right. Information and Control, 8(6):607–639, December 1965. ISSN 0019-9958. 9958(65)90426- 2.

Crossref

Google Scholar

[8]

Bernard Lang. Deterministic techniques for efficient non-deterministic parsers, pages 255–269. Springer, Berlin, Heidelberg, 1974. ISBN 978-3-540-37778-8. 540- 06841- 4_65.

Crossref

Google Scholar

[9]

Mikkel Thorup. Controlled grammatic ambiguity. ACM Transactions on Programming Languages and Systems (TOPLAS), 16 (3):1024–1050, May 1994. ISSN 0164-0925.

Digital Library

Google Scholar

[10]

Mikkel Thorup. Disambiguating grammars by exclusion of sub-parse trees. Acta Informatica, 33(5):511–522, August 1996. ISSN 0001-5903 (Print) 1432-0525 (Online).

Digital Library

Google Scholar

[11]

Mark G. J. van den Brand, Jeroen Scheerder, Jurgen J. Vinju, and Eelco Visser. Disambiguation Filters for Scannerless Generalized LR Parsers, pages 143–158. Springer, Berlin, Heidelberg, 2002. ISBN 978-3-540-45937-8.

Crossref

Google Scholar

[12]

Eelco Visser. Syntax Definition for Language Prototyping. PhD thesis, University of Amsterdam, 1997.

Google Scholar

[13]

R. M. Wharton. Resolution of ambiguity in parsing. Acta Informatica, 6(4):387–395, December 1976. ISSN 0001-5903 (Print) 1432-0525 (Online).

Digital Library

Google Scholar

Cited By

View all

Gissurarson MRoque DKoppel J(2023)Spectacular: Finding Laws from 25 Trillion Terms2023 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST57152.2023.00035(293-304)Online publication date: Apr-2023
https://doi.org/10.1109/ICST57152.2023.00035
Koppel JGuo Zde Vries ESolar-Lezama APolikarpova N(2022)Searching entangled program spacesProceedings of the ACM on Programming Languages10.1145/35476226:ICFP(23-51)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547622
Lee YRoychoudhury ACadar CKim M(2022)Improving IDE code inspections with tree automataProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3559081(1814-1815)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3559081

Index Terms

Restricting grammars with tree automata
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Parsers
      2. Translator writing systems and compiler generators
    2. Formal language definitions
      1. Syntax
2. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages
    2. Tree languages

Recommendations

Deterministic parsing of ambiguous grammars

Methods of describing the syntax of programming languages in ways that are more flexible and natural than conventional BNF descriptions are considered. These methods involve the use of ambiguous context-free grammars together with rules to resolve ...
Semantics and algorithms for data-dependent grammars
POPL '10: Proceedings of the 37th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages

We present the design and theory of a new parsing engine, YAKKER, capable of satisfying the many needs of modern programmers and modern data processing applications. In particular, our new parsing engine handles (1) full scannerless context-free ...
Semantics and algorithms for data-dependent grammars
POPL '10

We present the design and theory of a new parsing engine, YAKKER, capable of satisfying the many needs of modern programmers and modern data processing applications. In particular, our new parsing engine handles (1) full scannerless context-free ...

Comments

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Programming Languages

Proceedings of the ACM on Programming Languages Volume 1, Issue OOPSLA

October 2017

1786 pages

EISSN:2475-1421

DOI:10.1145/3152284

Issue’s Table of Contents

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 October 2017

Published in PACMPL Volume 1, Issue OOPSLA

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Defense Advanced Research Projects Agency

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
1,116
Total Downloads

Downloads (Last 12 months)187
Downloads (Last 6 weeks)26

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Gissurarson MRoque DKoppel J(2023)Spectacular: Finding Laws from 25 Trillion Terms2023 IEEE Conference on Software Testing, Verification and Validation (ICST)10.1109/ICST57152.2023.00035(293-304)Online publication date: Apr-2023
https://doi.org/10.1109/ICST57152.2023.00035
Koppel JGuo Zde Vries ESolar-Lezama APolikarpova N(2022)Searching entangled program spacesProceedings of the ACM on Programming Languages10.1145/35476226:ICFP(23-51)Online publication date: 31-Aug-2022
https://dl.acm.org/doi/10.1145/3547622
Lee YRoychoudhury ACadar CKim M(2022)Improving IDE code inspections with tree automataProceedings of the 30th ACM Joint European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3540250.3559081(1814-1815)Online publication date: 7-Nov-2022
https://dl.acm.org/doi/10.1145/3540250.3559081

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

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

Index Terms

Recommendations

Deterministic parsing of ambiguous grammars

Semantics and algorithms for data-dependent grammars

Semantics and algorithms for data-dependent grammars

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Funding Sources

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations