General Parsing

General Parsing Algorithms

While LL and LR parsers are incredibly fast ($O(n)$ time complexity), they are restrictive. They fail to parse ambiguous grammars or grammars with unresolved conflicts.

AutomataLab provides two General parsing algorithms. These algorithms can parse any Context-Free Grammar, even highly ambiguous ones, at the cost of slower time complexity ($O(n^3)$).

---

1. CYK Parser (Cocke-Younger-Kasami)

The CYK algorithm is a classic dynamic programming approach to parsing. It uses a triangular matrix (the CYK Table) to systematically build up valid derivations for substrings of the input.

The CNF Requirement

CYK has one strict, absolute requirement: The grammar must be in Chomsky Normal Form (CNF). Because every rule in CNF either produces exactly two non-terminals or exactly one terminal, the CYK algorithm can reliably split any substring of length $L$ into two smaller substrings of length $k$ and $L-k$, and check the table dynamically.

If you attempt to select the CYK parser on a non-CNF grammar, AutomataLab will refuse to run it. You must first use the Grammar Lab's CNF Conversion tool.

CYK Execution in AutomataLab

1. Convert your grammar to CNF.
2. Switch to Parser Studio and select CYK.
3. Type an input string.
4. Press Step.

AutomataLab visually populates the triangular CYK matrix step-by-step.

• The bottom row (length 1 substrings) is filled first by matching terminals.
• Higher rows are filled by mathematically combining the sets of non-terminals from two smaller cells in the rows below.
• If the Start Symbol $S$ appears in the very top cell of the matrix, the string is accepted!

---

2. Earley Parser

The Earley Parser is arguably the most robust parsing algorithm implemented in AutomataLab.

Unlike CYK, Earley does not require CNF. It can parse raw, unmodified grammars directly, including heavily left-recursive and ambiguous grammars without failing or looping infinitely.

Earley Chart Execution

Earley parsing works by constructing an array of State Sets (or a Chart) for every token position in the input string.

At each step, AutomataLab performs three fundamental operations on the Chart:

1. Predict: If the parser expects a non-terminal $X$, it adds all production rules for $X$ to the current state set with the dot • at the beginning.
2. Scan: If the parser expects a terminal that matches the next input token, it advances the dot and moves the rule into the next state set.
3. Complete: If a rule is fully parsed (the dot is at the end), the parser looks back to where that rule started and advances the dot for the "parent" rule that was waiting for it.

Ambiguity Handling

If you feed a highly ambiguous string to the Earley parser, it will successfully parse it. In the background, it generates a "Parse Forest" containing all valid derivation trees.

See Also

• Top-Down Parsing
• Bottom-Up Parsing
• Grammar Transformations