Meilleur générateur d'analyseur pour analyser de nombreux petits textes en C ++?

StackOverflow https://stackoverflow.com/questions/8356206

Question

Je suis, pour des raisons de performance, portage d'une bibliothèque C # C ++. En fonctionnement normal, cette bibliothèque besoins, entre autres, pour analyser sur les 150'000 expressions mathématiques (pensez formules Excel) avec une longueur moyenne de moins de 150 caractères.

Dans la version C #, j'ai utilisé analyseur GOLD pour générer le code analyse syntaxique. Il peut analyser toutes 150'000 expressions en moins d'une seconde.

Parce que nous avons pensé à l'extension de notre langue, je me suis dit le passage à C ++ pourrait être une bonne chance de changement ANTLR. J'ai porté la grammaire (de simples) à ANTLR et généré code C sur elle. Les expressions 150'000 analyse prend plus de 12 secondes, parce que pour chaque expression, je dois créer un nouveau ANTL3_INPUT_STREAM, flux symbolique, et l'analyseur lexer -. Il est, au moins dans la version 3.4, aucun moyen de les réutiliser

Je serais reconnaissant quelqu'un pourrait me donner une recommandation ce qu'il faut utiliser à la place - GOLD est bien sûr une option si la génération C ++ ou un code C semble beaucoup plus compliqué que la variété C #. Ma grammaire est LALR et LL (1) compatible. Paramount est la performance préoccupation sur les petites entrées analyse pas.

Était-ce utile?

La solution

Je voudrais essayer boost :: esprit. Il est souvent extreamly rapide (même pour l'analyse syntaxique des choses simples comme un entier, il peut être plus rapide que la fonction C atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html )

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

Il a de belles choses. En-tête uniquement, si l'enfer de la dépendance, licence libérale

Cependant, soyez averti que la courbe d'apprentissage est difficile. Il est moderne C ++ (pas de pointeur, mais beaucoup de modèle et très frustrant erreurs de compilation), donc en provenance de C ou C #, vous pourriez ne pas être très à l'aise.

Autres conseils

Si la grammaire à parser est simple, vous pourriez écrire simplement l'analyseur à la main.

La plupart des générateurs d'analyseur sont conçus pour le rendre facile à concocter un analyseur de travail, et le temps d'exécution souffre souvent en conséquence.

La meilleure performance que je l'ai vu dans parsing est venu de Boost.Spirit.Qi qui exprime la grammaire en C ++ en utilisant la programmation méta-modèle. Il n'est pas pour les faibles de cœur cependant.

Cela doit être bien isolé, et le temps de compilation du fichier contenant l'analyseur augmentera à plusieurs secondes (faire en sorte de mieux assurer qu'il ya aussi peu que possible là-bas).

Si la syntaxe de votre expression est assez simple, considérer faire un analyseur de descente récursive écrite à la main . Il peut courir très vite, et vous donner la possibilité (avec assez de soin) pour signaler les erreurs de syntaxe et bien spécifique.

Vous pouvez également utiliser bison , mais je crois un analyseur récursif écrit à la main serait probablement aller plus vite.

Et vous pouvez faire Lexing avec un produit flex lexer et faire l'analyse syntaxique manuellement, d'une manière de descente récursive.

Pour votre information, le compilateur GCC a ses propres parseurs descente récursive pour C ++ et C au moins. Il n'utilise des générateurs d'analyseur (comme bison ou ANTLR ) plus.

Au lieu de expr vous faites la grammaire reconnaîtrez sequence-of-expr.

EDIT:

Au lieu d'avoir (syntaxe de bison): 

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

ont: 

start: expr_seq ;

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

J'ai écrit beaucoup de parseurs, et descente récursive codée à la main est la façon dont je le fais. Ils sont faciles à écrire et à peu près optimale.

Cela dit, si la vitesse est ce que vous êtes après, peu importe ce que vous écrivez, il y aura beaucoup de place pour l'accélérer. Ceux-ci seront d'une manière qui pourrait vous surprendre, parce que tout ce que vous peut penser, vous avez déjà fait.

Voici un jeu de diapositives montrant comment le faire.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top