Лексер / парсер для генерации кода Scala из грамматики BNF

Question

В настоящее время я ищу лексер / парсер, который генерирует код Scala из грамматики BNF (файл ocamlyacc с приоритетом и ассоциативностью). Я совершенно сбит с толку, поскольку почти ничего не нашел о том, как это сделать.

Для разбора я нашел scala-bison (с которым у меня много проблем при работе). Все остальные инструменты - это просто парсеры Java, импортированные в Scala (например, ANTLR).

Для лексинга я ничего не нашел.

Я также нашел знаменитые комбинаторы парсеров из Scala, но (поправьте меня, если я ошибаюсь), даже если они довольно привлекательны, они занимают много времени и памяти, в основном из-за возвраты .

Итак, у меня есть два основных вопроса:

• Почему люди, кажется, концентрируются только на _parser комбинаторах?
• Какое ваше самое лучшее предложение лексера / генератора синтаксических анализаторов для использования с Scala?

Answer 1

Как один из авторов статьи о ScalaBison, я сталкивался с этой проблемой несколько раз.:-) Для сканирования в Scala я обычно использую JFlex .Он работает на удивление хорошо со ScalaBison, и все наши тесты были выполнены с использованием этой комбинации.К сожалению, недостатком является то, что он генерирует исходные коды Java, поэтому для компиляции требуется немного гимнастики.Я считаю, что Джон Бойленд (основной автор статьи) разработал режим вывода Scala для JFlex, но я не думаю, что он был опубликован.

Для моей собственной разработкиЯ много работал с техникой разбора без сканера.Пакетные парсин-комбинаторы Scala 2.8 довольно хороши, хотя и не обобщены.Я создал экспериментальную библиотеку , которая реализует обобщенный анализ в рамках комбинатора синтаксического анализатора.Его асимптотические границы намного лучше, чем у традиционных комбинаторов синтаксического анализа, но на практике постоянные затраты времени выше (я все еще над этим работаю).

Answer 2

Я знаю, что этот вопрос старый, но для тех, кто все еще ищет генератор лексеров, который выводит код Scala, я написал форк JFlex, который испускает Scala , а не Java, включая соответствующий Mavenи плагины sbt.Все они теперь доступны на Maven Central.

В настоящее время мы используем его (в том числе плагины Maven / sbt) для токенизации английского текста как части линии обработки естественного языка в FACTORIE - пример .flex файла, содержащего Scala здесь .

Answer 3

Scala 2.8 имеет синтаксический анализатор пакетов.Я цитирую здесь документы по API:

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