Compiladorescamarena PDF
Compiladorescamarena PDF
Compiladorescamarena PDF
Marzo de 2008
2
Índice general
1. Introducción 5
1.1. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2. Justificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3. Usuarios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4. Definiciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.5. El Análisis Léxico . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.6. El Análisis Sintáctico . . . . . . . . . . . . . . . . . . . . . . . 9
1.7. El Análisis Semántico . . . . . . . . . . . . . . . . . . . . . . . 9
1.8. Generador de Código Intermedio . . . . . . . . . . . . . . . . 9
1.9. El Optimizador de Código . . . . . . . . . . . . . . . . . . . . 10
1.10. La Tabla de Sı́mbolos . . . . . . . . . . . . . . . . . . . . . . . 10
1.11. Manejo de Errores . . . . . . . . . . . . . . . . . . . . . . . . 10
2. Análisis Léxico 11
2.1. Construcción de Analizadores Léxicos . . . . . . . . . . . . . . 11
2.2. El Generador de Analizadores lexicos: lex . . . . . . . . . . . . 13
3. Análisis Sintáctico 17
3.1. Análisis Sintáctico Descendente . . . . . . . . . . . . . . . . . 17
3.1.1. Parser descendente recursivo . . . . . . . . . . . . . . . 18
3.1.2. Parser predictivo descendente para gramáticas LL(1) . 19
3.2. Análisis Sintáctico Ascendente . . . . . . . . . . . . . . . . . . 32
3.2.1. Parsers LR . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3. El generador de analizadores sintácticos: yacc . . . . . . . . . 41
3
4 ÍNDICE GENERAL
Capı́tulo 1
Introducción
Programación de Computadoras
Arquitectura de Computadoras
Ingenierı́a de Software
Programación de Sistemas
5
6 CAPÍTULO 1. INTRODUCCIÓN
1.1. Objetivo
Proveer al alumno con principios y técnicas útiles para la construcción
de Compiladores. El alumno deberá ser capaz de implementar la traducción
de un lenguaje de programación de alto nivel al lenguaje de máquina de un
computador.
1.2. Justificación
El estudiante debe aprender como implementar compiladores utilizando
la tecnologı́a actual, estas notas deberán serle de gran ayuda.
1.3. Usuarios
Estudiantes de Ingenierı́a en COmputación de la Facultad de Ingenierı́a
Eléctrica
1.4. DEFINICIONES 7
1.4. Definiciones
Un compilador es un TRADUCTOR de un lenguaje de programación de
alto nivel a un lenguaje ensamblador el cual será traducido a su vez a código
objeto por algún ensamblador [1], [2], [3]. El conjunto de compiladores es
un subconjunto del producto cartesiano del conjunto de Lenguajes de alto
nivel, el conjunto de computadoras y el conjunto de sistemas operativos. Por
Ejemplo el compilador de C++ para McCintosh en ambiente Linux se podrı́a
representar por:
(C++,MAC,Linux)
Otros ejemplos podrı́an ser:
(Modula2,PC,DOS), (Pascal,Risc,Unix), (Java,Sun,OS/2), Etc....
Para colmo, se generan versiones nuevas frecuentemente de compiladores
ya existentes. Esto quiere decir que hay mucha gente el mundo trabajando
en el desarrollo de los compiladores. El primer compilador de Fortran IV
requirió de trabajo en equipo durante casi quince años. Sin embargo, ahora
se cuenta con muchas herramientas CASE para el desarrollo de compiladores,
ası́ como bases matemáticas y toda una tecnologı́a que por cierto se utiliza
también para el desarrollo de otro tipo de software como:
Análisis Léxico
11
12 CAPÍTULO 2. ANÁLISIS LÉXICO
%{
Declaraciones en C
%}
Declaraciones de lex (macros)
%%
fuente de lex (Expresiones regulares) y opcionalmente acciones en C
%%
Funciones en C
Operador Descripción
[] Corchetes para especificar conjuntos de caracteres
∧ Para designar el complemento de un conjunto
* Cerradura de Kleen
+ Cerradura positiva
| Operador or
() Para agrupar expresiones
- Para indicar un intervalo
{} para usar una macro de las definidas en la sección de declaraciones de lex
? para indicar una parte opcional
“” comillas para especificar una secuencia de caracteres en orden estricto
\ para escapar caracteres de la interpretacion de lex
. para especificar cualquier caracter
/ Se reconoce la expresión regular a la izquierda de /
solo si se encuentra seguida de la expresion regular a la derecha de /
D [0-9]
E [EDed][-+]?{D}+
%%
{D}+ puts("Entero");
{D}+"."{D}*{E}? |
{D}*"."{D}+{E}?
puts("Flotante");
2.2. EL GENERADOR DE ANALIZADORES LEXICOS: LEX 15
%%
main() { yylex(); }
yywrap() { return 1; }
%{
int k;
%}
%%
[0-9]+ {
k=atoi(yytext);
if ((k%7)==0) printf("%d",k+3); else ECHO;
}
%%
main() { yylex(); }
yywrap() { return 1; }
printf("%s",yytext)
%{
int longitudes[10];
%}
%%
[a-z]+ longitudes[yyleng]++;
%%
main() { yylex(); }
yywrap() {
int i;
printf("Longitud \t Numero de palabras\n");
for (i=0;i<10;i++)
if (longitudes[i]>0) printf("%d \t %d \n",i,longitudes[i]);
return 1;
}
#undef input
#undef unput
Análisis Sintáctico
17
18 CAPÍTULO 3. ANÁLISIS SINTÁCTICO
S → aA
A → bA
A → cBd
B→d
(3.1)
S() {
if ((lee_token()==’a’)&&A()) return TRUE;
deslee_token(’a’);
return FALSE;
}
pop si A = a ∀a ∈ VT
acepta si A = # y a=#
M (A, a) = (3.4)
(aα, i) si A → aα es la i − esima produccion
error en cualquier otro caso
1. S → aS
2. S → bA
3. A → c
4. A → dA
(3.5)
0. S 0 → S#
(abddc#,S#,ε)`(abddc#,aS#,1)`(bddc#,S#,1)`
(bddc#,bA#,12)`(ddc#,A#,12)`(ddc#,dA#,124)`
(dc#,A#,124)`(dc#,dA#,1244)`(c#,A#,1244)`
(c#,c#,12443)`(#,#,12443)`(ε,ε,12443)
a b c d #
S (aS,1) (bA,2)
A (c,3) (dA,4)
a pop
b pop
c pop
d pop
# aceptar
La localidad S,a tiene (aS,1) para indicar que se debe utilizar la regla de
producción número uno y meter en el stack la S y luego la a. La diagonal de
la submatriz de terminales contra terminales siempre tiene pop puesto que
si el sı́mbolo leido y el que esta en el tope del stack son el mismo, entonces
se debe de avanzar en la entrada y quitarlo del tope del stack. Las entradas
en blanco de la tabla indican que se debe marcar error de sintaxis.
22 CAPÍTULO 3. ANÁLISIS SINTÁCTICO
pop si A = a ∀a ∈ VT
acepta si A = # y a=#
M (A, a) = (3.6)
(β, i) si a ∈ P RIM ERO(β) y
A → β es la i − ésima producción
error en cualquier otro caso
(a,a):=(a,a)#
Mediante la gramática cuyas reglas de producción son:
0. S’→ S#
1. S→LB
3.1. ANÁLISIS SINTÁCTICO DESCENDENTE 23
2. B→;S;L
3. B→:=L
4. L→(EJ
5. J→,EJ
6. J→)
7. E→a
8. E→L
24 CAPÍTULO 3. ANÁLISIS SINTÁCTICO
a := ( ) , ; #
S (LB,1)
B (:=,3) (;S;L,2)
L ((EJ,4)
J (),6) (,EJ,5)
E (a,7) (L,8)
a pop
:= pop
( pop
) pop
, pop
; pop
# Aceptar
3.1. ANÁLISIS SINTÁCTICO DESCENDENTE 25
pop si A = a ∀a ∈ VT
acepta si A = # y a=#
(α, i) si a ∈ P RIM ERO(α) y
A → α es la i − esima produccion
M (A, a) = (3.7)
(α, i) si a ∈ SIGU IEN T E(A) y
A → α es la i − esima produccion
y A es nulif icable
error en cualquier otro caso
0. S → A#
1. A → Bb
2. A → Cd
3. B → aB
4. B→ε
5. C → cC
6. C→ε
(3.8)
Al principio el parser procede como en el ejemplo anterior, selecciona la
regla de producción 2, luego la 5 y luego la 5 otra vez, el trazado de in-
tantáneas hasta ahı́ es:
(ccd#,A#,ε)`(ccd#,Cd#,2)`(ccd#,cCd#,25)`
(cd#,Cd#,25)`(cd#,cCd#,255)`(d#,Cd#,255)`
(d#,d#,2556)`(#,#,2556)`(ε,ε,2556)
a b c d #
A (Bb,1) (Bb,1) (Cd,2) (Cd,2)
B (aB,3) (ε ,4)
C (cC,5) (ε,6)
a pop
b pop
c pop
d pop
# Aceptar
∗
Además, si αi ⇒ ε, es decir, si A es nulificable entonces se cumple también
que:
Manejo de errores
El parser LL(1) detecta un error de sintaxis cuando llega a una localidad
vacia de la tabla de parsing. Indicar “Error en la linea ...” y abortar puede ser
un comportamiento adecuado para un parser teórico abstracto, sin embargo,
para un compilador real tal reacción es inaceptable. Un compilador real debe
reportar el tipo de error e intentar continuar con el análisis sintáctico como
si no hubiera encontrado ningún error, tal vez mas adelante encuentre otros
errores que tambien denerá reportar de manera que cuando el programador
modifique el código fuente, corrija el mayor numero de errores que le sea
posible antes de recompilar.
Los parsers LL(1) poseen la caracterı́stica del prefijo válido, lo cual signifi-
ca que si el parser no detecta ningun error en la primera porción a1 a2 ...ak−1
de la entrada a1 a2 ...an , debe existir una secuencia de sı́mbolos ak ak+1 ...am
tal que a1 a2 ...am es una cadena válida del lenguaje. La propiedad del prefijo
válido implica que el parser detecta el error lo antes posible en el proceso de
barrido de izquierda a derecha de la entrada. Esta propiedad también elimi-
na la necesidad de borrar y/o insertar sı́mbolos en el stack en el proceso de
recuperación del error. Cuando el parser detecta un error en el sı́mbolo ak ,
3.1. ANÁLISIS SINTÁCTICO DESCENDENTE 29
el parser puede modificar los sı́mbolos ak ak+1 ...am y continuar con el proceso
de análisis sintáctico.
Ejemplo: Para la siguiente gramática:
E’→E#
E→TA
A→+TA
A→ ε
T→a
T→(E)
a ( ) + #
E (TA,1) (TA,1)
A (ε ,3) (+TA,2) (ε ,3)
T (a,4) ((E),5)
a pop
( pop
) pop
+ pop
# Aceptar
a)#
a ( ) + #
E (TA,1) (TA,1) 1 2 3
A 4 5 (ε ,3) (+TA,2) (ε ,3)
T (a,4) ((E),5) 6 7 8
a pop 9 10 11 12
( 13 pop 14 15 16
) 17 18 pop 19 20
+ 21 22 23 pop 24
# 25 26 27 28 Aceptar
E’→E#
T→(E)
1. E→E+T
2. E→T
3. T→T*F
4. T→F
5. F→(E)
6. F→id
izquierda a derecha, por lo cual debe detectar cuando la parte leida coincide
con la parte derecha de alguna regla de producción, en el ejemplo anterior, al
principio lee id y lo reconoce como la parte derecha de la regla 6 y por eso se
aplica primero dicha regla. A estas cadenas que coinciden con la parte derecha
de alguna regla de producción se les llama mangos, asideras o agarraderas
(handle en inglés).
3.2.1. Parsers LR
Los parsers LR(1) pueden de manera determinista decidir cual regla uti-
lizar con solo un token de look ahead. Son autómatas finitos con un stack
para recordar de que manera han llegado a un determinado estado. Al ir
barriendo la entrada de izquierda a derecha, van consultando en cada paso
una tabla de ACCIONES muy parecida a las tablas de parsing LL(1) donde
se indica que debe hacer el autómata: shift y cambiar de estado o reducir me-
diante determinada regla de producción, aceptar la entrada o marcar error.
También utilizan una tabla GOTO que tiene la información de a que estado
cambiarse cuando hace una reducción. En la Figura 3.1 se muestra un parser
LR(1) conceptualmente:
34 CAPÍTULO 3. ANÁLISIS SINTÁCTICO
A C C I Ó N GOTO
+ * a b # ε E T F
0 s4 s5 1 2 3
1 s7 s6
2 r2 s4 s5 r2 8
3 r4 s9 r4 r4 r4
4 r6 r6 r6 r6 r6
5 r7 r7 r7 r7 r7
6 aceptar
7 s4 s5 10 3
8 r3 s8 r3 r3 r3
9 r5 r5 r5 r5 r5
10 r1 s4 s5 r1 8
eso la acción es r1 se debe sacar T+E con todo y estados y meter E al stack.
Es claro el por qué se sacan del stack un número de elementos igual al doble
de la longitud de la cadena derecha de la regla de producción utilizada ya que
por cada sı́mbolo hay un estado. Si se opta por no almacenar los sı́mbolos
sino solamante los estados no se deberá sacar el doble de la longitud sino la
longitud solamente.
El problema a resolver ahora es el como contruir las tablas Acción y goto
que utiliza este parser. Para ello nos auxiliaremos del concepto de elemento,
un elemento es una regla de la gramática donde la parte derecha de la misma
está dividida en dos partes, la primera parte es la que ya fué verificada con
la entrada y la segunda es la que se espera que se verifique con la parte de
entrada que está por leerse. Si la marca que separa estas dos partes es un
punto, entonces los elementos tienen la forma:
A → α.β (3.12)
3.2. ANÁLISIS SINTÁCTICO ASCENDENTE 37
E→.E+T
E→.T
C0 ={
E’→.E# ,
E→.E+T ,
E→.T ,
T→.TF ,
T→.F ,
F→.F* ,
F→.a ,
F→.b
}
Este conjunto denota al estado inicial del autómata, para determinar los
estados a los que pasa el autómata a partir de este estado al leer E se buscan
los elementos que tengan E ensequida del punto (E’→.E# y E→.E+T) y se
cambian por los mismos elementos con el punto desplazado una posición a la
derecha (E’→E.# y E→E.+T) y despues se obtiene la cerradura de este con-
junto, en este caso el conjunto es igual a su cerradura puesto que después del
punto solo hay terminales. Por lo tanto, el estado al que pasa el autómata al
leer E estando en el estado cero queda denotado por el conjunto de elementos:
38 CAPÍTULO 3. ANÁLISIS SINTÁCTICO
C1 = {
E’→E.# ,
E→E.+T
}
C2 ={
E→T. ,
T→T.F ,
F→.F* ,
F→.a ,
F→.b
}
SIGUIENTE(E) = { +, # }
SIGUIENTE(T) = { a, b, #, + }
SIGUIENTE(F) = { *, a, b, #, + }
+
6
# 5 b
b
b
T
1 10
a 7
E b
Inicio
4
a
a
0
a F
T 8
* 9
2
F
F
F
*
3
%{
declaraciones en C
%}
declaraciones de yacc
%%
reglas de la gramática
%%
funciones en C
%{
#define YYSTYPE double /* Tipo de la pila de datos de yacc */
%}
%token NUMBER
%left ’+’ ’-’
%left ’*’ ’/’
%left UNARYMINUS
%%
lista:
| lista ’\n’
| lista expre ’\n’ { printf("\t%lf\n",$2); }
;
expre: NUMBER { $$ = $1; }
| ’-’ expre %prec UNARYMINUS {$$ = -$2; }
| expre ’+’ expre { $$ = $1 + $3; }
| expre ’-’ expre { $$ = $1 - $3; }
| expre ’*’ expre { $$ = $1 * $3; }
| expre ’/’ expre { $$ = $1 / $3; }
| ’(’ expre ’)’ { $$ = $2; }
;
%%
#include <stdio.h> #include <ctype.h>
yylex() { int c;
while ((c=getchar())==’ ’||c==’\t’);
44 CAPÍTULO 3. ANÁLISIS SINTÁCTICO
if (c==EOF) return 0;
if (c==’.’||isdigit(c)) {
ungetc(c,stdin);
scanf("%lf",&yylval);
printf("Token numero: %lf\n",yylval);
return NUMBER;
}
if (c==’\n’) num_lineas++;
printf("Token caracter: %c\n",c);
return c;
}
yyerror(char *s) {
warning(s,(char *)0);
}
[2] J.-P. Tremblay and P. G. Sorenson, The Theory and Practice of Compiler
Writing. Mac Graw Hill, 1985.
[4] J. R. Mason and D. Brown, lex and yacc. O’Reilly Associates Inc., 1990.
47