1 Compiladores. Gua 5
Tema: Generacin de analizadores con YACC
En esta gua se expondr la forma de generar el
analizador lxico y sintctico a travs de la
herramienta de YACC y LEX.
Aprender a utilizar la herramienta de YACC para la generacin de analizadores sintcticos.
Conocer la sintaxis de LEX y YACC para la generacin de analizadores lxicos y sintcticos.
Gua de Laboratorio N 5.
Parser Generator http://www.bumblebeesoftware.com/.
Libro Construccin de compiladores de Kenneth C. Louden.
YACC: Generacin de analizadores sintcticos LR
Un generador de analizadores sintcticos es un programa que
toma como su entrada una especificacin de la sintaxis de un
lenguaje en alguna forma, y produce como su salida un
procedimiento de anlisis sintctico para ese lenguaje.
Histricamente los generadores de analizadores sintcticos
fueron llamados compiladores de compilador, debido a que
todos los pasos de compilacin eran realizados de manera
tradicional como acciones incluidas dentro del analizador
Introduccin Terica
Gua 3
Gua 4
fa
Facultad: Ingeniera
Escuela: Computacin
Asignatura: Compiladores
Contenido
Objetivos Especficos
Material y Equipo
Compiladores. Gua 5
2
sintctico. La visin moderna es considerar al analizador
como solo una parte del proceso de compilacin, de modo que
este trmino se volvi obsoleto.
Un generador de analizadores sintcticos ampliamente
utilizado que incorpora el algoritmo de anlisis sintctico
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 especificacin (por lo regular con
sufijo .y) y produce un archivo de salida compuesto del
cdigo fuente en C para el analizador sintctico (por lo
general con sufijo .tab.c). Un archivo de especificacin de
YACC tiene el formato bsico
%%
%%
De este modo existen tres secciones separadas mediante lneas
que contienen doble signo de porcentaje.
La seccin de definiciones contiene informacin acerca de los
tokens, tipos de datos y reglas gramaticales que YACC
necesita para construir el analizador sintctico. Tambin
incluye cualquier cdigo en C que debera ir directamente en
el archivo de salida a su inicio (sobre todo directivas
#include de otros archivos de cdigo fuente). Esta seccin
del archivo de especificacin puede estar vaca.
La seccin de reglas contiene reglas gramaticales en una
forma BNF modificada, junto con acciones en cdigo C que se
ejecutaran siempre que se reconozca la regla gramatical
asociada. Las convenciones de meta smbolos utilizadas en
reglas gramaticales son de la manera siguiente. Como es
habitual, la barra vertical se utiliza para las alternativas
(las alternativas tambin se pueden escribir por separado).
El smbolo 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. Tambin un signo de punto y
coma debe finalizar cada regla gramatical.
Compiladores. Gua 5
3
La tercera seccin, de rutinas auxiliares, contiene
declaraciones de procedimientos y funciones que de otra
manera pueden no estar disponibles a travs de archivos
#include y que son necesarias para completar el analizador
sintctico y/o el compilador.
Esta seccin puede estar vaca, y si este es el caso se puede
omitir el segundo meta smbolo de porcentaje doble del
archivo de especificacin. De esta manera, un archivo de
especificacin mnimo de YACC consistira solo de %% seguidos
por reglas gramaticales y acciones (las acciones tambin se
pueden omitir si solo tratamos de analizar la gramtica).
YACC tambin permite insertar comentarios al estilo de C en
el archivo de especificacin en cualquier punto donde no
interfieran con el formato bsico.La primera seccin que
incluye las directivas #include se encierra entre los
smbolos %{ y %} ntese 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 numrico a continuacin del nombre del token.
En la segunda seccin, las reglas gramaticales se colocan
as: expresin: expresin trminos
Cuando se reconoce una regla gramatical, cada smbolo 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 anlisis
sintctico. Se puede hacer referencia a cada valor de smbolo
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 smbolo en el lado izquierdo
de la regla gramatical. Las pseudo variables $1, $2, $3 y as
sucesivamente, representan los valores de cada smbolo en
sucesin 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
sintctico. Sin embargo, un analizador sintctico de yacc no
Procedimiento
Gua 3
Gua 4
fa
Compiladores. Gua 5
4
puede funcionar por s solo, sino que necesita un analizador
lxico externo para funcionar.
Dicho de otra manera, el fuente en C que genera yacc contiene
llamadas a una funcin yylex() que debe estar definida y debe
devolver el tipo de lexema encontrado. Adems, es necesario
incorporar tambin una funcin yyerror(), que ser invocada
cuando el analizador sintctico encuentre un smbolo que no
encaja en la gramtica.
La estructura general de un programa en YACC es la siguiente:
%%
%%
Tabla 1
Ejemplo 1
Construir un analizador sintctico que reconozca la gramtica
para una calculadora simple, con las operaciones suma, resta,
multiplicacin y divisin con la herramienta Yacc.
Abra y ejecute el programa Parser Generator y abra un nuevo
texto, luego digite el cdigo de la tabla 2.
Figura 1: Ambiente de Parser Generator.
Compiladores. Gua 5
5
Gramtica 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.
/*Seccin de definicin*/
%token NUMBER
%{
#include
#include
#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. Gua 5
6
/*Los smbolos $$ 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 expresin,
y los smbolos $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;
}
/*Definicin del analizador lxico*/
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 sintctico.
Compiladores. Gua 5
7
Figura 3: De click sobre el icono del disket Save,
seleccionar nombre y ubicacin y guardamos el archivo como
calculadora.
Figura 4: Clic en el men Project y luego LibBuilder para
construir el YACC y las libreras de LEX.
Compiladores. Gua 5
8
Figura 5: Se construyeron las libreras, se muestran 0
errores, en la ventana LibBuilder de clic en el botn
Close.
Figura 6: Procedemos a travs del asistente a convertir el
cdigo YACC, para ello dar clic en el men Project y a
continuacin dar clic sobre la opcin ParseWizard.
Compiladores. Gua 5
9
Figura 7: A continuacin colocamos el nombre del proyecto, la
ubicacin donde se colocarn 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 continuacin de los tipos de archivos a
generar de forma intermedia YACC and Lex file.
Compiladores. Gua 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
lxico, ingrese calculadoralex.l y calculadoralex en las
cajas correspondientes.
Compiladores. Gua 5
11
Figura 11: Archivo calculadoralex.l que se utilizara como
analizador lxico escrito en lenguaje Lex aun.
Figura 12: Archivo calculadora que se utilizara como
analizador sintctico escrito en lenguaje YACC.
Compiladores. Gua 5
12
Figura 13: Procedemos ahora compilar ambos archivos del
proyecto calculadora, para ello damos clic en el men
Project luego clic sobre la opcin Compile File.
Figura 14: Ventana de resultados donde nos dice que no hubo
ningn error en la generacin de los archivos C++ a partir de
los archivos Lex y YACC.
Al terminar esta operacin, en la carpeta que usted ha
escogido como carpeta destino se deben visualizar los
archivos calculadoralex.h y calculadoralex.cpp, ambos
Compiladores. Gua 5
13
escritos con lenguaje C++ y estn listos para ser usados en
un compilador que reconozca el lenguaje de la calculadora
bsica.
Figura 15: Archivos generados por Parser Generator para el
proyecto de la calculadora.
Anlisis de resultados
Construya un analizador sintctico ascendente con la
herramienta Parser Generator para la gramtica del lenguaje
Micro C.
Investigacin complementaria
Responda:
Que es un analizador semntico
Cul es su funcin principal
Algoritmo para desarrollarlo
Cul es su dependencia con el analizador sintctico
Qu es una tabla de smbolos
Cules son los tipos de comprobaciones realizadas por un analizador semntico.
Que es un rbol de sintaxis abstracta.
Que es un AST decorado.
Bibliografa
Construccin de Compiladores. Principios y practica, Kenneth C. Louden.
Compiladores. Principios tcnicas y Herramientas. Sethi Ullman. Pearson Education.
Compiladores. Gua 5
14
EVALUACION
% 1-4 5-7 8-10 Nota
CONOCIMIENTO
Del 20
al 30%
Conocimie
nto
deficient
e de los
fundament
os
tericos
Conocimiento
y explicacin
incompleta de
los
fundamentos
tericos
Conocimiento
completo y
explicacin
clara de los
fundamentos
tericos
APLICACIN
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 gua.
Tiene actitud
proactiva y sus
propuestas son
concretas.
TOTAL 100%
Mquina No:
Mquina No:
Alumno:
Alumno: Docente:
Docente:
GL:
GL:
Fecha:
Gua 5: Generacin de analizadores
con YACC
Tema: Presentacin del programa
Hoja de cotejo:
Docente:
Mquina No:
GL:
a
5 1
Recommended