Is stateful packrat parsing really linear in practice? a counter-example, an improved grammar, and its parsing algorithms
Nariyoshi Chida, Yuhei Kawakoya, Dai Ikarashi, Kenji Takahashi, Koushik Sen · 2020
Stateful packrat parsing is an algorithm for parsing syntaxes that have context-sensitive features. It is a well-known knowledge among researchers that the running time of stateful packrat parsing is linear for real-world grammars, as demonstrated in existing studies. However, we have found the cases in real-world grammars and tools that lead its running time to become exponential.