CYK Context-Free Parse Counts

Parsing a string using a context-free grammar tells us whether the string is in the language generated by the grammar. When a grammar is ambiguous, a string can have multiple valid parse trees. The CYK (Cocke-Younger-Kasami) algorithm uses dynamic programming to efficiently determine membership and can also count the exact number of distinct parse trees.

Calculating parse counts

Consider the grammar S → SS | a. Let's trace the CYK algorithm for the string aaa. The algorithm builds a triangular chart where each cell (i, l) represents the substrings of length l starting at index i.

Length 1: The substrings are a at index 0, 1, and 2. Each derives from S with count 1.
Length 2: Substrings aa at index 0 and 1. The only split is S → SS (length 1 + length 1). Cell counts are 1 * 1 = 1 for S.
Length 3: Substring aaa at index 0. There are two splits: left length 1 + right length 2, and left length 2 + right length 1.
Split 1 gives count = 1 * 1 = 1. Split 2 gives count = 1 * 1 = 1. The total count for S spanning length 3 is 2.

The expected result is exactly 2 parse trees for aaa.

Visualizing the chart

Use the interactive chart to observe how parse counts multiply and accumulate.

Set Grammar to "Ambiguous a".
Set Tokens to "aaaa".
Observe that the Parse count is 5, which corresponds to the 4th Catalan number (Catalan(3) = 5).
Change the Grammar back to "Matched blocks" and observe that the parse count becomes 0, because "aaaa" cannot be generated by that grammar.

Assumptions and boundaries

This model assumes the grammar is already in Chomsky Normal Form (CNF), where all rules are eitherA → BC or A → a. Grammars not in CNF must be converted first. Additionally, this explorer does not support empty strings (epsilon transitions); an empty token list evaluates to a parse count of 0.

Primary references

For a complete explanation of the CYK parsing algorithm and ambiguity, refer to the notes fromYale CS470 Lecture 31.

CYK Context-Free Parse Counts