5

我必须检查是否可以从 Chomsky 范式的给定上下文中派生一个字符串。我正在使用 C++。

维基百科文章中有非常好的伪代码涵盖了 CYK 算法，但我不能很好地理解它。

有人会这么好心地帮助我，给我另一个 CYK 算法的伪代码，或者解释一下 wiki 文章中的那个吗？

4

1 回答 1

5

CYK 算法以乔姆斯基范式的 CFG 作为输入。这意味着每个产品要么具有形式

  • S → a，对于某个终端 a，或
  • S → AB，对于一些非终结符 A 和 B。

现在，假设您有一个字符串 w，并且您想查看是否可以从起始符号为 S 的文法中导出它。有两种选择：

  1. 如果 w 是单个字符长，那么解析它的唯一方法是对某个字符 a 使用形式 S → a 的产生式。因此，请查看是否有任何单字符产品与 a 匹配。
  2. 如果 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;
}

这个算法可以正常工作，但是如果你绘制出递归的形状，你会发现

  1. 它进行了大量冗余的递归调用，但是
  2. 没有那么多不同的可能递归调用。

事实上，不同的可能调用的数量是 O(n 2 N)，其中 n 是输入字符串的长度（对于开始和结束索引的每个可能组合），N 是语法中非终结符的数量。这些观察表明，该算法将受益于记忆化或动态编程，这取决于您碰巧认为哪种方法更好。

当您采用上述递归算法并记住结果时，或者等效地当您将上述递归算法转换为动态规划问题时，您会得到 CYK 算法。

有 O(n 2 N) 个可能的递归调用。对于每个尝试的生产，它确实 O(n) 工作。如果一个非终结符平均有 P 个产生式，这意味着总运行时间是 O(n 3 NP)，对于固定语法来说是 O(n 3 )。

于 2017-07-19T21:19:24.660 回答