Комбинаторы синтаксического анализатора Scala против синтаксического анализатора, сгенерированного ANTLR / Java?

Я пишу синтаксический анализатор выражений для приложения, написанного в основном на Scala. Я построил объекты AST на Scala, и теперь мне нужно написать парсер. Я слышал о встроенных комбинаторах синтаксического анализатора Scala, а также об ANTLR3, и мне интересно: что обеспечит лучшую производительность и простоту написания кода? Уже:

Профи ANTLR

  1. Хорошо известный
  2. Быстрый
  3. Внешний DSL
  4. ANTLRWorks (отличная IDE для отладки / тестирования парсера грамматики)

Минусы ANTLR

  1. На основе Java (взаимодействие со Scala может быть проблематичным, есть опыт?)
  2. Требуется большая зависимость во время выполнения

Плюсы синтаксического комбинатора

  1. Часть Scala
  2. На один шаг сборки меньше
  3. Нет необходимости в зависимости от времени выполнения; например уже включен в библиотеку времени выполнения Scala

Минусы синтаксического комбинатора

  1. Внутренний DSL (может означать более медленное выполнение?)
  2. Нет ANTLRWorks (предоставляет хорошие функции тестирования парсера и визуализации)

Есть предположения?

РЕДАКТИРОВАТЬ: этот синтаксический анализатор выражений анализирует алгебраические / математические выражения. Он будет использоваться в приложении Magnificalc для Android, когда оно будет завершено.


java parsing scala parser-combinators antlr3
person Nathan Moos    schedule 15.05.2011    source источник
comment
У меня нет опыта работы со Scala (и, следовательно, с комбинаторами синтаксического анализатора), поэтому я не могу дать рекомендации. Но для людей, которые имеют опыт в обоих направлениях, вы можете объяснить, на что способен (будет) ваш синтаксический анализатор выражений: поддерживает ли он области видимости переменных или какие-то классы / структуры? Объявления функций? ...   -  person Bart Kiers    schedule 16.05.2011
comment
Почему вы считаете использование внутреннего DSL мошенничеством?   -  person Jens Schauder    schedule 16.05.2011
comment
@Jens, потому что это может замедлить выполнение. Знаете ли вы что-нибудь о производительности предварительно скомпилированного по сравнению с внутренним DSL? Я был бы рад это услышать.   -  person Nathan Moos    schedule 17.05.2011
comment
Нет информации о производительности. Вы имеете в виду производительность получившегося парсера? Или производительность шага генерации парсера? Для первого внутреннего и внешнего не имеет значения. Во втором случае я бы ожидал, что внутренний DSL будет быстрее, поскольку его не нужно анализировать перед интерпретацией. / * здесь немного меты * /   -  person Jens Schauder    schedule 18.05.2011

Ответы (6)


arrow_upward
17
arrow_downward

Комбинаторы синтаксического анализатора Scala не очень эффективны. Они не были созданы для этого. Они хороши для выполнения небольших задач с относительно небольшими затратами.

Так что это действительно зависит от ваших требований. Проблем с взаимодействием с ANTLR быть не должно. Вызов Scala из Java может быть непростым делом, но вызов Java из Scala почти всегда работает.

person Erik Engbrecht    schedule 15.05.2011
comment
Я пробовал это, и это работает очень хорошо. Он также хорошо работает с case-классами Scalas (как и JFlex / JavaCup, кстати :-) - person aioobe; 16.05.2011
comment
Моя проблема в том, что мои объекты AST находятся исключительно в Scala ... есть ли способ вызвать эти объекты в анализаторе ANTLR? - person Nathan Moos; 17.05.2011
comment
Если вы хотите вызвать Scala из Java и чтобы он выглядел красиво, ваш Scala не может полагаться на специфичные для Scala языковые функции, такие как неявные преобразования, неявные аргументы, аргументы по умолчанию, символьные имена методов, параметры по имени и т. Д. также остается относительно простым. Если ваши объекты Scala относительно просты, проблем с их использованием из Java возникнуть не должно. - person Erik Engbrecht; 21.05.2011

arrow_upward
6
arrow_downward

Я бы не стал беспокоиться об ограничениях производительности комбинаторов синтаксического анализатора, если только вы не планировали анализировать алгебраические выражения длиной в несколько страниц. В книге Programming Scala упоминается, что возможна более эффективная реализация комбинаторов синтаксического анализатора. Может быть, кто-нибудь найдет время и силы написать его.

Я думаю, что с ANTLR вы говорите о двух дополнительных шагах сборки: ANTLR компилируется в Java, и вам нужно скомпилировать как Scala, так и Java в байт-код, а не только Scala.

person sullivan-    schedule 17.05.2011
comment
Дополнительный этап сборки не должен быть проблемой для меня, я использую Maven. - person Nathan Moos; 19.05.2011

arrow_upward
2
arrow_downward

Я создал внешние DSL с комбинаторами синтаксического анализатора ANTLRv4 и Scalas, и я явно предпочитаю комбинаторы синтаксического анализатора, потому что вы получаете отличную поддержку редактора при разработке языка, и очень легко преобразовать результаты анализа в любую структуру данных класса AST. Разработка грамматик ANTLR занимает гораздо больше времени, потому что даже при поддержке редактора ANTLRWorks разработка грамматик очень подвержена ошибкам. Весь рабочий процесс ANTLR кажется мне довольно раздутым по сравнению с рабочим процессом комбинаторов синтаксического анализатора.

person Hannes John    schedule 24.12.2015

arrow_upward
0
arrow_downward

Я был бы склонен попробовать создать внешний DSL, используя комбинаторы синтаксического анализатора. Это не обязательно должен быть внутренний DSL. Но не знаю, что было бы лучше.

Лучший способ выяснить это - взять упрощенную версию грамматики, попробовать ее в обоих направлениях и оценить различия.

person Don Roby    schedule 15.05.2011
comment
Под внутренним DSL я имел в виду, что определение грамматики - это внутренний DSL. - person Nathan Moos; 16.05.2011

arrow_upward
0
arrow_downward

Только что писал парсер для домашнего 8-битного ассемблера ЦП.

Я так далеко зашел с Antlr4, прежде чем почувствовал, что должен быть способ получше. Я решил попробовать комбинаторы синтаксического анализатора Scala и должен сказать, что это намного продуктивнее, ИМХО. Однако я знаю scala.

person johnlon    schedule 11.11.2020

arrow_upward
0
arrow_downward

Если вас все еще интересует парсер целочисленных выражений, взгляните на мой пример интерпретатора здесь: https://github.com/scala-szeged/hrank-while-language. Это 200-строчный код Scala, использующий комбинаторы синтаксического анализатора officail. Имеет синтаксический анализ выражений. Он также обрабатывает вложенные if, вложенные while, переменные и логические выражения. Я также реализовал обработку массивов в этом репозитории github. Если вам нужна обработка строк, я тоже могу вам помочь.

Другой, несколько более простой синтаксический анализатор выражений также присутствует в моем другом общедоступном репозитории https://github.com/scala-szeged/top-calc-dsl

person jseteny    schedule 31.03.2021