Skip to main content
Springer Nature Link
Log in

Parsing Expression Grammar and Packrat Parsing—A Review

  • Conference paper
  • First Online:
Information and Communication Technology for Competitive Strategies (ICTCS 2021)

Part of the book series: Lecture Notes in Networks and Systems ((LNNS,volume 400))

  • 720 Accesses

Abstract

Ford presented Parsing Expression Grammars (PEGs) as an alternative to specify rules for programming language, along with a Packrat parser, based on an idea of memoization. The idea proposed by Ford guarantees parsing of grammar written using PEGs in linear time in spite of backtracking. The primary aim of the paper is to highlight the details of PEGs followed by various challenges existing for a better understanding of the readers. From the entire overview presented, it has been observed that PEGs address the issue of undesired ambiguity in grammar for computer-oriented programming language, by not allowing any ambiguity in rules itself at the first place. However, the guarantee of linear time execution comes with a cost of large heap consumption, making it infeasible to implement for large inputs. Optimizing the resources required for memoization, may allow us to utilize the benefits offered by PEGs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Birman A (1970) The TMG recognition schema. PhD thesis, Princeton University, Department of Electrical Engineering, Princeton, NJ

    Google Scholar 

  2. Birman A, Ullman JD (1973) Parsing algorithms with backtrack. Inf Control 23(1):1–34

    Article  MathSciNet  Google Scholar 

  3. Ford B (2004) Parsing expression grammars: a recognition-based syntactic foundation. In: Proceedings of the 31st ACM SIGPLAN-SIGACT symposium on principles of programming languages (POPL ‘04). ACM, New York, NY

    Google Scholar 

  4. Ford B (2002) Packrat parsing: a practical linear-time algorithm with backtracking. Master’s thesis, Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science, Cambridge, MA

    Google Scholar 

  5. Ford B (2002) Packrat parsing: simple, powerful, lazy, linear time-functional pearl. In: Proceedings of the ACM SIGPLAN international conference on functional programming, ICFP, Pittsburgh. ACM

    Google Scholar 

  6. Medeiros S, Ierusalimschy R (2008) A parsing machine for PEGs. In: Proceedings of the 2008 symposium on dynamic languages (DLS ‘08). ACM, New York, NY

    Google Scholar 

  7. Oikawa M, Ierusalimschy R, Moura A (2010) Converting regexes to parsing expression grammars. In: Proceedings of the 14th Brazilian symposium on programming languages, SBLP, vol 10

    Google Scholar 

  8. Becket R, Somogyi Z (2008) DCGs + memoing = packrat parsing but is it worth it? In: 10th international symposium, PADL 2008, San Francisco, CA, 7–8 Jan 2008

    Google Scholar 

  9. Grimm R (2004) Practical packrat parsing. New York University technical report, Dept. of Computer Science, TR2004-854

    Google Scholar 

  10. Redziejowski RR (2009) Mouse: from parsing expressions to a practical parser. In: Concurrency specification and programming workshop

    Google Scholar 

  11. Chida N, Kuramitsu K (2017) Linear parsing expression grammars. Preprint version, Sept 2017

    Google Scholar 

  12. Dubroy P, Warth A (2017) Incremental packrat parsing. In: Proceedings of 2017 ACM SIGPLAN international conference on software language engineering (SLE’17). ACM, New York, NY

    Google Scholar 

  13. Laurent N, Mens K (2016) Parsing expression grammars made practical. Preprint version, Sept 2016

    Google Scholar 

  14. Moss A (2014) Derivatives of parsing expression grammars. arXiv preprint arXiv:1405.4841

  15. Johnson M (1995) Memoization in top-down parsing. Comput Linguist 21

    Google Scholar 

  16. Warth A, Douglass JR, Millstein TD (2008) Packrat parsers can support left recursion. In: PEPM 8

    Google Scholar 

  17. Kuramitsu K (2015) Packrat parsing with elastic sliding window. J Inf Process 23(4)

    Google Scholar 

  18. Goswami MM, Raghuwanshi MM, Malik L (2016) Performance improvement of stack based recursive-descent parser for parsing expression grammar. Int J Latest Trends Eng Technol 6(3)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer Technology, Yeshwantrao Chavan College of Engineering, Nagpur, Maharashtra, India

    Nikhil S. Mangrulkar & Kavita R. Singh

  2. Symbiosis Institute of Technology, Symbiosis International (Deemed University), Nagpur, Maharashtra, India

    Mukesh M. Raghuwanshi

Authors
  1. Nikhil S. Mangrulkar
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kavita R. Singh
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Mukesh M. Raghuwanshi
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Nikhil S. Mangrulkar .

Editor information

Editors and Affiliations

  1. Global Knowledge Research Foundation, Ahmedabad, India

    Amit Joshi

  2. Nottingham Trent University, Nottingham, UK

    Mufti Mahmud

  3. University of Peradeniya, Kandy, Sri Lanka

    Roshan G. Ragel

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Mangrulkar, N.S., Singh, K.R., Raghuwanshi, M.M. (2023). Parsing Expression Grammar and Packrat Parsing—A Review. In: Joshi, A., Mahmud, M., Ragel, R.G. (eds) Information and Communication Technology for Competitive Strategies (ICTCS 2021). Lecture Notes in Networks and Systems, vol 400. Springer, Singapore. https://doi.org/10.1007/978-981-19-0095-2_36

Download citation

  • DOI: https://doi.org/10.1007/978-981-19-0095-2_36

  • Published:

  • Publisher Name: Springer, Singapore

  • Print ISBN: 978-981-19-0094-5

  • Online ISBN: 978-981-19-0095-2

  • eBook Packages: EngineeringEngineering (R0)

Publish with us

Policies and ethics