Upload
realvaradog4831
View
14
Download
5
Embed Size (px)
DESCRIPTION
Capitulo i compiladores e interpretes
Citation preview
Compiladores e Interpretes EPCI - UNPRG
Ing. Luis Reyes Lescano 1
COMPILADORES E INTERPRETES
Análisis semántico:
Estudia el significado de la sentencia
Procesadores de lenguaje:
Convierte un programa fuente hecho en
un lenguaje fuente a un programa objeto
hecho en un lenguaje objeto. En
consecuencia, es un programa que esta
hecho en maquina virtual y es
transformado a un programa que
entienda la maquina real. Observe el
esquema:
El lenguaje objeto es creado por el
compilador, el cual debe estar preparado
para el sistema operativo en el que será
ejecutado y a la arquitectura respectiva
del hardware. Por ejemplo, existen
compiladores que a un programa fuente
lo transforman a ejecutable para
Windows (arquitectura CISC) o para
MacOS (arquitectura RISC).
Un SO de arquitectura propietaria son aquellas que restringen el desarrollo de aplicaciones sólo a
esa misma familia de SO, por ejemplo, Windows: sus aplicaciones no pueden ser ejecutadas por otros
SO tal como MacOS o LINUX
Un SO de arquitectura abierta es aquel en que sus aplicaciones pueden ser ejecutadas en cualquier
otro SO, como por ejemplo LINUX puede ser instalado en cualquier arquitectura como CISC o RISC, es
decir se puede instalar en una PC o una Mac (Apple) respectivamente.
Existen decompiladores que transforman un exe a código fuente. Pero, debe saberse de antemano cual
fue el lenguaje que lo originó.
Especie de caja negra (no perceptible por el usuario)
Programa fuente
(hecho en Leng. Fuente)
Programa objeto
(hecho en Leng. Objeto)
Firmware (microprograma ubicado
en la ROM)
CONVERTIR
Maquina Virtual (Generado por SO)
Maquina Real
Instrucciones máquina
para
para
Lenguaje objeto Lenguaje de implementación
Lenguaje fuente
Programa fuente
(hecho en Pascal)
(o para un SO Windows - CISC)
Programa objeto
(o para un SO MacOS - RISC)
Compilador
(hecho en lenguaje C++)
Interprete
(utiliza bytecode) Lenguaje de
implementación C++
Java Sistema Computacional
Por eso se dice que el Java es el sucesor del C ++
Compiladores e Interpretes EPCI - UNPRG
Ing. Luis Reyes Lescano 2
Tipos de procesadores de lenguaje
Traductores
Funcionalidad: Toma todo el programa fuente y genera las instrucciones máquina (Prog.objeto),
inclusive genera el exe que es igual al Prog.objeto+cargadores (rutinas de ejecusión del SO).
Interpretes
Funcionalidad: Toma el programa fuente y genera instrucciones máquina necesarias sentencia
por sentencia (fuente) sobre la marcha. Muchas veces no genera el ejecutable y para esto necesita
del software de apoyo (linker).
Estructura de un compilador
ANALISIS LEXICO
- Es un análisis lineal
- Se da de izquierda a derecha
- Necesita de un analizador léxico o scaner
Programa
Fuente
(Leng. de alto
niv el o medio niv el)
Programa
objeto
(Leng. objeto o
máquina)
Compilador
Programa
Fuente
(Leng. de alto niv el)
Interprete
Programa
objeto
(Leng. objeto o máquina)
Programa
Fuente
(Leng. de ensamble)
Ensamblador
Programa
objeto
(Leng. objeto o
máquina)
Tabla de símbolos
uniformes Análisis Semántico
Análisis Sintáctico
Análisis Léxico Etapa de
Análisis
Tabla de manejo de
errores
Generación código interno
Generación código final
Optimizador
Etapa de Síntesis
PROG. FUENTE PROG. OBJETO
Compiladores e Interpretes EPCI - UNPRG
Ing. Luis Reyes Lescano 3
Funcionalidad:
- Se encarga de disponer el programa fuente en unidades sintácticas, es decir, palabras con
significado propio, denominados componentes léxicos o tokens. Por ejemplo: palabras
reservadas, identificadores, constantes, operadores aritméticos, operadores relacionales,
operadores lógicos, símbolos de asignación, símbolos de puntuación o caracteres especiales del
lenguaje, etc.
- Elimina los caracteres en forma de espacios en blanco, ejemplo: espacio en blanco,
tabulaciones y saltos de línea.
- Elimina los comentarios.
- Actualiza la tabla de símbolos uniformes, que es la contenedora de todos los tokens del
programa fuente actual.
Conceptos básicos:
- Palabra reservada: Es aquella palabra del propio lenguaje de programación que no se puede
usar como identificador de variables ni como funciones de usuario. Mayormente todas las
palabras clave son reservadas, pero algunas palabras reservadas no siempre son palabras
clave.
Ejemplo de palabras claves:
main, if, else, switch, while, do, etc.
Ejemplo de palabras reservadas:
printf(), scanf(), getch(), putpixel() , gotoxy(), etc.
Estas últimas palabras son reservadas, pero no son palabras clave ya que pueden ser creadas
por el usuario como funciones propias, siempre y cuando no se usen las librerías del C++.
- Tabla de símbolos uniformes: Se basa en:
Tabla de terminales (palabras reservadas)
Tabla de identificadores (variables)
Tabla de literales (constantes)
ANALISIS SINTA CTICO
- Es un análisis de tipo jerárquico.
- Necesita de un analizador sintáctico o módulo denominado Parser
Funcionalidad:
- Verifica en forma permanente la correcta escritura de las sentencias, teniendo como
parámetros un conjunto de reglas denominada ―gramática‖.
- Una gramática se representa formalmente o matemáticamente en base a un cuádruple de la
forma:
G = (P, T, N, S), donde:
P = Producciones o reglas
T = Conjunto de terminales
N = Conjunto de no terminales
S = Axioma, símbolo distinguido o metanoción
printf ( ―%d‖, dato);
int a =1;
float suma ( a , b );
token
Identificador
de función
Identificador de variable
Compiladores e Interpretes EPCI - UNPRG
Ing. Luis Reyes Lescano 4
- Sigue la forma BNF (Backus Naur Form) que coincide con la gramática de libre contexto de
Chomsky.
Ejemplo:
Reglas para el reconocimiento de una sentencia de asignación:
1. Un identificador es una expresión.
2. Un número es una expresión.
3. Pueden darse los siguientes casos:
expresión + expresión
expresión - expresión
expresión * expresión
expresión / expresión
Todas ellas son expresiones
4. ―Identificador = expresión‖ es una proposición.
Transformando estas reglas a BNF, sería:
Ahora planteemos estas reglas o producciones a una sentencia de asignación:
X = A + 3 * C - 5
exp id exp num exp exp + exp exp exp - exp exp exp * exp exp exp / exp prop id = exp
exp id | num | exp + exp | exp - exp | exp * exp | exp / exp prop id = exp
O SE PUEDE REPRESENTAR
X *
+ -
A 3 C 5
=
árbol aritmético
P: {exp id | num |
exp + exp | exp - exp |
exp * exp | exp / exp
prop id = exp }
T: {X,=,A,+,3,*,C,-,5}
N: {id,exp,num}
S: {prop}
forma
gramatical
parser
id num id num
prop
X exp * exp
A 3 C 5
exp + exp exp - exp
id = exp
Compiladores e Interpretes EPCI - UNPRG
Ing. Luis Reyes Lescano 5
EJERCICIOS
I. Desarrollar el parser para el reconocimiento de las siguientes sentencias de asignación:
a. X = A * B / C / 2 + 3 * (4 + 5 / 2)
b. X = 4 + 5 * 3 – 4 + 1 / 2 / 4 * 6 + (3 * 5)
exp + exp
id = exp
exp / exp
exp * exp
id id
A B
C num num
5 2
exp / exp
exp / exp
id
4
num 3
num
2
num
exp * exp
exp + exp
prop
X
4
num
4
num
3
num
5
num
exp * exp
exp + exp
exp – exp
2
num
1
num
exp / exp
exp / exp
4
num
exp * exp
6
num
exp + exp
3
num
5
num
exp * exp
id = exp
prop
X exp + exp
Compiladores e Interpretes EPCI - UNPRG
Ing. Luis Reyes Lescano 6
c. X = ((A + 3) + 5 * 4 + (6 / 3 * 4)) / 2 + 4 * 3
d. X = (A + (3 * 5 + (6 * 4 / 3 / 2)) + 4 – 5 * 4) / 5 / 2
5
num 2
num
exp – exp
4
num
2
num
3
num
4
num
exp * exp
6
num
exp / exp
exp / exp
3
num
5
num
exp * exp
exp + exp
A
id
exp + exp
exp * exp
5
num
4
num
exp + exp
exp / exp
exp / exp
id = exp
prop
X
id = exp
prop
X exp + exp
exp + exp exp * exp exp / exp
4
num
3
num
6
num
4
num
5
num
3
num
A
id
exp * exp exp + exp 2
num exp + exp
exp / exp
4
num
3
num
exp * exp
Compiladores e Interpretes EPCI - UNPRG
Ing. Luis Reyes Lescano 7
II. Desarrollar las gramáticas para el reconocimiento de:
a. Sentencia condicional if() prop_cond if (exp) then {prop} | if (exp) then {prop} else {prop}
dig 0 – 9 num dig | dig num letra a – z | A – Z comp letra | dig | _ | ( letra | dig | _ ) comp id letra | letra (comp) op_arit + | - | * | / op_rel < | > | <= | >= | <> exp_arit exp op_arit exp exp_rel exp op_rel exp exp_log exp AND exp | exp OR exp | NOT exp exp id | num | exp_arit | exp_rel | exp_log prop_asig id = exp prop_var id++ | id— prop_declar tipo prop_asig | tipo id
prop prop_asig | prop_var | prop_declar | prop_cond | (prop_asig | prop_var | prop_declar | prop_cond) prop
b. Sentencia repetitiva for() prop_rep for (inicia; evalua; var) {prop}
inicia prop_asig | prop_declar | (prop_asig | prop_declar), inicia evalua exp_rel | exp_log var prop_var | prop_asig | (prop_var | prop_asig), var
prop prop_asig | prop_var | prop_declar | prop_cond | prop_rep | (prop_asig | prop_var | prop_declar | prop_cond | prop_rep) prop
c. Sentencia de control while() prop_ctrl while (evalua) {prop} | do {prop} while (evalua)
prop prop_asig | prop_var | prop_declar | prop_cond | prop_rep | prop_ctrl |
(prop_asig | prop_var | prop_declar | prop_cond | prop_rep | prop_ctrl) prop
d. Sentencia de selección múltiple switch() prop_selec switch (id) {enuncia | defa}
enuncia case valores: prop; break; | case valores: prop; break; enuncia valores num | letra | num, valores | letra, valores defa enuncia default: prop; break;
prop prop_asig | prop_var | prop_declar | prop_cond | prop_rep | prop_ctrl | prop_selec | (prop_asig | prop_var | prop_declar | prop_cond | prop_rep | prop_ctrl | prop_selec) prop
e. Sentencia de escritura printf() prop_esc printf (―cuerpo‖) | printf (―cuerpo‖, var_esc)
cuerpo cad | format | (cad | format) cuerpo cad letra | dig | car_esp | delim | (letra | dig | car_esp | delim) cad format %d | %f | %c | %s car_esp ! | ¡ | ¿ | ? | < | > | ‗ | #| $ | % | & | @ | / | ) | ( | ; | : | , | . | ... delim eb | TAB | space var_esc id | exp_arit | ( id | exp_arit ), var_esc
prop prop_asig | prop_var | prop_declar | prop_cond | prop_rep | prop_ctrl | prop_selec | prop_esc | (prop_asig | prop_var | prop_declar | prop_cond | prop_rep | prop_ctrl | prop_selec | prop_esc) prop
f. Sentencia de lectura scanf() prop_lect scanf (―format‖, var_lect)
var_lect id | &id | (id | &id) var_lect prop prop_asig | prop_var | prop_declar | prop_cond | prop_rep | prop_ctrl | prop_selec | prop_esc |
prop_lect | (prop_asig | prop_var | prop_declar | prop_cond | prop_rep | prop_ctrl | prop_selec | prop_esc | prop_lect) prop
Definición de reglas que
serán utilizadas para la
construcción de la
gramática de las
sentencias siguientes.
A xioma de la gramática que irá incrementándose