Преимущества Antlr (скажем, lex/yacc/bison)
В прошлом я использовал lex и yacc (чаще всего bison) для различных проектов, обычно для переводчиков (например, подмножество EDIF, передаваемого в приложение EDA). Кроме того, мне пришлось поддерживать код, основанный на грамматиках lex/yacc, датируемых десятилетиями. Так что я разбираюсь в инструментах, хотя я не эксперт.
В прошлом я видел положительные отзывы об Antlr на разных форумах, и мне любопытно, чего мне не хватает. Так что, если вы использовали оба, пожалуйста, скажите мне, что лучше или лучше в Antlr. Мои текущие ограничения заключаются в том, что я работаю в магазине C++, и любой поставляемый нами продукт не будет включать Java, поэтому полученные парсеры должны будут следовать этому правилу.
5 ответов
Одним из основных отличий является то, что 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 правила являются леворекурсивными. Это дает гораздо более эффективную AST, когда наступает время для генерации кода, потому что это устраняет необходимость в нескольких регистрах и ненужном разливе (левое дерево может быть свернуто, тогда как правое дерево не может).
С точки зрения личного вкуса, я думаю, что грамматики LALR намного проще создавать и отлаживать. Недостатком является то, что вам приходится иметь дело с несколько загадочными ошибками, такими как shift-Reduce и (страшно) Reduce-Reduce. Это ошибки, которые обнаруживает Bison при создании анализатора, поэтому это не влияет на работу конечного пользователя, но может сделать процесс разработки более интересным. Именно по этой причине ANTLR считается более простым в использовании, чем YACC/Bison.
Наиболее существенное различие между YACC/Bison и ANTLR заключается в типе грамматик, которые могут обрабатывать эти инструменты. YACC / Бизон обрабатывает грамматики LALR, ANTLR обрабатывает грамматики LL.
Часто людям, которые долгое время работали с грамматикой LALR, будет труднее работать с грамматикой LL, и наоборот. Это не означает, что с грамматикой или инструментами сложнее работать. Какой инструмент вы найдете более простым в использовании, в основном сводится к знакомству с типом грамматики.
Что касается преимуществ, то есть аспекты, где грамматики LALR имеют преимущества перед грамматиками LL, и есть другие аспекты, где грамматики LL имеют преимущества перед грамматиками LALR.
YACC/Bison генерируют парсер, управляемый таблицами, что означает, что "логика обработки" содержится в данных программы парсера, а не в коде парсера. Окупаемость заключается в том, что даже синтаксический анализатор для очень сложного языка имеет сравнительно небольшой объем кода. Это было более важно в 1960-х и 1970-х годах, когда аппаратное обеспечение было очень ограничено. Генераторы парсеров, управляемых таблицами, уходят в эту эпоху, и в то время основным требованием был небольшой объем кода.
ANTLR генерирует синтаксические анализаторы с рекурсивным спуском, что означает, что в коде синтаксического анализатора содержится "логика обработки", поскольку каждое производственное правило грамматики представлено функцией в коде синтаксического анализатора. Окупаемость заключается в том, что легче понять, что делает парсер, читая его код. Кроме того, парсеры рекурсивного спуска обычно работают быстрее, чем таблицы. Однако для очень сложных языков объем кода будет больше. Это было проблемой в 1960-х и 1970-х годах. В то время только относительно небольшие языки, такие как, например, Pascal, были реализованы таким образом из-за аппаратных ограничений.
Сгенерированные ANTLR парсеры обычно находятся в пределах 10000 строк кода и более. Рукописные парсеры рекурсивного спуска часто находятся на одной площадке. Компилятор Wirth's Oberon, пожалуй, самый компактный, с примерно 4000 строками кода, включая генерацию кода, но Oberon - это очень компактный язык, содержащий всего около 40 правил производства.
Как уже указывалось, большой плюс для ANTLR - это графический инструмент IDE, который называется ANTLRworks. Это полная лаборатория грамматики и языкового дизайна. Он визуализирует ваши грамматические правила по мере их ввода, и, если он обнаружит какие-либо конфликты, он наглядно покажет вам, что это за конфликт и что его вызывает. Он может даже автоматически рефакторировать и разрешать конфликты, такие как левая рекурсия. Если у вас есть бесконфликтная грамматика, вы можете позволить ANTLRworks разобрать входной файл на вашем языке, построить для вас дерево разбора и AST и графически отобразить дерево в IDE. Это очень большое преимущество, потому что оно может сэкономить вам много часов работы: вы обнаружите концептуальные ошибки в вашем языковом дизайне, прежде чем начнете кодировать! Я не нашел такого инструмента для грамматики LALR, кажется, такого инструмента нет.
Даже для людей, которые не хотят генерировать свои парсеры, а пишут их вручную, ANTLRworks - отличный инструмент для разработки и создания прототипов языка. Вполне возможно, лучший такой инструмент доступен. К сожалению, это не поможет вам, если вы хотите создавать парсеры LALR. Переключение с LALR на LL просто для того, чтобы воспользоваться преимуществами ANTLRworks, может быть целесообразным, но для некоторых людей переключение типов грамматики может быть очень болезненным. Другими словами: YMMV.
Пара преимуществ для ANTLR:
- может выводить парсеры на разных языках - Java не требуется для запуска сгенерированного парсера.
- Удивительный графический интерфейс облегчает отладку грамматики (например, вы можете увидеть сгенерированные права AST в графическом интерфейсе, дополнительные инструменты не требуются)
- Сгенерированный код на самом деле удобочитаем для человека (это одна из целей ANTLR), и тот факт, что он генерирует LL-парсеры, безусловно, помогает в этом отношении.
- определение терминалов также не зависит от контекста (в отличие от регулярного выражения в (f)lex), что позволяет, например, определять терминалы, содержащие правильно закрытые скобки
Мой.02$
Еще одним преимуществом ANTRL является то, что вы можете использовать ANTLRWORKS, хотя я не могу сказать, что это строгое преимущество, поскольку могут быть аналогичные инструменты и для других генераторов.
- В результате Bison и Flex занимают меньше памяти, но у вас нет графической среды IDE.
- antlr использует больше памяти, но у вас есть antlrworks, графическая IDE.
Использование памяти Bison/Flex обычно составляет мегабайт или около того. Сравните это с antlr - предполагая, что он использует 512 байт памяти для каждого токена в файле, который вы хотите проанализировать. 4 миллиона токенов, и вам не хватает виртуальной памяти в 32-битной системе.
Если файл, который вы хотите проанализировать, большой, у antlr может не хватить памяти, поэтому, если вы просто хотите проанализировать файл конфигурации, это будет жизнеспособным решением. В противном случае, если вы хотите проанализировать файл с большим количеством данных, попробуйте Bison.