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

StackOverflow https://stackoverflow.com/questions/212900

  •  03-07-2019
  •  | 
  •  

Вопрос

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

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

Это было полезно?

Решение

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

<Ч>

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

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

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

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

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

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

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

Другие советы

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

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

Что касается преимуществ, то есть аспекты, где грамматики 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.

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

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

Мой .02$

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

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

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

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top