🧠 Introduction

🎯 What is the Earley Parser?

The Earley parser is a general-purpose parsing algorithm for context-free grammars. Unlike LL and LR parsers, it can handle any context-free grammar, including ambiguous and left-recursive grammars. It uses dynamic programming and a chart to efficiently parse input.

Key insight: The Earley parser combines the best of top-down and bottom-up parsing. It's O(n³) for general CFGs, O(n²) for unambiguous grammars, and O(n) for LL/LR grammars. It's the parser of choice when you need generality.

Why the Earley Parser Matters

General: Handles any CFG. Ambiguity: Handles ambiguous grammars. Left recursion: No problem. Efficient: O(n³) worst case. Online: Left-to-right. NLP: Used in natural language parsing.

🔍 General CFG🔀 Ambiguity📊 Chart parsing⚡ Dynamic programming

# Earley Parser — the big picture
print("""
=== What is the Earley Parser? ===

Earley parser (Jay Earley, 1970):
  - General-purpose CFG parser.
  - Handles ANY context-free grammar.
  - Uses dynamic programming (chart).
  - Left-to-right, online.

=== The Problem with LL and LR ===

LL(1):
  - Can't handle left recursion.
  - Can't handle common prefixes.
  - Restricted to LL(1) grammars.

LR(1):
  - More powerful.
  - But still restricted.
  - Conflicts possible.
  - Large tables.

Both require grammar transformations.
Both fail on some grammars.

=== The Earley Solution ===

Earley parser:
  - No grammar restrictions.
  - Handles left recursion.
  - Handles ambiguity.
  - Handles any CFG.

How?
  - Dynamic programming.
  - Chart (table of items).
  - Three operations: Predict, Scan, Complete.

=== The Chart ===

The chart is a sequence of sets of items:
  C[0], C[1], C[2], ..., C[n]

where n = length of input.

C[i] contains items that:
  - Have consumed input up to position i.
  - Are waiting for more input.

Each item: [A → α · β, j]
  - A → αβ is a production.
  - · is the dot (progress marker).
  - j is the start position.

The parser fills the chart left to right.

=== Real-World Analogy ===

Think of parsing as a group project:
  - You have a set of tasks (grammar rules).
  - Each task can be broken into subtasks.
  - You track progress (dot position).
  - You coordinate (predict, scan, complete).

The chart is the project management board.
Each item is a task with progress.
Predict: assign subtasks.
Scan: check off a terminal.
Complete: finish a task.

This is exactly how Earley works!

=== Historical Context ===

1970: Jay Earley publishes the algorithm.
  "An Efficient Context-Free Parsing Algorithm"
  Communications of the ACM.

1980s: Used in NLP.
1990s: Optimized implementations.
2000s: Used in various tools.
Now: Standard for general CFG parsing.

The Earley parser is one of the
most important parsing algorithms.
""")

# ANALOGY
print("=== Analogy: Assembly Line ===")
print("""
Imagine an assembly line:
  - Products move from station to station.
  - At each station, work is done.
  - When a product is complete, it moves on.

Earley parser:
  - Input tokens are the products.
  - Grammar rules are the stations.
  - Chart is the assembly line.
  - Items track progress.

At each position i:
  - C[i] contains items that have consumed i tokens.
  - Predict: prepare for next token.
  - Scan: consume a token.
  - Complete: finish a rule.

The parser processes left to right.
Each token is scanned once.
Items are propagated.

=== Another Analogy: Graph Search ===

Earley parsing is like graph search:
  - Nodes: (item, position).
  - Edges: Predict, Scan, Complete.
  - Start: initial item.
  - Goal: complete start rule.

The chart is the visited set.
The algorithm explores the graph.
Dynamic programming avoids rework.

=== The Key Insight ===

Earley's insight:
  - Don't restrict the grammar.
  - Use dynamic programming.
  - Track all possible parses.
  - Share work between parses.

This is why Earley is general.
And why it's O(n³) worst case.
""")

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

Earley Parser:

  ┌─────────────────────────────────────┐
  │ Earley Parser                       │
  │  ┌───────────────────────────────┐  │
  │  │ General CFG                   │  │
  │  │  ┌─────────────────────────┐  │  │
  │  │  │ Ambiguous Grammars      │  │  │
  │  │  │  ┌───────────────────┐  │  │  │
  │  │  │  │ Left Recursion    │  │  │  │
  │  │  │  │  ┌─────────────┐  │  │  │  │
  │  │  │  │  │ LL/LR       │  │  │  │  │
  │  │  │  │  └─────────────┘  │  │  │  │
  │  │  │  └───────────────────┘  │  │  │
  │  │  └─────────────────────────┘  │  │
  │  └───────────────────────────────┘  │
  └─────────────────────────────────────┘

Earley is more general than LL and LR.
But slower in the worst case.

=== Key Facts ===

1. GENERAL
   Handles any CFG.
   No restrictions.

2. AMBIGUITY
   Handles ambiguous grammars.
   Can return all parses.

3. COMPLEXITY
   O(n³) general.
   O(n²) unambiguous.
   O(n) LL/LR.

4. ONLINE
   Processes left to right.
   Can parse incrementally.

5. DYNAMIC PROGRAMMING
   Uses chart.
   Shares work.

6. APPLICATIONS
   Natural language parsing.
   Grammar tools.
   Error recovery.
""")

# EARLEY IN CODE
print("=== Earley Parser in Code ===")

class EarleyItem:
    """An Earley item."""
    def __init__(self, rule, dot, start):
        self.rule = rule  # (lhs, rhs)
        self.dot = dot    # progress
        self.start = start  # start position
    
    def __repr__(self):
        lhs, rhs = self.rule
        rhs_list = list(rhs)
        rhs_list.insert(self.dot, '·')
        return f"[{lhs} → {' '.join(rhs_list)}, {self.start}]"
    
    def __eq__(self, other):
        return (self.rule == other.rule and 
                self.dot == other.dot and 
                self.start == other.start)
    
    def __hash__(self):
        return hash((self.rule, self.dot, self.start))
    
    def is_complete(self):
        return self.dot >= len(self.rule[1])
    
    def next_symbol(self):
        if self.dot < len(self.rule[1]):
            return self.rule[1][self.dot]
        return None
    
    def advance(self):
        return EarleyItem(self.rule, self.dot + 1, self.start)


class EarleyParser:
    """Earley parser."""
    def __init__(self, grammar, start_symbol):
        self.grammar = grammar  # dict: nonterminal -> list of rhs
        self.start = start_symbol
    
    def parse(self, tokens):
        """Parse tokens. Returns chart."""
        n = len(tokens)
        chart = [set() for _ in range(n + 1)]
        
        # Initial item
        start_rule = ('S\'', (self.start,))
        chart[0].add(EarleyItem(start_rule, 0, 0))
        
        for i in range(n + 1):
            # Process items in C[i]
            items = list(chart[i])
            j = 0
            while j < len(items):
                item = items[j]
                j += 1
                
                if item.is_complete():
                    # COMPLETE
                    self.complete(item, i, chart)
                else:
                    next_sym = item.next_symbol()
                    if next_sym in self.grammar:
                        # PREDICT
                        self.predict(item, next_sym, i, chart)
                    elif i < n and next_sym == tokens[i]:
                        # SCAN
                        self.scan(item, i, chart)
            
            # Add new items to items list
            for item in chart[i]:
                if item not in items:
                    items.append(item)
        
        return chart
    
    def predict(self, item, nonterminal, pos, chart):
        """Predict: add items for nonterminal."""
        for rhs in self.grammar.get(nonterminal, []):
            new_item = EarleyItem((nonterminal, rhs), 0, pos)
            chart[pos].add(new_item)
    
    def scan(self, item, pos, chart):
        """Scan: consume a terminal."""
        new_item = item.advance()
        chart[pos + 1].add(new_item)
    
    def complete(self, item, pos, chart):
        """Complete: advance items that were waiting."""
        lhs = item.rule[0]
        start = item.start
        for other in list(chart[start]):
            if not other.is_complete() and other.next_symbol() == lhs:
                new_item = other.advance()
                chart[pos].add(new_item)
    
    def accepts(self, tokens):
        """Check if tokens are accepted."""
        chart = self.parse(tokens)
        n = len(tokens)
        start_rule = ('S\'', (self.start,))
        for item in chart[n]:
            if item.rule == start_rule and item.is_complete():
                return True
        return False


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

parser = EarleyParser(grammar, 'E')

print("Earley Parser for arithmetic expressions:")
print("Grammar:")
for lhs, prods in grammar.items():
    for rhs in prods:
        print(f"  {lhs} → {' '.join(rhs)}")

print("\nParsing tests:")
test_inputs = [
    ['id'],
    ['id', '+', 'id'],
    ['id', '*', 'id'],
    ['id', '+', 'id', '*', 'id'],
    ['(', 'id', '+', 'id', ')', '*', 'id'],
    ['id', '+'],
    ['+', 'id'],
]

for tokens in test_inputs:
    result = parser.accepts(tokens)
    status = "✓" if result else "✗"
    print(f"  {status} '{' '.join(tokens)}'")

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

1. CHART
   C[0], C[1], ..., C[n].
   Each C[i] is a set of items.

2. ITEMS
   [A → α · β, j].
   Dot shows progress.
   j is start position.

3. OPERATIONS
   Predict: expand nonterminal.
   Scan: consume terminal.
   Complete: finish rule.

4. GENERAL
   No grammar restrictions.
   Handles left recursion.
   Handles ambiguity.

5. COMPLEXITY
   O(n³) general.
   O(n²) unambiguous.
   O(n) LL/LR.

=== Why Earley Works ===

The chart stores all possible parses.
Dynamic programming shares work.
No backtracking needed.
Left-to-right processing.

This is the essence of Earley parsing.
""")

⚙️ The Algorithm

🎯 The Three Operations

The Earley parser uses three operations: Predict, Scan, and Complete. These operations fill the chart left to right.

The Algorithm Steps

Predict: Expand nonterminal. Scan: Consume terminal. Complete: Finish rule. Chart: C[0]..C[n]. Items: [A→α·β, j]. Accept: Complete start rule in C[n].

🔮 Predict📖 Scan✅ Complete📊 Chart

# The Earley Algorithm
print("=" * 60)
print("THE EARLEY ALGORITHM")
print("=" * 60)

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

Input: Grammar G, input tokens w = w₁w₂...wₙ.
Output: Chart C[0], C[1], ..., C[n].

Initialization:
  Add [S' → · S, 0] to C[0].

For i = 0 to n:
  For each item [A → α · β, j] in C[i]:
    
    1. PREDICT:
       If β starts with nonterminal B:
         For each rule B → γ:
           Add [B → · γ, i] to C[i].
    
    2. SCAN:
       If β starts with terminal a and a = wᵢ:
         Add [A → α a · β', j] to C[i+1].
    
    3. COMPLETE:
       If β is empty (item is complete):
         For each item [B → γ · A δ, k] in C[j]:
           Add [B → γ A · δ, k] to C[i].

Acceptance:
  [S' → S ·, 0] ∈ C[n].

=== Predict ===

When: Item [A → α · B β, j] in C[i]
       and B is a nonterminal.

Action:
  For each rule B → γ:
    Add [B → · γ, i] to C[i].

Meaning:
  "We're expecting B. Let's start parsing B
   from position i."

Example:
  Item: [E → · T, 0]
  Rules: T → T * F | F
  
  Predict:
    Add [T → · T * F, 0]
    Add [T → · F, 0]

=== Scan ===

When: Item [A → α · a β, j] in C[i]
       and a is a terminal
       and a = wᵢ (current input).

Action:
  Add [A → α a · β, j] to C[i+1].

Meaning:
  "We've matched terminal a. Advance the dot
   and move to the next position."

Example:
  Item: [F → · id, 2]
  Input: w₂ = id
  
  Scan:
    Add [F → id ·, 2] to C[3].

=== Complete ===

When: Item [A → α ·, j] in C[i]
       (item is complete).

Action:
  For each item [B → γ · A δ, k] in C[j]:
    Add [B → γ A · δ, k] to C[i].

Meaning:
  "We've finished parsing A (from j to i).
   Now advance items that were waiting for A."

Example:
  Completed: [F → id ·, 2] in C[3].
  Items in C[2]:
    [T → · F, 2]
  
  Complete:
    Add [T → F ·, 2] to C[3].

=== The Chart ===

C[0]: items before consuming any input.
C[1]: items after consuming w₁.
...
C[n]: items after consuming all input.

Each C[i] is a set of items.
Items are added and processed until
no more items can be added.

Acceptance:
  [S' → S ·, 0] ∈ C[n].

=== Example: "id + id" ===

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

Input: id + id

C[0]:
  [S' → · E, 0]      (initial)
  [E → · E + T, 0]   (predict E)
  [E → · T, 0]       (predict E)
  [T → · T * F, 0]   (predict T)
  [T → · F, 0]       (predict T)
  [F → · ( E ), 0]   (predict F)
  [F → · id, 0]      (predict F)

C[1]: (after id)
  [F → id ·, 0]      (scan)
  [T → F ·, 0]       (complete F)
  [T → T · * F, 0]   (complete T)
  [E → T ·, 0]       (complete T)
  [E → E · + T, 0]   (complete E)

C[2]: (after +)
  [E → E + · T, 0]   (scan +)
  [T → · T * F, 2]   (predict T)
  [T → · F, 2]       (predict T)
  [F → · ( E ), 2]   (predict F)
  [F → · id, 2]      (predict F)

C[3]: (after id)
  [F → id ·, 2]      (scan)
  [T → F ·, 2]       (complete F)
  [T → T · * F, 2]   (complete T)
  [E → E + T ·, 0]   (complete T)
  [S' → E ·, 0]      (complete E)

Accept: [S' → E ·, 0] ∈ C[3]. ✓

=== The Algorithm in Pseudocode ===

function EARLEY-PARSE(grammar, input):
    n = length(input)
    chart = [set() for _ in range(n+1)]
    chart[0].add(Item(S' → · S, 0))
    
    for i = 0 to n:
        for each item in chart[i]:
            if item is complete:
                COMPLETE(item, i, chart)
            elif item.next is nonterminal:
                PREDICT(item, i, chart)
            elif i < n and item.next == input[i]:
                SCAN(item, i, chart)
    
    return chart

function COMPLETE(item, i, chart):
    A = item.lhs
    j = item.start
    for each other in chart[j]:
        if other.next == A:
            chart[i].add(other.advance())

function PREDICT(item, i, chart):
    B = item.next
    for each rule B → γ:
        chart[i].add(Item(B → · γ, i))

function SCAN(item, i, chart):
    chart[i+1].add(item.advance())

=== Key Properties ===

1. DYNAMIC PROGRAMMING
   Each item added once.
   Work shared between parses.

2. LEFT-TO-RIGHT
   Processes input in order.
   Online.

3. GENERAL
   Handles any CFG.
   No restrictions.

4. AMBIGUITY
   Multiple parses possible.
   Backpointers can recover them.

5. COMPLEXITY
   O(n³) general.
   O(n²) unambiguous.
   O(n) LL/LR.
""")

# ALGORITHM IN CODE
print("=== Algorithm Implementation ===")

class EarleyItem:
    def __init__(self, lhs, rhs, dot, start):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
        self.start = start
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"[{self.lhs} → {' '.join(rhs)}, {self.start}]"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and
                self.start == other.start)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot, self.start))
    
    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 EarleyItem(self.lhs, self.rhs, self.dot + 1, self.start)


class EarleyParser:
    def __init__(self, grammar, start):
        self.grammar = grammar
        self.start = start
        self.nonterminals = set(grammar.keys())
    
    def parse(self, tokens, verbose=False):
        n = len(tokens)
        chart = [set() for _ in range(n + 1)]
        
        # Initial item
        chart[0].add(EarleyItem("S'", [self.start], 0, 0))
        
        for i in range(n + 1):
            # Process items until no new ones
            items = list(chart[i])
            processed = set()
            
            while items:
                item = items.pop(0)
                if item in processed:
                    continue
                processed.add(item)
                
                if item.is_complete():
                    # COMPLETE
                    lhs = item.lhs
                    j = item.start
                    for other in list(chart[j]):
                        if not other.is_complete() and other.next_symbol() == lhs:
                            new_item = other.advance()
                            if new_item not in chart[i]:
                                chart[i].add(new_item)
                                items.append(new_item)
                
                else:
                    next_sym = item.next_symbol()
                    
                    if next_sym in self.nonterminals:
                        # PREDICT
                        for rhs in self.grammar[next_sym]:
                            new_item = EarleyItem(next_sym, rhs, 0, i)
                            if new_item not in chart[i]:
                                chart[i].add(new_item)
                                items.append(new_item)
                    
                    elif i < n and next_sym == tokens[i]:
                        # SCAN
                        new_item = item.advance()
                        chart[i + 1].add(new_item)
        
        if verbose:
            self._print_chart(chart, tokens)
        
        return chart
    
    def accepts(self, tokens):
        chart = self.parse(tokens)
        n = len(tokens)
        for item in chart[n]:
            if item.lhs == "S'" and item.is_complete():
                return True
        return False
    
    def _print_chart(self, chart, tokens):
        for i, items in enumerate(chart):
            print(f"\nC[{i}]" + (f" (after '{tokens[i-1]}')" if i > 0 else " (start)"))
            for item in sorted(items, key=str):
                print(f"  {item}")


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

parser = EarleyParser(grammar, 'E')

print("Earley Parser trace for 'id + id':")
tokens = ['id', '+', 'id']
chart = parser.parse(tokens, verbose=True)

print(f"\nAccepted: {parser.accepts(tokens)}")

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

1. CHART
   C[0] to C[n].
   Each C[i] is a set of items.

2. PROCESSING
   Process items until no new ones.
   Predict, Scan, Complete.

3. ACCEPTANCE
   [S' → S ·, 0] in C[n].

4. EFFICIENCY
   Each item processed once.
   Dynamic programming.

5. GENERAL
   No grammar restrictions.
   Handles left recursion.

=== Why Earley Works ===

The chart stores all possible parses.
Dynamic programming shares work.
No backtracking needed.
Left-to-right processing.

This is the essence of Earley parsing.
""")

📝 Earley Items

🎯 The Building Blocks

An Earley item is a production with a dot (progress marker) and a start position. Items are the fundamental data structure of the Earley parser.

Item Structure

Form: [A → α · β, j]. A → αβ: Production. ·: Progress marker. j: Start position. Complete: Dot at end. Incomplete: Dot in middle.

📝 [A → α·β, j]🔘 Dot📍 Start position✅ Complete

# Earley Items
print("=" * 60)
print("EARLEY ITEMS")
print("=" * 60)

print("""
=== Definition ===

An EARLEY ITEM is a triple:
  [A → α · β, j]

where:
  A → αβ is a production.
  · is the dot (progress marker).
  j is the start position.

Meaning:
  "We're parsing A starting at position j.
   We've recognized α.
   We're expecting β."

=== Example ===

Grammar rule: E → E + T

Items:
  [E → · E + T, 0]    (start, at position 0)
  [E → E · + T, 0]    (seen E, expecting + T)
  [E → E + · T, 0]    (seen E +, expecting T)
  [E → E + T ·, 0]    (complete, seen E + T)

Each item represents a different stage.

=== Complete vs Incomplete ===

COMPLETE item:
  [A → α ·, j]
  Dot is at the end.
  The rule has been fully recognized.

INCOMPLETE item:
  [A → α · β, j] with β ≠ ε
  Dot is in the middle.
  Still expecting more symbols.

=== The Dot ===

The dot separates:
  - α: what has been recognized.
  - β: what is still expected.

Dot position advances as we recognize symbols.

Example:
  [E → · E + T, 0]    → nothing recognized
  [E → E · + T, 0]    → E recognized
  [E → E + · T, 0]    → E + recognized
  [E → E + T ·, 0]    → E + T recognized (complete)

=== The Start Position ===

j is the position where parsing of A started.

Example:
  [F → id ·, 2] means:
    "We started parsing F at position 2.
     We've recognized id.
     F is complete."

Why is j important?
  When F is complete, we need to know
  where it started to advance other items.
  
  This is how COMPLETE works.

=== The Chart ===

The chart is a sequence of sets:
  C[0], C[1], ..., C[n]

C[i] contains items that:
  - Have consumed input up to position i.
  - Are waiting for more input.

Items in C[i] have dot position ≤ i.

=== Examples of Items ===

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

Items in C[0] (before any input):
  [S' → · E, 0]
  [E → · E + T, 0]
  [E → · T, 0]
  [T → · T * F, 0]
  [T → · F, 0]
  [F → · ( E ), 0]
  [F → · id, 0]

Items in C[1] (after 'id'):
  [F → id ·, 0]       (scan)
  [T → F ·, 0]        (complete F)
  [T → T · * F, 0]    (complete T)
  [E → T ·, 0]        (complete T)
  [E → E · + T, 0]    (complete E)

Notice:
  - Items with dot at end are complete.
  - Items with dot in middle are incomplete.
  - Start positions track where rules began.

=== Why Items Matter ===

1. TRACK PROGRESS
   Dot shows how much is recognized.

2. SHARE WORK
   Items are shared between parses.
   Dynamic programming.

3. HANDLE AMBIGUITY
   Multiple items can be in the chart.
   All possible parses tracked.

4. GENERAL
   No grammar restrictions.
   Any CFG can be parsed.

5. EFFICIENT
   Each item added once.
   O(n³) worst case.
""")

# ITEMS IN CODE
print("=== Items in Code ===")

class EarleyItem:
    """An Earley item."""
    def __init__(self, lhs, rhs, dot=0, start=0):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
        self.start = start
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"[{self.lhs} → {' '.join(rhs)}, {self.start}]"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and
                self.start == other.start)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot, self.start))
    
    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 EarleyItem(self.lhs, self.rhs, self.dot + 1, self.start)
    
    def __lt__(self, other):
        return str(self) < str(other)


# Examples
items = [
    EarleyItem('E', ['E', '+', 'T'], 0, 0),
    EarleyItem('E', ['E', '+', 'T'], 1, 0),
    EarleyItem('E', ['E', '+', 'T'], 2, 0),
    EarleyItem('E', ['E', '+', 'T'], 3, 0),
    EarleyItem('F', ['id'], 0, 2),
    EarleyItem('F', ['id'], 1, 2),
]

print("Earley items for E → E + T:")
for item in items[:4]:
    status = "COMPLETE" if item.is_complete() else "incomplete"
    print(f"  {item}  ({status})")

print("\nEarley items for F → id:")
for item in items[4:]:
    status = "COMPLETE" if item.is_complete() else "incomplete"
    print(f"  {item}  ({status})")

print(f"\nNext symbol of [E → E · + T, 0]: {items[1].next_symbol()}")
print(f"Next symbol of [E → E + T ·, 0]: {items[3].next_symbol()}")
print(f"Is [E → E + T ·, 0] complete? {items[3].is_complete()}")
print(f"Advance [E → E · + T, 0]: {items[1].advance()}")

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

1. ITEM FORM
   [A → α · β, j]
   Production + dot + start position.

2. DOT
   Shows progress.
   α recognized, β expected.

3. COMPLETE
   Dot at end.
   Rule fully recognized.

4. START POSITION
   Where parsing of A began.
   Needed for COMPLETE.

5. CHART
   C[0] to C[n].
   Items grouped by position.

=== Why This Works ===

Items are the state of the parser.
The chart is the state of the parse.
Predict, Scan, Complete update the state.
Dynamic programming shares work.

This is the essence of Earley parsing.
""")

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

Earley Item:
  [A → α · β, j]
  - A → αβ: production.
  - ·: progress marker.
  - j: start position.

Complete:
  Dot at end.
  Rule fully recognized.

Incomplete:
  Dot in middle.
  Still expecting symbols.

Chart:
  C[0] to C[n].
  Items grouped by position.

Operations:
  Predict: expand nonterminal.
  Scan: consume terminal.
  Complete: finish rule.

Key insight:
  Items are the fundamental data structure.
  They track progress and context.
  The chart is the state of the parse.
  Operations update the chart.
  Dynamic programming shares work.
""")

🔮 Predict

🎯 Expanding Nonterminals

The Predict operation expands a nonterminal by adding items for all its productions. It's the top-down component of Earley parsing.

Predict Operation

Trigger: Item [A → α · B β, j] where B is nonterminal. Action: Add [B → · γ, i] for each rule B → γ. Meaning: "Expecting B, start parsing B." Position: Same position i. Result: New items in C[i]. Top-down: Expands grammar.

🔮 Predict📝 Nonterminal📊 C[i]⬇️ Top-down

# Predict Operation
print("=" * 60)
print("PREDICT OPERATION")
print("=" * 60)

print("""
=== Definition ===

PREDICT is triggered when:
  An item [A → α · B β, j] is in C[i]
  where B is a nonterminal.

Action:
  For each rule B → γ in the grammar:
    Add [B → · γ, i] to C[i].

Meaning:
  "We're expecting B at position i.
   Let's start parsing B from position i."

=== Example ===

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

Item in C[0]:
  [E → · T, 0]

Trigger: Expecting T.
T is a nonterminal.

Predict:
  For each rule T → γ:
    T → T * F: add [T → · T * F, 0]
    T → F:     add [T → · F, 0]

New items in C[0]:
  [T → · T * F, 0]
  [T → · F, 0]

Now process these items:
  [T → · T * F, 0]: expecting T (predict again)
  [T → · F, 0]: expecting F (predict)

Continue until no new predictions.

=== Full Prediction for C[0] ===

Start: [S' → · E, 0]

Predict E:
  [E → · E + T, 0]
  [E → · T, 0]

Predict E (from E → E + T):
  [E → · E + T, 0]  (already there)
  [E → · T, 0]      (already there)

Predict T (from E → T):
  [T → · T * F, 0]
  [T → · F, 0]

Predict T (from T → T * F):
  [T → · T * F, 0]  (already there)
  [T → · F, 0]      (already there)

Predict F (from T → F):
  [F → · ( E ), 0]
  [F → · id, 0]

Final C[0]:
  [S' → · E, 0]
  [E → · E + T, 0]
  [E → · T, 0]
  [T → · T * F, 0]
  [T → · F, 0]
  [F → · ( E ), 0]
  [F → · id, 0]

All possible starts are predicted.

=== Predict in Code ===

def predict(item, i, chart, grammar):
    if item.is_complete():
        return
    next_sym = item.next_symbol()
    if next_sym in grammar:
        for rhs in grammar[next_sym]:
            new_item = Item(next_sym, rhs, 0, i)
            chart[i].add(new_item)

=== Why Predict Works ===

Predict is top-down:
  - We're expecting B.
  - B can be expanded in many ways.
  - Predict all possible expansions.

This is like recursive descent:
  - But no recursion.
  - Instead, add items to chart.
  - Dynamic programming.

=== Predict and Left Recursion ===

Predict handles left recursion naturally:

  E → E + T

When predicting E:
  [E → · E + T, 0]
  
  This item expects E.
  Predict E again:
    [E → · E + T, 0]  (already there)
  
  No infinite loop!
  Because items are stored in a set.
  Duplicates are ignored.

This is a key advantage over LL.
LL can't handle left recursion.
Earley can.

=== Predict and Nullable Rules ===

Nullable rules: A → ε

Predict handles them:
  [A → · ε, i]
  
  This item is immediately complete.
  Complete operation will handle it.

Example:
  A → ε

  Predict: [A → · , i]  (complete)
  Complete: advance items waiting for A.

Works correctly.

=== Predict and ε-Productions ===

If A → ε:
  [A → ·, i] is added by Predict.
  It's immediately complete.
  Complete advances items waiting for A.

This is how Earley handles ε.

=== Summary of Predict ===

Trigger:
  Item [A → α · B β, j] in C[i]
  B is nonterminal.

Action:
  Add [B → · γ, i] to C[i]
  for each rule B → γ.

Effect:
  Expands nonterminal B.
  Top-down prediction.

Position:
  Same position i.

Key properties:
  - Handles left recursion.
  - Handles ε-productions.
  - Dynamic programming.
  - No infinite loops.
""")

# PREDICT IN CODE
print("=== Predict in Code ===")

class EarleyItem:
    def __init__(self, lhs, rhs, dot=0, start=0):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
        self.start = start
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"[{self.lhs} → {' '.join(rhs)}, {self.start}]"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and
                self.start == other.start)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot, self.start))
    
    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 predict(item, i, chart, grammar):
    """Predict operation."""
    if item.is_complete():
        return []
    
    next_sym = item.next_symbol()
    if next_sym not in grammar:
        return []
    
    new_items = []
    for rhs in grammar[next_sym]:
        new_item = EarleyItem(next_sym, rhs, 0, i)
        if new_item not in chart[i]:
            chart[i].add(new_item)
            new_items.append(new_item)
    return new_items


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

# Simulate C[0]
chart = [set()]
chart[0].add(EarleyItem("S'", ['E'], 0, 0))

print("Predicting from [S' → · E, 0]:")
print(f"  Initial: {chart[0]}")

# Process items
items = list(chart[0])
for item in items:
    new = predict(item, 0, chart, grammar)
    if new:
        print(f"  Predict from {item}:")
        for ni in new:
            print(f"    {ni}")

print("\nFull C[0]:")
for item in sorted(chart[0], key=str):
    print(f"  {item}")

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

1. PREDICT EXPANDS
   Nonterminal B → all rules B → γ.

2. SAME POSITION
   New items start at position i.

3. NO INFINITE LOOPS
   Items stored in set.
   Duplicates ignored.

4. LEFT RECURSION
   Handled naturally.
   E → E + T works.

5. ε-PRODUCTIONS
   A → ε handled.
   Item immediately complete.

6. TOP-DOWN
   Predict is the top-down component.
   Expands nonterminals.

=== Why Predict Works ===

Predict is like recursive descent:
  - But no recursion.
  - Uses chart instead of call stack.
  - Dynamic programming.

This is why Earley is more powerful
than LL:
  - Handles left recursion.
  - Handles ε-productions.
  - No grammar restrictions.
""")

📖 Scan

🎯 Consuming Terminals

The Scan operation consumes a terminal from the input and advances the dot. It's the only operation that moves input forward.

Scan Operation

Trigger: Item [A → α · a β, j] in C[i]. Condition: a is terminal and a = w_i. Action: Add [A → α a · β, j] to C[i+1]. Meaning: "Matched a, advance dot." Position: Moves to i+1. Bottom-up: Consumes input.

📖 Scan🔤 Terminal➡️ C[i+1]⬆️ Bottom-up

# Scan Operation
print("=" * 60)
print("SCAN OPERATION")
print("=" * 60)

print("""
=== Definition ===

SCAN is triggered when:
  An item [A → α · a β, j] is in C[i]
  where a is a terminal
  and a = wᵢ (the i-th input token).

Action:
  Add [A → α a · β, j] to C[i+1].

Meaning:
  "We've matched terminal a at position i.
   Advance the dot to position i+1."

=== Example ===

Grammar:
  F → ( E ) | id

Input: id + id

C[0]:
  ...
  [F → · id, 0]

Item [F → · id, 0] in C[0].
Next symbol: id (terminal).
Input w₀ = id.

Scan:
  Add [F → id ·, 0] to C[1].

C[1]:
  [F → id ·, 0]  (from scan)
  ...

Notice:
  - Dot advanced past id.
  - Position moved to i+1.
  - Item is now complete.

=== Scan in Code ===

def scan(item, i, chart, tokens):
    if i >= len(tokens):
        return None
    next_sym = item.next_symbol()
    if next_sym == tokens[i]:
        new_item = item.advance()
        chart[i+1].add(new_item)
        return new_item
    return None

=== Full Example: "id + id" ===

Input: id + id
Positions: 0 1 2

C[0]:
  [F → · id, 0]

Scan with w₀ = id:
  [F → id ·, 0] → C[1]

C[1]:
  [F → id ·, 0]

Complete:
  [T → F ·, 0]
  [T → T · * F, 0]
  [E → T ·, 0]
  [E → E · + T, 0]

C[1]:
  [F → id ·, 0]
  [T → F ·, 0]
  [T → T · * F, 0]
  [E → T ·, 0]
  [E → E · + T, 0]

Scan with w₁ = +:
  [E → E + · T, 0] → C[2]

C[2]:
  [E → E + · T, 0]

Predict:
  [T → · T * F, 2]
  [T → · F, 2]
  [F → · ( E ), 2]
  [F → · id, 2]

C[2]:
  [E → E + · T, 0]
  [T → · T * F, 2]
  [T → · F, 2]
  [F → · ( E ), 2]
  [F → · id, 2]

Scan with w₂ = id:
  [F → id ·, 2] → C[3]

C[3]:
  [F → id ·, 2]

Complete:
  [T → F ·, 2]
  [T → T · * F, 2]
  [E → E + T ·, 0]
  [S' → E ·, 0]

Accept: [S' → E ·, 0] ∈ C[3]. ✓

=== Scan Properties ===

1. CONSUMES INPUT
   Scan is the only operation
   that advances the input position.

2. MOVES TO i+1
   New item goes to C[i+1].

3. MATCHES TERMINAL
   Only if next symbol equals input.

4. ADVANCES DOT
   Dot moves past the terminal.

5. BOTTOM-UP
   Scan is the bottom-up component.
   Consumes input.

=== Scan and Terminals ===

Scan only applies to terminals:
  [A → α · a β, j] with a terminal.

If next symbol is nonterminal:
  Predict applies instead.

If item is complete:
  Complete applies instead.

So the three operations are disjoint.

=== Scan in Different Positions ===

C[0]: no input consumed.
  Scan matches w₀.

C[1]: w₀ consumed.
  Scan matches w₁.

C[i]: w₀...wᵢ₋₁ consumed.
  Scan matches wᵢ.

C[n]: all input consumed.
  No scan (i = n).

=== Scan and Acceptance ===

After scanning all input:
  C[n] contains items that have consumed all input.

Acceptance:
  [S' → S ·, 0] ∈ C[n].

This means:
  - Start symbol S has been fully parsed.
  - Starting from position 0.
  - Ending at position n.

=== Summary of Scan ===

Trigger:
  Item [A → α · a β, j] in C[i]
  a is terminal
  a = wᵢ.

Action:
  Add [A → α a · β, j] to C[i+1].

Effect:
  Consumes input.
  Advances dot.
  Moves to next position.

Key properties:
  - Only operation that consumes input.
  - Matches terminals.
  - Bottom-up.
  - Linear (each token scanned once).
""")

# SCAN IN CODE
print("=== Scan in Code ===")

class EarleyItem:
    def __init__(self, lhs, rhs, dot=0, start=0):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
        self.start = start
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"[{self.lhs} → {' '.join(rhs)}, {self.start}]"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and
                self.start == other.start)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot, self.start))
    
    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 EarleyItem(self.lhs, self.rhs, self.dot + 1, self.start)


def scan(item, i, chart, tokens):
    """Scan operation."""
    if i >= len(tokens):
        return None
    next_sym = item.next_symbol()
    if next_sym == tokens[i]:
        new_item = item.advance()
        chart[i+1].add(new_item)
        return new_item
    return None


# Example
tokens = ['id', '+', 'id']
chart = [set() for _ in range(len(tokens) + 1)]

# Add some items to C[0]
chart[0].add(EarleyItem('F', ['id'], 0, 0))
chart[0].add(EarleyItem('E', ['E', '+', 'T'], 2, 0))  # E → E + · T

print("Scanning from C[0]:")
print(f"  Input: {tokens}")

# Scan F → · id with w₀ = id
item = EarleyItem('F', ['id'], 0, 0)
print(f"\n  Item: {item}")
print(f"  Next symbol: {item.next_symbol()}")
print(f"  Input[0]: {tokens[0]}")

result = scan(item, 0, chart, tokens)
if result:
    print(f"  Scan result: {result}")
    print(f"  Added to C[1]")

# Scan E → E + · T with w₀ = id (should fail)
item2 = EarleyItem('E', ['E', '+', 'T'], 2, 0)
print(f"\n  Item: {item2}")
print(f"  Next symbol: {item2.next_symbol()}")
print(f"  Input[0]: {tokens[0]}")

result2 = scan(item2, 0, chart, tokens)
if result2:
    print(f"  Scan result: {result2}")
else:
    print(f"  Scan failed (next symbol is nonterminal)")

print(f"\nC[1] contents:")
for item in sorted(chart[1], key=str):
    print(f"  {item}")

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

1. SCAN CONSUMES INPUT
   Only operation that advances position.
   Each token scanned once.

2. MATCHES TERMINAL
   Only if next symbol equals input.

3. MOVES TO i+1
   New item goes to next chart set.

4. ADVANCES DOT
   Dot moves past terminal.

5. BOTTOM-UP
   Scan is bottom-up.
   Consumes input.

=== Why Scan Works ===

Scan is simple:
  - Check if next symbol matches input.
  - If yes, advance dot.
  - Move to next position.

This is the only operation that
consumes input.
Predict and Complete work within
the same position.
Scan moves forward.

The three operations together
implement the Earley algorithm.
""")

✅ Complete

🎯 Finishing Rules

The Complete operation handles finished rules. When a rule is complete, it advances all items that were waiting for that nonterminal.

Complete Operation

Trigger: Complete item [A → α ·, j] in C[i]. Action: For each [B → γ · A δ, k] in C[j], add [B → γ A · δ, k] to C[i]. Meaning: "A is done, advance items waiting for A." Position: Stays at i. Bottom-up: Reduces rules.

✅ Complete📝 Nonterminal🔄 Advance⬆️ Bottom-up

# Complete Operation
print("=" * 60)
print("COMPLETE OPERATION")
print("=" * 60)

print("""
=== Definition ===

COMPLETE is triggered when:
  A complete item [A → α ·, j] is in C[i].

Action:
  For each item [B → γ · A δ, k] in C[j]:
    Add [B → γ A · δ, k] to C[i].

Meaning:
  "We've finished parsing A (from position j to i).
   Now advance items that were waiting for A."

=== Example ===

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

Input: id + id

C[0]:
  [T → · F, 0]
  [F → · id, 0]

Scan with w₀ = id:
  [F → id ·, 0] → C[1]

C[1]:
  [F → id ·, 0]  (complete)

Complete:
  Find items in C[0] waiting for F:
    [T → · F, 0]  (next symbol = F)
  
  Advance:
    [T → F ·, 0] → C[1]

C[1] now:
  [F → id ·, 0]
  [T → F ·, 0]

Complete again:
  [T → F ·, 0] is complete.
  Find items in C[0] waiting for T:
    [E → · T, 0]  (next symbol = T)
    [T → · T * F, 0]  (next symbol = T)
  
  Advance:
    [E → T ·, 0] → C[1]
    [T → T · * F, 0] → C[1]

C[1] now:
  [F → id ·, 0]
  [T → F ·, 0]
  [E → T ·, 0]
  [T → T · * F, 0]

Complete again:
  [E → T ·, 0] is complete.
  Find items in C[0] waiting for E:
    [S' → · E, 0]  (next symbol = E)
    [E → · E + T, 0]  (next symbol = E)
  
  Advance:
    [S' → E ·, 0] → C[1]
    [E → E · + T, 0] → C[1]

C[1] final:
  [F → id ·, 0]
  [T → F ·, 0]
  [E → T ·, 0]
  [T → T · * F, 0]
  [S' → E ·, 0]
  [E → E · + T, 0]

Continue to C[2], C[3].

=== Complete in Code ===

def complete(item, i, chart):
    lhs = item.lhs
    j = item.start
    for other in list(chart[j]):
        if not other.is_complete() and other.next_symbol() == lhs:
            new_item = other.advance()
            chart[i].add(new_item)

=== Why Complete Works ===

Complete is bottom-up:
  - A rule is finished.
  - This means A has been recognized.
  - Items waiting for A can advance.

This is like reduction in LR parsing:
  - But no conflicts.
  - No lookahead needed.
  - Dynamic programming.

=== Complete and the Chart ===

Complete looks back:
  - Item [A → α ·, j] in C[i].
  - Look at C[j] for items waiting for A.
  - Advance them to C[i].

This is why the start position j matters:
  - It tells us where to look for waiters.

=== Complete and Ambiguity ===

Complete handles ambiguity:
  - Multiple items can complete.
  - All are processed.
  - All parses are tracked.

Example:
  A → α | β
  Both α and β can complete.
  Complete advances items waiting for A
  for both parses.

This is how Earley handles ambiguity.

=== Complete and ε-Productions ===

For A → ε:
  [A → ·, i] is immediately complete.
  Complete advances items waiting for A.
  No scan needed (ε consumes no input).

This is how Earley handles ε.

=== Full Example: "id * id" ===

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

Input: id * id

C[0]:
  [S' → · E, 0]
  [E → · E + T, 0]
  [E → · T, 0]
  [T → · T * F, 0]
  [T → · F, 0]
  [F → · ( E ), 0]
  [F → · id, 0]

Scan: [F → id ·, 0] → C[1]
Complete: [T → F ·, 0] → C[1]
Complete: [T → T · * F, 0] → C[1]
Complete: [E → T ·, 0] → C[1]
Complete: [E → E · + T, 0] → C[1]

C[1]:
  [F → id ·, 0]
  [T → F ·, 0]
  [T → T · * F, 0]
  [E → T ·, 0]
  [E → E · + T, 0]

Scan: [T → T * · F, 0] → C[2]
Predict F: [F → · ( E ), 2], [F → · id, 2] → C[2]

C[2]:
  [T → T * · F, 0]
  [F → · ( E ), 2]
  [F → · id, 2]

Scan: [F → id ·, 2] → C[3]
Complete: [T → T * F ·, 0] → C[3]
Complete: [E → T ·, 0] → C[3]
Complete: [S' → E ·, 0] → C[3]

Accept: [S' → E ·, 0] ∈ C[3]. ✓

=== Summary of Complete ===

Trigger:
  Complete item [A → α ·, j] in C[i].

Action:
  For each [B → γ · A δ, k] in C[j]:
    Add [B → γ A · δ, k] to C[i].

Effect:
  Advances items waiting for A.
  Bottom-up reduction.

Position:
  Stays at i.

Key properties:
  - Handles ambiguity.
  - Handles ε-productions.
  - Bottom-up.
  - Dynamic programming.
""")

# COMPLETE IN CODE
print("=== Complete in Code ===")

class EarleyItem:
    def __init__(self, lhs, rhs, dot=0, start=0):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
        self.start = start
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"[{self.lhs} → {' '.join(rhs)}, {self.start}]"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and
                self.start == other.start)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot, self.start))
    
    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 EarleyItem(self.lhs, self.rhs, self.dot + 1, self.start)


def complete(item, i, chart):
    """Complete operation."""
    lhs = item.lhs
    j = item.start
    new_items = []
    for other in list(chart[j]):
        if not other.is_complete() and other.next_symbol() == lhs:
            new_item = other.advance()
            if new_item not in chart[i]:
                chart[i].add(new_item)
                new_items.append(new_item)
    return new_items


# Example
chart = [set() for _ in range(4)]

# C[0]: items waiting for F
chart[0].add(EarleyItem('T', ['F'], 0, 0))

# C[1]: complete item F → id ·
item = EarleyItem('F', ['id'], 1, 0)
chart[1].add(item)

print("Completing [F → id ·, 0] in C[1]:")
print(f"  Item: {item}")
print(f"  Looking in C[{item.start}] for items waiting for {item.lhs}")

# Complete
new_items = complete(item, 1, chart)

print(f"\n  Items in C[0] waiting for {item.lhs}:")
for other in sorted(chart[0], key=str):
    if not other.is_complete() and other.next_symbol() == item.lhs:
        print(f"    {other}")

print(f"\n  Advanced items added to C[1]:")
for ni in new_items:
    print(f"    {ni}")

print(f"\nC[1] contents:")
for it in sorted(chart[1], key=str):
    print(f"  {it}")

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

1. COMPLETE LOOKS BACK
   Complete item [A → α ·, j] in C[i].
   Look at C[j] for items waiting for A.

2. ADVANCES WAITERS
   Items waiting for A advance.
   New items go to C[i].

3. BOTTOM-UP
   Complete is the bottom-up component.
   Reduces rules.

4. HANDLES AMBIGUITY
   Multiple completes processed.
   All parses tracked.

5. HANDLES ε
   A → ε is immediately complete.
   Complete advances waiters.

=== Why Complete Works ===

Complete is like reduction in LR:
  - A rule is finished.
  - This means A has been recognized.
  - Items waiting for A can advance.

But unlike LR:
  - No conflicts.
  - No lookahead.
  - Dynamic programming.

This is why Earley is more general.

=== The Three Operations ===

Predict: top-down, expand nonterminals.
Scan: consume input.
Complete: bottom-up, reduce rules.

Together, they implement Earley parsing.
""")

🎯 Examples

🎯 Earley Parsing in Action

These examples illustrate the Earley parser on various grammars, showing how it handles different cases.

Example Categories

Simple: Basic arithmetic. Left recursion: E → E + T. Ambiguity: Multiple parses. ε-productions: Nullable rules. Complex: Natural language. Comparison: LL/LR vs Earley.

🔢 Arithmetic🔄 Left recursion🔀 Ambiguity📝 ε-productions

# Earley Parser Examples
print("=" * 60)
print("EARLEY PARSER EXAMPLES")
print("=" * 60)

# 1. SIMPLE ARITHMETIC
print("""
=== 1. Simple Arithmetic ===

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

Input: id + id * id

This grammar has:
  - Left recursion (E → E + T).
  - Precedence (* over +).
  - Parentheses.

Earley handles it naturally.

LL(1) would fail:
  - Can't handle left recursion.
  - Needs grammar transformation.

LR(1) would work:
  - But needs parsing table.
  - More complex.

Earley:
  - No grammar transformation.
  - Simple algorithm.
  - Works correctly.
""")

# 2. LEFT RECURSION
print("""
=== 2. Left Recursion ===

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

Left recursion: E → E + T, T → T * F.

LL(1) fails:
  - Infinite recursion.
  - Must eliminate left recursion.

Earley handles it:
  - Predict adds items.
  - No infinite loop.
  - Items stored in set.

Example: C[0]
  [E → · E + T, 0]  (predict)
  [E → · T, 0]      (predict)
  [T → · T * F, 0]  (predict)
  ...

The first item expects E.
Predict E again:
  [E → · E + T, 0]  (already there)

No infinite loop!
Because items are stored in a set.

=== 3. AMBIGUITY ===

Grammar:
  E → E + E | E * E | id

Input: id + id * id

Ambiguous:
  Two parse trees:
    (id + id) * id
    id + (id * id)

Earley handles it:
  - Tracks all parses.
  - Chart contains items for both.
  - Can return all parse trees.

LL(1) and LR(1) fail:
  - LL(1): conflicts.
  - LR(1): conflicts.
  - Need grammar transformation.

Earley:
  - No transformation.
  - Handles ambiguity.
  - Returns all parses.

=== 4. ε-PRODUCTIONS ===

Grammar:
  S → A B
  A → a | ε
  B → b | ε

Input: ab, a, b, ε

ε-productions:
  A → ε, B → ε.

Earley handles them:
  [A → ·, 0]  (predict, immediately complete)
  Complete advances items waiting for A.

LL(1):
  - Can handle ε.
  - But needs FIRST/FOLLOW.

Earley:
  - Handles ε naturally.
  - No special treatment.

=== 5. NATURAL LANGUAGE ===

Grammar (simplified English):
  S → NP VP
  NP → Det N | Det Adj N | NP PP
  VP → V NP | V PP | V
  PP → P NP
  Det → the | a
  N → cat | dog | mat
  V → sat | ate
  Adj → big | small
  P → on | in

Input: the big cat sat on the mat

Earley is used in NLP:
  - General CFG.
  - Handles ambiguity.
  - Handles complex structures.

LL/LR:
  - Need grammar transformation.
  - May have conflicts.
  - Less suitable for NLP.

Earley:
  - Natural fit.
  - Used in NLP tools.

=== 6. COMPARISON: LL vs LR vs Earley ===

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

Input: id + id * id

LL(1):
  - Must eliminate left recursion.
  - Transformed grammar:
    E → T E'
    E' → + T E' | ε
    ...
  - Works after transformation.

LR(1):
  - Handles left recursion.
  - Builds parsing table.
  - Works.

Earley:
  - Handles left recursion.
  - No transformation.
  - No table.
  - Works.

All three parse the input.
Earley is the most general.
""")

# EXAMPLES IN CODE
print("=== Examples in Code ===")

class EarleyItem:
    def __init__(self, lhs, rhs, dot=0, start=0):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
        self.start = start
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"[{self.lhs} → {' '.join(rhs)}, {self.start}]"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and
                self.start == other.start)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot, self.start))
    
    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 EarleyItem(self.lhs, self.rhs, self.dot + 1, self.start)


class EarleyParser:
    def __init__(self, grammar, start):
        self.grammar = grammar
        self.start = start
    
    def parse(self, tokens):
        n = len(tokens)
        chart = [set() for _ in range(n + 1)]
        
        chart[0].add(EarleyItem("S'", [self.start], 0, 0))
        
        for i in range(n + 1):
            items = list(chart[i])
            processed = set()
            
            while items:
                item = items.pop(0)
                if item in processed:
                    continue
                processed.add(item)
                
                if item.is_complete():
                    # COMPLETE
                    lhs = item.lhs
                    j = item.start
                    for other in list(chart[j]):
                        if not other.is_complete() and other.next_symbol() == lhs:
                            new_item = other.advance()
                            if new_item not in chart[i]:
                                chart[i].add(new_item)
                                items.append(new_item)
                else:
                    next_sym = item.next_symbol()
                    
                    if next_sym in self.grammar:
                        # PREDICT
                        for rhs in self.grammar[next_sym]:
                            new_item = EarleyItem(next_sym, rhs, 0, i)
                            if new_item not in chart[i]:
                                chart[i].add(new_item)
                                items.append(new_item)
                    
                    elif i < n and next_sym == tokens[i]:
                        # SCAN
                        new_item = item.advance()
                        chart[i + 1].add(new_item)
        
        return chart
    
    def accepts(self, tokens):
        chart = self.parse(tokens)
        n = len(tokens)
        for item in chart[n]:
            if item.lhs == "S'" and item.is_complete():
                return True
        return False


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

parser = EarleyParser(grammar, 'E')

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

test_inputs = [
    (['id'], True),
    (['id', '+', 'id'], True),
    (['id', '*', 'id'], True),
    (['id', '+', 'id', '*', 'id'], True),
    (['(', 'id', '+', 'id', ')', '*', 'id'], True),
    (['id', '+'], False),
    (['+', 'id'], False),
]

print("\nTest results:")
for tokens, expected in test_inputs:
    result = parser.accepts(tokens)
    status = "✓" if result == expected else "✗"
    print(f"  {status} '{' '.join(tokens)}' → {'ACCEPT' if result else 'REJECT'}")

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

parser2 = EarleyParser(ambiguous, 'E')

print("\nExample 2: Ambiguous Grammar")
print("Grammar:")
for lhs, prods in ambiguous.items():
    for rhs in prods:
        print(f"  {lhs} → {' '.join(rhs)}")

print("\nTest 'id + id * id' (ambiguous):")
result = parser2.accepts(['id', '+', 'id', '*', 'id'])
print(f"  Accepted: {result}")
print("  Note: Earley handles ambiguity (multiple parse trees).")

# Example 3: ε-productions
epsilon_grammar = {
    'S': [['A', 'B']],
    'A': [['a'], []],
    'B': [['b'], []],
}

parser3 = EarleyParser(epsilon_grammar, 'S')

print("\nExample 3: ε-Productions")
print("Grammar:")
for lhs, prods in epsilon_grammar.items():
    for rhs in prods:
        print(f"  {lhs} → {' '.join(rhs) if rhs else 'ε'}")

test_inputs3 = [
    ([], True),      # ε
    (['a'], True),   # a
    (['b'], True),   # b
    (['a', 'b'], True),  # ab
    (['a', 'a'], False),
]

print("\nTest results:")
for tokens, expected in test_inputs3:
    result = parser3.accepts(tokens)
    status = "✓" if result == expected else "✗"
    input_str = ' '.join(tokens) if tokens else 'ε'
    print(f"  {status} '{input_str}' → {'ACCEPT' if result else 'REJECT'}")

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

1. LEFT RECURSION
   Earley handles it naturally.
   No transformation needed.

2. AMBIGUITY
   Earley handles ambiguous grammars.
   Tracks all parses.

3. ε-PRODUCTIONS
   Earley handles ε.
   Items immediately complete.

4. GENERAL
   No grammar restrictions.
   Works on any CFG.

5. COMPARISON
   LL: needs transformation.
   LR: needs table, conflicts.
   Earley: general, no restrictions.

=== Why Earley is Special ===

Earley is the most general
practical parsing algorithm.
It handles:
  - Left recursion.
  - Ambiguity.
  - ε-productions.
  - Any CFG.

No grammar transformation.
No parsing table.
No conflicts.

This is why it's used in NLP
and general-purpose parsing.
""")

⏱️ Complexity

🎯 How Fast is Earley?

The Earley parser has different complexity depending on the grammar: O(n³) for general CFGs, O(n²) for unambiguous grammars, and O(n) for LL/LR grammars.

Complexity Results

General CFG: O(n³). Unambiguous: O(n²). LL/LR: O(n). Space: O(n²). Online: Left-to-right. Practical: Often faster.

⏱️ O(n³) general📊 O(n²) unambiguous⚡ O(n) LL/LR💾 O(n²) space

# Complexity of Earley Parsing
print("=" * 60)
print("COMPLEXITY OF EARLEY PARSING")
print("=" * 60)

print("""
=== Complexity Results ===

Earley parser complexity:

  General CFG:       O(n³) time, O(n²) space.
  Unambiguous CFG:   O(n²) time, O(n²) space.
  LL/LR CFG:         O(n) time, O(n²) space.
  
  n = length of input.

=== Why O(n³)? ===

The chart has n+1 sets.
Each set can have O(n) items (by start position).
Each item can trigger O(n) operations.

Total: O(n) × O(n) × O(n) = O(n³).

More precisely:
  - Number of items: O(n²).
  - Each item processed once.
  - Complete operation: O(n) per item.
  - Total: O(n³).

=== Why O(n²) for Unambiguous? ===

For unambiguous grammars:
  - Each substring has at most one parse.
  - Fewer items in the chart.
  - Complete operation: O(1) amortized.
  - Total: O(n²).

=== Why O(n) for LL/LR? ===

For LL/LR grammars:
  - Each position has O(1) items.
  - Deterministic parsing.
  - Total: O(n).

This matches LL/LR complexity.

=== Space Complexity ===

Space: O(n²).

Why?
  - Chart has n+1 sets.
  - Each set can have O(n) items.
  - Each item: O(1) space.
  - Total: O(n²).

Can be reduced to O(n) for some grammars.

=== Comparison with Other Parsers ===

Parser      Time        Space      Grammar Class
──────────────────────────────────────────────────
LL(1)       O(n)        O(n)       LL(1)
LR(1)       O(n)        O(n)       LR(1)
Earley      O(n³)       O(n²)      All CFG
            O(n²)       O(n²)      Unambiguous
            O(n)        O(n)       LL/LR
CYK         O(n³)       O(n²)      CNF
GLR         O(n³)       O(n²)      All CFG

Earley is slower than LL/LR in general.
But handles all CFGs.

=== Practical Performance ===

In practice, Earley is often faster:
  - Real grammars are usually unambiguous.
  - Chart is often sparse.
  - Optimizations help.

Optimizations:
  1. Item sharing (dynamic programming).
  2. Chart pruning.
  3. Lookahead.
  4. Packed parse forests.

With optimizations:
  - Close to O(n) for many grammars.
  - Practical for NLP.

=== The Earley Algorithm's Complexity ===

Let's derive O(n³) more carefully.

Number of items:
  - For each start position j (0 to n).
  - For each rule (|G| rules).
  - For each dot position (≤ |rule|).
  - Total: O(n × |G|) = O(n) items per start.
  - Total: O(n²) items.

Each item processed once:
  - Predict: O(|G|) per item.
  - Scan: O(1) per item.
  - Complete: O(n) per item.

Total: O(n² × n) = O(n³).

For unambiguous grammars:
  - Fewer items.
  - Complete: O(1).
  - Total: O(n²).

For LL/LR:
  - Even fewer items.
  - Total: O(n).

=== Space Complexity Details ===

Chart: n+1 sets.
Each set: O(n) items.
Each item: O(1) space.
Total: O(n²).

Can be reduced:
  - Only keep necessary items.
  - Use backpointers.
  - O(n) for LL/LR.

=== Comparison with CYK ===

CYK:
  - Requires CNF.
  - O(n³) time.
  - O(n²) space.
  - Bottom-up.

Earley:
  - Any CFG.
  - O(n³) time.
  - O(n²) space.
  - Top-down + bottom-up.

Earley is more general.
Both are O(n³).

=== Why Earley is Practical ===

Despite O(n³) worst case:
  - Most grammars are unambiguous.
  - Chart is often sparse.
  - Optimizations help.

In practice:
  - O(n²) or better for many grammars.
  - Used in NLP.
  - Used in general parsing.

=== Summary ===

Complexity:
  General CFG: O(n³) time, O(n²) space.
  Unambiguous: O(n²) time, O(n²) space.
  LL/LR: O(n) time, O(n²) space.

Comparison:
  Slower than LL/LR in worst case.
  But handles all CFGs.
  Practical with optimizations.

Key insight:
  Earley trades speed for generality.
  O(n³) worst case.
  But often much faster.
  Handles any CFG.
  No grammar restrictions.
""")

# COMPLEXITY TABLE
print("=== Complexity Comparison Table ===")
print(f"{'Parser':<12} {'Time':<12} {'Space':<12} {'Grammar':<20}")
print("-" * 60)
print(f"{'LL(1)':<12} {'O(n)':<12} {'O(n)':<12} {'LL(1)':<20}")
print(f"{'LR(1)':<12} {'O(n)':<12} {'O(n)':<12} {'LR(1)':<20}")
print(f"{'Earley':<12} {'O(n³)':<12} {'O(n²)':<12} {'All CFG':<20}")
print(f"{'Earley (unamb.)':<12} {'O(n²)':<12} {'O(n²)':<12} {'Unambiguous':<20}")
print(f"{'Earley (LL/LR)':<12} {'O(n)':<12} {'O(n)':<12} {'LL/LR':<20}")
print(f"{'CYK':<12} {'O(n³)':<12} {'O(n²)':<12} {'CNF':<20}")
print(f"{'GLR':<12} {'O(n³)':<12} {'O(n²)':<12} {'All CFG':<20}")

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

1. EARLEY IS SLOWER
   O(n³) vs O(n) for LL/LR.
   But handles all CFGs.

2. UNAMBIGUOUS IS FASTER
   O(n²) instead of O(n³).
   Most real grammars are unambiguous.

3. LL/LR IS FASTEST
   O(n) for restricted grammars.
   But less general.

4. SPACE IS O(n²)
   Chart can be large.
   But manageable.

5. PRACTICAL PERFORMANCE
   Often much faster than worst case.
   Optimizations help.
   Used in NLP.

=== When to Use Earley ===

Use Earley when:
  - Grammar is not LL/LR.
  - Grammar is ambiguous.
  - Grammar has left recursion.
  - Generality is needed.

Use LL/LR when:
  - Grammar is LL/LR.
  - Speed is critical.
  - Table can be built.

Use CYK when:
  - Grammar is in CNF.
  - Bottom-up is preferred.

Key insight:
  Earley is the general-purpose parser.
  O(n³) worst case.
  But often faster.
  Handles any CFG.
  No grammar restrictions.
""")

🔀 Ambiguity

🎯 Handling Multiple Parses

The Earley parser naturally handles ambiguous grammars. It tracks all possible parses in the chart and can return all parse trees or a packed parse forest.

Ambiguity Handling

Multiple items: Chart holds all parses. No conflicts: All paths explored. Packed forest: Shared structure. All parses: Can extract. Efficiency: Shared work. NLP: Common in natural language.

🔀 Ambiguity📊 Chart🌳 Parse forest📝 NLP

# Ambiguity in Earley Parsing
print("=" * 60)
print("AMBIGUITY IN EARLEY PARSING")
print("=" * 60)

print("""
=== What is Ambiguity? ===

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

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

Input: id + id * id

Parse 1: (id + id) * id
  E → E * E
    → (E + E) * E
    → (id + id) * id

Parse 2: id + (id * id)
  E → E + E
    → id + (E * E)
    → id + (id * id)

Both are valid.
The grammar is ambiguous.

=== LL/LR vs Earley ===

LL(1):
  - Conflicts.
  - Must choose one parse.
  - Ambiguity unresolved.

LR(1):
  - Conflicts.
  - Must choose one parse.
  - Ambiguity unresolved.

Earley:
  - No conflicts.
  - Tracks all parses.
  - Can return all parse trees.

=== How Earley Handles Ambiguity ===

The chart contains ALL possible items.
No conflicts because:
  - Items are stored in sets.
  - Multiple items can be in the same set.
  - All are processed.

Example:
  C[1] after "id":
    [F → id ·, 0]
    [T → F ·, 0]
    [E → T ·, 0]
    [T → T · * F, 0]
    [E → E · + T, 0]
  
  All these items represent different
  possible parses.
  All are tracked.

=== Packed Parse Forest ===

For efficiency, Earley uses a PACKED PARSE FOREST:
  - Shared structure.
  - Multiple parses in one DAG.
  - Extract individual parses on demand.

Nodes in forest:
  - (Nonterminal, start, end).
  - Multiple rules for same node.

Example:
  Node (E, 0, 3) might have:
    E → E + E
    E → E * E
  
  Both derivations for the same span.

=== Extracting Parse Trees ===

To extract a parse tree:
  1. Start from (S, 0, n).
  2. Choose a rule.
  3. Recursively extract children.
  4. Build tree.

For all parses:
  - Enumerate all choices.
  - Exponential in worst case.
  - But shared structure helps.

=== Example: Ambiguous Expression ===

Grammar:
  E → E + E | E * E | id

Input: id + id * id

Earley chart (partial):

C[0]:
  [S' → · E, 0]
  [E → · E + E, 0]
  [E → · E * E, 0]
  [E → · id, 0]

C[1] after "id":
  [E → id ·, 0]
  [E → E · + E, 0]
  [E → E · * E, 0]
  [S' → E ·, 0]

C[2] after "+":
  [E → E + · E, 0]
  [E → · E + E, 2]
  [E → · E * E, 2]
  [E → · id, 2]

C[3] after "id":
  [E → id ·, 2]
  [E → E · + E, 2]
  [E → E · * E, 2]
  [E → E + E ·, 0]  ← complete E → E + E
  ...

C[4] after "*":
  [E → E * · E, 2]
  ...

C[5] after "id":
  [E → id ·, 4]
  [E → E · + E, 4]
  [E → E · * E, 4]
  [E → E * E ·, 2]  ← complete E → E * E
  [E → E + E ·, 0]  ← complete E → E + E (using E * E)
  [S' → E ·, 0]

Two parses:
  1. E → E + E (with E → E * E inside)
     = id + (id * id)
  2. E → E * E (with E → E + E inside)
     = (id + id) * id

Both are in the chart.
Both can be extracted.

=== Ambiguity in NLP ===

Natural language is highly ambiguous:
  "I saw the man with the telescope."
  
  Parse 1: I saw (the man with the telescope).
  Parse 2: I (saw the man) with the telescope.

Earley handles this:
  - Tracks all parses.
  - Uses probabilities to rank.
  - Packed forest for efficiency.

This is why Earley is used in NLP.

=== Advantages of Earley for Ambiguity ===

1. NO CONFLICTS
   All parses tracked.
   No need to choose.

2. SHARED WORK
   Dynamic programming.
   Common subparses shared.

3. PACKED FOREST
   Efficient representation.
   Extract parses on demand.

4. GENERAL
   Handles any ambiguous grammar.
   No restrictions.

5. NLP
   Natural for natural language.
   Used in parsers.

=== Disadvantages ===

1. EXPONENTIAL PARSES
   Number of parses can be exponential.
   Packed forest handles this.

2. COMPLEXITY
   O(n³) for ambiguous.
   Slower than deterministic.

3. MEMORY
   O(n²) space.
   Can be large.

4. EXTRACTION
   Extracting all parses can be expensive.

=== Summary ===

Earley handles ambiguity:
  - No conflicts.
  - Tracks all parses.
  - Packed parse forest.
  - Used in NLP.

Key insight:
  Ambiguity is not a problem for Earley.
  It's a feature.
  All parses are tracked.
  Packed forest for efficiency.
  Ideal for natural language.
""")

# AMBIGUITY IN CODE
print("=== Ambiguity Example ===")

class EarleyItem:
    def __init__(self, lhs, rhs, dot=0, start=0):
        self.lhs = lhs
        self.rhs = tuple(rhs)
        self.dot = dot
        self.start = start
    
    def __repr__(self):
        rhs = list(self.rhs)
        rhs.insert(self.dot, '·')
        return f"[{self.lhs} → {' '.join(rhs)}, {self.start}]"
    
    def __eq__(self, other):
        return (self.lhs == other.lhs and 
                self.rhs == other.rhs and 
                self.dot == other.dot and
                self.start == other.start)
    
    def __hash__(self):
        return hash((self.lhs, self.rhs, self.dot, self.start))
    
    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 EarleyItem(self.lhs, self.rhs, self.dot + 1, self.start)


def earley_parse(grammar, start, tokens):
    n = len(tokens)
    chart = [set() for _ in range(n + 1)]
    
    chart[0].add(EarleyItem("S'", [start], 0, 0))
    
    for i in range(n + 1):
        items = list(chart[i])
        processed = set()
        
        while items:
            item = items.pop(0)
            if item in processed:
                continue
            processed.add(item)
            
            if item.is_complete():
                lhs = item.lhs
                j = item.start
                for other in list(chart[j]):
                    if not other.is_complete() and other.next_symbol() == lhs:
                        new_item = other.advance()
                        if new_item not in chart[i]:
                            chart[i].add(new_item)
                            items.append(new_item)
            else:
                next_sym = item.next_symbol()
                if next_sym in grammar:
                    for rhs in grammar[next_sym]:
                        new_item = EarleyItem(next_sym, rhs, 0, i)
                        if new_item not in chart[i]:
                            chart[i].add(new_item)
                            items.append(new_item)
                elif i < n and next_sym == tokens[i]:
                    new_item = item.advance()
                    chart[i + 1].add(new_item)
    
    return chart


# Ambiguous grammar
ambiguous_grammar = {
    'E': [['E', '+', 'E'], ['E', '*', 'E'], ['id']],
}

tokens = ['id', '+', 'id', '*', 'id']

print("Ambiguous grammar:")
for lhs, prods in ambiguous_grammar.items():
    for rhs in prods:
        print(f"  {lhs} → {' '.join(rhs)}")

print(f"\nInput: {' '.join(tokens)}")

chart = earley_parse(ambiguous_grammar, 'E', tokens)

print(f"\nChart size: {sum(len(c) for c in chart)} items")

# Check acceptance
n = len(tokens)
accepted = False
for item in chart[n]:
    if item.lhs == "S'" and item.is_complete():
        accepted = True
        break

print(f"Accepted: {accepted}")

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

1. MULTIPLE ITEMS
   Chart contains items for all parses.
   No conflicts.

2. COMPLETION
   E → E + E completes.
   E → E * E completes.
   Both tracked.

3. ACCEPTANCE
   [S' → E ·, 0] in C[5].
   Accepted.

4. ALL PARSES
   Both parse trees are represented.
   Packed forest would extract them.

5. EFFICIENCY
   Shared work.
   Dynamic programming.

=== Why Earley Handles Ambiguity ===

Earley doesn't choose.
It tracks all possibilities.
The chart is a set.
Multiple items can coexist.
No conflicts.

This is a fundamental advantage
over LL and LR.
""")

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

Ambiguity:
  Multiple parse trees for same string.

LL/LR:
  Conflicts.
  Must choose one parse.
  Ambiguity unresolved.

Earley:
  No conflicts.
  Tracks all parses.
  Packed parse forest.
  Can return all parse trees.

Packed parse forest:
  Shared structure.
  DAG representation.
  Extract parses on demand.

NLP:
  Natural language is ambiguous.
  Earley is ideal for NLP.
  Tracks all parses.
  Uses probabilities to rank.

Key insight:
  Ambiguity is a feature, not a bug.
  Earley handles it naturally.
  No conflicts.
  All parses tracked.
  Packed forest for efficiency.
  Ideal for natural language.
""")

📊 Comparison

🎯 Earley vs LL vs LR vs CYK

Comparing Earley with other parsing algorithms: power, complexity, and practical use.

Parser Comparison

Earley: General, O(n³). LL(1): Simple, O(n). LR(1): Powerful, O(n). CYK: CNF, O(n³). GLR: General, O(n³). PEG: Ordered choice.

🔍 Earley⬇️ LL⬆️ LR📊 CYK

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

print("""
=== Detailed Comparison ===

Algorithm   Time       Space      Grammar        Direction    Ambiguity
────────────────────────────────────────────────────────────────────────
LL(1)       O(n)       O(n)       LL(1)          Top-down     No
LR(1)       O(n)       O(n)       LR(1)          Bottom-up    No
Earley      O(n³)      O(n²)      All CFG        Both         Yes
  (unamb.)  O(n²)      O(n²)      Unambiguous    Both         No
  (LL/LR)   O(n)       O(n)       LL/LR          Both         No
CYK         O(n³)      O(n²)      CNF            Bottom-up    Yes
GLR         O(n³)      O(n²)      All CFG        Bottom-up    Yes
PEG         O(n)       O(n)       PEG            Top-down     No

=== Earley vs LL ===

LL(1):
  - Top-down.
  - Predictive.
  - No left recursion.
  - No common prefixes.
  - O(n) time.
  - Hand-written.

Earley:
  - Both top-down and bottom-up.
  - No restrictions.
  - Handles left recursion.
  - Handles ambiguity.
  - O(n³) worst case.
  - General.

When to use:
  LL: simple grammars, hand-written.
  Earley: complex grammars, general.

=== Earley vs LR ===

LR(1):
  - Bottom-up.
  - Shift-reduce.
  - Handles left recursion.
  - Conflicts possible.
  - O(n) time.
  - Tool-generated.

Earley:
  - Both.
  - No conflicts.
  - No restrictions.
  - Handles ambiguity.
  - O(n³) worst case.
  - General.

When to use:
  LR: programming languages, tool-generated.
  Earley: general CFG, NLP.

=== Earley vs CYK ===

CYK:
  - Requires CNF.
  - Bottom-up.
  - O(n³) time.
  - O(n²) space.
  - Dynamic programming.

Earley:
  - Any CFG.
  - Both.
  - O(n³) time.
  - O(n²) space.
  - Dynamic programming.

When to use:
  CYK: CNF grammars, simple.
  Earley: any CFG, more general.

=== Earley vs GLR ===

GLR:
  - Generalized LR.
  - Handles ambiguity.
  - Forks parse stack.
  - O(n³) time.
  - Bottom-up.

Earley:
  - Chart parsing.
  - Handles ambiguity.
  - No forking.
  - O(n³) time.
  - Both.

When to use:
  GLR: LR-like grammars, ambiguity.
  Earley: any CFG, NLP.

=== Earley vs PEG ===

PEG:
  - Ordered choice.
  - No ambiguity.
  - O(n) time.
  - Backtracking.
  - Not CFG.

Earley:
  - All CFG.
  - Handles ambiguity.
  - O(n³) time.
  - No backtracking.
  - General.

When to use:
  PEG: DSLs, simple parsing.
  Earley: general CFG, NLP.

=== Practical Comparison ===

Aspect              Earley       LL(1)      LR(1)      CYK
─────────────────────────────────────────────────────────────
Grammar class       All CFG      LL(1)      LR(1)      CNF
Left recursion      Yes          No         Yes        Yes
Ambiguity           Yes          No         No         Yes
Time (general)      O(n³)        O(n)       O(n)       O(n³)
Time (unamb.)       O(n²)        O(n)       O(n)       O(n³)
Space               O(n²)        O(n)       O(n)       O(n²)
Online              Yes          Yes        Yes        No
Hand-written        Hard         Easy       Hard       Hard
Tool support        Some         ANTLR      Yacc/Bison Few

=== Choosing a Parser ===

For PROGRAMMING LANGUAGES:
  → LR(1) / LALR(1).
  Fast, tool-generated.

For SIMPLE GRAMMARS:
  → LL(1).
  Hand-written, good errors.

For NATURAL LANGUAGE:
  → Earley.
  General, handles ambiguity.

For CNF GRAMMARS:
  → CYK.
  Simple, bottom-up.

For GENERAL CFG:
  → Earley or GLR.
  Both handle all CFGs.

=== Why Earley is Special ===

Earley is:
  - General (any CFG).
  - Handles ambiguity.
  - Handles left recursion.
  - Online.
  - Dynamic programming.

Earley is not:
  - Fastest (O(n³)).
  - Simplest (more complex than LL).
  - Most common (LR is more common).

But Earley is:
  - Most general.
  - Best for NLP.
  - Best for ambiguous grammars.
  - Best for research.

=== Summary ===

Earley:
  - General CFG.
  - O(n³) worst case.
  - Handles ambiguity.
  - Handles left recursion.
  - Used in NLP.

LL/LR:
  - Restricted grammars.
  - O(n) time.
  - No ambiguity.
  - Used in compilers.

Key insight:
  Earley trades speed for generality.
  O(n³) vs O(n).
  But handles all CFGs.
  Best for NLP and general parsing.
""")

# COMPARISON TABLE
print("=== Summary Table ===")
print(f"{'Parser':<12} {'Time':<10} {'Space':<10} {'Grammar':<15} {'Ambiguity':<10} {'Use':<15}")
print("-" * 75)
print(f"{'LL(1)':<12} {'O(n)':<10} {'O(n)':<10} {'LL(1)':<15} {'No':<10} {'Compilers':<15}")
print(f"{'LR(1)':<12} {'O(n)':<10} {'O(n)':<10} {'LR(1)':<15} {'No':<10} {'Compilers':<15}")
print(f"{'Earley':<12} {'O(n³)':<10} {'O(n²)':<10} {'All CFG':<15} {'Yes':<10} {'NLP':<15}")
print(f"{'CYK':<12} {'O(n³)':<10} {'O(n²)':<10} {'CNF':<15} {'Yes':<10} {'Theory':<15}")
print(f"{'GLR':<12} {'O(n³)':<10} {'O(n²)':<10} {'All CFG':<15} {'Yes':<10} {'C++':<15}")
print(f"{'PEG':<12} {'O(n)':<10} {'O(n)':<10} {'PEG':<15} {'No':<10} {'DSLs':<15}")

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

1. GENERALITY
   Earley: any CFG.
   LL/LR: restricted grammars.

2. SPEED
   LL/LR: O(n).
   Earley: O(n³).

3. AMBIGUITY
   Earley: handles it.
   LL/LR: doesn't.

4. NLP
   Earley: ideal.
   LL/LR: less suitable.

5. COMPILERS
   LR: standard.
   Earley: rare.

Key insight:
  Different parsers for different needs.
  Earley for generality.
  LL/LR for speed.
  CYK for CNF.
  PEG for DSLs.
""")

💼 Applications

🎯 Earley in the Real World

The Earley parser is used in natural language processing, grammar tools, and anywhere general CFG parsing is needed.

Application Areas

NLP: Natural language parsing. Grammar tools: Parser generators. Research: Computational linguistics. Education: Teaching parsing. Prototyping: Quick parsers. Ambiguity: Ambiguous grammars.

📝 NLP🛠️ Tools🔬 Research🎓 Education

# Applications of Earley Parsing
print("=" * 60)
print("APPLICATIONS OF EARLEY PARSING")
print("=" * 60)

# 1. NLP
print("""
=== 1. Natural Language Processing ===

Natural language is:
  - Highly ambiguous.
  - Context-free (approximately).
  - Complex.

Earley is ideal for NLP:
  - Handles ambiguity.
  - Handles complex grammars.
  - Tracks all parses.

Examples:
  "I saw the man with the telescope."
  
  Ambiguous:
    I saw (the man with the telescope).
    I (saw the man) with the telescope.
  
  Earley tracks both.

Tools:
  - NLTK (Python)
  - Various research parsers
  - Chart parsers

=== 2. Grammar Tools ===

Earley is used in:
  - Parser generators.
  - Grammar checkers.
  - Syntax highlighters.
  - Language servers.

Example: Grammar checker
  - Parse sentence.
  - Check grammar rules.
  - Report errors.

Earley's generality helps:
  - No grammar restrictions.
  - Handles complex rules.

=== 3. Research ===

Computational linguistics:
  - Parsing natural language.
  - Grammar induction.
  - Statistical parsing.

Earley is a baseline:
  - General CFG parser.
  - Used for comparison.
  - Foundation for extensions.

Extensions:
  - Probabilistic Earley.
  - Earley with unification.
  - Earley for tree adjoining grammars.

=== 4. Education ===

Teaching parsing:
  - General algorithm.
  - Handles any CFG.
  - No restrictions.

Earley is taught in:
  - Compiler courses.
  - NLP courses.
  - Formal language courses.

Why?
  - General.
  - Elegant.
  - Dynamic programming.
  - Historical importance.

=== 5. Prototyping ===

Quick parser development:
  - No grammar transformation.
  - No table construction.
  - Just write grammar and parse.

Earley is good for:
  - Prototypes.
  - Small languages.
  - DSLs.
  - Experiments.

Advantages:
  - Fast development.
  - No restrictions.
  - Easy to modify.

=== 6. Ambiguous Grammars ===

When ambiguity is inherent:
  - Natural language.
  - Some DSLs.
  - Research languages.

Earley handles ambiguity:
  - Tracks all parses.
  - Packed forest.
  - Extract on demand.

LL/LR can't:
  - Conflicts.
  - Must choose.
  - Lose information.

=== 7. Case Study: NLTK ===

NLTK (Natural Language Toolkit):
  - Python library for NLP.
  - Includes Earley parser.
  - Used in research and education.

Example:
  import nltk
  from nltk.parse import EarleyChartParser
  
  grammar = nltk.CFG.fromstring('''
    S -> NP VP
    NP -> Det N | Det Adj N
    VP -> V NP | V
    Det -> 'the' | 'a'
    N -> 'cat' | 'dog'
    V -> 'sat' | 'ate'
    Adj -> 'big' | 'small'
  ''')
  
  parser = EarleyChartParser(grammar)
  for tree in parser.parse(['the', 'big', 'cat', 'sat']):
      print(tree)

This is a classic NLP example.

=== 8. Case Study: Speech Recognition ===

Speech recognition:
  - Input: sequence of words.
  - Output: parse tree.

Earley is used:
  - General CFG.
  - Handles ambiguity.
  - Probabilistic extensions.

Example:
  "recognize speech" vs "wreck a nice beach"
  
  Ambiguity at word level.
  Earley tracks all parses.
  Probabilities rank them.

=== 9. Case Study: Information Extraction ===

Information extraction:
  - Extract structured data from text.
  - Use grammar to define patterns.

Earley:
  - Parse text.
  - Extract patterns.
  - Handle ambiguity.

Example:
  "John Smith, age 30, lives in NYC."
  
  Grammar:
    Person -> Name ',' 'age' Number ',' 'lives' 'in' City
  
  Earley parses and extracts.

=== 10. Summary of Applications ===

Application         Use Case
─────────────────────────────────────────
NLP                 Natural language parsing
Grammar tools       Parser generators
Research            Computational linguistics
Education           Teaching parsing
Prototyping         Quick parsers
Ambiguity           Ambiguous grammars
Speech              Speech recognition
Info extraction     Structured data
""")

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

Applications:
  1. NLP: natural language parsing.
  2. Grammar tools: parser generators.
  3. Research: computational linguistics.
  4. Education: teaching parsing.
  5. Prototyping: quick parsers.
  6. Ambiguity: ambiguous grammars.
  7. Speech: speech recognition.
  8. Info extraction: structured data.

Key advantages:
  - General CFG.
  - Handles ambiguity.
  - Handles left recursion.
  - No grammar transformation.
  - Dynamic programming.

Tools:
  - NLTK (Python)
  - Various research parsers
  - Custom implementations

Key insight:
  Earley is the general-purpose parser.
  Ideal for NLP.
  Ideal for ambiguous grammars.
  Ideal for research.
  Trades speed for generality.
  But it's practical and widely used.
""")

🚀 Advanced Topics

🎯 Beyond Basic Earley

The Earley algorithm has been extended in many ways: probabilistic Earley, Earley with unification, incremental Earley, and parallel Earley.

Advanced Directions

Probabilistic: PCFG parsing. Unification: Feature structures. Incremental: Online parsing. Parallel: Multi-core. Tree: Tree adjoining. Neural: Learned parsing.

📊 Probabilistic🔗 Unification⚡ Incremental🧠 Neural

# Advanced Topics in Earley Parsing
print("=" * 60)
print("ADVANCED TOPICS")
print("=" * 60)

# 1. PROBABILISTIC EARLEY
print("""
=== 1. Probabilistic Earley ===

Probabilistic CFG (PCFG):
  - Each rule has a probability.
  - Sum of probabilities = 1.

Probabilistic Earley:
  - Compute probability of each parse.
  - Find most likely parse.
  - Use inside-outside algorithm.

Algorithm:
  - Items have probabilities.
  - Complete combines probabilities.
  - Viterbi for best parse.

Applications:
  - NLP parsing.
  - Speech recognition.
  - Machine translation.

Tools:
  - NLTK (probabilistic Earley)
  - Custom implementations

=== 2. Earley with Unification ===

Unification-based grammar:
  - Feature structures.
  - Unification constraints.
  - More expressive than CFG.

Earley with unification:
  - Items have feature structures.
  - Unification during Complete.
  - Handles agreement, case, etc.

Applications:
  - Linguistics.
  - Grammar formalisms (HPSG, LFG).
  - Natural language understanding.

Challenge:
  - Unification can be expensive.
  - Need efficient data structures.

=== 3. Incremental Earley ===

Incremental parsing:
  - Parse as input arrives.
  - No re-parsing from scratch.
  - Update chart incrementally.

Algorithm:
  - Keep chart between inputs.
  - Process new token.
  - Update items.

Applications:
  - IDEs.
  - Interactive systems.
  - Speech recognition.

Challenge:
  - State management.
  - Error recovery.

=== 4. Parallel Earley ===

Parallel parsing:
  - Multi-core.
  - Process positions in parallel.
  - Share chart.

Algorithm:
  - Partition chart.
  - Parallel Predict, Scan, Complete.
  - Synchronization.

Challenges:
  - Dependencies between positions.
  - Synchronization overhead.
  - Load balancing.

Applications:
  - Large-scale parsing.
  - Real-time systems.
""")

# 5. TREE ADJOINING GRAMMARS
print("""
=== 5. Earley for TAG ===

Tree Adjoining Grammars (TAG):
  - More powerful than CFG.
  - Mildly context-sensitive.
  - Used in NLP.

Earley for TAG:
  - Extend Earley to trees.
  - Handle adjunction.
  - More complex.

Applications:
  - NLP (linguistics).
  - Treebanks.

Challenge:
  - More complex algorithm.
  - Higher complexity.

=== 6. Earley for Multiple Context-Free Grammars ===

MCFG:
  - More powerful than CFG.
  - Handles some non-CFG languages.
  - Used in NLP.

Earley for MCFG:
  - Extend items to tuples.
  - Handle multiple dimensions.
  - More complex.

Applications:
  - NLP (cross-serial dependencies).
  - Formal language theory.

=== 7. Neural Earley ===

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

Hybrid approaches:
  - Neural + Earley.
  - Use neural for predictions.
  - Use Earley for structure.

Applications:
  - NLP.
  - Machine translation.
  - Information extraction.

Research:
  - Active area.
  - Combining symbolic and neural.

=== 8. Open Problems ===

1. EFFICIENCY
   Can Earley be O(n²) for all grammars?
   No (known lower bounds).

2. INCREMENTAL
   Efficient incremental parsing?
   Active research.

3. PROBABILISTIC
   Efficient probabilistic Earley?
   Inside-outside is O(n³).

4. PARALLEL
   Scalable parallel Earley?
   Challenges remain.

5. UNIFICATION
   Efficient unification?
   Depends on grammar.

6. NEURAL
   Neural-symbolic parsing?
   Active research.

=== 9. RECOMMENDATIONS ===

For students:
  1. Master basic Earley first.
  2. Implement it from scratch.
  3. Understand complexity.
  4. Study applications.
  5. Explore extensions.

For researchers:
  1. Probabilistic Earley.
  2. Incremental parsing.
  3. Neural-symbolic.
  4. Parallel parsing.
  5. Unification.

For practitioners:
  1. Use Earley for NLP.
  2. Use LL/LR for compilers.
  3. Understand trade-offs.
  4. Profile performance.
  5. Optimize as needed.

=== Final Thoughts ===

Earley parser is:

✓ GENERAL
  Handles any CFG.

✓ ELEGANT
  Simple algorithm.
  Dynamic programming.

✓ POWERFUL
  Handles ambiguity.
  Handles left recursion.

✓ PRACTICAL
  Used in NLP.
  Used in research.

✓ EXTENSIBLE
  Probabilistic, unification, incremental.

✓ HISTORICAL
  One of the first general parsers.
  Still relevant today.

Key takeaway:
  Earley is the general-purpose parser.
  It trades speed for generality.
  O(n³) worst case.
  But handles all CFGs.
  Ideal for NLP and ambiguous grammars.
  
  Understanding Earley is essential
  for anyone working in parsing,
  NLP, or computational linguistics.

"Parsing is the bridge between
 text and meaning."
  — Computational Linguist

Go parse something!
""")

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

Earley Parser:
  - General CFG parsing.
  - Dynamic programming (chart).
  - Three operations: Predict, Scan, Complete.

Item:
  [A → α · β, j]

Operations:
  Predict: expand nonterminal.
  Scan: consume terminal.
  Complete: finish rule.

Acceptance:
  [S' → S ·, 0] ∈ C[n].

Complexity:
  O(n³) general.
  O(n²) unambiguous.
  O(n) LL/LR.

Space:
  O(n²).

Advantages:
  - Any CFG.
  - Handles ambiguity.
  - Handles left recursion.
  - Online.

Disadvantages:
  - O(n³) worst case.
  - More complex than LL.

Applications:
  - NLP.
  - Grammar tools.
  - Research.
  - Prototyping.

Tools:
  - NLTK (Python).
  - Various research parsers.

Key insight:
  Earley is the general-purpose parser.
  Ideal for NLP.
  Ideal for ambiguous grammars.
  Trades speed for generality.
  Still relevant today.
""")