Ответ 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. Я также мог бы копаться в компараторах парсеров, которые являются функциональным способом компоновки парсов рекурсивного спуска вместе.