воскресенье, 9 ноября 2008 г.

Выбор языка и фреймворка для БНФ парсера.

Возникла задачка написать парсер для потоковых данных, причем писать парсер можно было либо на .Net, либо на С++. Грамматика входных данных сложная, в данных могут быть ошибки...

На С++, наверное, оптимальным выбором был бы Spirit фреймворк из Boost. Запробовав парочку простых примеров, я пересмотрела еще некоторые посложнее и поняла, что если начинать БНФ-писать парсер на С++, то начинать надо с использованием этого фреймворка.

С .Net оказалось несколько сложнее, но тоже возможно. Существует порт Spirit'а Spart Parser Framework for .Net. Правда, это не совсем полный порт, но для данной задачи его бы хватило.

Для сравнения, приведу пример описания грамматик в обоих фреймворках для калькулятора.

Исходная БНФ-грамматика:

group ::= '(' expression ')'
factor ::= integer | group
term ::= factor (('*' factor) | ('/' factor))*
expression ::= term (('+' term) | ('-' term))*


Описание на Spirit:

group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));


Описание на Spart:

group.Parser = Ops.Seq('(',Ops.Seq(expression,')'));
factor.Parser = integer | group;
term.Parser = Ops.Seq( factor, Ops.Klenee(
Ops.Seq('*',factor) | Ops.Seq('/',factor) ));
expression.Parser = Ops.Seq(term,Ops.Klenee(Ops.Seq('+',term) |
Ops.Seq('-',term) ))


Оба фреймворка по понятным причинам похожи и при использовании в примерах не было выявлено особых преимуществ у какого-либо одного фреймворка перед другим.
Далее уже надо выбирать по производительности каждого из них (может дойдут руки сравнить), по трудозатратам на проект и другим аспектам.

PS. Задачка на неопределенное время отошла на задний план, поэтому интерес к вопросу сугубо теоретический. Если до дела все-таки дойдет, то постараюсь отписаться поконкретнее об использовании фреймворков на практике.

9 комментариев:

Yuri Volkov комментирует...

я как то пользовался flex+bison для решения подобных задач. В целом остался доволен.

Omega комментирует...

Распространенное решение, но меня вот это несколько обескуражило:

"Note that Flex is seriously out-of-date on Windows when it comes to generating C++ scanners. Recent Flex versions which are able to generate ISO C++ scanners do not support Win32 (MinGW or VS), so you're probably better of trying to generate a C scanner and call it from C++."
(Отсюда: http://stackoverflow.com/questions/226820/how-do-you-compile-gnu-flex-in-visual-studio-20052008)

Yuri Volkov комментирует...

единственная проблема, которая может возникнуть - это собрать бинарник flex под win32. А приведенное замечание противоречит ИМХО самому себе. ISO C++ - никак не зависит от платформы. Что значит "do not support Win32 (MinGW or VS)"? Не интегрируется с процессом сборки? не собирается сам flex под win32? или не собирается сгенерированный им код (чего не должно быть в виду ISO C++). Doxygen к стати использует его и файлы проектов для VS есть и с процессом сборки проекта генерация парсера интегрирована. В общем высказанное мнение по ссылке вызывает у меня большие сомнения.

С другой стороны boost может оказаться хорошим решением правда я не знаю как у него обстоят дела с перфомансом.

Alena комментирует...

А lex и yacc не подойдут?

Yuri Volkov комментирует...

ну lex & yacc сейчас по большому счету если брать линукс то это всего лишь обертки над flex & bison ;-). В BSD & Solaris это по моему не так.

Omega комментирует...
Этот комментарий был удален автором.
Omega комментирует...

По ссылке, как я поняла, речь о проблемах с компиляцией сгенеренного С++ парсера.

Меня смущает сам подход (в смысле, что с flex программист парсер генерит, а при помощи spirit - пишет) и связанные с ним потенциальные проблемы - вопросы совместимости с компиляторами и поддержки кода.

С компиляторами еще ладно, я тоже не думаю, что само по себе это фатально, может просто вопрос опций компиляции, все-таки действительно пишут про стандарт.

С поддержкой - такой есть момент, если для добавления небольшого нового функционала библиотека будет перегенериться заново, черт его знает.. как-то непонятно, что делать с уже внесенными изменениями в коде, если они были. Постоянные перепроверки всего при перегенерации.. Т.е. конечно можно и так, но что-то мне подсказывает, что это - подход для реальных компиляторов, с известной и редко изменяемой грамматикой. А для нашей задачи - это уже "из пушки по воробьям", тут просто хотелось избежать ручного труда, не более того.

Про перфоманс, авторы spirit пишут, что он медленее yacc, но они уже обещают spirit-2, который будет приближаться. (ссылку потом дам, на этом компе у меня нет).

Sergey Semenov комментирует...

Я бы посмотрел в сторону Coco/R.

Omega комментирует...

Посмотрела, спасибо. Отписалась в вашей заметке об анализаторах...