Earley Nullable Chart Parsing

Worked Example

Let us trace the Earley algorithm for the grammar Matched pairs: S → a S b | ε on the word aabb of length 4. The initial state adds the start rule to Chart 0.

1. Chart 0 (Initial): We predict S → a S b and S → ε. Since S can be empty, we also bypass the nullable symbol and complete START → S • (0).
2. Chart 1 (Token a): The parser scans a from S → • a S b in Chart 0, adding S → a • S b (0) to Chart 1. We then predict the same rules for S in Chart 1.
3. Chart 2 (Token a): We scan the second a, creating S → a • S b (1) in Chart 2. Again, we predict rules for S.
4. Chart 3 (Token b): Scanning b requires completing an S first. The nullable prediction S → • (2) in Chart 2 is instantly completed, advancing S → a S • b (1) in Chart 2. This rule can now scan the b, adding S → a S b • (1) to Chart 3.
5. Chart 4 (Token b): In Chart 3, completing S triggers completion in Chart 1, creating S → a S • b (0) in Chart 3. Scanning the final b produces S → a S b • (0) in Chart 4. Finally, START → S • (0) is completed in Chart 4, proving the word is accepted. The parse count is exactly 1.

Experiment

Open the Earley Nullable Chart Parsing interactive module to explore how the chart states change with different grammars and input words.

1. Select the Grammar "Ambiguous concatenation" (S → S S | a).
2. 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.
3. 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.

Limitations

The visualization assumes a finite predefined set of grammars and fixed input tokens to demonstrate nullable closures and recursive descents. It is not a general-purpose grammar editor. While Earley parsing can technically handle any CFG, tracking the exact parse tree counts for highly ambiguous grammars (like S → S S | ε) without loops requires more advanced shared packed parse forest (SPPF) extraction. Here, parse counts are computed independently via dynamic programming or Catalan numbers for the known domain. Numerical limits apply to precision if string lengths exceed Javascript's exact integer capabilities.

References

The Earley parser was introduced by Jay Earley in his seminal 1970 paper. For historical context and deep dive into the algorithm's origins:

Earley, J. (1968). "An Efficient Context-Free Parsing Algorithm"— This technical report describes the foundational mechanism for maintaining sets of items to parse general context-free grammars efficiently, establishing the core predictability and completion phases simulated in the interactive charts.