Естественно-языковые системы. Евдокимова И.С. - 82 стр.

параллельно (или по очереди в случае последовательного анализа), при неудаче какого-либо
варианта разбора соответствующий вариант удаляется из набора возможностей. Во втором
случае, при анализе "в глубину", выбирается одна из альтернатив, а при неудаче построения
разбора происходит возврат на точку последней альтернативы и выбор другого варианта.
Использование анализа с проходом сверху-вниз не позволяет создавать неграмматичные
варианты. С другой стороны, анализ снизу-вверх не позволяет генерировать гипотезы
разбора, невозможные для данного предложения.
     Комбинацию достоинств этих вариантов представляет анализ с помощью таблиц,
содержимое которых является результатом частичного разбора. В случае, если разбор по
какому-то пути зашел в тупик, происходит возврат на точку выбора последнего правила и
делается попытка использовать другое правило. Однако заполнение таблицы, порожденное
предыдущим способом разбора, сохраняется в таблице и может быть использовано в разборе
по текущей ветке. Эта информация не запрещает проход анализа по тем веткам, которые уже
были опробованы, но неудачно. Для этой цели применяется запоминание также и гипотез,
выдвигаемых при разборе, и результатов их проверки. Такой подход называется анализом с
помощью схем (chart-parsing). Впервые его предложил Мартин Кэй в системе Powerful Parser.
     Грамматики конечных автоматов достаточно эффективны в реализации, но обладают
слишком ограниченными возможностями для анализа, по этой причине одним из широко
используемых механизмов анализа является формализм расширенных сетей переходов
(augmented transition networks, ATN). Формализм ATN расширяет грамматику конечных
автоматов, вводя аппарат рекурсивного вызова новой подсети переходов (операция PUSH) и
набор регистров, в которых хранятся текущие результаты разбора фразы, а также средства
работы с этими регистрами. Значения регистров могут выступать условиями для переходов
по веткам, что обеспечивает частичную зависимость от контекста и выход за пределы КС-
грамматик. Благодаря регистрам и операциям над значениями, которые там хранятся, ATN-
формализм эквивалентен процедурному языку программирования, в котором можно описать
анализ языка произвольной сложности.
     Логико-алгоритмические подходы синтаксического анализа. В настоящее время можно
говорить о существовании трех основных логико-алгоритмических подходов СА:
недетерминированный «сначала в ширину», недетерминированный «сначала в глубину» и
детерминированный.
     Недетерминированный «сначала в ширину». Недетерминированный подход «сначала
в ширину» характеризуется тем, что процедура синтаксического анализа на первом этапе
порождает заведомо избыточный набор синтаксических связей, из числа которых на втором
этапе с помощью серии фильтров отбираются такие, которые в совокупности давали бы
правильную синтаксическую структуру входного предложения (или несколько правильных
синтаксических структур). Этот подход был впервые теоретически обоснован и
экспериментально проверен О.С.Кулагиной. В настоящее время эта стратегия имеет
варианты, которые различаются:
     1) степенью ослабления контекстуальных условий на этапе порождения связей;


                                              82