python-lalr-lookahead-propagation-merge-conflict-exactness
Done. The verified solution is written to ~/SOLUTION.md with the runnable analyzer at ~/lalr_diag.py.
Root cause. This problem class fails from three interacting traps, not one bug:
A -> α . B β with lookahead a, closure must give B -> . γ the set FIRST(β a). Dropping the inherited a when β is nullable silently loses lookaheads.goto only, or doing a single pass, under-approximates the sets and reports wrong conflicts. I cross-check the propagated sets against the union of canonical LR(1) lookaheads after core-merge.(state, item, lookahead). Bucketing actions by terminal is required; BFS over an unsorted set makes state ids nondeterministic, so the triples aren't reproducible.Fix. Grammar.canonical_lr1() builds canonical LR(1); merge_by_core() groups identical LR(0) cores and unions lookaheads; lalr_propagate() independently computes LALR lookaheads by iterating closure + goto edges seeded with $ on S'->.S; action_table() emits one triple per reduce item and applies shift-preferred selection.
Verification (all assertions pass):
| Grammar | Canonical | Merged | Propagation == merge | Conflicts |
|---|---|---|---|---|
S -> aEc \| aFd \| bFc \| bEd, E->e, F->e |
14 | 13 | True | 0 canonical, 4 spurious RR at state 6 on c/d |
| dangling-else | 17 | 10 | True | 1 SR, chosen shift on else |
S -> C C, C -> c C \| d |
10 | 7 | True | none (LALR(1) control) |
The 0-canonical / 4-LALR result is the exact proof that the four (6, E->e. / F->e., c|d) reduce/reduce conflicts are merge-induced. State numbering is stable across PYTHONHASHSEED=1,2,3, and the reuse example (Expr grammar) produces the expected 22→12 merge with no conflicts.
# Evidence - Problem class: python-lalr-lookahead-propagation-merge-conflict-exactness - Model: openrouter/deepseek/deepseek-v4.1-flash - Solved: 2026-10-01T10:09:49.752Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "Given a BNF grammar, build the canonical LR(1) item-set collection, then merge states with identical LR(0) cores and compute LALR(1) lookahead sets by lookahead propagation over the goto/closure graph instead of re-deriving them. Report the exact shift/reduce and reduce/reduce conflicts as (state, item, lookahead) triples, including the spurious reduce/reduce conflicts that merging introduces for a grammar that is LR(1) but not LALR(1). Output the canonical and merged state counts plus the action-table cell chosen at each conflict under the shift-preferred default.", "environment": "python3", "language": "python", "model": "openrouter/deepseek/deepseek-v4.1-flash", "problem_class": "python-lalr-lookahead-propagation-merge-conflict-exactness", "provider": "openrouter", "solved_at": "2026-10-01T10:09:49.752Z", "version": "3.11"}