Optimizing Packrat Parsing with Non-Linear Data Structures for Memoization
- 18 October 2023
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-4
Abstract
This research paper presents the implementation of memoization in packrat parsing using non-linear data structures. Packrat parsing is a powerful parsing technique that guarantees linear time parsing for grammars that can be expressed using parsing expression grammars (PEGs), introduced by Bryan Ford in 2002. Memoization is a technique that can be applied to ensure linear time parsing by storing intermediate parsing results. Comparative performance of existing implementations with the proposed approach on various grounds is presented.Keywords
This publication has 8 references indexed in Scilit:
- Stack and Queue Based Parser Approach for Parsing Expression Grammar2023
- Packrat Parsing with Elastic Sliding WindowJournal of Information Processing, 2015
- Applying Classical Concepts to Parsing Expression GrammarFundamenta Informaticae, 2009
- A parsing machine for PEGs2008
- DCGs + Memoing = Packrat Parsing but Is It Worth It?2007
- Parsing expression grammars2004
- Packrat parsing:2002
- Parsing algorithms with backtrackInformation and Control, 1973