Scala парсеры: доступность, различия и объединение? - PullRequest
25 голосов
/ 12 декабря 2010

Мой вопрос о парсерах Scala:

  • Какие из них доступны (в стандартной библиотеке и за ее пределами),
  • какая разница между ними,
  • у них общий API и
  • Можно ли комбинировать разные парсеры для разбора одной входной строки?

Я нашел по крайней мере эти:

  • "Стандартный" синтаксический анализатор Scala (кажется, LL-анализатор)
  • Scala's Packrat parser (начиная с 2.8, это LALR-парсер)
  • Parboiled parser (PEG parser?)
  • синтаксический анализатор Spiewak's GLL комбинатор

Ответы [ 4 ]

12 голосов
/ 15 декабря 2010

Существует также реализация Дэном Спиваком GLL-синтаксических анализаторов .

11 голосов
/ 06 февраля 2012

Стоит отметить, что стандартные комбинаторы парсера Scala не являются ни LL, ни комбинаторами Packrat LALR. Комбинаторы Parser - это форма рекурсивного спуска с бесконечным возвратом. Вы можете думать о них как «LL (*)». Класс языков, поддерживаемых этой техникой, является в точности классом однозначных контекстно-свободных языков или тем же классом, что и LALR (1) и Packrat. Однако класс грамматика немного отличается, при этом наиболее заметным недостатком является отсутствие поддержки левой рекурсии.

Packrat комбинаторы do поддерживают левую рекурсию, но они по-прежнему не поддерживают многие другие, более тонкие функции LALR. Эта слабость обычно проистекает из упорядоченного оператора выбора, который может привести к дьявольски хитрым ошибкам грамматики, а также препятствует определенным хорошим грамматическим формулировкам. Наиболее часто встречающийся пример этих ошибок возникает, когда вы случайно заказываете неоднозначные варианты выбора как самые короткие, что приводит к жадному совпадению, которое препятствует попыткам правильной ветвления. У LALR нет этой проблемы, поскольку он просто пробует все возможные ветки одновременно, откладывая точку принятия решения до конца производства.

8 голосов
/ 06 февраля 2012

Существует также новый подход, известный как "разбор с производными".Подход описан здесь .Существует реализация в Scala от Daniel Spiewak.

4 голосов
/ 10 марта 2014

Просто хотел обновить этот ответ указателем на последнюю итерацию пропаренного проекта под названием parboiled2:

https://github.com/sirthias/parboiled2

parboiled2 предназначается только для Scala (в отличие от Scala + Java), использует макросы Scala и поддерживается очень активно.

...