Синтаксический анализатор грамматического словаря

Задача, решаемая синтаксическим анализатором

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

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

Анализируемые предложения могут иметь разную сложность, включать неизвестные слова или отступления от нормативного синтаксиса. Чтобы эффективно справляться с разными задачами, синтаксический анализатор применяет несколько разных алгоритмов, включая структурный нисходящий анализ и восходящий анализ, а также применяет семантический анализ для уточнения результатов в случае неоднозначностей.

Структурный нисходящий анализ - самый точный. Восходящий анализ работает очень быстро и способен разобрать даже очень длинные предложения, игнорируя непонятные фрагменты. Достоинства и недостатки каждого вида анализа мы рассмотрим ниже.

Восходящий и нисходящий вероятностный парсинг предложения

В парсере реализованы два алгоритма недетерминированного синтаксического разбора предложения - нисходящий (top-down) и восходящий (bottom-up).

Как следует из названий, они по-разному организуют процесс распознавания синтаксических конструкций.

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

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

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

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

Правила, управляющие синтаксическим разбором

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

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

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

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

Достоинства и недостатки структурного нисходящего парсера

Далее приводятся характерные особенности структурного нисходящего парсера (далее СНП), работающего в режиме “анализ через синтез”.

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

(+) СНП найдет все возможные варианты разбора предложения, если грамматика содержит неоднозначности.

(+) СНП способен делать ослабляющие допущения и оценивать выполненный анализ с учетом таких допущений.

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

(+/-) СНП не имеет внутреннего состояния и выполняет разбор за 1 заход. Нет естественного способа остановить выполнения разбора в промежуточной стадии и получить частичные результаты. Эта особенность имеет также важное положительное следствие. Отсутствие состояния позволяет распараллеливать выполнение анализа.

(-) СНП естественным образом реализует поиск в глубину. Это может приводить к тому, что из-за отсутствия хороших эвристик очень много времени будет уделено проверке заведомо проигрышным вариантам анализа, а выигрышный путь в пространстве состояний так и не будет найден до исчерпания лимита времени.

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

(-) Если структура предложения не выводится правилами грамматики в точном виде, то СНП вообще ничего не выведет, если не принимать специальные меры. Под такими специальными мерами подразумевается неполный анализ.

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

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

Достоинства и недостатки итерационного анализа

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

Далее перечисляются только собственные особенности данного алгоритма.

1. Недетерминированность процесса. Входная цепочка токенов может породить несколько альтернативных новых цепочек после применения правила переписывания. Выбор оптимального результата выполняется с помощью механизма задания баллов для правил переписывания, либо с использованием общих с алгоритмов анализ-через-синтез приемов - ассоциации слов, tree scorer.

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

3. Простота отладки. Процесс переписывания можно прервать в момент применения очередного правила и увидеть весь текущий набор результатов.

4. Порядок задания правил имеет значение.

5. Работа с длинными предложениями. Можно задать такие правила, что автомат будет работать в минимальным контекстом - например, ограничить его правилами для пар слов. К примеру, связывать частицу НЕ с наречиями, прилагательными, деепричастиями и глаголами и т.д. Поэтому автомат может выполнять постепенное построение синтаксического дерева для очень длинных предложений, не пытаясь сразу охватить слишком большие фрагменты текста.

6. Правила переписывания используют весь набор возможностей для задания опорных точек контекста. Это позволяет задавать правила, которые сопоставляются с контекстом заранее неизвестной длины. Кроме того, доступны такие средства, как 1) теоретико-множественные операторы для проверки вхождения токена в именованное множество, 2) проверка с помощью регулярных выражений, 3) использование пользовательских функций, написанных на встроенном языке, 4) проверка согласования фрагментов сопоставляемого контекста.

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

8. Итерационный анализ можно начинать не просто с исходной цепочки токенов, а попытаться "прикинуть" общую структуру предложения с помощью набора специальных правил. Например, можно найти в предложении местоимение я и согласующийся с ним глагол, предположить из связь как подлежащего и сказуемого и далее уже запускать итерации, опираясь на эти ключевые токены.

Распознающая или порождающая грамматика

Архитектурная особенность структурного парсера заключается в таком нюансе.

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

С другой стороны, алгоритм распознавания грамматики спроектирован так, что он порождает по набору заданных правил возможные фразы и сопоставляет их с имеющейся фразой, отвергая недопустимые выводы и уточняя подтверждающиеся. Порождение начинается (если отбросить незначительные в данном случае детали) с некоторого начального нетерминального символа, обозначающего целое предложение, и постепенно расщепляется на множество вариантов, каждый из которых проверяется отдельно. Например, разный порядок следования S-V-O и O-V-S для русского языка приводит к тому, что некоторые предложения подходят под разные шаблоны: мать любит дочь.

В итоге, синтаксический анализ предложения выполняется через синтез синтаксической структуры. Если синтез неоднозначен, то на выходе парсера появляются альтернативные результаты. К примеру, без подключения дополнительного семантического анализа невозможно выбрать порядок связывания для предложения: “руки с мылом мой”. Возможные два варианта в скобочной записи выглядят так: мой(руки(с(мылом))) и мой(руки,с(мылом)). Оба они корректны с грамматической точки зрения.

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

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

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

Лексикализация нетерминалов в правилах нисходящего разбора

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

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

Весь этот набор доступен в вышестоящих правилах наряду с именем самого нетерминала.

На уровне синтаксиса правил лексикализация выполняется использованием двух вещей.

Во-первых, каждая реализация нетерминала может экспортировать определенный, заранее объявленный набор лексем и морфологических признаков. Именно этот набор расширяет нетерминальный символ.

Во-вторых, в месте “вызова” нетерминального символа можно указать секцию уточнения, в которой задать проверки на вхождение или невхождение главного слова в именованные множества, заданные значения морфологических атрибутов или согласование морфологических атрибутов.

Оба этих механизма подробно описаны далее, когда объясняется синтаксис правил парсера.

Общий принцип работы нисходящего структурного парсера

Слово нисходящий в определении структурного парсера подчеркивает фундаментальную особенность данного алгоритма. Он выполняет разбор предложения с помощью выдвижения альтернативных гипотез и их доказательства или опровержения. Разбор начинается с выдвижения гипотез самого общего вида по поводу структуры предложения, например - вопрос, утверждение, вежливая побудительная конструкция. Для каждой из выдвинутых гипотез определяется набор гипотез, чье доказательство необходимо для их подтверждения или опровержения. Процесс доказательства гипотез продолжается до тех пор, пока не будет найдена необходимая комбинация токенов. Алгоритм нисходящего вывода позволяет применять альтернативные гипотезы (реализация недетерминированного автомата). Это крайне важно для текстов на естественном языке, в которых грамматическая трактовка токенов зависит от контекста заранее неизвестной ширины. В ходе доказательства гипотез может выполняться рекурсивное применение. Например, при разборе группы существительного с правым причастным оборотом может возникнуть необходимость разобрать входящие в состав оборота другие, более мелкие группы существительного, в которых также может быть причастный оборот, и так далее. Такие конструкции характерны для письменной речи, насыщенной сложными оборотами.

Нисходящий анализатор выполняет одновременно несколько важнейших операций над исходным текстом. Он распознает грамматические признаки слов (part of speech tagging в широком понимании), разрешает неоднозначности, строит синтаксическое дерево, возможно с альтернативными вариантами, взвешиваемыми на основе разных весовых алгоритмов.

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

Посмотрим, как парсер разбирает предложение

Мы спали.

Анализ всегда начинается с начального нетерминального символа Предложение.

Допустим, у нас есть два правила, которые выводят из этого начального символа две новых цепочки:

Предложение := Подлежащее Сказуемое

Предложение := Сказуемое Подлежащее

Оба варианта допускаются в русском синтаксисе.

Применение двух первых правил:

Было:

Предложение

Стало:

Вариант 1. Подлежащее Сказуемое

Вариант 2. Сказуемое Подлежащее

Символы Сказуемое и Подлежащее - это тоже нетерминалы, то есть они не соответствуют никаким словам, а обозначают некие абстрактные синтаксические сущности, которые еще предстоит раскрыть.

Добавляем два новых правила:

Подлежащее := мы

Сказуемое := спали

В этих правилах появляются нормальные слова, иначе говоря терминальные символы нашей грамматики. После их применения к двум текущим вариантам имеем:

Вариант 1. мы Сказуемое

Вариант 2. спали Подлежащее

Мы пока заменили только первый элемент в каждом варианте. Так как результатом этих замен являются терминальные слова, которые дальше уже не могут заменяться другими символами, то парсер приступает к первой проверке гипотез. Вариант №1 успешно проходит проверку, так как в предложении в текущей позиции стоит как раз нужное слово. Вариант №2 проваливает проверку, и поэтому парсер далее не пытается с ним работать. Это очень важный момент, так как мы еще не делали замену вторых частей в обоих вариантах и не пытались взять из предложения следующие слов. Отбросив второй вариант как явно недопустимый, мы экономим вычислительные ресурсы.

Парсер продолжает работат с первым вариантом. Он применяет имеющееся правило к нетерминалу Сказуемое и получает:

Вариант 1: мы спали.

После замены опять выполняется проверка, которая успешно подтверждает гипотезу для первого варианта. Гипотеза эта, как нетрудно догадаться звучит в нашем примере так: предложение имеет структуру Подлежащее+Сказуемое.

Так как нетерминалов более не осталось и текущие терминальные символы сопоставлены со словами в исходном предложении, то парсер прекращает анализ, сообщая о найденной структуре.

Более сложные примеры работы парсера в целом идут именно таким путем - поиск замен для нетерминальных правил, сопоставление полученных терминалов со словами в предложении, отсечение некорректных гипотез.

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

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

Ветер, качающий деревья

Элементами причастного оборота могут быть прямые дополнения - существительные. И у этих существительных также могут быть причастные обороты в роли их атрибутов:

Ветер, качающий деревья, посаженные вдоль аллеи.

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

Алгоритм восходящего синтаксического разбора

Следующая иллюстрация дает наглядное представление о том, как работает восходящий парсер.

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

Затем алгоритм начинает сворачивать пары нетерминалов в новые нетерминалы, постепенно переходя на более высокие уровки абстракции. Работа заканчивается, когда подлежащее и сказуемое образуют особый нетерминал S, называемый еще "начальным символом".

Ограничения на грамматику

В отличие от нисходящего парсера, этот алгоритм сильно ограничивает описание грамматики. Благодаря этим ограничениям алгоритм получается очень эффективным в плане разбора длинных предложений.

Во-первых, его правила работают только с нетерминалами. Из этого следует, что правила могут анализировать грамматические категории только через создании множества нетерминальных символов на стадии начального разбора предложения. Если мы ходим в правилах учитывать модальность (-->) глагола, то нам придется создать специальный нетерминал, что-то типа ГЛ_МОД.

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


Сущ_Жен_Им_Ед
Сущ_Муж_Им_Ед
...
Сущ_Им_Мн
...

Таким образом, первая особенность восходящего алгоритма разбора - создание большого количества нетерминальных символов.

Во-вторых, правила восходящего разбора ограничены в размерах правой части. Он могут быть либо заменой типа

A :- B

Либо раскрывать левый нетерминал в 2 других:

A :- B C

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

ПричОбор2 :- ПричОборот Запятая

ГруппаСущ :- ГруппаСущ ПричОбор2

Запуск алгоритма, начальное распознавание нетерминалов

Как уже было сказано выше, восходящий алгоритм работает только с нетерминалами.

Нетерминал, или нетерминальный символ, можно рассматривать просто как некоторое условное обозначение для категории слов. К примеру, все существительные женского рода в именительном падеже и единственном числе можно обозначать как Сущ_Ж_Им_Ед.

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

Допустим, у нас на входе есть предложение:

кошка прыгнула на стол

Мы должны преобразовать его в такую цепочку (грамматика сильно упрощена, чтобы сократить выкладки):

Сущ Гл Предл Сущ

Таким преобразованием занимаются особые правила, которые записываются вот так:

word_nonterm Сущ { СУЩЕСТВИТЕЛЬНОЕ:*{} }

word_nonterm Гл{ ГЛАГОЛ:*{} }

word_nonterm Гл{ ПРЕДЛ:*{} }

Ключевое слово word_nonterm начинает правило, затем идет название нетерминала, и затем в фигурных скобочках стоит морфологическое требование к слову.

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

Для удобства работы парсер позволяет с помощью правила начального распознавания выявлять не только одиночные слова как нетерминалы, но и охватывать целые цепочки слов. Например, мы можем (это не совсем правильно из-за особенностей русского синтаксиса, но пока для простоты пренебрежем этим) распознавать сочетание частицы НЕ и последующего глагола БЫТЬ как один нетерминал ГлБыть.

Для этого в качестве начальных распознавателей надо использовать правила нисходящего анализа, которые эффективно распознают цепочки слов.

Благодаря этой возможности начальное распознавание выступает в роли chunker'а, то есть разбивает исходный набор слов на более крупные кусочки, с которыми можно работать быстрее.

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

Правила грамматики, построение матрицы связывания

Грамматика для восходящего разбора описывается с помощью очень простых правил вида

A := B C

X := Y

Другими словами, вместо двух или одного нетерминалов подставляется один новый. Вообще говоря, в правилах для двух нетерминалов слева и справа может упоминаться один и тот же нетерминальный символ:

ГруппаПрил := Прил ГруппаПрил

С помощью таких “рекурсивных” правил можно связывать цепочки синтаксически однородных элементов, не вводя новых нетерминалов.

Вернемся к нашему простому примеру. Предложение

Кошка прыгнула на стол

на первом этапе было заменено на цепочку:

Сущ Гл Предл Сущ

Вводим грамматику с помощью правил

ПредлСущ := Предл Сущ

ГруппаГл := Гл ПредлСущ

S := Сущ ГруппаГл

Первое правило связывает последовательно идущие предлог и существительное.

Второе правило создает группу глагола как глагол и идущий следом паттерн из предлога и существительного.

Наконец, третье правило распознаёт существительное в роли подлежащего и группу глагола в роли сказуемого как завершенное предложение, и заменяет их на начальный символ S.

Порядок следования правил в исходных текстах не играет никакой роли.

Восходящий парсер реализует своеобразный brute force - он фактически перебирает все возможные сочетания из нетерминалов, полученных при начальном распознавании и найденных правилами грамматики. Именно для того, чтобы этот перебор выполнялся за конечное время, вводятся ограничения на размер правой части в правилах. Время, затрачиваемое на перебор вариантов и применение правил, зависит от числа начальных нетерминалов в кубе, то есть для него справедлива оценка O(n^3).

Scoring для правил

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

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

Во-вторых, в любом правиле можно вызвать расчет оценки с помощью просмотра таблицы N-грамм для слов, которые кроются за нетерминальными символами.

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

… глава будет расширена …

Правила связывания по умолчанию

… глава будет расширена …

Метод динамического программирования

Можно заметить, что восходящий парсер фактически перебирает всевозможные сочетания пар нетерминалов, создавая в случае успеха новые нетерминалы. Каким образом алгоритму удается обеспечивать скорость разбора?

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

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

Алгоритм построения синтаксического дерева

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

В случае, если вариантов достижения начального нетерминала S несколько, то алгоритм может построить все варианты синтаксических деревьев.

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

Так как разработчик грамматики может влиять на алгоритм построения и перебора деревьев только косвенно, то мы не будем углубляться в особенности теории графов. Достаточно помнить, что правильный выбор оценок для правил и использование вероятностной модели на основе базы N-грамм улучшает вероятность получать лучшие варианты разбора.

Исходный текст правил восходящего разбора

Вы можете посмотреть на то, как описана упрощенная русская грамматика, в файле rus_sa_cyk.sol.

Статистическая модель языка

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

Нисходящий и восходящий парсеры предоставляют разработчику грамматики очень важный механизм для создания модели языка с помощью ДАЛЬНОДЕЙСТВУЮЩИХ N-ГРАММ и задания веса правил. Эти средства взвешивать выдаваемые результаты, то есть присваивать каждому варианту распознавания синтаксиса некоторую числовую величину. Сравнивая эти числовые оценки для набора распознаваний, можно выявить наиболее достоверные варианты, отбросить или убрать в конец списка все остальные.

В восходящем парсере этот механизм ограничен биграммами, так как алгоритм этого парсера по своей архитектуре работает только с парами нетерминалов.

В нисходящем парсере ограничений на количество нетерминалов в правой части правил не существует. Но на практике оказывается достаточным задавать биграммы и триграммы. Биграммы позволяют описывать такой аспект языковой модели, как сочетаемость наречий с граголами и прилагательными, прилагательных с существительными и существительных в паттернах с родительным падежом, а также глаголов и существительных в роли прямого дополнения. Триграммы очень эффективны для описания предложных паттернов - то есть для сочетаний глаголов, предлогов и существительного. Хотя дальнодействующие N-граммы боле высоких порядков также можно использовать без каких-либо ограничений, на практике их полезность, по всей видимости, крайне мала. Надо заметить, что эти данные N-граммы отличаются от обычных N-грамм для цепочек слов, которые по мере увеличения порядка N-грамм все лучше описывают реально встречающиеся предложения, снижая, в частности, количество альтернативных вариантов в режиме предсказания следующего слова на основе заданной цепочки длины N-1.

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

работать по выходным в большой, проветриваемой общей вытяжкой и хорошо освещенной комнате.

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

Итак, можно выделить две причины изменения веса в ходе порождения грамматики и сопоставления.

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

дойти до конца

идти до последнего

Вариант с прилагательным употребляется достаточно редко, в связи с этим разумно присвоить соответствующему правилу штрафные очки, чтобы выдаваемые им сопоставления было легко отделить в примерах типа:

искать из последних сил

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

Кроме двух вышеперечисленных путей появления весов у результатов, особняком стоит алгоритм взвешивания синтаксических деревьев.

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

Это правила позволяют задавать соответствие для фрагмента синтаксического дерева и условного веса. После построения синтаксического дерева специальный алгоритм проходит по всем альтернативным деревьям и "взвешивает" каждое из них - применяет релевантные правила. Конечно, для эффективного перебора правил в условиях большого количества альтернативных деревьев требуется соблюденгие некоторых ограничивающих условий. Однако в целом эти правила позволяют очень просто описывать СЕМАНТИЧЕСКИЕ критерии, на основе которых из множества альтернативных деревьев выбирается одно или несколько самых достоверных.

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

Так как данные правила работают с синтаксических графом, то не играет роли алгоритм получения этого графа. Таким образом, восходящий алгоритм парсинга, архитектурно ограниченный работой с парой нетерминалов, также попадает под действие правил tree scoring.

Принцип работы итерационного алгоритма синтаксического анализа

Основная идея, лежащая в основе итерационного алгоритма, заключается в следующем. Для связывания некоторых слов достаточно проанализировать локальный контекст, в предельном случае - только два связываемых слова. Например, модификатор “очень” можно спокойно прикреплять к наречию, например в словосочетании “очень часто”, не анализируя даже соседние слова. Если выстроить процесс связывания соседних слов согласно синтаксической важности соответствующих связей, то можно быстро анализировать очень длинные предложения. Выстраивание заключается том, что сначала мы связыванием модификаторы с наречиями, затем наречия с прилагательными, глаголами, причастиями и прилагательными, затем прилагательные с существительными и так далее, постепенно переходя ко все более важным конструкциям - к связи подлежащего и сказуемого.

Однако нужно понимать, что некоторые слова требуют анализа достаточно широкого контекста, либо сами влияют на правильный разбор далеких от свого словоместа частей фразы. Самый яркий пример - частица “не”. Дело в том, что многие русские переходные глаголы меняют свою падежную валентность в отрицательной аналитической форме. Например:

Я знаю всё (винительный падеж).

Я не знаю ничего (родительный падеж).

Из-за такого влияния на синтаксические свойства русского глагола частица “не” должна быть видна правилам при анализе глагольных паттернов. Если ее прикрепить до этого момента к глаголу и вывести из контекста, то некоторые конструкции не будут правильно собираться.

Итерационный алгоритм позволяет в большинстве случаев обойти вышеуказанное ограничение, так как он не ограничивает размер сопоставляемого одним правилом контекста. Впрочем, границы применимости у него все-таки есть, и они определяются раскрываемым далее требованием обязательного укорачивания цепочки токенов до 1 элемента.

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

По мере прохода правил по цепочке появляется лес - набор синтаксических деревьев. В идеальном случае в конце концов останется только одно синтаксическое дерево.

Полный и неполный анализ. Разбор зашумленного текста.

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

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

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

В обычном режиме включается другая стратегия - неполный анализ.

Неполный анализ включает два взаимодополняющих варианта.

Кусочно-непрерывный анализ. Парсер пытается сопоставить максимально длинную цепочку токенов. Если справа остаются несопоставленные токены, то он повторяет вывод и сопоставление. Количество таких фрагментов ничем не ограничено. Парсер стремится уменьшить количество фрагментов до минимума. В предельном случае с 1 фрагментом получает обычный полный анализ. Кусочно-непрерывный анализ достаточно быстр, но в некоторых случаях можут неправильно распознать синтаксис фрагментов, так как фрагменты могут на самом деле быть синтаксически связанными. Результат его работы - лес синтаксических деревьев, каждое из которых соответствует одному фрагменту. Например, для предложения солнышко светит xxx птички поют парсер выдает такой результат:

Анализ с пропуском токенов намного более трудоемок, но способен работать с зашумленным текстом, содержащим незнакомые слова или не вписывающиеся в грамматику словоформы. Пропуск токенов может управляться задаваемым вручную правилами или выполняться автоматически. В случае управляемого пропуска разработчик грамматики может задавать штраф за пропуск и описывать достаточно сложные цепочки. К примеру, можно задавать правила для пропуска различных вводных фраз или оборотов с семантикой выражения мнения, не накладывая штафа за пропуск таких фрагментов. Неуправляемый пропуск позволяет обходить нераспознаваемые цепочки символов. Например, для предложения птички xxx поют yyy песенки получаются такие результаты:

Оба метода дополняют другу друга, как например в таком случае сильно зашумленного текста кошки xxx ловят zzz мышей yyy птички ttt поют:

Разбор от исходных данных и разбор от цели

На работу алгоритмов структурного парсера можно взглянуть с точки зрения направления анализа.

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

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

Правила и группы правил

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

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

Множество правил, имеющих одно и то же имя, образуют группу. Группы правил должны быть обязательно объявлены явно с помощью директивы patterns. Эта директива кроме ввода в грамматику нового нетерминала позволяет задать ряд дополнительных свойств правил в данной группе.

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

Каждое правило вводится с помощью директивы pattern и имени группы, к которому оно принадлежит. Формально, такое правило описывает условия, при которых в исходную цепочку слов вводится соответствующий нетерминал. Для удобства программирования правила, относящиеся к одной группе, можно вводить в любом порядке с другими правилами, причем размещая их по разным файлам. При компиляции словаря все правила будут собраны в свои группы.

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

Применение правил

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

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

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

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

Тем не менее, всегда есть риск, что новое вводимое правило будет сопоставляться с непредусмотренными замыслом разработчика конструкциями и добавит в результаты новые варианты, которые вытеснят правильные. Другой возможный случай - изменения в проверенном правиле могут неожиданно исказить его работу, и часть ранее проверенных предложений перестанет разбираться.

Чтобы упростить проверку корректности изменений мы применяем автоматизированное тестирование. Набор тестовых предложений, для которых зафиксированы требуемые результаты, прогоняются через специальную консольную утилиту. В случае расхождений получаемых фактических результатов с ожидаемыми можно начать выяснение причин. Тест выполняется в консоли и не требует никакого ручного контроля помимо запуска на исполнение.

Подробное описание формата файла с тестовыми предложениями можно прочитать на этой странице. Утилита, которая выполняет эти тесты, вместе со своими исходными текстами на C++ включена в состав SDK Грамматического Словаря.

Граммемы и теоретико-множественные операторы

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

Для практического удобства написания правил грамматический движок поддерживает другой механизм введения подмножеств слов. Этот механизм представляет собой несколько директив объявления именованных множеств слов, словарных статей, словоформ и словосочетаний. От граммем он отличается только выразительными средства и удобством использования в некоторых случаях. К примеру, если в данном контексте могут употребляться только некоторые слова, то можно либо добавить в соответствующие словарные статьи новый грамматический атрибут, либо явно перечислить эти слова и присвоить этому набору некоторое наименование, на которое потом ссылаться. Например, некоторые существительные в русском языке могут присоединять правый инфинитив: желание петь. Мы можем добавить в соответствующие словарные статьи грамматический атрибут МОДАЛЬНЫЙ, и таким образом при необходимости проверить это свойство. Либо можно по месту, рядом с соответствующим правилом, ввести именованное подмножество.

Объявленные именованные множества вводят в "фазовое" лексическое пространство новые граммемы в нужном количестве, описывающие свойства слов с нужной детальностью. В правилах мы можем ссылаться на имена подмножеств, требуя вхождения или невхождения слова в заданный набор множеств.

Именованные подмножества вводятся следующими директивами.

wordentry_set - множество словарных статей, то есть любых форм заданных слов.

word_set - множество буквально заданных слов.

wordform_set - множество словоформ.

collocation_set - множество словосочетаний.

Компилятор словаря поддерживает консистентность подмножеств, запрещая повторно давать уже выбранное имя или дважды добавлять один и тот же элемент в множество.

Кроме указанных выше именованных подмножеств, разработчик может использовать метастатьи - небольшие подмножества словарных статей, объединяемых по какому-либо морфологическому критерию. Например, для русского словаря оказывается очень удобно создать для всех глагольных частей речи метастатьи так, чтобы каждая метастатья объединяла инфинитив, глагол, причастия и деепричастия. Упоминание метастатьи в контексте правила равносильно логической операции OR для всех вариантов лемм, объединяемых этой метастатьей.

Способы представления глубинных падежей (слоты)

Описание грамматики в рамках структурного парсера предоставляет несколько способов хранить и проверять возможность участия слова в разных синтаксических и лексических контекстах. Эти способы позволяют описывать "глубинные падежы", а именно задавать наборы обязательных и опциональных слотов для слова, которое присоединяет другие слова или словосочетания.

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

Второй способ - взвешивание синтаксических деревьев. Один tree scorer определяет вес описываемого фрагмента синтаксического дерева. Задав корень и набор веток, можно описать очень детальные и разнообразные варианты "глубинных падежей". Недостаток этого подходя напрямую следует из хронологии применения данных правил - они срабатывают уже после построения синтаксических деревьев. Таким образом, они не могут оптимизировать процесс разбора.

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

Маркеры начала и конца предложения

В правилах верхнего уровня можно иногда увидеть употребление специальных нетерминальных словарных статей beth:begin{} и beth:end{}. Они появляются в обрабатываемом предложении всегда и однозначно задают левую и правую границу.

С ними связан простой трюк, позволяющий реализовать неполный анализ. Он заключается в следующем. Если мы хотим, чтобы правило обязательно распознало всё предложение или провалилось, то достаточно указать в наборе опорных точек эти два маркета.

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

Макросы и текстовый препроцессор

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

Общая структура правила

Любое правило состоит из шапки, в которой как минимум задается имя группы, тела правила в фигурных скобках с условием применения правила, и дополнительными директивами после закрывающей фигурной скодки.

Тело правила - это цепочка опорных точек. Движок будет проверять применимость правила путем сопоставления каждой опорной точки с исходной цепочкой слов слева направо (это одна из немногих неявных привязок к привычному нам направлению письма).

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

Кроме требования к слову в текущей позиции, опорная точка может являться именем группы правил, то есть выполнять поиск сопоставимых с текущей позиции паттернов. Опорная точка может быть именем подмножества (см. теоретико-множественные операции), или одной из нескольких поддерживаемых оспециальных функций. Наконец, опорная точка может быть пользовательской функцией, написанной на встроенном языке.

Встроенные функции для опорных точек

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

@not(x) - логическое отрицание, дает успех, если x не удается сопоставить.

@and(x,y1,y2,...) - сопоставление будет успешным, если будут успешно сопоставлены все перечисленные аргументы.

@or(x,y,z,...) - движок будет пытаться сопоставить в текущей позиции сначала условие x, если оно провалилось - условие y, и так далее. При исчерпании условий будет констатирован провал сопоставления данной опорной точки.

@optional(x) - жадная условная функция. Если ей удается сопоставить условие x в текущей позиции, то она сдвигает текущую позицию вправо. Если сопоставить не удается, то все равно считается, что имеет место успех для цепочки нулевой длины.

@coalesce(x) - нежадный вариант функции @optional с ветвлением. Если сопоставление не выполнено, то фиксируется успех с длиной сопоставленной цепочки 0. В противном случае дальнейшее продвижение процесса сопоставления ветвится на 2 альтернативы - так, будто сопоставление удалось и текущая позиция сдвинута вправо, и так, будно текущая позиция осталась на месте.

@mark(x,name) - функция маркировки, вводит в локальный контекст указанную переменную с именем name, что позволяет в дальнейшем ссылаться на некоторые результаты сопоставления x. Эта функция имеет другой, более удобный вариант написания (синтаксический сахар) без использования скобок: name=x.

@regex("rx") - проверка слова с помощью регулярного выражения, с игнорированием регистра.

@regex_string("rx") - регистро-зависимая проверка слова с помощью регулярного выражения.

Тело правила

Общий вид правила переписывания в самом простом случае:

pattern ИмяГруппы
{
 ОпорнаяТочка1
 ОпорнаяТочка2
 ...
}

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

Опорная точка - требования для единственного слова

В самом простом случае опорная точка проверяет буквальное значение слова. Для этого достаточно записать лексему в одиночных или двойных апострофах:

pattern ИмяГруппы
{
 'слово1'
 ...
}

Чтобы проверить, что слово является одной из грамматических форм конкретной статьи, нужно написать примерно такой код:

pattern ИмяГруппы
{
 существительное:галактика{}
 ...
}

Слова галактика, галактикой, галактикою, галактики и т.д. будут успешно сопоставлены. Обратите внимание на пустой блок (секция уточнения) из фигурных скобочек, следующий непосредственно после имени статьи. Он является обязательным элементом и выполняет две функции. Во-первых, он отграничивает многословные названия статей, например существительное:Нижний Новгород{}. Во-вторых, внутри этих скобок могут размещаться дополнительные проверки, которые мы рассмотрим позднее.

Чтобы проверить, что слово в текущей позиции относится к заданной части речи, можно вместо имени словарной статьи указать квантор *:

pattern ИмяГруппы
{
 существительное:*{}
 ...
}

Такой терм сопоставляется с любым существительным русского языка.

В качестве образца можно указать имя объявленного ранее множества. К примеру, мы можем объявить множество слов и затем использовать имя этого множества для проверки, что текущее слово входит в это множество:

word_set WordSet1=
{
 'галактику',
 'планету',
 'орбиту'
}

pattern ИмяГруппы
{
 WordSet1
 ...
}

Объявленное с помощью ключевого слова word_set множество содержит буквальные значения слов. Если мы хотим проверить, что слово является грамматической формой любой статьи в заданном наборе, то следует объявить множество командой wordentry_set:

wordentry_set WordentrySet1=
{
 существительное:галактика{},
 прилагательное:галактический{},
 глагол:приземляться{}
}

pattern ИмяГруппы
{
 WordentrySet1
 ...
}

Еще один вариант использования именованного множества заключается в объявлении набора словоформ с помощью команды wordform_set:

wordform_set WordformSet1=
{
 существительное:галактика{ падеж:им число:ед },
 прилагательное:галактический{ число:мн падеж:род форма:атриб },
 глагол:приземлиться{ время:прошедшее род:жен }
}

pattern ИмяГруппы
{
 WordentrySet1
 ...
}

Ряд полезных возможностей доступен с помощью проверки текущего слова с помощью регулярных выражений. Существует две встроенные функции, выполняющие такие проверки.

Функция @regex("xxx") проверяет, что текущее слово сопоставляется с заданным выражением, игнорируя регистр букв.

Функция @regex_string("xxx") проверяет слово на соответствие регулярному выражения с точным соответствием регистра.

К примеру, такое правило позволяет распознать слово "А.Пушкин":

pattern ФИО
{
 @regex_strict("[АБВГДЕЖЗИКЛМНОПРСТУФХЦЧШЩЭЮЯ]\\.[АБВГДЕЖЗИЙКЛМНОПРСТУФХЦЧШЩЭЮЯ][абвгдежзийклмнопрстуфхцчшщьыъэюя]+")
}

Содержимое секции уточнения

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

pattern ИмяГруппы
{
 'галактики'{ падеж:им }
 ...
}

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

Секция уточнения может содержать несколько требований на значение грамматических признаков слова. Каждое из них записывается как имя признака, двоеточие и имя состояния. Особо интерпретируется упоминание бистабильных координат, у которых есть два неявных состояния. В грамматическом словаре действует общее соглашение для таких координат. Просто упоминание имени такой координаты подразумевает состояние "1". Например, у модальных глаголов есть грамматический атрибут МОДАЛЬНЫЙ, с неявным состоянием 1. У всех остальных глаголов вообще не указан данный признак, что подразумевает пару МОДАЛЬНЫЙ:0.

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

pattern ИмяГруппы
{
 существительное:*{ ~род:ср }
 ...
}

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

wordform_set WordformSet1=
{
 существительное:галактика{ падеж:им число:ед },
 прилагательное:галактический{ число:мн падеж:род форма:атриб },
 глагол:приземлиться{ время:прошедшее род:жен }
}

pattern ИмяГруппы
{
 существительное:*{ ~WordformSet1 }
 ...
}

Комбинируя требования на грамматические признаки и теоретико-множественные предикаты в секции уточнения, можно очень точно управлять фильтрацией слов при сопоставлении.

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

wordform_set WordformSet1=
{
 существительное:галактика{ падеж:им число:ед },
 прилагательное:галактический{ число:мн падеж:род форма:атриб },
 глагол:приземлиться{ время:прошедшее род:жен }
}

pattern ИмяГруппы
{
 WordformSet1{ class:глагол НАКЛОНЕНИЕ:ИЗЪЯВ }
 ...
}

В отдельной главе рассмотрим еще один элемент секции уточнения, работающий в паре с маркировкой результатов сопоставления.

Маркировки, back reference и проверки согласования

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

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

Решается эта задача следующим образом.

Во-первых, мы можем промаркировать опорные точки в правиле, примерно так:

pattern ИмяГруппы
{
 прил1=прилагательное:*{}
 прил2=прилагательное:*{}
 ...
}

Конструкция xxx=yyy вводит новую локальную переменную. Эти переменные видны только в рамках текущего правила. Другие правила могут вводить свои переменные с такими же именами, и они не будут мешать друг другу. Аналогичную работу выполняется функция @mark(xxx,yyy), но она более громозда и менее наглядна, поэтому был введен синтаксический сахар со знаком =.

Во-вторых, в секции уточнения мы можем написать требование, чтобы грамматические свойства текущего проверяемого слова соответствовали грамматическим признакам промаркированного:

pattern ИмяГруппы
{
 прил1=прилагательное:*{}
 существительное:*{ =прил1:РОД =прил1:ЧИСЛО =прил1:ПАДЕЖ }
}

Связывание узлов и построение синтаксического дерева

Каждое правило может связывать слова, с которыми сопоставлены его термы, в фрагмент синтаксического дерева. Делается это с помощью маркировки всех термов и объявлением ребер в секции : links {} после тела правила:

pattern ИмяГруппы
{
 прил=прилагательное:*{}
 сущ=существительное:*{}
} : links { сущ.<LEFT_ATTRIBUTE>прил }

Синтаксис объявления именованного множества словарных статей

Полный формат объявления множества включает в себя указание для каждого элемента имени части речи и имени словарной статьи:

wordentry_set WordentrySet1=
{
 существительное:галактика{},
 прилагательное:галактический{},
 глагол:приземляться{}
}

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

wordentry_set WordentrySet1=
{
 глагол:увязать{ вид:соверш }, ...
}

В именованное множество словарных статей можно включать метастатьи. В этом случае в множество будут добавлены входящие в метастатью леммы.

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

wordentry_set WordentrySet1=прилагательное:{
 галактический, внегалактический, планетарный, 'кометно-астероидный'
}

Имя части речи с двоеточием помещается сразу после знака =, а элементы множества перечисляются просто как лексемы. Многословные лексемы, содержащие внутри себя символы разделители, нужно заключать в одинарные или двойные кавычки.

Актуальность спецификаций в текущей версии документа

Данный документ является предварительным вариантом полной спецификации. Он может содержать отдельные неточности. Некоторые аспекты синтаксиса правил парсинга пока не описаны полностью. В ходе развития математической модели парсера некоторые части движка могут быть переработаны без сохранения обратной совместимости с предыдущими версиями.

Дополнительные материалы

Внутренний язык грамматической машины

Компилятор словаря

Синтаксический анализатор

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

Трансформация текста

  © Elijah Koziev 2010
прикладные проекты на основе грамматического словаря API грамматической машины компоненты для доступа к грамматическому словарю условия получения SDK токенизатор и сегментатор морфологический анализ и синтез лемматизатор база N-грамм синтаксический анализатор словоформы морфология и синтаксис русского языка падеж число род совершенный и несовершенный вид экспорт в SQL формат экспорт в XML формат скрипт SQL словаря структура SQL словаря структура XML словаря компоненты для доступа к грамматическому словарю ORM Persistent Dictionary Library лемматизация стемминг примеры использования грамматического словаря склонение существительных в русском языке склонение русских прилагательных спряжение глаголов в русском языке поиск текста с учетом морфологии OCR подсистема расширенные регулярные выражения генератор текста генератор случайного текста и имитатор рандомизатор синонимизатор перефразировщик Статистика буквенных паттернов

Грамматический словарь русского языка



Грамматический словарь
склонение и спряжение глаголов, существительных, прилагательных

В состав входит русский и английский словарь.

платформа:  Windows 2000 ... Windows 7
требования: 512 Mb свободной памяти, 300 Мб на диске
размер:         34 Мб

  скачать грамматический словарь купить грамматический словарь SDK грамматического словаря
грамматический словарь русского языка



SDK Грамматического словаря



SDK Грамматического Словаря
склонение и спряжение глаголов, существительных, прилагательных

В состав входит русский и английский словарь.

платформа:  Windows 2000 ... Windows 7
размер:         13 Мб

SQL словарь (демо):
sqlite mysql oracle firebird mssql

скачать демо-версию SDK купить SDK API грамматического словаря



Поисковая система



Integra
настольная и сетевая поисковая система 

платформа:  Windows XP ... Windows 7
требования: 512 Mb свободной памяти
размер:         21 Мб

Дополнительные компоненты:
MySQL поисковый сервер 13.5 Мб
Integra.Premium MySQL 3.9 Мб

скачать поисковую систему SDK поисковой системыописание поисковой системы



SDK Поисковой системы



SDK Поискового движка
API для настольной и сетевой поисковая система 

платформа:  Windows XP ... Windows 7
размер:         17 Мб

Дополнительные компоненты:

MySQL поисковый сервер 13.5 Мб
Integra.Premium MySQL 3.9 Мб

скачать SDK SDK поисковой системы



Экранный переводчик



Translator
экранный переводчик

платформа:  Windows XP ... Windows 7
требования: 256 Mb свободной памяти
размер:         4.4 Мб

Дополнительные компоненты:
расширенный англо-русский словарь 6.4 Мб


скачать экранный переводчикописание экранного переводчика



изменено 23-Nov-12