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

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

Согласно Wikipedia, анализ LR имеет преимущества перед LL:

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

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

Ответ 1

GLR великолепно, если вы хотите разделить дерево/лес и не возражать против черных ящиков. Он позволяет вам вводить любые CFG, которые вы хотите за счет проверки двусмысленностей во время разбора посредством исчерпывающего тестирования вместо того, чтобы разрешать LR/LALR конфликтует статически. Некоторые говорят, что хороший компромисс. Инструмент Ira Baxter DMS или Elkhound, который имеет свободную грамматику С++, полезны для этого класса проблем. ANTLR полезен и для большого класса языковых приложений, но использует подход сверху вниз, генерируя паркуры рекурсивного спуска, называемые LL (*), которые допускают семантические предикаты. Я приведу здесь без доказательства, что предикаты позволяют вам анализировать контекстно-зависимые языки вне CFG. Программистам нравится вставлять действия в грамматики, такие как хорошая обработка ошибок, и как одноэтапная отладка. LL хорош во всех трех. LL - это то, что мы делаем вручную, чтобы было легче понять. Не верьте глупости википедии о том, что LR лучше справляется с ошибками. Тем не менее, если вы много возвращаетесь с ANTLR, ошибки действительно хуже с LL (*) (у PEGs есть эта проблема).

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

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

ANTLR AN другой T ool для L ang R. anti-LR, но мне это тоже нравится;)

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

Ответ 2

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

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

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

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

Ответ 3

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

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

Ответ 4

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

Ответ 5

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