Лучший генератор парсеров для разбора большого количества небольших текстов на 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/home/

В нем есть приятные вещи: только заголовок, так что ад зависимостей, либеральная лицензия.

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

Answer 2

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

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

Answer 3

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

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

Answer 4

If the syntax of your expression is simple enough, consider making a hand-written recursive descent parser. It can run really fast, and give you the ability (with enough care) to report nicely and specifically syntax errors.

You could also use bison, but I believe a hand-written recursive parser would probably go faster.

And you can do lexing with a flex generated lexer, and do the parsing manually, in a recursive descent way.

For your information the GCC compiler has its own recursive-descent parsers for C++ & C at least. It does not use parser generators (like bison or ANTLR) anymore.

Answer 5

Instead of expr make you grammar recognize sequence-of-expr.

EDIT:

Instead of having (bison syntax):

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

have:

start: expr_seq ;

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

Answer 6

I've written many parsers, and hand-coded recursive-descent is the way I do it. They are easy to write and pretty much optimal.

That said, if speed is what you're after, no matter what you write there will be plenty of room to speed it up. These will be in ways that could surprise you, because anything you could think of, you would have already done.

Here's a slide set showing how to do it.