Какие преимущества имеют парсеры LL по сравнению с парсерами LR?

Question

Какие преимущества имеют парсеры LL по сравнению с парсерами LR, чтобы гарантировать их относительную популярность в современных инструментах генератора парсеров ?

Согласно Википедии , LR-анализ, похоже,преимущества перед LL:

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

Примечание: это не домашняя работа.Я был просто удивлен, когда узнал, что Antlr является генератором синтаксического анализатора LL (несмотря на то, что в его имени есть "LR").

Answer 1

GLR отлично подходит, если вы хотите разобрать дерево / лес и не возражаете против черных ящиков.Это позволяет вам вводить все, что вы хотите CFG , за счет проверки неоднозначностей во время анализа путем исчерпывающего тестирования, вместо статического разрешения конфликтов LR / LALR.Некоторые говорят, что это хороший компромисс.Инструмент DMS Ира Бакстера или Elkhound, который имеет бесплатную грамматику C ++, полезен для этого класса проблем. ANTLR также полезен для большого класса языковых приложений, но использует подход «сверху вниз», генерирующий парсеры рекурсивного спуска, называемые LL (*), которые допускают семантические предикаты.Я приведу здесь без доказательств, что предикаты позволяют вам анализировать контекстно-зависимые языки за пределами CFG.Программисты любят вставлять действия в грамматику, любят хорошую обработку ошибок и любят одношаговую отладку.Л.Л. хорош во всех трех.LL - это то, что мы делаем вручную, чтобы его было легче понять.Не верьте бессмыслице в Википедии о том, что LR лучше обрабатывает ошибки .Тем не менее, если вы откатываете много назад с ANTLR, ошибки действительно хуже с LL (*) (у PEG есть эта проблема).

Повторный откат.GLR также спекулирует (то есть возвращается), как PEG, ANTLR и любая другая недетерминированная стратегия.В любом недетерминированном состоянии LR GLR «разветвляет» подпарсеры, чтобы опробовать любой жизнеспособный путь.В любом случае, LL имеет хороший контекст для обработки ошибок.Если LR знает, что оно соответствует выражению, LL знает, что это выражение в присваивании или IF -условие;LR знает, что это может произойти, но не уверен - и эта неопределенность заключается в том, где он получает свою силу.

GLR - O(n^3) худший случай.packrat / PEG - O(n) худший случай.ANTLR имеют значение O(n^2) из-за циклического прогнозируемого DFA, но на практике O(n).На самом деле не имеет значения.GLR достаточно быстр.

ANTLR это AN прочее T ool для L ang R признание не анти-LR, но оно мне тоже нравится;)

Честно говоря, как и многие молодые программисты в 80-х, я не понимал LALR и не любил черные ящики (теперь я копаюкрасота двигателя GLR но все же предпочитаю LL).Я создал коммерческий компилятор на основе LL (k) и решил создать инструмент для генерации того, что я создал вручную.ANTLR не для всех, и такие крайние случаи, как C ++, могли бы быть лучше обработаны с помощью GLR, но многие люди находят, что ANTLR вписывается в их зону комфорта.С января 2008 года было загружено 134 000 бинарных файлов ANTLR в пределах ANTLRWorks и общее количество почтовых индексов (согласно Google Analytics).См. нашу статью на LL (*) с большим количеством эмпирических данных.

Answer 2

Если вам нужно передать код один, рекурсивное спускание (LL) - это то, что вы можете сделать реалистично;люди не могут создавать парсеры L (AL) R вручную практически вручную.

Учитывая, что современные генераторы парсеров будут обрабатывать все конструкции парсера для вас, и это пространство не является большой проблемой, я предпочитаю парсеры LR, потому чтовам не нужно так много сражаться с грамматиками, чтобы сделать их действительными для вашего конкретного генератора синтаксического анализатора (нет глупости "удалить всю левую рекурсию").

На самом деле, я предпочитаю анализаторы GLR , который в значительной степени будет анализировать что угодно с контекстно-свободной грамматикой.Никаких левых рекурсий.Нет сдвига / уменьшить беспокойство конфликта.Нет предельных ограничений.

Если вы хотите увидеть диапазон языков, с которыми может работать один механизм синтаксического анализа GLR (включая язык, который трудно анализировать с использованием LL / LALR, C ++), вы можете посмотреть здесь .

Answer 3

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

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

Answer 4

Сложность синтаксического анализа LL в худшем случае составляет O (n ^ 4), тогда как сложность синтаксического анализа LR в худшем случае лучше, O (n ^ 3).

(Но никто никогда не будет писать O (n ^ 4) грамматика.)

https://en.wikipedia.org/wiki/Top-down_parsing

Answer 5

Единственное преимущество, с которым я когда-либо был знаком, - это то, что вы можете легко кодировать парсеры LL вручную.Парсеры LR НАМНОГО сложнее кодировать вручную (вы обычно используете генератор парсеров).

Answer 6

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