Lessons learned while optimizing my Java parser combinator library

[u/WellFoundedCake]

A while ago, I shared my Java parser combinator library, jjparse, here on reddit. Since then, I've been working on a few improvements, which eventually led to the release of a new major version. I thought this would be a good opportunity to share some of the things I've learned along the way, give a little update on the project, and hopefully get some feedback and discussion going.

As you might know, parser combinators typically rely heavily on backtracking (which is the default in jjparse). Consequently, parser failures are not necessarily exceptional but often part of perfectly successful parsing operations.

My original implementation was pretty straightforward: Whenever a parser failed, it generated diagnostic information explaining what went wrong (i.e., an error message). A perfectly reasonable approach from a conceptual point of view, but as it turned out, not particularly efficient.

Even when parsing eventually succeeded, all those intermediate failures generated error messages that were immediately discarded. And with enough backtracking, that's a lot of unnecessary heap allocations. I only noticed this when I started experimenting with larger inputs for benchmarking. Smaller examples worked just fine, but larger ones showed wildly varying runtimes. Profiling eventually revealed that a substantial part of the runtime was spent dealing with all the garbage produced by error reporting.

So, my lesson learned here is to keep allocations on parser failures to a minimum and only generate detailed error messages when they're actually needed. Looking back, it seems pretty obvious, but I guess that's often the case with these things.

The new implementation stores the information needed for diagnostics in the parser itself. Failures now only point to this information, and actual error messages are generated lazily when requested. I've also added tracking of the farthest failure to provide more useful diagnostics in the presence of backtracking. Redesigning the error reporting also made me reconsider what information a useful error message should actually contain.

For ordinary syntax errors, expectations work quite well:

unexpected token 'x', expected token 'y'

However, parser combinators can also recognize languages beyond the class of context-free languages, and not every failure is purely syntactic in the typical sense. For example, when parsing identifiers that must not be reserved keywords, an explanation might be more useful than an expectation:

unexpected token 'x', because 'x' is a reserved keyword

This led me to distinguish between an expectation and a reason, both of which are optional. The general format of a reported error is now:

unexpected <input token>, expected <expectation> because <reason>

I'm still not entirely sure how flexible this design will turn out to be, particularly when it comes to composing expectations and reasons across parser alternatives. Should reasons be combined? Should expectations take precedence? What if different alternatives fail for entirely different reasons? I'd be interested in hearing what you think!

That aside, all these changes required some breaking API changes, hence version 2.0. A couple of other things I've been working on in this regard:

• Input filtering: Previously, whitespace skipping was somewhat of a hack built into the parser implementation. Now, inputs can be filtered using another parser (input.withFilter(parser)). Whether the implementation is particularly efficient remains to be seen, but I quite like how the API turned out.

• Benchmarks: I've finally added a JMH benchmark to the repository, parsing 10 - 100 MB of synthetically generated, non-repetitive JSON into an AST. The result is around 30 - 34 MB/s. Nothing to write home about compared to specialized parsers, but probably at least roughly comparable to other parser combinator libraries on the JVM (although I haven't tested that yet, tbh). One obvious performance bottleneck is the generic input abstraction, which means that even parsing plain text involves boxing and unboxing characters (or rather Unicode codepoints). I might eventually optimize this under the hood in the future, but I'd really like to preserve the generic API. After all, that's kind of the whole point of the library.

Anyway, I'm still figuring things out, and I'm sure there are plenty of things that could be improved. I'd particularly love to hear your thoughts on the API and overall design. Criticism, suggestions, alternative approaches, or even a PR are all very welcome!

For anyone interested in taking a look: https://github.com/BjoernLoetters/Jar-Jar-Parse

[u/Riduidel]

I've recently developed a C4PlantUML to Structurizr DSL converter (not yet terminated, but nevertheless covering some of the most important use cases). I seriously envisionned using JJParse, but finally choose Parboiled. I found that the Parboiled documentation was more complete and progressive. Their various examples make sure I can go from the simple calculator example (which looks like the canonical example) to parsing a complex language (they even include a full Java language parser!). I suggest you try a similar approach. I must say the most controversial aspect of Parboiled is their use of asm, which makes the parser class a particular class, in which some classical Java constructs make asm fail to generate the underlying classes. Provided you do not use asm or other bytecode generation library, I guess you'll have an advantage in terms of reusability. (but performance-wise, their choice is interesting, I would be very interested in a parser combinator library able to generate underlying classes at compile-time, like what Quarkus does for enterprise applications)

[u/WellFoundedCake → u/Riduidel]

Oh wow, it's really nice to hear that you considered using jjparse for your project! Thanks a lot for sharing your experience!

You're absolutely right about the documentation. That's definitely one of the bigger TODOs on my list. I actually set up an MkDocs website for the project a while ago, but unfortunately haven't found the time to properly work on it yet. I'll definitely take a closer look at Parboiled's documentation. Having a good example of how to gradually introduce more complex use cases is really helpful, thanks!

And if you happen to have any interesting or more challenging parsing examples in mind, feel free to share them, perhaps as an issue or just a small code snippet. I'd be happy to learn from real-world use cases and maybe turn some of them into tutorials. No pressure, of course!

Regarding ASM, jjparse doesn't rely on bytecode generation or transformation, as you observed. It's just plain Java, which is something I'd like to preserve (to keep the reusability and flexibility). The idea of generating specialized parsers at compile time is interesting, though. This actually reminds me of an old Scala project of mine, where I used macros to generate a table-driven parser from a PEG. It's a shame that Java doesn't offer similar compile-time meta-programming capabilities.

Thanks again for the feedback, I really appreciate it!

[u/Torutofu_Raeva]

i'd merge expected tokens only at the farthest offset and keep reasons tied to their branch; pulling in earlier backtracking failures can make the final message noisy.

[u/jeffreportmill]

Very nice. I created a custom parser too for my Java parser in SnapCode (a Java IDE) to replace Javacc, which I thought was too messy with it’s mixed grammar/handler files (and Javacc seemed to be abandoned). My parser uses the basic Javacc grammar file, minus the embedded code, and instead uses custom parse rule handlers (each with methods for parsedOne() and parsedAll()).

SnapKit parser classes: https://github.com/reportmill/SnapKit#the-parser-package

Java Parser: https://github.com/reportmill/SnapCode/blob/master/src/javakit/parse/JavaParser.txt

I didn’t realize it was a ‘parser combinator’ until I saw your post. :-)

[u/Plane-Bake3604]

lazy error evaluation is a huge win for combinators. Are you storing the failure state in a mutable context object passed through the parse tree to avoid allocating result wrappers on every failed branch?

[u/DelayLucky]

Yeah. I had AI agent benchmarked and rationalized why jjparse 1.0 wasn't fast and the eager error message was the main conclusion it arrived at. Great job optimizing it away!

Most people, myself included, have long assumed that combinators can't compete with parser generators like ANTLR. But I was surprised when I benchmarked (ANTLR/JavaCC implemented by AI): combinators can beat generators, by a wide margin even.

Combinators are still slower than hand-written parsers. I'm hoping that when Valhalla is available, combinators can finally be made to compete with hand-written parsers. But that part is a tall order (my initial benchmarking with a pre-release didn't show much gain).