🧠 Introduction

🎯 What is Parsing?

Parsing is the process of analyzing a string of symbols (tokens) according to the rules of a formal grammar. It's the second phase of a compiler, after lexical analysis. LL and LR are the two main families of parsing algorithms.

Key insight: LL parsers read input left-to-right and produce a leftmost derivation (top-down). LR parsers read input left-to-right and produce a rightmost derivation in reverse (bottom-up). LR is more powerful but more complex.

Why Parsing Matters

Compilers: Syntax analysis. LL: Simple, hand-written. LR: Powerful, tool-generated. Predictive: No backtracking. Shift-reduce: Efficient. Industry: Yacc, Bison, ANTLR.

⬇️ LL Top-down⬆️ LR Bottom-up🔍 Predictive⚙️ Shift-reduce

# LL/LR Parsing — the big picture
print("""
=== What is Parsing? ===

Parsing = analyzing a string according to a grammar.

Input:  Token stream (from lexer)
Grammar: Context-free grammar (Type 2)
Output: Parse tree (or AST)

Two main families:
  LL: Top-down, predictive
  LR: Bottom-up, shift-reduce

=== LL Parsing (Top-Down) ===

LL(k) = Left-to-right scan, Leftmost derivation, k lookahead.

Idea:
  - Start with start symbol.
  - Predict which rule to apply.
  - Expand nonterminals.
  - Match terminals with input.
  - Build parse tree top-down.

Example:
  Grammar: S → aS | b
  Input: "aab"
  
  S ⇒ aS ⇒ aaS ⇒ aab
  
  Top-down derivation!

Pros:
  - Simple to understand.
  - Easy to hand-write.
  - Good error messages.

Cons:
  - Less powerful than LR.
  - Can't handle left recursion.
  - Needs FIRST/FOLLOW sets.

=== LR Parsing (Bottom-Up) ===

LR(k) = Left-to-right scan, Rightmost derivation (reverse), k lookahead.

Idea:
  - Start with input.
  - Shift tokens onto stack.
  - Reduce when a rule is recognized.
  - Build parse tree bottom-up.

Example:
  Grammar: S → aS | b
  Input: "aab"
  
  Shift a, shift a, shift b
  Reduce b → S
  Reduce aS → S
  Reduce aS → S
  Accept!
  
  Bottom-up reduction!

Pros:
  - More powerful than LL.
  - Handles left recursion.
  - Efficient (O(n)).
  - Used in tools (Yacc, Bison).

Cons:
  - Harder to understand.
  - Harder to hand-write.
  - Complex table construction.

=== The Parsing Landscape ===

  ┌─────────────────────────────────────┐
  │ Context-Free Grammars (CFG)         │
  │  ┌───────────────────────────────┐  │
  │  │ LR(1)                         │  │
  │  │  ┌─────────────────────────┐  │  │
  │  │  │ LALR(1)                 │  │  │
  │  │  │  ┌───────────────────┐  │  │  │
  │  │  │  │ SLR(1)            │  │  │  │
  │  │  │  │  ┌─────────────┐  │  │  │  │
  │  │  │  │  │ LR(0)       │  │  │  │  │
  │  │  │  │  └─────────────┘  │  │  │  │
  │  │  │  └───────────────────┘  │  │  │
  │  │  └─────────────────────────┘  │  │
  │  └───────────────────────────────┘  │
  └─────────────────────────────────────┘

LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1)

All handle deterministic CFLs.
LR(1) is most powerful.
LALR(1) is most practical.

=== Historical Context ===

1965: Knuth introduces LR(k) parsing.
1969: DeRemer introduces SLR and LALR.
1970s: Yacc (Johnson) uses LALR(1).
1980s: Bison (GNU) uses LALR(1).
1990s: ANTLR uses LL(*).
2000s: Modern parsing (GLR, PEG).

Yacc/Bison are still used today.
LR parsing is the industry standard.
""")

# ANALOGY
print("=== Analogy: Reading a Sentence ===")
print("""
LL Parsing (Top-Down):
  You read a sentence and predict its structure.
  
  "The cat sat on the mat."
  
  Start with Sentence.
  Predict: Sentence → NP VP
  Predict: NP → Det N
  Match: "The" (Det), "cat" (N)
  Predict: VP → V PP
  Match: "sat" (V)
  Predict: PP → P NP
  Match: "on" (P)
  Predict: NP → Det N
  Match: "the" (Det), "mat" (N)
  Done!

LR Parsing (Bottom-Up):
  You read words and combine them into phrases.
  
  "The cat sat on the mat."
  
  Shift: The
  Shift: cat
  Reduce: Det N → NP
  Reduce: NP → Subject
  Shift: sat
  Shift: on
  Shift: the
  Shift: mat
  Reduce: Det N → NP
  Reduce: P NP → PP
  Reduce: V PP → VP
  Reduce: Subject VP → Sentence
  Accept!

Both produce the same parse tree.
Different strategies.
""")

# THE BIG PICTURE
print("""
=== The Big Picture ===

Parsing:
  - Second phase of compiler.
  - Analyzes syntax.
  - Builds parse tree.

LL:
  - Top-down.
  - Predictive.
  - Hand-written.
  - Simpler.
  - Less powerful.

LR:
  - Bottom-up.
  - Shift-reduce.
  - Tool-generated.
  - More complex.
  - More powerful.

Key facts:
  - LL(1) is the most common LL.
  - LALR(1) is the most common LR.
  - Yacc/Bison use LALR(1).
  - ANTLR uses LL(*).
  - All handle deterministic CFLs.

=== Compiler Pipeline ===

Source → Lexer → Tokens → Parser → AST → Codegen
         (Type 3)        (Type 2)     (Type 0)

Lexer: Regular expressions (Type 3).
Parser: Context-free grammar (Type 2).
Codegen: Turing machine (Type 0).

The parser is the bridge between
simple tokens and complex syntax.
""")

# PARSING IN CODE
print("=== Parsing in Code: Simple Example ===")

class SimpleLLParser:
    """A simple LL(1) parser for arithmetic expressions."""
    def __init__(self):
        # Grammar:
        #   E → T E'
        #   E' → + T E' | ε
        #   T → F T'
        #   T' → * F T' | ε
        #   F → ( E ) | id
        self.grammar = {
            'E': [['T', "E'"]],
            "E'": [['+', 'T', "E'"], []],
            'T': [['F', "T'"]],
            "T'": [['*', 'F', "T'"], []],
            'F': [['(', 'E', ')'], ['id']],
        }
    
    def parse(self, tokens):
        """Parse tokens (LL(1) table-driven)."""
        # Simplified parsing table
        table = {
            ('E', 'id'): ['T', "E'"],
            ('E', '('): ['T', "E'"],
            ("E'", '+'): ['+', 'T', "E'"],
            ("E'", '$'): [],
            ("E'", ')'): [],
            ('T', 'id'): ['F', "T'"],
            ('T', '('): ['F', "T'"],
            ("T'", '+'): [],
            ("T'", '*'): ['*', 'F', "T'"],
            ("T'", ')'): [],
            ("T'", '$'): [],
            ('F', 'id'): ['id'],
            ('F', '('): ['(', 'E', ')'],
        }
        
        stack = ['$', 'E']
        tokens = tokens + ['$']
        pos = 0
        steps = []
        
        while stack:
            top = stack[-1]
            current = tokens[pos]
            
            if top == current:
                # Match
                steps.append(f"Match {top}")
                stack.pop()
                pos += 1
                if top == '$':
                    return True, steps
            elif top in self.grammar:
                # Expand
                rule = table.get((top, current))
                if rule is None:
                    return False, steps + [f"Error: no rule for ({top}, {current})"]
                stack.pop()
                # Push in reverse
                for symbol in reversed(rule):
                    stack.append(symbol)
                steps.append(f"{top} → {' '.join(rule) if rule else 'ε'}")
            else:
                return False, steps + [f"Error: unexpected {current}"]
        
        return False, steps


# Example: parse "id + id * id"
parser = SimpleLLParser()
tokens = ['id', '+', 'id', '*', 'id']

print("LL(1) parsing of 'id + id * id':")
print("Grammar:")
print("  E → T E'")
print("  E' → + T E' | ε")
print("  T → F T'")
print("  T' → * F T' | ε")
print("  F → ( E ) | id")
print()

success, steps = parser.parse(tokens)
print(f"Result: {'✓ ACCEPT' if success else '✗ REJECT'}")
print("\nSteps:")
for i, step in enumerate(steps, 1):
    print(f"  {i}. {step}")

print("""
=== Key Observations ===

1. TOP-DOWN
   Start with E (start symbol).
   Expand nonterminals.
   Match terminals.
   Build tree top-down.

2. PREDICTIVE
   Use parsing table.
   No backtracking.
   One symbol lookahead.

3. LL(1)
   Left-to-right scan.
   Leftmost derivation.
   1 symbol lookahead.

4. STACK
   Holds expected symbols.
   Top of stack = next expected.
   Match or expand.

5. SIMPLE
   Easy to understand.
   Easy to implement.
   Good for hand-written parsers.

=== LR Parsing ===

For comparison, LR parsing would:
  1. Shift tokens onto stack.
  2. Reduce when a rule is recognized.
  3. Build tree bottom-up.

More powerful but more complex.
""")

📝 Grammar Basics

🎯 Context-Free Grammars

Parsing operates on context-free grammars (CFGs). Understanding CFGs, derivations, and parse trees is essential for understanding parsing algorithms.

Grammar Concepts

CFG: 4-tuple (V, Σ, R, S). Derivation: Sequence of rule applications. Leftmost: Always expand leftmost nonterminal. Rightmost: Always expand rightmost. Parse tree: Tree representation. Ambiguity: Multiple parse trees.

📝 CFG🔄 Derivation🌳 Parse tree⚠️ Ambiguity

# Grammar Basics for Parsing
print("=" * 60)
print("GRAMMAR BASICS FOR PARSING")
print("=" * 60)

print("""
=== Context-Free Grammars ===

A CFG is a 4-tuple:
  G = (V, Σ, R, S)

where:
  V: nonterminals (variables)
  Σ: terminals (tokens)
  R: production rules (A → α)
  S: start symbol

Example:
  E → E + T | T
  T → T * F | F
  F → ( E ) | id

V = {E, T, F}
Σ = {+, *, (, ), id}
S = E
R = the rules above

=== Derivations ===

A derivation is a sequence of rule applications:
  S ⇒ α₁ ⇒ α₂ ⇒ ... ⇒ w

Leftmost derivation:
  Always expand the leftmost nonterminal.
  Notation: ⇒_lm

Rightmost derivation:
  Always expand the rightmost nonterminal.
  Notation: ⇒_rm

Example (leftmost):
  E ⇒ E + T
    ⇒ T + T
    ⇒ F + T
    ⇒ id + T
    ⇒ id + T * F
    ⇒ id + F * F
    ⇒ id + id * F
    ⇒ id + id * id

Example (rightmost):
  E ⇒ E + T
    ⇒ E + T * F
    ⇒ E + T * id
    ⇒ E + F * id
    ⇒ E + id * id
    ⇒ T + id * id
    ⇒ F + id * id
    ⇒ id + id * id

Both produce the same string.

=== Parse Trees ===

A parse tree shows the structure:
  - Root: start symbol.
  - Internal: nonterminals.
  - Leaves: terminals.
  - Children: RHS of production.

Example for "id + id * id":

        E
       /|\
      E + T
      |   /|\
      T  T * F
      |  |   |
      F  F  id
      |  |
     id id

The yield is the derived string.

=== Ambiguity ===

A grammar is AMBIGUOUS if some string has
two or more different parse trees.

Example:
  E → E + E | E * E | id

String "id + id * id" has two parse trees:
  (id + id) * id
  id + (id * id)

Ambiguity is bad for parsing:
  - Multiple meanings.
  - Parsers need to choose.
  - Usually resolved by precedence.

=== Parsing and Derivations ===

LL parsing:
  - Top-down.
  - Leftmost derivation.
  - Predict next rule.

LR parsing:
  - Bottom-up.
  - Rightmost derivation in reverse.
  - Reduce when rule is recognized.

Both produce a parse tree.

=== Grammar Transformations ===

To make grammars suitable for parsing:

1. ELIMINATE LEFT RECURSION
   A → A α | β
   becomes:
   A → β A'
   A' → α A' | ε

2. LEFT FACTORING
   A → α β₁ | α β₂
   becomes:
   A → α A'
   A' → β₁ | β₂

3. ELIMINATE AMBIGUITY
   Use precedence and associativity.

4. ELIMINATE ε-PRODUCTIONS
   If needed for LL(1).

These transformations preserve the language.
""")

# GRAMMAR TRANSFORMATIONS IN CODE
print("=== Grammar Transformations in Code ===")

class Grammar:
    """Simple grammar representation."""
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules  # dict: nonterminal -> list of productions
    
    def __repr__(self):
        lines = []
        for lhs in sorted(self.rules.keys()):
            for rhs in self.rules[lhs]:
                rhs_str = ' '.join(rhs) if rhs else 'ε'
                lines.append(f"  {lhs} → {rhs_str}")
        return '\n'.join(lines)


# Example: Ambiguous grammar
ambiguous = Grammar('E', {
    'E': [['E', '+', 'E'], ['E', '*', 'E'], ['id']],
})

print("Ambiguous grammar:")
print(ambiguous)

# Unambiguous grammar
unambiguous = Grammar('E', {
    'E': [['E', '+', 'T'], ['T']],
    'T': [['T', '*', 'F'], ['F']],
    'F': [['(', 'E', ')'], ['id']],
})

print("\nUnambiguous grammar:")
print(unambiguous)

# Left recursion elimination
left_recursive = Grammar('E', {
    'E': [['E', '+', 'T'], ['T']],
    'T': [['T', '*', 'F'], ['F']],
    'F': [['(', 'E', ')'], ['id']],
})

print("\nLeft recursion example:")
print("  E → E + T | T")
print("\nAfter elimination:")
print("  E → T E'")
print("  E' → + T E' | ε")

print("""
=== Key Observations ===

1. AMBIGUITY
   Ambiguous grammars have multiple parse trees.
   Bad for parsing.
   Resolve with precedence/associativity.

2. LEFT RECURSION
   A → A α is left recursive.
   Bad for LL parsing (infinite loop).
   Eliminate for LL.

3. LEFT FACTORING
   A → α β₁ | α β₂
   Factor out common prefix.
   Needed for LL(1).

4. UNAMBIGUOUS GRAMMAR
   Use layered grammar (E, T, F).
   Enforces precedence.
   Standard for expressions.

5. PARSING
   LL: needs no left recursion.
   LR: handles left recursion.
   Both need unambiguous grammar.

=== Grammar Design for Parsing ===

For LL(1):
  - No left recursion.
  - No common prefixes.
  - FIRST/FOLLOW disjoint.

For LR(1):
  - Handles left recursion.
  - Handles common prefixes.
  - More flexible.

This is why LR is more powerful.
""")

# SUMMARY
print("""
=== Summary ===

CFG:
  G = (V, Σ, R, S)

Derivations:
  Leftmost: expand leftmost nonterminal.
  Rightmost: expand rightmost nonterminal.

Parse trees:
  Root: start symbol.
  Internal: nonterminals.
  Leaves: terminals.

Ambiguity:
  Multiple parse trees for same string.
  Bad for parsing.

Transformations:
  Eliminate left recursion.
  Left factoring.
  Eliminate ambiguity.

LL vs LR:
  LL: top-down, leftmost, predictive.
  LR: bottom-up, rightmost (reverse), shift-reduce.

Key insight:
  Grammar design is crucial for parsing.
  LL needs more restrictions.
  LR is more flexible.
  Both need unambiguous grammar.
""")

📊 FIRST and FOLLOW

🎯 The Key Sets for LL Parsing

FIRST and FOLLOW sets are essential for constructing LL(1) parsing tables. They tell the parser which rule to apply based on the next input token.

FIRST and FOLLOW

FIRST(α): Terminals that can begin strings derived from α. FOLLOW(A): Terminals that can appear immediately after A. ε: Included in FIRST if α can derive ε. $: Included in FOLLOW of start symbol. Table: M[A, a] = rule. Disjoint: FIRST and FOLLOW must not conflict.

FIRSTFOLLOW📊 TableLL(1)

# FIRST and FOLLOW Sets
print("=" * 60)
print("FIRST AND FOLLOW SETS")
print("=" * 60)

print("""
=== FIRST Sets ===

FIRST(α) = set of terminals that can begin
           strings derived from α.

Definition:
  FIRST(α) = { a | α ⇒* aβ for some β }
  
  Also includes ε if α ⇒* ε.

Rules:
  1. FIRST(a) = {a} for terminal a.
  2. FIRST(ε) = {ε}.
  3. FIRST(A) = ∪ FIRST(α) for all A → α.
  4. FIRST(X₁X₂...Xₙ):
     - Add FIRST(X₁) - {ε}.
     - If ε ∈ FIRST(X₁), add FIRST(X₂) - {ε}.
     - Continue...
     - If all Xᵢ have ε, add ε.

Example:
  E → T E'
  E' → + T E' | ε
  T → F T'
  T' → * F T' | ε
  F → ( E ) | id

FIRST(E) = FIRST(T) = FIRST(F) = { (, id }
FIRST(E') = { +, ε }
FIRST(T') = { *, ε }

=== FOLLOW Sets ===

FOLLOW(A) = set of terminals that can appear
            immediately after A in some sentential form.

Definition:
  FOLLOW(A) = { a | S ⇒* αAaβ for some α, β }
  
  Also includes $ if A can be at the end.

Rules:
  1. $ ∈ FOLLOW(S) (S = start symbol).
  2. For A → αBβ:
     - Add FIRST(β) - {ε} to FOLLOW(B).
     - If ε ∈ FIRST(β), add FOLLOW(A) to FOLLOW(B).
  3. For A → αB:
     - Add FOLLOW(A) to FOLLOW(B).

Example (continued):
  FOLLOW(E) = { $, ) }
  FOLLOW(E') = FOLLOW(E) = { $, ) }
  FOLLOW(T) = FIRST(E') - {ε} ∪ FOLLOW(E)
            = { + } ∪ { $, ) } = { +, $, ) }
  FOLLOW(T') = FOLLOW(T) = { +, $, ) }
  FOLLOW(F) = FIRST(T') - {ε} ∪ FOLLOW(T)
            = { * } ∪ { +, $, ) } = { *, +, $, ) }

=== LL(1) Parsing Table ===

For each rule A → α:
  For each a ∈ FIRST(α) - {ε}:
    M[A, a] = A → α
  If ε ∈ FIRST(α):
    For each b ∈ FOLLOW(A):
      M[A, b] = A → α

Example (continued):

  Nonterminal | id      | +       | *       | (       | )       | $
  ────────────┼─────────┼─────────┼─────────┼─────────┼─────────┼────────
  E           | E→TE'   |         |         | E→TE'   |         |
  E'          |         | E'→+TE' |         |         | E'→ε    | E'→ε
  T           | T→FT'   |         |         | T→FT'   |         |
  T'          |         | T'→ε    | T'→*FT' |         | T'→ε    | T'→ε
  F           | F→id    |         |         | F→(E)   |         |

This table is LL(1) — no conflicts!

=== Conflicts ===

A grammar is LL(1) if the table has no conflicts.

Conflict types:
  1. FIRST-FIRST conflict:
     Two rules have overlapping FIRST sets.
     A → α | β with FIRST(α) ∩ FIRST(β) ≠ ∅.
  
  2. FIRST-FOLLOW conflict:
     A rule has ε in FIRST and
     FOLLOW(A) overlaps with FIRST of another rule.
     A → α | ε with FIRST(α) ∩ FOLLOW(A) ≠ ∅.

Example of conflict:
  S → if E then S | if E then S else S | other

  FIRST(if E then S) = {if}
  FIRST(if E then S else S) = {if}
  Conflict! Both start with "if".

Solution: Left factoring.
  S → if E then S S'
  S' → else S | ε

=== Computing FIRST and FOLLOW in Code ===
""")

# FIRST AND FOLLOW IN CODE
print("=== Computing FIRST and FOLLOW ===")

class Grammar:
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules
        self.nonterminals = set(rules.keys())
        self.terminals = set()
        for prods in rules.values():
            for rhs in prods:
                for s in rhs:
                    if s not in self.nonterminals:
                        self.terminals.add(s)
    
    def first(self, symbol):
        """Compute FIRST of a symbol."""
        if symbol in self.terminals or symbol == 'ε':
            return {symbol}
        
        result = set()
        for rhs in self.rules.get(symbol, []):
            if not rhs:
                result.add('ε')
            else:
                for s in rhs:
                    first_s = self.first(s)
                    result |= (first_s - {'ε'})
                    if 'ε' not in first_s:
                        break
                else:
                    result.add('ε')
        return result
    
    def first_of_string(self, string):
        """Compute FIRST of a string."""
        result = set()
        for s in string:
            first_s = self.first(s)
            result |= (first_s - {'ε'})
            if 'ε' not in first_s:
                break
        else:
            result.add('ε')
        return result
    
    def follow(self, symbol):
        """Compute FOLLOW of a nonterminal."""
        follow = {self.start: {'$'}}
        for nt in self.nonterminals:
            if nt not in follow:
                follow[nt] = set()
        
        changed = True
        while changed:
            changed = False
            for lhs, prods in self.rules.items():
                for rhs in prods:
                    for i, s in enumerate(rhs):
                        if s in self.nonterminals:
                            rest = rhs[i+1:]
                            first_rest = self.first_of_string(rest)
                            follow[s] |= (first_rest - {'ε'})
                            if 'ε' in first_rest:
                                follow[s] |= follow[lhs]
                            changed = True
        return follow
    
    def ll1_table(self):
        """Build LL(1) parsing table."""
        table = {}
        first_sets = {}
        follow_sets = self.follow(None) if False else {}
        
        # Compute FOLLOW
        follow_sets = {self.start: {'$'}}
        for nt in self.nonterminals:
            follow_sets.setdefault(nt, set())
        
        changed = True
        while changed:
            changed = False
            for lhs, prods in self.rules.items():
                for rhs in prods:
                    for i, s in enumerate(rhs):
                        if s in self.nonterminals:
                            rest = rhs[i+1:]
                            first_rest = self.first_of_string(rest)
                            old = len(follow_sets[s])
                            follow_sets[s] |= (first_rest - {'ε'})
                            if 'ε' in first_rest:
                                follow_sets[s] |= follow_sets[lhs]
                            if len(follow_sets[s]) > old:
                                changed = True
        
        for lhs, prods in self.rules.items():
            for rhs in prods:
                first_rhs = self.first_of_string(rhs)
                for a in first_rhs - {'ε'}:
                    table[(lhs, a)] = rhs
                if 'ε' in first_rhs:
                    for b in follow_sets[lhs]:
                        table[(lhs, b)] = rhs
        
        return table, follow_sets


# Example grammar
g = Grammar('E', {
    'E': [['T', "E'"]],
    "E'": [['+', 'T', "E'"], []],
    'T': [['F', "T'"]],
    "T'": [['*', 'F', "T'"], []],
    'F': [['(', 'E', ')'], ['id']],
})

print("Grammar:")
print("  E → T E'")
print("  E' → + T E' | ε")
print("  T → F T'")
print("  T' → * F T' | ε")
print("  F → ( E ) | id")

print("\nFIRST sets:")
for nt in ['E', "E'", 'T', "T'", 'F']:
    first = g.first(nt)
    print(f"  FIRST({nt}) = {sorted(first)}")

print("\nFOLLOW sets:")
# Compute FOLLOW
follow = {g.start: {'$'}}
for nt in g.nonterminals:
    follow.setdefault(nt, set())

changed = True
while changed:
    changed = False
    for lhs, prods in g.rules.items():
        for rhs in prods:
            for i, s in enumerate(rhs):
                if s in g.nonterminals:
                    rest = rhs[i+1:]
                    first_rest = g.first_of_string(rest)
                    old = len(follow[s])
                    follow[s] |= (first_rest - {'ε'})
                    if 'ε' in first_rest:
                        follow[s] |= follow[lhs]
                    if len(follow[s]) > old:
                        changed = True

for nt in ['E', "E'", 'T', "T'", 'F']:
    print(f"  FOLLOW({nt}) = {sorted(follow[nt])}")

# LL(1) table
table, _ = g.ll1_table()
print("\nLL(1) Parsing Table:")
terminals = sorted(g.terminals | {'$'})
header = "  " + " | ".join(f"{t:8s}" for t in terminals)
print(header)
print("-" * len(header))

for nt in ['E', "E'", 'T', "T'", 'F']:
    row = f"  {nt:8s} | "
    for t in terminals:
        rule = table.get((nt, t))
        if rule is None:
            row += "        | "
        else:
            rhs = ' '.join(rule) if rule else 'ε'
            row += f"{rhs:8s} | "
    print(row)

print("""
=== Key Observations ===

1. FIRST
   Terminals that can start a derivation.
   Includes ε if derivation can be empty.

2. FOLLOW
   Terminals that can follow a nonterminal.
   Includes $ for start symbol.

3. LL(1) TABLE
   For each (nonterminal, terminal):
     M[A, a] = rule to apply.
   No conflicts means LL(1).

4. CONFLICTS
   FIRST-FIRST: overlapping FIRST sets.
   FIRST-FOLLOW: ε and FOLLOW overlap.
   Resolve by grammar transformation.

5. COMPUTATION
   Iterative fixed-point computation.
   FIRST: bottom-up.
   FOLLOW: top-down with iterations.
""")

# SUMMARY
print("""
=== Summary ===

FIRST(α):
  Set of terminals that can begin strings derived from α.
  Includes ε if α ⇒* ε.

FOLLOW(A):
  Set of terminals that can appear after A.
  Includes $ if A can be at the end.

LL(1) Table:
  M[A, a] = rule to apply.
  No conflicts means LL(1).

Conflicts:
  FIRST-FIRST: overlapping FIRST sets.
  FIRST-FOLLOW: ε and FOLLOW overlap.

Grammar transformations:
  Left factoring.
  Eliminate left recursion.
  Eliminate ambiguity.

Key insight:
  FIRST and FOLLOW are the foundation
  of LL(1) parsing.
  They determine which rule to apply.
  No conflicts means LL(1).
""")

⬇️ LL(1) Parsing

🎯 Predictive Top-Down Parsing

LL(1) parsing is a top-down parsing technique that uses one symbol of lookahead to predict which rule to apply. It's simple, efficient, and widely used for hand-written parsers.

LL(1) Parsing Facts

Top-down: Start with start symbol. Predictive: Use table, no backtracking. Lookahead: 1 symbol. Stack: Holds expected symbols. Table: M[A, a] = rule. Restrictions: No left recursion, no conflicts.

⬇️ Top-down🔍 Predictive📊 Table-driven⚡ O(n)

# LL(1) Parsing
print("=" * 60)
print("LL(1) PARSING")
print("=" * 60)

print("""
=== The Algorithm ===

Input: Token stream w, LL(1) parsing table M.
Output: Parse tree or error.

Data structures:
  - Stack: holds expected symbols.
  - Input: token stream.
  - Table: M[A, a] = rule.

Algorithm:
  1. Initialize stack with $ and S.
  2. Set input pointer to first token.
  3. Repeat:
     a. Let X = top of stack.
     b. Let a = current input token.
     c. If X = a = $: ACCEPT.
     d. If X = a: POP, advance input.
     e. If X is nonterminal:
        - If M[X, a] = X → Y₁...Yₖ:
          POP, PUSH Yₖ...Y₁ (reverse).
        - Else: ERROR.
     f. Else: ERROR.

=== Example ===

Grammar:
  E → T E'
  E' → + T E' | ε
  T → F T'
  T' → * F T' | ε
  F → ( E ) | id

Input: id + id * id

Step | Stack          | Input           | Action
─────┼────────────────┼─────────────────┼──────────────────
1    | $ E            | id + id * id $  | E → T E'
2    | $ E' T         | id + id * id $  | T → F T'
3    | $ E' T' F      | id + id * id $  | F → id
4    | $ E' T' id     | id + id * id $  | Match id
5    | $ E' T'        | + id * id $     | T' → ε
6    | $ E'           | + id * id $     | E' → + T E'
7    | $ E' T +       | + id * id $     | Match +
8    | $ E' T         | id * id $       | T → F T'
9    | $ E' T' F      | id * id $       | F → id
10   | $ E' T' id     | id * id $       | Match id
11   | $ E' T'        | * id $          | T' → * F T'
12   | $ E' T' F *    | * id $          | Match *
13   | $ E' T' F      | id $            | F → id
14   | $ E' T' id     | id $            | Match id
15   | $ E' T'        | $               | T' → ε
16   | $ E'           | $               | E' → ε
17   | $              | $               | ACCEPT

=== Advantages ===

1. SIMPLE
   Easy to understand.
   Easy to implement.

2. EFFICIENT
   O(n) time.
   No backtracking.

3. ERROR DETECTION
   Detects errors immediately.
   Good error messages.

4. HAND-WRITTEN
   Easy to write by hand.
   Recursive descent.

5. PREDICTIVE
   No guessing.
   Deterministic.

=== Disadvantages ===

1. LESS POWERFUL
   Can't handle all CFGs.
   Restricted to LL(1).

2. LEFT RECURSION
   Must eliminate.
   Inconvenient.

3. LEFT FACTORING
   Must factor common prefixes.
   Inconvenient.

4. CONFLICTS
   Some grammars aren't LL(1).
   Need transformation.

5. MEMORY
   Stack can grow.
   But usually small.

=== Recursive Descent ===

LL(1) can be implemented as recursive descent:

  def parse_E():
      parse_T()
      parse_E_prime()
  
  def parse_E_prime():
      if lookahead == '+':
          match('+')
          parse_T()
          parse_E_prime()
      # else: epsilon (do nothing)
  
  def parse_T():
      parse_F()
      parse_T_prime()
  
  def parse_T_prime():
      if lookahead == '*':
          match('*')
          parse_F()
          parse_T_prime()
  
  def parse_F():
      if lookahead == 'id':
          match('id')
      elif lookahead == '(':
          match('(')
          parse_E()
          match(')')
      else:
          error()

This is the standard way to write
hand-written LL(1) parsers.

=== LL(k) ===

LL(k) uses k symbols of lookahead.
More powerful than LL(1).
But still less powerful than LR.
Used in some tools (ANTLR uses LL(*)).
""")

# LL1 PARSER IN CODE
print("=== LL(1) Parser in Code ===")

class LL1Parser:
    """A complete LL(1) parser."""
    def __init__(self, start, rules, table):
        self.start = start
        self.rules = rules
        self.table = table  # (nonterminal, terminal) -> production
    
    def parse(self, tokens):
        """Parse tokens. Returns (success, steps)."""
        stack = ['$', self.start]
        tokens = tokens + ['$']
        pos = 0
        steps = []
        
        while stack:
            top = stack[-1]
            current = tokens[pos]
            
            if top == current:
                steps.append(f"Match {top}")
                stack.pop()
                pos += 1
                if top == '$':
                    return True, steps
            elif top in self.rules:
                rule = self.table.get((top, current))
                if rule is None:
                    return False, steps + [f"Error: no rule for ({top}, {current})"]
                stack.pop()
                for symbol in reversed(rule):
                    stack.append(symbol)
                rule_str = ' '.join(rule) if rule else 'ε'
                steps.append(f"{top} → {rule_str}")
            else:
                return False, steps + [f"Error: unexpected {current}"]
        
        return False, steps


# Build LL(1) table for arithmetic grammar
rules = {
    'E': [['T', "E'"]],
    "E'": [['+', 'T', "E'"], []],
    'T': [['F', "T'"]],
    "T'": [['*', 'F', "T'"], []],
    'F': [['(', 'E', ')'], ['id']],
}

# Manually build table (computed from FIRST/FOLLOW)
table = {
    ('E', 'id'): ['T', "E'"],
    ('E', '('): ['T', "E'"],
    ("E'", '+'): ['+', 'T', "E'"],
    ("E'", ')'): [],
    ("E'", '$'): [],
    ('T', 'id'): ['F', "T'"],
    ('T', '('): ['F', "T'"],
    ("T'", '+'): [],
    ("T'", '*'): ['*', 'F', "T'"],
    ("T'", ')'): [],
    ("T'", '$'): [],
    ('F', 'id'): ['id'],
    ('F', '('): ['(', 'E', ')'],
}

parser = LL1Parser('E', rules, table)

print("LL(1) Parser for arithmetic expressions:")
print("Grammar:")
for lhs, prods in rules.items():
    for rhs in prods:
        rhs_str = ' '.join(rhs) if rhs else 'ε'
        print(f"  {lhs} → {rhs_str}")

# Test cases
test_cases = [
    (['id'], True),
    (['id', '+', 'id'], True),
    (['id', '*', 'id'], True),
    (['id', '+', 'id', '*', 'id'], True),
    (['(', 'id', '+', 'id', ')', '*', 'id'], True),
    (['id', '+'], False),
    (['+', 'id'], False),
]

print("\nParsing tests:")
for tokens, expected in test_cases:
    success, steps = parser.parse(tokens)
    status = "✓" if success == expected else "✗"
    input_str = ' '.join(tokens)
    print(f"  {status} '{input_str}' → {'ACCEPT' if success else 'REJECT'}")

# Detailed trace for one input
print("\nDetailed trace for 'id + id * id':")
success, steps = parser.parse(['id', '+', 'id', '*', 'id'])
for i, step in enumerate(steps, 1):
    print(f"  {i:2d}. {step}")

print("""
=== Key Observations ===

1. TABLE-DRIVEN
   Parsing table determines actions.
   No hard-coded logic.

2. PREDICTIVE
   One symbol lookahead.
   Deterministic.

3. EFFICIENT
   O(n) time.
   O(depth) space.

4. RECURSIVE DESCENT
   Can be implemented recursively.
   Easy to hand-write.

5. ERROR DETECTION
   Errors detected immediately.
   Can give good messages.

=== LL(1) Restrictions ===

1. NO LEFT RECURSION
   A → A α | β
   Must eliminate.

2. NO COMMON PREFIXES
   A → α β₁ | α β₂
   Must left factor.

3. NO CONFLICTS
   FIRST/FOLLOW must be disjoint.
   Otherwise, not LL(1).

These restrictions make LL(1) less
powerful than LR(1).
But LL(1) is simpler and more intuitive.
""")

# SUMMARY
print("""
=== Summary ===

LL(1) Parsing:
  - Top-down.
  - Predictive.
  - One symbol lookahead.
  - Table-driven.

Algorithm:
  1. Stack initialized with $ and S.
  2. Compare top of stack with input.
  3. Match or expand.
  4. Accept when both are $.

Advantages:
  - Simple.
  - Efficient.
  - Good error messages.
  - Easy to hand-write.

Disadvantages:
  - Less powerful.
  - No left recursion.
  - No common prefixes.
  - Conflicts possible.

Implementation:
  - Table-driven.
  - Recursive descent.

Key insight:
  LL(1) is the simplest practical parsing method.
  It's used for hand-written parsers.
  It's less powerful than LR but easier.
  It's the foundation of predictive parsing.
""")

⬆️ LR(0) Parsing

🎯 The Simplest LR Parser

LR(0) parsing is the simplest bottom-up parsing technique. It uses no lookahead and is based on the concept of items and automata.

LR(0) Parsing Facts

Bottom-up: Start with input. Shift-reduce: Shift tokens, reduce rules. Items: Productions with dot. Automaton: States = item sets. No lookahead: LR(0). Restrictions: Conflicts common.

⬆️ Bottom-up🔄 Shift-reduce📊 Items⚙️ Automaton

# LR(0) Parsing
print("=" * 60)
print("LR(0) PARSING")
print("=" * 60)

print("""
=== LR(0) Items ===

An LR(0) ITEM is a production with a dot:
  A → α · β

Meaning: we've seen α, expecting β.

Example: Rule E → E + T

Items:
  E → · E + T    (start)
  E → E · + T    (seen E)
  E → E + · T    (seen E +)
  E → E + T ·    (complete)

=== The Closure Operation ===

CLOSURE(I) for a set of items I:
  1. Start with I.
  2. For each item A → α · B β in I:
     For each rule B → γ:
       Add B → · γ to I.
  3. Repeat until no new items.

Example:
  I = { E → · E + T }
  
  Closure:
    E → · E + T
    E → · T
    T → · T * F
    T → · F
    F → · ( E )
    F → · id

=== The GOTO Operation ===

GOTO(I, X) for a set of items I and symbol X:
  = CLOSURE({ A → α X · β | A → α · X β ∈ I })

Example:
  I = { E → E · + T, E → E · }
  
  GOTO(I, +) = CLOSURE({ E → E + · T })
             = { E → E + · T,
                 T → · T * F, T → · F,
                 F → · ( E ), F → · id }

=== The LR(0) Automaton ===

States: canonical collection of LR(0) item sets.
Transitions: GOTO.

Construction:
  1. Start with CLOSURE({ S' → · S }).
  2. For each state I and symbol X:
     J = GOTO(I, X).
     If J is new, add it.
  3. Repeat until no new states.

=== LR(0) Parsing Table ===

For each state I:
  - If A → α · a β ∈ I (a = terminal):
    ACTION[I, a] = shift J where J = GOTO(I, a).
  - If A → α · ∈ I (A ≠ S'):
    ACTION[I, a] = reduce A → α for all a.
    (This is the LR(0) reduction — no lookahead!)
  - If S' → S · ∈ I:
    ACTION[I, $] = accept.
  - GOTO[I, A] for nonterminal A.

=== Example ===

Grammar:
  0: S' → E
  1: E → E + T
  2: E → T
  3: T → T * F
  4: T → F
  5: F → ( E )
  6: F → id

LR(0) automaton (states):
  I0: S' → · E, E → · E + T, E → · T, T → · T * F, T → · F, F → · ( E ), F → · id
  I1: S' → E ·, E → E · + T
  I2: E → T ·, T → T · * F
  I3: T → F ·
  I4: F → ( · E ), E → · E + T, E → · T, T → · T * F, T → · F, F → · ( E ), F → · id
  I5: F → id ·
  I6: E → E + · T, T → · T * F, T → · F, F → · ( E ), F → · id
  I7: T → T * · F, F → · ( E ), F → · id
  I8: F → ( E · ), E → E · + T
  I9: E → E + T ·, T → T · * F
  I10: T → T * F ·
  I11: F → ( E ) ·

Conflicts:
  I1: shift on +, but also accept on $.
  I2: shift on *, but also reduce E → T.
  I9: shift on *, but also reduce E → E + T.

These are conflicts!
LR(0) is too weak for this grammar.

=== Conflicts ===

SHIFT-REDUCE conflict:
  State has both shift and reduce actions.
  Example: I2 (shift on *, reduce E → T).

REDUCE-REDUCE conflict:
  State has two reduce actions.
  Example: I2 (reduce E → T and T → F).

LR(0) is conflict-prone.
Need lookahead to resolve.
""")

# LR(0) IN CODE
print("=== LR(0) Automaton in Code ===")

class LR0Item:
    def __init__(self, lhs, rhs, dot=0):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"{self.lhs} → {' '.join(rhs)}"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot))
    
    def is_complete(self):
        return self.dot >= len(self.rhs)
    
    def next_symbol(self):
        if self.dot < len(self.rhs):
            return self.rhs[self.dot]
        return None
    
    def advance(self):
        return LR0Item(self.lhs, self.rhs, self.dot + 1)


class LR0Automaton:
    def __init__(self, start, rules):
        self.start = start
        self.rules = rules
        self.states = []
        self.transitions = {}
        self.build()
    
    def closure(self, items):
        closure = set(items)
        changed = True
        while changed:
            changed = False
            for item in list(closure):
                sym = item.next_symbol()
                if sym in self.rules:
                    for rhs in self.rules[sym]:
                        new_item = LR0Item(sym, rhs, 0)
                        if new_item not in closure:
                            closure.add(new_item)
                            changed = True
        return frozenset(closure)
    
    def goto(self, items, symbol):
        next_items = set()
        for item in items:
            if item.next_symbol() == symbol:
                next_items.add(item.advance())
        if not next_items:
            return frozenset()
        return self.closure(next_items)
    
    def build(self):
        start_item = LR0Item("S'", [self.start], 0)
        I0 = self.closure({start_item})
        self.states = [I0]
        self.transitions = {}
        
        queue = [I0]
        visited = {I0}
        
        while queue:
            state = queue.pop(0)
            idx = self.states.index(state)
            
            # Collect symbols
            symbols = set()
            for item in state:
                sym = item.next_symbol()
                if sym:
                    symbols.add(sym)
            
            for sym in symbols:
                next_state = self.goto(state, sym)
                if not next_state:
                    continue
                
                if next_state not in visited:
                    visited.add(next_state)
                    self.states.append(next_state)
                    queue.append(next_state)
                
                next_idx = self.states.index(next_state)
                self.transitions[(idx, sym)] = next_idx
    
    def display(self):
        for i, state in enumerate(self.states):
            print(f"\nState I{i}:")
            for item in sorted(state, key=str):
                print(f"  {item}")
        
        print("\nTransitions:")
        for (src, sym), dst in sorted(self.transitions.items()):
            print(f"  I{src} --{sym}--> I{dst}")


# Example grammar
rules = {
    'E': [['E', '+', 'T'], ['T']],
    'T': [['T', '*', 'F'], ['F']],
    'F': [['(', 'E', ')'], ['id']],
}

print("Grammar:")
for lhs, prods in rules.items():
    for rhs in prods:
        print(f"  {lhs} → {' '.join(rhs)}")

# Build automaton (may have many states, just show a few)
automaton = LR0Automaton('E', rules)
print(f"\nNumber of LR(0) states: {len(automaton.states)}")

# Show first few states
print("\nFirst few states:")
for i, state in enumerate(automaton.states[:5]):
    print(f"\nState I{i}:")
    for item in sorted(state, key=str):
        print(f"  {item}")

print("""
=== Key Observations ===

1. LR(0) ITEMS
   Productions with a dot.
   Dot shows progress.

2. CLOSURE
   Adds items for nonterminals after dot.
   Computes reachable items.

3. GOTO
   Moves dot over a symbol.
   Computes next state.

4. AUTOMATON
   States: item sets.
   Transitions: GOTO.

5. CONFLICTS
   LR(0) often has conflicts.
   Too weak for many grammars.
   Need lookahead (SLR, LALR, LR(1)).

=== LR(0) Limitations ===

1. NO LOOKAHEAD
   Reduces on all terminals.
   Conflicts common.

2. WEAK
   Only handles simple grammars.
   Most real grammars need lookahead.

3. FOUNDATION
   But LR(0) is the foundation.
   SLR, LALR, LR(1) extend it.

4. PEDAGOGICAL
   Important for understanding.
   Simpler than SLR/LALR/LR(1).

5. PRACTICAL
   Rarely used directly.
   Used as a starting point.
""")

# SUMMARY
print("""
=== Summary ===

LR(0) Items:
  A → α · β
  Dot shows progress.

Closure:
  Add items for nonterminals after dot.

GOTO:
  Move dot over symbol.
  Compute next state.

Automaton:
  States: LR(0) item sets.
  Transitions: GOTO.

Parsing table:
  Shift: on terminal after dot.
  Reduce: on complete item.
  Accept: on S' → S ·.
  GOTO: on nonterminal.

Conflicts:
  Shift-reduce: shift and reduce.
  Reduce-reduce: two reduces.

Key insight:
  LR(0) is the foundation of LR parsing.
  Simple but weak.
  Conflicts are common.
  Need lookahead for practical use.
""")

🔍 SLR(1) Parsing

🎯 Simple LR with Lookahead

SLR(1) parsing extends LR(0) by using FOLLOW sets to resolve conflicts. It's simple, practical, and more powerful than LR(0).

SLR(1) Parsing Facts

Extension: LR(0) + FOLLOW sets. Reduce: Only on FOLLOW(A). Lookahead: 1 symbol. Conflicts: Fewer than LR(0). Power: LR(0) ⊊ SLR(1) ⊊ LALR(1). Practical: Used in some tools.

🔍 SLR(1)📊 FOLLOW sets🔄 Reduce on FOLLOW⚡ O(n)

# SLR(1) Parsing
print("=" * 60)
print("SLR(1) PARSING")
print("=" * 60)

print("""
=== SLR(1) = LR(0) + FOLLOW ===

Idea:
  Use FOLLOW sets to resolve conflicts.
  
  Instead of reducing on all terminals,
  reduce only on FOLLOW(A).
  
  This is more precise than LR(0).

=== SLR(1) Parsing Table ===

For each state I:
  1. If A → α · a β ∈ I (a = terminal):
     ACTION[I, a] = shift J where J = GOTO(I, a).
  
  2. If A → α · ∈ I (A ≠ S'):
     For each a ∈ FOLLOW(A):
       ACTION[I, a] = reduce A → α.
     (Only on FOLLOW(A), not all terminals!)
  
  3. If S' → S · ∈ I:
     ACTION[I, $] = accept.
  
  4. GOTO[I, A] for nonterminal A.

=== Example ===

Grammar:
  0: S' → E
  1: E → E + T
  2: E → T
  3: T → T * F
  4: T → F
  5: F → ( E )
  6: F → id

FOLLOW sets:
  FOLLOW(E) = { $, ) }
  FOLLOW(T) = { +, $, ) }
  FOLLOW(F) = { *, +, $, ) }

LR(0) states (from previous):
  I0: S' → · E, E → · E + T, E → · T, T → · T * F, T → · F, F → · ( E ), F → · id
  I1: S' → E ·, E → E · + T
  I2: E → T ·, T → T · * F
  I3: T → F ·
  I4: F → ( · E ), ...
  I5: F → id ·
  I6: E → E + · T, ...
  I7: T → T * · F, ...
  I8: F → ( E · ), E → E · + T
  I9: E → E + T ·, T → T · * F
  I10: T → T * F ·
  I11: F → ( E ) ·

SLR(1) actions:

State I1:
  S' → E ·: accept on $.
  E → E · + T: shift on +.
  Actions: shift +, accept $.
  No conflict!

State I2:
  E → T ·: reduce E → T on FOLLOW(E) = {$, )}.
  T → T · * F: shift on *.
  Actions: shift *, reduce on $ and ).
  No conflict! (shift on *, reduce on $, ))

State I3:
  T → F ·: reduce T → F on FOLLOW(T) = {+, $, )}.
  Actions: reduce on +, $, ).
  No conflict!

State I9:
  E → E + T ·: reduce E → E + T on FOLLOW(E) = {$, )}.
  T → T · * F: shift on *.
  Actions: shift *, reduce on $, ).
  No conflict!

State I2 has:
  E → T · (reduce)
  T → T · * F (shift)
  
  Shift on *, reduce on FOLLOW(E) = {$, )}.
  No overlap! SLR(1) resolves it.

=== Why SLR(1) Works ===

LR(0) reduces on ALL terminals.
SLR(1) reduces only on FOLLOW(A).

This is more precise:
  - Reduce A → α only when A can be followed by a.
  - Avoids conflicts where a ∉ FOLLOW(A).

=== SLR(1) Limitations ===

SLR(1) can still have conflicts.

Example:
  S → L = R | R
  L → * R | id
  R → L

FOLLOW sets:
  FOLLOW(S) = {$}
  FOLLOW(L) = {=, $}
  FOLLOW(R) = {=, $}

State I2:
  S → L · = R
  R → L ·
  
  Shift on =, reduce R → L on FOLLOW(R) = {=, $}.
  
  Conflict! Shift on =, reduce on =.
  
  But: R → L · should only reduce when
  the context is R, not S → L = R.
  
  SLR(1) doesn't distinguish contexts.
  Need LALR(1) or LR(1) for this.

=== SLR(1) vs LR(0) ===

LR(0): reduce on all terminals.
SLR(1): reduce on FOLLOW(A).

SLR(1) is more precise.
But still not enough for all grammars.

=== SLR(1) vs LALR(1) ===

SLR(1): FOLLOW sets (context-free).
LALR(1): lookahead sets (context-sensitive).

LALR(1) is more precise.
LALR(1) handles more grammars.

=== SLR(1) in Practice ===

SLR(1) is:
  - Simple to implement.
  - More powerful than LR(0).
  - Less powerful than LALR(1).
  - Used in some tools.

But LALR(1) is more common.
(Yacc, Bison use LALR(1).)
""")

# SLR(1) IN CODE
print("=== SLR(1) Parser in Code ===")

class SLRParser:
    """SLR(1) parser."""
    def __init__(self, start, rules, follow_sets):
        self.start = start
        self.rules = rules
        self.follow = follow_sets
        self.build_automaton()
    
    def build_automaton(self):
        """Build LR(0) automaton."""
        from itertools import count
        
        # Simplified: use LR(0) automaton
        self.states = []
        self.transitions = {}
        
        # (Build as before, omitted for brevity)
    
    def parse(self, tokens):
        """Parse tokens."""
        # Simplified implementation
        return True


print("SLR(1) parsing example:")
print("  Grammar: E → E + T | T")
print("           T → T * F | F")
print("           F → ( E ) | id")
print()
print("FOLLOW sets:")
print("  FOLLOW(E) = { $, ) }")
print("  FOLLOW(T) = { +, $, ) }")
print("  FOLLOW(F) = { *, +, $, ) }")
print()
print("Conflicts resolved:")
print("  I2: shift on *, reduce on FOLLOW(E) = {$, )}")
print("  I9: shift on *, reduce on FOLLOW(E) = {$, )}")
print("  No conflicts! SLR(1) works.")

print("""
=== Key Observations ===

1. FOLLOW SETS
   Used to restrict reductions.
   Reduce A → α only on FOLLOW(A).

2. FEWER CONFLICTS
   SLR(1) has fewer conflicts than LR(0).
   More grammars are SLR(1).

3. STILL LIMITED
   Some grammars aren't SLR(1).
   Need LALR(1) or LR(1).

4. SIMPLE
   Easy to implement.
   Based on LR(0) automaton.
   Just use FOLLOW sets.

5. PRACTICAL
   Used in some tools.
   But LALR(1) is more common.

=== SLR(1) vs LALR(1) ===

SLR(1):
  - Uses FOLLOW sets.
  - Context-free lookahead.
  - Less powerful.
  - Simpler.

LALR(1):
  - Uses lookahead sets.
  - Context-sensitive lookahead.
  - More powerful.
  - Slightly more complex.

LALR(1) is the practical choice.
(SLR(1) is a stepping stone.)
""")

# SUMMARY
print("""
=== Summary ===

SLR(1):
  - LR(0) + FOLLOW sets.
  - Reduce only on FOLLOW(A).
  - More precise than LR(0).
  - Fewer conflicts.

Parsing table:
  Shift: on terminal after dot.
  Reduce: on FOLLOW(A).
  Accept: on S' → S ·.
  GOTO: on nonterminal.

Advantages:
  - Simple.
  - More powerful than LR(0).
  - Based on LR(0) automaton.

Disadvantages:
  - Still limited.
  - Conflicts possible.
  - Less powerful than LALR(1).

Example:
  E → E + T | T
  T → T * F | F
  F → ( E ) | id
  
  Is SLR(1).
  No conflicts.

Key insight:
  SLR(1) improves on LR(0) by using FOLLOW sets.
  But it's not enough for all grammars.
  LALR(1) and LR(1) are more powerful.
""")

🎯 LALR(1) Parsing

🎯 The Practical LR Parser

LALR(1) parsing (Look-Ahead LR) is the most practical LR parsing method. It's used by Yacc and Bison, and it balances power and table size.

LALR(1) Parsing Facts

LR(1) states: Merged with same core. Lookahead: Context-sensitive. Power: SLR(1) ⊊ LALR(1) ⊊ LR(1). Table size: Same as SLR(1). Used by: Yacc, Bison. Practical: Industry standard.

🎯 LALR(1)📊 Merged states🛠️ Yacc/Bison⚡ Practical

# LALR(1) Parsing
print("=" * 60)
print("LALR(1) PARSING")
print("=" * 60)

print("""
=== LALR(1) = LR(1) with Merged States ===

Idea:
  1. Build LR(1) automaton.
  2. Merge states with the same core.
  3. Result: LALR(1) automaton.

Core: set of LR(0) items in the state.
States with same core are merged.

This reduces the number of states.
Table size: same as SLR(1).
Power: between SLR(1) and LR(1).

=== LR(1) Items ===

LR(1) item: [A → α · β, a]
  a is the lookahead symbol.

Meaning: we've seen α, expecting β,
         and a can follow A.

Closure for LR(1):
  For [A → α · B β, a]:
    For each rule B → γ:
      For each b ∈ FIRST(βa):
        Add [B → · γ, b].

This is more precise than LR(0).

=== LALR(1) Construction ===

1. Build LR(1) automaton (canonical).
2. Group states by core (LR(0) items).
3. Merge states in each group.
4. Lookaheads are unioned.

Result: LALR(1) automaton.
States: fewer than LR(1).
Lookaheads: unions of LR(1) lookaheads.

=== Example ===

Grammar:
  S → L = R | R
  L → * R | id
  R → L

LR(1) states:
  I0: S' → · S, $
      S → · L = R, $
      S → · R, $
      L → · * R, =
      L → · id, =
      R → · L, $
      L → · * R, $
      L → · id, $
  
  I2: S → L · = R, $
      R → L ·, $
  
  I5: L → id ·, =
      L → id ·, $

Wait, let me redo this.

Actually, LR(1) states:
  I0: S' → · S, $
      S → · L = R, $
      S → · R, $
      L → · * R, =
      L → · id, =
      R → · L, $
      L → · * R, $
      L → · id, $
  
  I2: S → L · = R, $
      R → L ·, $
  
  I3: S → R ·, $
  
  I4: L → * · R, =
      R → · L, =
      L → · * R, =
      L → · id, =
  
  I5: L → id ·, =
      L → id ·, $
  
  Wait, I5 has two items with different lookaheads.
  Actually, in LR(1), they're in the same state
  because they have the same core.
  
  Hmm, let me reconsider.
  
  Actually, I5 (LR(1)):
    L → id ·, =
    L → id ·, $
  
  These can be merged (same core).
  
  LALR(1) merges I5's lookaheads:
    L → id ·, {=, $}
  
  This is correct.

  I6: S → L = · R, $
      R → · L, $
      L → · * R, $
      L → · id, $
  
  I7: L → * R ·, =
  
  I8: R → L ·, =
  
  I9: S → L = R ·, $

Now, merge states with same core:
  I5 (L → id ·) with lookaheads = and $.
  I8 (R → L ·) with lookahead =.
  I2 (S → L · = R, R → L ·) with lookaheads $ and $.

Wait, I2 and I8 have different cores:
  I2: S → L · = R, R → L ·
  I8: R → L ·

They're different. Don't merge.

I5 (L → id ·) is unique.

Hmm, this grammar is LALR(1) but not SLR(1).
Let me check.

SLR(1) had a conflict in I2:
  S → L · = R (shift on =)
  R → L · (reduce on FOLLOW(R) = {=, $})
  Conflict! Shift and reduce on =.

LALR(1) resolves it:
  I2 has:
    S → L · = R, $
    R → L ·, $
  
  Reduce R → L only on $ (not on =).
  Shift on =.
  No conflict!

So LALR(1) handles this grammar.
SLR(1) doesn't.

=== LALR(1) vs SLR(1) ===

SLR(1): uses FOLLOW sets.
LALR(1): uses lookahead sets (more precise).

LALR(1) resolves more conflicts.
LALR(1) handles more grammars.

=== LALR(1) vs LR(1) ===

LR(1): canonical, most states.
LALR(1): merged states, fewer states.

Table size:
  LR(1): large (can be 10x LALR(1)).
  LALR(1): small (same as SLR(1)).

Power:
  LR(1): most powerful.
  LALR(1): slightly less (rare conflicts).

In practice:
  LALR(1) handles almost all grammars.
  Used by Yacc, Bison.

=== LALR(1) Conflicts ===

LALR(1) can have conflicts that LR(1) doesn't.

Example:
  S → a A d | b B d | a B e | b A e
  A → c
  B → c

This grammar is LR(1) but not LALR(1).
Merging states introduces reduce-reduce conflict.

But such grammars are rare in practice.

=== LALR(1) in Practice ===

Yacc: LALR(1).
Bison: LALR(1).
CUP: LALR(1).
JavaCC: LL(k).

LALR(1) is the industry standard
for parser generators.

=== Advantages ===

1. PRACTICAL
   Handles almost all grammars.
   Used in industry.

2. SMALL TABLES
   Same size as SLR(1).
   Much smaller than LR(1).

3. POWERFUL
   More powerful than SLR(1).
   Handles most real grammars.

4. EFFICIENT
   O(n) parsing.
   Fast.

5. TOOL SUPPORT
   Yacc, Bison, CUP.
   Mature tools.

=== Disadvantages ===

1. CONFLICTS
   Rare conflicts possible.
   Need to resolve.

2. NOT MOST POWERFUL
   LR(1) is more powerful.
   But LALR(1) is sufficient.

3. COMPLEX
   Harder to understand than LL.
   But manageable.
""")

# LALR(1) IN CODE
print("=== LALR(1) Parsing Example ===")

print("""
Grammar: S → L = R | R
         L → * R | id
         R → L

This grammar is LALR(1) but not SLR(1).

SLR(1) conflict:
  State I2: S → L · = R
            R → L ·
  
  Shift on =, reduce on FOLLOW(R) = {=, $}.
  Conflict on =.

LALR(1) resolution:
  State I2: [S → L · = R, $]
            [R → L ·, $]
  
  Shift on =.
  Reduce R → L on $.
  No conflict!

Why? Because LALR(1) lookahead for R → L
is only $, not =.
""")

# SUMMARY
print("""
=== Summary ===

LALR(1):
  - LR(1) with merged states.
  - Same core → merge.
  - Lookaheads unioned.
  - Same table size as SLR(1).
  - Power between SLR(1) and LR(1).

Construction:
  1. Build LR(1) automaton.
  2. Merge states with same core.
  3. Union lookaheads.

Advantages:
  - Practical.
  - Small tables.
  - Powerful.
  - Efficient.
  - Tool support (Yacc, Bison).

Disadvantages:
  - Rare conflicts.
  - Not most powerful.
  - Complex.

Comparison:
  SLR(1): FOLLOW sets.
  LALR(1): lookahead sets.
  LR(1): canonical, most states.

Key insight:
  LALR(1) is the practical choice.
  It's used by Yacc and Bison.
  It handles almost all real grammars.
  It balances power and table size.
  It's the industry standard.
""")

🔬 LR(1) Parsing

🎯 The Most Powerful LR Parser

LR(1) parsing is the most powerful deterministic bottom-up parsing method. It uses one symbol of lookahead in a context-sensitive way, avoiding conflicts that SLR(1) and LALR(1) can't resolve.

LR(1) Parsing Facts

Items: [A → α·β, a] with lookahead. Closure: Uses FIRST(βa). Power: Most powerful deterministic LR. Table size: Can be very large. Conflicts: Rare. Practical: Used in some tools.

🔬 LR(1)📊 Lookahead🏆 Most powerful📈 Large tables

# LR(1) Parsing
print("=" * 60)
print("LR(1) PARSING")
print("=" * 60)

print("""
=== LR(1) Items ===

An LR(1) item is a pair:
  [A → α · β, a]

where:
  A → αβ is a production.
  · is the dot (progress marker).
  a is a terminal (the lookahead).

Meaning:
  "We've seen α, expecting β,
   and after reducing A → αβ,
   the next input should be a."

=== Closure for LR(1) ===

CLOSURE(I) for a set of LR(1) items:
  For each item [A → α · B β, a] in I:
    For each rule B → γ:
      For each b ∈ FIRST(βa):
        Add [B → · γ, b] to I.
  Repeat until no new items.

Key difference from LR(0):
  The lookahead b is computed from FIRST(βa),
  not just FIRST(β).

This is more precise.
The lookahead depends on context.

=== GOTO for LR(1) ===

GOTO(I, X) for a set of LR(1) items I and symbol X:
  = CLOSURE({ [A → α X · β, a] | [A → α · X β, a] ∈ I })

Same as LR(0) but with lookaheads.

=== LR(1) Automaton ===

States: canonical collection of LR(1) item sets.
Transitions: GOTO.

Construction:
  1. Start with CLOSURE({ [S' → · S, $] }).
  2. For each state I and symbol X:
     J = GOTO(I, X).
     If J is new, add it.
  3. Repeat until no new states.

=== LR(1) Parsing Table ===

For each state I:
  1. If [A → α · a β, b] ∈ I (a = terminal):
     ACTION[I, a] = shift J where J = GOTO(I, a).
  
  2. If [A → α ·, a] ∈ I (A ≠ S'):
     ACTION[I, a] = reduce A → α.
     (Only on lookahead a!)
  
  3. If [S' → S ·, $] ∈ I:
     ACTION[I, $] = accept.
  
  4. GOTO[I, A] for nonterminal A.

=== Example ===

Grammar:
  S → L = R | R
  L → * R | id
  R → L

LR(1) states (partial):
  I0: [S' → · S, $]
      [S → · L = R, $]
      [S → · R, $]
      [L → · * R, =]
      [L → · id, =]
      [R → · L, $]
      [L → · * R, $]
      [L → · id, $]
  
  I2: [S → L · = R, $]
      [R → L ·, $]
  
  I8: [R → L ·, =]
  
  Wait, I2 and I8 have different cores:
    I2: S → L · = R, R → L ·
    I8: R → L ·
  
  They're different. Don't merge.
  
  In LALR(1), they're different states.
  In LALR(1), they stay separate.

  I2:
    [S → L · = R, $]  → shift on =
    [R → L ·, $]      → reduce R → L on $
    No conflict!
  
  I8:
    [R → L ·, =]      → reduce R → L on =
    No conflict!

So LR(1) resolves the conflict.
This grammar is LR(1).

=== LR(1) vs LALR(1) ===

LR(1): more states, more precise.
LALR(1): fewer states, less precise.

LR(1) can handle grammars that
LALR(1) can't (rare).

Example:
  S → a A d | b B d | a B e | b A e
  A → c
  B → c

This grammar is LR(1) but not LALR(1).
Merging states introduces reduce-reduce conflict.

In practice, such grammars are rare.
LALR(1) handles almost all real grammars.

=== LR(1) Table Size ===

LR(1) tables can be very large.
Up to 10x LALR(1) in some cases.

This is why LALR(1) is preferred.
Same power (for practical grammars),
smaller tables.

=== LR(k) ===

LR(k) with k > 1:
  More powerful in theory.
  But rarely used in practice.
  LR(1) is sufficient for most grammars.

=== Advantages ===

1. MOST POWERFUL
   Handles most deterministic CFLs.
   Fewer conflicts than SLR/LALR.

2. PRECISE
   Context-sensitive lookahead.
   Resolves conflicts.

3. THEORETICAL
   Important for understanding.
   Basis for LALR(1).

4. FOUNDATION
   LALR(1) is derived from LR(1).
   Understanding LR(1) helps.

=== Disadvantages ===

1. LARGE TABLES
   Many states.
   Memory intensive.

2. COMPLEX
   More complex than LALR(1).
   Harder to implement.

3. RARELY USED
   LALR(1) is more practical.
   LR(1) rarely used directly.

4. TOOL SUPPORT
   Fewer tools use LR(1).
   Most use LALR(1) or LL.
""")

# LR(1) IN CODE
print("=== LR(1) Automaton in Code ===")

class LR1Item:
    def __init__(self, lhs, rhs, dot=0, lookahead='$'):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
        self.lookahead = lookahead
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"[{self.lhs} → {' '.join(rhs)}, {self.lookahead}]"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and
                self.lookahead == other.lookahead)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot, self.lookahead))
    
    def is_complete(self):
        return self.dot >= len(self.rhs)
    
    def next_symbol(self):
        if self.dot < len(self.rhs):
            return self.rhs[self.dot]
        return None
    
    def advance(self):
        return LR1Item(self.lhs, self.rhs, self.dot + 1, self.lookahead)


print("LR(1) items for 'S → L = R | R':")
print()
print("State I0:")
print("  [S' → · S, $]")
print("  [S → · L = R, $]")
print("  [S → · R, $]")
print("  [L → · * R, =]")
print("  [L → · id, =]")
print("  [R → · L, $]")
print("  [L → · * R, $]")
print("  [L → · id, $]")
print()
print("State I2:")
print("  [S → L · = R, $]")
print("  [R → L ·, $]")
print()
print("State I8:")
print("  [R → L ·, =]")
print()
print("I2 and I8 have different cores.")
print("They remain separate in LR(1).")
print("This resolves the conflict.")

print("""
=== Key Observations ===

1. LOOKAHEAD
   Each item has a lookahead.
   More precise than LR(0).

2. CLOSURE
   Uses FIRST(βa).
   Lookahead depends on context.

3. MORE STATES
   LR(1) has more states than LALR(1).
   But fewer conflicts.

4. CONFLICTS
   LR(1) resolves conflicts that
   SLR(1) and LALR(1) can't.

5. PRACTICAL
   LALR(1) is more common.
   LR(1) is a theoretical foundation.

=== LR(1) vs LALR(1) vs SLR(1) ===

SLR(1):
  - FOLLOW sets.
  - Least powerful.
  - Smallest tables.

LALR(1):
  - Lookahead sets (merged).
  - Middle power.
  - Small tables.

LR(1):
  - Lookahead sets (canonical).
  - Most powerful.
  - Large tables.

All are O(n) parsing.
All handle deterministic CFLs.
LR(1) handles the most.
LALR(1) is the most practical.
""")

# SUMMARY
print("""
=== Summary ===

LR(1):
  - Most powerful deterministic LR.
  - Context-sensitive lookahead.
  - Items: [A → α·β, a].

Closure:
  For [A → α·Bβ, a]:
    For B → γ:
      For b ∈ FIRST(βa):
        Add [B → ·γ, b].

Parsing table:
  Shift: on terminal after dot.
  Reduce: on lookahead a.
  Accept: on S' → S·, $.
  GOTO: on nonterminal.

Advantages:
  - Most powerful.
  - Resolves most conflicts.
  - Precise lookahead.

Disadvantages:
  - Large tables.
  - Complex.
  - Rarely used directly.

Comparison:
  LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1).

Key insight:
  LR(1) is the most powerful LR parser.
  It uses context-sensitive lookahead.
  But LALR(1) is more practical.
  LR(1) is a theoretical foundation.
""")

⚠️ Conflicts

🎯 When Parsers Get Confused

Conflicts occur when a parsing table has multiple actions for the same (state, lookahead) pair. They indicate that the grammar is not suitable for that parser type.

Conflict Types

Shift-reduce: Shift or reduce. Reduce-reduce: Two reduces. Cause: Grammar ambiguity or insufficient lookahead. Resolution: Precedence, associativity, grammar rewriting. Tools: Report conflicts. Impact: Parser may choose wrong action.

⚠️ Shift-reduce⚠️ Reduce-reduce🔧 Resolution📊 Precedence

# Conflicts in Parsing
print("=" * 60)
print("CONFLICTS IN PARSING")
print("=" * 60)

print("""
=== What is a Conflict? ===

A conflict occurs when the parsing table
has multiple actions for the same entry.

Two main types:
  1. SHIFT-REDUCE conflict
  2. REDUCE-REDUCE conflict

=== Shift-Reduce Conflict ===

State I has:
  - A shift action on terminal a.
  - A reduce action on terminal a.

Example:
  State I2: E → T · (reduce E → T)
            T → T · * F (shift on *)
  
  If a = *, we can:
    - Shift * (continue parsing T * F)
    - Reduce E → T (treat T as E)
  
  Which is correct?
  Depends on the grammar.

Cause:
  - Ambiguous grammar.
  - Insufficient lookahead.
  - Operator precedence not encoded.

Resolution:
  - Use precedence: shift for higher precedence.
  - Use associativity: reduce for left-associative.
  - Rewrite grammar.
  - Use LR(1) instead of SLR(1)/LALR(1).

=== Reduce-Reduce Conflict ===

State I has:
  - Two reduce actions on terminal a.

Example:
  State I: A → α · (reduce A → α)
           B → β · (reduce B → β)
  
  If both reduce on a, which to choose?

Cause:
  - Grammar ambiguity.
  - Insufficient lookahead.

Resolution:
  - Rewrite grammar.
  - Use LR(1) instead of LALR(1).
  - Choose one rule (usually the first).

=== Example: Dangling Else ===

Grammar:
  S → if E then S
    | if E then S else S
    | other

State after "if E then S":
  S → if E then S ·
  S → if E then S · else S

Conflict:
  Shift on else (continue inner if)
  Reduce S → if E then S (match outer if)

Resolution:
  Shift (else matches nearest if).
  This is the standard convention.

Grammar rewriting:
  S → M | U
  M → if E then M else M | other
  U → if E then S
    | if E then M else U

This grammar is unambiguous.

=== Example: Expression Grammar ===

Ambiguous grammar:
  E → E + E | E * E | id

Conflicts:
  Shift-reduce on +, *.

Resolution using precedence:
  * has higher precedence than +.
  So shift * (higher precedence).
  
  + is left-associative.
  So reduce E → E + E (left-associative).

Resolution using grammar:
  E → E + T | T
  T → T * F | F
  F → ( E ) | id

This grammar is unambiguous.
No conflicts (for LALR(1)).

=== Conflict Resolution Strategies ===

1. PRECEDENCE
   Assign precedence to operators.
   Shift for higher precedence.
   Reduce for lower precedence.

2. ASSOCIATIVITY
   Left-associative: reduce.
   Right-associative: shift.
   Non-associative: error.

3. GRAMMAR REWRITING
   Restructure grammar.
   Eliminate ambiguity.
   Encode precedence in layers.

4. PARSER CHOICE
   Use more powerful parser.
   LR(1) instead of LALR(1).
   LALR(1) instead of SLR(1).

5. TOOL DIRECTIVES
   Yacc/Bison: %left, %right, %nonassoc.
   Precedence declarations.

=== Conflict Reporting ===

Parser generators report conflicts:
  "conflicts: 2 shift/reduce"

Some conflicts are benign:
  - Resolved correctly by default.
  - Don't affect parsing.

Some are serious:
  - Indicate grammar problems.
  - Need resolution.

=== Example: Yacc/Bison ===

%left '+'
%left '*'

%%

E : E '+' E { $$ = $1 + $3; }
  | E '*' E { $$ = $1 * $3; }
  | '(' E ')' { $$ = $2; }
  | ID { $$ = $1; }
  ;

The %left declarations resolve conflicts.
'+' and '*' are left-associative.
'*' has higher precedence (declared later).

=== Why Conflicts Matter ===

1. PARSER CORRECTNESS
   Conflicts can lead to wrong parse.
   Need to resolve correctly.

2. GRAMMAR QUALITY
   Conflicts indicate grammar issues.
   Ambiguity, insufficient structure.

3. TOOL USAGE
   Yacc/Bison report conflicts.
   Need to understand them.

4. PRACTICAL
   Most real grammars have some conflicts.
   Need to resolve them.
""")

# CONFLICT EXAMPLES
print("=== Conflict Examples in Code ===")

print("""
Example 1: Ambiguous expression grammar
  E → E + E | E * E | id

Conflicts:
  Shift-reduce on + and *.

Resolution:
  Use precedence:
    * > +
  Use associativity:
    + left-associative
    * left-associative

Yacc/Bison:
  %left '+'
  %left '*'

Example 2: Dangling else
  S → if E then S | if E then S else S | other

Conflict:
  Shift-reduce on else.

Resolution:
  Shift (else matches nearest if).
  Standard convention.

Grammar rewrite:
  S → M | U
  M → if E then M else M | other
  U → if E then S | if E then M else U

Example 3: Grammar that is LR(1) but not LALR(1)
  S → a A d | b B d | a B e | b A e
  A → c
  B → c

Conflict:
  Reduce-reduce after merging states.

Resolution:
  Use LR(1) instead of LALR(1).
  Or rewrite grammar.

=== Conflict Resolution in Practice ===

1. START WITH UNAMBIGUOUS GRAMMAR
   Layered grammar for expressions.
   E → E + T | T
   T → T * F | F
   F → ( E ) | id

2. USE PRECEDENCE DECLARATIONS
   Yacc/Bison %left, %right, %nonassoc.

3. CHECK CONFLICTS
   Parser generator reports conflicts.
   Investigate and resolve.

4. TEST EXTENSIVELY
   Ensure parser behaves correctly.

=== Summary of Conflicts ===

Shift-reduce:
  - Shift or reduce.
  - Common in expression grammars.
  - Resolve with precedence/associativity.

Reduce-reduce:
  - Two reduces.
  - Indicates ambiguity.
  - Resolve by grammar rewriting.

Resolution:
  - Precedence.
  - Associativity.
  - Grammar rewriting.
  - Parser choice.
  - Tool directives.

Key insight:
  Conflicts are common.
  Most can be resolved.
  Understanding them is essential
  for writing correct grammars.
""")

# SUMMARY
print("""
=== Summary ===

Conflicts:
  - Multiple actions in parsing table.
  - Shift-reduce or reduce-reduce.

Shift-reduce:
  - Shift on a, reduce on a.
  - Common in expressions.
  - Resolve with precedence/associativity.

Reduce-reduce:
  - Two reduces.
  - Indicates ambiguity.
  - Resolve by grammar rewriting.

Resolution:
  1. Precedence.
  2. Associativity.
  3. Grammar rewriting.
  4. Parser choice.
  5. Tool directives.

Examples:
  - Expression grammar: precedence.
  - Dangling else: shift.
  - LR(1) not LALR(1): use LR(1).

Key insight:
  Conflicts are normal.
  Most can be resolved.
  Understanding them is essential.
  Tools report conflicts.
  Resolve them correctly.
""")

📊 Comparison

🎯 LL vs LR vs SLR vs LALR

Comparing the main parsing algorithms: power, complexity, table size, and practical use.

Parser Comparison

LL(1): Top-down, simple. LR(0): Bottom-up, weak. SLR(1): LR(0)+FOLLOW. LALR(1): Practical. LR(1): Most powerful. Canonical LR: Largest.

⬇️ LL(1)⬆️ LR(0)🔍 SLR(1)🎯 LALR(1)🔬 LR(1)

# Comparison of Parsing Algorithms
print("=" * 60)
print("COMPARISON OF PARSING ALGORITHMS")
print("=" * 60)

print("""
=== Power Hierarchy ===

LL(1) ⊊ LL(k) ⊊ LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1) ⊊ LR(k)

Each is strictly more powerful than the previous.

=== Detailed Comparison ===

Aspect          LL(1)      LR(0)      SLR(1)     LALR(1)    LR(1)
────────────────────────────────────────────────────────────────────
Direction       Top-down   Bottom-up  Bottom-up  Bottom-up  Bottom-up
Derivation      Leftmost   Rightmost  Rightmost  Rightmost  Rightmost
Lookahead       1          0          1          1          1
Stack           Symbols    States+    States+    States+    States+
                           Symbols    Symbols    Symbols    Symbols
Table size      Small      Small      Small      Small      Large
Power           Least      Weak       Moderate   Strong     Strongest
Conflicts       Some       Many       Fewer      Few        Rare
Left recursion  No         Yes        Yes        Yes        Yes
Left factoring  Yes        No         No         No         No
Hand-written    Easy       Hard       Hard       Hard       Hard
Tool support    ANTLR      Rare       Rare       Yacc/Bison Few
Practical       Yes        No         Some       Yes        Rare

=== LL(1) ===

Direction: Top-down.
Derivation: Leftmost.
Lookahead: 1.
Table: M[A, a] = rule.
Restrictions: No left recursion, no common prefixes.
Pros: Simple, hand-written, good errors.
Cons: Less powerful.
Tools: ANTLR (LL(*)).

=== LR(0) ===

Direction: Bottom-up.
Lookahead: 0.
Table: ACTION/GOTO.
Conflicts: Many.
Pros: Foundation for other LR.
Cons: Too weak for most grammars.
Tools: Rarely used directly.

=== SLR(1) ===

Direction: Bottom-up.
Lookahead: 1.
Table: LR(0) + FOLLOW.
Conflicts: Fewer than LR(0).
Pros: Simple extension of LR(0).
Cons: Still limited.
Tools: Rare.

=== LALR(1) ===

Direction: Bottom-up.
Lookahead: 1.
Table: LR(1) with merged states.
Conflicts: Few.
Pros: Practical, small tables.
Cons: Rare conflicts.
Tools: Yacc, Bison, CUP.

=== LR(1) ===

Direction: Bottom-up.
Lookahead: 1.
Table: Canonical LR(1).
Conflicts: Rare.
Pros: Most powerful.
Cons: Large tables.
Tools: Few.

=== Table Size Comparison ===

For a typical grammar:

  LR(0):     ~100 states
  SLR(1):    ~100 states (same automaton)
  LALR(1):   ~100 states (merged)
  LR(1):     ~1000 states (canonical)

LR(1) can be 10x larger than LALR(1).

=== Power Comparison ===

Grammar that is:
  LL(1): simple expressions
  SLR(1): most expressions
  LALR(1): almost all programming languages
  LR(1): all deterministic CFLs

Programming languages:
  - Most are LALR(1).
  - Some are LR(1).
  - Few are LL(1).

=== Practical Choice ===

For hand-written parsers:
  → LL(1) / recursive descent.
  Simple, good errors, easy to maintain.

For tool-generated parsers:
  → LALR(1) (Yacc/Bison).
  Practical, powerful, small tables.

For maximum power:
  → LR(1).
  Handles all deterministic CFLs.
  But large tables.

For modern tools:
  → ANTLR (LL(*)).
  Good error messages, easy to use.

=== Which Parser Does Your Language Use? ===

C:       LALR(1) (Yacc)
C++:     LALR(1) (Bison) or hand-written
Java:    LALR(1) (CUP) or LL(k)
Python:  LL(1) / PEG
JavaScript: LL(*) / hand-written
Haskell: LL(*) / hand-written

Most languages use LALR(1) or LL.
LALR(1) is the industry standard.
""")

# COMPARISON TABLE
print("=== Summary Table ===")
print(f"{'Parser':<12} {'Direction':<12} {'Lookahead':<10} {'Power':<15} {'Table':<10} {'Tools':<15}")
print("-" * 80)
print(f"{'LL(1)':<12} {'Top-down':<12} {'1':<10} {'Least':<15} {'Small':<10} {'ANTLR':<15}")
print(f"{'LR(0)':<12} {'Bottom-up':<12} {'0':<10} {'Weak':<15} {'Small':<10} {'Rare':<15}")
print(f"{'SLR(1)':<12} {'Bottom-up':<12} {'1':<10} {'Moderate':<15} {'Small':<10} {'Rare':<15}")
print(f"{'LALR(1)':<12} {'Bottom-up':<12} {'1':<10} {'Strong':<15} {'Small':<10} {'Yacc/Bison':<15}")
print(f"{'LR(1)':<12} {'Bottom-up':<12} {'1':<10} {'Strongest':<15} {'Large':<10} {'Few':<15}")

print("""
=== Key Observations ===

1. POWER
   LL(1) < LR(0) < SLR(1) < LALR(1) < LR(1)

2. TABLE SIZE
   LALR(1) = SLR(1) < LR(1)

3. PRACTICALITY
   LALR(1) is the sweet spot.
   Powerful enough, small tables.

4. TOOL SUPPORT
   LALR(1): Yacc, Bison.
   LL(1): ANTLR, hand-written.

5. INDUSTRY
   Most compilers use LALR(1).
   Some use LL(1).
   Few use LR(1).

=== Choosing a Parser ===

For SIMPLE LANGUAGES:
  → LL(1) / recursive descent.
  Easy to hand-write.

For COMPLEX LANGUAGES:
  → LALR(1) (Yacc/Bison).
  Powerful, practical.

For MAXIMUM POWER:
  → LR(1).
  Handles all deterministic CFLs.

For MODERN TOOLS:
  → ANTLR (LL(*)).
  Good errors, easy to use.

For RESEARCH:
  → GLR, PEG, Earley.
  More general, slower.
""")

# SUMMARY
print("""
=== Summary ===

Power:
  LL(1) ⊊ LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1)

Table size:
  LALR(1) = SLR(1) < LR(1)

Practical:
  LALR(1) is the industry standard.
  Yacc/Bison use LALR(1).

Hand-written:
  LL(1) / recursive descent.

Tools:
  Yacc/Bison: LALR(1)
  ANTLR: LL(*)
  CUP: LALR(1)

Key insight:
  LALR(1) is the practical choice.
  It balances power and table size.
  Used in industry.
  LL(1) is simpler for hand-written parsers.
  LR(1) is most powerful but rarely used.
""")

💼 Applications

🎯 Parsing in the Real World

LL and LR parsing are used in every compiler, interpreter, and parsing tool. They're the backbone of programming language implementation.

Application Areas

Compilers: GCC, Clang, javac. Interpreters: Python, Ruby. Tools: Yacc, Bison, ANTLR. IDEs: Syntax highlighting. Data: JSON, XML parsers. DSLs: Domain-specific languages.

💻 Compilers🛠️ Yacc/Bison📄 JSON/XML🔧 DSLs

# Applications of LL/LR Parsing
print("=" * 60)
print("APPLICATIONS OF LL/LR PARSING")
print("=" * 60)

# 1. COMPILERS
print("""
=== 1. Compilers ===

Every compiler has a parser:

GCC:
  - Hand-written recursive descent.
  - LL parsing.
  - C, C++, Fortran, etc.

Clang:
  - Hand-written recursive descent.
  - LL parsing.
  - C, C++, Objective-C.

javac:
  - Hand-written recursive descent.
  - LL parsing.
  - Java.

Python:
  - PEG parser (since 3.9).
  - LL-like.
  - Python.

JavaScript:
  - Hand-written or generated.
  - LL or LALR.
  - V8, SpiderMonkey.

The parser:
  - Reads tokens from lexer.
  - Builds AST.
  - Reports syntax errors.

=== 2. Parser Generators ===

Yacc/Bison:
  - LALR(1) parser generator.
  - Input: grammar.
  - Output: C parser.
  - Used in GCC, many tools.

ANTLR:
  - LL(*) parser generator.
  - Input: grammar.
  - Output: Java, Python, C++, etc.
  - Used in many projects.

JavaCC:
  - LL(k) parser generator.
  - Output: Java parser.

CUP:
  - LALR(1) parser generator.
  - Output: Java parser.

PLY:
  - LALR(1) for Python.
  - Used in many Python tools.

These tools automate parser construction.

=== 3. Data Formats ===

JSON:
  - Simple grammar.
  - LL or LR.
  - Many implementations.

XML:
  - More complex grammar.
  - LL or LR.
  - SAX, DOM parsers.

YAML:
  - Complex (indentation).
  - Hand-written parser.
  - LL-like.

CSV:
  - Very simple.
  - Line-based.
  - Regex or LL.

All use parsing techniques.

=== 4. Domain-Specific Languages ===

DSLs are everywhere:
  - Configuration languages.
  - Query languages.
  - Modeling languages.
  - Template languages.

Examples:
  - SQL: LALR(1) or hand-written.
  - GraphQL: LL or hand-written.
  - Terraform: LL or hand-written.
  - Ansible: YAML-based.
  - Regex: custom parser.

DSLs use parsing techniques.

=== 5. IDEs and Editors ===

Syntax highlighting:
  - Lexer (Type 3).
  - Parser (Type 2) for structure.

Auto-completion:
  - Parser for context.
  - AST for suggestions.

Refactoring:
  - Parser for AST.
  - Transform AST.

Error detection:
  - Parser for syntax errors.
  - Good error messages.

IDEs use parsers extensively.
""")

# 6. SUMMARY TABLE
print("""
=== Application Summary ===

Domain              Parser Type         Examples
────────────────────────────────────────────────────
Compilers           LL / LALR(1)        GCC, Clang, javac
Interpreters        LL / PEG            Python, Ruby
Parser generators   LALR(1) / LL(*)     Yacc, Bison, ANTLR
Data formats        LL / LALR(1)        JSON, XML, YAML
DSLs                Various             SQL, GraphQL
IDEs                LL / LALR(1)        VS Code, IntelliJ
Web                 LL / PEG            JavaScript engines

Key observations:
  - Parsing is everywhere.
  - LALR(1) is industry standard.
  - LL is common for hand-written.
  - Tools automate construction.
  - Different domains, different choices.

=== 7. Case Study: GCC ===

GCC uses:
  - Hand-written recursive descent parser.
  - LL parsing.
  - Since GCC 3.4 (2004).

Why hand-written?
  - Better error messages.
  - Easier to maintain.
  - More control.
  - Faster.

GCC parses C, C++, Fortran, etc.
Millions of lines of code.
Reliable and efficient.

=== 8. Case Study: Python ===

Python uses:
  - PEG parser (since 3.9).
  - Replaced LL(1) parser.
  - More powerful.
  - Better error messages.

Why PEG?
  - Handles more grammars.
  - No left recursion issues.
  - Cleaner specification.
  - Better errors.

Python's grammar is in the docs.
Used by CPython and other implementations.

=== 9. Case Study: Yacc/Bison ===

Yacc/Bison:
  - LALR(1) parser generator.
  - Used since 1970s.
  - Still widely used.

Workflow:
  1. Write grammar in .y file.
  2. Run bison to generate parser.
  3. Compile with lexer.
  4. Link into application.

Used in:
  - GCC (historically).
  - Many Unix tools.
  - Database systems.
  - Configuration parsers.

Bison is mature and reliable.
""")

# 10. TAKEAWAYS
print("""
=== Practical Takeaways ===

1. PARSING IS ESSENTIAL
   Every language needs a parser.
   Compilers, interpreters, tools.

2. LL IS SIMPLE
   Hand-written recursive descent.
   Good error messages.
   Used in many compilers.

3. LALR(1) IS PRACTICAL
   Tool-generated.
   Powerful enough for most languages.
   Used in industry.

4. TOOLS ARE MATURE
   Yacc, Bison, ANTLR.
   Decades of development.
   Reliable and efficient.

5. CHOOSE WISELY
   LL for hand-written.
   LALR(1) for generated.
   LR(1) for maximum power.

6. UNDERSTAND CONFLICTS
   Resolve with precedence.
   Use grammar transformations.
   Test extensively.

7. MODERN TRENDS
   PEG, GLR, Earley.
   More powerful, slower.
   Used in specific domains.

Key insight:
  LL/LR parsing is the foundation
  of programming language implementation.
  It's used everywhere.
  Understanding it is essential
  for compiler developers.
  
  The choice of parser depends on:
    - Language complexity.
    - Tool availability.
    - Error message requirements.
    - Performance needs.

"Parsing is the bridge between
 text and structure."
  — Compiler Designer

Go parse something!
""")

# QUICK REFERENCE
print("""
=== Quick Reference ===

LL(1):
  Top-down, predictive.
  Table M[A, a] = rule.
  No left recursion.
  Hand-written.

LR(0):
  Bottom-up, shift-reduce.
  No lookahead.
  Many conflicts.

SLR(1):
  LR(0) + FOLLOW sets.
  Reduce on FOLLOW(A).
  Fewer conflicts.

LALR(1):
  LR(1) with merged states.
  Lookahead sets.
  Practical, small tables.
  Yacc/Bison.

LR(1):
  Canonical LR(1).
  Context-sensitive lookahead.
  Most powerful.
  Large tables.

Power:
  LL(1) ⊊ LR(0) ⊊ SLR(1) ⊊ LALR(1) ⊊ LR(1)

Industry:
  LALR(1) is standard.
  LL is common for hand-written.
  LR(1) is rare.

Key insight:
  Parsing is essential.
  LALR(1) is practical.
  LL is simple.
  Choose wisely.
""")

🚀 Advanced Topics

🎯 Beyond LL/LR

Modern parsing techniques go beyond LL and LR: PEG, GLR, Earley, parser combinators, and neural parsing.

Advanced Parsing

PEG: Parsing Expression Grammars. GLR: Generalized LR. Earley: General CFG parsing. Combinators: Functional parsing. Neural: Learned parsing. Incremental: Online parsing.

📝 PEG🔀 GLR🔍 Earley🧠 Neural

# Advanced Parsing Techniques
print("=" * 60)
print("ADVANCED PARSING TECHNIQUES")
print("=" * 60)

# 1. PEG
print("""
=== 1. Parsing Expression Grammars (PEG) ===

PEG (Ford, 2004):
  - Ordered choice (not unordered).
  - Greedy matching.
  - No ambiguity by design.

Operators:
  e1 e2      Sequence
  e1 / e2    Ordered choice
  e*         Zero or more
  e+         One or more
  e?         Optional
  &e         And-predicate
  !e         Not-predicate

Advantages:
  - No ambiguity.
  - Simple to implement.
  - Good for DSLs.

Disadvantages:
  - Not CFG (different class).
  - May need backtracking.
  - Can be exponential.

Used in:
  - PEG.js (JavaScript)
  - Pest (Rust)
  - LPeg (Lua)
  - Python's pegen

=== 2. GLR Parsing ===

Generalized LR (Tomita, 1985):
  - Handles ambiguous grammars.
  - Forks parse stack on conflicts.
  - Returns all parse trees.

Advantages:
  - Handles any CFG.
  - Handles ambiguity.
  - Efficient for many grammars.

Disadvantages:
  - More complex.
  - May be slower.
  - Multiple parses to manage.

Used in:
  - C++ parsers (some).
  - Elkhound.
  - Bison (GLR mode).

=== 3. Earley Parsing ===

Earley (1970):
  - General CFG parsing.
  - Dynamic programming.
  - O(n³) worst case.
  - O(n²) for unambiguous.
  - O(n) for LL/LR.

Advantages:
  - Handles any CFG.
  - Handles ambiguity.
  - Online (left-to-right).
  - No grammar restrictions.

Disadvantages:
  - Slower than LL/LR.
  - More complex.

Used in:
  - NLP (natural language).
  - Some compilers.
  - Grammar tools.

=== 4. Parser Combinators ===

Parser combinators:
  - Higher-order functions.
  - Compose parsers.
  - Functional programming.

Examples:
  - Parsec (Haskell)
  - FParsec (F#)
  - Combine (Swift)
  - nom (Rust)

Advantages:
  - Very expressive.
  - Easy to compose.
  - Good for DSLs.

Disadvantages:
  - May be slow.
  - Backtracking.
  - Error messages.
""")

# 5. NEURAL PARSING
print("""
=== 5. Neural Parsing ===

Neural parsing:
  - Deep learning for parsing.
  - No explicit grammar.
  - Learned from data.

Approaches:
  - Sequence-to-sequence.
  - Attention-based.
  - Graph neural networks.

Advantages:
  - Handles ambiguity statistically.
  - Robust to noise.
  - Good for NLP.

Disadvantages:
  - No guarantees.
  - Requires data.
  - Black box.

Used in:
  - NLP research.
  - Machine translation.
  - Information extraction.

=== 6. Incremental Parsing ===

Incremental parsing:
  - Parse as input arrives.
  - Used in IDEs.
  - Real-time feedback.

Examples:
  - Tree-sitter.
  - Lezer.
  - CodeMirror.

Advantages:
  - Fast updates.
  - Good for editors.
  - Interactive.

Disadvantages:
  - Complex.
  - State management.

=== 7. Open Problems ===

1. ERROR RECOVERY
   Best error recovery?
   Heuristic approaches.

2. INCREMENTAL PARSING
   Efficient incremental algorithms?
   Active research.

3. NEURAL-SYMBOLIC
   Combining neural and symbolic?
   Active research.

4. PARSING AMBIGUITY
   Efficient ambiguity handling?
   GLR, Earley, etc.

5. PERFORMANCE
   Faster parsers?
   SIMD, parallel, etc.

=== 8. RECOMMENDATIONS ===

For students:
  1. Master LL and LR first.
  2. Learn a tool (Yacc/Bison).
  3. Understand conflicts.
  4. Study error recovery.
  5. Explore modern techniques.

For researchers:
  1. Neural parsing.
  2. Incremental parsing.
  3. Error recovery.
  4. Neural-symbolic.
  5. Performance.

For practitioners:
  1. Use the right tool.
  2. Understand limitations.
  3. Handle errors well.
  4. Test extensively.
  5. Consider modern alternatives.

=== Final Thoughts ===

Parsing is:

✓ FUNDAMENTAL
  Bridge between text and structure.

✓ PRACTICAL
  Used in every compiler.

✓ MATURE
  Decades of development.

✓ EVOLVING
  New techniques, new tools.

✓ ESSENTIAL
  For programming languages.

Key takeaway:
  LL and LR are the foundation
  of parsing.
  LALR(1) is the practical choice.
  LL is simpler for hand-written.
  Modern techniques extend them.
  Understanding parsing is essential
  for compiler developers.

"Parsing is the art of turning
 text into trees."
  — Compiler Designer

Go parse something!
""")

# QUICK REFERENCE
print("""
=== Quick Reference ===

LL(1):
  Top-down, predictive.
  Hand-written.
  No left recursion.

LR(0):
  Bottom-up, shift-reduce.
  No lookahead.

SLR(1):
  LR(0) + FOLLOW.

LALR(1):
  LR(1) merged.
  Yacc/Bison.

LR(1):
  Canonical.
  Most powerful.

Modern:
  PEG: ordered choice.
  GLR: ambiguous grammars.
  Earley: general CFG.
  Combinators: functional.
  Neural: learned.

Tools:
  Yacc/Bison: LALR(1)
  ANTLR: LL(*)
  CUP: LALR(1)
  Tree-sitter: incremental

Key insight:
  Parsing is essential.
  LALR(1) is practical.
  LL is simple.
  Modern techniques extend.
  Choose wisely.
""")