Почему синтаксический анализ снизу вверх чаще, чем синтаксический анализ сверху вниз?

Кажется, что парсеры с рекурсивным спусками не только просты в объяснении, но и простейшие в дизайне и обслуживании. Они не ограничены грамматиками LALR (1), и сам код может быть понят простым смертным. Напротив, анализаторы с нижним индексом имеют ограничения на грамматику, которую они могут распознать, и должны быть созданы специальными инструментами (потому что таблицы, которые их приводят, невозможно создать вручную).

Почему тогда происходит снизу вверх (т.е. сдвиг-уменьшение) синтаксический анализ чаще, чем синтаксический анализ с уменьшением вниз (то есть рекурсивный спуск)?

Ответ 1

Если вы выберете мощный генератор синтаксического анализатора, вы можете закодировать свою грамматику, не беспокоясь о специфических свойствах. (LA) LR означает, что вам не нужно беспокоиться о левой рекурсии, еще одна головная боль. GLR означает, что вам не нужно беспокоиться о локальной двусмысленности или взгляде.

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

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

Ответ 2

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

Разница в производительности увеличивается при увеличении сложности грамматики.

Ответ 3

Это происходит из нескольких разных вещей.

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

К сожалению, методы синтаксического анализа сверху вниз имеют тенденцию падать при применении к таким обозначениям, поскольку они не могут обрабатывать многие распространенные случаи (например, левая рекурсия). Это оставляет вам семейство LR, которое хорошо работает и может обрабатывать грамматики, а так как они производятся машиной, кто заботится о том, как выглядит код?

Вы правы, хотя: партизаны сверху вниз работают более "интуитивно", поэтому их легче отлаживать и обслуживать, и как только у вас есть небольшая практика, их так же легко написать, как созданные с помощью инструментов, (Особенно, когда вы попадаете в сдвиг/уменьшаете конфликт ад.) Многие ответы говорят о производительности синтаксического анализа, но на практике синтаксические анализаторы часто могут быть оптимизированы так быстро, как машинные парсеры.

Вот почему многие составители произведений используют рукописные лексеры и парсеры.

Ответ 4

У меня есть две догадки, хотя я сомневаюсь, что это полностью объясняет это:

Синтаксический анализ сверху вниз может быть медленным. Анализаторы с рекурсивным спусками могут потребовать экспоненциального времени для выполнения своей работы. Это создало бы серьезные ограничения на масштабируемость компилятора, который использует синтаксический анализатор сверху вниз.
Лучшие инструменты. Если вы можете выразить язык в каком-то варианте EBNF, то, скорее всего, вы можете Lex/Yacc пройти мимо множества утомительных кодов. Кажется, что не так много инструментов, чтобы помочь автоматизировать задачу составления парсера сверху вниз. И пусть смотреть на него, измельчая код парсера, просто не интересная часть игр с языками.

Ответ 5

Я никогда не видел реального сравнения парсера с нисходящим и сдвигом:

только две небольшие программы работали одновременно, бок о бок, используя подход сверху вниз и более одного, используя подход "снизу вверх", каждый из примерно 200 строк кода,

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

Итак, как честно говорить о чем-то, чего мы никогда не делали: строгое сравнение двух подходов?

Ответ 6

Чтобы добавить к другим ответам, важно понять, что, помимо эффективности, синтаксические анализаторы снизу вверх могут принимать значительно больше грамматик, чем парсеры с рекурсивным спусками. Синтаксические анализаторы сверху вниз - имеют прогностическое или нет - могут иметь только один токен с выражением и потерпеть неудачу, если текущий токен и все, что сразу следует за токеном, могут быть получены с использованием двух разных правил. Конечно, вы могли бы реализовать парсер, чтобы иметь больше обзоров (например, LL (3)), но насколько вы готовы его вытолкнуть, прежде чем он станет таким же сложным, как парсер снизу вверх? С другой стороны, партизаны Bottom-up (LALR) поддерживают список firsts и follows и могут обрабатывать случаи, когда ниспадающие парсеры не могут.

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