Compiladores Trabajo Final
Compiladores Trabajo Final
Compiladores Trabajo Final
FACULTAD DE INGENIERA
ESCUELA PROFESIONAL EN INGENIERA DE INFORMTICA Y SISTEMAS
PRESENTADO POR:
TACNA - PER
2017
1
INDICE
1. PRESENTACIN...3
2. CAPTULO I..4
2.1. MARCO TEORICO....4
2.2. COMPILADORES..4
2.4. ANALIZADOR LEXICO..5
2.5. ANALIZADOR SINTACTICO..6
2.6. ANALIZADOR SEMANTICO..8
3. CAPTULO II10
3.1 ANALISIS Y DESARROLLO...10.
3.1.1. Analizador Lexico...10
3.1.2. Analizador Sintactico...11
3.1.3. Analizador Semantico..11
4. CAPITULO III...12
4.1. REFERENCIAS BIBLIOGRAFICAS12
4.2. ANEXOS...13.
2
PRESENTACIN
3
CAPTULO I
I. MARCO TERICO:
COMPILADORES:
Un traductor que transforma textos fuentes de lenguaje de alto nivel a lenguaje de bajo
nivel se le denomina compilador (en ingls compiler). El tiempo que se necesita para
traducir un lenguaje de alto nivel a lenguaje objeto se denomina tiempo de compilacin
(compilation time). El tiempo que tarda en ejecutarse un programa objeto se denomina
tiempo de ejecucin (rum time) (Lovelle, 1998).
.
Figura 2: concepto de tiempo de ejecucin
Fases de un compilador:
El trabajo de un compilador se divide en las siguientes frases.
- anlisis lxico, anlisis lexicogrfico o rastreo
- anlisis sintctico o anlisis gramatical
- anlisis semntico
4
- optimizacin
- preparacin para la generacin de cdigo
- generacin de cdigo
1. ANALIZADOR LXICO
Es la primera fase del compilador y la nica que tiene acceso al texto del
programa fuente. La representacin interna del programa cambia conforme
avanza la compilacin. El analizador lxico lee la secuencia de caracteres del
programa fuente y la convierte en una secuencia de tokens. (Lovelle, 1998)
5
Por ejemplo, si la entrada fuese la sentencia de asignacin en lenguaje C
"energia=total=cantidad+23", el analizador leera dicha secuencia de caracteres
y los agruparon formando tokens. Cada token representa una secuencia de
caracteres lgicamente coherentes. Por ejemplo un identificador, una constante
entera, un operador, una palabra clave como WHILE o FOR, signos de
puntuacin, un operador formado por varios caracteres como "++". En nuestro
caso el analizador lxico agrupar los caracteres formando los tokens (Milln,
2009).
- el identificador energa
- el operador de asignacin = (ASIGN en lo sucesivo)
- el identificador total
- el operador de asignacin = (ASIGN en lo sucesivo)
- el identificador cantidad
- el operador de suma +
- la constante numrica entera 23
2. ANALIZADOR SINTCTICO
6
similar como se determina mediante expresiones regulares la estructura Ixica
de los tokens reconocida por el analizador lxico (Kanneth C., Louden, 1997).
Flex
Es una herramienta para generar escneres: programas que reconocen
patrones lxicos en texto. Flex lee los archivos de entrada dados, o su entrada
estndar si no se dan nombres de archivo, para una descripcin de un escner
para generar. La descripcin est en forma de pares de expresiones regulares y
cdigo C, llamadas reglas. Flex genera como salida un archivo de origen C,
lex.yy.c, que define una rutina yylex (). Este archivo se compila y enlaza
con la biblioteca -lfl para producir un ejecutable. Cuando se ejecuta el
ejecutable, analiza su entrada para las apariciones de las expresiones regulares.
Cuando encuentra uno, ejecuta el cdigo C correspondiente.
Bison
Es un generador sintctico de propsito general que convierte una
descripcin de la gramtica para un LALR (1) sin contexto en un programa C
para analizar esa gramtica. Una vez que se es competente con Bison, se puede
utilizarlo para desarrollar una amplia gama de analizadores de lenguajes, desde
los que se utilizan en las calculadoras simples de escritorio hasta complejos
lenguajes de programacin.
Bison es compatible con Yacc: todas las gramticas de Yacc debidamente
escritas deberan funcionar con Bison sin cambios.
Yacc
Yacc proporciona una herramienta general para imponer la estructura en
la entrada a un programa de computadora. El usuario Yacc prepara una
especificacin del proceso de entrada; Esto incluye reglas que describen la
estructura de entrada, cdigo a ser invocado cuando se reconocen estas reglas y
una rutina de bajo nivel para realizar la entrada bsica. Entonces Yacc genera
7
una funcin para controlar el proceso de entrada. Esta funcin, llamada
analizador, llama a la rutina de entrada de bajo nivel suministrada por el usuario
(el analizador lxico) para recoger los elementos bsicos (denominados tokens)
del flujo de entrada. Estos tokens se organizan de acuerdo con las reglas de
estructura de entrada, llamadas reglas gramaticales; Cuando se ha reconocido
una de estas reglas, se invoca el cdigo de usuario suministrado para esta regla,
una accin; Las acciones tienen la capacidad de devolver valores y hacer uso de
los valores de otras acciones.
Yacc est escrito en un dialecto porttil de C y las acciones, y la subrutina de
salida, estn en C tambin. Adems, muchas de las convenciones sintcticas de
Yacc siguen a C.
Gramtica ambigua
Una gramtica que genera una cadena con dos rboles de anlisis
gramaticales distintos se denomina gramtica ambigua.
3. ANALIZADOR SEMNTICO
Qu es un analizador semntico?
8
Segn sus restricciones del lenguaje el analizador semntico utiliza
estas para validar que la expresin cumpla con la restriccin que est
relacionada.
Por ejemplo:
Asignacion ->id:=(expresion);
El analizador semntico es una de la fase ms importante de un
compilador ya que ella analiza que cada estructura sintctica tenga coherencia.
El anlisis semntico utiliza como entrada el rbol sintctico detectado
por el anlisis sintctico para comprobar restricciones de tipo y otras
limitaciones semnticas y preparar la generacin de cdigo.
En compiladores de un solo paso, las llamadas a las rutinas semnticas
se realizan directamente desde el analizador sintctico y son dichas rutinas las
que llaman al generador de cdigo. El instrumento ms utilizado para
conseguirlo es la gramtica de atributos.
En compiladores de dos o ms pasos, el anlisis semntico se realiza
independientemente de la generacin de cdigo, pasndose informacin a travs
de un archivo intermedio, que normalmente contiene informacin sobre el rbol
sintctico en forma linealizada (para facilitar su manejo y hacer posible su
almacenamiento en memoria auxiliar).
En cualquier caso, las rutinas semnticas suelen hacer uso de una pila (la
pila semntica) que contiene la informacin semntica asociada a los operandos
(y a veces a los operadores) en forma de registros semnticos.
Gramtica de atributos
Es una extensin de la notacin de Backus que consiste en introducir en
las reglas sintcticas ciertos smbolos adicionales no sintcticos (smbolos de
accin) que, en definitiva, se reducen a llamadas implcitas o explcitas a rutinas
semnticas.
Por ejemplo: sea la gramtica simplificada que analiza las instrucciones
de asignacin:
9
llamada al generador de cdigo) o generar representacin intermedia (si es una
compilacin en dos o ms pasos).
CAPTULO II
Se defini los tokens para las palabras y operaciones comunes del lenguaje
PASCAL FC, ver Tabla 1.
Tabla 1 Lista de Tokens
10
else return(ELSE);
"*" return(OPMult); while return(WHILE);
"/" return(OPMult); do return(DO);
div return(OPMult); for return(FOR);
mod return(OPMult); to return(TO);
and return(OPMult);
{id} return(ID);
"(" return(PABRE); {digito} return(NUM);
")" return(PCIERRA);
"[" return(PABREC);
El analizador lxico es el archivo pascal2.l que reconoce los tokens del programa
fuente, para ello tambin se ayuda de una tabla de smbolos pascal2.tab, que asigna
valores a cada token. Se utiliz la herramienta Flex que devuelve tokens y sern
utilizados como entrada para el analizador sintctico.
11
; |IF expresion THEN prop else
lista_id: ID |
| lista_id COMA ID ;
; argumentos: PABRE lista_parametros
declaraciones: declaraciones VAR PCIERRA
lista_id DOSP tipo PTOCOMA |
| ;
; lista_parametros: lista_id DOSP tipo
expresion: expr_simple | lista_parametros
| expr_simple OPREL PTOCOMA lista_id DOSP tipo
expr_simple ;
; prop_compuesta: BEG lista_prop END
expr_simple: termino ;
| expr_simple OPSuma termino lista_prop: prop
; | lista_prop PTOCOMA prop
termino: factor ;
| termino OPMult factor
;
12
CAPTULO III
IV. ANEXOS
delim [ \t]
blancos [delim]+
letra [A-Za-z]
digito [0-9]+
id {letra}({letra}|{digito})*
coment{[^}\n]}
%%
{blancos}
"\n" {ln++;}
"=" return(OPREL);
13
"<>" return(OPREL);
"<" return(OPREL);
"<=" return(OPREL);
">=" return(OPREL);
">" return(OPREL);
"+" return(OPSuma);
"-" return(OPSuma);
"*" return(OPMult);
"/" return(OPMult);
div return(OPMult);
mod return(OPMult);
and return(OPMult);
"(" return(PABRE);
")" return(PCIERRA);
"[" return(PABREC);
"]" return(PCIERRAC);
"{" return(LLAVEA);
"}" return(LLAVEC);
program return(PROG);
var return(VAR);
array return(ARR);
of return(OF);
integer return(INT);
real return(REAL);
function return(FUNC);
procedure return(PROC);
14
begin return(BEG);
end return(END);
if return(IF);
then return(THEN);
else return(ELSE);
while return(WHILE);
do return(DO);
for return(FOR);
to return(TO);
{id} return(ID);
{digito} return(NUM);
%%
%}
/*Declaraciones de BISON*/
%token OPREL
%token OPSuma
%token OPAsigna
%token DOSP
%token PTOCOMA
%token COMA
%token PTO
%token OPMult
%token PABRE
%token PCIERRA
%token PABREC
%token PCIERRAC
%token PROG
%token VAR
%token ARR
%token OF
%token INT
%token REAL
%token FUNC
%token PROC
%token BEG
%token END
15
%token IF
%token THEN
%token ELSE
%token WHILE
%token DO
%token FOR
%token TO
%token ID
%token NUM
%token LLAVEA
%token LLAVEC
/*Gramtica*/
%%
programa: encabezado codigo PTO
;
encabezado: PROG ID PABRE lista_id PCIERRA PTOCOMA
|
;
codigo: declaraciones declaraciones_subp prop_compuesta
;
lista_id: ID
| lista_id COMA ID
;
declaraciones: declaraciones VAR lista_id DOSP tipo PTOCOMA
|
;
tipo: tipo_std
|ARR PABREC NUM PTO PTO NUM PCIERRAC OF tipo_std
;
tipo_std: INT
| REAL
;
declaraciones_subp: declaraciones_subp declaracion_subp PTOCOMA
|
;
declaracion_subp: encab_subp declaraciones prop_compuesta
;
encab_subp: FUNC ID argumentos DOSP tipo_std PTOCOMA
| PROC ID argumentos PTOCOMA
;
argumentos: PABRE lista_parametros PCIERRA
|
;
lista_parametros: lista_id DOSP tipo
| lista_parametros PTOCOMA lista_id DOSP tipo
;
prop_compuesta: BEG lista_prop END
;
lista_prop: prop
| lista_prop PTOCOMA prop
;
prop: prop_procedimiento
| prop_compuesta
|variable OPAsigna expresion
16
| WHILE expresion DO prop
| FOR ID OPAsigna expresion TO expresion DO prop
|IF expresion THEN prop else
|
;
else: ELSE prop
|
;
variable: ID
| ID PABREC expresion PCIERRAC
;
prop_procedimiento: ID
| ID PABRE lista_expr PCIERRA
;
lista_expr: expresion
| lista_expr COMA expresion
;
expresion: expr_simple
| expr_simple OPREL expr_simple
;
expr_simple: termino
| expr_simple OPSuma termino
;
termino: factor
| termino OPMult factor
;
factor: ID
| ID PABRE lista_expr PCIERRA
| NUM
| PABRE expresion PCIERRA
;
%%
main ()
{
printf("______________________________\n");
printf("Digite el programa a analizar \n");
printf("______________________________\n\n");
yyparse ();
17
}
int yywrap()
{
printf("Codigo PASCAL reconocido \n");
}
end;
begin
read(x,y);
write(mcd(x,y));
end.
Prueba 2:
program test2(input,output);
var a,b,c:integer;
begin
read(a,b);
c:=a+b;
writeln(c);
end.
Prueba 3:
program test3(input, output);
var a,b: integer;
begin
read(a,b);
while (a>b)
do
write(a);
end.
Prueba 4:
program test4(intput,output);
var dato:integer;
procedure modifica(variable:integer);
begin
variable:=3;
writeln(variable);
end;
begin
dato:=2;
18
writeln(dato);
modifica(dato);
writeln(dato);
end.
19