| |
CYK algorithm[Categories: Parsing algorithms]
The Cocke-Younger-Kasami (CYK) algorithm (alternatively called CKY) determines whether a
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 is an example of dynamic programming.
The standard version of CYK recognizes languages defined by context-free grammars written in Chomsky normal form
(CNF). Since any context-free grammar can be converted to CNF without
too much difficulty, CYK can be used to recognize any context-free
language. It is also possible to extend the CYK algorithm to handle
some context-free grammars which are not written in CNF; this may be
done to improve performance, although at the cost of making the
algorithm harder to understand.
The worst case asymptotic time complexity of CYK is Θ(n3), where n
is the length of the parsed string. This makes it one of the most
efficient (in those terms) algorithms for recognizing any context-free
language. However, there are other algorithms that will perform better
for certain subsets of the context-free languages.
The CYK
algorithm is important theoretically, since it can be used to
constructively prove that the membership problem for context-free
languages is decidable.
The CYK algorithm for the membership problem is as follows:- Let the input string be a sequence of n letters a1 ... an.
- Let the grammar contain r terminal and nonterminal symbols R1 ... Rr. This grammar contains the subset Rs which is the set of start symbols.
- Let P[n,n,r] be an array of booleans. Initialize all elements of P to false.
- For each i = 1 to n
For each unit production Rj → ai, set P[i,1,j] = true.- For each i = 2 to n -- Length of span
For each j = 1 to n-i+1 -- Start of span
For each k = 1 to i-1 -- Partition of span
For each production RA -> RB RC- If P[j,k,B] and P[j+k,i-k,C] then set P[j,i,A] = true
- If any of P[1,n,x] is true (x is iterated over the set s, where s are all the indices for Rs)
Then string is member of language
Else string is not member of language
In
informal terms, this algorithm considers every possible consecutive
subsequence of the sequence of letters and sets P[i,j,k] to be true if
the sequence of letters starting from i of length j can be generated
from Rk. Once it has considered sequences of length 1, it
goes on to sequences of length 2, and so on. For subsequences of length
2 and greater, it considers every possible partition of the subsequence
into two halves, and checks to see if there is some production P → Q R
such that Q matches the first half and R matches the second half. If
so, it records P as matching the whole subsequence. Once this process
is completed, the sentence is recognized by the grammar if the
subsequence containing the entire string is matched by the start symbol.
|
CYK table| S | | | VP | | | | | | S | | | | | | VP | | | PP | | S | | NP | | | NP | | NP | V, VP | Det. | N | P | Det | N | | she | eats | a | fish | with | a | fork |
It
is simple to extend the above algorithm to not only determine if a
sentence is in a language, but to also construct a parse tree, by
storing parse tree nodes as elements of the array, instead of booleans.
Since the grammars being recognized can be ambiguous, it is necessary
to store a list of nodes (unless one wishes to only pick one possible
parse tree); the end result is then a forest of possible parse trees.
An alternative formulation employs a second table B[n,n,r] of so-called backpointers.
It is also possible to extend the CYK algorithm to parse strings using weighted and stochastic context-free grammars.
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).
References John Cocke
and Jacob T. Schwartz (1970). Programming languages and their
compilers: Preliminary notes. Technical report, Courant Institute of
Mathematical Sciences, New York University.
T. Kasami (1965). An efficient recognition and syntax-analysis
algorithm for context-free languages. Scientific report AFCRL-65-758,
Air Force Cambridge Research Lab, Bedford, MA.
Daniel H. Younger (1967). Recognition and parsing of context-free languages in time n3. Information and Control 10(2): 189–208.
Víctor M. Jiménez and András Marzal (2000). Computation of the N best parse trees for weighted and stochastic context-free grammars. Proc. SSPR/SPR 2000, Lecture Notes in Computer Science 1876: 183–192.
More Subjects form Category
| | The source of this article is Wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL. |
|
|
|
