Performance tuning? about pegparser HOT 4 CLOSED

What is useful about the "grammar analysis" is that it detects a lot more than left-recursion, it also catches mistakes like e.g. foo ::= bar+ with bar ::= ' '*. Happy hacking :-)

from pegparser.

Hey @ColinH, thanks for the issue! Tbh I'm not surprised about the low performance, especially for simple languages such as JSON. PEGParser was not designed for performance, but rather for ease-of-use and rapid prototyping of complex languages, and has the ability to build new parsers at run-time. Because of this it cannot possibly compete with optimised hand written parsers or compile time libraries such as PEGTL.

About memoization, it's a requirement for this project as it allows parsing naive grammars containing left recursion (without rewriting them) and otherwise the time-complexity would get out of hand fairly quickly. I might look into benchmarking and optimising this library in the future but that hasn't been a priority so far.

That said, I'm currently using PEGParser in production on a mobile App containing thousands of LOC in complex custom programming language (containing both left and right associative binary operators defined recursively) and it's not even close to being a performance bottleneck there. I've actually tried implementing a subset of the grammar in a third-party, non-memoizing parsing library and immediately had noticeable performance problems with complex input strings.

For PEGTL though, I agree that memoization should not be considered. In the readme, the project is stated as aiming for "efficiency and simplicity", one of which would likely need to be sacrificed for adding memoization. Most grammars can instead easily be rewritten to achieve great performance on recursive-descent parsers. (after being prototyped in this library, for example 😉)

from pegparser.

Hi and thanks for your response! Right, different design goals, different solutions and trade offs, and I'm happy that you confirm our intuition regarding memoization. Our "solution" to left-recursion is to ship a "grammar analysis" that detects (probably) all grammar rules that can be part of an infinite loop without progress, but it is up to the user to fix the issue by changing the grammar. If I ever need to create grammars at runtime I'll take a much closer look at your library as that is the one thing totally incompatible with our approach.

from pegparser.

Glad to hear, the left-recursion detection sounds like a great solution to avoid runtime bugs! If I ever need high performance parsing I'll be sure to check out PEGTL as well. :)

from pegparser.