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

4.4. АПРИОРНЫЕ КРИТЕРИИ ДЛЯ АНАЛИЗА СНИЗУ ВВЕРХ

В чистом виде метод разбора снизу вверх не очень эффективен, так как возможно большое число неудачных попыток. Однако можно воспользоваться эффективным априорным критерием.

Рассмотрим предыдущий пример на этапе

Имеет смысл применять только те правила подстановки, которые начинаются с ид. Каждое такое правило подстановки является частью определения промежуточного класса. Если с этого класса не может начинаться предложение, то ни к чему применять соответствующее правило подстановки. В данном случае применимы два правила подстановки

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

Опять применимы два правила подстановки, на этот раз

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

и поэтому остаток должен начинаться с S. Следовательно, к началу фразы b X с применимы только правила подстановки, описывающие такие классы, с которых может начинаться S.

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

и далее мы применяем только правила подстановки, описывающие такие классы, с которых может начинаться Q.

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

Рассмотрим работу этого алгоритма при разборе предложения применительно к грамматике

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

Слева записывается предложение, справа — примененное правило подстановки и в середине некоторая последовательность пар. Первым элементом каждой пары является остаток подстановки, а вторым элементом — название класса, которому соответствует данное правило подстановки. Если первый элемент первой пары соответствует первому слову в предложении, то мы удаляем его и из предложения, и из записи подстановки.

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

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

Развивая второй вариант, мы получаем

Первый из этих вариантов означал бы завершение разбора и поэтому не пригоден.

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

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