CYK Context-Free Parse Counts
Count context-free parse trees by combining span charts and grammar rules.
Free theory articleCount context-free parse trees by combining span charts and grammar rules.
Concept & interpretation
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.
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.