APLR is Quite Adequate
Early this year the Hardly Original Compiler Compiler (Hocc) started seeing some serious use, but unfortunately IELR (inadequacy elimination LR) proved frustratingly slow enough to warrant another round of optimization. IELR is ~2X faster now, but this was a 10X performance problem, so I reluctantly ordered a new computer to gain a further ~3X (netting ~6X). But during the couple weeks it took for the computer to be delivered, along came APLR (adequacy preservation LR), which is dramatically faster than IELR for my use cases, as well as being simpler. Concretely, even with the ~6X performance gains the current (incomplete) Hemlock grammar takes 16.5 seconds to generate with IELR, versus 1.3 seconds with APLR. IELR might be tolerable with some additional optimization, but there’s no doubt that APLR is quite adequate. I’m currently dreaming a dream that one day people will reach by default for APLR, and that LALR will join SLR as a limited approach relegated to the annals of history.
I remain quite delighted that APLR arrived spontaneously. Having run out of ideas for IELR optimization I was working on precise parser state reachability analysis in the pursuit of better garbage collection. Something about the (ultimately intractable) simulation-based tracing algorithm I was attempting triggered a rapid chain of realizations. Ten minutes of “Aha!”, a momentary “Eureka!”, a couple days of programming, and the first usable version of APLR was here.
That was in early March 2026. Three months later when I was putting the final touches on an APLR technical report it finally became apparent that Hocc’s IELR implementation is actually more general than that of Bison. No wonder the algorithm was so hard to figure out! And just a couple days ago I was pulling together details for a blog post about a failed APLR optimization experiment, which led to the discovery that there was an n² search algorithm in APLR that could be reduced to n in the common case. Instead of writing that blog post I updated Hocc and the APLR technical report, before even getting a chance to blog about the original version! If you’ve already read the IELR/APLR technical reports, you might want to take another look; both have been significantly updated since original publication.
Precise parser automaton garbage collection (GC)
In February, as I was running out of ideas for IELR optimizations I came across this nerd snipe in Bison’s documentation regarding unreachable states:
While Bison is able to remove unreachable states, it is not guaranteed to remove other kinds of useless states. Specifically, when Bison disables reduce actions during conflict resolution, some goto actions may become useless, and thus some additional states may become useless. If Bison were to compute which goto actions were useless and then disable those actions, it could identify such states as unreachable and then remove those states. However, Bison does not compute which goto actions are useless.
How hard could it be to add precise automaton tracing to Hocc? The answer turned out to be “pretty hard” (see the GC section of the Hocc manual for what worked), but even aside from inadvertently inspiring APLR the effort was worthwhile, because it made LALR/PGM/IELR/APLR automaton comparison much easier. Inconsequential unreachable artifacts caused enough “noise” that important differences remained obscured. Among other things, precise GC exposed a great deal of cruft in the Lyken grammar that obscured LR-relative grammar inadequacies when using the PGM construction algorithm as originally intended. This grammar turned out to be an important test case for achieving equivalence between IELR and APLR (there were bugs in both implementations), but that would not have been feasible had the cruft remained in the automata. More generally, precise GC has been handy during grammar development as a diagnostic for unintended consequences of manual conflict resolution.
IELR versus IELR⁺
It turns out that Hocc’s IELR implementation isn’t actually IELR; I’ve started referring to it informally as IELR⁺. The original IELR algorithm as implemented by Bison assumes that there are no unresolved conflicts in the corresponding LR grammar, which dramatically reduces lane tracing overhead, as well as avoiding precautionary state splitting. Unfortunately it also makes unresolved conflicts difficult to diagnose in the same ways as does the LALR algorithm. In contrast, IELR⁺ preserves LR conflicts in their original forms, just as APLR does.
IELR⁺ was an accident due to my misunderstanding of the original IELR paper as well as ambiguity in the Bison manual regarding IELR:
IELR (Inadequacy Elimination LR) is a minimal LR algorithm. That is, given any grammar (LR or non-LR), parsers using IELR or canonical LR parser tables always accept exactly the same set of sentences.
APLR happened due to a series of accidents. It was motivated by IELR⁺, which was accidentally more general than IELR. But IELR⁺ was too slow. Had I implemented IELR, performance would not have been a lingering problem.
IELR is fine, right? Well, maybe not. Several times now I’ve explained to other developers the failure mode distinctions between LALR/IELR/IELR⁺, and it is proving even more difficult for people to absorb the nuances of IELR failure modes than the age-old brain buster that is LALR-caused reduce-reduce conflicts. I’m of the opinion that LALR-specific confusion is a major cause of developers reaching for inferior parsing technologies, and IELR is even more confusing (though less dangerous).
That failed APLR optimization experiment
As first mentioned in the IELR technical report, IELR⁺ needs a way to remerge precautionary state splits, and Hocc’s original remerging implementation handled only the simple case of individual pairs of states. A couple weeks ago I had the bright idea of optimizing APLR to do multiple remerging passes, iteratively deepening the subgraph search. Depth=1 search is the foundation of the original remerging implementation, and my hypothesis was that quickly finding small remergeable subgraphs would reduce total time spent searching non-remergeable large subgraphs.
Wrong. The naive remergeability search algorithm tests every pair of split states; for a 100-way split that means 100 choose 2 pairs (4950). But most split states are remergeable, and unlimited-depth remergeability tests succeed much more often than do depth=1 tests. And here’s the crux: every successful test effectively decrements n, because two states can thereafter be treated as a cluster. If all 100 states are remergeable, only 99 pairwise tests are required rather than 4950.
APLR was already benefiting somewhat, but its inner loop was still iterating over all n choose 2 pairings rather than immediately clustering remergeable states. With this pointless inefficiency refactored away, APLR sped up by as much as 33X for the benchmarks in the APLR technical report.