¿Es el generador de analizadores ANTLR el mejor para una aplicación C++ con memoria limitada?

Question

Estoy buscando un buen generador de analizadores que pueda usar para leer un formato de archivo de texto personalizado en nuestra gran aplicación comercial. Actualmente, este formato de archivo particular se lee con un analizador sintáctico recursivo hecho a mano, pero el formato ha crecido y se ha complejizado hasta el punto en que ese enfoque se ha vuelto inmanejable.

Parece que la mejor solución sería construir una gramática adecuada para este formato y luego usar un generador de analizador real como yacc para leerlo, pero tengo problemas para decidir qué generador usar o incluso si ' vale la pena el problema en absoluto. Miré ANTLR y Spirit, pero nuestro proyecto tiene limitaciones específicas más allá de earlier answers que me preguntan si son apropiadas para nosotros. En particular, necesito:

• Un analizador que genera código C o C++ con MSVC. ANTLR 3 no es compatible con C++; afirma generar C directa, pero los documentos sobre cómo conseguir que funcione realmente son un tanto confusos.
• Uso de memoria severamente restringido. La memoria es una gran ventaja en nuestra aplicación e incluso pequeñas pérdidas son fatales. Necesito poder anular el asignador de memoria del analizador para usar nuestro malloc personalizado(), o al menos necesito darle un conjunto contiguo del cual extrae toda su memoria (y que luego puedo desasignar en bloque). Puedo ahorrar unos 200 kb para el ejecutable del analizador, pero cualquier montón dinámico que asigna en el análisis tiene que liberarse después.
• Buen rendimiento. Esto es menos crítico, pero deberíamos poder analizar 100 kb de texto en no más de un segundo en un procesador de 3 ghz.
• Debe estar libre de GPL. No podemos usar el código GNU.

me gusta herramientas IDE y depuración ANTLRworks', pero parece conseguir su objetivo C para ponerse a trabajar con nuestra aplicación será una empresa enorme. Antes de embarcarme en esa palabrería, ¿ANTLR es la herramienta adecuada para este trabajo?

El formato de texto en cuestión se ve algo como:

attribute "FluxCapacitance" real constant 

asset DeLorean 
{ 
    //comment foo bar baz 
    model "delorean.mdl" 
    animation "gullwing.anm" 
    references "Marty" 
    loadonce 
} 

template TimeMachine 
{ 
    attribute FluxCapacitance 10  
    asset DeLorean 
} 

Answer 1

ANTLR 3 no es compatible con C++; reclama para generar C directo pero los documentos en consiguiendo que funcione realmente son tipo de confusión.

Genera C, y además, funciona con Visual Studio y C++. Lo sé porque lo he hecho antes y he enviado un parche para que funcione con stdcall.

La memoria es muy importante en nuestra aplicación e incluso pequeñas fugas son fatales. Necesito ser capaz de anular asignador la memoria del analizador de usar nuestra costumbre malloc(), o por lo menos yo necesito darle una piscina contigua desde que se saca toda su memoria (y que puedo desasignar en bloque después). Puedo ahorrar aproximadamente 200kb para el ejecutable del analizador mismo, pero cualquiera que sea el montón dinámico que asigna en el análisis tiene que ser liberado después.

El tiempo de ejecución de antlr3c, la última vez que lo comprobé no tiene una pérdida de memoria, y utiliza el paradigma de grupo de memoria que usted describe. Sin embargo, tiene un inconveniente en la API que el autor se niega a cambiar, que es que si solicita la cadena de un nodo, creará una nueva copia cada vez hasta que libere todo el analizador.

No tengo ningún comentario sobre la facilidad de utilizar un malloc personalizado, pero tiene una macro para definir qué función malloc usar en todo el proyecto.

En cuanto al tamaño del ejecutable, mi compilación fue de aproximadamente 100 kb de tamaño, incluyendo un pequeño intérprete.

Mi sugerencia para usted es seguir aprendiendo ANTLR, porque todavía se ajusta a sus necesidades y es probable que necesite sacrificar un poco más de tiempo antes de que comience a funcionar para usted.

Answer 2

analizadores ANTLR, y de hecho cualquier analizador LALR construida con algo o similares, tienden a ser grandes. ¿Tienes una gramática real para esto? Es se ve como podría ser más fácilmente analizado con un analizador sintáctico de descenso recursivo escrito a mano, pero no es una gran muestra.

Vaya, mi error, ya que ANTLR aparentemente genera descenso recursivo. Aún así, he tenido problemas con ANTLR generando analizadores grandes.

Answer 3

Usamos Boost Spirit con éxito en nuestra aplicación. El Boost license es muy liberal, por lo que no hay problema para utilizarlo en aplicaciones comerciales.

Quote from the documentation:

Espíritu es un marco generador de análisis sintáctico descendente recursivo orientado a objetos implementado utilizando técnicas de meta-programación de la plantilla. Las plantillas de expresión nos permiten aproximarnos por completo a la sintaxis del Backus-Normal Form (EBNF) extendido en C++. El marco de Spirit permite que una gramática de destino se escriba exclusivamente en C++.Las especificaciones de gramática en línea EBNF se pueden mezclar libremente con otros códigos C++ y, gracias al poder generativo de las plantillas C++, son inmediatamente ejecutables. En retrospectiva, los compiladores compiladores convencionales o los generadores de analizadores sintácticos tienen que realizar un paso de traducción adicional desde el código fuente EBNF al código C o C++.

Answer 4

¿Entonces por qué no usa flex/yacc? Genera código C, se puede ejecutar desde MSVC, se desarrolló con la eficiencia en mente, puede tener overlode malloc (google para yymalloc), ellos mismos son GPL, pero el código resultante (el código que usa en su proyecto) no es AFAIK.

O utilice un analizador sintáctico hecho a mano.

Answer 5

De manera realista, si su gramática es relativamente pequeña, y no contiene muchas ambigüedades ni complejidades de análisis, entonces no debería importar si utiliza un analizador de descenso recursivo o un analizador de desplazamiento-reducción.

Yo diría que mira ANTLR y Spirit, también mira a Flex y Bison. Hay otros analizadores menos conocidos como Coco/R (contiene generadores para muchos idiomas, incluido C++) también.

Answer 6

Un analizador de descenso recursivo codificado a mano es en realidad bastante rápido y puede ser muy compacto. El único inconveniente es que debe tener cuidado para codificar esencialmente gramáticas LL (1).[Si usa ANTLR, tiene restricciones similares, así que esto no es tan importante].

Puede codificar manualmente dichos analizadores como código C recursivo simple. (Ver esta respuesta para los detalles completos: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?)

Si está realmente apretado en el espacio, se puede definir un máquina virtual de análisis, y construir un pequeño intérprete C para ejecutarlo. Solía ​​construir intérpretes de BASIC de esta manera a principios de los 70.

Al seguir las convenciones muy simples que hacen que estos analizadores realmente funcionen, puede garantizar que no hay ninguna pérdida de memoria causada por la maquinaria de análisis . (Por supuesto, puede adjuntar acciones arbitrarias al analizador donde reconoce elementos de interés, si esas acciones tienen una fuga es una cuestión de programación general, no el analizador).

Las ideas provienen de un documento de 1964 sobre metacompiladores de Val Schorre, que muestra cómo compilar compiladores completos en 10 páginas. El generador de analizadores minúsculos de Shorre produce muy buenos recursivos de bajada recursiva analizadores. Un sitio que describe este papel y mostrando precisamente cómo construir tales analizadores se puede encontrar en http://www.bayfronttechnologies.com/metaii.html

utilicé métodos de Schorre para construir compiladores básicos a finales de los años 70, después me cansé de gramáticas complejas codificación manual.

Answer 7

Eche un vistazo al nuevo objetivo de C++ que he publicado para ANTLR. También tiene la opción de restringir el uso de memoria del analizador, y expone todas las rutinas de gestión de memoria necesarias en forma de rasgos.

http://www.antlr.org/wiki/pages/viewpage.action?pageId=29130826