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

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

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

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

1 68
parsing shell grammar context-free-grammar recursive-descent

1 ответ:

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

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

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

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

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

86