CYK法（）は、ある文字列が与えられた文脈自由文法で生成できるかを決め、生成できる場合の生成方法を求めるアルゴリズムである。CYK は Cocke-Younger-Kasami の略。文字列の構文解析手法として知られている。このアルゴリズムは一種の動的計画法である。標準的なCYK法は、チョムスキー標準形で書かれた文脈自由文法で定義される言語を認識する。任意の文脈自由文法をチョムスキー標準形に書き換えるのはそれほど困難ではないので、CYK法は任意の文脈自由文法の認識に使うことができる。CYK法を拡張してチョムスキー標準形で書かれていない文脈自由文法を扱うようにすることも可能である。これにより性能は向上するが、アルゴリズムを理解することは難しくなる。CYK法の最悪時間計算量は Θ(n) であり、"n" は解析対象の文字列の長さである。従って、CYK法は任意の文脈自由言語を認識できる最も効率的なアルゴリズムの1つである。ただし、文脈自由言語の特定のサブセットについて、より効率の良いアルゴリズムが他に存在する。CYK法はボトムアップ構文解析アルゴリズムであり、文脈自由言語のメンバシップ問題が決定可能であることを構成的に証明できることから、理論的にも重要である。メンバシップ問題についてのCYK法は次の通り。形式的でない説明をするなら、このアルゴリズムは単語の並びについて、考えられるあらゆる組合せを考慮し、与えられた文字列の i 番目から長さ j の並びが R から生成される場合に P[i,j,k] を true にセットする。長さ 1 の並びを検討したら、次に長さ 2 の並びというように検討していく。長さ 2 以上の並びの場合、その並びを2つに分け（分け方を様々に変えて）、P → Q R という生成規則で Q と R がその並びの前半部分と後半部分にマッチするかどうかを調べる。マッチする場合、P をその並び全体にマッチするものとして記録する。この一連の処理が完了すると、入力文字列全体を含む記号の並びが開始記号から生成されるかどうかが判定できる。このアルゴリズムを、文が言語に含まれるかどうかを決定するだけでなく、構文木を構築するよう拡張するには、構文木のノードをブーリアンの代わりに配列の要素として格納すればよい。認識しようとする文法は曖昧な場合があるので、ノードのリストを格納する必要がある（可能な解釈からひとつだけ選べばよい場合はその限りではない）。従って、結果として複数の構文木が得られる。別の方式としては、"backpointers" と呼ばれる第二のテーブル B[n,n,r] を使う方式もある。加重文脈自由文法や確率文脈自由文法を使って文字列の構文解析をするよう拡張することも可能である。この場合、加重や確率はテーブル P にブーリアンの代わりに格納される。すなわち、P[i,j,A] は i から長さ j の並びが A から生成される最小加重（または最大確率）を格納する。さらにアルゴリズムを拡張すれば、あらゆる加重（確率）の構文木を列挙できる。

出典:wikipedia