Лексический анализатор/синтаксический анализатор, чтобы сгенерировать код Scala от грамматики BNF
Я в настоящее время ищу лексический анализатор/синтаксический анализатор, который генерирует код Scala от грамматики BNF ( ocamlyacc файл с приоритетом и ассоциативностью). Я вполне смущен, так как я почти ничего не нашел о том, как сделать это.
Для парсинга я нашел scala-bison (что я испытываю много затруднений для работы с). Все другие инструменты являются просто синтаксическими анализаторами Java, импортированными в Scala (как ANTLR).
Для lexing я ничего не нашел.
Я также нашел известный синтаксический анализатор combinators Scala, но (исправьте меня, если я неправ), даже если они являются довольно привлекательными, они используют много времени и памяти, главным образом из-за отслеживания в обратном порядке.
Таким образом, у меня есть два основных вопроса:
- Почему люди, только кажется, концентрируются на _parser combinators?
- Что Ваше лучшее предложение лексического анализатора/парсера-генератора состоит в том, чтобы использовать с Scala?
2 ответа
Как один из авторов статьи ScalaBison, я несколько раз сталкивался с этой проблемой. :-) Для сканирования в Scala я обычно использую JFlex . Он на удивление хорошо работает со ScalaBison, и все наши тесты производительности проводились с использованием этой комбинации. Прискорбным недостатком является то, что он генерирует исходные коды Java, и поэтому компиляция требует некоторой гимнастики. Я полагаю, что Джон Бойленд (главный автор статьи) разработал режим вывода Scala для JFlex, но я не думаю, что он был выпущен публично.
Для собственной разработки я много работал с методами разбора без сканирования. Комбинаторы синтаксического анализатора packrat в Scala 2.8 довольно хороши, хотя до сих пор не являются обобщенными. Я построил экспериментальную библиотеку , которая реализует обобщенный синтаксический анализ в рамках структуры комбинатора синтаксического анализатора. Его асимптотические границы намного лучше, чем у традиционных комбинаторов синтаксического анализатора, но на практике накладные расходы на постоянное время выше (я все еще работаю над этим).
В Scala 2.8 есть парсер packrat. Цитирую из документации API здесь:
Packrat Parsing - это техника для реализации обратного обхода, рекурсивно-восходящего синтаксического анализатора, с тем преимуществом которой является то, что она гарантирует неограниченный и линейное время разбора. Используя эту технику, левые рекурсивные грамматики также могут быть приняты.