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

      2) статусом синтаксических структур, подвергающихся фильтрации (синтаксическая
структура входного предложения, синтаксическая структура фрагмента входного
предложения) и другими чертами.
      Примерами систем, использующих этот подход, могут служить АРТ, ЭТАП-2,
алгоритм Л.Г. Митюшина,1 и 2 версии ЛГУ, алгоритм Е.И. Анно и т.д.
      Недетерминированный «сначала в глубину». Во многих системах, ориентированных
на промышленную эксплуатацию, используется другая стратегия СА. Она встречается под
разными названиями: стратегия, опирающаяся на механизм возвратов backtracking, стратегия
depth-first («сначала в глубину»); в некоторых работах эта стратегия объединяется с
предыдущей под одним названием «недетерминированный анализ». Этот подход принят,
например, в системе АДАМАНТ. Отличие его от концепции псевдопараллелизма состоит в
том, что алгоритм на каждом шаге выбирает одну из возможных интерпретаций, но при этом
сохраняется принципиальная возможность порождения альтернативных интерпретаций в
случае той или иной неудачи с первой (например, если полученная синтаксическая структура
входного предложения или его фрагмент не удовлетворяет требованиям проективности,
связности, не проходит семантический фильтр и т.п.). Если первый вариант разбора
признается неудовлетворительным, нет необходимости начинать анализ сначала. Процедуре
анализа достаточно вернуться в ближайшее из состояний, при котором возможен был
альтернативный путь, и попытаться довести до конца этот вариант. Если же и он окажется
неприемлемым, процедура снова использует механизм возвратов и перейдет к следующему
варианту и так далее, пока не будет порожден первый приемлемый вариант разбора входного
предложения. Поиск других вариантов после этого прекращается.
      Скорость работы системы с механизмом возвратов зависит от того, удается ли ей в
подавляющем большинстве случаев получать приемлемый вариант синтаксического анализа
с минимальным количеством возвратов – в идеале без них. Если алгоритм не позволяет
этого, он не является оптимальным с точки зрения быстродействия, так как прежде, чем
приемлемый вариант будет найден, алгоритм затратит время на порождение и фильтрацию
неверных вариантов анализа входного предложения или его фрагментов. Такими являются, к
примеру, алгоритмы в системах LUNAR Вудса и SHRDLU Т. Винограда.
      Это общий недостаток двух рассмотренных стратегий. Однако скорость анализатора,
опирающегося на механизм возвратов, по-видимому, выше. Алгоритм, опирающийся на
механизм возвратов, может располагать эффективным способом обработки простых и
стандартных по структуре предложений, практически не порождая избыточных
синтаксических структур. В то же время использование механизма возвратов позволит ему
найти приемлемую интерпретацию для менее стандартного по структуре предложения.
      Чтобы избежать указанного недостатка, в ряде систем (например, АДАМАНТ) упор
делается на развитые эвристические методы, управляющие процессом анализа, которые
позволили бы получать предпочтительный вариант разбора первым.
      Детерминированный подход. Третья стратегия – стратегия детерминированного
анализа – базируется на следующем принципе: ни одна синтаксическая связь, установленная


                                              83