Лучший генератор парсера для разбора множества маленьких текстов на C++?

Я, по соображениям производительности, портирую библиотеку C# на C++. Во время нормальной работы этой библиотеке, помимо прочего, необходимо проанализировать около 150 000 математических выражений (например, формул Excel) со средней длиной менее 150 символов.

В версии C# я использовал GOLD-парсер для генерации кода разбора. Он может анализировать все 150 000 выражений за одну секунду.

Поскольку мы думали о расширении нашего языка, я подумал, что переход на C++ может быть хорошим шансом перейти на ANTLR. Я перенес (простую) грамматику в ANTLR и сгенерировал код C из нее. Анализ 150 000 выражений занимает более 12 секунд, потому что для каждого выражения мне нужно создать новый ANTL3_INPUT_STREAM, поток токенов, лексер и анализатор - по крайней мере, в версии 3.4 нет способа их повторного использования.

Я был бы благодарен, если бы кто-то мог дать мне рекомендацию, что использовать вместо этого - GOLD, конечно, вариант, хотя генерация кода C++ или C кажется намного более сложной, чем разнообразие C#. Моя грамматика совместима с LALR и LL(1). Первостепенной задачей является анализ производительности на небольших входах.

Источник

6 ответов

Решение

Я бы попробовал boost::spirit. Это часто очень быстро (даже для анализа простых вещей, таких как целое число, это может быть быстрее, чем функция C atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html)

http://boost-spirit.com/home/

У него есть хорошие вещи: только заголовок, так что ад зависимости, либеральная лицензия.

Однако следует помнить, что кривая обучения сложна. Это современный C++ (без указателя, но с большим количеством шаблонов и очень неприятными ошибками компиляции), поэтому, исходя из C или C#, вам может быть не очень удобно.

Источник

Если анализируемая грамматика проста, вы можете просто написать анализатор вручную.

Большинство генераторов синтаксического анализатора разработаны так, чтобы упростить сборку работающего синтаксического анализатора, и в результате время выполнения часто страдает.

Источник

Лучшая производительность, которую я видел при разборе, пришла от Boost.Spirit.Qi, который выражает грамматику в C++ с использованием программирования мета-шаблонов. Это не для слабонервных, хотя.

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

Источник

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

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

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

К вашему сведению, компилятор GCC имеет как минимум собственные синтаксические анализаторы с рекурсивным спуском для C++ и C. Он больше не использует генераторы синтаксического анализатора (такие как Bison или ANTLR).

Источник

Вместо expr заставить вас признать грамматику sequence-of-expr,

РЕДАКТИРОВАТЬ:

Вместо наличия (синтаксис бизонов):

start: expr { process_expr ($1); }
     ;

иметь:

start: expr_seq ;

expr_seq:   expr          { process_expr ($1); }
          | expr_seq expr { process_expr ($2); }
          ;
Источник

Я написал много парсеров, и рекурсивный спуск вручную - это то, как я это делаю. Они просты в написании и в значительной степени оптимальны.

Тем не менее, если вам нужна скорость, независимо от того, что вы пишете, у вас будет достаточно места для ее ускорения. Это будет таким образом, что может вас удивить, потому что все, о чем вы могли подумать, вы бы уже сделали.

Вот набор слайдов, показывающий, как это сделать.

Источник
Другие вопросы по тегам