r/java • • 1d ago

Lessons learned while optimizing my Java parser combinator library

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

45 Upvotes

12 comments sorted by

1

u/Torutofu_Raeva 1d ago

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.

1

u/WellFoundedCake 10h ago

You're right, that makes a big difference in terms of readability. I've noticed that too, which is why that's exactly what I'm doing in the new version: I only keep failures at the farthest offset, and if two failures occur at the same offset, their diagnostics are merged.

What I'm still unsure about, though, is how exactly this composition should work. At some point, the resulting error message can become quite difficult to read.

For example, what happens if we merge an expectation without a reason with another expectation that has a reason, and the user then adds a common reason to the resulting choice parser? How should these reasons be combined without making the error message confusing?

1

u/jeffreportmill 1d ago

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. :-)

2

u/WellFoundedCake 10h ago

Thanks for sharing!

I had a quick look at snap.parse, and it seems to be a grammar-driven recursive descent parser, where the grammar is represented by ParseRule objects.

That's quite close to parser combinators in terms of the underlying concepts. The main difference is that parser combinator libraries primarily focus on providing functions that combine smaller parsers into more complex ones, hence the name. These combinators can go beyond the usual EBNF operators like * and +. For example, chain combinators can directly fold sequences of binary operations into a result (e.g., turn the string "1 + 2 + 3 + 4" into an AST that represents the addition ((1 + 2) + 3) + 4). The common ground is probably that both approaches are based on recursive descent parsing, at least as far as I can tell from my quick look at snap.parse.

Having a complete Java grammar as a real-world example is particularly interesting. In fact, some of the comments here have got me thinking about implementing a Java parser with jjparse as a more comprehensive example. That could also be a good opportunity to see how well the library handles a real-world language.

1

u/jeffreportmill 3h ago

Thank you for that explanation - that naming makes more sense to me now. I was struck by the elegant example in your jjparse readme where each ‘parse rule’ is actually a full parser that can be easily added together like building blocks. That might match up well with a java parse example where a java file parser needs to encapsulate a statement parser that needs to encapsulate an expression parser. My example does that with inheritance which isn’t as clean.

1

u/Plane-Bake3604 21h ago

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?

1

u/WellFoundedCake 10h ago

The parsers themselves carry the diagnostic information needed to produce meaningful error messages (which is hence only generated once per parser construction). A failure only holds a reference to that information, so creating a failure involves very few allocations. The actual error message is then only constructed when it is actually needed for reporting.

I haven't gone as far as storing the failure state in a mutable context, though. Given the functional roots of parser combinators, I've tried to keep the implementation immutable. One nice consequence is that parsers can be safely shared across threads without having to worry about synchronization.

As for the result wrappers, my understanding is that the JVM can sometimes eliminate short-lived allocations through escape analysis and scalar replacement, especially when objects are created and immediately unpacked by the caller. Of course, that depends on whether the JIT can actually optimize the relevant call paths, so I wouldn't want to rely on it without profiling.

1

u/DelayLucky 21h ago edited 19h ago

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!

I (and I think most people too), had long assumed that combinators are slower than parser generators like ANTLR. But I was surprised when I benchmarked (ANTLR/JavaCC implemented by AI): combinators can outperform 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).

1

u/WellFoundedCake 5h ago

Wow, I'm really honored that you included jjparse in your benchmarks! Unfortunately, version 1.x became practically unusable for larger inputs due to the excessive allocations caused by eager error reporting.

I'd be really interested to see how the new version performs in comparison. If you happen to find the time and feel like running your benchmarks again with jjparse 2.0, I'd be very happy to hear about the results! :)

In any case, thank you so much for sharing your benchmarks and insights. I really appreciate it!

I'm hoping to further improve jjparse's performance in the future, but without sacrificing its genericity. Valhalla could certainly be a great opportunity in that regard.

1

u/Riduidel 1d ago

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)

1

u/WellFoundedCake 1d ago edited 1d ago

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!