Skip to content
Algorithm Atlas
ParsingAll categories
SpecializedSource checked

CYK Algorithm

Checks whether a string can be generated by a context-free grammar.

Explore relationshipsOpen constellationBrowse atlas

Quick Facts

Compact metadata for implementation and discovery.

Category
Parsing
Difficulty
Advanced
Family
Dynamic Programming Parser
Tier
Specialized
Status
Verified
Review
Source Checked
Sources
1
Formulas
1
Relationships
2
Code example
Not ready
Visualization
Ready
Aliases
Cocke-Younger-Kasami Algorithm

Overview

The CYK Algorithm fills a table of grammar variables that can produce each substring.

Core Concepts

grammar normalizationspan tabledynamic programmingparse recognitionparse stategrammar productiondynamic programming parsertoken stream

Quick facts

Complexity

Runtime and memory behavior at a glance.

Best

O(n^3 |G|)

Average

O(n^3 |G|)

Worst

O(n^3 |G|)

Space

O(n^2 |G|)

When to Use

  • Use CYK Algorithm when you need to parse with dynamic programming.
  • Use it for formal language analysis with inputs like string of tokens.
  • Use it when text or tokens must be turned into a reliable structured representation.
  • Use it when the Dynamic Programming Parser tradeoff is acceptable for the problem size.

When Not to Use

  • Avoid it when the state table would exceed available memory.
  • Avoid it when the grammar is ambiguous or left-recursive in ways the parser cannot handle.
  • Avoid it when O(n^3 |G|) worst-case behavior is too costly for the expected input size.
  • Avoid it when the required output is not accepted or rejected result.

What It Does

  • Parses with dynamic programming
  • Tests grammar membership

Use Cases

  • Formal language analysis
  • Teaching parsing theory
  • Grammar validation

Inputs

  • String of tokens
  • Grammar in Chomsky normal form

Outputs

  • Accepted or rejected result
  • Optional parse table

Key Formulas (1)

Span combination

table[start, length] includes A if A → B C and B,C cover a split
table[start, length] includes A if A -> B C and B,C cover a split

Builds parse recognition from shorter spans.

Pseudocode

  1. 1.Fill table cells for substrings of length one
  2. 2.For each longer substring length:
  3. 3.Split the substring at every possible point
  4. 4.Check grammar rules that combine left and right variables
  5. 5.Accept if the start symbol appears for the full string

Canonical Example

Input
tokens = ['2', '+', '3', '*', '4']
Output
structured expression tree or evaluated result
Explanation
CYK Algorithm: The parser uses grammar or precedence rules to recover structure from tokens.

Implementation Notes

  • Keep the input contract explicit: String of tokens; Grammar in Chomsky normal form.
  • Use this step as the implementation spine: Fill table cells for substrings of length one.
  • Then preserve the next state change: For each longer substring length:.
  • Name the DP state and transition before writing loops.
  • Keep tokenization separate from parsing unless the algorithm explicitly combines them.

Common Pitfalls

  • CYK requires the grammar to be converted to Chomsky normal form.
  • Small grammar changes can introduce ambiguity or precedence mistakes.
  • Producing unclear errors that do not point to the token or rule that failed.
  • Returning accepted or rejected result without handling empty, invalid, or boundary inputs.

Interactive Mechanism Walkthrough

Sequence Window & Automaton Alignment

Show a triangular dynamic programming table filling from short spans to long spans.

Input:ABABABCABAB
Window:ABAB
Step 1 of 5: Fill table cells for substrings of length one
parse-chart

Notes

CYK Algorithm operates in O(n^3 |G|) time and O(n^2 |G|) space within the Dynamic Programming Parser family. Key governing relation: table[start, length] includes A if A -> B C and B,C cover a split. Often compared with Recursive Descent Parsing and Pratt Parsing.

Sources (1)

What each reference supports for this entry.

Introduction to Automata Theory, Languages, and Computation

Book

Formal-languages reference for CYK parsing over context-free grammars in Chomsky normal form.

Explore Next

Good next jumps from the relationship graph, ranked for useful discovery.

Open discoveryOpen map
Alternative toEarley Parser

Parsing · Specialized

CYK and Earley parsing are dynamic-programming parsers for context-free grammars.

Compare with this

Relationships

View full relationship page
Alternative toEarley Parser

CYK and Earley parsing are dynamic-programming parsers for context-free grammars.

Related Algorithms

Recursive Descent ParsingPratt Parsing

Tags

ParsingGrammarDynamic Programming