Разбор любой грамматики: нормальная форма Хомского и алгоритм CYK

Если ты приведёшь грамматику к нормальной форме Хомского, заполнишь таблицу CYK для короткой строки и объяснишь, откуда в оценке куб, - листай до «Теперь сам».

Как думаешь, можно ли разобрать строку по любой грамматике

Грамматика дана как есть: с левой рекурсией, с неоднозначностью, с правилами, начинающимися с одного токена. Переписывать её руками под удобный разбор нельзя или некому. Нужно ответить, выводится ли строка.

Попробуй угадать до чтения: существует ли алгоритм, который отвечает для любой КС-грамматики и любой строки, и сколько он стоит? Перебор всех деревьев отпадает: у выражения из восьми чисел их 429, и число растёт экспоненциально. Алгоритм существует и стоит n³. Деревьев экспоненциально много, но разных вопросов «выводится ли этот кусок строки из этого нетерминала» - всего n² на нетерминал, и каждый достаточно решить один раз.

На что это похоже

Сборка длинного моста из пролётов. Прежде чем спрашивать, можно ли перекрыть всю реку, выясняют про каждый короткий участок, какими типами пролётов он перекрывается. Потом про участки на пролёт длиннее, и так далее: участок перекрывается, если его можно хоть в каком-то месте разрезать на два уже разобранных и в каталоге есть конструкция, соединяющая пролёты этих двух типов.

Никто не перебирает способы построить мост целиком. Про каждый участок хранится только список типов, которыми он перекрывается, а не то, как именно.

Механизм: нормальная форма и таблица по отрезкам

Нормальная форма Хомского разрешает правила двух видов:

A → B C        справа ровно два нетерминала
A → a          справа ровно один терминал

Отдельно разрешено правило «начальный нетерминал → ε», если пустая строка входит в язык; начальный нетерминал при этом не должен встречаться в правых частях. Если встречается, как в S → aSb | ε, сначала заводят новый начальный нетерминал с правилом S₀ → S. Любую КС-грамматику можно привести к такой форме, не изменив язык; как именно - во втором разборе.

Форма нужна ради одного свойства. Если кусок строки длиннее одного символа выводится из A, то первым шагом применено какое-то правило A → B C, и кусок делится на две непустые части: левая выводится из B, правая из C. Других вариантов нет. Части непустые, потому что пустую строку не выводит ни B, ни C: правило с ε есть только у начального нетерминала, а он справа не встречается.

Отсюда таблица. Пусть T[i][d] - множество нетерминалов, из которых выводится кусок строки, начинающийся в позиции i и имеющий длину d. Позиции считаются с нуля; таблица T - не нетерминал T из грамматик выражений.

d = 1:   T[i][1] = все A, у которых есть правило
         A → символ строки в позиции i

d > 1:   для каждого места разреза  s = 1 … d − 1
         для каждого правила  A → B C
             если  B  лежит в  T[i][s]   и   C  лежит в  T[i + s][d − s]
             то добавить  A  в  T[i][d]

Таблица заполняется по возрастанию d: к моменту, когда нужен кусок длины d, все более короткие уже посчитаны. Строка длины n принадлежит языку, если начальный нетерминал лежит в T[0][n].

Это алгоритм Кока-Янгера-Касами, по первым буквам фамилий - CYK. Кусков порядка n², мест разреза в каждом до n, правил g: всего порядка g · n³ проверок. Это динамическое программирование, в котором подзадача - отрезок строки: ответ для отрезка собирается из уже посчитанных ответов для двух его частей по всем местам разреза.

Если в клетке хранить не только нетерминал, но и то, каким разрезом и каким правилом он получен, по таблице восстанавливается дерево разбора. Если хранить число способов - получается число деревьев, и неоднозначность строки видна по счётчику начального нетерминала в T[0][n]: больше единицы - разборов несколько. Счёт идёт по грамматике в нормальной форме - той, с которой работает алгоритм, - а приведение к ней может слить два дерева исходной в одно: подстановка вместо правил «нетерминал → нетерминал» превращает два пути E → T → F → n и E → F → n в одно правило E → n.

Правило

Алгоритм CYK решает, выводится ли строка длины n по грамматике в нормальной форме Хомского с g правилами, за O(g · n³) действий и O(n²) клеток памяти: клетка T[i][d] хранит нетерминалы, выводящие кусок с позиции i длины d, и вычисляется по всем разрезам и всем правилам A → B C. Алгоритм работает для любой КС-грамматики, приведённой к этой форме, - в том числе неоднозначной и леворекурсивной.

Разбор: скобки и откуда берётся куб

В грамматике скобок из первого урока главы, S → (S)S | ε, есть пустое правило. Чтобы не убирать его, возьмём грамматику того же языка без пустой строки, S → S S | ( S ) | ( ). В нормальной форме:

S → S S | L A | L R         A → S R         L → (         R → )

Здесь L и R - скобки, а A - «правильная запись и закрывающая скобка», вспомогательный нетерминал для длинного правила ( S ). В программе двойные правила - список троек «левая часть, первый, второй», правила для терминалов - словарь от символа к списку левых частей: {"(": ["L"]} для правила L → (. Счётчик proverok считает, сколько раз проверено правило для разреза.

def cyk(dvojnye, bukvy, stroka):
    n = len(stroka)
    tabl = []
    for i in range(n):
        ryad = []
        for d in range(n + 1):
            ryad.append(set())
        tabl.append(ryad)
    for i in range(n):
        if stroka[i] in bukvy:
            for golova in bukvy[stroka[i]]:
                tabl[i][1].add(golova)
    proverok = 0
    for d in range(2, n + 1):
        for i in range(n - d + 1):
            for sleva in range(1, d):
                for pravilo in dvojnye:
                    proverok = proverok + 1
                    if (pravilo[1] in tabl[i][sleva]
                        and pravilo[2] in tabl[i + sleva][d - sleva]):
                        tabl[i][d].add(pravilo[0])
    return [n > 0 and "S" in tabl[0][n], proverok]

dvojnye = [["S", "S", "S"], ["S", "L", "A"],
           ["S", "L", "R"], ["A", "S", "R"]]
bukvy = {"(": ["L"], ")": ["R"]}
for stroka in ["()", "(())", "(()())", "())(", "((", "()()"]:
    print(stroka, cyk(dvojnye, bukvy, stroka))
for n in [4, 8, 16, 32]:
    print(n, cyk(dvojnye, bukvy, "()" * (n // 2)))

() [True, 4]
(()) [True, 40]
(()()) [True, 140]
())( [False, 40]
(( [False, 4]
()() [True, 40]
4 [True, 40]
8 [True, 336]
16 [True, 2720]
32 [True, 21824]

Ответы верные, а число проверок зависит только от длины: 40 и для (()), и для ())(. Алгоритм не смотрит, похожа ли строка на правильную, - он заполняет всю таблицу.

При удвоении длины число проверок растёт в 8,4, в 8,1 и в 8,0 раза: это куб. Точная формула для этой программы - число правил, умноженное на (n³ − n) / 6: кусков длины d в строке n − d + 1, разрезов у каждого d − 1, и сумма этих произведений по всем d даёт (n³ − n) / 6. При n = 32 это 4 · 5456 = 21 824. Стек из прошлых уроков проверил бы ту же строку за 32 шага. Разница в семьсот раз на строке из тридцати двух символов - цена того, что CYK не пользуется никакими особенностями грамматики.

Разбор: приведение к нормальной форме и неудобная грамматика

Возьмём грамматику выражений с левой рекурсией, которую рекурсивный спуск не принимает как есть. Терминал «число» записан одной буквой n, потому что программа читает строку посимвольно; с длиной строки эта буква не связана.

E → E + T | T          T → T * F | F          F → ( E ) | n

Приведение идёт в три шага.

1. терминалы внутри длинных правил получают свои нетерминалы:
       P → +      M → *      L → (      R → )
2. правила длиннее двух символов режутся вспомогательными нетерминалами:
       E → E X,  X → P T      T → T Y,  Y → M F      F → L Z,  Z → E R
3. правила «нетерминал → один нетерминал» убираются подстановкой:
       F → L Z | n
       T → T Y | L Z | n          вместо  T → F  подставлены правила F
       E → E X | T Y | L Z | n    вместо  E → T  подставлены правила T

Было шесть правил, стало шестнадцать: девять двойных и семь для терминалов. Если в грамматике есть правила с пустой правой частью, добавляется ещё один шаг - их удаление: в каждое правило, где справа стоит нетерминал, способный дать пустую строку, добавляют вариант без него, а сами пустые правила вычёркивают - кроме правила «начальный → ε», если пустая строка входит в язык. Его делают после разрезания длинных правил и до третьего шага: удаление пустых правил само порождает правила вида «нетерминал → нетерминал». Порядок важен и для размера: в другом порядке грамматика может вырасти экспоненциально, в этом - не больше чем квадратично.

Та же функция, что и выше, только возвращает таблицу целиком.

def cyk(dvojnye, bukvy, stroka):
    n = len(stroka)
    tabl = []
    for i in range(n):
        ryad = []
        for d in range(n + 1):
            ryad.append(set())
        tabl.append(ryad)
    for i in range(n):
        if stroka[i] in bukvy:
            for golova in bukvy[stroka[i]]:
                tabl[i][1].add(golova)
    for d in range(2, n + 1):
        for i in range(n - d + 1):
            for sleva in range(1, d):
                for pravilo in dvojnye:
                    if (pravilo[1] in tabl[i][sleva]
                        and pravilo[2] in tabl[i + sleva][d - sleva]):
                        tabl[i][d].add(pravilo[0])
    return tabl

dvojnye = [["E", "E", "X"], ["E", "T", "Y"], ["E", "L", "Z"],
           ["T", "T", "Y"], ["T", "L", "Z"]]
dvojnye = dvojnye + [["F", "L", "Z"], ["X", "P", "T"],
                     ["Y", "M", "F"], ["Z", "E", "R"]]
bukvy = {"n": ["E", "T", "F"], "+": ["P"], "*": ["M"],
         "(": ["L"], ")": ["R"]}
for stroka in ["n+n*n", "(n+n)*n", "n+*n", "n*(n", "((n))"]:
    tabl = cyk(dvojnye, bukvy, stroka)
    print(stroka, "E" in tabl[0][len(stroka)])
tabl = cyk(dvojnye, bukvy, "n+n*n")
for d in [5, 4, 3, 2, 1]:
    ryad = []
    for i in range(5 - d + 1):
        ryad.append("".join(sorted(tabl[i][d])))
    print(d, ryad)

n+n*n True
(n+n)*n True
n+*n False
n*(n False
((n)) True
5 ['E']
4 ['', 'X']
3 ['E', '', 'ET']
2 ['', 'X', '', 'Y']
1 ['EFT', 'P', 'EFT', 'M', 'EFT']

Левая рекурсия алгоритму не мешает: он не идёт по правилам, а заполняет клетки. Последние пять строк - таблица для n+n*n: слева длина куска, дальше клетки по позициям начала. В нижнем ряду каждое n выводится из E, T и F. В ряду длины 3 кусок n*n (позиция 2) выводится из T и E, а кусок n+n (позиция 0) - только из E. Кусок +n*n длины 4 выводится из X, «плюс и слагаемое». Вся строка получена одним способом: E → E X с разрезом после первого n. Разрез после n+n не подошёл: кусок *n - это Y, а с Y справа есть только правила вида T Y; кусок же n+n из T не выводится. Так таблица и показывает, что умножение выполняется раньше.

Что ломается без этого

Перебор деревьев вместо таблицы. Разбор с возвратами по неоднозначной грамматике экспоненциален по той же причине, что и поиск по регулярному выражению возвратами: одни и те же куски разбираются заново в разном окружении.

CYK применён к грамматике не в нормальной форме. С правилом из трёх символов справа одного разреза мало, и алгоритм молча теряет выводы.

Забыт случай пустой строки. Таблица начинается с кусков длины 1; пустую строку проверяют отдельно - есть ли правило «начальный → ε».

Общий алгоритм взят там, где хватило бы частного. Исходный текст на сто тысяч токенов и куб - это 10¹⁵ действий. Языки программирования проектируют так, чтобы их разбирал линейный алгоритм.

Зачем это в работе

Грамматики, которые нельзя сделать удобными. Естественный язык неоднозначен по существу, и разбор предложений строился на CYK и его родственниках: в клетке для каждого нетерминала хранят не отметку «выводится», а вероятность лучшего разбора. Тот же приём находит наиболее вероятную вторичную структуру молекулы РНК.

Быстрые общие алгоритмы. Алгоритм Эрли работает с любой грамматикой без приведения к нормальной форме, в худшем случае за те же n³, на однозначных грамматиках - за n², а на многих грамматиках языков программирования - за линейное время. Его используют библиотеки разбора, которым дают произвольную грамматику.

Граница возможного. Вэлиант в 1975 году показал, что разбор сводится к умножению матриц и поэтому возможен быстрее куба, а Ли в 2002 году - что и наоборот, быстрый разбор дал бы быстрое умножение булевых матриц. Кубический барьер у разбора тот же, что у матриц, и существенно ниже его на практике никто не опустился.

Теперь сам

1. Приведи к нормальной форме Хомского грамматику S → a S b | a b.
2. Сколько клеток в таблице CYK для строки длины 10, если считать только куски, которые существуют?
3. Какие нетерминалы окажутся в клетке для куска () в грамматике скобок из первого разбора?
4. Строку удлинили втрое. Во сколько раз вырастет работа CYK?
5. Как изменить алгоритм, чтобы он считал число деревьев разбора?