¿Cuándo usar un Combinador de analizador? ¿Cuándo usar un generador de analizador?

Recientemente me sumergí en el mundo de los analizadores sintéticos, queriendo crear mi propio lenguaje de programación.

Sin embargo, descubrí que existen dos enfoques algo diferentes para escribir analizadores: Generadores de analizadores y Combinadores de analizadores.

Curiosamente, no he podido encontrar ningún recurso que explique en qué casos qué enfoque es mejor; Más bien, muchos recursos (y personas) que pregunté sobre el tema no conocían el otro enfoque, solo explicaban su enfoque como el enfoque y no mencionaban el otro en absoluto:

• El famoso libro de Dragon entra en lexing / scan y menciona (f) lex, pero no menciona a los Combinadores de analizador en absoluto.
• Language Implementation Patterns se basa en gran medida en el generador de analizador ANTLR construido en Java, y no menciona en absoluto los combinadores de analizador.
• El tutorial Introducción a Parsec en Parsec, que es un Combinador de analizador en Haskell, no menciona a los Generadores de analizador en absoluto.
• Boost :: spirit , el combinador de analizador de C ++ más conocido, no menciona a los generadores de analizador en absoluto.
• La gran publicación explicativa del blog que podría haber inventado Combinadores de analizador no menciona a los generadores de analizador en absoluto.

Resumen simple:

Generador de analizador

Un generador de analizador toma un archivo escrito en un DSL que es un dialecto de la forma Backus-Naur extendida y lo convierte en código fuente que luego (cuando se compila) puede convertirse en un analizador del lenguaje de entrada que se describe en este DSL.

Esto significa que el proceso de compilación se realiza en dos pasos separados. Curiosamente, los generadores Parser también son compiladores (y muchos de ellos son de hecho autohospedaje ).

Combinador de analizador

Un Combinador de analizador describe funciones simples llamadas analizadores que toman una entrada como parámetro e intentan arrancar los primeros caracteres de esta entrada si coinciden. Devuelven una tupla (result, rest_of_input), donde resultpodría estar vacía (por ejemplo, nilo Nothing) si el analizador no pudo analizar nada de esta entrada. Un ejemplo sería un digitanalizador sintáctico. Otros analizadores pueden, por supuesto, tomar analizadores como primeros argumentos (el argumento final sigue siendo la cadena de entrada) para combinarlos : por ejemplo, many1intenta emparejar a otro analizador tantas veces como sea posible (pero al menos una vez, o falla).

Ahora, por supuesto, puede combinar (componer) digity many1, para crear un nuevo analizador, decir integer.

Además, choicese puede escribir un analizador de nivel superior que tome una lista de analizadores, probando cada uno de ellos por turno.

De esta manera, se pueden construir lexers / analizadores muy complejos. En los idiomas que admiten la sobrecarga del operador, esto también se parece mucho a EBNF, a pesar de que todavía está escrito directamente en el idioma de destino (y puede utilizar todas las funciones del idioma de destino que desee).

Diferencias simples

Idioma:

• Los generadores de analizadores se escriben en una combinación de la DSL EBNF-ish y el código que estas declaraciones deben generar cuando coinciden.
• Los combinadores del analizador se escriben directamente en el idioma de destino.

Lexing / Parsing:

• Los generadores de analizadores tienen una diferencia muy clara entre el 'lexer' (que divide una cadena en tokens que podrían estar etiquetados para mostrar qué tipo de valor estamos tratando) y el 'analizador' (que toma la lista de salida de tokens del lexer e intenta combinarlos, formando un árbol de sintaxis abstracta).
• Los Combinadores de analizador no tienen / necesitan esta distinción; por lo general, los analizadores simples realizan el trabajo del 'lexer' y los analizadores de más alto nivel llaman a estos analizadores más simples para decidir qué tipo de nodo AST crear.

Pregunta

Sin embargo, incluso teniendo en cuenta estas diferencias (¡y esta es una lista de diferencias que probablemente esté lejos de ser completa!), No puedo hacer una elección informada sobre cuándo usar cuál. No veo cuáles son las implicaciones / consecuencias de estas diferencias.

¿Qué propiedades del problema indicarían que un problema se resolvería mejor usando un generador de analizador? ¿Qué propiedades del problema indicarían que un problema se resolvería mejor con un Combinador de analizador?

He investigado mucho estos últimos días para comprender mejor por qué existen estas tecnologías separadas y cuáles son sus fortalezas y debilidades.

Algunas de las respuestas ya existentes insinuaban algunas de sus diferencias, pero no dieron la imagen completa, y parecían ser algo obstinadas, razón por la cual se escribió esta respuesta.

Esta exposición es larga, pero importante. tenga paciencia conmigo (o si está impaciente, desplácese hasta el final para ver un diagrama de flujo).

Para comprender las diferencias entre los Combinadores de analizador y los Generadores de analizador, primero hay que comprender la diferencia entre los diversos tipos de análisis existentes.

Analizando

El análisis es el proceso de análisis de una cadena de símbolos de acuerdo con una gramática formal. (En Computing Science), el análisis se usa para permitir que una computadora entienda el texto escrito en un idioma, generalmente creando un árbol de análisis que representa el texto escrito, almacenando el significado de las diferentes partes escritas en cada nodo del árbol. Este árbol de análisis se puede usar para una variedad de propósitos diferentes, como traducirlo a otro idioma (usado en muchos compiladores), interpretar las instrucciones escritas directamente de alguna manera (SQL, HTML), permitiendo que herramientas como Linters hagan su trabajo. , etc. A veces, un árbol de análisis no es explícitamentegenerado, sino que la acción que se debe realizar en cada tipo de nodo en el árbol se ejecuta directamente. Esto aumenta la eficiencia, pero bajo el agua todavía existe un árbol de análisis implícito.

El análisis es un problema que es computacionalmente difícil. Ha habido más de cincuenta años de investigación sobre este tema, pero aún queda mucho por aprender.

En términos generales, hay cuatro algoritmos generales para permitir que una computadora analice la entrada:

• Análisis LL. (Sin contexto, análisis de arriba hacia abajo).
• LR analizando. (Sin contexto, análisis de abajo hacia arriba).
• Análisis PEG + Packrat.
• Earley Parsing.

Tenga en cuenta que estos tipos de análisis son descripciones teóricas muy generales. Hay varias formas de implementar cada uno de estos algoritmos en máquinas físicas, con diferentes compensaciones.

LL y LR solo pueden mirar las gramáticas libres de contexto (es decir, el contexto alrededor de los tokens que están escritos no es importante para entender cómo se usan).

El análisis PEG / Packrat y el análisis Earley se utilizan mucho menos: el análisis Earley es bueno porque puede manejar muchas más gramáticas (incluidas las que no son necesariamente sin contexto) pero es menos eficiente (como afirma el dragón libro (sección 4.1.1); no estoy seguro de si estas afirmaciones siguen siendo precisas). Parsing Expression Grammar + Packrat-parsing es un método que es relativamente eficiente y también puede manejar más gramáticas que LL y LR, pero oculta las ambigüedades, como se tratará rápidamente a continuación.

LL (derivación de izquierda a derecha, más a la izquierda)

Esta es posiblemente la forma más natural de pensar en el análisis. La idea es mirar el siguiente token en la cadena de entrada y luego decidir cuál de las múltiples llamadas recursivas posibles se debe tomar para generar una estructura de árbol.

Este árbol está construido 'de arriba hacia abajo', lo que significa que comenzamos en la raíz del árbol y recorremos las reglas gramaticales de la misma manera que recorremos la cadena de entrada. También puede verse como la construcción de un equivalente 'postfix' para la secuencia de tokens 'infix' que se está leyendo.

Los analizadores que realizan análisis de estilo LL se pueden escribir para parecerse mucho a la gramática original que se especificó. Esto hace que sea relativamente fácil de entender, depurar y mejorar. Los combinadores de analizador clásico no son más que 'piezas de lego' que se pueden unir para construir un analizador de estilo LL.

LR (derivación de izquierda a derecha, más a la derecha)

El análisis LR viaja en sentido contrario, de abajo hacia arriba: en cada paso, los elementos superiores en la pila se comparan con la lista de gramática, para ver si podrían reducirse a una regla de nivel superior en la gramática. Si no, el siguiente token de la secuencia de entrada se desplaza y se coloca en la parte superior de la pila.

Un programa es correcto si al final terminamos con un solo nodo en la pila que representa la regla inicial de nuestra gramática.

Mirar hacia el futuro

En cualquiera de estos dos sistemas, a veces es necesario echar un vistazo a más tokens de la entrada antes de poder decidir qué elección hacer. Este es el (0), (1), (k)o (*)-Sintaxis que se ve después de los nombres de estos dos algoritmos generales, como LR(1) o LL(k). kpor lo general significa "todo lo que su gramática necesita", mientras que por lo *general significa "este analizador realiza un retroceso", que es más potente / fácil de implementar, pero tiene un uso de memoria y tiempo mucho mayor que un analizador que simplemente puede seguir analizando linealmente

Tenga en cuenta que los analizadores de estilo LR ya tienen muchos tokens en la pila cuando pueden decidir 'mirar hacia adelante', por lo que ya tienen más información para enviar. Esto significa que a menudo necesitan menos "anticipación" que un analizador de estilo LL para la misma gramática.

LL vs. LR: ambigüedad

Al leer las dos descripciones anteriores, uno podría preguntarse por qué existe el análisis de estilo LR, ya que el análisis de estilo LL parece mucho más natural.

Sin embargo, el análisis de estilo LL tiene un problema: Recursión izquierda .

Es muy natural escribir una gramática como:

expr ::= expr '+' expr | term term ::= integer | float

Pero, un analizador de estilo LL se atascará en un bucle recursivo infinito al analizar esta gramática: al probar la posibilidad más a la izquierda de la exprregla, vuelve a recurrir a esta regla sin consumir ninguna entrada.

Hay formas de resolver este problema. Lo más simple es reescribir su gramática para que este tipo de recursión ya no ocurra:

expr ::= term expr_rest expr_rest ::= '+' expr | ϵ term ::= integer | float (Aquí, ϵ representa la 'cadena vacía')

Esta gramática ahora es correcta recursiva. Tenga en cuenta que de inmediato es mucho más difícil de leer.

En la práctica, la recursividad izquierda puede ocurrir indirectamente con muchos otros pasos intermedios. Esto hace que sea un problema difícil de tener en cuenta. Pero tratar de resolverlo hace que tu gramática sea más difícil de leer.

Como dice la Sección 2.5 del Libro del Dragón:

Parece que tenemos un conflicto: por un lado, necesitamos una gramática que facilite la traducción, por otro lado, necesitamos una gramática significativamente diferente que facilite el análisis. La solución es comenzar con la gramática para facilitar la traducción y transformarla cuidadosamente para facilitar el análisis. Al eliminar la recursividad izquierda podemos obtener una gramática adecuada para usar en un traductor predictivo de descenso recursivo.

Los analizadores de estilo LR no tienen el problema de esta recursión izquierda, ya que construyen el árbol de abajo hacia arriba. Sin embargo , la traducción mental de una gramática como la anterior a un analizador de estilo LR (que a menudo se implementa como un autómata de estado finito )
es muy difícil (y propensa a errores), ya que a menudo hay cientos o miles de estados + transiciones de estado a considerar. Esta es la razón por la cual los analizadores de estilo LR generalmente son generados por un generador de analizador, que también se conoce como un "compilador compilador".

Cómo resolver ambigüedades

Vimos dos métodos para resolver las ambigüedades de recursión izquierda anteriores: 1) reescribir la sintaxis 2) usar un analizador LR.

Pero hay otros tipos de ambigüedades que son más difíciles de resolver: ¿qué pasa si dos reglas diferentes son igualmente aplicables al mismo tiempo?

Algunos ejemplos comunes son:

• expresiones aritméticas
• el otro colgado

Los analizadores de estilo LL y LR tienen problemas con estos. Los problemas con el análisis de expresiones aritméticas se pueden resolver introduciendo la precedencia del operador. De manera similar, se pueden resolver otros problemas como el Dangling Else, eligiendo un comportamiento de precedencia y manteniéndolo. (En C / C ++, por ejemplo, el colgante siempre pertenece al 'if' más cercano).

Otra 'solución' para esto es usar la Gramática de expresión de analizador (PEG): es similar a la gramática BNF utilizada anteriormente, pero en el caso de una ambigüedad, siempre 'elija el primero'. Por supuesto, esto realmente no "resuelve" el problema, sino que oculta que existe una ambigüedad: los usuarios finales pueden no saber qué elección hace el analizador, y esto puede conducir a resultados inesperados.

Más información que es mucho más profunda que esta publicación, incluido por qué es imposible en general saber si su gramática no tiene ambigüedades y las implicaciones de esto es el maravilloso artículo de blog LL y LR en contexto: ¿Por qué analizar? Las herramientas son difíciles . Lo recomiendo mucho; Me ayudó mucho entender todas las cosas de las que estoy hablando en este momento.

50 años de investigación

Pero la vida sigue. Resultó que los analizadores de estilo LR 'normales' implementados como autómatas de estado finito a menudo necesitaban miles de estados + transiciones, lo cual era un problema en el tamaño del programa. Entonces, se escribieron variantes como Simple LR (SLR) y LALR (Look-ahead LR) que combinan otras técnicas para hacer que el autómata sea más pequeño, reduciendo la huella de disco y memoria de los programas del analizador.

Además, otra forma de resolver las ambigüedades enumeradas anteriormente es utilizar técnicas generalizadas en las que, en el caso de una ambigüedad, se mantengan y analicen ambas posibilidades: cualquiera de las dos podría fallar al analizar la línea (en cuyo caso la otra posibilidad es la 'correcto'), así como devolver ambos (y de esta manera mostrar que existe una ambigüedad) en el caso de que ambos sean correctos.

Curiosamente, después de que se describió el algoritmo LR generalizado , resultó que se podría usar un enfoque similar para implementar analizadores LL generalizados , que es igualmente rápido ($ O (n ^ 3) $ complejidad de tiempo para gramáticas ambiguas, $ O (n) $ para gramáticas completamente inequívocas, aunque con más contabilidad que un analizador LR simple (LA), lo que significa un factor constante más alto), pero nuevamente permite escribir un analizador en un estilo de descenso recursivo (de arriba hacia abajo) que es mucho más natural para escribir y depurar

Combinadores de analizadores, generadores de analizadores

Entonces, con esta larga exposición, ahora estamos llegando al núcleo de la pregunta:

¿Cuál es la diferencia entre los Combinadores de analizador y los Generadores de analizador, y cuándo se debe usar uno sobre el otro?

Son realmente diferentes tipos de bestias:

Los Combinadores de analizador se crearon porque las personas escribían analizadores de arriba hacia abajo y se dieron cuenta de que muchos de ellos tenían mucho en común .

Los generadores de analizadores se crearon porque las personas buscaban construir analizadores que no tuvieran los problemas que tenían los analizadores de estilo LL (es decir, analizadores de estilo LR), lo que resultó muy difícil de hacer a mano. Los más comunes incluyen Yacc / Bison, que implementan (LA) LR).

Curiosamente, hoy en día el paisaje está algo confuso:

• Es posible escribir Combinadores de analizador que funcionen con el algoritmo GLL , resolviendo los problemas de ambigüedad que tenían los analizadores de estilo LL clásicos, siendo tan legible / comprensible como todo tipo de análisis de arriba hacia abajo.

• Los generadores de analizadores también se pueden escribir para analizadores de estilo LL. ANTLR hace exactamente eso y utiliza otras heurísticas (Adaptive LL (*)) para resolver las ambigüedades que tenían los analizadores clásicos de estilo LL.

En general, crear un generador de analizador LR y depurar la salida de un generador de analizador de estilo LR (LA) que se ejecuta en su gramática es difícil, debido a la traducción de su gramática original al formulario LR 'de adentro hacia afuera'. Por otro lado, las herramientas como Yacc / Bison han tenido muchos años de optimizaciones y han visto un gran uso en la naturaleza, lo que significa que muchas personas ahora lo consideran como la forma de analizar y son escépticas hacia nuevos enfoques.

Cuál debe usar, depende de qué tan difícil sea su gramática y qué tan rápido deba ser el analizador. Dependiendo de la gramática, una de estas técnicas (/ implementaciones de las diferentes técnicas) podría ser más rápida, tener una huella de memoria más pequeña, tener una huella de disco más pequeña o ser más extensible o más fácil de depurar que las otras. Su kilometraje puede variar .

Nota al margen: sobre el tema del análisis léxico.

El análisis léxico se puede utilizar tanto para los combinadores del analizador como para los generadores del analizador. La idea es tener un analizador 'tonto' que sea muy fácil de implementar (y por lo tanto rápido) que realice un primer paso sobre su código fuente, eliminando, por ejemplo, la repetición de espacios en blanco, comentarios, etc., y posiblemente 'tokenizando' de una manera muy de manera aproximada los diferentes elementos que componen su idioma.

La principal ventaja es que este primer paso hace que el analizador real sea mucho más simple (y por eso posiblemente más rápido). La principal desventaja es que tiene un paso de traducción separado y, por ejemplo, el informe de errores con números de línea y columna se vuelve más difícil debido a la eliminación de espacios en blanco.

Un lexer al final es "simplemente" otro analizador y puede implementarse usando cualquiera de las técnicas anteriores. Debido a su simplicidad, a menudo se utilizan otras técnicas distintas del analizador principal y, por ejemplo, existen 'generadores lexer' adicionales.

Tl; Dr:

Aquí hay un diagrama de flujo que es aplicable a la mayoría de los casos:

Para la entrada que está garantizada de estar libre de errores de sintaxis, o donde un correcto general de aprobación / falla en la corrección sintáctica está bien, los combinadores de analizador sintáctico son mucho más simples de trabajar, especialmente en lenguajes de programación funcionales. Estas son situaciones como programar rompecabezas, leer archivos de datos, etc.

La característica que hace que desee agregar la complejidad de los generadores de analizadores son los mensajes de error. Desea mensajes de error que dirijan al usuario a una línea y columna, y es de esperar que también sean entendibles por un humano. Se necesita mucho código para hacerlo correctamente, y los mejores generadores de analizadores como antlr pueden ayudarlo con eso.

Sin embargo, la generación automática solo puede llegar hasta ahora, y la mayoría de los compiladores de código abierto comerciales y de larga duración terminan escribiendo manualmente sus analizadores. Supongo que si te sintieras cómodo haciendo esto, no hubieras hecho esta pregunta, por lo que te recomendaría ir con el generador de analizadores.

Sam Harwell, uno de los mantenedores del generador de analizadores ANTLR, escribió recientemente :

Descubrí que [los combinadores] no satisfacen mis necesidades:

1. ANTLR me proporciona herramientas para gestionar cosas como ambigüedades. Durante el desarrollo hay herramientas que pueden mostrarme resultados de análisis ambiguos para que pueda eliminar esas ambigüedades en la gramática. En tiempo de ejecución, puedo aprovechar la ambigüedad resultante de una entrada incompleta en el IDE para producir resultados más precisos en características como la finalización del código.
2. En la práctica, he descubierto que los combinadores de analizador sintáctico no eran adecuados para cumplir mis objetivos de rendimiento. Parte de esto se remonta
3. Cuando los resultados de análisis se utilizan para funciones como el esquema, la finalización del código y la sangría inteligente, es fácil que cambios sutiles en la gramática afecten la precisión de esos resultados. ANTLR proporciona herramientas que pueden convertir estos desajustes en errores de compilación, incluso en los casos en que los tipos de otra manera se compilarían. Puedo crear un prototipo con confianza de una nueva función de lenguaje que afecta la gramática sabiendo que todo el código adicional que forma el IDE proporcionará una experiencia completa para la nueva función desde el principio. Mi bifurcación de ANTLR 4 (en el que se basa el objetivo de C #) es la única herramienta que conozco que incluso intenta proporcionar esta función.

Esencialmente, los combinadores de analizador sintáctico son un juguete genial para jugar, pero simplemente no están hechos para hacer un trabajo serio.

Como Karl menciona, los generadores de analizadores tienden a tener mejores informes de errores. Adicionalmente:

• tienden a ser más rápidos, ya que el código generado puede especializarse para la sintaxis y generar tablas de salto para la búsqueda anticipada.
• tienden a tener mejores herramientas, identificar sintaxis ambigua, eliminar la recursividad izquierda, completar ramas de error, etc.
• tienden a manejar mejor las definiciones recursivas.
• tienden a ser más robustos, ya que los generadores han estado más tiempo y hacen más de la placa repetitiva por ti, reduciendo la posibilidad de que la arruines.

Por otro lado, los combinadores tienen sus propias ventajas:

• están en código, por lo que si su sintaxis varía en tiempo de ejecución, puede mutar más fácilmente las cosas.
• tienden a ser más fáciles de vincular y consumir (la producción de generadores de analizadores tiende a ser muy genérica y difícil de usar).
• están en código, por lo que tienden a ser un poco más fáciles de depurar cuando su gramática no hace lo que espera.
• tienden a tener una curva de aprendizaje más superficial ya que funcionan como cualquier otro código. Los generadores de analizadores tienden a tener sus propias peculiaridades para aprender a hacer que las cosas funcionen.