U1: Introducción a los Compiladores
Definición y Funciones
Un compilador es una herramienta de desarrollo de software destinada a traducir un programa escrito en lenguaje de alto nivel (programa fuente) en otro programa escrito en lenguaje máquina (programa objeto).
Funciones principales:
- Informa al usuario sobre la presencia de errores en el programa fuente, realizando una valoración semántica.
- Traduce todo el programa antes de ejecutarlo, generando un programa objeto que será ejecutado por el hardware.
Enlazador
Un enlazador es una herramienta del sistema que combina uno o más archivos objeto y bibliotecas para generar un único archivo ejecutable. Se encuentra ubicado entre el programa objeto y el programa ejecutable.
Etapas de un Compilador
- Etapa de Análisis: Fase de análisis léxico, fase de análisis sintáctico y fase de análisis semántico.
- Etapa de Síntesis: Fase de generación de código intermedio, fase de optimización de código y fase de generación de programa objeto.
Errores Sintácticos
Ocurren cuando la estructura del código no sigue las reglas del lenguaje. Ejemplos:
- Paréntesis o corchetes no balanceados.
- Ausencia de operadores u operandos.
- Delimitadores o separadores incorrectos.
Autómatas, Intérpretes y Máquinas Abstractas
Los autómatas poseen comportamientos preestablecidos, mientras que la autonomía implica la capacidad de alterar el comportamiento según el entorno. Un intérprete ejecuta instrucciones línea por línea sin generar un archivo objeto, siendo más lento que un compilador pero más flexible en la ejecución progresiva.
U2: Gramáticas Formales
Una Gramática Formal (GF) es un conjunto de reglas estructuradas que definen la sintaxis de un lenguaje. Se define como la cuádrupla G = (Σt, Σn, S, P).
Reglas de Reescritura
Una producción es un par ordenado (α, β), denotado como α := β, donde α es el lado izquierdo y β el derecho.
Conceptos Clave
- Lenguaje generado: Conjunto de todas las cadenas de símbolos terminales que pueden derivarse desde el axioma.
- Ambigüedad: Ocurre cuando una cadena puede ser generada por distintas derivaciones que producen diferentes árboles de análisis sintáctico.
- Recursión: Producción donde el no terminal del lado izquierdo aparece también en el lado derecho.
Formas Normales y Limpieza
- FNC (Forma Normal de Chomsky): Producciones con dos no terminales, un terminal o cadena vacía.
- FNG (Forma Normal de Greibach): Producciones que inician con un terminal seguido de no terminales.
- Gramática Limpia: Sin reglas innecesarias, símbolos inaccesibles ni símbolos superfluos.
U3: Autómatas Finitos (AFD)
Diferencia entre AFDt (filtro/clasificador) y AFDr (transformador/genera salida). El conjunto cociente Q/E agrupa estados equivalentes para la minimización del autómata.
Máquinas de Mealy y Moore
- Mealy: La salida depende del estado y de la entrada.
- Moore: La salida depende únicamente del estado actual (incorpora retardo).
U4: No Determinismo (AFND)
El no determinismo permite múltiples opciones en la función de transición ante una misma entrada. El Algoritmo de Thompson permite construir un AFND a partir de una expresión regular, garantizando un único estado inicial y uno final.