API синтаксического анализатора

Продолжаю свой предыдущий пост. Время сфокусироваться на деталях внутреннего устройства синтаксического анализатора. В качестве языка реализации я выбрал Go, поскольку хотел малой ценой получить параллельный (в смысле, использующий все доступные ядра CPU) производительный инструмент, без погружения в низкоуровневую пучину C++.

Полученный код предоставляет следующий API:

type Attribute struct {
    Name   string
    Value  string
}

type ParseMatch struct {
    Text            string
    Nonterminal     string
    Rule            string
    Attributes      []Attribute
    Submatches      []ParseMatch
    Hypotheses      []string
    HypothesisCount uint
}

func Parse(text, nonterminal string, hypotheses_limit uint) []ParseMatch

Match ссылается на дочерние объекты того же типа, соотвествующие нетерминалам или лексическим терминалам подошедшего правила. В общем случае, из-за неоднозначности, присущей естественным языкам, тексту соответствует несколько разборов (например, из-за наличия омонимов). Поэтому функция Parse возвращает множество объектов Match. Вышеупомянутая неоднозначность синтаксического разбора должна устраняться на следующем (семантическом) уровне анализа текста.

Итак, функция Parse берёт text — текст для разбора, nonterminal — название нетерминала (например, «sentence»), а также максимальное число выдвигаемых гипотез hypotheses_limit (об этом чуть ниже). Параметр nonterminal может быть пустым. В этом случае тексту будет сопоставляться лексический терминал, найденный в морфологической базе.

В терминах данного анализатора гипотеза — это предположение того, что нарушенное ограничение значения атрибута вызвано случайной причиной. Если анализатор встречает несоответствие значения атрибута ограничению, заданному рассматриваемым в данный момент правилом, а число выдвинутых гипотез не достигло hypotheses_limit, то данное несоответствие игнорируется. В противном случае рассматриваемое правило отбрасывается. Данный механизм удобен для отладки правил, но должен избегаться в реальной работе, поскольку чудовищно замедляет процесс разбора.

Сопоставление нетерминалов

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

Для данного нетерминала анализатор извлекает все соответствующие правила (исходя из грамматики) и пытается найти соответствия каждому из них. Так, для каждого такого правила анализатор проверяет наличие присвоения значений атрибутов ("@{...}", должно быть вначале правила). Далее вызывается рекурсивная функция parseRulePart, которая последовательно производит следующие действия:

• В случае наличия в текущем месте правила терминала сопоставляет его тексту.
• В случае наличия в текущем месте правила нетерминала или лексического терминала вызывает функцию Parse.
• Проверяет выполнение ограничений на значения атрибутов для полученных Match-объектов.
• Для каждого из подходящих Match-объектов функция вызывает саму себя в новом потоке (goroutine) для сопоставления оставшейся части правила.
• Match-объекты, возвращённые созданными потоками, дополняются данными из текущего Match-объекта и возвращаются.

Сопоставление лексических терминалов

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

• Из текста извлекается терминал, ограниченный символом, разделяющим слова.
• В морфологической базе находятся все лексические терминалы, начинающиеся с извлечённого терминала.
• Из полученных лексических терминалов выбираются те, что соответствуют данному тексту.

Морфологическая база

Я использую морфологический словарь русского языка, скачанный с сайта OpenCorpora. Для использования синтаксическим анализатором эти данные должны быть минимизированы и индексированы. Сначала я пробовал для этой цели использовать SQLite, но полученное решение имело неудовлетворительную производительность (даже после включения кэширования). Поэтому пришлось реализовывать специализированную морфологическую базу. Замеры показали примерно 9-кратное ускорение поиска и более чем 300-кратное ускорение начальной индексации.

Формат файла морфологической базы достаточно прямолинеен: заголовок + две большие части. Первая часть состоит из словоформ, разделённых символом '\0'. Второй частью является сортированный массив структур, содержащих 32-битное смещение текста соответствующей словоформы и упакованные в 32-бита значения её атрибутов. Для высокой скорости поиска обе части морфологической базы полностью загружаются в оперативную память.

Полученный код предоставляет следующий API:

func BuildMorph(txt_filename, morph_filename string) error
func InitMorph(morph_filename string) error
func FinalizeMorph()
func FindTerminals(prefix, separator string) []ParseMatch

Функция FindTerminals принимает дополнительный параметр разделителя, поскольку в случае устойчивого словосочетания он является его неотъемлемой частью, в противном же случае разделитель оказывается ненужным и должен быть отброшен.

Кэш разбора

Даже после ускорения поиска словоформ общая производительность разбора оставляла желать лучшего (разбор распространённых предложений длился несколько секунд). Поскольку структура разработанной грамматики предполагает многократные сопоставления текста одним и тем же нетерминалам (наличие множества похожих правил), то напрашивалось применение кэширования. Поэтому, прежде чем начинать разбор, функция Parse проверяет наличие такого (произведенного ранее) разбора в кэше.

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

Использование анализатора

Для использования разработанного анализатора требуется:

• Скачать морфологический словарь.
• Собрать на его основе морфологическую базу (morph.bin, см. main.go).
• Дополнять/изменять правила грамматики в файле rules.yaml.
• Быть любознательным и ловить кайф от исследований.