The APLR(1) algorithm for compact LR(1) parsers is simpler and more capable than
4 hours ago
- #parser generation
- #LR(1) algorithms
- #automata minimization
- APLR(1) is a new LR(1)-family parser generation algorithm that produces compact parsers without LR(1)-relative inadequacies, even for nondeterministic or ambiguous grammars.
- APLR(1) parser automata are suitable for Generalized LR (GLR) parsing, and for deterministic parsing, they prevent mysterious conflicts during grammar development.
- APLR(1) can augment other algorithms like IELR(1) by remerging unnecessary state splits, offering a simpler alternative based on subgraph isomorphism search.
- Unlike LALR(1), which can cause mysterious conflicts (new, invasive, mutated), APLR(1) preserves adequacy by remerging states from a canonical LR(1) automaton without changing the recognized language.
- APLR(1) and IELR(1) are duals; APLR(1) starts with a resolved LR(1) automaton and remerges states, while IELR(1) starts with LALR(1) and splits states to eliminate inadequacies.
- Experiments show APLR(1) is viable across grammars (e.g., Gawk, Gpic, Lyken, OCaml), with performance depending on subgraph complexity but generally efficient when conflict resolution is enabled.
- APLR(1) implementation is simpler (~700 LOC in Hocc) compared to IELR(1) (~1600 LOC), making it an attractive choice for new parser generator implementations in 2026.