if len(s) >= 2 and s[0] == s[-1] and s[0] in ('"', "'"):
I built a complete LR(1) parser generator in Python that handles the full pipeline: grammar parsing, LR(1) item DFA construction, parse table generation with conflict detection, precedence/associativity-based conflict resolution, and a working parser with error reporting.
Architecture:
Grammar representation (Grammar class): Stores rules, terminals, non-terminals, precedence/associativity directives, and computes FIRST sets.
LR(1) item set construction (closure, goto, items): Computes LR(1) closure correctly by propagating lookaheads through FIRST sets of βa (where β follows the dot and a is the current lookahead).
Parse table (build_parse_table): Constructs ACTION and GOTO tables, detecting and resolving conflicts:
All conflicts are reported with details
Parser (Parser.parse): Standard LR(1) parsing with the constructed table, including panic-mode error recovery and detailed error messages.
Key implementation details:
# Quote stripping from grammar symbols
@staticmethod
def _strip_quotes(s: str) -> str:
if len(s) >= 2 and s[0] == s[-1] and s[0] in ('"', "'"):
return s[1:-1]
return s
# LR(1) closure: FIRST(βa) propagation
def closure(items, grammar):
# For each item with dot before nonterminal B,
# add all B→γ rules with lookaheads from FIRST(βa)
beta_plus = rule.rhs[item.dot + 1:] + (item.lookahead,)
first_set = grammar.first(beta_plus)
# Conflict resolution via precedence
def resolve_conflict(grammar, term, rule_idx, conflict_type):
t_level, t_assoc = grammar.prec.get(term)
r_level, r_assoc = grammar.rule_prec(rule_idx)
if t_level > r_level: return 'shift'
elif t_level < r_level: return 'reduce'
else: # same level → associativity
if t_assoc == PREC_ASSOC_LEFT: return 'reduce'
elif t_assoc == PREC_ASSOC_RIGHT: return 'shift'
**11 tests pass, 0 fail.** Tested scenarios: | Test | Description | Result | |------|-------------|--------| | Expression grammar construction | `E → E + E \| E * E \| (E) \| n` with `%left + -`, `%left * /`, `%right ^` | 50 shift/reduce conflicts detected and resolved | | Parse `n + n * n` | Correctly produces `n + (n * n)` — multiplication binds tighter | ACCEPTED | | Parse `(n + n) * n` | Parentheses override precedence correctly | ACCEPTED | | Parse `n + + n` | Invalid syntax rejected with error | REJECTED with message | | Dangling-else grammar | `%right "else"` resolves the classic ambiguity | 1 conflict resolved as shift (else binds to innermost if) | | Parse if-else | `if id then if id then other else other` — else matched to inner if | ACCEPTED | | Simple non-ambiguous grammar | `S → A B, A → a A | b, B → c d` | 0 conflicts | | Parse `b c d` | Valid input | ACCEPTED | | Parse `a b c d` | Valid input | ACCEPTED | | Parse `a c d` | Error: missing `b` fails with descriptive message | REJECTED+error | | Precedence correctness | Verify `%left +` vs `%left *` resolves correctly | 4 conflicts all resolved correctly | **Edge cases handled:** - Terminal symbols with and without quotes (`'+'`, `+`, `"if"`) - Epsilon rules (`ε`) - The `$` end marker properly handled in FIRST sets and terminals - Accept/reduce, shift/reduce, reduce/reduce conflicts all detected and reported - Panic-mode error recovery ---
{"model": "claude-sonnet-4-20250514", "problem_class": "lr1-parser-generator-resolve-8b3d", "result": "passed", "tests": 11}