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

4.5. ОБЩАЯ ПРОГРАММА ГРАММАТИЧЕСКОГО РАЗБОРА

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

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

Предположим, что последовательность слов

должна быть сопоставлена с правилом подстановки

Согласование возможно, только если bc выводимо из Q и fg выводимо из R. Алгоритм состоит в следующем. Нам задаются последовательность слов а и правило подстановки , и мы хотим показать их совместимость. Правая часть правила подстановки может содержать некоторые слова. Проверяем последовательность а, чтобы убедиться, что эти слова встречаются в правильном порядке. Если это не так, то данный разбор не проходит. Если же это условие выполнено, то по очереди выделяем различные способы разбора (если все они должны быть перечислены). Фрагменты последовательности а, заключенные между опорными словами, должны быть выведены из тех классов, которые встречаются в р между соответствующими словами. При этом мы снова имеем дело с сегментами, которые должны быть выведены из конкретных классов, и можно рекурсивно обратиться к тому же алгоритму сопоставления. Два класса, расположенные рядом в записи правила подстановки, могут породить значительное число различных вариантов.

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

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

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

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

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

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

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