APLR(1) Reframes Compact Parser Generation as Adequacy Preservation

Thesis

The BranchTaken article on APLR(1) is not merely a report about a new parser-generation algorithm inside Hocc, the parser generator associated with the Hemlock language project. It is an argument about where complexity should live in compiler tooling: in fragile grammar workarounds, in opaque state-splitting machinery, or in a direct graph-theoretic test of whether parser states can be merged while preserving the behavior of canonical LR(1).

APLR(1), short for Adequacy Preservation LR(1), begins from a canonical LR(1) automaton, optionally after conflict resolution, and then searches for state subgraphs that can be remerged without changing the recognized language. That direction matters philosophically as much as technically. LALR(1), the old workhorse popularized by Yacc-style tools, starts from aggressive merging and accepts the risk of mysterious conflicts. IELR(1), as implemented in tools such as GNU Bison, starts from an LALR-like compact automaton and tries to split states just enough to recover LR(1) adequacy. APLR(1) reverses the intuition: first build the fully adequate thing, then remove only the redundancy that can be proven unnecessary.

The result, according to the report, is an algorithm that is conceptually simpler than IELR(1), capable of handling nondeterministic or ambiguous grammars in a way suitable for GLR-style parsing, and practical enough for real grammars when conflict resolution is enabled. Its deepest claim is not just that APLR(1) can produce compact automata, but that it changes parser generation from a procedural art of avoiding hidden state-merging damage into a structural question about subgraph equivalence.

Key Arguments

The first argument is historical: LR(1) has always had the right semantic shape, but not the right practical size. Knuth’s canonical LR(1) construction gives parser generators a powerful model of deterministic context-free parsing, yet canonical LR(1) automata can become very large because they distinguish states by lookahead information. LALR(1), introduced later and spread through Yacc, solved the size problem by merging states with identical LR(0) cores, but it did so by disregarding lookahead during state construction. That bargain was attractive for early machines, but it left language implementers with the notorious phenomenon of mysterious conflicts, where a grammar that is valid under canonical LR(1) appears broken under LALR(1) because independent lookahead contexts have been collapsed.

The article’s terminology is useful because it separates two questions that are often blended together. A parser automaton can be compact, meaning it avoids the huge state count of canonical LR(1), while still being adequate relative to LR(1), meaning it accepts the same language and does not introduce artifacts caused by unsafe merging. LALR(1) is compact but can be inadequate. Canonical LR(1) is adequate but often too large. The interesting middle ground is occupied by algorithms such as Pager’s PGM LR(1), IELR(1), IELR+(1), and now APLR(1), all of which attempt to preserve canonical LR(1) behavior while avoiding canonical LR(1) bulk.

The second argument concerns ambiguity. Traditional LR parser generation often treats conflicts as failures, then offers precedence and associativity as controlled escape hatches. In practice, most expression grammars rely on those mechanisms, since rewriting every precedence hierarchy into an unambiguous grammar can distort both the grammar and the parse tree. The BranchTaken piece insists that any modern LR(1)-family algorithm must be evaluated not only on clean LR(1) grammars, but also on grammars that contain ambiguity before resolution, or even retain nondeterminism for use with GLR.

This is where the distinction between IELR(1) and IELR+(1) becomes central. IELR(1), as described in the 2010 paper by Joel Denny and Brian Malloy and connected to Bison’s implementation, analyzes an unresolved LALR(1) automaton and traces conflict contributions backward to determine where state splits are needed. That works well under the assumption that the corresponding LR(1) automaton does not itself contain unresolved ambiguity. IELR+(1), Hocc’s generalized extension described in BranchTaken’s earlier IELR(1) report, removes that assumption, but at a cost: it must trace richer contribution sets through closure, sometimes making precautionary state splits that later prove unnecessary.

APLR(1) offers the dual move. Instead of asking which merged states must be split, it asks which split states can be merged. It analyzes the complete LR(1) automaton and searches among isocoric states, states with the same LR(0) core, for maximal non-overlapping isomorphic subgraphs that can be rejoined. A pair of states may be merged when their shift transitions, reduce actions, and goto transitions either match directly or can be shown to match through transitive remergeability. If one state has no action for a lookahead symbol while another has only reductions on that symbol, the merge can still be valid under the algorithm’s criteria, provided the broader state set remains behaviorally consistent.

That phrase, transitive remergeability, carries much of the algorithm’s elegance. A parser automaton is not a bag of states, it is a directed graph whose states point to successor states through shifts and gotos. Two states that look different locally may still be equivalent for parser purposes if their differences point into subgraphs that are themselves remergeable. Conversely, a pair that appears promising can fail because some downstream state pair contains an incompatible conflict. The algorithm therefore memoizes what it learns: once a pair is known mergeable, future searches can reuse that fact; once a pair is known distinct, searches that depend on it can fail without repeating the same exploration.

The third argument is about implementation comprehensibility. IELR-style lane tracing is powerful, but the report portrays it as difficult to reason about, especially when bugs manifest as missing state splits. A missing split may produce an automaton that looks clean while silently recognizing the wrong language or resolving a conflict too early. APLR(1), by contrast, begins from the most discriminating automaton and then performs explicit remerging. The author claims that APLR(1) stabilized within days in Hocc, while IELR+(1) took years to mature, and uses line count as one rough measure: roughly 700 lines for APLR(1) versus about 1600 for IELR+(1).

Line count alone is never proof of correctness, but in compiler infrastructure it can be evidence of cognitive surface area. Parser generators are trusted components, often used to build other tools that developers trust. An algorithm whose failure modes are easier to observe and whose core idea can be stated as subgraph equivalence has a practical advantage over one that requires subtle reasoning about backward conflict lanes, closure, and precautionary splitting.

The fourth argument is empirical. The report compares LALR(1), PGM LR(1), IELR+(1), APLR(1), and canonical LR(1) on grammars including Gawk, Gpic, Lyken, and OCaml. The results do not present APLR(1) as uniformly fastest. They show a more textured picture. With conflict resolution enabled, APLR(1) produces compact state counts matching IELR+(1) in the reported cases, such as 367 states for Gawk and 428 for Gpic, while avoiding the thousands or tens of thousands of states produced by canonical LR(1). For Lyken, APLR(1) is dramatically faster than IELR+(1) under conflict resolution in the reported run. For OCaml with conflict resolution enabled, IELR+(1) is faster than APLR(1), while both produce the compact 1878-state result.

The unresolved OCaml grammar is the stress test that prevents the essay from becoming triumphalist. There, APLR(1) takes more than nine hours in the reported benchmark, while IELR+(1) takes several minutes and canonical LR(1) takes under two minutes, despite producing over 100,000 states. That result is a reminder that graph search algorithms can be conceptually clean and still suffer under highly interconnected state spaces. The author’s response is pragmatic: this is not a common production scenario, since real parser development normally uses conflict resolution rather than intentionally leaving a large grammar unresolved.

Implications

The immediate implication for parser-generator authors is that APLR(1) may be the more attractive algorithm to implement in 2026 if the goal is compact LR(1)-relative adequacy without IELR’s conceptual load. The article’s recommendation is blunt: an aspiring LR(1)-family parser generator author with limited time should implement APLR(1). That recommendation is plausible not because APLR(1) dominates every benchmark, but because its correctness story is easier to audit. It starts from canonical LR(1), whose behavior is well understood, then asks whether merging preserves that behavior.

For language designers, the deeper implication is about the kind of feedback a parser generator should provide during grammar development. Mysterious conflicts are not just annoying diagnostics. They are failures of explanation. When a parser generator reports a conflict that exists only because of an implementation shortcut, the developer is forced to reason about the tool’s approximation rather than the grammar’s meaning. APLR(1), like IELR, tries to remove that class of confusion by ensuring that conflicts correspond to real LR(1)-level phenomena rather than artifacts of unsafe LALR merging.

This matters in modern tooling because grammars are not only used to build compilers. They sit inside language servers, formatters, linters, query engines, code-indexing systems, refactoring tools, and program-analysis pipelines. A tool author who uses Menhir, Bison, or another LR-family generator is not only choosing a parser. They are choosing a model of how much ambiguity and diagnostic complexity will be pushed back onto the grammar author. Compact adequate algorithms make it easier to preserve a grammar’s intended structure without constantly reshaping it to appease the table generator.

There is also an implication for GLR. Generalized LR parsing treats conflicts as nondeterminism and explores multiple actions in parallel, accepting input if some path succeeds. But GLR is only as faithful as the automaton it runs on. If an LALR(1) automaton has already collapsed states and conflict resolution has removed actions that canonical LR(1) would have preserved, then GLR cannot recover those lost alternatives. APLR(1)’s claim to handle nondeterministic or ambiguous grammars without LR(1)-relative inadequacy makes it interesting as a front end for GLR techniques, because it tries to distinguish fundamental ambiguity in the grammar from accidental ambiguity or loss introduced by table construction.

The article also invites a broader reflection about minimization. Minimizing LR(1) state machines is known to be computationally difficult in the general case, as discussed in Wuu Yang’s paper Minimizing LR(1) State Machines is NP-Hard. APLR(1) does not claim global minimality. It is greedy, and the order of pairwise remergeability tests can affect the final automaton. That limitation is not a defect so much as a design boundary. The practical question is not whether the automaton is mathematically smallest, but whether it is small enough, adequate, understandable, and generated within acceptable time for real grammars.

This is a recurring pattern in language tooling. The exact optimum is often less useful than an invariant that engineers can trust. APLR(1)’s invariant is adequacy preservation. Once that is fixed, compactness becomes a search problem bounded by practical heuristics rather than a license to merge recklessly. In that sense, APLR(1) is less a replacement for all prior parser research than a clarification of priorities: correctness of recognized language first, compactness second, global optimality only when it does not consume the whole engineering budget.

Counter-perspectives

The strongest counter-perspective is that APLR(1) may be simpler in theory but still expensive in bad cases. The OCaml benchmark with unresolved conflicts is not a minor footnote, since OCaml’s grammar is a serious, real-world grammar rather than a contrived torture test. If a parser generator must support interactive grammar development where large ambiguous grammars are temporarily common, then long APLR(1) runs could be painful. IELR+(1), despite its complexity, may be a better engineering fit for some workflows because its cost profile differs.

A second counterpoint is that canonical LR(1) construction itself can be too large for some environments, even if the final APLR(1) automaton is compact. The report discusses a possible future direction in which automaton closure is driven from within the subgraph remergeability search, allowing many canonical states to remain unmanifested in common cases. That idea is attractive, but it would complicate the current clean two-phase account. APLR(1)’s simplicity partly depends on having the complete canonical automaton available before minimization-like remerging begins.

A third counterpoint is ecosystem inertia. LALR(1) remains common not because it is theoretically ideal, but because it is familiar, fast, and widely implemented. Bison’s IELR mode already gives many users a path away from LALR inadequacy without adopting an entirely new generator. Menhir has its own mature design choices and a long relationship with OCaml grammar engineering. APLR(1) may be compelling for new implementations, but parser-generation algorithms spread through tools, documentation, habits, and trust, not only through clean arguments.

The final counter-perspective is that ambiguity support can be a mixed gift. GLR and unresolved conflicts can help grammar authors express languages more naturally, but they can also defer hard language-design decisions. A parser that accepts nondeterminism faithfully does not tell the language designer whether the ambiguity is desirable, accidental, or hostile to downstream tooling. APLR(1) can prevent the parser generator from inventing mysterious conflicts, but it cannot decide which ambiguities belong in the language. That remains a semantic and human question.

Synthesis

APLR(1) is most interesting as a philosophical inversion of a long-standing compromise. The old compromise said: build something small by merging aggressively, then teach grammar authors to live with the consequences. IELR softened that compromise by splitting where necessary. APLR(1) makes a different bet: begin with the full LR(1) truth, then erase distinctions only when the automaton graph itself proves that those distinctions do not matter.

That makes the algorithm feel unusually aligned with the way compilers ought to be built. A compiler is a machine for preserving distinctions until they can be safely collapsed. Lexers distinguish characters until tokens are enough. Parsers distinguish derivations until a syntax tree is enough. Type checkers distinguish expressions until constraints are solved. Optimizers distinguish program states until equivalences justify rewriting. APLR(1) applies the same ethic to parser automata: do not confuse compactness with blindness, and do not treat a smaller table as progress if it has forgotten why the larger table was correct.

The BranchTaken report therefore contributes more than another acronym to the LR family. It gives parser authors a clear mental model: adequacy is preservation, compactness is remerging, and the graph is the proof object. Whether APLR(1) becomes widely adopted will depend on implementations, benchmarks, and integration into tools people already use, but the idea is strong because it restores a clean relationship between grammar meaning and parser machinery.