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

Question

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

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

Answer 1

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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

Answer 4

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

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

Answer 5

Я никогда не видел реального сравнения между синтаксическим анализатором сверху вниз и сдвигом-уменьшением:

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

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

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

Answer 6

У меня есть два предположения, хотя я сомневаюсь, что любой из них полностью объясняет это:

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

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