Los generadores de parsers también pueden producir buenos errores.
(dalinaum.github.io)Traducción de un artículo publicado en 2010 por Russ Cox, desarrollador del lenguaje Go.
-
Existía el mito de que los generadores de sintaxis como yacc no podían producir bien los errores de sintaxis.
-
Pero este problema ya había sido resuelto por Clinton Jeffery en 2003, y no es algo que requiera escribir el parser a mano.
-
Si se busca en una tabla el contenido que coincide con el estado (bison) y el token de entrada, se pueden usar errores mejores que un simple error de sintaxis.
3 comentarios
(A continuación, resumí lo que escribí en el servidor coreano de Discord de Rust.)
El mayor problema de este texto es si entonces Go usa actualmente un generador de analizadores sintácticos. No. El analizador principal de Go sigue estando escrito a mano. No sé bien la razón, pero es muy probable que, aunque a rsc le pareciera bien, otros desarrolladores de Go no hayan pensado lo mismo.
La idea de Jeffrey, si la comparamos con compiladores, se puede comparar con un peephole optimizer. Antes de emitir código máquina, se conserva una cantidad fija de las instrucciones de código máquina emitidas más recientemente (de ahí el nombre: se mira por una pequeña "mirilla", un peep hole, dentro de esa ventana) y, si aparece cierto patrón, en ese mismo momento esas instrucciones se sustituyen por otras más rápidas. Un peephole optimizer es una herramienta conveniente que puede usarse junto con otros pases de optimización más generales, pero no puede, por sí solo, realizar todos los tipos de optimización que requiere un compilador. Del mismo modo, el enfoque de generar errores a partir de los tokens recientes no puede cubrir todos los errores de parsing. Además, es un enfoque independiente que puede aplicarse incluso sin que haya un generador de analizadores sintácticos, así que no es correcto afirmar que, por el solo hecho de que exista este enfoque, desaparecen los problemas de los generadores de analizadores sintácticos.
Personalmente, no creo que el concepto de generador de analizadores sintácticos sea malo, sino que el problema está en la forma de pensar que el generador de analizadores sintácticos "impone". Cuando uno escribe un parser, ya sea generado o escrito a mano, tiene que considerar, por ejemplo, la recursión izquierda y la recursión derecha, y no puede simplemente convertir una gramática "natural" en código tal cual. Pero cuando se escribe a mano, eso se hace aceptando ese costo; si al usar un generador de analizadores sintácticos de todos modos hay que escribirlo ajustándose a un subconjunto de la "gramática" atado a algoritmos de parsing específicos como LL/LR, entonces las ventajas del generador se reducen a la mitad. (Algoritmos como GLR dan un poco más de margen, pero tienen límites). Hay una razón por la que, en la actualidad, la mayoría de las implementaciones de lenguajes a nivel de producción no usan generadores de analizadores sintácticos o, en algunos casos, usan enfoques como PEG que, aunque técnicamente son generadores de analizadores sintácticos, para nada aprovechan las ventajas de un generador general.
Entiendo el punto de no usar generadores de parsers porque no quieres quedar atado a la gramática que imponen, pero aun así me parece raro afirmar que los generadores de parsers le están imponiendo una gramática específica al usuario.
Los generadores de parsers surgieron para ayudar con la creación de tablas de parsing para gramáticas LR, que tienen la ventaja del parsing en tiempo lineal porque hacerlo a mano es demasiado difícil; generar parsers recursivos para gramáticas context-sensitive no deterministas, o parsers recursivos en los que ni siquiera sabes cuándo va a terminar el parsing, probablemente no sea algo que interese a quienes investigan o desarrollan generadores de parsers.
Por eso, creo que un generador de parsers no es un programa que idolatra e impone gramáticas LR o LALR poco intuitivas, sino una herramienta que cumple bien su papel al resolver el problema tan difícil del parsing en tiempo lineal y de la construcción de las tablas de parsing necesarias para lograrlo.
Casi todos los lenguajes que podemos ver en la práctica tienen una gramática LL(1), así que es posible hacer parsing en tiempo lineal sin usar un parser LR. (Esto no significa que la gramática preferida para ese lenguaje sea LL(1).) Por lo tanto, decir que para lograr parsing en tiempo lineal hay que usar un parser LR y que se necesita un generador porque es difícil construir la tabla de parsing invierte el orden lógico de las cosas. Además, el proceso mismo de construir la tabla de parsing no es esencialmente complejo (lo difícil es demostrar el algoritmo).