Tema 3: Compilación y Enlazado de Programas

Tema 3: Compilación y Enlazado de Programas

3.1 Lenguajes de Programación

• Un lenguaje de programación es un conjunto de símbolos y reglas para combinarlos que se utilizan para expresar algoritmos.
• Características importantes:
  • Son independientes de la arquitectura física del computador, lo que aumenta la portabilidad de los programas.
  • Una instrucción en un lenguaje de alto nivel se traduce en varias instrucciones en lenguaje máquina.
  • Un lenguaje de alto nivel utiliza notaciones fácilmente reconocibles por las personas en el ámbito en que se usan.

3.2 Construcción de Traductores

• Gramática:
  • Proporciona una especificación sintáctica precisa de un lenguaje de programación.
  • La complejidad de la verificación sintáctica depende del tipo de gramática que define el lenguaje.
  • Se define como G=(Vn, Vt, P, S), donde:
    • Vn es el conjunto de símbolos no terminales (auxiliares que se usan para operar con la gramática).
    • Vt es el conjunto de símbolos terminales (símbolos que se usan al programar).
    • P es el conjunto de producciones o reglas gramaticales (combinaciones válidas de los símbolos).
    • S es el símbolo inicial (un símbolo no terminal).
• Traductor:
  • Es un programa que recibe como entrada un texto en un lenguaje de programación concreto y produce, como salida, un texto en lenguaje máquina equivalente.
  • Hay dos tipos: compilador e interprete.
  • Entrada: Lenguaje fuente, que define a una máquina virtual.
  • Salida: Lenguaje objeto que define a una máquina real.

3.3 Proceso de Compilación: Fases de Traducción

• Fase de análisis:
  • Análisis léxico:
    • Lee los caracteres de la entrada del programa fuente, los agrupa en lexemas (palabras) y produce una secuencia o lista de tokens para cada lexema.
  • Análisis sintáctico:
    • Evalúa si la secuencia es correcta o no sintácticamente (existe un conjunto de reglas gramaticales aplicables para poder estructura la secuencia de tokens).
    • Nos devuelve el orden en el que hay que aplicar las producciones de la gramática para obtener la secuencia de entrada; es decir, el árbol sintáctico.
  • Análisis semántico:
    • La semántica de un lenguaje de programación se refiere al significado de las distintas construcciones sintácticas.
    • En los lenguajes de programación, el significado está ligado a la estructura sintáctica de las sentencias.
• Fase de síntesis:
  • Generación de código:
    • En esta fase se genera un archivo con un código en lenguaje objeto (generalmente lenguaje máquina) con el mismo significado que el texto fuente.
  • Optimización de código:
    • Mejora el código mediante comprobaciones locales a un grupo de instrucciones (bloque básico) o a nivel global.

3.4 Modelos de Memoria de un Proceso

• Niveles de la gestión de memoria:
  • Nivel de procesos: Reparto de memoria entre los procesos, responsabilidad del sistema operativo.
  • Nivel de regiones: Distribución del espacio asignado a las regiones de un proceso, gestionado por el sistema operativo aunque la división en regiones la hace el compilador.
  • Nivel de zonas: Reparto de una región entre las diferentes zonas (nivel estático, dinámico basado en pila y dinámico basado en heap) de esta, gestionado por el lenguaje de programación con soporte del sistema operativo.
• Necesidades de memoria en un proceso:
  • Tener un espacio lógico independiente.
  • Espacio protegido del resto de procesos.
  • Posibilidad de compartir memoria.
  • Soporte para diferentes regiones.
  • Facilidades de depuración.
  • Uso de un mapa amplio de memoria.
  • Uso de diferentes tipos de objetos de memoria.
  • Persistencia de datos.
  • Desarrollo modular.
  • Carga dinámica de módulos (por ejemplo, plug-in).
• Tipos de datos (desde el punto de vista de su implementación en memoria):
  • Datos estáticos:
    • Existen a lo largo de toda la vida del programa.
    • Según el ámbito de visibilidad: Globales a todo el programa, módulo o locales a una función.
    • Constantes o variables.
    • Con o sin valor inicial.
  • Datos dinámicos:
    • Asociados a la ejecución de una función:
      • Se almacenan en la pila y se crean al ser llamada la función, y se destruyen cuando esta termina.
    • Controlados por el programa:
      • Heap (zona de memoria usada en tiempo de ejecución para albergar los datos no conocidos en tiempo de compilación).
      • Existirán hasta que se liberen explícitamente (new y delete).
      • Su dirección de memoria se gestiona manualmente con el uso de punteros.

3.5 Ciclo de Vida de un Programa

• Fases:
  • 1. Preprocesado (archivos.i en C): Se procesan los includes, las directivas de preprocesador, etc.
  • 2. Compilación (archivos.s en C): Se genera el código en lenguaje ensamblador.
  • 3. Ensamblado (archivos.o en C): El código ensamblador se traduce por el assembler a código máquina.
  • 4. Enlazado (archivos.exe y a.out): El enlazador/linker se encarga de, a partir de los archivos objeto y las bibliotecas, resolver las referencias pendientes y generar el archivo ejecutable.
  • 5. Carga y ejecución: El cargador/loader (parte del SO) es el que ayuda a la asignación y carga del programa como un proceso en memoria principal en estado nuevo.

3.6 Bibliotecas

• Las bibliotecas son colecciones de código, normalmente relacionados entre sí.
• Favorecen modularidad y reusabilidad de código.
• Tipos:
  • Estáticas (se ligan con el programa en el enlazado, .a):
    • Conjunto de archivos objeto que se copian en un único archivo que forma la biblioteca.
  • Dinámicas (se ligan con el programa en ejecución, .so):
    • Se integran con los procesos que las usan en tiempo de ejecución, por ello se realiza previamente la reubicación de módulos.

3.7 Automatización del Proceso de Compilación y Enlazado

• Automatizar la construcción es la técnica utilizada durante el ciclo de vida de desarrollo de software donde la transformación del código fuente en el ejecutable se realiza mediante un guion (script).

• La automatización mejora la calidad del resultado final y permite el control de versiones.

• Formas:

  • Herramienta Make – archivos Makefile.
  • IDE (Integrated Development Environment – Entornos de Desarrollo Integrados), que embebe los guiones y el proceso de compilación y enlazado, p.e. CodeBlocks.### Archivos y Organización de los Mismos

• Un archivo es un conjunto de información sobre un mismo tema, tratada como una unidad de almacenamiento en memoria secundaria y organizada de forma estructurada para la búsqueda de un dato individual.

• Está compuesto de registros homogéneos que contienen información sobre el tema.

• Los archivos se clasifican según el tipo de registros: longitud fija, longitud variable, y longitud indefinida.

Organización de Archivos

• Organización secuencial:
  • Los registros se almacenan físicamente de forma contigua.
  • Adecuada cuando se quiere leer los registros en la misma secuencia en que están almacenados.
  • Ventajas: buen aprovechamiento del espacio, sencilla de utilizar, se puede utilizar con dispositivos secuenciales de bajo precio.
  • Operaciones: añadir registros (solo al final), consulta o recuperación (lector previamente), modificación (solo si no se aumenta la longitud), eliminación (no es posible eliminar un registro, pero se puede marcar como no válido).

Organización Secuencial Encadenada

• Junto a cada registro se almacena un puntero con la dirección física del registro siguiente.
• Permite insertar y borrar registros con facilidad, pero las consultas solo pueden realizarse de forma secuencial.
• Operaciones: añadir registros (localizar la posición, escribir el registro, asignar el puntero, modificar el registro anterior), consulta o recuperación (secuencial), borrado (asignar el puntero del registro anterior al siguiente).

Organización Secuencial Indexada

• Un archivo con organización secuencial indexada está formado por dos estructuras: zona de registros y zona de índices.
• La zona de registros es una zona donde se direccionan los registros del archivo, se divide en tramos lógicos.
• La zona de índices contiene información de los tramos de la zona de registros.
• Operaciones: consulta (se realiza por llave, sin necesidad de leer los registros que no se encuentran en su mismo tramo), inserción y borrado (no son posibles, solo se puede marcar como no válido).

Organización Directa o Aleatoria

• Es un archivo escrito sobre un soporte de acceso directo (direccionable).
• Se utiliza cuando los accesos deben realizarse por llave.
• La organización directa es útil para archivos donde los accesos deben realizarse por llave.
• Operaciones: consulta (se realiza por llave), borrado (siempre se realiza un borrado lógico), modificación e inserción (siempre se puede modificar o insertar un nuevo registro).

Problemas de los Sinónimos

• Problema fundamental: elegir la función de transformación adecuada.
• Problemas no deseados: direcciones que no se corresponden con ninguna llave, direcciones que se corresponden con más de una llave.
• Soluciones: zona de desbordamiento, dirección de la llave y el código binario del carácter.

Métodos de Direccionamiento

• Direccionamiento directo: se utiliza como dirección la propia llave.
• Direccionamiento asociado: se utiliza cualquier tipo de llave.
• Direccionamiento calculado (“hashing”): se obtiene la dirección de cada registro realizando una transformación sobre la llave.

Bases de Datos

• Concepto: un sistema formado por un conjunto de datos y un paquete software para gestión de dicho conjunto de datos.
• Requisitos: acceso múltiple, utilización múltiple, flexibilidad, seguridad, protección contra fallos, independencia física, independencia lógica, redundancia controlada, interfaz de alto nivel, interrogación directa.

Estructura de una Base de Datos

• Una base de datos se almacena información de una serie de objetos o elementos llamados entidades.
• De cada entidad se almacenan una serie de datos que se denominan atributos de la entidad.
• La información de cada entidad se almacena en registros, y cada atributo en campos de dicho registro.

Modelo entidad-relación

• Conceptos básicos: entidad, conjunto de entidades, relación, conjunto de relaciones, atributo.

• Tipos de correspondencia (cardinalidad): uno a uno, uno a muchos, muchos a uno, muchos a muchos.

• Diagrama entidad-relación: representación gráfica de los conjuntos de entidades y relaciones.

• Transformación del Modelo entidad-relación al modelo de datos relacional: se define una tabla para cada conjunto de entidades.### Cardinalidad en Conjuntos de Entidades

• En relaciones 1:N o N:1, se agregan columnas en la tabla del conjunto de entidades que participa de forma “muchos” para albergar los atributos que forman la clave del otro conjunto de entidades.

• En relaciones N:M, se define una tabla propia para el conjunto de relaciones y se definen las columnas necesarias para albergar los atributos que forman la clave de cada uno de los conjuntos de entidades que relaciona ese conjunto de relaciones.

Conjuntos de Relaciones con Atributos Propios

• En relaciones 1:1, 1:N o N:1, se puede seguir el mismo enfoque dado para conjuntos de relaciones sin atributos propios, pero añadiendo columnas necesarias para albergar los atributos del conjunto de relaciones en la misma tabla del conjunto de entidades.
• En relaciones N:M, 1:1, 1:N o N:1, se define una tabla propia para el conjunto de relaciones y se definen las columnas necesarias para albergar los atributos que forman la clave de cada uno de los conjuntos de entidades que relaciona ese conjunto de relaciones, y además se definen las columnas necesarias para albergar los atributos propios del conjunto de relaciones.

Sistema de Gestión de la Base de Datos (SGBD)

• Definición: un conjunto de software destinado a la creación, control y manipulación de la información de una base de datos.
• Funciones que debe permitir un SGBD:
  • Definición del esquema de la base de datos y de los distintos subesquemas.
  • Acceso a los datos desde algún lenguaje de alto nivel.
  • Interrogación (o recuperación de la información) directa en modo conversacional.
  • Organización física de la base de datos y recuperación tras fallos del sistema.

Lenguajes Específicos en un SGBD

• Lenguaje de descripción de datos (DDL): se usa para la descripción del esquema y de los subesquemas.
• Lenguaje de manipulación de datos (DML): se utiliza para el acceso a la base de datos desde lenguajes de alto nivel o en modo conversacional.
• El sistema de gestión de la base de datos actúa como intermediario entre los programas de aplicación y el sistema operativo, lo que permite que los programas sean independientes de la estructura física de los datos.