Course contentsShow
← Computer Science
Lesson 1846 of 2,87241. Context-Free LanguagesFree lesson

Earley Parsing Algorithm

General parsing algorithm that handles any CFG including ambiguous grammars efficiently.

Earley Parsing Algorithm

What you'll learn: You'll discover a general parsing algorithm that can handle any context-free grammar, including ambiguous ones, with remarkable efficiency.

The Big Picture

After learning specialized algorithms like CYK (which requires Chomsky Normal Form), you might wonder: Is there a way to parse any CFG directly, without preprocessing? The Earley parsing algorithm is that solution. Developed by Jay Earley in 1968, it handles all context-free grammars—left-recursive, right-recursive, ambiguous—exactly as written.

How It Works

Think of the Earley parser as a detective tracking multiple hypotheses simultaneously. It builds Earley items (also called states) that represent partially matched production rules at specific positions in the input string.

An Earley item looks like: A → α • β [j]

  • The dot • shows how far we've matched this rule
  • [j] records where this rule application started in the input

The algorithm fills a chart with sets of items (one set per input position) using three operations:

  1. Prediction: When the dot precedes a nonterminal, add items for all rules that could expand it
  2. Scanning: When the dot precedes a terminal that matches the next input symbol, advance the dot
  3. Completion: When the dot reaches the end of a rule, update all items waiting for that nonterminal

The parser processes input left-to-right in a single pass, maintaining all possible parse paths simultaneously through nondeterminism.

Why It Matters

Earley parsing runs in O(n³) time for any CFG, O(n²) for unambiguous grammars, and O(n) for most deterministic grammars—adapting its efficiency to grammar structure. Unlike CYK, it needs no grammar transformation.

Key Takeaway: The Earley algorithm provides a universal, efficient parsing solution that accepts any CFG in its natural form, making it ideal for flexible language processing where grammar preprocessing is impractical.