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

Question

По соображениям производительности я портирую библиотеку 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).Первостепенной задачей является анализ производительности на небольших входах.

Answer 1

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

http://boost -spirit.com / дома /

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

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

Для вашей информации, компилятор GCC имеет как минимум свои собственные парсеры рекурсивного спуска для C ++ & C.Он больше не использует генераторы парсеров (например, bison или ANTLR ).

Answer 5

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

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

Answer 6

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

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

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

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

есть:

start: expr_seq ;

expr_seq:   expr          { process_expr ($1); }
          | expr_seq expr { process_expr ($2); }
          ;