Достаточно ли комбинаторов парсера Scalas / Haskells?

Question

Мне интересно, достаточно ли комбинаторов парсера Scalas / Haskells для синтаксического анализа языка программирования. Конкретнее язык MiniJava. В настоящее время я читаю конструкцию компилятора, и jflex и java cup довольно болезненно работать, поэтому мне интересно, могу ли я вместо этого использовать / должен использовать комбинаторы парсеров. Синтаксис MiniJava очень маленький. MiniJavas BNF: http://www.cambridge.org/us/features/052182060X/grammar.html

Answer 1

Я никогда не использовал Scala, но наличие окончательного BNF делает это легко.

Простой перевод на Haskell Text.ParserCombinators.Parsec :

goal = do c <- mainClass
          cs <- many classDeclaration
          eof
          return $ c:cs
mainClass = do token "class"
               name <- identifier
               ...

и т.д.. Перевод PArrows тоже довольно тривиален. Возможно, вам будет проще иметь четкую фазу лексинга перед парсером, но вы можете обойтись и без нее.

Answer 2

Я использую синтаксические анализаторы Scala для анализа PL / SQL-кода, это работает как шарм.

Answer 3

По крайней мере, в Parsec есть встроенный лексер для Java-подобных языков:

lexer = makeTokenParser javaStyle

Вы должны определить зарезервированные слова самостоятельно.

Answer 4

Синтаксический анализатор Scala является анализатором обратного отслеживания, поэтому он может работать практически с любым BNF или EBNF. Это также означает, однако, что существуют крайние случаи, когда ввод может быть мучительно медленным для чтения.

Если грамматику можно изменить на LL (1) грамматику , вы можете использовать ~! оператор, чтобы сохранить возврат к минимуму.

Грамматика, вероятно, МОЖЕТ быть превращена в LL (1), но, как написано, это не так. Посмотрите, например, что у выражений и операторов есть конфликты первый / первый (посмотрите в конце связанной статьи).

Во всяком случае, для академического проекта этого достаточно. Для реального компилятора вам понадобятся более быстрые парсеры.

Answer 5

Программирование в Scala (стр. 647) говорит:

Это [каркас синтаксического анализатора Scala] гораздо легче понять и адаптировать, чем генератор синтаксического анализатора, и разница в скорости часто не имеет значения на практике, если вы не хотите анализировать очень большие входные данные.

Поскольку я бы не классифицировал исходный код как очень большой ввод (в идеале), этого должно быть достаточно.

Answer 6

Я не имел дело с библиотеками комбинатора синтаксического анализатора Scala или Haskell, но похоже, что грамматика должна быть в порядке.