ALL(*): Adaptive LL(*)

Despite the advances made by modern parsing strategies such as PEG, LL(*), GLR, and GLL, parsing is not a solved problem. Existing approaches suffer from a number of weaknesses, including difficulties supporting side-effecting embedded actions, slow and/or unpredictable performance, and counter-intuitive matching strategies. This paper introduces the ALL(*) parsing strategy that combines the simplicity, efficiency, and predictability of conventional top-down LL(k) parsers with the power of a GLR-like mechanism to make parsing decisions. The critical innovation is to move grammar analysis to parse-time, which lets ALL(*) handle any non-left-recursive context-free grammar. ALL(*) is $O(n^4)$ in theory but consistently performs linearly on grammars used in practice, outperform in general strategies such as GLL and GLR by orders of magnitude. ANTLR 4 generates ALL(*) parsers and supports direct left-recursion through grammar rewriting.

— Parsing: The Power of Dynamic Analysis, Terence Parr, Sam Harwell, and Kathleen Fisher, 2014 ↗

Implementations

• ANTLR v4 ↗ (Java, Cpp, CSharp, Dart, JavaScript, PHP, Python3, Swift, TypeScript, Go)