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

Question

He usado lex y yacc (más habitualmente 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 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

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 genera analizadores sintácticos, 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 generados ANTLR 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, sino que los codifican 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 2

Otra ventaja de ANTRL es que puedes 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:

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

Mi .02 $

Answer 4

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 las más obvias las operadoras:

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

ANTLR es completamente incapaz de manejar esta gramática tal como es. 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 mejor ejemplo podría ser el despacho:

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

Tenga en cuenta que tanto las reglas expr como las actuals son recursivas a la izquierda. 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 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 tienes 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 desea 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.