Ventajas de Antlr (versus say, lex / yacc / bison) [cerrado]

Question

He usado lex y yacc (más generalmente bison) en el pasado para varios proyectos, generalmente traductores (como un subconjunto de EDIF transmitido a una aplicación EDA). Además, he tenido que admitir código basado en gramáticas lex / yacc que datan de décadas. Así que conozco las herramientas, aunque no soy un experto.

He visto comentarios positivos sobre Antlr en varios foros en el pasado, y tengo curiosidad por saber lo que me puedo estar perdiendo. Entonces, si ha usado ambos, dígame qué es mejor o más avanzado en Antlr. Mis limitaciones actuales son que trabajo en una tienda de C ++, y cualquier producto que enviemos no incluirá Java, por lo que los analizadores resultantes tendrían que seguir esa regla.

Answer 1

Actualización / advertencia: ¡Esta respuesta puede estar desactualizada!

---

Una diferencia importante es que ANTLR genera un analizador LL (*), mientras que YACC y Bison generan analizadores que son LALR. Esta es una distinción importante para una serie de aplicaciones, siendo los operadores más obvios:

expr ::= expr '+' expr
       | expr '-' expr
       | '(' expr ')'
       | NUM ;

ANTLR es totalmente incapaz de manejar esta gramática como está. Para usar ANTLR (o cualquier otro generador de analizador de LL), necesitaría convertir esta gramática a algo que no sea recursivo a la izquierda. Sin embargo, Bison no tiene ningún problema con las gramáticas de esta forma. Necesitaría declarar '+' y '-' como operadores asociativos a la izquierda, pero eso no es estrictamente necesario para la recursión izquierda. Un mejor ejemplo podría ser el envío:

expr ::= expr '.' ID '(' actuals ')' ;

actuals ::= actuals ',' expr | expr ;

Observe que tanto las reglas de expr como las de actuals son recursivas por la izquierda. Esto produce un AST mucho más eficiente cuando llega el momento de la generación de código, ya que evita la necesidad de múltiples registros y derrames innecesarios (un árbol que se inclina hacia la izquierda puede colapsarse mientras que un árbol que se inclina hacia la derecha no).

En términos de gusto personal, creo que las gramáticas LALR son mucho más fáciles de construir y depurar. La desventaja es que tiene que lidiar con errores un tanto crípticos como el cambio de reducción y (el temido) reducir-reducir. Estos son errores que Bison detecta al generar el analizador, por lo que no afecta la experiencia del usuario final, pero puede hacer que el proceso de desarrollo sea un poco más interesante. ANTLR se considera generalmente más fácil de usar que YACC / Bison por precisamente este motivo.

Answer 2

La diferencia más significativa entre YACC / Bison y ANTLR es el tipo de gramáticas que pueden procesar estas herramientas. YACC / Bison manejan gramáticas LALR, ANTLR maneja gramáticas LL.

A menudo, las personas que han trabajado con las gramáticas LALR durante mucho tiempo, encontrarán que trabajar con las gramáticas LL es más difícil y viceversa. Eso no significa que las gramáticas o herramientas sean inherentemente más difíciles de trabajar. La herramienta que le resulte más fácil de usar principalmente se familiarizará con el tipo de gramática.

En cuanto a las ventajas, hay aspectos en los que las gramáticas LALR tienen ventajas sobre las gramáticas LL y hay otros aspectos en los que las gramáticas LL tienen ventajas sobre las gramáticas LALR.

YACC / Bison genera analizadores controlados por tabla, lo que significa que la lógica de procesamiento " está contenido en los datos del programa de análisis, no tanto en el código del analizador. La recompensa es que incluso un analizador para un lenguaje muy complejo tiene una huella de código relativamente pequeña. Esto fue más importante en las décadas de 1960 y 1970, cuando el hardware era muy limitado. Los generadores de analizadores controlados por tablas se remontan a esta era y la huella de código pequeño era un requisito principal en ese entonces.

ANTLR genera analizadores de descendencia recursivos, lo que significa que la lógica de procesamiento " está contenido en el código del analizador, ya que cada regla de producción de la gramática está representada por una función en el código del analizador. La recompensa es que es más fácil entender lo que hace el analizador leyendo su código. Además, los analizadores de descenso recursivo suelen ser más rápidos que los de mesa. Sin embargo, para lenguajes muy complejos, la huella del código será mayor. Este fue un problema en los años sesenta y setenta. En ese entonces, solo lenguajes relativamente pequeños como Pascal, por ejemplo, se implementaron de esta manera debido a las limitaciones de hardware.

Los analizadores generados por ANTLR suelen estar cerca de 10.000 líneas de código y más. Los analizadores de descenso recursivos escritos a mano suelen estar en el mismo estadio. El compilador Oberon de Wirth es quizás el más compacto con aproximadamente 4000 líneas de código, incluida la generación de código, pero Oberon es un lenguaje muy compacto con solo unas 40 reglas de producción.

Como alguien ya ha señalado, una gran ventaja para ANTLR es la herramienta gráfica IDE, llamada ANTLRworks. Es un completo laboratorio de gramática y diseño de idiomas. Visualiza las reglas gramaticales a medida que las escribe y, si encuentra algún conflicto, le mostrará gráficamente qué es el conflicto y qué lo causa. Incluso puede refactorizar y resolver automáticamente conflictos como la recursión izquierda. Una vez que tenga una gramática libre de conflictos, puede dejar que ANTLRworks analice un archivo de entrada de su idioma y cree un árbol de análisis y AST para usted y muestre el árbol gráficamente en el IDE. Esta es una gran ventaja porque le puede ahorrar muchas horas de trabajo: ¡encontrará errores conceptuales en el diseño de su idioma antes de comenzar a codificar! No he encontrado ninguna herramienta de este tipo para las gramáticas LALR, parece que no existe tal herramienta.

Incluso para las personas que no desean generar sus analizadores sino que los codifican a mano, ANTLRworks es una gran herramienta para el diseño / creación de prototipos de idiomas. Posiblemente la mejor herramienta disponible. Desafortunadamente, eso no te ayuda si quieres construir analizadores LALR. Cambiar de LALR a LL simplemente para aprovechar ANTLRworks puede valer la pena, pero para algunas personas, cambiar de gramática puede ser una experiencia muy dolorosa. En otras palabras: YMMV.

Answer 3

Un par de ventajas para ANTLR:

• puede generar analizadores en varios idiomas, Java no es necesario para ejecutar el analizador generado.
• La GUI impresionante hace que la depuración de la gramática sea fácil (por ejemplo, puede ver los AST generados directamente en la GUI, no se requieren herramientas adicionales)
• El código generado es en realidad legible para los humanos (es uno de los objetivos de ANTLR) y el hecho de que genera analizadores LL seguramente ayuda en este sentido.
• la definición de terminales también está libre de contexto (a diferencia de las expresiones regulares en (f) lex), lo que permite, por ejemplo, la definición de terminales que contienen paréntesis correctamente cerrados

Mi .02 $

Answer 4

Otra ventaja de ANTRL es que puede usar ANTLRWORKS , aunque no puedo diga que esta es una ventaja estricta, ya que puede haber herramientas similares para otros generadores también.

Answer 5

• Bison y Flex dan como resultado una huella de memoria más pequeña, pero no tiene un IDE gráfico.
• antlr usa más memoria, pero tienes antlrworks, un IDE gráfico.

El uso de memoria Bison / Flex es típicamente un mbyte más o menos. Compare esto con antlr, suponiendo que utiliza 512 bytes de memoria para cada token en el archivo que desea analizar. 4 millones de tokens y ya no tiene memoria virtual en un sistema de 32 bits.

Si el archivo que desea analizar es grande, antlr puede quedarse sin memoria, por lo que si solo desea analizar un archivo de configuración, sería una solución viable. De lo contrario, si desea analizar un archivo con muchos datos, pruebe Bison.