A Haskell Library for Adaptable Parsing Expression Grammars
Authors: 
Elton Máximo Cardoso, Rodrigo Geraldo Ribeiro, Leonardo Vieira dos Santos Reis, Marcos EmilianoAuthors Info & Claims
Pages 73 - 81
Abstract
Adaptable Parsing Expression Grammar (APEG) is a formal model for describing languages which provide a mechanism to extend its own syntax during the parsing process. In this work, we review the syntax and semantics of APEG and discuss the implementation of a Haskell library for building parsers for extensible languages. We also present an example of an APEG parser for a tiny extensible language.
References
[1]
Clement Blaudeau and Natarajan Shankar. 2020. A Verified Packrat Parser Interpreter for Parsing Expression Grammars. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (New Orleans, LA, USA) (CPP 2020). Association for Computing Machinery, New York, NY, USA, 15 pages. https://doi.org/10.1145/3372885.3373836
[2]
William J. Bowman. 2016. Growing a Proof Assistant. https://www.williamjbowman.com/resources/cur.pdf
[3]
Martin Bravenboer, Karl Trygve Kalleberg, Rob Vermaas, and Eelco Visser. 2008. Stratego/XT 0.17. A language and toolset for program transformation. Science of Computer Programming 72, 1 (2008), 52 – 70. https://doi.org/10.1016/j.scico.2007.11.003 Special Issue on Second issue of experimental software and toolkits (EST).
[4]
Janusz A. Brzozowski. 1964. Derivatives of regular expressions. JOURNAL OF THE ACM 11 (1964), 481–494.
[5]
Elton M. Cardoso, Rodrigo G. Ribeiro, Leonardo V. S. Reis, Mariza A. S. Bigonha, Roberto S. Bigonha, and Vladimir O. Di Iorio. 2019. An Attribute Language Definition for Adaptable Parsing Expression Grammars. In Proceedings of the 34th ACM/SIGAPP Symposium on Applied Computing (Limassol, Cyprus) (SAC’19). Association for Computing Machinery, New York, NY, USA, 1518–1525. https://doi.org/10.1145/3297280.3299738
[6]
Pierce Darragh and Michael D. Adams. 2020. Parsing with Zippers (Fuctional Pearl). Proceedings of the ACM on Programming Languages 4, ICFP (Aug. 2020), 108:1–108:30. https://doi.org/10.1145/3408990
[7]
Sergey Dmitriev. 2004. Language oriented programming: The next programming paradigm. JetBrains onBoard 1, 2 (2004), 1–13.
[8]
Romain Edelmann, Jad Hamza, and Viktor Kunčak. 2020. Zippy LL(1) Parsing with Derivatives. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, New York, NY, USA, 16 pages. https://doi.org/10.1145/3385412.3385992
[9]
Sebastian Erdweg, Stefan Fehrenbach, and Klaus Ostermann. 2014. Evolution of Software Systems with Extensible Languages and DSLs. IEEE Software 31, 5 (2014), 68–75.
[10]
Sebastian Erdweg, Tillmann Rendel, Christian Kästner, and Klaus Ostermann. 2011. SugarJ: library-based syntactic language extensibility. In Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applications (Portland, Oregon, USA) (OOPSLA’11). ACM, New York, NY, USA, 391–406.
[11]
Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, Shriram Krishnamurthi, Eli Barzilay, Jay A. McCarthy, and Sam Tobin-Hochstadt. 2015. The Racket Manifesto. In 1st Summit on Advances in Programming Languages, SNAPL 2015, May 3-6, 2015, Asilomar, California, USA(LIPIcs, Vol. 32), Thomas Ball, Rastislav Bodík, Shriram Krishnamurthi, Benjamin S. Lerner, and Greg Morrisett (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 113–128. https://doi.org/10.4230/LIPIcs.SNAPL.2015.113
[12]
Robert Bruce Findler and Matthew Flatt. 2004. Slideshow: functional presentations. In Proceedings of the Ninth ACM SIGPLAN International Conference on Functional Programming, ICFP 2004, Snow Bird, UT, USA, September 19-21, 2004, Chris Okasaki and Kathleen Fisher (Eds.). ACM, 224–235. https://doi.org/10.1145/1016850.1016880
[13]
Matthew Flatt, Eli Barzilay, and Robert Bruce Findler. 2009. Scribble: closing the book on ad hoc documentation tools. In Proceeding of the 14th ACM SIGPLAN international conference on Functional programming, ICFP 2009, Edinburgh, Scotland, UK, August 31 - September 2, 2009, Graham Hutton and Andrew P. Tolmach (Eds.). ACM, 109–120. https://doi.org/10.1145/1596550.1596569
[14]
Bryan Ford. 2004. Parsing Expression Grammars: A Recognition-based Syntactic Foundation. In Proceedings of the 31st Symposium on Principles of Programming Languages (Venice, Italy) (POPL’04). ACM, New York, NY, USA, 111–122.
[15]
Andy Gill. 2004. Monad transformer library. Retrieved 2021-07-01 from https://hackage.haskell.org/package/mtl
[16]
Grzegorz Herman. 2020. Faster General Parsing through Context-Free Memoization. In Proceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation (London, UK) (PLDI 2020). Association for Computing Machinery, New York, NY, USA, 14 pages. https://doi.org/10.1145/3385412.3386032
[17]
Gérard P. Huet. 1997. The Zipper. J. Funct. Program. 7, 5 (1997), 549–554. http://journals.cambridge.org/action/displayAbstract?aid=44121
[18]
Lennart C.L. Kats and Eelco Visser. 2010. The Spoofax Language Workbench: Rules for Declarative Specification of Languages and IDEs. In Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications (Reno/Tahoe, Nevada, USA) (OOPSLA 10). Association for Computing Machinery, New York, NY, USA, 20 pages. https://doi.org/10.1145/1869459.1869497
[19]
Casey Klein, John Clements, Christos Dimoulas, Carl Eastlund, Matthias Felleisen, Matthew Flatt, Jay A. McCarthy, Jon Rafkind, Sam Tobin-Hochstadt, and Robert Bruce Findler. 2012. Run your research: on the effectiveness of lightweight mechanization. In Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2012, Philadelphia, Pennsylvania, USA, January 22-28, 2012, John Field and Michael Hicks (Eds.). ACM, 285–296. https://doi.org/10.1145/2103656.2103691
[20]
Yannis Lilis and Anthony Savidis. 2019. A Survey of Metaprogramming Languages. ACM Comput. Surv. 52, 6, Article 113 (Oct. 2019), 39 pages. https://doi.org/10.1145/3354584
[21]
Geoffrey Mainland. 2007. Why Its Nice to Be Quoted: Quasiquoting for Haskell. In Proceedings of the ACM SIGPLAN Workshop on Haskell Workshop (Freiburg, Germany) (Haskell 07). Association for Computing Machinery, New York, NY, USA, 10 pages. https://doi.org/10.1145/1291201.1291211
[22]
Leonardo V.S. Reis, Roberto S. Bigonha, Vladimir O. Di Iorio, and Luis Eduardo S. Amorim. 2012. Adaptable Parsing Expression Grammars. In Programming Languages, Francisco Heron Carvalho Junior and Luis Soares Barbosa (Eds.). Lecture Notes in Computer Science, Vol. 7554. Springer Berlin Heidelberg, 72–86.
[23]
Leonardo V.S. Reis, Roberto S. Bigonha, Vladimir O. Di Iorio, and Luis Eduardo S. Amorim. 2014. The formalization and implementation of Adaptable Parsing Expression Grammars. Science of Computer Programming 96, Part 2 (2014), 191 – 210. Selected and extended papers of the SBLP 2012.
[24]
Tim Sheard and Simon Peyton Jones. 2002. Template Meta-Programming for Haskell. SIGPLAN Not. 37, 12 (Dec. 2002), 16 pages. https://doi.org/10.1145/636517.636528
[25]
Michael Snoyman. 2012. Developing Web Applications with Haskell and Yesod. O’Reilly Media, Inc.
[26]
Sam Tobin-Hochstadt, Vincent St-Amour, Ryan Culpepper, Matthew Flatt, and Matthias Felleisen. 2011. Languages as libraries. In Proceedings of the 32nd ACM SIGPLAN conference on Programming language design and implementation (San Jose, California, USA) (PLDI’11). ACM, New York, NY, USA, 132–141.
[27]
Martin P Ward. 1994. Language-oriented programming. Software-Concepts and Tools 15, 4 (1994), 147–161.
Recommendations
Parsing expression grammars made practical
SLE 2015: Proceedings of the 2015 ACM SIGPLAN International Conference on Software Language EngineeringParsing Expression Grammars (PEGs) define languages by specifying a recursive-descent parser that recognises them. The PEG formalism exhibits desirable properties, such as closure under composition, built-in disambiguation, unification of syntactic and ...
Parsing expression grammars: a recognition-based syntactic foundation
POPL '04For decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...
Parsing expression grammars: a recognition-based syntactic foundation
POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languagesFor decades we have been using Chomsky's generative system of grammars, particularly context-free grammars (CFGs) and regular expressions (REs), to express the syntax of programming languages and protocols. The power of generative grammars to express ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2023
110 pages
ISBN:9798400716287
DOI:10.1145/3624309
Copyright © 2023 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 the author(s) 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: 02 November 2023
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- FAPEMIG
Conference
SBLP 2023
SBLP 2023: XXVII Brazilian Symposium on Programming Languages
September 25 - 29, 2023
Campo Grande, MS, Brazil
Acceptance Rates
Overall Acceptance Rate 22 of 50 submissions, 44%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 23Total Downloads
- Downloads (Last 12 months)18
- Downloads (Last 6 weeks)1
Reflects downloads up to 13 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format