Top-down Parsing: Earley and Predictive Parsers

Top-down Parsing: Earley and Predictive Parsers

Recall first

Why can naïve recursive descent loop on A → A x? Which top-down parser uses a chart and can handle general CFGs?

First principles

The syllabus says “Early”; the standard algorithm is Earley parsing, named after Jay Earley. It is a top-down chart parser for general context-free grammars. An Earley state is written

[A → α • β, j]

in chart position i: the parser has recognized α, expects β, and the production began at origin j.

For each chart position, apply:

• Predictor: if the dot is before nonterminal B, add [B → • γ, i] for each B → γ.
• Scanner: if the dot expects terminal a and the next input is a, advance the dot to the next chart.
• Completer: if [B → γ •, j] completes at i, advance any state in chart j waiting for B.

Duplicate states are stored once. A final completed start state indicates acceptance. Earley handles left recursion and grammars beyond CNF; worst-case complexity is cubic, with faster behavior for more restricted/unambiguous cases. It can preserve ambiguity in a shared chart rather than blindly committing to one derivation.

A predictive parser is a restricted top-down parser, commonly recursive descent with one-symbol lookahead (LL(1)). It selects a production using FIRST sets; if a production can derive ε, FOLLOW information helps decide. It requires a suitably factored grammar with no left recursion and no FIRST/FIRST or relevant FIRST/FOLLOW conflicts. It is simple and often linear, but grammar transformation may be needed and ambiguous/general CFGs are outside its comfortable range.

Worked micro-trace. For S→NP VP, NP→Det N, input the dog, start with [S→•NP VP,0]. Predictor adds [NP→•Det N,0], then [Det→•the,0]; scanner reads the; completion of Det advances NP to [NP→Det • N,0]; prediction adds N; scanner reads dog; completing N completes NP, advancing S to [S→NP • VP,0]. The trace shows prediction, scanning, and completion—not a stack-only reduction.

Exercise — reveal after answering

Which grammar repair helps predictive parsing with A → A x | y?

Answer: Remove left recursion, e.g. A → y A' and A' → x A' | ε, then use FIRST/FOLLOW-guided choice.

Exam lens

Correct the spelling to Earley politely if needed. List the three Earley operations and state chart positions. Contrast Earley’s generality with predictive parsing’s LL(1) speed/grammar restrictions.

Rapid revision checklist

• Write Earley state notation.
• Recall predictor, scanner, completer.
• Define LL(1), FIRST, FOLLOW, and left-recursion issue.
• Compare generality and complexity.

Key takeaways

• Earley is chart-based top-down parsing for general CFGs.
• Predictive parsing chooses one production from lookahead under strong grammar conditions.
• Left recursion is a central top-down hazard; Earley handles it, LL(1) grammar must remove it.

Sources

• Jurafsky & Martin, Ch. 18: Context-Free Grammars and Constituency Parsing
• Earley, “An Efficient Context-Free Parsing Algorithm” (DOI)
• Jurafsky & Martin, Appendix F: Context-Free Grammars