Comment by Porygon
9 hours ago
Memoization to limit left-recursive recursion is nicely described in Guido van Rossums' article here: https://medium.com/@gvanrossum_83706/left-recursive-peg-gram...
I recently tried that approach while simultaneously building an abstract syntax tree, but I dropped it in favor of a right-recursive grammar for now, since restoring the AST when backtracking got a bit complex.
You can look at the Earley parser. It handles left recursion well well using a method that’s basically memoization.