Yacc

Diseño de Compiladores I
YACC

Introducción:

Yacc provee una herramienta general para analizar estructuralmente una entrada. El usuario de Yacc prepara una especificación que incluye:
un conjunto de reglas que describen los elementos de la entrada
un código a ser invocado cuando una regla es reconocida
una o más rutinas para examinar la entrada
Luego Yacc convierte la especificación en unafunción en C que examina la entrada. Esta función, un parser, trabaja mediante la invocación de un analizador léxico que extrae tokens de la entrada. Los tokens son comparados con las reglas de construcción de la entrada, llamadas reglas gramaticales. Cuando una de las reglas es reconocida, el código provisto por el usuario para esa regla (una acción) es invocado. Las acciones son fragmentos decódigo C, que pueden retornar valores y usar los valores retornados por otras acciones.
Tanto el analizador léxico como el sintáctico pueden ser escritos en cualquier lenguaje de programación. A pesar de la habilidad de tales lenguajes de propósito general como C, lex y yacc son más flexibles y mucho menos complejos de usar.
Lex genera el código C para un analizador léxico, y yacc genera el códigopara un parser. Tanto lex como yacc toman como entrada un archivo de especificaciones que es típicamente más corto que un programa hecho a medida y más fácil de leer y entender. Por convención, la extensión del archivo de las especificaciones para lex es .l y para yacc es .y. La salida de lex y yacc es código fuente C. Lex crea una rutina llamada yylex en un archivo llamado lexyy.c. Yacc crea unarutina llamada yyparse en un archivo llamado y_tab.c.
Estas rutinas son combinadas con código fuente C provisto por el usuario, que se ubica típicamente en un archivo separado pero puede ser ubicado en el archivo de especificaciones de yacc. El código provisto por el usuario consiste de una rutina main que llama a yyparse, que en su momento, llama a yylex. Todas estas rutinas deben ser compiladas, yen la mayoría de los casos, las librerías lex y yacc deben ser cargadas en tiempo de compilación. Estas librerías contienen un número de rutinas de soporte que son requeridas, si no son provistas por el usuario.
El siguiente diagrama permite observar los pasos en el desarrollo de un compilador usando lex y yacc:

















Los elementos de una gramática

La sintaxis de un programa puede serdefinida por una gramática libre de contexto. Ésta es esencialmente una estructura jerárquica que indica las relaciones de las construcciones del lenguaje. La notación más común usada para describir una gramática libre de contexto es BNF. La especificación de YACC se hace en BNF.
La descripción se hace en la forma de reglas de producción, que consisten de un nombre de no terminal, el ladoizquierdo, seguido por su definición. La definición, o lado derecho, consiste de cero a más símbolos que son no terminales que apuntan a otras reglas o terminales que corresponden a tokens. Por ejemplo, una gramática simple:
lista ¬ objeto | lista objeto
objeto ¬ cadena | numero
cadena ¬ texto | comentario | comando
numero ¬ numero | ´+´ numero | ´-´ numero | numero ´.´ numero

En este ejemplo, laspalabras en negrita representan los terminales y el resto los no terminales. La primera regla establece que una lista se forma de un objeto o de una lista y un objeto.
La segunda forma de la regla es una definición recursiva. Esto permite que un concepto complejo, como una lista, sea descripto en una forma compacta. Puesto que no sabemos de antemano cuántos elementos formarán la lista, nopodríamos definirla convenientemente sin esta forma recursiva. Así, se establece que una lista es una secuencia de objetos, uno después de otro. Si quisiéramos describir una lista separada por comas, la regla sería:
lista ¬ objeto | lista ´,´ objeto

| es un operador de unión. Notar por ejemplo, su uso en la última regla. Así, un número es o un numero, o un numero con un mas (+) adelante, un numero...