CYK algorithm
Class | Parsing with context-free grammars |
---|---|
Data structure | String |
Worst-case performance | , where:
|
In computer science, the Cocke–Younger–Kasami algorithm (alternatively called CYK, or CKY) is a parsing algorithm for context-free grammars published by Itiroo Sakai in 1961.[1][2] The algorithm is named after some of its rediscoverers: John Cocke, Daniel Younger, Tadao Kasami, and Jacob T. Schwartz. It employs bottom-up parsing and dynamic programming.
The standard version of CYK operates only on context-free grammars given in Chomsky normal form (CNF). However any context-free grammar may be algorithmically transformed into a CNF grammar expressing the same language (Sipser 1997).
The importance of the CYK algorithm stems from its high efficiency in certain situations. Using big O notation, the worst case running time of CYK is , where is the length of the parsed string and is the size of the CNF grammar (
Standard form
The dynamic programming algorithm requires the context-free grammar to be rendered into Chomsky normal form (CNF), because it tests for possibilities to split the current sequence into two smaller sequences. Any context-free grammar that does not generate the empty string can be represented in CNF using only production rules of the forms , , and where is the start symbol.[3]
Algorithm
As pseudocode
The algorithm in pseudocode is as follows:
let the input be a string I consisting of n characters: a1 ... an. let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1. let P[n,n,r] be an array of booleans. Initialize all elements of P to false. let back[n,n,r] be an array of lists of backpointing triples. Initialize all elements of back to the empty list. for each s = 1 to n for each unit production Rv → as set P[1,s,v] = true for each l = 2 to n -- Length of span for each s = 1 to n-l+1 -- Start of span for each p = 1 to l-1 -- Partition of span for each production Ra → Rb Rc if P[p,s,b] and P[l-p,s+p,c] then set P[l,s,a] = true, append <p,b,c> to back[l,s,a] if P[n,1,1] is true then I is member of language return back -- by retracing the steps through back, one can easily construct all possible parse trees of the string. else return "not a member of language"
Probabilistic CYK (for finding the most probable parse)
Allows to recover the most probable parse given the probabilities of all productions.
let the input be a string I consisting of n characters: a1 ... an. let the grammar contain r nonterminal symbols R1 ... Rr, with start symbol R1. let P[n,n,r] be an array of real numbers. Initialize all elements of P to zero. let back[n,n,r] be an array of backpointing triples. for each s = 1 to n for each unit production Rv →as set P[1,s,v] = Pr(Rv →as) for each l = 2 to n -- Length of span for each s = 1 to n-l+1 -- Start of span for each p = 1 to l-1 -- Partition of span for each production Ra → Rb Rc prob_splitting = Pr(Ra →Rb Rc) * P[p,s,b] * P[l-p,s+p,c] if prob_splitting > P[l,s,a] then set P[l,s,a] = prob_splitting set back[l,s,a] = <p,b,c> if P[n,1,1] > 0 then find the parse tree by retracing through back return the parse tree else return "not a member of language"
As prose
In informal terms, this algorithm considers every possible substring of the input string and sets to be true if the substring of length starting from can be generated from the nonterminal . Once it has considered substrings of length 1, it goes on to substrings of length 2, and so on. For substrings of length 2 and greater, it considers every possible partition of the substring into two parts, and checks to see if there is some production such that matches the first part and matches the second part. If so, it records as matching the whole substring. Once this process is completed, the input string is generated by the grammar if the substring containing the entire input string is matched by the start symbol.
Example
This is an example grammar:
Now the sentence she eats a fish with a fork is analyzed using the CYK algorithm. In the following table, in , i is the number of the row (starting at the bottom at 1), and j is the number of the column (starting at the left at 1).
S | ||||||
VP | ||||||
S | ||||||
VP | PP | |||||
S | NP | NP | ||||
NP | V, VP | Det. | N | P | Det | N |
she | eats | a | fish | with | a | fork |
For readability, the CYK table for P is represented here as a 2-dimensional matrix M containing a set of non-terminal symbols, such that Rk is in if, and only if, . In the above example, since a start symbol S is in , the sentence can be generated by the grammar.
Extensions
Generating a parse tree
The above algorithm is a
Parsing non-CNF context-free grammars
As pointed out by Lange & Leiß (2009), the drawback of all known transformations into Chomsky normal form is that they can lead to an undesirable bloat in grammar size. The size of a grammar is the sum of the sizes of its production rules, where the size of a rule is one plus the length of its right-hand side. Using to denote the size of the original grammar, the size blow-up in the worst case may range from to , depending on the transformation algorithm used. For the use in teaching, Lange and Leiß propose a slight generalization of the CYK algorithm, "without compromising efficiency of the algorithm, clarity of its presentation, or simplicity of proofs" (Lange & Leiß 2009).
Parsing weighted context-free grammars
It is also possible to extend the CYK algorithm to parse strings using
Numerical stability
When the probabilistic CYK algorithm is applied to a long string, the splitting probability can become very small due to multiplying many probabilities together. This can be dealt with by summing log-probability instead of multiplying probabilities.
Valiant's algorithm
The worst case running time of CYK is , where n is the length of the parsed string and |G| is the size of the CNF grammar G. This makes it one of the most efficient algorithms for recognizing general context-free languages in practice. Valiant (1975) gave an extension of the CYK algorithm. His algorithm computes the same parsing table as the CYK algorithm; yet he showed that algorithms for efficient multiplication of matrices with 0-1-entries can be utilized for performing this computation.
Using the
See also
References
- ISBN 978-0-387-20248-8.
- ^ Itiroo Sakai, “Syntax in universal translation”. In Proceedings 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Her Majesty’s Stationery Office, London, p. 593-608, 1962.
- OCLC 58544333.
- arXiv:1504.01431 [cs.CC].
Sources
- Sakai, Itiroo (1962). Syntax in universal translation. 1961 International Conference on Machine Translation of Languages and Applied Language Analysis, Teddington, England. Vol. II. London: Her Majesty’s Stationery Office. pp. 593–608.
- Cocke, John; Schwartz, Jacob T. (April 1970). Programming languages and their compilers: Preliminary notes (PDF) (Technical report) (2nd revised ed.). CIMS, NYU.
- ISBN 0-201-02988-X.
- AFCRL. 65-758.
- ISBN 0-201-89684-2.
- Lang, Bernard (1994). "Recognition can be harder than parsing". S2CID 5873640.
- Lange, Martin; Leiß, Hans (2009). "To CNF or not to CNF? An Efficient Yet Presentable Version of the CYK Algorithm". Informatica Didactica. 8.
- S2CID 1243491.
- ISBN 0-534-94728-X.
- .
- Younger, Daniel H. (February 1967). "Recognition and parsing of context-free languages in time n3". .