Clase 0608¶
Aplicaciones de la traduccion orienndada por la sintaxis¶
Una cosa que debemos de tomar en cuenta que no debemos de tener ciclos, ademas en un arbol para su analisis semantico debemos usar aquel que es ascendente. No descendente ya que es mas facil de recorrer que el anterior.
Construccion de arboles con atributos heredados¶
Aqui mira que tenemos recursividad por la izquierda asi que implementamos un reocrrido ascendente.
Los atributos sintetizados sirven para redirigir la inormacion a la raiz del arbol
Siempre y cuando la informacion se obtenga de los padres y hermanos. Cuando la informacion se obtenga de ellos mismos.
No es posible, porque hacemos reducciones en el cuerpo, y puede que para reducir B necesitemos A . Entonces por eso no se puede.
Clase 1108¶
Generacion de codigo Intermedio¶
Despues de tener el analisis lexico y sintactico, en el analisis semantico , determinamos si esta semanticamente correcto.
Podemos asumir que no tiene errores ni lexicos, ni sintacticos ni semanticos. Algunas validaciones semanticas son sintacticas, como ver si tenemos una sentencia break y ver que este dentro de un ciclo.
Entonces como esto es muy complicado se queda en una validacion semantica.
Diagrama de fases de un compilador¶
La salida del analizador semantico es la entrada del codigo intermedio, vamos a asumir que el generador de codigo intermedio esta bien, no tenemos que validar nada mas.
Luego de eso vamos a tener una rperesentacion intermedia o "codigo de 3 direcciones", y luego se crea a aseembler.
Queventajas tiene este modelo on el anterior.
Si nosotros usamos un fronted para una generacion intermedia y un backend para el ensamblador ,podemos hacerlo si la representacion intermedia esta estandarizada.
Es indispensable generar codigo intermedio ?¶
Es indispensable crear codigo intermedio no es indispensable, pero si sirve para poder dividir el codigo intermedio porque . Depende de como vamos a manejar representaciones intermedias que son lengaujes intermedios.
Por ejemplo los primeros compiladores de c++ eran convertidos a c y luego estos a assembler.
La ventaja de tener un codigo de 3 direcciones o representacion intermedia es que es reversiblle.
Vamos a tener 3 cosas
- Programa fuente
- Representacion intermedia a alto nivel
- representacion intermedia a bajo nivel
- codigo convertido.
Ves que el a aparece mas de una vez , esto pasa porque lo que vamos a hacer es representar el arbol de una manera mas optima, con un grafo dirigido aciclico, con esto reducimos reundancia
En una definicion dirigida por la sintacis, al generar un arbol de analisis sintactico , en la parte baja tendriamos un arbol sintactico. La idea que nosotros vamos a trabajar, es que con esta direccion, dirigida por la sintaxis, sino crear el grafo aciclico, es lo mismo que la anterior,
Ahora al crear el arbol de analisis sintactico, con la gramatica, ya no creamos el arbol sintactico haciendo consulta de los nodos ya visitados. Entonces solo se reutiliza.
La reutilizacion se hace recorrer el arbol en une estructura de datos, lo vuelvo a reutilizar. Lo que hago es si encuentro que ese nodo ya existe.
Esa estructura de datos la indexamos de cierta manera , y la idea general es , si voy a generar un nodo nuevo, antes de crear el nodo, y si ese valor ya existe lo que debo de devolver es la llave de ese registro, y si luego de eso hago a busqueda y no encuentro ningun valor lo genero como nuevo nodo. Pra esto guardamos el padre, hijo izquierdo, hijo derecho y si lo encuentro lo devuelvo sino lo creo.
El problema es que debemos de optimizar las busquedas asi que cambiamos a una tabla hash para que optimice esto.
Codigo de 3 direcciones¶
Es una representacion lineal de un arbol sintactico , con las ventajas con el arbol aciclico. Es factible optimizar ,
< direccion > = < direccion > < operador > < direccion >
direcciones
- Variable
- Constantes
- Variable temporal por el compilador generada.
No se hacen mas de 3 referencias a posiciones de memoria.
Algunos ejemplos son
- Instruccion de asignacion
x = y op z
x = op z
instruccion de copia
x = ySalto incondicional
goto L
Siempre tenemos que tomar en consideracion este tipo. Este lenguaje de alto nivel , lo traducimos a algo equivalente pero debe de hacer exactamente lo mismo. Para todo esto para llevarlo a un plano un poco mas complejo, lo llevamos a algo mas sencillo
x + y * z
Se traduce a
t1 = y * z
t2 = x + t1
Esto se hace para no ocupar mas de 3 espacios de memoria, vamos a representar las variables como variables de este tipo como simplicidad, entonces hacemos referencias a la tabla de simbolos a las entradas que representan estas variables.
Esto se endendera mejor con mas ejemplos.
Las variables temporales no se guardan en la tabla de simbolos, y tiene por objeto no se salgan las lineas del codigo de 3 direcciones.
Ahora como convertimos
a + a * (b-c) + (b-c) * d
Generamos una instruccion para el paraentesis
t1 = b - c
t2 = a * t1
t3 = a + t2
t4 = t1 * d
t5 = t3 + t4
Clase 1308¶
El lenguaje de alto nivel cosas complicadas como polimorfismo, y objetos, y interfaces y cosas mas horribles como asyncronismo. Cosas de ese pinche estilo es por eso que se usa el codigo de 3 direcciones visto anteriormente.
El codigo de 3 direcdciones no espera que sea eficiente. Sino que lo convierta a 3 direcciones .
Esto se divide en 2 y no lo optimiza, debido a que es mucho mas dificil de optimizar de una que ya tener uno y optimizarlo
Operaciones comunies¶
- Saltos con goto L,
- Salto condicional con operador relacional
- Instrucciones de copia indexada
do i = i + 1 ; whitle (a{i} < v);
En codigo de 3 direcciones seria
L. t1 = i + 1
i = t1
t2 = i * 8 // se multiplica por 8porque son variables enteras, esto sirve para indicar al puntero moverse 8 unidades
t3 = a[t2]
if t3 < v goto L
La mejor forma es que cada linea tenga su propia etiqueta de valor
Y como lo guardamos ? ,
Lo que podemos hacer es usar una estructura de datos. Si se acaba la ram, si lo guardo en una estructura de datos no hay problema en la ram ya que se guarda en una posicion.
Hay varias formas de estrutctura de datos, la estrcutrua de datos es cuadruplos
Una tabla, con indice, operador, arg1, arg2, resultado
El operador es el operador donde se ejeucta, el resultado es el temporal o variable en donde se va a guardar ,
el arg 1 y arg 2 es de los 2 eejecutados.
Ahora el = que se hace es si solo existe ese se ppone como operador en las demas esta implicito que se guardo en el resultado.
No vamos a hacer busquedas, sino que vamos a dar un acceso secuencial , por eso se utiliza este tipo de estructura.
Se llama CUADRUPLOS
Tripleta
La tripleta no guarda el resultado, tipo operador, arg1, y arg2.
Esto ocupa menos ram, El pedo es que es que la optimizacion es bien compleja y sevuelve mas complicada el hacer cambios
Clase 18082025¶
La logica de nuestro codigo original , debe de preservar en el codigo de 3 direcciones el significado semantico del lenguaje osea mantener la misma funcionalidad.
Llama a procedimiento o funcion¶
param x1
param x2
param x3
....
param xn
call p, n
y = p + n
return y
Supongamos que tenemos un archivo de texto plano con nuestro codigo de 3 direcciones. La dificultad es que tenemos que hacer un lexer y parser para leer el codigo, y se hacen pasos adicionales. Para recuperar la info. Este es un desafio innecesario
Lo que debemos de hacer es guardarlo en una estructura de datos . Si lo hacemos en una estructura de datos nos hes posible recuperar la informacion en Ram simplemente accediendo a partes especificas.
Ahora guardarlo no hay problema, porque el SO se encarga de guardar en disco si excede la RAM
Es mejor idea usar tripletas si no voy a optimizar, si voy a usar cuadruplos mejor usalo antes
Entornos en tiempo de ejecucion¶
Si te acuerdas en assembly no hay ambitos, como manejo clases , paradigmas e interfaces, lllamadas a funciones complejas en un lenguaje donde no hay valores de retorno.
Pero siempre respetando lo del significado semantico del lenguaje. Osea como convierto cosas complejas de alto nivel a cosas simples de bajo nivel. Todos los conceptos que definimos de cosas complejas realmente son abstraidos.
Abstraccion¶
Es aislar conceptualmente propiedades de un objeto. Y la definicion de informatica es aislar fuera de su contexto.
Para entender como se implementan los conceptos, vamos a ver como se subdivide la memoria. Para que se pueda ejectuar el codigo , el compilador crea un entorno en tiempo de ejecucion, en donde asigna las direcciones de memoria.
Ya vimos que desde la perspectiva del compilador, nos vamos a enfocar en direcciones logicas y que son contiguas. No vamos a caer en la complejidad de donde lo guardo, sino que vamos a asumir que nuestro compilador maneja un nivel de abstraccion. Entonces las referencias a direcciones fisicas no hay , talvez si en cierto punto pero mas que todo direcciones logicas.
Otra cosa que vamos a asumir, pero eso depende del procesador. Pero vamos a sumir con procesadores de 32 bits
Memoria y su uso¶
- Codigo: Es algo logico nada mas, ir a colocar el codigo ensamblador que vamos a ejecutar cuando el programa vaya a correr. Lo vamos guardar en ram nuestro codigo de ensamblador. Podemos identificar de que tama;o nos quedo el codigo ensamblador.
- Datos estaticos : Cuando lleguemos a tener datos estaticos, en donde tengamos datos globales, que le servira de utilidad al garbage collector. Podemos saber a ciencia cierta que tama;o de ram se necesita para guardar que datos son estaticos.
Areas Dinamicas¶
Si la pila crece el espacio de monticulo se reduce y la pila, si el monticulo crece la memoria libre se reduce. Y la pila crece tambien se reduce la memoria libre
- Monticulo: Asignar y desasignar datos , pero dado por el programador. Un ejemplo es C y el uso de malloc.
- Pila : Llamadas a procedimientos.
Como se sabe cuanto debo de reservar de ram para una variable.
En el monticulo si necesita mas memoria va pidiendo mas memoria libre. Si hacemos mal uso del monticulo tendremos programas ineficientes
Estatico y Dinamico¶
La idea que cuando hablamos de algo dinamico es como se maneja la memoria en tiempo de ejecucion, y estatico es memoria en tiempo de ejecucion. Ahora el problema es que tendremos cosas llamadas iguales pero estaran guardadas en lugares distintos
Jerarquia de memoria¶
La memoria tiene una caracteristica, la que es pque;a es rapida, la pe;a es cara y la grande es mas barata.
- Registros guardan 32 palabras. La ventaja es que lo jalamos en 1 ns
- La cache es el 2do nivel, 16kb hasta 64kb. 5 a 10 ns
- La cache L2, es 128kb a 4MB 40 a 60 ns
- La ram podemos guardar hasta 2GB osea 100ns a 150ns
- El siguiente almacenamiento es Memoria Virtual 3ms a 15 ms y mas de 200 GB
Lo que debemos de optimizar es el acceso a memoria. Otra cosa que es bien importante, es que podemos usar el procesador que utilice los registros. Lo que va a hacer el procesador es utiliza cache , sino ram y sino a memoria virtual.
Lo unico que le podemos decir es que utilice registros o memoria
Lo que no existe es que exista almacenamiento rapido y grande .
Existen algunos fenomenos, como localidad temporal si las ubicaciones de memoria que las accede las volvera a acceder en corto tiempo.
Localidad espacial es que vuelva a utilizar localidades cercanas
Heap¶
Objetos podemos guardarlos en el monticulo o heap.
Clase 2008¶
Como puedes ver en nmemoria se consturye un arbol de activacion es un arbol compuestos de procesos que llaman a otros procesos. anidados
En cada nodo tenemos
Vamos a tener un parametro por referencia vamos a tener un puntero.
Clase 25082025¶
Administrador de MEMORIA¶
- Asignacion de espacios
- Desasignacion de espacios
Si el heap crece seq queda de un tama;o expandido y no regresas a quedar en un tama;o reducido.
Propiedades deseadas
- Eficiencia de espacio
- Eficiencia del programa
- Baja sobrecarga
Subidivison de Memoria¶
El monticulo informacion de objetos Pila llamadas a procedimientos Codigo es las instrucciones Datos estaticos son los que nunca cambian
REegistro de activacion¶
Es algo logico , y tener que partes del almacenamiento abarca.
Parm actuales : Parametros que usa el procedimiento que hizo la llamada. Como cambia el registro de activacion si uso una lammda de procedimiento si los parametros pasan por valor o por referencia. Cuando le mandamos parametros por valor, y si en el procedimiento lo altero
valor devuelto valor que devuelve
enlace de contro
enlace de acceso: Cuando en el procedimiento cuando una variable esta antes en la pila de contro, se necesita un puntero a esos datos para conocer el valor. Parece como si fuese una variable de referencia.
Estado maquina guardada. Como se encontraa la maquina antes de hacer la llamada, ya que tras realizar todo el changarro , los registros del procesador tengan el mismo valor
datos locales
Datos propios del procedimiento.
- Temporales maneja las variables temporales, en algun moemnto necesitamos ir guardando valores temporales.
Que pasaria ocn la pila de control en la llamada de procedimiento, cuando etenemos lallamada en maiz se crea en mjmia es un registro de activacion Toda esta
Garbage Collector¶
La recoleccion es escencial pero es dificil de realizarse con eficiencia. . En el heap es en donde vamos a encontrar basura. Hay un conceto interesante.
En la pila suceden mas buasura y no se marco como memoria libre
Los objetos tienen que tener un tipo y el garbage debe saber que sinigifca ese tipo.
Lo primero que debemos de suponer es que tiene la posibilida de conocer los tipos de datos de maner adinamica, en tiempo de ejecucaion el tam;o del heap. Si se cual es el tipo del objeto se cuanto ocupa del taama;o
Las referencias es referencia a la direccion de memoria y a la primera posicion.
Hay varios tipos de garbage collector.
- Basado en Rastreo
Empieza a buscar en el heap todos los objetos que son utiles y los que estan siendo utilizados y no tienen una referencia vacioa. Despues de hacer ese barrido, todo lo que no encuentre una referencia asume que no lo va a poder reutilizar. De maner aparaelella hace movimiento los objetos,
- Por conteo de referencias Una manera de identificar si no se va a usar, es saber que ya no va a ser util . Otra tecnia que se utiliza es pasar por lugares de referencias de los objetos. No llega a encontrarse a ningun lugar que haga referencia a ese objeto. Tener un control que los objetos qe se han creado, buscar las referencias y contar las referencias. Y si las referencias son 0 entonces ese objeto no se va a utilizar.
El problema que da es que
INTERMEDIO A ENSAMBLADOR¶
OBJETIVOS¶
Podemos ver que el codigo intermidio es la fase antes del optimizador. No vamos a trabajarla pero no es necesario. Y luego el codigo intermedio
El frontend es todo lo que abarca desde el lexer hasta el generador del codigo intermedio. Tenemos la tabla de simbolos llena , generado los cuadruplos.
Usamos codigo ensamblador porque podemos tener un frontend que es compatible con varios backends.
Lo que yo escribi en el lenguaje de alto nivel cuando tenga el codigo ensamblador debe ser una traduccion. Debe hacer lo mismo.
No es factible sino es indispensable de cumplir. Debemos de respetar el significado semantico del lenguaje. El segundo objetivo es generar codigo de buena calidad.
El codigo debe ser de buena calidad. Osea que no es indispensable porque esta no es la ultima fase del proceso de compilacion. Podemos tener una fase extra de la optimizacion del ensamblador pero no es factible porque no hay una manera matematica a hacerla.
Ahora la duda es si generarle de manera eficiente no es necesario o no es indispensable. Si se tarda en compilar un poco mas no importa, lo que importa es que tenga buena calidad aunque tengamos otra fase.
Y el siguiente objetivo es que sea facil la generacion y mantenimiento.
HEURISTICA¶
Es vista como el arte de inventar por parte de los seres humanos. Para la parte no tenemos esos algoritmos como la receta de como hacerlo de la manera correcta. Debemos de usar nuestro ingenio, un compilador que se hizo uso de heuristicas genera codigo mas rapido a diferencia del cual no se hizo.
Los retos son
- Seleccion de instrucciones. La estructura de datos que vamos a guardar el codigo de 3 direcciones son los cuadruplos y tripletas, Y vamos a ir linea por linea. Vamos a ir linea por linea. Y eso tiene un equivalente de instrucciones en esnsamblador . Y van a ser las instrucciones equivalentes en ensamblador para eso. Conocer en la maquina de destino que instruccion en ensamblador es equivalente. Yo barro la estructura , registro por registro yo ya tengo un lugar si tengo una operacion de suma que es equivalente en ensamblador. Osea mapear por cada operacion.
Genero todas esas operaciones de ensamblador que respetan el significado semantico
- Particion y asignacion de registros. Cuando yo encuentre la primera instruccion de ensamblador , tengo que respetar la arquitectura .
El primer reto que vamos a tener que almomento de mover registro a memoria. La primera vez podria parecer que cualquier opcion es buena. Que vamos a saber que registro utilizar. En que momento un valor del registro lo debo dejar ahi y no meterlo en memoria. Que valores colocar y que valores mantener , sabemos que de todos los almc el registro es el mas rapido.
Si tenemos un numero limitado de registros. Ese es otro reto que nos vamos a encontrar. Y el otro es el orden de ejecuciones que nos vamos a encontrar. Para ciertas partes del ensamblador lo va a colocar en un orden distinto.
Arquitecturas¶
Dependiendo de las caracteristicas de la maquina de destino va a depender mucho de lo que vamos a usar.
- CISC
Esta es la de mi maquina , son complex instrucction set computer. Tiene pocos registros, pero la manera de interactuar osea que son amplios, y las instrucciones son mas complejas. Cada registro tiene propositos especificos. No puedo usar n registros para todas las operaciones .
- RISC
REview instruction set computer. Tiene mas registros que una arquitectura cisc, las formas como se interactuan entre memorias y registros son formas simples, y podemos hacer operaciones con 3 direcciones. Una maquina risc podemos tener esas opciones de 3 direcciones
- Maquina de pila
La arquitectura mas usada es la maquina de pila. Se colocan los operandos de la pila.
De que tan buena calidad debe ser el codigo que debemos generar.¶
El mapeo entre instrucciones de 3 direcciones y ensamblador es un desafio mas facil de abordar. Debemos de enteneder que hacer en esta fase un poco antes de completar la fase anterior. Si generamos un codigo intermedio de menor nivel. Algunos ejemplos de como se genera este codigo ensamblador. van a ser los siguientes
EJEMPLO
x = Y + Z
Para convertirla usaremos los primeros registros todo los persibimos en memoria. Los registros podemos hacer referencia a registros
El valor dque esta del registro 1 sumelo al registro 0 y guardelo en el registro 0. Lo que debo de hacer uso ahora de ST, el problema es que en cada instruccion puede hacer una cosa , la idea base es que cuando pasa un ciclo que se ejecuta una instruccion, si tneemos instrucciones demas, tendremos un uso ineficiente por eso no debemos.
En pocas palabras debemos de evitar hacer uso de ram si tenemos informacion en los registros.
Aqui tnego una inneficiencia evidnete porque guardo y luego cargo . El impacto es evidente.
Clase 29092025¶
Los modos de direccionamiento RISC son sencillos pero costosos, pero son mas populares los CISC La maquina de pila ya no existe la mataron xd
En este ejemplo se hicieorn mas uso de instrucciones por traer a memoria, pero podemos ahorrar espacio obviando esto con informacion que tengamos en los registros
Debemos de evitr los conceptos, vamos a asumir que nuestra maquina es RISC, tendremos registros de proposito general no especifico.
Como van a ser ejemplos peque;os no usaremos varios registros .Haremos operaciones con 3 direcciones
Operaciones¶
Lo que hace LOAD es pasarle el registro y luego en donde va a estar en memoria lo que vamos a traer
Para hacer operaciones de calculo
Modos de direccionamiento
aqui lo que le dijo que lo que voy a cargar va a ser el contenido de a mas la direccion del registro 2
Clase 1 de Octubre¶
MIPS muchos lo usan porque el direccionamiento de memoria es mas facil
Ejemplo con variables
buscaremos en memoria la variable i y la cargaremos en el registro 1
El 4 ejemplo es
Una forma es hacer una resta de registros . Pero usamos BLTZ para hacer un salto condicional si R1 es menor a 0
Con un string lo manejo como puntero , basicamente lo trato como puntero. Como booleanas podemos guardar valores numericos
Las opciones para booleanos usare la maquina destino desea
Direcciones de Memoria en codigo Destino¶
La memoria es almacenamiento y toda la memoria que vamos a tratar es volatil osea no se guarda
Lo vamos a ver como una columna de celdas con posicion y valor
Como se genera el codigo destino¶
vamos a tener una estructura de datos la represntacion intermedia osea el codigo de 3 direcciones como cuadruplos o tripletas y vamos a buscar las direcciones de ensamblador equivalentes
Vamos a otmar en cuenta ciertas consideraciones.
El codigo que este generando debe de tener calidad. El codigo tiene que ser compacto
Subdivision de la memoria¶
Son subdivisiones a nivel logico
- Los datos estaticos son constantes que no cambiaran
- Heaps guardaremos los objetos y yo no se que valor se guardara ahi
- Espacio libre
- La pila guarda llamadas a procedimientos y registros de activacion
Vamos a interactuar con en codigo. Cuando hagamos llamadas a procedimientos guardamos en pila.
En pila pila los registros de activacion tienen informacion diversa. Una vez que tenemos claro que necesitamos surge la pregunta.
COMO VAMOS A ASIGNAR MEMORIA¶
Antes definimos terminologia
- action es un bloque de codigo
- call llamado a procedimiento
- return devolver valor de memoria
- halt es devolver el control al SO
Ejemplo
Lo que va a consistir esta secuencia es que los actions se ejecuta 1, 3, 2
Este es el codigo ensamblador del anterior. estos numeros son las posiciones en memoria
Por eso se guarda en una upicacion logica de la memoria osea llamada "codigo".
si ves saltos es porque eso ocupa la instruccion
podes ver que el * es un direccionamiento o un puntero
y por eso nos manda a la linea 140 y ejecuto el bloque de acciones
esto es el registro de activacion de p que vimos anteriormente en la imagen
Osea que la primera imagen es codigo , la segunda es pila
No hay limites, estos son logicos
Debemos de ir definiendo eso
En realidad uno el codigo y la pila aumentan y disminuyen direcciones y el desafio es manejar el procedimiento
Ejemplo asignacion en pila¶
Este codigo lo traduciremos a ensamblador, m es el main q es quicksor que parte en 2 y llama a p y es recursivo .
La pila que lo primero se pone al inicio de esta y lo ultimo esta hasta arriba.
Este es el ejercicio