Earley Nullable Chart Parsing
Follow a chart parser through nullable productions, left recursion and ambiguous derivations.
Free theory articleFollow a chart parser through nullable productions, left recursion and ambiguous derivations.
Concept & interpretation
The Earley parser is an algorithm for parsing strings that belong to a given context-free grammar. Unlike naive top-down or bottom-up approaches, it handles left-recursive rules, nullable productions, and ambiguous grammars gracefully, typically running in O(N³) time for general CFGs and O(N²) for unambiguous ones.
Experiment
Open the Earley Nullable Chart Parsing interactive module to explore how the chart states change with different grammars and input words.
- Select the Grammar "Ambiguous concatenation" (S → S S | a).
- Change the Word to "aaabbb". Observe how the parser immediately halts expansion for tokens not matching the grammar, leaving later charts empty and producing a "No" for acceptance.
- Change the Word back to "aa". The parser populates multiple states tracking the ambiguities. The independent parse tree count for "aa" is evaluated to 1, while "aaa" (or higher) will show Catalan number growth.