3.8 Generadores de Analizadores Sintácticos

Esta sección muestra cómo utilizar un generador de analizadores sintácticos para facilitar la construcción de la etapa inicial de un compilador. El generador de analizadores sintácticos LALR YACC se usará como base de esta exposición, puesto que implanta muchos de los conceptos estudiados en las dos secciones anteriores y es fácil de encontrar. YACC significa "otro compilador de compiladores más" (del inglés Yet Another Compiler-Compiler), lo que refleja la popularidad de los generadores de analizadores sintácticos al principio de los años setenta, cuando S. C. John son creó la primera versión de YACC. Este generador se encuentra disponible como una orden del sistema UNIX, y se ba utilizado para facilitar la implantación de cientos de compiladores.

El generador de analizadores sintácticos YACC Se puede construir un traductor utilizando Y ACC de la forma que se ilustra en la figura. Primero, se prepara un archivo, por ejemplo traduce. y, que contiene una especificación en YACC del traductor. La orden del sistema UNIX Yacc traduce y transforma al archivo traduce, y en un programa escrito en C llamado y .tab.c usando el método LALR. El programa y. tab. c es una representación de un analizador sintáctico escrito en C, junto con otras rutinas en C que el usuario pudo haber preparado. La tabla de análisis sintáctico LALR se comprime, al compilar y. tab. c junto con la biblioteca ly que contiene el programa de análisis sintáctico LR utilizando la orden cc y. tab.c–ly se obtiene el programa objeto deseado a. out que realiza la traducción especificada por el programa original en Y ACC!'. Si se necesitan otros procedimientos, se pueden compilar o cargar con y. tab. e, igual que en cualquier programa en C.

Un programa fuente en YACC tiene tres partes:

Declaraciones

-------------------------------

reglas de traducción

--------------------------------

rutinas en C de apoyo

• De estas tres secciones, sólo la segunda es obligatoria, y no debe estar vacía (nótese que en lex, las tres secciones pueden estar vacías). Esto quiere decir que el mínimo programa en yacc es:

regla gramatical      acción en C

•  La sección de declaraciones puede incluir varias cosas, tal y como ocurría en lex, pero ahora su función principal no es definir expresiones regulares, sino declarar los símbolos terminales de la gramática mediante la directriz %token. Todo lo que no sea un terminal, será considerado un símbolo no terminal, y por tanto debe haber una regla para él:

 token                              IF,ELSE,LLAVE_AB,LLAVE_CE,IDENT

• La sección de reglas contiene la gramática en sí. Componentes es una combinación de terminales y no terminales que describe al no terminal de la izquierda de la regla:

no_terminal:                    componentes                   {acciones en C} 

• La sección de rutinas tiene la misma función que la de lex, pero yacc (dependiendo de su variante) no define por defecto las funciones main(), yylex() e yyerror(), así que hay que incluirlas aquí, o bien en otro fichero que se enlazará en la fase final de la compilación.

Yacc genera una función llamada yyparse() que contiene el analizador sintáctico. Esta función se comporta como una máquina de estados cuya misión es intentar reducir todo el fichero de entrada al símbolo inicial de la gramática (el primero que se haya definido). Si yacc lo consigue, el analizador sintáctico volverá sin error, y en caso contrario, se invocará a la función y yerror(), que debe estar definida también en algún sitio.