Преимущества Antlr (по сравнению с lex/yacc/bison)

Я использовал lex и yacc (чаще всего bison) в прошлом для разных проектов, обычно переводчиков (например, подмножество EDIF, передаваемого в приложение EDA). Кроме того, мне пришлось поддерживать код на основе грамматик lex/yacc, относящихся к десятилетиям. Поэтому я знаю свой путь вокруг инструментов, хотя я не эксперт.

Я видел положительные отзывы о Antlr на разных форумах в прошлом, и мне любопытно, чего я могу потерять. Поэтому, если вы использовали оба варианта, скажите, пожалуйста, что лучше или более продвинуто в Antlr. Мои текущие ограничения заключаются в том, что я работаю в магазине С++, и любой продукт, который мы отправляем, не будет включать Java, поэтому полученные парсеры должны будут следовать этому правилу.

Ответ 1

Одно существенное отличие состоит в том, что ANTLR генерирует парсер LL (*), тогда как YACC и Bison генерируют парсеры, которые являются LALR. Это важное различие для ряда приложений, наиболее очевидными из которых являются операторы:

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

ANTLR полностью неспособен справиться с этой грамматикой как есть. Чтобы использовать ANTLR (или любой другой генератор парсеров LL), вам нужно будет преобразовать эту грамматику в то, что не является леворекурсивным. Однако у Бизона нет проблем с грамматиками этой формы. Вам нужно будет объявить "+" и "-" как лево-ассоциативные операторы, но это строго не требуется для левой рекурсии. Лучшим примером может быть отправка:

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

Обратите внимание, что правила expr и actuals являются леворекурсивными. Это дает намного более эффективный АСТ, когда наступает время для генерации кода, потому что оно позволяет избежать необходимости в нескольких регистрах и излишнем разливе (дерево с левым склоном может быть свернуто, тогда как дерево с правом наклоном не может).

С точки зрения личного вкуса, я думаю, что LALR-грамматики намного легче создавать и отлаживать. Недостатком является то, что вам приходится иметь дело с несколькими загадочными ошибками, такими как уменьшение сдвига и (страшное) уменьшение-уменьшение. Это ошибки, которые Bison ловит при создании парсера, поэтому он не влияет на опыт конечных пользователей, но может сделать процесс разработки немного более интересным. ANTLR обычно считается более простым в использовании, чем YACC/Bison именно по этой причине.

Ответ 2

Самое существенное различие между YACC/Bison и ANTLR - это тип грамматик, который могут обрабатывать эти инструменты. YACC/Bison обрабатывают грамматики LALR, ANTLR обрабатывает грамматики LL.

Часто люди, которые работали с грамматиками LALR в течение долгого времени, найдут труднее работать с грамматиками LL и наоборот. Это не означает, что грамматикам или инструментам по своей сути труднее работать. Какой инструмент, который вы найдете более простым в использовании, в основном сводится к знакомству с типом грамматики.

Что касается преимуществ, существуют аспекты, в которых грамматики LALR имеют преимущества по сравнению с LL-грамматиками, и есть другие аспекты, где грамматики LL имеют преимущества перед грамматиками LALR.

YACC/Bison генерируют парсинг, управляемый таблицами, что означает, что "логика обработки" содержится в данных программы анализатора, а не в коде парсера. Окупаемость заключается в том, что даже парсер для очень сложного языка имеет относительно небольшой размер кода. Это было более важно в 1960-х и 1970-х годах, когда аппаратное обеспечение было очень ограниченным. Генераторы парсера, приводимые в действие таблицами, восходят к этой эпохе, и тогда было основным требованием к коду.

ANTLR генерирует рекурсивные парсеры спуска, что означает, что "логика обработки" содержится в коде парсера, так как каждое производственное правило грамматики представлено функцией в коде парсера. Окупаемость заключается в том, что легче понять, что делает парсер, читая его код. Кроме того, рекурсивные анализаторы спуска обычно быстрее, чем таблицы. Однако для очень сложных языков размер кода будет больше. Это была проблема в 1960-х и 1970-х годах. В то время, только относительно небольшие языки, такие как Pascal, например, были реализованы таким образом из-за ограничений аппаратного обеспечения.

Созданные ANTLR парсеры обычно находятся в пределах 10.000 строк кода и т.д. Рукописные рекурсивные партизаны спуска часто находятся в одном и том же шаре. Компилятор Wirth Oberon, пожалуй, самый компактный с примерно 4000 строк кода, включая генерацию кода, но Oberon - очень компактный язык с примерно 40 правилами производства.

Как уже указывал кто-то, большим плюсом для ANTLR является графический инструмент IDE под названием ANTLRworks. Это полная лаборатория грамматики и языка. Он визуализирует ваши правила грамматики по мере их ввода, и если он обнаружит какие-либо конфликты, он покажет вам графически, что такое конфликт и что его вызывает. Он может даже автоматически реорганизовывать и разрешать конфликты, такие как левая рекурсия. После того, как у вас есть свободная от конфликта грамматика, вы можете позволить ANTLRworks проанализировать входной файл вашего языка и построить дерево разбора и AST для вас и показать дерево графически в среде IDE. Это очень большое преимущество, поскольку оно может сэкономить вам много часов работы: перед началом кодирования вы обнаружите концептуальные ошибки в своем языковом дизайне! Я не нашел такого инструмента для LALR-грамматик, кажется, что такого инструмента нет.

Даже для людей, которые не хотят генерировать своих парсеров, но передают их код, ANTLRworks - отличный инструмент для языкового дизайна/прототипирования. Вполне возможно, лучший такой инструмент доступен. К сожалению, это не поможет вам, если вы хотите построить партизаны LALR. Переключение с LALR на LL просто для использования ANTLRworks вполне может оказаться полезным, но для некоторых людей переключение типов грамматики может быть очень болезненным. Другими словами: YMMV.

Ответ 3

Пара преимуществ ANTLR:

может выводить парсеры на разных языках - Java не требуется для запуска сгенерированного парсера.
Awesome GUI облегчает отладку грамматики (например, вы можете видеть сгенерированный AST прямо в графическом интерфейсе, без дополнительных инструментов)
Сгенерированный код на самом деле доступен для человека (это одна из целей ANTLR) и тот факт, что он генерирует парсер LL, безусловно, помогает в этом отношении.
определение терминалов также не имеет контекста (в отличие от регулярного выражения в (f) lex), что позволяет, например, определить терминалы, содержащие правильно закрытые круглые скобки

Мой .02 $

Ответ 4

Еще одно преимущество ANTRL заключается в том, что вы можете использовать ANTLRWORKS, хотя я не могу сказать, что это строгое преимущество, так как может быть аналогичные инструменты для других генераторов.

Ответ 5

Bison и Flex приводят к уменьшению объема памяти, но у вас нет графической среды разработки.
antlr использует больше памяти, но у вас есть antlrworks, графическая среда IDE.

Использование памяти Bison/Flex обычно составляет mbyte или около того. Сравните это с antlr - если он использует 512 байт памяти для каждого токена в файле, который вы хотите проанализировать. 4 миллиона токенов, и вы вышли из виртуальной памяти в 32-разрядной системе.

Если файл, который вы хотите разобрать, большой, у antlr может закончиться нехватка памяти, поэтому, если вы просто хотите проанализировать файл конфигурации, это будет жизнеспособным решением. В противном случае, если вы хотите проанализировать файл с большим количеством данных, попробуйте Bison.