CYK 算法将乔姆斯基范式的 CFG 作为输入。这意味着每个产生式要么具有以下形式
- S → a，对于某个终端 a，或者
- S → AB，对于某些非终结符 A 和 B。
现在，假设您有一个字符串 w，并且您想看看是否可以从起始符号为 S 的语法中导出它。有两个选项：
- 如果 w 是单个字符长，那么解析它的唯一方法是对某个字符 a 使用 S → a 形式的产生式。因此，看看是否有任何单字符产品可以匹配 a。
- 如果 w 超过一个字符长，那么解析它的唯一方法是对某些非终结符 A 和 B 使用 S → AB 形式的产生式。这意味着我们需要将字符串 w 分成两部分 x 和 y其中 A 导出 x，B 导出 y。一种方法是尝试将 w 分成两部分的所有可能方法，并查看其中是否有效。
请注意，这里的选项 (2) 最终成为一个递归解析问题：要查看是否可以从 S 导出 w，请查看是否可以从 A 导出 x，从 B 导出 y。
有了这种洞察力，下面是递归函数的伪代码，您可以使用它来查看非终结符 S 是否派生出字符串 w：
bool canDerive(nonterminal S, string w) {
return canDeriveRec(S, w, 0, w.size());
}
/* Can you derive the substring [start, end) of w from S? */
bool canDeriveRec(nonterminal S, string w, int start, int end) {
/* Base case: Single characters */
if (end - start == 1) {
return whether there is a production S -> a, where a = w[start];
}
/* Recursive case: Try all possible splits */
for (each production S -> AB) {
for (int mid = start + 1; mid < end; mid++) {
if (canDeriveRec(A, w, start, mid) &&
canDeriveRec(B, w, mid, end)) {
return true;
}
}
}
return false;
}
这个算法工作正常，但是如果你绘制出递归的形状，你会发现
- 它进行了大量冗余的递归调用，但是
- 没有那么多不同的可能的递归调用。
In fact, the number of distinct possible calls is O(n2 N), where n is the length of the input string (for each possible combination of a start and end index) and N is the number of nonterminals in the grammar. These observations suggest that this algorithm would benefit either from memoization or dynamic programming, depending on which approach you happen to think is nicer.
CYK算法是当你采用上述递归算法并记住结果时得到的，或者等效地将上述递归算法转换为动态规划问题时得到的。
There are O(n2 N) possible recursive calls. For each production tried, it does O(n) work. If there are P productions, on average, for a nonterminal, this means the overall runtime is O(n3 NP), which is O(n3) for a fixed grammar.
