The CYK algorithm, also called the Cocke-Younger-Kasami algorithm, is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961 and named for several of its rediscoverers, including John Cocke, Daniel Younger and Tadao Kasami. It uses bottom-up parsing and dynamic programming, operates on grammars in Chomsky normal form, into which any context-free grammar can be algorithmically converted, and its worst-case running time makes it one of the most efficient parsing algorithms by asymptotic complexity, even though other algorithms can be faster in practice.
Facts
Classification
Design Technique Sources
1. CYK Algorithm (Wikipedia)
https://en.wikipedia.org/wiki/CYK_algorithmQuote, https://en.wikipedia.org/wiki/CYK_algorithm
It employs bottom-up parsing and dynamic programming.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.