parsing - compilers - lr parser
¿Por qué algunos compiladores prefieren el analizador hecho a mano sobre los generadores de analizador? (5)
De acuerdo con la documentación de Vala: "Antes del 0.3.1, el analizador de Vala era el clásico escáner flexible y la combinación del analizador Bison LALR. Pero a partir de commit eba85a , el analizador es un analizador de descenso recursivo hecho a mano". Mi pregunta es: ¿por qué?
La pregunta podría dirigirse a cualquier compilador que no esté utilizando el generador de analizador. ¿Cuáles son los pros y los contras de un cambio de este tipo desde el generador de analizador hasta el analizador hecho a mano? ¿Cuáles son las desventajas de usar generadores de analizadores (Bison, ANTLR) para compiladores?
Como comentario adicional: estoy interesado en Vala específicamente porque me gusta la idea de tener un lenguaje con características modernas y sintaxis limpia pero compilable en lenguaje de alto nivel "nativo" y "no administrado" (C en el caso de Vala). Sólo he encontrado a Vala hasta ahora. Estoy pensando en divertirme haciendo que Vala (o un lenguaje similar) sea compilable a C ++ (respaldado por Qt libs). Pero como no quiero inventar un lenguaje completamente nuevo, estoy pensando en tomar algo de gramática existente. Obviamente, los analizadores hechos a mano no tienen gramática formal escrita que pueda reutilizar. Sus comentarios sobre esta idea son bienvenidos (¿es una idea tonta?).
De acuerdo con la documentación de Vala: "Antes de la versión 0.3.1, el analizador de Vala era el clásico escáner flexible y la combinación del analizador Bison LALR. Pero a partir de Commit eba85a, el analizador es un analizador de descenso recursivo hecho a mano". Mi pregunta es: ¿por qué?
Aquí estoy preguntando específicamente acerca de Vala, aunque la pregunta podría dirigirse a cualquier compilador que no esté utilizando el generador de analizador. ¿Cuáles son los pros y los contras de un cambio de este tipo desde el generador de analizador hasta el analizador artesanal? ¿Cuáles son las desventajas de usar generadores de analizadores (Bison, ANTLR) para compiladores?
Tal vez los programadores descubrieron algunas vías de optimización que el generador de analizador no detectó, y estas vías de optimización requerían un algoritmo de análisis completamente diferente. Alternativamente, quizás el generador de analizador generó código en C89, y los programadores decidieron que la refactorización para C99 o C11 mejoraría la legibilidad.
Como comentario adicional: estoy interesado en Vala específicamente porque me gusta la idea de tener un lenguaje con características modernas y sintaxis limpia pero compilable en lenguaje de alto nivel "nativo" y "no administrado" (C en el caso de Vala).
Solo una nota rápida: C no es nativo . Tiene sus raíces en la portabilidad , ya que fue diseñado para abstraer los detalles específicos del hardware / sistema operativo que causaron mucho dolor a los programadores al realizar la migración. Por ejemplo, piense en el dolor de usar un sistema completamente diferente para cada sistema operativo y / o sistema de archivos; No solo me refiero a la funcionalidad diferente , sino también a las expectativas de entrada y salida, por ejemplo. Diferentes argumentos, diferentes valores de retorno . Del mismo modo, C11 introduce hilos portátiles; El código que utiliza subprocesos podrá usar el mismo código compatible con C11 para apuntar a todos los sistemas operativos que implementan subprocesos.
He encontrado a Vala hasta ahora. Estoy pensando en divertirme haciendo que Vala (o un lenguaje similar) sea compilable a C ++ (respaldado por Qt libs). Pero como no quiero inventar un lenguaje completamente nuevo, estoy pensando en tomar algo de gramática existente. Obviamente, los analizadores hechos a mano no tienen gramática formal escrita que pueda reutilizar. Sus comentarios sobre esta idea son bienvenidos (¿es una idea tonta?).
Puede ser factible utilizar el analizador hecho a mano para producir código C ++ con poco esfuerzo, por lo que no descartaría esta opción tan rápidamente; El viejo generador de analizador flex / bison puede o no ser más útil. Sin embargo, esta no es tu única opción. En cualquier caso, me sentiría tentado a estudiar la especificación exhaustivamente.
Es curioso que estos autores pasaran del bisonte al RD. La mayoría de la gente iría en la dirección opuesta.
La única razón real por la que puedo ver lo que hicieron los autores de Vala sería una mejor recuperación de errores, o tal vez su gramática no sea muy limpia.
Creo que encontrará que la mayoría de los idiomas nuevos comienzan con analizadores escritos a mano, ya que los autores tienen una idea de su propio idioma nuevo y descubren qué es lo que quieren hacer. También en algunos casos a medida que los autores aprenden a escribir compiladores. C es un ejemplo clásico, como es C ++. Más adelante en la evolución se puede sustituir un analizador generado. Los compiladores para lenguajes estándar existentes, por otro lado, pueden desarrollarse más rápidamente a través de un generador de analizador, posiblemente incluso a través de una gramática existente: el tiempo de comercialización es un parámetro comercial crítico de estos proyectos.
He escrito media docena de analizadores sintéticos hechos a mano (en la mayoría de los casos, analizador de descendencia recursiva, también conocido como analizador de arriba hacia abajo) en mi carrera y he visto analizadores generados por generadores de analizadores y debo admitir que estoy predispuesto a los generadores de analizadores.
Aquí hay algunos pros y contras para cada enfoque.
Generadores de analizador
Pros:
- Obtenga rápidamente un analizador funcional (al menos si no sabe cómo codificarlo manualmente).
Contras:
- El código generado es difícil de entender y depurar.
- Difícil de implementar el manejo adecuado de errores. El generador creará un analizador correcto para el código sintácticamente correcto, pero se ahogará con el código incorrecto y en la mayoría de los casos no podrá proporcionar los mensajes de error adecuados.
- Un error en el generador de analizador puede detener su proyecto. Debe corregir el error en el código de otra persona (si el código fuente está disponible), esperar a que el autor lo solucione o solucionar el error (si es posible).
Analizador artesanal de descenso recursivo
Pros:
- El código generado es fácil de entender. Los analizadores recursivos generalmente tienen una función correspondiente a cada construcción de lenguaje, por ejemplo, parseWhile para analizar una declaración ''while'', parseDeclaration para analizar una declaración y así sucesivamente. Comprender y depurar el analizador es fácil.
- Es fácil proporcionar mensajes de error significativos, recuperarse de los errores y continuar el análisis de la forma que tenga más sentido en una situación particular.
Contras:
Tomará algún tiempo codificar manualmente el analizador, especialmente si no tiene experiencia con estas cosas.
El analizador puede ser algo lento. Esto se aplica a todos los analizadores recursivos, no solo a los escritos a mano. Al tener una función correspondiente a cada construcción de lenguaje para analizar un literal numérico simple, el analizador puede hacer una docena o más de llamadas anidadas comenzando desde, por ejemplo, parseExpression a través de parseAddition, parseMultiplication, etc. parseLiteral. Las llamadas a funciones son relativamente baratas en un lenguaje como C pero aún así pueden llegar a un tiempo significativo.
Una solución para acelerar un analizador recursivo es reemplazar partes de su analizador recursivo por un sub-analizador de abajo hacia arriba que a menudo es mucho más rápido. Los candidatos naturales para dicho sub-analizador son las expresiones que tienen una sintaxis casi uniforme (es decir, expresiones binarias y unarias) con varios niveles de precedencia. El analizador de abajo hacia arriba para una expresión generalmente también es fácil de codificar a mano, a menudo es solo un bucle que recibe tokens de entrada del lexer, una pila de valores y una tabla de búsqueda de precedencia de operadores para tokens de operador.
Los analizadores de LR (1) y LALR (1) son realmente molestos por dos razones:
- El generador de analizador no es muy bueno para producir mensajes de error útiles.
- Ciertos tipos de ambigüedad, como los bloques de estilo C de if-else, hacen que escribir la gramática sea muy doloroso.
Por otro lado, la gramática LL (1) es mucho mejor en estas dos cosas. La estructura de las gramáticas LL (1) hace que sean muy fáciles de codificar como analizadores de descendencia recursivos, por lo que tratar con un generador de analizador no es realmente una victoria.
Además, en el caso de Vala, el analizador y el compilador se presentan como una biblioteca, de modo que puede crear un backend personalizado para el compilador de Vala utilizando la biblioteca del compilador de Vala y obtener todo el análisis y la comprobación de tipos, entre otros.
Sé que esto no va a ser definitivo, y si sus preguntas no estuvieran específicamente relacionadas con Vala, no me molestaría, pero como son ...
No estaba demasiado involucrado con el proyecto en ese entonces, así que no tengo muy en claro algunos detalles, pero la gran razón que recuerdo de cuando Vala cambió fue de dogfooding . No estoy seguro de que fuera la motivación principal, pero sí recuerdo que fue un factor.
La mantenibilidad también fue un problema. Ese parche reemplazó un analizador más grande escrito en C / Bison / YACC (relativamente pocas personas tienen experiencia significativa con los dos últimos) con un analizador más pequeño en Vala (que casi cualquier persona interesada en trabajar en Valac probablemente conozca y se sienta cómodo).
Mejor reporte de errores fue también un objetivo, IIRC.
No sé si fue un factor en absoluto, pero el analizador escrito a mano es un analizador de descenso recursivo. Sé que ANTLR los genera, el ANTLR está escrito en Java, que es una dependencia bastante pesada (sí, sé que no es una dependencia en tiempo de ejecución, pero aún así).
Como comentario adicional: estoy interesado en Vala específicamente porque me gusta la idea de tener un lenguaje con características modernas y sintaxis limpia pero compilable en lenguaje de alto nivel "nativo" y "no administrado" (C en el caso de Vala). Sólo he encontrado a Vala hasta ahora. Estoy pensando en divertirme haciendo que Vala (o un lenguaje similar) sea compilable a C ++ (respaldado por Qt libs). Pero como no quiero inventar un lenguaje completamente nuevo, estoy pensando en tomar algo de gramática existente. Obviamente, los analizadores hechos a mano no tienen gramática formal escrita que pueda reutilizar. Sus comentarios sobre esta idea son bienvenidos (¿es una idea tonta?).
Mucho de Vala es realmente un reflejo de las decisiones tomadas por GObject, y las cosas pueden o no funcionar de la misma manera en C ++ / Qt. Si su objetivo es reemplazar GObject / C en valac con Qt / C ++, es probable que tenga más trabajo del que espera. Sin embargo, si solo desea que las bibliotecas de C ++ y Qt sean accesibles desde Vala, eso debería ser posible. De hecho, Luca Bruno comenzó a trabajar en eso hace aproximadamente un año (vea la sucursal wip/cpp ). No ha visto actividad por un tiempo debido a la falta de tiempo, no a problemas técnicos.