lalr1-parser-synthesizer
The LALR(1) parser generator is implemented in a single Python file at ~/lalr1_parser_synthesizer.py. The implementation is structured as a pipeline with these key components:
Grammar Parsing & Analysis (Grammar class)
- Parses BNF-like specs with LHS -> RHS1 RHS2 ... | alt2 format, epsilon support
- Nullable: Iterative fixpoint — a nonterminal is nullable if all RHS symbols are nullable or the RHS is empty
- FIRST sets: Fixpoint computation starting from terminals (trivially {term}), propagating through productions
- FOLLOW sets: Fixpoint adding $ to the augmented start's follow, then for each production position: FOLLOW(B) ∪= FIRST(β) when A → αBβ, and FOLLOW(B) ∪= FOLLOW(A) when β is nullable or B is last
LR(0) Automaton (LALRAutomaton)
- Kernel-based states: each state stores only kernel items (the closure is recomputed)
- closure(I): adds [X → ·γ] for every production where dot precedes nonterminal X
- goto(I, X): advances the dot past X for all items where possible
- States are created iteratively until no new kernel sets are discovered
LALR(1) Lookaheads (DeRemer & Pennello algorithm)
- All items start with empty lookahead sets
- The initial item [S' → ·S] in state 0 gets {$}
- Propagated lookaheads: When [A → α·Xβ, a] transitions to [A → αX·β, a] in the GOTO state, the lookahead propagates
- Spontaneous lookaheads: For [A → α·Xβ, a] where X is a nonterminal, compute FIRST(βa) and add to each closure item [X → ·γ] in the same state
- Iterates until fixed point
Parse Table Generation
- ACTION: Shift entries for terminal transitions on any item; Reduce entries from reduce items using their computed lookaheads; Accept for [S' → S·, $]
- GOTO: Non-terminal transitions between states
- Conflict detection: Any (state, symbol) entry with multiple actions is flagged as shift-reduce or reduce-reduce
Parser Engine (Parser class)
- Standard shift-reduce loop with a state stack
- Conflict resolution prefers shift over reduce (can be overridden)
Key design decisions that made this work correctly:
1. Augmented start tracking: The augmented production S' → S is appended last, so its index is always len(productions) - 1
2. FIRST(βa) computation: Handles nullable chains correctly — if all symbols in β are nullable, the original lookahead a is included
3. Fixpoint iteration: The LALR lookahead computation uses a while changed loop to handle transitive propagation through multiple states
All 42 tests pass with the final implementation. Test categories: | Category | Tests | Status | |----------|-------|--------| | **Expression grammar** — FIRST/FOLLOW correctness, parsing `id+id*id`, `(id+id)*id`, `id` | 12 | ✅ | | **Epsilon grammars** — nullable detection, `ε ∈ FIRST`, parsing with `a*` and empty input | 5 | ✅ | | **Conflict detection** — dangling-else shift/reduce, reduce-reduce | 2 | ✅ | | **Arithmetic** — precedence via grammar, `num+num*num`, `num` | 2 | ✅ | | **Empty language** — `S → ε` parsing empty input | 1 | ✅ | | **Invalid input rejection** — partial/empty/bad tokens | 3 | ✅ | | **List grammar** — `L → L, E | E` parsing `id,id,id` | 2 | ✅ | | **Simple nullable grammar** — `S→AB, A→a|ε, B→b` — FIRST/FOLLOW chains | 5 | ✅ | | **Summary metadata** — JSON output structure | 3 | ✅ | Additional verified edge cases: - **LALR(1) but not SLR(1) grammar** (`S → V=E | E`, `V → *E | id`, `E → V`): zero conflicts ✓ - **Left recursion** (`S → Sa | a`): parses `aaa` correctly ✓ - **Right recursion** (`S → aS | ε`): parses `aaa` and empty correctly ✓ - **Deeply nested expressions** (`((id))`): works ✓ - **Long input** (99 tokens): parses successfully ✓ - **Reduce-reduce conflict** detection: correctly identifies `A→id | B→id` conflict ✓ ---
{"model": "claude-3.5", "problem_class": "lalr1-parser-synthesizer", "result": "passed", "tests": 42}The LALR(1) parser generator is implemented in a single Python file at ~/lalr1_parser_synthesizer.py. The implementation is structured as a pipeline with these key components:
Grammar Parsing & Analysis (Grammar class)
- Parses BNF-like specs with LHS -> RHS1 RHS2 ... | alt2 format, epsilon support
- Nullable: Iterative fixpoint — a nonterminal is nullable if all RHS symbols are nullable or the RHS is empty
- FIRST sets: Fixpoint computation starting from terminals (trivially {term}), propagating through productions
- FOLLOW sets: Fixpoint adding $ to the augmented start's follow, then for each production position: FOLLOW(B) ∪= FIRST(β) when A → αBβ, and FOLLOW(B) ∪= FOLLOW(A) when β is nullable or B is last
LR(0) Automaton (LALRAutomaton)
- Kernel-based states: each state stores only kernel items (the closure is recomputed)
- closure(I): adds [X → ·γ] for every production where dot precedes nonterminal X
- goto(I, X): advances the dot past X for all items where possible
- States are created iteratively until no new kernel sets are discovered
LALR(1) Lookaheads (DeRemer & Pennello algorithm)
- All items start with empty lookahead sets
- The initial item [S' → ·S] in state 0 gets {$}
- Propagated lookaheads: When [A → α·Xβ, a] transitions to [A → αX·β, a] in the GOTO state, the lookahead propagates
- Spontaneous lookaheads: For [A → α·Xβ, a] where X is a nonterminal, compute FIRST(βa) and add to each closure item [X → ·γ] in the same state
- Iterates until fixed point
Parse Table Generation
- ACTION: Shift entries for terminal transitions on any item; Reduce entries from reduce items using their computed lookaheads; Accept for [S' → S·, $]
- GOTO: Non-terminal transitions between states
- Conflict detection: Any (state, symbol) entry with multiple actions is flagged as shift-reduce or reduce-reduce
Parser Engine (Parser class)
- Standard shift-reduce loop with a state stack
- Conflict resolution prefers shift over reduce (can be overridden)
Key design decisions that made this work correctly:
1. Augmented start tracking: The augmented production S' → S is appended last, so its index is always len(productions) - 1
2. FIRST(βa) computation: Handles nullable chains correctly — if all symbols in β are nullable, the original lookahead a is included
3. Fixpoint iteration: The LALR lookahead computation uses a while changed loop to handle transitive propagation through multiple states
All 42 tests pass with the final implementation. Test categories: | Category | Tests | Status | |----------|-------|--------| | **Expression grammar** — FIRST/FOLLOW correctness, parsing `id+id*id`, `(id+id)*id`, `id` | 12 | ✅ | | **Epsilon grammars** — nullable detection, `ε ∈ FIRST`, parsing with `a*` and empty input | 5 | ✅ | | **Conflict detection** — dangling-else shift/reduce, reduce-reduce | 2 | ✅ | | **Arithmetic** — precedence via grammar, `num+num*num`, `num` | 2 | ✅ | | **Empty language** — `S → ε` parsing empty input | 1 | ✅ | | **Invalid input rejection** — partial/empty/bad tokens | 3 | ✅ | | **List grammar** — `L → L, E | E` parsing `id,id,id` | 2 | ✅ | | **Simple nullable grammar** — `S→AB, A→a|ε, B→b` — FIRST/FOLLOW chains | 5 | ✅ | | **Summary metadata** — JSON output structure | 3 | ✅ | Additional verified edge cases: - **LALR(1) but not SLR(1) grammar** (`S → V=E | E`, `V → *E | id`, `E → V`): zero conflicts ✓ - **Left recursion** (`S → Sa | a`): parses `aaa` correctly ✓ - **Right recursion** (`S → aS | ε`): parses `aaa` and empty correctly ✓ - **Deeply nested expressions** (`((id))`): works ✓ - **Long input** (99 tokens): parses successfully ✓ - **Reduce-reduce conflict** detection: correctly identifies `A→id | B→id` conflict ✓ ---
{"model": "claude-3.5", "problem_class": "lalr1-parser-synthesizer", "result": "passed", "tests": 42}