Как работает алгоритм CYK?

Алгоритм CYK принимает на вход CFG в нормальной форме Хомского. Это означает, что всякая продукция либо имеет вид

• S a, для некоторого терминала a, или
• S AB для некоторых нетерминалов A и B.

Теперь представьте, что у вас есть строка w, и вы хотите узнать, можно ли вывести ее из грамматики, начальным символом которой является S. Есть два варианта:

1. Если w состоит из одного символа, то единственный способ разобрать его — использовать произведение формы S a для некоторого символа a. Итак, посмотрите, будет ли какое-либо из односимвольных произведений соответствовать a.
2. Если w имеет длину более одного символа, то единственный способ разобрать его — использовать произведение вида S AB для некоторых нетерминалов A и B. Это означает, что нам нужно разделить строку w на две части x и y, где A выводит x, а B выводит y. Один из способов сделать это — попробовать все возможные способы разбиения w на две части и посмотреть, работает ли какой-либо из них.

Обратите внимание, что вариант (2) здесь заканчивается проблемой рекурсивного синтаксического анализа: чтобы увидеть, можете ли вы вывести w из S, посмотрите, можете ли вы вывести x из A и y из B.

С учетом этого понимания вот псевдокод для рекурсивной функции, которую вы можете использовать, чтобы увидеть, выводит ли нетерминал 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² N), где n — длина входной строки (для каждой возможной комбинации начального и конечного индексов), а N — количество нетерминалов в грамматике. Эти наблюдения показывают, что этот алгоритм выиграл бы либо от мемоизации, либо от динамического программирования, в зависимости от того, какой подход вы считаете более приятным.

Алгоритм CYK — это то, что вы получаете, когда берете приведенный выше рекурсивный алгоритм и запоминаете результат, или, что то же самое, когда вы преобразуете приведенный выше рекурсивный алгоритм в задачу динамического программирования.

Существует O(n² N) возможных рекурсивных вызовов. Для каждой проверенной продукции это работает O (n). Если для нетерминала в среднем имеется P продуктов, это означает, что общее время выполнения составляет O(n³ NP), то есть O(n³) для фиксированного грамматика.