Optimizing Packrat Parsing with Non-Linear Data Structures for Memoization
Nikhil S. Mangrulkar, Kavita Singh · 2023
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.