parser-generator

name: parser-generator description: 'Generates LALR(1) and recursive-descent parsers from grammar specifications. Use when: (1) Building compilers, (2) Creating DSLs, (3) Parsing configuration files.' version: 1.0.0 tags:

• compiler
• parsing
• grammars
• frontend difficulty: intermediate languages:
• python
• ocaml
• rust dependencies:
• lexer-generator

Parser Generator

Generates parsers from context-free grammar specifications.

When to Use

• Building compilers for new languages
• Creating DSL parsers
• Parsing structured text/data formats
• Generating ASTs from source code

What This Skill Does

1. Parses grammar specs - Converts BNF to internal representation
2. Generates parsers - LALR(1) or recursive descent
3. Handles ambiguity - Resolves with precedence/associativity
4. Reports errors - Generates meaningful error messages

Key Concepts

def peek(self, type: str) -> bool:
    """Check if current token has type"""
    return self.current().type == type

# Grammar rules

def parse_expr(self):
    """Expr -> Term (('+' | '-') Term)*"""
    result = self.parse_term()
    
    while self.peek("PLUS") or self.peek("MINUS"):
        op = self.consume().value
        right = self.parse_term()
        result = BinOp(op, result, right)
    
    return result

def parse_term(self):
    """Term -> Factor (('*' | '/') Factor)*"""
    result = self.parse_factor()
    
    while self.peek("TIMES") or self.peek("DIV"):
        op = self.consume().value
        right = self.parse_factor()
        result = BinOp(op, result, right)
    
    return result

def parse_factor(self):
    """Factor -> NUMBER | '(' Expr ')'"""
    if self.peek("NUMBER"):
        return Number(int(self.consume().value))
    
    if self.peek("LPAREN"):
        self.consume()
        result = self.parse_expr()
        self.consume("RPAREN")
        return result
    
    raise ParseError(f"Unexpected token: {self.current()}")

### AST Nodes

```python
@dataclass
class ASTNode:
    """Base class for AST nodes"""
    pass

@dataclass
class Number(ASTNode):
    value: int

@dataclass
class BinOp(ASTNode):
    op: str
    left: ASTNode
    right: ASTNode

@dataclass
class UnaryOp(ASTNode):
    op: str
    operand: ASTNode

@dataclass
class Var(ASTNode):
    name: str

@dataclass
class Assign(ASTNode):
    name: str
    value: ASTNode

@dataclass
class If(ASTNode):
    condition: ASTNode
    then_branch: ASTNode
    else_branch: Optional[ASTNode]

@dataclass
class While(ASTNode):
    condition: ASTNode
    body: ASTNode

@dataclass
class Block(ASTNode):
    statements: list[ASTNode]

LALR(1) Parser Generator

# Simplified LALR(1) parser generator
from collections import defaultdict

class Grammar:
    def __init__(self):
        self.productions = []  # [(lhs, [rhs symbols])]
        self.terminals = set()
        self.nonterminals = set()
        self.start = None
    
    def add_production(self, lhs, rhs):
        """Add production: lhs -> rhs"""
        self.productions.append((lhs, rhs))
        self.nonterminals.add(lhs)
        for sym in rhs:
            if sym.islower() or sym in ('+', '*', '(', ')'):
                self.terminals.add(sym)
            else:
                self.nonterminals.add(sym)
    
    def augmented_start(self):
        """Create augmented grammar with S' -> S"""
        self.start = self.productions[0][0]
        self.productions.insert(0, ("S'", [self.start]))
        self.nonterminals.add("S'")

# Item: production with dot position
@dataclass
class LRItem:
    lhs: str
    rhs: tuple
    dot: int  # position in rhs
    lookaheads: set

def closure(items, grammar):
    """Compute closure of LR(1) items"""
    closure_set = set(items)
    changed = True
    
    while changed:
        changed = False
        for item in list(closure_set):
            if item.dot < len(item.rhs):
                symbol = item.rhs[item.dot]
                if symbol in grammar.nonterminals:
                    # Find all productions for this nonterminal
                    for lhs, rhs in grammar.productions:
                        if lhs == symbol:
                            # Calculate lookahead
                            beta = item.rhs[item.dot + 1:]
                            new_lookaheads = compute_lookahead(
                                item.lookaheads, beta, grammar
                            )
                            new_item = LRItem(lhs, rhs, 0, new_lookaheads)
                            if new_item not in closure_set:
                                closure_set.add(new_item)
                                changed = True
    
    return closure_set

def compute_lookahead(lookaheads, beta, grammar):
    """Compute lookahead for GOTO"""
    result = set(lookaheads)
    for symbol in beta:
        if symbol in grammar.terminals:
            return {symbol}
        # Handle nullable nonterminals
        if is_nullable(symbol, grammar):
            continue
        break
    return result

def goto(items, symbol, grammar):
    """Compute GOTO(I, X)"""
    goto_set = set()
    for item in items:
        if item.dot < len(item.rhs) and item.rhs[item.dot] == symbol:
            new_item = LRItem(
                item.lhs, 
                item.rhs, 
                item.dot + 1, 
                item.lookaheads
            )
            goto_set.add(new_item)
    return closure(goto_set, grammar)

def build_lalr_table(grammar):
    """Build LALR(1) parsing table"""
    grammar.augmented_start()
    
    # Build canonical collections
    C = [closure({LRItem("S'", (grammar.start,), 0, {"$"})}, grammar)]
    
    # ... (complete algorithm in production code)
    
    # Build action/goto tables
    action = {}
    goto_table = {}
    
    # ... fill in tables
    
    return action, goto_table

Using the LALR Parser

def lalr_parse(tokens, grammar):
    """LALR(1) parser"""
    action, goto = build_lalr_table(grammar)
    
    stack = [0]  # State stack
    symbols = []  # Symbol stack
    
    while True:
        state = stack[-1]
        token = tokens[lookahead]
        
        if (state, token.type) in action:
            action_entry = action[(state, token.type)]
            
            if action_entry[0] == 'shift':
                stack.append(action_entry[1])
                symbols.append(token)
                lookahead += 1
            
            elif action_entry[0] == 'reduce':
                prod = action_entry[1]
                lhs, rhs = grammar.productions[prod]
                # Pop len(rhs) states and symbols
                for _ in range(len(rhs)):
                    stack.pop()
                    symbols.pop()
                # Push nonterminal
                symbols.append(lhs)
                # New state
                new_state = goto[stack[-1], lhs]
                stack.append(new_state)
            
            elif action_entry[0] == 'accept':
                return symbols[1]  # Return AST
            
            else:
                raise ParseError(f"Unknown action: {action_entry}")
        else:
            raise ParseError(f"Unexpected token: {token}")

Key Concepts

Precedence & Associativity

# Specify in grammar
precedence = [
    ('left', ['PLUS', 'MINUS']),
    ('left', ['TIMES', 'DIV']),
    ('right', ['UMINUS']),  # Unary minus
]

# Resolve during parser generation
# 1. Shift > Reduce for unambiguous precedence
# 2. Left-assoc: reduce on leftmost match
# 3. Right-assoc: reduce on rightmost match

Tips

• Start with simple grammars, add features incrementally
• Use left-recursion for recursive descent (or convert to right)
• Handle errors gracefully (error productions, recovery)
• Track source locations in AST
• Consider semantic actions during parsing

Common Issues

Tradeoffs and Limitations

Algorithm Tradeoffs

When NOT to Use This Approach

• For highly ambiguous grammars: Consider parsing expression grammars (PEGs) or GLR
• For streaming/large inputs: Consider incremental parsing
• For error recovery: Use error productions and recovery strategies

Limitations

• LL/LR limits: Not all context-free grammars are parsable
• Ambiguity: Some grammars are inherently ambiguous; must resolve
• Error messages: Parser errors can be cryptic; requires effort for good UX
• Left recursion: Traditional recursive descent fails; requires transformation

Assessment Criteria

A high-quality parser generator should have:

Quality Indicators

✅ Good: Complete grammar coverage, good error messages, preserves locations ⚠️ Warning: Limited grammar coverage, poor error messages ❌ Bad: Wrong parses accepted, crashes on valid input

Related Skills

• lexer-generator - Generate lexers
• program-transformer - Transform ASTs
• lambda-calculus-interpreter - Execute ASTs

Canonical References

Research Tools & Artifacts

Real-world parser generators and tools:

Parser Generator Research

• GLR (Generalized LR) - Handles ambiguity gracefully
• Incremental Parsing - Reparse after small edits
• Error Recovery - Parse errors, continue, report
• Packrat Parsing - PEG with memoization

Research Frontiers

1. Adaptive Parsing

• Approach: Choose parser strategy based on input
• Papers: "Adaptive LL(*) Parsing" (Parr & Fisher)
• Tool: ANTLR 4's ALL(*) algorithm
• Advantage: Handles more grammars

2. Incremental Parsing

• Approach: Reuse parse tree after edits
• Papers: "Incremental Parsing" (Wagner & Graham)
• Tools: Roslyn (C#), tree-sitter
• Advantage: Fast for IDEs

3. Error Recovery Strategies

• Approach: Recover from errors, continue parsing
• Papers: "Error Recovery in LR Parsers" (Burke & Fisher)
• Techniques: Panic mode, phrase-level, partial parsing
• Advantage: Better error messages

4. PEGs vs CFGs

• PEG: Parsing Expression Grammars (ordered choice)
• CFG: Context-free grammars (ambiguous)
• Papers: "Parsing Expression Grammars" (Ford)
• Tools: PEG.js, pest, Scala parser combinators

Implementation Pitfalls

The "Dangling Else" Problem

Classic ambiguity in grammars:

stmt → if expr then stmt
      | if expr then stmt else stmt
      | ...

if E1 then if E2 then S1 else S2
-- Which if does else bind to?
-- Standard: binds to innermost (shift-reduce conflict)

LR Conflict Resolution

%left '+' '-'
%left '*' '/'
%right '='  /* Lowest precedence */

/* In expr:  expr: expr '+' expr  %prec '+'  */
/* Use %prec to assign precedence to rules */

This is why bison uses precedence declarations!