GLR отлично подходит, если вы хотите дерево / лес синтаксического анализа и не возражаете против черных ящиков. Он позволяет вам вводить любой CFG, который вы хотите, на стоимость проверки на неоднозначность во время синтаксического анализа посредством исчерпывающего тестирования вместо статического разрешения конфликтов LR / LALR. Некоторые говорят, что это хороший компромисс. Инструмент Иры Бакстера DMS или Elkhound, который имеет бесплатную грамматику C ++, полезен для этого класса задач. ANTLR также полезен для большого класса языковых приложений, но использует нисходящий подход, генерируя синтаксические анализаторы с рекурсивным спуском. называется LL (*), что позволяет использовать семантические предикаты. Здесь я без доказательства заявлю, что предикаты позволяют анализировать контекстно-зависимые языки помимо CFG. Программистам нравится вставлять действия в грамматики, например, хорошо обрабатывать ошибки и выполнять пошаговую отладку. LL хорош по всем трем. 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 другой инструмент для распознавания L и R, а не анти-LR. , но он мне тоже нравится;)
Честно говоря, как и многие молодые программисты 80-х, я не понимал LALR и не любил черные ящики (теперь я копаю красоту движка GLR, но все же предпочитаю LL). Я построил коммерческий компилятор на основе LL (k) и решил создать инструмент для генерации того, что я построил вручную. ANTLR не для всех, и такие крайние случаи, как C ++, могут быть лучше обработаны с помощью GLR, но многие люди считают, что ANTLR подходит для их зоны комфорта. С января 2008 года было 134 000 загрузок двоичного файла jar ANTLR в рамках ANTLRWorks, а общее количество исходных zip-архивов (по данным Google Analytics). См. нашу статью по LL (*) с большим количеством эмпирических данных.
person
Terence Parr
schedule
04.11.2010
