IELR(1) is a straightfoward optimisation for building a LR(1) parser. Instead of building the canonical LR(1) automaton by copying every LR(0) state with every possible lookahead, we only copy the state when the lookahead actually changes what the parser does. Essentially, we try to build LALR(1) and only split states when we get reduce/reduce conflicts. In Lezer’s case, we also split at conflicts from overlapping tokens.
Here’s why I’m proposing this. Right now, grammars relying on lookaheads can be very slow to build, because a lot of intermediate LR(0) states are created before merging them to make the final parse table. I created a faithful Scala grammar, which currently builds 80,000 states before shrinking to 900 final states. This currently takes about 80s to run on my machine. Claude claims that this is an artifact of Scala’s grammar depending a lot on lookaheads: in particular, a type may be followed by a lot of different tokens.
The Julia grammar has a similar issue, building 79,000 LR(0) states that merge to 2000 final states and takes 130s to build.
I’ve made a fork with a proof of concept. Small grammars aren’t affected, but most larger grammars have dramatic improvements: Scala new builds in 1.6s and Julia builds in 12.3s. Memory also improves a lot (before Julia would run out of memory on Node’s default heap limit, now it uses 600MB of memory). The exception in JavaScript, which has a slight increase in the parser table size (1.3k → 1.4k states). This is due to duplicated tokens; deduplicating them removes the increase in size.
I’m working on a Tree-sitter to Lezer converter, which involved building a converted grammar once and using the results to make optimisations. This is significantly sped up with the new builder.
I also added a proposal document (written with Claude) explaining the changes and giving the benchmarks.