Packrat Parsing with Dynamic Buffer Allocation

Authors

  • Nikhil Mangrulkar
  • Kavita Singh
  • Mukesh Raghuwanshi

DOI:

https://doi.org/10.46947/joaasr412022227

Keywords:

Packrat parsing, Parsing Expression Grammars, parser generators, backtracking.

Abstract

Packrat parsing is a type of recursive decent parsing with guaranteed liner time parsing. For this,
memoization technique is implemented in which all parsing results are memorized to avoid repetitive scanning
of inputs in case of backtracking. The issue with this technique is large heap consumption for memoization which
out weigh the benefits. In many situations the developers need to make a tough decision of not implementing
packrat parsing despite the possibility of exponential time parsing. In this paper we present our developed
technique to avoid such a tough choice. The heap consumption is upper bounded since memorized results are
stored in buffer, capacity of which is decided at runtime depending on memory available in the machine. This
dynamic buffer allocation is implemented by us in Mouse parser. This implementation achieves stable
performance against a variety of inputs with backtracking activities while utilizing appropriate size of memory
for heap.

Downloads

Published

2022-04-07

How to Cite

Nikhil Mangrulkar, Kavita Singh, & Mukesh Raghuwanshi. (2022). Packrat Parsing with Dynamic Buffer Allocation. JOURNAL OF ADVANCED APPLIED SCIENTIFIC RESEARCH, 4(1). https://doi.org/10.46947/joaasr412022227