Bester Parser-Generator zum Parsen vieler kleiner Texte in C ++?

Question

Ich portiere aus Leistungsgründen eine C # -Bibliothek nach C ++. Während des normalen Betriebs muss diese Bibliothek unter anderem etwa 150'000 mathematische Ausdrücke (Think Excel-Formeln) mit einer durchschnittlichen Länge von weniger als 150 Zeichen analysieren.

In der C # -Version habe ich den GOLD-Parser verwendet, um Parsing-Code zu generieren. Es kann alle 150'000 Ausdrücke in weniger als einer Sekunde analysieren.

Da wir darüber nachdachten, unsere Sprache zu erweitern, dachte ich, dass die Umstellung auf C ++ eine gute Chance sein könnte, auf ANTLR umzusteigen. Ich habe die (einfache) Grammatik auf ANTLR portiert und daraus C-Code generiert. Das Parsen der 150'000 Ausdrücke dauert mehr als 12 Sekunden, da ich für jeden Ausdruck einen neuen ANTL3_INPUT_STREAM, Token-Stream, Lexer und Parser erstellen muss - zumindest in Version 3.4 gibt es keine Möglichkeit, sie wiederzuverwenden.

Ich wäre dankbar, wenn mir jemand eine Empfehlung geben könnte, was ich stattdessen verwenden soll - GOLD ist natürlich eine Option, obwohl das Generieren von C ++ oder C-Code viel komplizierter erscheint als die C # -Variante. Meine Grammatik ist LALR- und LL (1) -kompatibel. Das Hauptanliegen ist das Parsen der Leistung bei kleinen Eingaben.

Answer 1

Ich würde Boost :: Spirit ausprobieren.Es ist oft extrem schnell (selbst zum Parsen einfacher Dinge wie einer Ganzzahl kann es schneller sein als die C-Funktion atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html )

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

Es hat nette Dinge: nur Header, also Abhängigkeitshölle, liberale Lizenz.

Seien Sie jedoch gewarnt, dass die Lernkurve schwierig ist.Es ist modernes C ++ (kein Zeiger, aber viele Vorlagen und sehr frustrierende Kompilierungsfehler). Wenn Sie also von C oder C # kommen, fühlen Sie sich möglicherweise nicht sehr wohl.

Answer 2

If the grammar to be parsed is simple, you might just write the parser by hand.

Most parser generators are designed to make it easy to whip up a working parser, and execution time often suffers as a result.

Answer 3

The best performance I have seen in parsing came from Boost.Spirit.Qi which expresses the grammar in C++ using meta-template programming. It is not for the faint of heart though.

This will need be well insulated, and the compilation time of the file containing the parser will increase to several seconds (so better make sure there is as few as possible there).

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.