UNIDAD 2_AUTOMATAS.pdf

5/26/2018 UNIDAD 2_AUTOMATAS.pdf

1/58

GENERACIN DE CDIGOINTERMEDIO

UNIDAD II


2/58

COMPILADORES TEORA E IMPLEMENTACION JACINTO RUIZ CATALN ALFAOMEGA

CONSTRUCCION DE COMPILADORES PRINCIPIOS YPRACTICA KENNETH C. LOUDEN THOMSON EDITORES

TRADUCTORES Y COMPILADORES CON LEX YACCJFLEX CUP Y JAVACC SERGIO GALVES ROJAS MIGUEL ANGEL MORA MATA


3/58

Analizar una mquina virtual que ejecute

cdigo intermedio a partir del cdigo fuente

de un lenguaje prototipo.


4/58

2.1 Notaciones

2.1.1 Prefija 2.1.2 Infija 2.2.3 Postfija

2.2 Representaciones de cdigo Intermedio. 2.2.1 Notacin Polaca 2.2.2 Cdigo P 2.2.3 Triplos 2.2.4 Cudruplos.

2.3 Esquema de generacin. 2.3.1 Variables y constantes. 2.3.2 Expresiones. 2.3.3 Instruccin de asignacin. 2.3.4 Instrucciones de control. 2.3.5 Funciones 2.3.6 Estructuras


5/58

CODIGO FUENTE

FRONT

END

ANALISIS LEXICO

ANALISISSINTACTICO

ANALISISSEMANTICO

Fases dependientes del lenguajeFuente e independientes de la

Maquina final

GENERACIN DECODIGO

INTERMEDIO

CODIGO INTERMEDIO

BACKEND

OPTIMIZACION DECODIGO

INTERMEDIO

GENERACION DECODIGO FINAL

OPTIMIZACIN DECODIGO FINAL

CODIGO FINAL /EJECUTABLE

Fases independientes del lenguajeFuente pero dependientes del cdigo

Intermedio y de la maquina final


6/58

Diferencia entre cdigo fuente y cdigoejecutable.

Diferencia entre cdigo interpretable y

cdigo ejecutable nativo.

Obtencin de cdigo ejecutable.


7/58

Arquitectura bsica de Von Neumann

En la memoria se almacena el programa y los datos necesariospara que ste opere

Instrucciones del procesador

Son las instrucciones bsicas que puede realizar la UCP.Con ellas se construyen los programas que puede entender la UCPcdigomquina

Cada instruccin bsica instruccin mquina se especificamediante un cdigo de instruccin junto con la informacin sobre

cmo obtener los operandos necesarios. Todo ello conforma elformatode instruccin.

FORMATO DE INSTRUCCIN

operador operando1 operando2


8/58

Unidad Central de Proceso CPU

Componente encargado de ejecutar lasinstrucciones que estn en memoria principal.

Capaz de ejecutar millones de instrucciones MHz


9/58

Las instrucciones de los programas sonalmacenados en la memoria primaria. Laprimer tarea del CPU es leer una instruccinde la memoria.

ELPROC

ESADOR


10/58

La unidad Prefetch le indica al bus queinstruccin o conjunto de instrucciones tieneque leer (direcciones de memoria).

Prelectura de la instruccin desde lamemoria principal.

ELPROC

ESADOR


11/58

La Unidad de Decodificacin toma lasinstrucciones ledas y las traslada a unaforma adecuada para el procesamiento

interno de CPU.operador operando1 operando2

ELPROC

ESADOR

FORMATO DE INSTRUCCIN


12/58

La Unidad de Control coordina y organizacuales elementos del CPU realizarn

funciones.

ELPROC

ESADOR


13/58

La Unidad Aritmtico Lgica (Logic Unit) seencarga de ejecutar las operacionescorrespondientes. Incluye registros de 32 o

64 bits generalmente.

ELPROC

ESADOR


14/58

Creacin y ejecucin de programas en cdigonativo (Lenguaje C)

Archivo de texto escritopor el programador


15/58

Ejecucin de cdigo intermedio (interpretado) Creacin y ejecucin de programas en cdigo

interpretado. (Java) Bite Code

hola.class


16/58

El cdigo intermedio (CI) es larepresentacin en un lenguaje sencillo de lasecuencia real de las operaciones que seharn como resultado de las fases anteriores.

Se trata de representar de una maneraformalizada las operaciones a llevar a cabo

en un lenguaje ms cercano a la mquinafinal, aunque no a una mquina concreta sino a una mquina abstracta.


17/58

Ventajas del cdigo intermedio

Aumenta la portabilidad delcompilador de una mquina a otra.

EJEMPLO Java

Fcil de producir. Reglas claras de construccin. Fcil de traducir al lenguaje objeto.


18/58


19/58

Las notaciones son una forma especial en laque se pueden expresar una expresinmatemtica y puedan ser de 3 formas:infija, prefija y posfija.

Los prefijos, Pre - Pos - In se refieren a laposicin relativa del operador con respecto alos dos operandos.

a + b

Operando Operador Operando


20/58

La caracterstica distintiva de esta notacines que coloca los operadores a la izquierdade sus operandos.

2+3

+ 2 3

No requiere de parntesis para indicar elorden de precedencia de operadores.

Se evala de izquierda a derecha hasta quese encuentre el primer operador seguidoinmediatamente de un par de operandos.


21/58

(3*6)/ (2+4)EVALUACIN

LECTURA FINAL


22/58

/ * 3 6 + 2 4EVALUACIN


23/58

(3*6)/ (2+4)4 2 + 6 3 * /

) )

+

E / /

)

/

*

E

EVALUACIN

LECTURA FINAL /*36+24


24/58

4 4

2

6 6

6

6

6

3

6

18

3

/ * 3 6 + 2 4

2+4 3*6 18/6

EVALUACIN


25/58

Nodo, Hijo_izquierdo, Hijo_derechoexpexp op exp|num

(3*6)/ (2+4)

*

3 6

/

+

2 4

/*36+24


26/58

Es la notacin comn defrmulas aritmticas y lgicas, en la cual seescriben los operadores entre los operandosen que estn actuando:

2 + 2No es tan simple de analizar por las

computadoras, como la notacin prefija o

la notacin postfija, aunque muchoslenguajes de programacin la utilizan debidoa su familiaridad.


27/58

Hijo_izquierdo, Nodo, Hijo_derechoexpexp op exp|num

(3*6)/ (2+4)

*

3 6

/

+

2 4

3*6 / 2+4


28/58

Se refiere a que el operador ocupa la posicin

despus de los operandos.

S = A + B * CS A B C * + =

Su principio es el de evaluar los datosdirectamente cuando se introducen y manejarlosdentro de una estructura LIFO (Last In First Out),

lo que optimiza los procesos a la hora deprogramar.


29/58

EVALUACIN

LECTURA FINAL

(3*6)/ (2+4)


30/58

EVALUACIN

3 6 * 2 4 + /


31/58

(3*6)/ (2+4)

3 6 * 2 4 + /

( (

*

/ /

(

/

(

+

E E

EVALUACIN

LECTURA FINAL 36*24+/


32/58

3 3

6

18 18

2

18

2

4

18

6

3

3 6 * 2 4 + /EVALUACIN

3*6 4+2 18/6


33/58

Hijo_izquierdo, Hijo_derecho, Nodoexpexp op exp|num

(3*6)/ (2+4)

*

3 6

/

+

2 4

3 6 * 2 4 + /


34/58

Generacin de cdigo: Simple No utiliza registros

Optimizacin Es difcil de reordenar ya que hay que considerar

el contenido de la pila (Polaca Inversa) Interpretacin rpida Es muy fcil de interpretar ya que solo necesita

una pila Transportable: Si, ya que todos los procesadores implementan

una pila.


35/58


36/58

if then else No se puede traducir a

If

Cdigo generadoSalta Si falso Etiqueta1

Salta Etiqueta2Etiqueta1:

Su principio es el de evaluar los datos directamente cuando se introduceny manejarlos dentro de una estructura LIFO (Last In First Out), lo que optimizalos procesos.


37/58

Es una especificacin de una Unidad Central

de Procesamiento donde las instruccionesestn diseadas a ser ejecutadas porsoftware (interpretadas) en lugar deHardware.


38/58

El cdigo P comenz como un cdigoensamblador objetivo estndar producido porvarios compiladores Pascal en la dcada de

1970.

Fue diseado para una maquina de pilahipottica la idea era hacer que loscompiladores de Pascal se transportaranfcilmente.


39/58

En la creacin de cdigo intermedio se utilizaninstrucciones simblicas para representar losdatos (variables, parmetros, etc.) queposteriormente se trasladarn a direcciones

reales en el mapa fsico de memoria.


40/58

Cada instruccin de tres direcciones tiene a lo

sumo un operador.

El compilador debe generar un nombre temporal

para guardar los valores calculados por cadainstruccin.

Algunas instrucciones de "tres direcciones" tienemenos de tres operadores.


41/58

CudruplosTriplos


42/58

Ejemplo:

x=x+1; //Supongamos que x representa un entero

Pasos para generar el CI

R1= valor (x)

R2= valor (1)

R3= R1 + R2

x=R3

CODIGO DE TRES DIRECCIONES

CARGAR x null R1 CARGAR 1 null R2 SUMAR R1 R2 R3 CARGAR R3 null x

CDIGOD

ETRESDIRECCI

ONES


43/58

int x

main(){x=0;x=x+1;

}

CARGAR 0 null 10000CARGAR 10000 null 9000

CARGAR 9000 null 10001CARGAR 1 null 10002SUMAR 10001 10002 10003

CARGAR 10003 null 9000 CDIGOSDET

RESDIRECC

IONES

posteriormente setrasladarn a direccionesreales en el mapa fsico dememoria

CI

CARGAR x null R1 CARGAR 0 null R1 CARGAR 1 null R2 SUMAR R1 R2 R3 CARGAR R3 null x

OTROS ARGUMENTOS DEL CI


44/58

OTROS ARGUMENTOS DEL CI

RESTAR, MULTIPLICAR, DIVIDIR

OR, AND

MAYOR, MENOR (Si se cumple coloca 1 en el res) IGUAL, DISTINTO

ETIQUETA

Salto incondicional SALTAR_ETIQUETA null null etiq

Saltos condicionales SALTAR_CONDICION op1 null etiq //SOLO SI ES FALSA

IMPRIMIR_ENTERO 7 null null

IMPRIMIR_CADENA cad null null

Llamada al procedimiento p(x 1,x 2,...,x n). paramx1

...

paramxn

Call p,n

EL CI es muy prximo a un lenguaje ensamblador


45/58

If a


46/58

, ,

El resultado se asocia al nmero de tripleta

Ejemplo: W*X+(Y+Z)

1( *, W, X)

2( +, Y, Z)3 (+, (1), (2))


47/58

Control de flujo:

IF X>Y THEN Z=X ELSE Z=Y+11 (>, X, Y)2 (Saltar si falso, (1), 5)3 (=, Z, X)

4 (Saltar, , 7)5 (+, Y, 1)6. (=, Z, (5))7. ...


48/58

SI FALSO


49/58


50/58

EJERCICIO:A=B+C*D/EF=C*D

Operaciones Tripletas1. (1) (1) *, C, D2. (2) (2) /, (1), E3. (3) (3) +, B (2)4. (4) (4) =, A, (3)

5. (1) (5) =, F, (1)6. (5)


51/58

Los cuartetos son la herramienta ms general InconvenientesOcupan demasiado espacio Requieren muchas variables auxiliares para almacenar

los resultados intermedios Los tercetos resuelven este problema

suprimiendo el operando del resultado, quedaimplcito y asociado a dicho terceto

Inconvenientes La optimizacin supone mover tripletas y hay que

recalcular las referencias


52/58

int x 10;


53/58

int x = 10;

int y = 0;

main(){

while(x>0){

y =y+x;

x=x-1;

}

print(Si leer);

if(x==0 && y>54){print(Si leer);

}else{

print(No leer);

}

}

CARGAR 10 null 10001CARGAR 0 null 10002ETIQUETA null null BUCLE_1CARGAR 10001 null 10003

CARGAR 0 null 10004MAYOR 10003 10004 10005SALTAR_CONDICION 10005 null FIN_BUCLE_1CARGAR 10002 null 10006CARGAR 10001 null 10007SUMAR 10006 10007 10008

CARGAR 10008 null 10002CARGAR 10001 null 10009CARGAR 1null 10010RESTAR 10009 10010 10011CARGAR 10011 null 10001SALTAR_ETIQUETA null null BUCLE_1

ETIQUETA null null FINBUCLE_1IMPRIMIR_CADENA cadena1 null null

int x = 10;


54/58

CARGAR 10001 null 10013CARGAR 0 null10014IGUAL 10013 10014 10015CARGAR 10002 null 10016CARGAR 54 null10017MAYOR 10016 10017 10018

AND 10015 10018 10019SALTAR_CONDICION 10019 null ELSE_1IMPRIMIR_CADENA cadena2 null nullETIQUETA null null ELSE_1IMPRIMIR_CADENA cadena3 null null

int x = 10;

int y = 0;

main(){

while(x>0){

y =y+x;

x=x-1;

}

print(Si leer);

if(x==0 && y>54){print(Si leer);

}else{

print(No leer);

}

}

CARGAR 10 null 10001


55/58

int x=10;

int y=20;

while (x*2x*4){

x=x+1;

}

}

CARGAR 20 null 10002ETIQUETA null null BUCLE_1CARGAR 10001 null 10003CARGAR 2 null 10004

MULTIPLICAR 10003 10004 10005CARGAR 10002 null 10006MENOR 10005 10006 10007SALTAR_CONDICION 10007 null FIN_BUCLE_1ETIQUETA null null BUCLE_2CARGAR 10002 null 10008

CARGAR 10001 null 10009CARGAR 4 null 10010MULTIPLICAR 10009 10010 10011MAYOR 10008 10011 10012SALTAR_CONDICION 10012 null FIN_BUCLE_2CARGAR 10001 null 10013

CARGAR 1 null 10014SUMAR 10013 10014 10015CARGAR 10001 null 10015SALTAR_ETIQUETA null null BUCLE_2SALTAR_ETIQUETA null null BUCLE_1ETIQUETA null null FIN_BUCLE_2ETIQUETA null null FIN_BUCLE_1

int x=1-12;TAREA


56/58

;int y=x*32main(){

x=1-12;y=x*32;x=(32/12)*y;

if(x>7){

while(y>0){y=y-1;if(y>1){print(y);}

}}

}

TAREACUADRUPLOSY TRIPLOS


57/58

COMPILADORES TEORA E IMPLEMENTACION JACINTO RUIZ CATALN ALFAOMEGA

CONSTRUCCION DE COMPILADORES PRINCIPIOS YPRACTICA KENNETH C. LOUDEN THOMSON EDITORES

TRADUCTORES Y COMPILADORES CON LEX YACCJFLEX CUP Y JAVACC SERGIO GALVES ROJAS MIGUEL ANGEL MORA MATA


58/58

GENERACIN DE CDIGOINTERMEDIO.

UNIDAD II

Documents

UNIDAD 2_AUTOMATAS.pdf