Ventajas de Antlr (frente a decir, lex/yacc/bison)

Question

He usado lex y yacc (más generalmente bisontes) 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 se remontan a décadas atrás. Así que sé cómo manejar las herramientas, aunque no soy un experto.

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

Answer 1

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, los operadores más obvia es:

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

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

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

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

en cuenta que tanto el expr y las reglas actuals se dejan recursiva. Esto produce una AST mucho más eficiente cuando llega el momento de la generación de código porque evita la necesidad de registros múltiples y derrames innecesarios (un árbol de inclinación izquierda puede colapsarse mientras que un árbol de inclinación derecha no puede).

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 tienes que lidiar con errores algo crípticos como shift-reduce 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 generalmente se considera más fácil de usar que YACC/Bison por precisamente esta razón.

Answer 2

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

Answer 3

Un par de ventajas para antlr: analizadores de salida

• lata en varios idiomas - Java no requieren para ejecutar el analizador generado.
• GUI impresionante hace que la depuración de la gramática fácil (por ejemplo, se puede ver el derecho generada de AST en la interfaz gráfica de usuario, sin herramientas adicionales requeridos)
• código generado es realmente legible (es uno de los objetivos de antlr) y el hecho de que genera analizadores de LL sin duda ayuda en este sentido.
• definición de terminales está libre de contexto, así (a diferencia de regex en (f) lex) - por lo tanto permite, por ejemplo, la definición de terminales contienen paréntesis correctamente cerrados

Mi 0.02 $

Answer 4

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

A menudo, las personas que han trabajado con gramáticas LALR durante mucho tiempo, encontrarán que trabajar con gramáticas LL es más difícil y viceversa. Eso no significa que las gramáticas o las herramientas sean intrínsecamente más difíciles de trabajar. La herramienta que encuentres más fácil de usar se reducirá principalmente a la familiaridad 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 generan analizadores sintácticos de tabla, lo que significa que la "lógica de procesamiento" está contenida en los datos del programa analizador, 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 los años 60 y 70 cuando el hardware era muy limitado. Los generadores de analizadores sintácticos basados ​​en tablas se remontan a esta era y la huella de código pequeña era un requisito principal en aquel entonces.

ANTLR genera analizadores de descenso recursivos, lo que significa que la "lógica de procesamiento" está contenida 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 descendentes recursivos son típicamente más rápidos que los basados ​​en tablas. Sin embargo, para idiomas muy complejos, la huella del código será mayor. Este fue un problema en los años 60 y 70. En aquel entonces, solo los lenguajes relativamente pequeños como Pascal, por ejemplo, se implementaban de esta manera debido a limitaciones de hardware.

Los analizadores ANTLR generados suelen estar cerca de las 10.000 líneas de código y más. Analizadores sintácticos recursivos manuscritos a menudo están en el mismo estadio. El compilador Wirth's Oberon es quizás el más compacto con unas 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 laboratorio completo de diseño de gramática y lenguaje. Visualiza sus reglas de gramática 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 automáticamente y resolver conflictos como la recursividad a la izquierda. Una vez que tenga una gramática libre de conflictos, puede dejar que ANTLRworks analice un archivo de entrada de su idioma y crear un árbol de análisis sintáctico y AST para usted y mostrar el árbol de forma gráfica en el IDE. Esta es una gran ventaja porque puede ahorrarle 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 pero codificarlos a mano, ANTLRworks es una gran herramienta para el diseño de lenguaje/creación de prototipos. Muy posiblemente la mejor herramienta disponible. Desafortunadamente, eso no te ayuda si quieres construir analizadores LALR. Cambiar de LALR a LL simplemente para aprovechar ANTLRworks bien puede valer la pena, pero para algunas personas, cambiar los tipos de gramática puede ser una experiencia muy dolorosa. En otras palabras: YMMV.

Answer 5

• Bison y Flex tienen como resultado un espacio de memoria más pequeño, pero no tiene un IDE gráfico.
• antlr usa más memoria, pero tiene antlrworks, un IDE gráfico.

El uso de la memoria Bison/Flex es típicamente de un mbyte más o menos. Contraste eso con antlr, suponiendo que utiliza 512 bytes de memoria para cada token en el archivo que desea analizar. 4 millones de tokens y 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 quiere analizar un archivo de configuración, sería una solución viable. De lo contrario, si quieres analizar un archivo con muchos datos, prueba Bison.