Resumen Final

Competencia entre recursos.

Semáforos
Acceso restringidos: permite que se hagan lecturas antes de la escritura, permitir lecturas durante la escritura pero no tomando la zona modificada la lectura se bloquea.
Lecturas sucias ( son los registros fantasmas).
Paralelismo:
Son ejecuciones que se realizan en  paralelo.
Scheduler: asigna espacios de ejecución y resuelve bloqueos.

Distribución y clasificación

Clasificación de arquitecturas:
SISD: Single Instruction Single Data .
SIMD: Single Instruction Single Data.
MISD: Multiple Instruction Single Data.
MIMD: Multiple Instruction Multiple Data.


Ligas entre lenguajes

Algunos de los objetivos en los que es utilizada:
Mejor acceso a recursos.
Buscar los beneficios de un paradigma.
Necesidad por la plataforma.
Mejora el rendimiento.
Programar algoritmos complejos en el lenguaje principal.

Generador de código (Video)

https://www.youtube.com/watch?v=1zVedvs7Qr8

Tabla de símbolos (Video)

https://www.youtube.com/watch?v=mHMcGOjbjtU

Resumen 10

1. Asignaci on de memoria

Tiempo de ejecuci ón

Estructura  activaci ón de memoria:
- Stack.
- Enlaces de control.
- Informaci ón de entorno.
- Valor de retorno.
- Par ametros.
- Variables temporales.

Valor de retorno: es la informaci on acerca de los datos o direcciones donde se debe
cargar la respuesta si se requiere.

Stack: es el espacio utilizado para la asignación de memoria

Enlaces de control: guarda informaci on de relaciones en la memoria entre cada
llamada de activació n.

Primer enfoque: asignaci ón de bloques :
- Se asigna un tamano.
- El sistema operativo casi siempre ocupa la posici on 0.
Ventajas: Facíl de implementar.

Desventajas: Desaprovechamiento de la memoria y limitaci on para la
asignaci on din amica.
Fragmentaci on:
    - Interna: Son los espacios dentro de un proceso.
    - Externa: Espacios entre dos procesos.


2. Segundo enfoque particiones

Ventajas: Simple,  mejor utilizaci on de la memoria.

Desventajas: Fragmentaci ón, mala utilizaci ón por parte de los
desarrolladores.

C omo asignar un espacio nuevo?
     -Primer espacio: es m as simple pero no necesariamente es mejor.
     -Mejor espacio: es el que mejor se ajuste, mayor aprovechamiento y se
realiza un recorrido de toda la memoria.
     -Peor espacio: es m as grande, busca que los espacios disponibles sean del
mismo tamaño y se da un recorrido de toda la memoria.

Utilizaci on de un Heap: se solicita un espacio inicial m aximo a ser
utilizado, es utilizado como t ecnica dentro del proceso para que la
aplicaci on utilice el espacio solicitado.

Resumen 9

Estilos de programación

Programación iterativa: se utiliza menos memoria, hay una mejor utilización de memoria y menos llamadas de actuación.

Programación recursiva de cola:  Si la llamada recursiva es la operación más externa, es decir la última operación que se ejecuta.

Programación recursiva: Se puede considerar como solución.

Usos: Lenguajes Funcionales

Desarrollo académico.
Desarrollo científico.
Desarrollo comercial.

Lenguajes lógicos

Son formados por:
         -Consultas.         -Predicados.
         -Teoremas.

Definiciones:

Teoremas: Son simples sentenias que se toman como verdaderas.
Predicados: las predicciones son construcciones de condiciones que permiten modelar expresiones complejas y paramétricas.
Consultas: es el ingreso de problemas que se resuelven a partir de teoremas y  predicados.

Funciones puras:

No generan ningún efecto de contexto.
Si llamamos con los mismos parámetros, obtenemos  el mismo resultado.

Grafos Dirigidos Aciclicos (Video)

https://www.youtube.com/watch?v=hrRdVlYdYQE

Resumen 7

Paginación de memoria

Dividen los programas en pequeñas partes o páginas. Del mismo modo, la memoria es dividida en trozos del mismo tamaño que las páginas llamados marcos de página.

En un momento cualquiera, la memoria se encuentra ocupada con páginas de diferentes procesos, mientras que algunos marcos están disponibles para su uso. El sistema operativo mantiene una lista de estos últimos marcos, y una tabla por cada proceso, donde consta en qué marco se encuentra cada página del proceso. De esta forma, las páginas de un proceso pueden no estar contiguamente ubicadas en memoria, y pueden intercalarse con las páginas de otros procesos.

Las tablas de paginación o tablas de páginas son una parte integral del Sistema de Memoria Virtual en sistemas operativos, cuando se utiliza paginación. Son usadas para realizar las traducciones de direcciones de memoria virtual (o lógica) a memoria real (o física) y en general el sistema operativo mantiene una por cada proceso corriendo en el sistema.

 ALGORITMOS DE SUSTITUCIONES
- Menos usada.
- FIFO.
- Optima: toma la pagina que se usara menos en el futuro.
- reloj.

Resumen 6

1. An alisis sem antico

Sistema de tipo

Es la organizaci on impl ícita de operadores, variables, constantes, funciones, procedimientos los cuales tienen un valor y un tipo.

Contexto

Son los bloques que de nen el alcance de diferentes objetos como: variables, funciones, grupos de restricciones, entre otros.

Sobrecarga de operadores
La sobrecarga de operadores es un mecanismo que  aumenta las capacidades de los lenguajes de programaci ón orientados a objetos. En C++, la declaraci on y de finici on de una sobrecarga de operador es muy similar a la declaraci on y de nici on de una funci on cualquiera.

int var = 8 + 7 (int + int)
int var = "Hola" (string)
int var = 6 + "Hola"(int + string)

Ventajas de los grafos dirigidos ací clicos
- Disminuye la evaluaci ón.
- Disminuye la gram atica de c ódigo.
- Permite disminuir el tamano de las expresiones.

Tabla de sí mbolos
Estructura donde se almacena la informaci on l exica, sint actica,sem antica y relacionada a la
generaci ón de c ódigo de elementos como variables, constantes, funciones, procedimientos, entre otras.

        Es simple de implementar.
        Búsqueda es lineal.
        Dentro de una lista cada nodo tiene al menos la siguiente información
          - Nombre
          - Tipo: ejemplo: int(entero).
          - Direcci on de memoria.          - Alcance.
          - Valores.
          - Par ametros.

Análisis Sintáctico (Video)

https://www.youtube.com/watch?v=7YZTWmtAKuc

Resumen 5

1. Conversi ón  no determinista a  determinista.

mueve (X, b): conjunto de estado del aut ómata finito no determini stico donde una transici ón con el sí mbolo de entrada  a algún estado en X del aut ómata finito determinista.


cerradura E (X): consiste en un conjunto de estados del autómata fi nito no determinista alcanzables desde algún estado en X con transiciones E solamente.En palabras más simples consiste en todos los conjuntos de nodos a los que se pueden llegar mediante E.

Ejemplos:

Cerradura de -E(1) = 2,3,5.
Cerradura de -E(3) = 5.
Cerradura de -E(2) = E .
Mueve (1 , a) = 4 .
Mueve (3 , d) = E.

Resumen 4

1. Análisis Léxico

Su principal función es leer código fuente, analizar los los componentes léxicos requeridos para el análisis sintáctico. En este análisis se ignoran comentarios, saltos de línea y espacios.

Un analizador léxico  es la primera fase de un compilador consistente en un programa que recibe como entrada el código fuente de otro programa y produce una salida compuesta de tokens  o símbolos.

2. Autómata 

Son también conocidos como diagramas de transición y se clasifican en dos tipos:

Autómatas determinísticos: no acepta vacío (E).

Autómatas no determinísticos: este tipo de autómata acepta más de una transición desde un estado a otros con un mismo elemento del alfabeto.

Ambos autómatas representan expresiones regulares, se pueden usar tablas de transición y además se pueden ejecutar algoritmos para minimizar los estados.

Formalmente un autómata tiene:

S es un conjunto de estados.

T un conjunto de estados de aceptación.

E un alfabeto.

F(x) una función de transición de estados y elementos del alfabeto.

So un estado inicial.

Ejemplo:

Automata(Video)

https://www.youtube.com/watch?v=DXBu9qCOO-o

Resumen 3

1. Elementos alrededor de un compilador
Otros elementos alrededor de un compilador:
Preprocesador. Se carga de uni car el programa fuente para poder realizar las
fases de un compilador
|-Carga Bibliotecas
|-Carga Subclases,SuperClase,entre otros..
Carga y enlace(del Sistema Operativo)
|-Resuelve direcciones de memoria
|-Da acceso a la parte de asignaci on de memoria y recursos f sicos.
Generador de c odigo intermedio:
temp1 = real(60)
temp2=id3*temp1
temp3=id2+temp2
id1=temp3
Optimizaci on de C odigo:
temp1=id3*60.0
id1= id2+temp1
Generador de C odigo:
movf id3,r2
1
mulf 60.0,t2
movf id2,r1
addf r2,r1
movf r1,id1
Consideraciones de dise~no de un compilador:
Lenguaje Fuente
|Tama~no del Lenguaje
|Cambio del lenguaje mientras se construye el compilador
|. Modularizar componentes ayuda afrontar el cambio
Lenguaje Objeto
|Si es nuevo debe asegurarse que es correcto
|Producci on para varias generaciones de m aquina objeto
Rendimiento
|Debe ser r apido
|Calidad de c odigo
|Localizaci on de errores
|Mantenimiento
|Transportabilidad
|. Redestinaci on: Pueda cambiar el c odigo objeto que genera.
|. Relocalizaci on: puede ejecutarse r apidamente en m aquinas distintas
inicializado?
Taxonom a de Lenguajes (por Abstracci on)
Primera Generaci on: Binario.
Segunda Generaci on: Lenguajes Simb olicos.
Tercera Gernaraci on: ALTO Nivel. Tienen Estructuras independientes de la
m aquina (C,Pascal,Java).
*Cuarta Generacai on: Construcci on de aplicaciones con piezas prefabricadas.
*Quinta Generaci on: De uso espec co. El programador conoce el problema y
el lenguaje puedo
ayudar a resolverlo a partir de las reglas.
Taxonom a de Lenguajes(por su Gram atica)
-Una gram atica describe de forma natural la estructura jer arquica de la
construcci on de lenguajes de programaci on
-Son reglas y principios que predicen correctamente las combinaciones de
oraciones de un lenguaje.
|-Ejemplo de Espa~nol
Para comprender mejor la idea, podemos considerar un modelo para el espa~nol:
1. ORACI ON {>SUJETO PREDICADO
2. SUJETO {>DETERMINANTE NOMBRE
3. PREDICADO {>VERBO COMPLEMENTO
4.DETERMINANTE {>EL
5. NOMBRE {>NI~NO|HOMBRE|ANCIANO
6.VERBO {>duerme|r e|come
7. COMPLEMENTO {>pl acidamente|intranquilo
2
Gram atica Regulares
Operaciones
+= aparecer una o m as veces
?= Aparece m aximo una vez
=Aparece 0 o m as veces (Cerradura de Kleene)
/[] o /() = Agrupaci on
|= OR
-= rangos. Ejemplo A-Z o 0-9
E = Vac o
|-Otras variantes
|- $ = Fin
|- .Potencias|||->a^(4) = aaaa
Gram aticas libres de contexto
1-Conjunto de componentes l exicos denominados S mbolos Terminales
2-Conjunto de componentes l exicos denominados No terminales
3-Producciones conformadas de no terminales y terminales
4-De nici on de un Noterminal como s mbolo inicial
S mbolos terminales->Se denotan con min uscula
|-Se pueden visualizar como las hojas de un arbol sint actico
|-En las gram aticas libres de contexto solo se encuentran en la parte derecha
de la producci on
Producciones->Se denotan con may uscula
3
Tienen dos partes, el Nombre(No terminal) y la parte derecha que indica la
sustituci on y puede tener terminales y no terminales
||Ejemplo
Lista{Lista + D gito
Lista{Lista - D gito
Lista{D gito
D gito{ 0|1|2|3|4|5|6|7|8|9
Propiedades de las Gram aticas
|-Cuando se dise~na una gram atica se busca que no sea ambigua.
|||Se dice que una gram atica es ambigua cuando se pueden construir 2
arboles sint acticos para una misma entrada
4

Resumen 2

Fases de los Compiladores

Fases de un Compilador:
           Análisis Léxico
           Análisis Sintáctico
           Análisis Semántico
           Generación de Código Intermedio
           Optimización de Código
           Generación de Código Final

Generación de Código Intermedio:
-Se genera la primera versión del lenguaje objeto al cual se desea transforma el
lenguaje fuente.
-Normalmente esta primera versión puede ser mejorada
-Normalmente cuando se transforma un ensamblador es en este punto donde se
utilizan algoritmos como:
|Código de tres dimensiones.
|Creación/Sustitución de variables por temporales más simples .
|Construcción de Grafos Dirigidos cíclicos para optimizar la primera versión.

Optimización de Código Intermedio:
-Reducir operaciones.
-Reducir código.
-Eliminar código que no se ocupa.
-Cambiar el orden del código para mejorar el rendimiento.
-Disminuir el uso de variables.
-Utilización de la memoria.
-Reutilización de segmentos de código.
-Detector de errores de ejecución.

Generación de Código Final:
-Genera la Salida
|Cuando es un compilador{>Archivo ejecutable.
|Cuando es un interprete{>Instrucción ejecutable.
-Características de la salida.
|Formato del archivo.
|Encoding: Utf-8, Utf-16.

Tabla de Símbolos: Variables y Constantes:
Nombre.
Tipo.
Alcance.
Valor.
Nombre Temporal Asociado
Utilización: Se usa?
Esta inicializado?

Manejo de Errores:
La construcción de un manejador de errores permite al desarrollador obtener:
m ás información, localización, opciones de correpción, avanzar en el proceso de
búsqueda de más errores, correpción automática de errores.

Pasadas:
| Solo una pasada:
Lee el programa fuente solo una vez.
Tiende a ser más optimo
.
| Múltiples pasadas:
Requiere de varias lecturas para realizar la compilación / interpretación.
Normalmente usado por interpretes y menos usado por compiladores por su
costo.
Diferencias de un Compilador y un Interprete:
|
|
Compilador:
-Tiene una salida un único lenguaje objeto.
-El rendimiento en la ejecución del programa compilado(la salida) es más
rápido que el interpretado.
-La salida puede depender de la arquitectura.
-Los errores sintácticos y semánticos se detectan antes de la ejecución del
programa objeto.
-No requiere del programa fuente porque el programa objeto es ejecutable (se
puede mantener en secreto el programa fuente).
-Menor flexibilidad en el uso de la memoria para el programa objeto.
|
Interprete:
-Tiene como salida instrucciones traducidas.
-El rendimiento del interprete se somete al rendimiento de realizar la
traducción.
Tiende a ser más portable e independiente de la arquitectura.
Se detectan los errores durante la ejecución del programa.
-Se requiere del programa fuente para la ejecución.
-Es más flexible para que el programa pueda usar la memoria.
Taxonomía de los compiladores:
|
|Cruzadas
|Optimizadores
|Una sola pasada
|Varias pasadas
|JIT(Just in time): Híbrido Compilar/Interpretar
|Ensambladores|- Utilización de nmónicos.

Análisis Léxico(Video)

https://www.youtube.com/watch?v=nWsC3bfqkhI

Resumen 1

1. Introducción a compiladores

Compilador: se define como un programa que se encarga de traducir un lenguaje fuente o lenguaje objeto.
Lenguaje Fuente: es aquel lenguaje que es comprensible para un intérprete humano y es empleado para escribir programas de computadora.
Lenguaje objeto: consiste en el lenguaje de salida del compilador.
Un compilador se caracteriza por tres lenguajes: un lenguaje fuente F, el lenguaje en el cual está escrito el compilador I y el lenguaje objeto O. Los tres se representan utilizando un diagrama llamado diagrama T como el que se muestra a continuación.

Ejemplo:

Figura 1.

Ejemplo más complicado:

Figura 2.

La función principal que cumple es traducir a un lenguaje mucho mas sencillo y entendible por la maquina, informa al usuario si existen errores en el código fuente con el fin de ejecutar la aplicación sin problema, si existe algún error simplemente se detiene.