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

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

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

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


parsing grammar ll context-free-grammar recursive-descent
person Noldorin    schedule 25.06.2009    source источник
comment
Эй, не могли бы вы объяснить. Вы пишете , похоже, это парсер LL (с ​​использованием таблицы стека / синтаксического анализа) и парсер с рекурсивным спуском (просто с использованием рекурсии).. В этом ответе говорится, что все нисходящие синтаксические анализаторы являются анализаторами LL. Я смущен   -  person Max Koretskyi    schedule 31.08.2017
comment
@MaximKoretskyi Это определенно неправда. Парсеры LL - это подмножество парсеров сверху вниз.   -  person Noldorin    schedule 31.08.2017
comment
спасибо, не могли бы вы опубликовать свой ответ на мой вопрос?   -  person Max Koretskyi    schedule 31.08.2017

Ответы (1)


arrow_upward
108
arrow_downward

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

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

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

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

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

person Daniel Spiewak    schedule 25.06.2009
comment
Я очень надеялся на ответ! :) Спасибо за всю информацию (включая последнюю часть, о которой я даже не знал). Возможно, потребуется немного больше прочитать, прежде чем я пойму все концепции, которые вы представили в этом ответе, но вы, безусловно, ответили на мой вопрос и указали мне правильное направление для дальнейшего изучения. Главное, о чем я сейчас не уверен, - это то, как PEG соотносятся с рекурсивными синтаксическими анализаторами спуска, а также как именно комбинатор синтаксического анализатора объединяет различные синтаксические анализаторы. Если бы вы могли прояснить одно / оба из них, я был бы очень признателен. - person Noldorin; 25.06.2009
comment
Кроме того, просто для подтверждения; эффективно ли встраивание наборов прогнозов в предиктивный синтаксический анализ? В таком случае, что представляет собой весь класс грамматик? - person Noldorin; 26.06.2009
comment
PEG - это формальное описание синтаксического анализатора с рекурсивным спуском. Поскольку на самом деле рекурсивный спуск не является анализом LL, потребовалась другая модель. Вы можете думать о них как о LALR и Bison, один из которых является формализмом, а другой - реализацией. - person Daniel Spiewak; 26.06.2009
comment
Наборы прогнозов: это действительно зависит от используемой стратегии. Если вы исключительно полагаетесь на эти наборы прогнозов и не выполняете поиск с возвратом, тогда класс грамматик - это в точности LL (k), где k - количество опережающих просмотров, используемых для вычисления наборов прогнозов. Тем не менее, вы можете получить много преимуществ от прогнозного синтаксического анализа, встраивая наборы прогнозируемых данных в R-D без полного исключения обратного отслеживания. Это позволяет синтаксическим анализаторам, которые принимают все грамматики, обычно обрабатываемые R-D, но с более быстрым средним регистром. К сожалению, худший случай для таких парсеров все еще экспоненциальный. - person Daniel Spiewak; 26.06.2009
comment
Большинство синтаксических анализаторов с рекурсивным спуском (даже написанные вручную) будут использовать встроенные наборы предсказаний для ограничения альтернатив, ограничивая отслеживание с возвратом без ограничения гибкости. Конечным результатом является синтаксический анализатор, который почти линейно работает по времени для всего, кроме наиболее патологических грамматик, и который по-прежнему принимает весь класс PEG. - person Daniel Spiewak; 26.06.2009
comment
Хорошая вещь. Одна придирка: большинство нетривиальных вариантов использования реализовано в каком-то генераторе синтаксического анализатора ... Это неправда. Наиболее широко используемые компиляторы и IDE (хорошие примеры - C #, VB, Visual C ++ и GCC) используют рукописные синтаксические анализаторы. Это, возможно, одни из самых нетривиальных применений. - person Scott Wisniewski; 05.07.2010
comment
Совершенно верно (ну, почти; GCC использует Bison). Как известно, в Java используется рукописный синтаксический анализатор (хотя в Java 7 есть переписанный синтаксический анализатор на основе ANTLR), как и в Scala, Python, Haskell и многих других. Однако я думаю, что если вы проведете полную перекличку, включая такие, как C / C ++, Ruby и т. Д., Я думаю, вы обнаружите, что толпа генераторов парсеров в целом выигрывает. - person Daniel Spiewak; 05.07.2010
comment
Не могли бы вы привести пример экспоненциального парсера RD? - person Giovanni Funchal; 23.07.2010
comment
@DanielSpiewak Я знаю, что вы опубликовали этот комментарий много лет назад, но даже тогда это было неправильно;) GCC использовал bison для C-парсера до 3.x, но переключился на рукописный рекурсивный анализатор спуска в 2008 году, насколько я могу скажите из этого gcc.gnu.org/wiki/New_C_Parser - person Morten Jensen; 13.03.2013
comment
Я могу подтвердить, что парсеры LL работают всегда с линейным временем (если, конечно, вы намеренно не пытаетесь сделать его нелинейным; замедление работы обычно не т сложно!). Это потому, что никакого обратного отслеживания никогда не происходит (другими словами, LL(k) синтаксический анализатор всегда точно знает, какую альтернативу выбрать только из k опережающих символов). LL(1) - это обычный случай, когда у вас есть только один такой токен. - person Tim Čas; 11.02.2015
comment
@Daniel Spiewak: Я не думаю, что Python использует рукописный синтаксический анализатор. Но он использует собственный генератор парсеров, написанный GvR. Это был первый код, который он написал для Python. (Я думаю, что лексический синтаксис Python технически не является LL (k) из-за необходимости отслеживать произвольные уровни отступа, но грамматика высокого уровня - это. Не уверен.) - person Jason Orendorff; 23.02.2016
comment
@DanielSpiewak LL обычно является более эффективным методом синтаксического анализа, чем рекурсивный спуск. Это правда? При разборе грамматики LL при рекурсивном спуске никогда не нужно возвращаться, верно? (Я поддерживаю парсер рекурсивного спуска; он выполняет возврат только в тех местах, где грамматика явно не-LL.) - person Jason Orendorff; 23.02.2016
comment
Согласитесь с @JasonOrendorff. Подобное относительное утверждение имеет смысл только в том случае, если вы сравниваете алгоритмы на одних и тех же наборах входных данных. Тот факт, что рекурсивный спуск может быть очень медленным для грамматик, отличных от LL (k), не имеет значения для прямого сравнения. - person Raphael; 24.04.2017
comment
LL - это не метод разбора. Это урок грамматики. Синтаксический анализатор с рекурсивным спуском может быть написан в соответствии с грамматикой LL (1). Существует алгоритм анализа LL, управляемый таблицами, который, по-видимому, вы обсуждаете. - person user207421; 01.09.2017