En cierto punto en su carrera, es probable que usted vaya a implementar un lenguaje de programación. Posiblemente no será Java o C #, ya que es posible que usted ni siquiera los reconozca como lenguajes. La verdad sea dicha, hay una cantidad tremenda de lenguajes de dominio-específico o "pequeños lenguajes " [7] de uso común como los siguientes:

archivos de configuración,
documentos HTML/XML,
shell scripts,
protocolos de red,
encabezamientos de correo,
argumentos de comando-líne

La lista es muy extensa e incluye ciertos programas que permiten escribir scripts para controlar su operación; de hecho, el otro día descargué un simulador de red neural que proporcioná un pequeño lenguaje de programación para iniciar la simulación.

Pero, cómo se implementa un lenguaje? Por supuesto se puede usar el acercamiento ad hoc, solamente que esté no es muy adecuado para desarrollar lenguajes de diseño complejo o que requieran cambios frecuentes. Entre otras cosas porque se termina escribiendo código para realizar tareas que pueden ser facilmente automatizadas.

Otro camino es considerar el uso de lenguajes ya existentes como Tcl [18] o Python [6]. Estos lenguajes estan diseñados para ser embebidos en una aplicación existente, o para ser extendidos con facilidad. Esta es una buena solución, que ahorra tiempo y esfuerzo cuando puede ser utilizada. Sin embargo, se debe considerar si desea atar su lenguaje a uno que en sí mismo está cambiando, o tener en cuenta si la sintaxis y la semántica de su lenguaje corresponden o no, con las de estos lenguajes.

Un tercer acercamiento es el de utilizar herramientas de compilación para ejecutar el lenguaje. La mayoría de estas herramientas fueron diseñadas para la implementación de grandes lenguajes de programación, pero estos mismos principios y técnicas se pueden aplicar igualmente en el caso de lenguajes más pequeños. Este artículo discute la historia de una de estas herramientas -- un generador de analizis de sintaxis -- y lo que es más importante, una sugerencia sobre que clase de herramienta lo va a substituir y porque.

El papel del analizador de sintaxis

El analisis de sintaxis es comunmente la segunda fase de la compilación. Primero, un scanner (explorador) realiza un análisis léxico de la información, dividiendola en trozos, lo que constituye basicamento lo mismo que dividir una oración en palabras. Despues el analizador de sintaxis, (el responsable de los temidos errores de sintaxis) revisa la secuencia de estos trozos para verificar si la sintaxis es o no la correcta.

El analizador de sintaxis, controla la sintaxis usando un conjunto de las reglas gramaticales que han sido provistas por el implementador del lenguaje. (para ser exactos, me estoy refiriendo a reglas gramaticales "context-free " o -independientes del contexto- ) Si las reglas se pueden aplicar de manera que se pueda derivar la entrada de información (input), entonces la sintaxis se considera la correcta. En este caso es posible que aun no se obtenga ningún significado coherente , pero por lo menos se sabe que la sintaxis es valida.

La figura 1 muestra una gramática para expresiones aritméticas simples. Una buena manera de pensar en la gramática es entenderla como un conjunto de reglas de substitución: el símbolo en el lado izquierdo de la flecha es una variable, la cual puede ser substituida por lo que sea que exista en el lado derecho [21]. La figura 2 muestra una secuencia de substituciones que derivan la entrada de información n + n. De cierta manera, un analizador de sintaxis debe trabajar al revés, porque su entrada de información (input) es el último paso de esta secuencia de substitución (en este caso, n + n) y el analizador de sintaxis debe adivinar la secuencia de las substituciones que condujeron a esto.

Expression grammar

Figura 1: Expresión gramatical

Derivation

Figura 2: Derivación

El análisis de sintaxis (parsing) es un topico muy bien estudiado, sobre el cual existen muchos y muy buenos libros, que van desde los orientados hacia los compiladores [1, 9] los teoricos [2] hasta los de caracter enciclopédico [12]. Por qué se ha hecho tanto trabajo alrededor de esto? Resulta que no existe solo un algoritmo de análisis sintáctico, sino docenas. Si se piensa en el conjunto de gramáticas "independientes del contexto" como un pie (torta), cada algoritmo de análisis sintáctico se limita a trabajar en gramáticas que pertenecen a una rebanada determinada de el pie (torta). Muchas de las investigaciones en compiladores en los 70s, estuvieron dedicados a rebanar ese pie de diversas maneras muy creativas, combinando una sola pieza de el pie con otras, reorientando los pedazos, y asi sucesivamente.

El objetivo de tanto trabajo era el de generar un algoritmo de análisis sintáctico que fuera una mezcla perfecta entre la potencia expresiva, la velocidad de ejecución, y el ahorro de espacio. Hay que tener en cuenta que en ese momento el costo de recursos que computación era muy alto, en relación con los de programación. Era perfectamente aceptable esperar que un programador, invirtiera mucho tiempo transformando la gramática de manera que fuera adecuada para un eficiente algoritmo. ES en este ambiente que Yacc fue desarrollado.

Yacc

La sigla Yacc [14,16] significa "Yet Another Compiler-Compiler" es decir " Otro Compilador de Compilador " y es lo que ahora sería llamado un generador de analisis de sintaxis (parser generator). Lo que hace Yacc es tomar una gramática como informacion de entrada, y producir código en C, a la vez que genera un analizador de sintaxis para esa misma gramática. Como un implementador de lenguaje usando Yacc, usted hace basicamente dos cosas: proporcionar la gramática de entrada, y después tomar el código C generado por Yacc, compilarlo y conectarlo dentro a su código. Voila! Un analizador instantaneo!

Yacc emergió de los laboratorios Bell a mediados de los anhos setenta, y es indiscutiblemente la herramienta de análisis sintáctico disponible mas exitosa . De ella se se han producido numerosas variantes, como Berkeley Yacc y el bisonte de la fundación de software libre; otras herramientas parecidas se pueden encontrar para la mayori;a de los lenguajes (e.g., el generador del analizador de sintaxis CUP para Java). En este articulo se utiliza el término " Yacc " para significar cualquiera de las herramientas de esta misma familia.

Internamente, Yacc utiliza un algoritmo de análisis sintáctico LALR(1), junto con algunos trucos, que lo dejen aceptar una gama más amplia de gramáticas. Si usted no sabe lo que esto significa, tranquilo no esta solo. El problema básico es que usted debe saber mucho sobre este algoritmo para poder utilizar Yacc de una manera exitosa. Por ejemplo, supongamos que usted desea generar un lenguajede ensamble simple, donde cada línea tenga maximo una opcion de etiqueta, un opcode y un operador opcional. Un programa de este tipo seria algo asi:

    loop:  lda   foo
           shift bar
           halt

Un manera obvia de proceder seri;a comenzar en un nivel alto y descomponer el diseño, usando una gramática como la que se muestra en la Figura 3.

**Figura 3: Gramática del lenguaje de ensamblaje**

**Figura 4: Yacc**

Esta gramática dice que una línea tiene: una marca, un opcode, y un operando; el hecho de que la marca es opcional y puede no estar, es representado por la marca con una cara derecha vacía. El mismo dispositivo se utiliza para los operandos. Esta gramática describe correctamente el lenguaje de ensamblaje que se tiene como ejemplo, sin embargo por sus esfuerzos, Yacc le recompensa con un mensaje de error:

    example.y contains 1 shift/reduce conflict

Qué significa esto? La respuesta se relaciona de nuevo con el LALR(1) mencionado anteriormente -- esencialmente, el algoritmo no puede elegir entre varias acciones en conflicto. Para hacer la historia corta, si usted reescribe su gramática a esta version levemente alterada que se muestra en la figura 4, Yacc lo aceptara sin queja alguna. Pero éste no es necesariamente el objetivo final: Yacc ha producido un analizador de sintaxis que no hace nada además de quejarse amargamente cuando encuentra un error del sintaxis. Para hacerlo realmente útil, usted necesita agregar acciones semánticas.

Las acciones semánticas son trozos de código que pueden asociarse a reglas gramaticales. Cuando el analizador de sintaxis determina que se ha utilizado una regla gramatical, ejecutará la accion(es) semántica(s) asociada(s). En un compilador, usted puede utilizar estas acciones para construir una representación interna de la entrada de información, realizar chequeos semánticos, emitir código, o cualquier otra cosa que usted imagine.

Internamente, Yacc implementa acciones semánticas modificando la gramática. Esa misma gramática que en primer lugar usted ya habia modificado con tanto esfuerzo para que Yacc no reportara ningun error. Agregue una acción semántica en el lugar incorrecto y se encontrará de regreso en el punto de partida.

    example.y contains 1 shift/reduce conflict

Este ejemplo presenta claramente algunos de los defectos importantes de Yacc como herramienta:

Un conocimiento profundo del algoritmo interno de Yacc es necesario para su uso; lo que deja por fuera a una gran cantidad de usuarios ocasionales.
Modificar la gramática para hacerla compatible con Yacc, introduce errores potenciales. Cómo estar seguros que la gramática una vez modificada aun describe el mismo lenguaje anterior?
Las ediciones de mantenimiento también son introducidas por modificaciones en la gramática, ya que la gramática modificada se asemeja a la original cada vez menos.
La productividad se ve afectada como resultado de gastar el tiempo luchando con una herramienta.

La figura 5 da una descripción general del ciclo de desarrollo con Yacc. Para ser justos es necesario reconocer que Yacc proporciona un muy buen mecanismo para descubrir errores cuando se presentan problemas. El algoritmo LALR(1) esta basado en autómatas finitos de estado, y Yacc es muy bueno en dar una interpretación en ASCII del autómata que es muy útil a la hora de resolver errores.

Figura 5: Ciclo de desarrollo Yacc

Sinembargo a estas alturas, usted ya ha invertido una tremenda cantidad de tiempo y ha requerido un conocimiento basto sobre cómo trabaja Yacc para conseguir la validación de su gramática. Las condiciones computacionales han cambiado mucho desde los años 70 -- Es Yacc realmente una herramienta eficaz?

Más allá de Yacc

Para ayudar a contestar a esta pregunta, imaginemos una herramienta que no ponga ninguna restricción en la gramática que se le da. Qué tipo de cosas se pueden hacer con esta herramienta?

Para el caso de principiantes, muchos de los lenguajes de programación comunes se especifican usando gramáticas ambiguas, que están más allá de las capacidades del algoritmo LALR(1) usado por Yacc. Estos incluyen lenguajes como C, C++, y Perl. Como mencioné en la introducción, usted puede no estar implementando un compilador completo para su lenguaje; quizas lo que usted desea sea escribir una herramienta que extraiga declaraciones variables, o código de fuente limpio, o mediciones métricas de la calidad del software. Todos estos trabajos se pueden hacer usando herramientas de análisis.

Muchos de lenguajes de dominio-específicos presentan diseños ad hoc que han ido acumulando differentes características a lo largo de los años , y que no tienen ninguna grámatica simple que los describa y que sea compatible con Yacc. Este es uno de los casos en donde una herramienta más poderosa y de mayor acceso podria ayudar. (Irónicamente, los propios archivos generadas por Yacc se analizan mejor con un analizador de sintaxis mas poderoso que Yacc [14].)

Este tipo de análisis (parsing), se puede considerar también como una forma de encontrar concordancia entre patrones. Esta caracteristica se ha explotado en la generación del código atravez de compiladores: Una gramática (altamente ambigua) especifica qué patrones (o modelos) buscar en el programa de entrada de información, y las acciones semánticas emiten el código al ser ejecutadas [10]. Yo he utilizado una idea similar para decompilar Python nuevamente en código de fuente, lo que no hubiera ni siquiera intentado usando Yacc

Adicionalmente, las gramáticas ambiguas son de gran utilidad en la reingeneria de software [20]; el poder analizar fácilmente programas de herencia es un aspecto clave en este campo. El problema que estos ingenieros enfrentan es: la respuesta correcta a la pregunta " se puede analizar este programa de COBOL? " es : " Sí, pero de que dialecto de COBOL estamos hablando? " Con una gramática ambigua usted puede: especificar múltiples dialectos, posiblemente en conflicto, o tener una especificación gramátical base con la cual componer reglas específicas de acuerdo al dialecto y segun sea necesario. Ah, y cualquier gramatica de ensamblaje funciona sin ningun tipo de modificación

El caso para los algoritmos generales de análisis sintáctico

Cómo pueden las gramáticas generales ser analizadas? En algunos casos, estas grámaticas pueden manipularse para ser analizadas por Yacc usando varios trucos. en cuyo caso se estaria en la misma situacion descrita con anterioridad, sin haber avanzado mucho.

En este caso existen algunos algoritmos de análisis sintáctico que pueden manejar todas las gramática independientemente del contexto, incluidas las ambiguas. Dos de los más prácticos son Earley [8] y LR generalizado (o GLR) [19]. (este ultimo se llama a veces " Tomita ", aunque esta basado en una idea anterior de Lang [15].)

Curiosamente, Earley y los algoritmos generales de análisis sintáctico de tipo GLR son de la misma generación que Yacc y compan~ia: los 70s. La razón principal por la cual no se convirtieron en standard en ese entonces no fue una cuestión de funciones, sino de desempen~o. Para muchos no sera sorpresa el hecho de que un algoritmo general sea más lento que uno mucho especializado. La mayor complejidad, en terminos de tiempo. en el algoritmo de Earley es O(n³), donde n equivale a la longitud de entrada de información [8], algo similar sucede en la peor de las situaciones en GLR donde la inversion en tiempo puede ser aun mayores .

Sin embargo, estas limitaciones se presentan basicamente en los casos mas desesperados. Alimente un algoritmo de análisis sintáctico general con la gramática mas ambigua, más mala, y mas ambiciosa que usted puede pensar y , sin ninguna duda, tomara un rato para reflexionar sobre ello. En casos normales la situacion es absolutamente diferente. Para el caso de La mayoría de las gramáticas, como las de lenguajes de programación, los algoritmos de análisis sintáctico generales mencionados aquí; dan un funcionamiento tan eficaz como Yacc.

Aun asi, los análisis de complejidad abstraen y dejan por fuera muchos detalles. En práctica, los algoritmos de análisis sintáctico generales tienen una contabilidad mas alta que los especializados, y se ejecutan mucho más lentamente [12]. a pesar de esto, existen dos razones para considerar el uso de un algoritmo de análisis sintáctico general:

Investigaciones actuales estan haciendo estos algoritmos mucho más rápidos [3,4, 5,11, 17]. Por ejemplo, mi colega y yo hemos logrado recientemente que un analizador de sintaxis de Earley sea ejecutado en un tiempo comparable al del bisonte Yacc.
Estos ya no son los 70s! Su tiempo y productividad cuestan mucho más que cualquier ordenador! Para que ahorrar todos esos ciclos de CPU?

Su siguiente herramienta de análisis sintáctico

En la actualidad se pueden encontrar varias herramientas (libres) que emplean algoritmos de ananálisis sintáctico de tipo general:

ACCENT, una herramienta de análisis sintáctico de tipo Earley, a lo largo de las mismas líneas de Yacc.
SPARK, Un set de exploración, analisis y reescritura. Proporciona soporte para la compilación de lenguajes de dominio, usualmente de pequenha escala en Python, aunque ha sido usado en projectos mas grandes. Usa una logoritmo de tipo Early para el análisis.
ASF+SDF, un set de herramientas para el procesamiento de lenguaje. Usa análisis GRL.

El hecho de que cada una de la herramientas anteriores debe proporcionar un cierto mecanismo para manejar la ambigúedad gramatical, las hace perceptiblemente diferentes del grupo Yacc. Es decir, cuando hay mas de una manera de interpretar la entrada de información, debe ser posible decirle a la herramienta la manera en que usted esta interesado en que lo haga. Desafortunadamente, no hay manera de decir si una gramática arbitraria es ambigua o no [13], de manera que usted tendrá que confiar en la prueba final para identificar y solucionar los problemas. Yo no he encontrado que en la práctica esto sea un gran problema.

Otra diferencia importante, especialmente si esta acostumbrado a utilizar herramientas más tradicionales como Yacc, es la facilidad de uso de estas herramientas basadas en algoritmos de análisis generales. Usted introduce su gramática y ellas funcionan. No es necesario gastar demasiado tiempo peleando con detalles, una vez hecho esto usted puede continuar con su siguiente tarea sin mayores contratiempos, como se supone debe ser una buena herramienta.

Conclusión

La moraleja de esta historia es muy clara. Herramientas diseñadas para una era de computación pueden no ser la mejor opción para otra. La elección de herramientas es una opción que debe ser reevaluada periódicamente. En este caso determinado, tiene sentido comenzar a alejarse de herramientas anticuadas como Yacc, con su algoritmo de análisis sintáctico especializado. Las herramientas de análisis sintáctico que usan algoritmos más generales permiten un desarrollo más fácil y un mantenimiento más simple, eliminan una clase de errores, y permiten que nuevos usuarios hagan uso de ellas.

Hace doscientos anhos, el bisonte, o buffalo, vagaba por Norteamérica en grandes manadas. Los colonos que llegaron los cazaron hasta casi la extinción. En contraste, hoy en dia la extinción de este otro bisonte, el Yacc, no debe ser razón para arrepentirse; es simplemente una cuestión de elegir herramientas más eficaces y de mayor alcance.

Agradecimientos

Nigel Horspool y Shannon Jaeger hicieóon comentarios muy valiosos en versiones de borrador de este artículo, lo mismo que Amie Souter y otros evaluadores anonimos.

Referencias

1: Aho, A.V., Sethi, R., and Ullman, J.D. Compilers: Principles, Techniques, and Tools. Addison-Wesley, 1986.
2: Aho, A.V., and Ullman, J.D. The Theory of Parsing, Translation, and Compiling, Volume 1: Parsing. Prentice-Hall, 1972.
3: Aycock, J., and Horspool, N. Faster generalized LR parsing. In Proceedings of the 8th International Conference on Compiler Construction (LNCS #1575). Springer-Verlag, 1999, pp. 32-46.
4: Aycock, J., and Horspool, N. Directly-executable Earley parsing. In Proceedings of the 10th International Conference on Compiler Construction (LNCS #2027). Springer-Verlag, 2001, pp. 229-243.
5: Aycock, J., Horspool, N., Janousek, J., and Melichar, B. Even faster generalized LR parsing. To appear in Acta Informatica.
6: Beazley, D. Python Essential Reference. New Riders, 1999.
7: Bentley, J. Little languages. In More Programming Pearls. Addison-Wesley, 1988, pp. 83-100.
8: Earley, J. An efficient context-free parsing algorithm. Communications of the ACM 13, 2 (Feb. 1970), 94-102.
9: Fischer, C.N., and LeBlanc Jr., R.J. Crafting a Compiler. Benjamin/Cummings, 1988.
10: Glanville, R.S., and Graham, S.L. A new method for compiler code generation. In 5th Annual ACM Symposium on Principles of Programming Languages. ACM/SIGPLAN, 1978, pp. 231-240.
11: Graham, S.L., Harrison, A.M., and Ruzzo, W.L. An improved context-free recognizer. ACM Transactions on Programming Languages and Systems 2, 3 (1980), 415-462.
12: Grune, D., and Jacobs, C.J.H. Parsing Techniques: A Practical Guide. Ellis Horwood, 1990.
13: Hopcroft, J.E., and Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 1979.
14: Johnson, S.C. YACC -- yet another compiler compiler. UNIX Programmer's Manual, 7th Edition, 2B, 1978.
15: Lang, B. Deterministic techniques for efficient non-deterministic parsers. In Automata, Languages, and Programming (LNCS #14). Springer-Verlag, 1974, pp. 255-269.
16: Levine, J.R., Mason, T., and Brown, D. Lex & Yacc, second edition. O'Reilly & Associates, 1992.
17: McLean, P., and Horspool, R.N. A faster Earley parser. In Proceedings of the International Conference on Compiler Construction (CC '96). Spring-Verlag, 1996, pp. 281-293.
18: Ousterhout, J.K. Tcl and the Tk Toolkit. Addison-Wesley, 1994.
19: Tomita, M. Efficient Parsing for Natural Languages. Kluwer Academic, 1986.
20: van den Brand, M., Sellink, A., and Verhoef, C. Current parsing technologies in software renovation considered harmful. In International Workshop on Program Comprehension, 1998, pp. 108-117.
21: Weingarten, F.W. Translation of Computer Languages. Holden-Day, 1973.

John Aycock (aycock@csc.uvic.ca) es estudiante de Phd en el departamento de la informática de la Universidad de Victoria. Ha sido usuario de Yacc por cerca de diez años. Sus intereses de investigación incluyen compiladores y lenguajes de programación; el tema de su tesis son los algoritmos generales de análisis sintáctico.

Last Modified: Thursday, 19-Jul-2001 19:22:15 EDT
Location: www.acm.org/crossroads/espanol/xrds7-5/bison.html

00606