Linux

Generador de analizadores sint´cticos BISON a

PROCESADORES DE LENGUAJES 4o Inform´tica a http://ccia.ei.uvigo.es/docencia/PL noviembre-2008

– 2008 ccia PL –

1. Introducci´n o

Traduce la especificaci´n de una gram´tica de contexto libre a un o a programa en C que implementa un analizador LALR(1) para esa gram´tica. a
• analizador ascendente de desplazamiento-reducci´n. o

Permiteasociar c´digo C (acciones sem´nticas) a las reglas de la o a gram´tica a
• se ejecutar´ cada vez que se aplique la regla correspondiente a

Esquema de funcionamiento:
fichero.y ---> BISON ---> fichero.tab.c fichero.tab.c + (ficheros .c) ---> GCC | |-- main() |-- yyerror() |-- yylex() ---> ejecutable

Compilaci´n: o $ bison fichero.y
Compila la especificaci´n de la gram´tica y crea el ficherofichero.tab.c con el o a c´digo y las tablas del analizador LALR(1) o

$ gcc fichero.tab.c (ficheros .c)
El usuario debe proporcinar las funciones main(), yyerror() y yylex() . El c´digo de o usuario deber´ llamar a la funci´n yyparse(), desde la cual se llamar´ a la funci´n a o a o yylex() del analizador l´xico cada vez que necesite un token. e

Opciones:
bison -d genera "fichero.tab.h"con las definiciones de las constantes asociadas a los tokens, adem´s de variables y estrucutras de datos necesarias para el analizador a l´xico. e bison -v genera "fichero.output" con un resumen legible del aut´mata LALR(1) o y se˜ala los conflictos y/o errores presentes en la gram´tica de entrada n a

– 2008 ccia PL –

1

2. Funcionamiento del analizador

El fichero "XXXX.tab.c" continelas tablas del analizador y la funci´n int yyparse(void) o
• yyparse() simula el analizador LALR(1) • devolver´ 0 si el an´lisis tuvo ´xito y 1 si el an´lisis fallo a a e a • deber´ de ser llamada desde el c´digo del usuario a o

Cada vez que yyparse() necesite un nuevo token, llamar´ a la a funci´n int yylex() o
• yylex() devuelve un no entero que identifica al siguiente token • esas constantesenteras aparecen en el fichero "XXXX.tab.h" • yylex() devolver´ el token eof (end of file) cuando alcance el final del fichero a

Para comunicar los atributos de los tokens se usa la variable global yylval
• es de tipo yystype y est´ declarada en "XXXX.tab.h" a • yylex() escribe en yylval los valores que despu´s usar´ yyparse() e a

La funci´n yyparse() realiza un an´lisis ascendentesalto-reducci´n o a o
• agrupa tokens y no terminales seg´n a las reglas de la gram´tica u a • utiliza una pila donde acumula s´ ımbolos • cuando en la cima de la pila se localiza el lado derecho de una regla, se eliminar´n de la pila y se meter´ en ella el no terminal del lado derecho de la a a ´ regla. (REDUCCION)

Por regla general el c´digo asociado a una regla (acciones sem´ntio a cas) se ejecutar´en el momento en que se reduzca la regla a
• es posible incluir c´digo en mitad de la parte derecha de las reglas o • a cada elemento de la pila se le asocia asociada una variable de tipo yystype • el c´digo de las acciones sem´nticas puede acceder a esas varibles usando las o a pseudo-variables $$, $1, $2, $3, . . .

– 2008 ccia PL –

2

3. Especificaci´n de gram´ticas en BISON o a
3partes separadas por s´ ımbolo "%%" (2 primeras obligatorias, pueden ir vac´ ıas)
o %% o %% o

(a) Secci´n de Declaraciones. o
C´digo C necesario para las acciones sem´nticas. o a • Ir´ entre los s´ a ımbolos "%{" y "%}" (se copia tal cual en "XXXX.tab.c") • Generalmente ser´n #includes y/o estructuras y variables a Definiciones de BISON. 1. Especificaci´n de yystype (tipo de los valoressem´nticos) o a • tipo de datos asociado a los elementos de la pila (tokens y no terminales) • se usa la directiva %union XXXX.Y XXXX.TAB.H / XXXX.TAB.C %union { int entero; double real; char * texto; } typedef union { int entero; double real; char * texto; } YYSTYPE;

2. Especificaci´n de tokens y de sus propiedades (asociatividad, precedencia) o • directiva %token: indica el nombre de un token y...