Преимущества Antlr (скажем, lex / yacc / bison) [закрыто]

143

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

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

Дон Уэйкфилд
источник

Ответы:

145

Обновление / предупреждение: этот ответ может быть устаревшим!


Одно из основных отличий состоит в том, что 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.

Даниэль Спивак
источник
2
Итак, большое, возможно, единственное преимущество Antlr в вашем восприятии состоит в том, что он генерирует меньше ошибок, таких как sr и rr, на этапе строительства? Я ожидаю, что попробую, но, вероятно, в конечном итоге буду придерживаться того, что знаю ...
Дон Уэйкфилд,
1
Да, вот и все. :-) Я тоже не совсем согласен с распространенным мнением, что ANTLR проще, чем Bison, поэтому я думаю, что согласился бы с вашим решением.
Даниэль Спивак
2
Нужно ли правилу 'facts' второе правило, чтобы указать, что простой 'expr' является фактическим? В противном случае, хорошее объяснение.
Джонатан Леффлер
8
Другой комментарий, который я недавно обнаружил, хотя ему было десятилетие, дает разумное наблюдение за результатами : compilers.iecc.com/comparch/article/98-11-040 : «ANTLR / PCCTS - это LL, что затрудняет написание грамматики, но сгенерированный код читабелен. Yacc, будучи LALR (конечно, вы это знаете), облегчает написание грамматики, но сгенерированный код также может быть иероглифическим. "
Дон Уэйкфилд
72
Я только что завершил немедленную поддержку левой рекурсии для следующего выпуска ANTLR v3.4. Обрабатывает правила выражения LR и подобные вещи, такие как правила C-объявления. :)
Теренс Парр
117

Наиболее существенным отличием YACC / Bison от ANTLR является тип грамматики, которую могут обрабатывать эти инструменты. YACC / Бизон обрабатывает грамматики LALR, ANTLR обрабатывает грамматики LL.

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

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

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

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

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

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

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

trijezdci
источник
4
нравится, потому что он объясняет историю, стоящую за различными механизмами, которые сразу же делают людей понятными
zinking
35

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

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

Мой .02 $

Кристиан Дьяконеску
источник
9

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

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

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

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

просто я
источник
7
Мне любопытно. Можете ли вы указать на документацию, описывающую потребление 512 байт памяти на один токен? Я не помню, чтобы видел эту дискуссию. Мой выбор ключевых слов Google также не приносит мне удовлетворения ...
Дон Уэйкфилд
2
Вы говорите об объеме памяти генератора парсера при генерации синтаксического анализатора или говорите об объеме памяти сгенерированного синтаксического анализатора при синтаксическом анализе ввода для исходного языка? Миллионы токенов в грамматике были бы абсолютно безумными. Вы должны быть заперты в психиатрической больнице, если вы серьезно пытались продать такую ​​идею. Что касается входных файлов для самого синтаксического анализатора, могут быть случаи, когда в них может быть чрезвычайно большое количество токенов, но большинство языков являются модульными, вы не анализируете весь ввод в одном файле, отдельные модули меньше.
trijezdci