research-article

Packrat parsers can support left recursion

Authors:

Alessandro Warth,

James R. Douglass,

Todd MillsteinAuthors Info & Claims

PEPM '08: Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

Pages 103 - 110

https://doi.org/10.1145/1328408.1328424

Published: 07 January 2008 Publication History

Get Access

Abstract

Packrat parsing offers several advantages over other parsing techniques, such as the guarantee of linear parse times while supporting backtracking and unlimited look-ahead. Unfortunately, the limited support for left recursion in packrat parser implementations makes them difficult to use for a large class of grammars (Java's, for example). This paper presents a modification to the memoization mechanism used by packrat parser implementations that makes it possible for them to support (even indirectly or mutually) left-recursive rules. While it is possible for a packrat parser with our modification to yield super-linear parse times for some left-recursive grammars, our experimentsshow that this is not the case for typical uses of left recursion.

References

[1]

Bryan Ford. Packrat Parsing: a practical linear-time algorithm with backtracking. Master's thesis, Massachusetts Institute of Technology, September 2002.

Google Scholar

[2]

Bryan Ford. Packrat Parsing: Simple, Powerful, Lazy, Linear Time (functional pearl). In ICFP '02: Proceedings of the seventh ACM SIGPLAN International Conference on Functional Programming, pages 36--47, New York, NY, USA, 2002. ACM Press.

Digital Library

Google Scholar

[3]

Bryan Ford. Parsing Expression Grammars: a Recognition-Based Syntactic Foundation. In POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of Programming Languages, pages 111--122, New York, NY, USA, 2004. ACM Press.

Digital Library

Google Scholar

[4]

Richard A. Frost and Rahmatullah Hafiz. A new top-down parsing algorithm to accommodate ambiguity and left recursion in polynomial time. SIGPLAN Notices, 41(5):46--54, 2006.

Digital Library

Google Scholar

[5]

James Gosling, Bill Joy, Guy Steele, and Gilad Bracha. The Java Language Specification, Third Edition. Addison-Wesley, 2005.

Digital Library

Google Scholar

[6]

Robert Grimm. Better Extensibility Through Modular Syntax. In PLDI '06: Proceedings of the 2006 ACM SIGPLAN conference on Programming Language Design and Implementation, pages 38--51, New York, NY, USA, 2006. ACM Press.

Digital Library

Google Scholar

[7]

Mark Johnson. Memoization in top-down parsing. Computational Linguistics, 21(3):405--417, 1995.

Digital Library

Google Scholar

[8]

Roman Redziejowski. Parsing Expression Grammar as a primitive recursive-descent parser with backtracking. In G. Lindemann and H. Schlingloff, editors, Proceedings of the CS&P'2006 Workshop, volume 3 of Informatik-Bericht Nr. 206, pages 304--315. Humboldt-Universitäät zu Berlin, 2006. To appear in Fundamenta Informaticae.

Google Scholar

[9]

Eric Van Wyk and August Schwerdfeger. Context-Aware Scanning for Parsing Extensible Languages. In Intl. Conf. on Generative Programming and Component Engineering, GPCE 2007. ACM Press, October 2007.

Digital Library

Google Scholar

[10]

Eelco Visser. Scannerless Generalized-LR Parsing. Technical Report P9707, Programming Research Group, University of Amsterdam.

Google Scholar

[11]

Alessandro Warth and Ian Piumarta. OMeta: an Object-Oriented Language for Pattern-Matching. In OOPSLA '07: Companion to the 22nd ACM SIGPLAN conference on Object-Oriented Programming Systems, Languages, and Applications, New York, NY, USA, 2007. ACM Press.

Digital Library

Google Scholar

Cited By

View all

van der Merwe B(2023)Ordered Context-Free Grammars RevisitedElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.388.13388(140-153)Online publication date: 15-Sep-2023
https://doi.org/10.4204/EPTCS.388.13
M. Cardoso EDe Paula RPereira DReis LRibeiro RHong JLanperne MPark JCerny TShahriar H(2023)Type-based Termination Analysis for Parsing Expression GrammarsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577620(1372-1379)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577620
Purve SGogte PBhave R(2023)Stack and Queue Based Parser Approach for Parsing Expression Grammar2023 11th International Conference on Emerging Trends in Engineering & Technology - Signal and Information Processing (ICETET - SIP)10.1109/ICETET-SIP58143.2023.10151539(1-6)Online publication date: 28-Apr-2023
https://doi.org/10.1109/ICETET-SIP58143.2023.10151539
Show More Cited By

Index Terms

Packrat parsers can support left recursion
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
      1. Parsers

Recommendations

Incremental packrat parsing
SLE 2017: Proceedings of the 10th ACM SIGPLAN International Conference on Software Language Engineering

Packrat parsing is a popular technique for implementing top-down, unlimited-lookahead parsers that operate in guaranteed linear time. In this paper, we describe a method for turning a standard packrat parser into an incremental parser through a simple ...
Parsing expression grammars: a recognition-based syntactic foundation
POPL '04: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on Principles of programming languages

For 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 ...
Packrat parsers can handle practical grammars in mostly constant space
PASTE '10: Proceedings of the 9th ACM SIGPLAN-SIGSOFT workshop on Program analysis for software tools and engineering

Packrat parsing is a powerful parsing algorithm presented by Ford in 2002. Packrat parsers can handle complicated grammars and recursive structures in lexical elements more easily than the traditional LL(k) or LR(1) parsing algorithms. However, packrat ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PEPM '08: Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation

January 2008

214 pages

ISBN:9781595939777

DOI:10.1145/1328408

General Chair:
John Hatcliff
Kansas State University, USA
,
Program Chairs:
Robert Glück
University of Copenhagen, Denmark
,
Oege de Moor
Oxford University, UK

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: 07 January 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PEPM08

Sponsor:

PEPM08: Partial Evaluation and Program Manipulation

January 7 - 8, 2008

California, San Francisco, USA

Acceptance Rates

Overall Acceptance Rate 31 of 49 submissions, 63%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

37
Total Citations
View Citations
680
Total Downloads

Downloads (Last 12 months)33
Downloads (Last 6 weeks)3

Reflects downloads up to 22 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

van der Merwe B(2023)Ordered Context-Free Grammars RevisitedElectronic Proceedings in Theoretical Computer Science10.4204/EPTCS.388.13388(140-153)Online publication date: 15-Sep-2023
https://doi.org/10.4204/EPTCS.388.13
M. Cardoso EDe Paula RPereira DReis LRibeiro RHong JLanperne MPark JCerny TShahriar H(2023)Type-based Termination Analysis for Parsing Expression GrammarsProceedings of the 38th ACM/SIGAPP Symposium on Applied Computing10.1145/3555776.3577620(1372-1379)Online publication date: 27-Mar-2023
https://dl.acm.org/doi/10.1145/3555776.3577620
Purve SGogte PBhave R(2023)Stack and Queue Based Parser Approach for Parsing Expression Grammar2023 11th International Conference on Emerging Trends in Engineering & Technology - Signal and Information Processing (ICETET - SIP)10.1109/ICETET-SIP58143.2023.10151539(1-6)Online publication date: 28-Apr-2023
https://doi.org/10.1109/ICETET-SIP58143.2023.10151539
Redziejowski R(2023)Left Recursion by Recursive AscentConcurrency, Specification and Programming10.1007/978-3-031-26651-5_2(29-46)Online publication date: 5-May-2023
https://doi.org/10.1007/978-3-031-26651-5_2
Beckmann TRein PMattis THirschfeld RFischer BBurgueño LCazzola W(2022)Partial Parsing for Structured EditorsProceedings of the 15th ACM SIGPLAN International Conference on Software Language Engineering10.1145/3567512.3567522(110-120)Online publication date: 29-Nov-2022
https://dl.acm.org/doi/10.1145/3567512.3567522
Cardoso EPereira DDe Paula RReis LRibeiro R(2022)A Type-Directed Algorithm to Generate Random Well-Formed Parsing Expression GrammarsProceedings of the XXVI Brazilian Symposium on Programming Languages10.1145/3561320.3561326(8-14)Online publication date: 6-Oct-2022
https://dl.acm.org/doi/10.1145/3561320.3561326
Mangrulkar NSingh KRaghuwanshi M(2022)Parsing Expression Grammar and Packrat Parsing—A ReviewInformation and Communication Technology for Competitive Strategies (ICTCS 2021)10.1007/978-981-19-0095-2_36(377-384)Online publication date: 23-Jun-2022
https://doi.org/10.1007/978-981-19-0095-2_36
van der Merwe BBerglund M(2022)Ordered Context-Free GrammarsImplementation and Application of Automata10.1007/978-3-031-07469-1_4(53-66)Online publication date: 28-Jun-2022
https://dl.acm.org/doi/10.1007/978-3-031-07469-1_4
Dejanović I(2021)Parglare: A LR/GLR parser for PythonScience of Computer Programming10.1016/j.scico.2021.102734(102734)Online publication date: Oct-2021
https://doi.org/10.1016/j.scico.2021.102734
Park JPark JAn SRyu SGrundy JLe Goues CLo D(2020)JISETProceedings of the 35th IEEE/ACM International Conference on Automated Software Engineering10.1145/3324884.3416632(647-658)Online publication date: 21-Dec-2020
https://dl.acm.org/doi/10.1145/3324884.3416632
Show More Cited By

View Options

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

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Abstract

References

Cited By

Index Terms

Recommendations

Incremental packrat parsing

Parsing expression grammars: a recognition-based syntactic foundation

Packrat parsers can handle practical grammars in mostly constant space

Comments

Information

Published In

Sponsors

Publisher

Publication History

Permissions

Check for updates

Author Tags

Qualifiers

Conference

Acceptance Rates

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

Login options

Full Access

View options

PDF

eReader

Share

Share this Publication link

Share on social media

Affiliations