Content deleted Content added
→External Links: Added link to an online demo of CKY. |
m Correct standard headers and general fixes |
||
Line 1:
The '''Cocke-Younger-Kasami (CYK) algorithm''' (alternatively called CKY) determines whether a
[[string (computer science)|string]] can be generated by a given [[context-free grammar]] and, if so, how it can be generated. This is known as [[parsing]] the string. The algorithm employs [[bottom-up parsing]] and [[dynamic programming]].
The standard version of CYK operates on context-free grammars given in [[Chomsky normal form]] (CNF). Any context-free grammar may be written thus.
| last=Sipser
| first=Michael
Line 18:
==Standard form==
The algorithm as given in [[pseudocode]] is as follows:
===As pseudocode===
'''Let''' the input be a string ''S'' consisting of ''n''characters: ''a''<sub>1</sub> ... ''a''<sub>''n''</sub>.
'''Let''' the grammar contain ''r'' nonterminal symbols ''R''<sub>1</sub> ... ''R''<sub>''r''</sub>.
This grammar contains the subset R<sub>s</sub> which is the set of start symbols.
'''Let''' P[n,n,r] be an array of booleans. Initialize all elements of P to false.
Line 50 ⟶ 51:
| || VP || || || PP
|-
| '''S'''|| || NP || || || NP
|-
| NP || V, VP || Det. || N || P || Det || N
|- style="border-top:3px solid grey;"
| she || eats || a || fish || with || a || fork
|}
Line 68 ⟶ 69:
It is also possible to extend the CYK algorithm to parse strings using [[weighted context-free grammar|weighted]] and [[stochastic context-free grammar]]s. Weights (probabilities) are then stored in the table P instead of booleans, so P[i,j,A] will contain the minimum weight (maximum probability) that the substring from i to j can be derived from A. Further extensions of the algorithm allow all parses of a string to be enumerated from lowest to highest weight (highest to lowest probability).
==
* [[Earley parser]]
* [[Packrat parser]]
Line 78 ⟶ 79:
* Daniel H. Younger (1967). Recognition and parsing of context-free languages in time ''n''<sup>3</sup>. ''Information and Control'' 10(2): 189–208.
==
* [http://homepages.uni-tuebingen.de/student/martin.lazarov/demos/cky.html CYK parsing demo in JavaScript]<br/>
* [http://www.informatik.uni-leipzig.de/alg/lehre/ss08/AUTO-SPRACHEN/Java-Applets/CYK-Algorithmus.html Interactive Applet from the University of Leipzig to demonstrate the CYK-Algorithm (Site is in german)]<br />
* [http://www.swisseduc.ch/compscience/exorciser/ Exorciser is a Java application to generate exercises in the CYK algorithm as well as Finite State Machines, Markov algorithms etc (this page is in English)]
[[Category:Parsing algorithms]]
| |||