¿El mejor generador de analizadores sintácticos para analizar muchos textos pequeños en C ++?

Question

Estoy, por motivos de rendimiento, portando una biblioteca C # a C ++. Durante el funcionamiento normal, esta biblioteca necesita, entre otras cosas, analizar unas 150.000 expresiones matemáticas (piense en fórmulas de Excel) con una longitud promedio de menos de 150 caracteres.

En la versión C #, utilicé el analizador GOLD para generar código de análisis. Puede analizar las 150.000 expresiones en menos de un segundo.

Debido a que estábamos pensando en extender nuestro lenguaje, pensé que el cambio a C ++ podría ser una buena oportunidad para cambiar a ANTLR. He portado la gramática (simple) a ANTLR y he generado código C a partir de ella. Analizar las 150.000 expresiones lleva más de 12 segundos, porque para cada expresión, necesito crear un nuevo ANTL3_INPUT_STREAM, flujo de tokens, lexer y analizador; al menos en la versión 3.4, no hay forma de reutilizarlos.

Estaría agradecido si alguien me pudiera dar una recomendación sobre qué usar en su lugar - GOLD es, por supuesto, una opción, aunque generar código C ++ o C parece mucho más complicado que la variedad C #. Mi gramática es compatible con LALR y LL (1). La principal preocupación es analizar el rendimiento en pequeñas entradas.

Answer 1

Intentaría impulsar :: espíritu.A menudo es extremadamente rápido (incluso para analizar cosas simples como un número entero, puede ser más rápido que la función C atoi http://alexott.blogspot.com/2010/01/boostspirit2-vs-atoi.html )

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

Tiene cosas bonitas: solo encabezado, por lo que el infierno de dependencia, licencia liberal.

Sin embargo, tenga en cuenta que la curva de aprendizaje es difícil.Es un C ++ moderno (sin puntero, pero con muchas plantillas y errores de compilación muy frustrantes), por lo que al venir de C o C #, es posible que no se sienta muy cómodo.

Answer 2

Si la gramática que se va a analizar es simple, puede escribir el analizador a mano.

La mayoría de los generadores de analizadores sintácticos están diseñados para facilitar la creación de un analizador sintáctico que funcione y, como resultado, el tiempo de ejecución suele verse afectado.

Answer 3

El mejor rendimiento que he visto en parsing vino de Boost.Spirit.Qi, que expresa la gramática en C ++ usando programación de meta-plantillas.Sin embargo, no es para los débiles de corazón.

Esto deberá estar bien aislado y el tiempo de compilación del archivo que contiene el analizador aumentará a varios segundos (así que es mejor asegurarse de que haya la menor cantidad posible allí).

Answer 4

Si la sintaxis de su expresión es lo suficientemente simple, considere hacer un analizador de descenso recursivo escrito a mano .Puede ejecutarse muy rápido y brindarte la capacidad (con suficiente cuidado) de informar de manera agradable y específica errores de sintaxis.

También podría utilizar bison , pero creo que un analizador recursivo escrito a mano probablementeir más rápido.

Y puede realizar lexing con un flex generado lexer y realizar el análisis manualmente,en forma de descenso recursivo.

Para su información, el compilador GCC tiene sus propios analizadores sintácticos de descenso recursivo para C ++ y C al menos.Ya no usa generadores de analizadores sintácticos (como bison o ANTLR ).

Answer 5

En lugar de expr, haz que tu gramática reconozca sequence-of-expr.

<×EDIT:

En lugar de tener (sintaxis de bisonte):

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

tienen:

start: expr_seq ;

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

Answer 6

He escrito muchos analizadores y la forma en que lo hago es el descenso recursivo codificado a mano.Son fáciles de escribir y bastante óptimos.

Dicho esto, si lo que busca es velocidad, no importa lo que escriba, habrá mucho espacio para acelerarlo. Estos serán de formas que podrían sorprenderlo, porque cualquier cosa que pudiera pensar, ya lo habría hecho.

Aquí se muestra un conjunto de diapositivas cómo hacerlo.