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

4.2. АПРИОРНЫЕ КРИТЕРИИ ДЛЯ ГРАММАТИЧЕСКОГО РАЗБОРА СВЕРХУ ВНИЗ

Метод разбора сверху вниз имеет один существенный недостаток. Рассмотрим грамматику

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

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

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

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

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

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

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

получаем

Это означает, что S начинается с Т или а и что Т начинается с Т или с.

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

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

порождает

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

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

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

Может оказаться также, что последовательность слов не соответствует остатку разбора. Не менее желательно, чтобы мы не занимались многократно установлением этого факта. Позволяющий избежать повторений при анализе метод, ориентированный на естественные языки, описан в статье [25].

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