Нисходящий анализ: компьютерный алгоритм
Нисходящий анализ был представлен в 1970-х годах и остается широко распространенной стратегией, которая также стала основой для более новых и сложных алгоритмов. Стратегия «сверху вниз» предпочиталась в течение длительного периода времени из-за ее сравнительной простоты, удобства использования и возможности настройки. Как следует из самого термина, синтаксический анализ сверху вниз включает идентификацию корня дерева синтаксического анализа. Когда корень идентифицирован, происходит движение вниз по поддеревьям и, в конце концов, находятся листья дерева. Синтаксический анализатор исследует дерево разбора с помощью формальных правил перезаписи грамматики.
Наши специалисты могут предоставить индивидуальное эссе
с учетом ваших инструкций
всего за 13,00 $ 11,05 $/стр. сформировать входную строку. Анализ начинается с фокуса на начальном символе дерева синтаксического анализа, а листовые узлы дерева синтаксического анализа являются конечной целью процесса.
Чтобы проиллюстрировать особенности нисходящей модели, можно подробнее рассмотреть простой пример сложения (68 + 124). Двигаясь вправо, лексер идентифицирует цифру 68, пробел, знак плюс и еще одну цифру. Сначала идентифицируется токен типа NUM, за которым следует токен типа PLUS. После этого лексер находит еще один токен типа NUM (124). Наконец, лексер определит последовательность как выражение суммы.
Преимущества алгоритма довольно многочисленны, что делает модель все еще применимой. Разделение проблемы на мелкие части позволяет понять, кто именно должен это сделать. Каждый шаг характеризуется доработкой новых элементов, которые становятся более понятными и управляемыми.
Что касается недостатков, то при нисходящем разборе каждый сегмент программируется отдельно, поэтому часто встречается избыточность. Линейный характер процесса также связан с существенным недостатком. Следующая последовательность может быть невозможна для обработки парсером сверху вниз: 3 * 5 * 8 + 4 * 2. Как и в примере, упомянутом выше, парсер идентифицирует токены и символы типа NUM. Когда синтаксический анализатор распознает его как выражение, решением этой последовательности является переключение с разбора сверху вниз на алгоритм специального назначения.
В заключение можно отметить, что этот тип алгоритма разбора языка программирования может использоваться в различных ситуациях, когда доступны линейные последовательности.