Разница между парсером LL и рекурсивным спусками?

Question

Я недавно пытался научить себя, как работают парсеры (для языков/контекстно-свободных грамматик), и большинство из них, кажется, имеет смысл, кроме одного. Я фокусирую свое внимание, в частности на LL (k) грамматики, для которых два основных алгоритма кажутся LL parser (с использованием таблицы стека/разбора) и Recursive Descent parser (просто используя рекурсию).

Насколько я вижу, алгоритм рекурсивного спуска работает на всех граммах LL (k) и, возможно, больше, тогда как парсер LL работает на всех грамматиках LL (k). Однако рекурсивный синтаксический анализатор спуска очень прост, чем LS-парсер для реализации, хотя (как LL один проще, чем LR).

Так что мой вопрос в том, какие преимущества/проблемы могут возникнуть при использовании любого из алгоритмов? Почему можно было бы выбрать LL над рекурсивным спуском, учитывая, что он работает с одним и тем же набором грамматик и сложнее реализовать?

Answer 1

LL обычно является более эффективной методикой синтаксического анализа, чем рекурсивный спуск. Фактически, парсер наивного рекурсивного спуска будет фактически O (k^n) (где n - размер ввода) в худшем случае. Некоторые методы, такие как memoization (который дает парсер Packrat), могут улучшить это, а также расширить класс грамматик, принятых парсером, но всегда есть компромисс между пространством. Анализаторы LL (насколько мне известно) всегда линейны.

С другой стороны, вы верны в своей интуиции, что паркуры с рекурсивным спусками могут обрабатывать более высокий класс грамматик, чем LL. Рекурсивный спуск может обрабатывать любую грамматику, которая является LL (*) (то есть без ограничений lookahead), а также небольшой набор неоднозначных грамматик. Это связано с тем, что рекурсивный спуск на самом деле представляет собой прямую кодировку PEG, или Parser Expression Grammar(s). В частности, дизъюнктивный оператор (a | b) не является коммутативным, то есть a | b не равен b | a. Парсер с рекурсивным спусками будет пытаться использовать каждую альтернативу по порядку. Поэтому, если a соответствует входу, оно будет выполнено, даже если bбудет иметь, соответствующий входу. Это позволяет классифицировать неоднозначность «длинного совпадения», например, проблему оборванности else, просто путем упорядочения дизъюнкций.

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

Что касается того, почему LL выбирается по рекурсивному спуску, это в основном вопрос эффективности и ремонтопригодности. Паркурсы с рекурсивным спусками значительно проще реализовать, но их обычно сложнее поддерживать, поскольку грамматика, которую они представляют, не существует ни в одной декларативной форме. В большинстве случаев нетривиального использования парсера используется генератор парсеров, такой как ANTLR или Bison. С такими инструментами действительно не имеет значения, является ли алгоритм прямо-кодированным рекурсивным спусканием или управляемым таблицей LL (k).

В качестве интереса также стоит посмотреть на recursive-ascent, который представляет собой алгоритм синтаксического анализа, который напрямую кодируется после рекурсивного спуска, но способен обрабатывать любую грамматику LALR. Я бы также копал в parser combinators, которые являются функциональным способом составления парсов рекурсивного спуска вместе.