LL обычно более эффективный метод разбора, чем рекурсивный спуск. На самом деле, наивный анализатор рекурсивного спуска на самом деле будет O (k ^ n) (где n - размер ввода) в худшем случае. Некоторые методы, такие как запоминание (которое дает парсер Packrat ), могут улучшить это, а также расширить класс грамматик, принимаемых парсером, но всегда есть пробел. Парсеры LL - это (насколько мне известно) всегда линейное время.
С другой стороны, вы правы в своей интуиции, что парсеры рекурсивного спуска могут обрабатывать больший класс грамматик, чем LL. Рекурсивный спуск может обрабатывать любую грамматику LL (*) (т. Е. unlimited lookahead), а также небольшой набор неоднозначных грамматик. Это связано с тем, что рекурсивный спуск - это на самом деле прямая кодировка реализации PEG или грамматик (ов) выражения синтаксического анализатора . В частности, дизъюнктивный оператор (a | b) не является коммутативным, что означает, что a | b не равно b | a. Парсер рекурсивного спуска будет пробовать каждую альтернативу по порядку. Поэтому, если a соответствует входному значению, оно будет успешным, даже если b будет соответствовать входному. Это позволяет обрабатывать классические неоднозначности «самого длинного совпадения», такие как висящая проблема else, просто упорядочив дизъюнкции.
С учетом всего вышесказанного, возможно реализовать LL (k) -парсер с использованием рекурсивного спуска, чтобы он работал за линейное время. Это делается путем, по существу, встраивания наборов предсказаний, так что каждая подпрограмма синтаксического анализа определяет соответствующую производительность для данного ввода в постоянное время. К сожалению, такая техника исключает обработку целого класса грамматик. Как только мы приступим к интеллектуальному анализу, такие проблемы, как висячие else, уже не будут решаться с такой легкостью.
Что касается того, почему LL будет выбран вместо рекурсивного спуска, то это в основном вопрос эффективности и ремонтопригодности. Синтаксические анализаторы с рекурсивным спуском заметно проще в реализации, но их обычно сложнее поддерживать, поскольку представляемая ими грамматика не существует ни в какой декларативной форме. В большинстве нетривиальных сценариев синтаксического анализа используется генератор синтаксического анализатора, такой как ANTLR или Bison. С такими инструментами действительно не имеет значения, является ли алгоритм прямым кодированием рекурсивного спуска или LL (k), управляемым таблицей.
Интересно также обратить внимание на рекурсивное восхождение , которое представляет собой алгоритм синтаксического анализа, кодируемый непосредственно после способа рекурсивного спуска, но способный обрабатывать любую грамматику LALR. Я бы также углубился в комбинаторы парсеров , которые являются функциональным способом составления парсеров рекурсивного спуска.