tema: generación de analizadores con yacc · para una calculadora simple, con las operaciones...
TRANSCRIPT
1 Compiladores. Guía 5
Tema: Generación de analizadores con YACC
En esta guía se expondrá la forma de generar el
analizador léxico y sintáctico a través de la
herramienta de YACC y LEX.
Aprender a utilizar la herramienta de YACC para la
generación de analizadores sintácticos.
Conocer la sintaxis de LEX y YACC para la generación de
analizadores léxicos y sintácticos.
Guía de Laboratorio Nº 5.
Parser Generator http://www.bumblebeesoftware.com/.
Libro “Construcción de compiladores” de Kenneth C.
Louden.
YACC: Generación de analizadores sintácticos LR
Un generador de analizadores sintácticos es un programa que
toma como su entrada una especificación de la sintaxis de un
lenguaje en alguna forma, y produce como su salida un
procedimiento de análisis sintáctico para ese lenguaje.
Históricamente los generadores de analizadores sintácticos
fueron llamados compiladores de compilador, debido a que
todos los pasos de compilación eran realizados de manera
tradicional como acciones incluidas dentro del analizador
Introducción Teórica
Guía 3
Guía 4
fía
Facultad: Ingeniería
Escuela: Computación
Asignatura: Compiladores
Contenido
Objetivos Específicos
Material y Equipo
Compiladores. Guía 5
2
sintáctico. La visión moderna es considerar al analizador
como solo una parte del proceso de compilación, de modo que
este término se volvió obsoleto.
Un generador de analizadores sintácticos ampliamente
utilizado que incorpora el algoritmo de análisis sintáctico
LR(1) se conoce como Yacc (Yet Anoter Compiler- Compiler es
decir, “otro compilador de compilador mas” en ingles).
Fundamentos de YACC
YACC toma un archivo de especificación (por lo regular con
sufijo .y) y produce un archivo de salida compuesto del
código fuente en C para el analizador sintáctico (por lo
general con sufijo .tab.c). Un archivo de especificación de
YACC tiene el formato básico
<sección de definiciones>
%%
<sección de reglas>
%%
<sección de rutinas>
De este modo existen tres secciones separadas mediante líneas
que contienen doble signo de porcentaje.
La sección de definiciones contiene información acerca de los
tokens, tipos de datos y reglas gramaticales que YACC
necesita para construir el analizador sintáctico. También
incluye cualquier código en C que debería ir directamente en
el archivo de salida a su inicio (sobre todo directivas
#include de otros archivos de código fuente). Esta sección
del archivo de especificación puede estar vacía.
La sección de reglas contiene reglas gramaticales en una
forma BNF modificada, junto con acciones en código C que se
ejecutaran siempre que se reconozca la regla gramatical
asociada. Las convenciones de meta símbolos utilizadas en
reglas gramaticales son de la manera siguiente. Como es
habitual, la barra vertical se utiliza para las alternativas
(las alternativas también se pueden escribir por separado).
El símbolo flecha “→” que hemos empleado para separar el lado
izquierdo y derecho de una regla gramatical se reemplaza en
YACC por un signo de dos puntos. También un signo de punto y
coma debe finalizar cada regla gramatical.
Compiladores. Guía 5
3
La tercera sección, de rutinas auxiliares, contiene
declaraciones de procedimientos y funciones que de otra
manera pueden no estar disponibles a través de archivos
#include y que son necesarias para completar el analizador
sintáctico y/o el compilador.
Esta sección puede estar vacía, y si este es el caso se puede
omitir el segundo meta símbolo de porcentaje doble del
archivo de especificación. De esta manera, un archivo de
especificación mínimo de YACC consistiría solo de %% seguidos
por reglas gramaticales y acciones (las acciones también se
pueden omitir si solo tratamos de analizar la gramática).
YACC también permite insertar comentarios al estilo de C en
el archivo de especificación en cualquier punto donde no
interfieran con el formato básico.La primera sección que
incluye las directivas #include se encierra entre los
símbolos %{ y %} nótese que los signos de porcentaje se
anteponen a las llaves.
Para definir un token se realiza así: %token nombreToken
Si se desea inicializar como una variable deberá colocarse el
valor numérico a continuación del nombre del token.
En la segunda sección, las reglas gramaticales se colocan
así: expresión: expresión términos
Cuando se reconoce una regla gramatical, cada símbolo en la
regla posee un valor, que se supone es un entero a menos que
sea cambiado por el programador.
Esos valores se conservan en una pila de valor mediante Yacc,
la cual se mantiene paralela a la pila de análisis
sintáctico. Se puede hacer referencia a cada valor de símbolo
en la pila utilizando una pseudo variable que comience con el
signo “$”. $$ representa el valor del no terminal que se
acaba de reconocer, es decir, el símbolo en el lado izquierdo
de la regla gramatical. Las pseudo variables $1, $2, $3 y así
sucesivamente, representan los valores de cada símbolo en
sucesión en el lado derecho de la regla gramatical.
Yacc no es directamente un analizador sino un generador de
analizadores. A partir de un fichero fuente en yacc, se
genera un fichero fuente en C que contiene el analizador
sintáctico. Sin embargo, un analizador sintáctico de yacc no
Procedimiento
Guía 3
Guía 4
fía
Compiladores. Guía 5
4
puede funcionar por sí solo, sino que necesita un analizador
léxico externo para funcionar.
Dicho de otra manera, el fuente en C que genera yacc contiene
llamadas a una función yylex() que debe estar definida y debe
devolver el tipo de lexema encontrado. Además, es necesario
incorporar también una función yyerror(), que será invocada
cuando el analizador sintáctico encuentre un símbolo que no
encaja en la gramática.
La estructura general de un programa en YACC es la siguiente:
<sección de definiciones>
%%
<sección de reglas>
%%
<sección de rutinas>
Tabla 1
Ejemplo 1
Construir un analizador sintáctico que reconozca la gramática
para una calculadora simple, con las operaciones suma, resta,
multiplicación y división con la herramienta Yacc.
Abra y ejecute el programa “Parser Generator” y abra un nuevo
texto, luego digite el código de la tabla 2.
Figura 1: Ambiente de Parser Generator.
Compiladores. Guía 5
5
Gramática para la calculadora simple:
exp -> exp opsuma term | term
opsuma -> + | -
term -> term opmult factor | factor
opmult -> *
factor -> (exp) | numero
Figura 2: Creando un archivo para introducir el texto de la
tabla 2.
/*Sección de definición*/
%token NUMBER
%{
#include <ctype.h>
#include <stdio.h>
#define YYSTYPE double /* double type para pila YACC */
%}
/*La seccion de codigo de c de la definicion debe estar entre
los delimitadores %{ y %}*/
%%
/*Fin de la seccion de definiciones e inicio de la seccion de
reglas de derivacion para el analizador sintactico*/
lines : lines expr '\n' { printf("%g\n", $2);
}
| lines '\n'
| /* e */
| error '\n' { yyerror("reenter
last line:"); yyerrok(); }
;
expr : expr '+' term { $$ = $1 + $3; }
| expr '-' term { $$ = $1 - $3; }
| term
;
Compiladores. Guía 5
6
/*Los símbolos $$ indican el valor introducido en la pila de
valor manejada por YACC, es el no terminal que se ha
reconocido en ese momento del lado izquierdo de la expresión,
y los símbolos $1, $2, etc. indican el valor de las
pseudovariables que vaya encontrando en ese orden hacia la
derecha*/
/*pseudovariables term=$1 '*'=$2 factor=$3 */
term : term '*' factor { $$ = $1 * $3; }
| term '/' factor { $$ = $1 / $3; }
| factor
;
factor : '(' expr ')' { $$ = $2; }
| '(' expr error { $$ = $2;
yyerror("missing ')'"); yyerrok(); }
| '-' factor { $$ = -$2; }
| NUMBER
;
%%
/*Fin de la seccion de reglas y adicion de rutinas auxiliares
en c*/
int main(void)
{
yyparse();
/*Invocacion de la funcion del analizador sintactico*/
return 0;
}
/*Definición del analizador léxico*/
int yylex(void)
{
int c;
while ((c = getchar()) == ' ');
/*Elimina los espacios en blanco*/
if (c == '.' || isdigit(c)) {
/*El character . indica que se termino el programa*/
ungetc(c, stdin);
scanf("%lf", &yylval);
return NUMBER;
}
return c;
}
Tabla 2
Ahora procederemos a guardar nuestro archivo para generar el
analizador sintáctico.
Compiladores. Guía 5
7
Figura 3: De click sobre el icono del disket “Save”,
seleccionar nombre y ubicación y guardamos el archivo como
“calculadora”.
Figura 4: Clic en el menú “Project” y luego “LibBuilder” para
construir el YACC y las librerías de LEX.
Compiladores. Guía 5
8
Figura 5: Se construyeron las librerías, se muestran 0
errores, en la ventana LibBuilder de clic en el botón
“Close”.
Figura 6: Procedemos a través del asistente a convertir el
código YACC, para ello dar clic en el menú “Project” y a
continuación dar clic sobre la opción “ParseWizard”.
Compiladores. Guía 5
9
Figura 7: A continuación colocamos el nombre del proyecto, la
ubicación donde se colocarán los archivos de resultado y
luego el lenguaje objetivo en nuestro caso C++, por ultimo
escogemos el compilador del lenguaje objetivo y escogemos
Microsoft Visual C++ de 32 bits.
Figura 8: Escogemos a continuación de los tipos de archivos a
generar de forma intermedia “YACC and Lex file”.
Compiladores. Guía 5
10
Figura 9: Escogemos los nombres de los archivos YACC,
colocamos “calculadora.y” y “calculadora” respectivamente.
Figura 10: Escogemos el nombre de los archivos del analizador
léxico, ingrese “calculadoralex.l” y “calculadoralex” en las
cajas correspondientes.
Compiladores. Guía 5
11
Figura 11: Archivo calculadoralex.l que se utilizara como
analizador léxico escrito en lenguaje Lex aun.
Figura 12: Archivo calculadora que se utilizara como
analizador sintáctico escrito en lenguaje YACC.
Compiladores. Guía 5
12
Figura 13: Procedemos ahora compilar ambos archivos del
proyecto calculadora, para ello damos clic en el menú
“Project” luego clic sobre la opción “Compile File”.
Figura 14: Ventana de resultados donde nos dice que no hubo
ningún error en la generación de los archivos C++ a partir de
los archivos Lex y YACC.
Al terminar esta operación, en la carpeta que usted ha
escogido como carpeta destino se deben visualizar los
archivos “calculadoralex.h” y “calculadoralex.cpp”, ambos
Compiladores. Guía 5
13
escritos con lenguaje C++ y están listos para ser usados en
un compilador que reconozca el lenguaje de la calculadora
básica.
Figura 15: Archivos generados por Parser Generator para el
proyecto de la calculadora.
Análisis de resultados
Construya un analizador sintáctico ascendente con la
herramienta Parser Generator para la gramática del lenguaje
Micro C.
Investigación complementaria
Responda:
Que es un analizador semántico
Cuál es su función principal
Algoritmo para desarrollarlo
Cuál es su dependencia con el analizador sintáctico
Qué es una tabla de símbolos
Cuáles son los tipos de comprobaciones realizadas por un
analizador semántico.
Que es un árbol de sintaxis abstracta.
Que es un AST decorado.
Bibliografía
“Construcción de Compiladores. Principios y practica”,
Kenneth C. Louden.
“Compiladores. Principios técnicas y Herramientas”.
Sethi Ullman. Pearson Education.
Compiladores. Guía 5
14
EVALUACION
% 1-4 5-7 8-10 Nota
CONOCIMIENTO
Del 20
al 30%
Conocimie
nto
deficient
e de los
fundament
os
teóricos
Conocimiento
y explicación
incompleta de
los
fundamentos
teóricos
Conocimiento
completo y
explicación
clara de los
fundamentos
teóricos
APLICACIÓN
DEL
CONOCIMIENTO
Del 40%
al 60%
ACTITUD
Del 15%
al 30%
No tiene
actitud
proactiva
.
Actitud
propositiva y
con
propuestas no
aplicables al
contenido de
la guía.
Tiene actitud
proactiva y sus
propuestas son
concretas.
TOTAL 100%
Máquina No:
Máquina No:
Alumno:
Alumno: Docente:
Docente:
GL:
GL:
Fecha:
Guía 5: Generación de analizadores
con YACC
Tema: Presentación del programa
Hoja de cotejo:
Docente:
Máquina No:
GL:
a
5 1