Синтаксический анализ входных сообщений

Задачей синтаксического анализа является построение синтаксической структуры входного предложения (осуществление разбора предложения) на основе морфологической информации о словоформах и синтаксических правил объединения слов и словосочетаний. Синтаксическая структура отражает синтаксические связи, существующие между словами в предложении. Ее получение начинается с построения всевозможных связей между словами, которые в последующем отсеиваются на основе локальных и глобальных «фильтров». Конкретный вид структуры определяется выбранной системой синтаксических отношений (ССИО) [10].

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

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

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

· множество содержит отрезок, состоящий из всех точек цепочки , и все одноточечные отрезки ;

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

Элементы называются составляющими. Одноточечные отрезки называются точечными (тривиальными) составляющими.

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

(Мы увидели (( древние стены) города))

1 23 3 21

(Мы увидели (древние (стены города)))

1 2 3 321

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

Остановимся подробнее на способе описания синтаксической структуры с помощью деревьев зависимостей (деревьев синтаксического подчинения).

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

Рис. 3.7. Пример дерева зависимостей

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

Иногда для представления синтаксической структуры предложения используют смешанное представление, называемое обобщенной синтаксической структурой (ОСС). ОСС выражает, как и дерево зависимостей, ориентацию связей, но, в отличие от дерева зависимостей, ОСС снабжена информацией о словосочетаниях, образованных группами членов предложения (группой подлежащего, группой сказуемого, группой дополнений, группой обстоятельств и т.п.). Эти группы называются именными группами (ИГ). Кроме того, ОСС изображает в общем случае не один вариант разбора предложения, а несколько омонимичных (с точки зрения СИА) вариантов. Указанное обстоятельство позволяет уменьшить как количество возвратов от семантического анализа к синтаксическому анализу, так и количество вариантов разбора, генерируемых на этапе СИА.

Рассмотрим основные принципы построения алгоритма синтаксического анализа.

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

Общая структура алгоритма СИА может быть определена следующим образом:

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

2. Для выбранного разбиения предложения на ИГ осуществляется построение всех вариантов проведения СИО внутри каждой ИГ, т.е. построение обобщенного варианта разбора ИГ.

3. Если при выполнении пунктов 1 и 2 СИО были установлены на все слова предложения, то алгоритм передает управление этапу семантического анализа (СЕА). Иначе управление передается п. 1 для выбора очередного разбиения предложения на ИГ.

4. Если этап СЕА не смог обработать переданную ему синтаксическую структуру входного предложения, то этап СЕА возвращает управление п. 1.