Главная > Разное > Автоматический синтаксический анализ
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

3. ГРАММАТИЧЕСКИЙ РАЗБОР

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

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

в принципе не имеет значения то, как мы пытаемся заполнить внутреннюю часть треугольника. Мы можем заполнять треугольник от вершины вниз

или снизу к вершине

или же от левого угла

или в любом другом порядке. Однако порядок заполнения треугольника может в большой степени влиять на эффективность процесса.

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

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

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

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

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

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

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

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

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

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

Для иллюстрации рассмотрим грамматику

Если производить для этой грамматики разбор сверху вниз

то на первом шаге имеем

на втором шаге

и на третьем шаге

Мы руководствовались здесь следующим априорным критерием. Если осталось одно незатронутое слово, применяем подстановку

в противном случае применяем

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

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

<< Предыдущий параграф Следующий параграф >>
Оглавление