My parser uses backtracking, so failed branches are common even when parsing succeeds. What should I look at when optimizing it, and how can I keep the final errors useful?
How can I make a Java parser combinator library faster?
Answers
Start with failure reporting. If every failed branch builds a detailed error string, a successful parse can still create a lot of short-lived garbage.
Keep the information needed for diagnostics separately, let failures refer to it, and format the message only when you actually report an error. Profile with larger inputs too. Small examples may not reveal allocation pressure or time spent collecting garbage.
Reply to this answer
For the final diagnostic, track the farthest input offset reached by a failure. When multiple failures occur at that offset, merge their expected tokens. Including failures from earlier backtracking branches can make the message noisy.
Keep branch-specific reasons associated with their branches rather than combining everything into one undifferentiated explanation. How to present a complicated merge still needs some care.
Reply to this answer
Benchmark your actual grammar and representative inputs before assuming combinators have to be slower than a generated parser. The amount of backtracking and the work done on each failure matter, so a broad comparison won't tell you where your implementation spends its time.
Reply to this answer
Speed isn't the only thing that makes a parser library usable. Give people a progression of examples beyond a basic calculator, with enough documentation to see how the pieces fit together in a larger grammar. That can make choosing and using the library much easier.
Reply to this answer
Add your answer
Answers are reviewed before publication.
Saffy:
Would a mutable parse context help avoid allocating a wrapper for every failure as well?