Часть .1: Языки описания языков

В идеале нам хотелось бы разбирать текст за линейное время и за один проход. Регулярные выражения это позволяют, но уже с CFG это не получится: например, S > A | B; A > a | x A; B > b | x B превращает строку x…xa в дерево из узлов A, а строку x…xb в дерево из узлов B — и пока разборщик не увидит последний символ строки, он не знает, что делать со всеми предыдущими символами. Поэтому на грамматики для языков программирования накладывают дополнительные ограничения — по сути, чтобы для разбора не приходилось "заглядывать вперёд" — позволяющие разбирать текст программы за один проход. Кто ковырялся в компиляторах, тот наверняка знаком с LL- и LR-разбором, и имеет опыт "подгонки" грамматики языка под требования конкретного алгоритма разбора. Но при работе с естественными языками нет возможности "подправить" язык для удобства разбора — приходится работать с тем языком, какой есть.

В 1960-х был разработан алгоритм CYK для разбора произвольного CFG. Считается, что впервые его опубликовали — независимо друг от друга — И. Сакаи из японского НИИ Минобороны в 1961 и Дж. Кок из Нью-Йоркского университета в 1962. В 1966 тот же самый алгоритм публиковали — опять независимо — Д. Янгер из General Electric и Т. Касами из Университета Иллинойса. Янгер в своей публикации упоминает имена Кока и Сакаи, но не ссылается ни на какие конкретные их работы: по всей видимости, работы Кока и Сакаи Янгеру — как и мне сейчас — не были доступны. Чтобы никому из изобретателей алгоритма не было обидно, его называют в честь сразу троих, хотя они, скорее всего, даже не были между собой знакомы.

Идея CYK заключается в разборе "снизу вверх" — от терминалов к S — и использовании динамического программирования для избежания повторных вычислений: вначале составим все узлы, выводимые непосредственно из терминалов, и поместим их на "доску". На каждом шаге алгоритма возьмём с доски один узел, составим все возможные узлы с его участием, и добавим на доску ещё и их. Если на доске появился S для всего текста целиком, значит разбор удался; если все узлы с доски обработаны, но S там так и не появился — значит, разбор не удался. Википедия в качестве примера разбирает предложение "She eats the fish with a fork." по следующей грамматике:

S > NP VP
VP > VP PP | V NP | V
PP > P NP
NP > Det N | she
V > eats
P > with
N > fish | fork
Det > a | the

Какова сложность CYK для CFG? На доске может быть как максимум  узлов — для каждого нетерминального символа и для каждой подстроки входного текста; поэтому доску удобно хранить в виде трёхмерного массива, индексы которого — нетерминал, начало подстроки и конец подстроки. На каждом шаге обрабатывается один узел с доски — значит, для разбора потребуются  шагов. На каждом шаге проверяются все правила грамматики, и для каждого правила, где обрабатываемый узел подходит под правую часть, будут проверены все узлы с доски, могущие участвовать в правой части вместе с обрабатываемым узлом. Осталось определить сложность такого шага.

Исходный алгоритм CYK работал с CFG в нормальной форме Хомского (CNF) — в правой части каждого правила вывода допускались либо один терминал, либо два нетерминала. Для правила A > BC "все узлы с доски, могущие участвовать в правой части вместе с обрабатываемым узлом" — это как максимум  узлов с индексами (C, end_B, ?) и/или как максимум  узлов с индексами (B, ?, start_C). (Если B=C, то подходят оба набора вариантов.) Получается, что сложность одного шага CYK для CNF — это , а сложность всего разбора — это .

А если CFG не в CNF? Для правила A > BCD придётся обработать:

• как максимум  узлов с индексами (C, end_B, ?), и для каждого из них — как максимум  узлов с индексами (D, end_C, ?);

• как максимум  пар узлов с индексами (B, ?, start_C), и (D, end_C, ?);

• как максимум  узлов с индексами (C, ?, start_D), и для каждого из них — как максимум  узлов с индексами (B, ?, start_C).

Значит, если в правой части правила вывода допустить до трёх нетерминалов, то сложность одного шага CYK будет , а сложность всего разбора будет . Обобщая на произвольную CFG — видим, что сложность разбора при помощи CYK будет , где  — максимальная длина правой части правил вывода ("ранг грамматики").

Теперь обобщим CYK для MCFG, сохраняя его центральную идею: на каждом шаге алгоритма берём с доски один узел, составляем все возможные узлы с его участием, и добавляем их на доску. Разбор "Я тебя детям просил помочь!" по грамматике, приведённой в ч.1 и для удобства повторённой здесь, получится таким:

VP(X,Y) < NP(X),V(Y)
CP(X,Y) < VP(X,Y)
VP(X,YZW) < NP(X),V(Z),CP(Y,W)
S(XYZ) < NP(X),VP(Y,Z)
NP(я) < ?
NP(тебя) < ?
NP(детям) < ?
V(просил) < ?
V(помочь) < ?

Как реализовать такой разбор, и какой получится его сложность? Трёхмерной доской уже не обойтись: узлы двухместных предикатов, таких как VP и CP, могут существовать для любой пары подстрок входного текста, так что понадобится индексация пятёрками (нетерминал, начало₁, конец₁, начало₂, конец₂). Одно уже это повышает число шагов разбора до . Теперь надо понять, какие узлы такой пятимерной доски могут участвовать вместе с обрабатываемым узлом в применении правила вывода — например, правила P(XY,ZW) < P(X,Z),P(Y,W) из приведённой в ч.1 грамматики языка дважды повторённых строк. Подходящие узлы будут находиться по индексам (P, end_X, ?, end_Z, ?) и (P, ?, start_Y, ?, start_W), так что их будет штук. В предположении, что "размерность грамматики" равна 2 (т.е. предикаты как максимум двухместные) и её ранг тоже равен 2 (т.е. правила вывода допускают конкатенацию как максимум двух переменных) — получаем, что сложность CYK-разбора будет .

А если ранг выше, как в вышеприведённой грамматике, где правило VP(X,YZW) < NP(X),V(Z),CP(Y,W) включает конкатенацию трёх переменных? В этом случае подходящие для V узлы будут находиться по индексам (CP, ?, start_Z, end_Z, ?) и (NP, ?, ?, ?, ?), так что их будет уже штук. Аналогично, подходящие для NP узлы будут находиться по индексам (CP, ?, ?, ?, ?) и (V, end_Y, start_W, ?, ?), и их тоже будет штук. Получаются шагов сложностью каждый. Огромное число бесполезных шагов заметно и в приведённом примере разбора: в предложении, где три NP и два V, из каждой их попарной комбинации выводится по узлу VP и CP.

В целом можно видеть, что алгоритм разбора остаётся полиномиальным, но показатель степени быстро растёт по мере усложнения грамматики: обобщая приведённые рассуждения, получим сложность , где  — размерность грамматики. Это значит, что разбор можно существенно упростить, заменяя конкатенацию более чем двух переменных на новый нетерминал, например правило VP(X,YZW) < NP(X),V(Z),CP(Y,W) на пару правил CP'(Y,ZW) < V(Z),CP(Y,W); VP(X,YZ) < NP(X),CP'(Y,Z). Полученное таким образом дерево разбора дальше от теоретического описания структуры предложения, но тем не менее, такая "нормализация" грамматик широко применяется.

Как отмечалось в ч.1, тексты на естественных языках часто допускают несколько возможных разборов, и среди этих возможных разборов требуется выбрать наиболее вероятный. Самое лобовое решение — это присвоить каждому правилу вывода вероятность (например, VP(X,Y) < 75% NP(X),V(Y); VP(X,YZW) < 25% NP(X),V(Z),CP(Y,W) — такую вероятностную грамматику называют PMCFG), и тогда вероятность разбора — это произведение вероятностей всех использованных в нём правил вывода. Намного удобнее, чем с микроскопическими вероятностями, работать с их логарифмами: тогда перемножение вероятностей заменяется сложением их логарифмов.

В заключение поделюсь моей реализацией CYK для PMCFG на Python, практически применимой (требовалось разбирать предложения до 10 слов в пределах 5 секунд) для , но способной работать и вне этих ограничений. Вместо -мерного массива для доски я использую двухуровневый dict, в котором ключи первого уровня — нетерминалы, второго — объекты Chunk, а значения — логарифмы вероятностей. Для каждой комбинации из нетерминала и набора подстрок может существовать только один экземпляр Chunk, так что для сравнения объектов достаточно сравнить их id — это многократно ускоряет поиск в dict по сравнению с использованием в качестве ключа обычной записи (data class).

class Chunk:
    instances = {}
    def __new__(cls, symbol, inputs):
        key = symbol, tuple(inputs)
        i = cls.instances.get(key)
        if i:
           return i
        i = super(Chunk, cls).__new__(cls)
        i.symbol = symbol
        i.inputs = inputs
        cls.instances[key] = i
        return i


def parse(grammar, string):
    chart = {n: {} for n in grammar.non_terminals}
    agenda = {Chunk(rule.left.symbol, [(i, i + 1)]): rule.prob
              for i in range(len(string)) for rule in grammar.rules
              if rule.terminating and rule.left.inputs[0] == string[i]}
    goal = Chunk(grammar.start, [(0, len(string))])
    while agenda and goal not in chart[grammar.start]:
        (best, prob) = max(agenda.items(), key=lambda x: x[1])
        chart[best.symbol][best] = prob
        del agenda[best]
        for rule in grammar.rules:
            if not rule.terminating and any(best.symbol == prod.symbol for prod in rule.right):
                right = list(rule.right)
                for perm in itertools.product(*(chart[prod.symbol].keys() for prod in right)):
                    if best in perm:
                        sat = satisfies(perm, rule.left, right, chart)
                        if sat is not None:
                            chunk = sat[0]
                            new_prob = sat[1] + rule.prob
                            if (chunk not in chart[chunk.symbol]) and                                ((chunk not in agenda) or (agenda[chunk] != new_prob)):
                                agenda[chunk] = new_prob
    return chart[grammar.start].get(goal)


def satisfies(perm, left, right, chart):
    mapping = {}
    prob = 0
    for chunk, pred in zip(perm, right):
        for c_i, p_i in zip(chunk.inputs, pred.inputs):
            mapping[p_i] = c_i
        prob += chart[chunk.symbol][chunk]
    inputs = []
    for r in left.inputs:
        if len(r) == 1:
            inputs.append(mapping[r])
        else:
            mapped = [mapping[c] for c in r]
            for k in range(len(mapped) - 1):
                if mapped[k][1] != mapped[k + 1][0]:
                    return None
            inputs.append((mapped[0][0], mapped[-1][1]))
    if len(inputs) > 1:
        for i in range(len(inputs) - 1):
            if inputs[i][1] > inputs[i + 1][0]:
                return None
    return Chunk(left.symbol, inputs), prob

Самые внимательные заметят, что эта реализация допускает терминалы только в правилах вида N(t) < ?, по аналогии с CNF. Это отчасти дань традиции, предписывающей категоризовать каждое слово перед составлением синтаксических конструкций с его участием.

Облачные серверы от Маклауд быстрые и безопасные.

Зарегистрируйтесь по ссылке выше и получите 10% скидку на первый месяц аренды сервера любой конфигурации!