The parsing process is inefficient. #1
Description
Currently, the parser is implemented using recursive descent with backtracking. The use of backtracking makes this an algorithm with exponential asymptotic runtime. The plan is to switch to using an LR(k) parser relying on the finite automata library used throughout the regular expression and lexer libraries instead. The LR(k) class of parsers are incredibly expressive and efficient to run. However, there is more work required to build the parser initially (especially in terms of memory usage as k increases).
Workarounds:
- I can't lie: this inefficiency is detrimental. Small grammars can still be used (like the one given in the test suite). However, even moderately sized grammars become impossible to run. For now, stick to small grammars for simple things like expression parsing and things should work fine.