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

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

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

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

Ответ 1

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

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

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

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

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