B3-T2: LENGUAJES DE PROGRAMACIÓN — CONCEPTOS, PARADIGMAS Y COMPILACIÓN
Tema teórico importante. Preguntan mucho sobre las fases del compilador, la jerarquía de Chomsky (tipos 0-3 de gramáticas), la diferencia entre compilación e interpretación, y los paradigmas de programación. También caen preguntas sobre gestión de memoria y recolección de basura (garbage collection).
CLASIFICACIÓN DE LENGUAJES
Por nivel de abstracción
| Nivel | Descripción | Ejemplos |
|---|
| Lenguaje máquina | Instrucciones binarias directamente ejecutables por la CPU. Específico de cada arquitectura (ISA) | Código binario (0s y 1s) |
| Ensamblador (bajo nivel) | Mnemónicos que representan instrucciones máquina. Correspondencia 1:1 con instrucciones de la CPU | x86 ASM, ARM ASM, MIPS ASM |
| Alto nivel | Abstrae el hardware. Sintaxis cercana al lenguaje humano. Una sentencia equivale a muchas instrucciones máquina | C, Java, Python, JavaScript |
| Muy alto nivel / DSL | Orientados a un dominio específico. Máxima abstracción | SQL, MATLAB, R, HTML/CSS |
Por modo de ejecución
| Tipo | Proceso | Ventaja | Desventaja | Ejemplos |
|---|
| Compilado | Código fuente → compilador → código máquina nativo | Máxima velocidad de ejecución | No portable (binario específico de plataforma), compilación lenta | C, C++, Rust, Go, Fortran |
| Interpretado | Código fuente → intérprete ejecuta línea a línea | Portable, desarrollo rápido, dinámico | Menor velocidad de ejecución | Python, Ruby, PHP, Perl, Bash |
| Bytecode + VM | Código fuente → compilador → bytecode → máquina virtual (JIT) | Portable ("write once, run anywhere") + buena velocidad | Overhead de la VM, mayor uso de memoria | Java (JVM), C# (CLR), Kotlin |
| Transpilado | Código fuente de un lenguaje → código fuente de otro lenguaje | Nuevas funcionalidades sobre lenguaje establecido | Debugging más complejo (source maps) | TypeScript→JS, Sass→CSS, CoffeeScript→JS |
Examen: Java NO es ni puramente compilado ni interpretado — se compila a bytecode (.class) que ejecuta la JVM. La JVM usa JIT (Just-In-Time) para compilar bytecode a código nativo en tiempo de ejecución. Python se compila a bytecode (.pyc) pero se ejecuta en su intérprete (CPython).
Por paradigma
| Paradigma | Concepto central | Características | Lenguajes |
|---|
| Imperativo / procedural | Secuencia de instrucciones que modifican el estado | Variables, asignación, bucles, funciones/procedimientos | C, Pascal, Fortran, COBOL |
| Orientado a objetos (OO) | Objetos que encapsulan datos y comportamiento | Clases, herencia, polimorfismo, encapsulación, abstracción | Java, C#, C++, Python, Ruby |
| Funcional | Funciones puras sin efectos secundarios | Inmutabilidad, funciones de orden superior, recursión, evaluación perezosa | Haskell, Erlang, Clojure, F#, Lisp, Scala |
| Lógico | Hechos y reglas; el motor infiere conclusiones | Unificación, backtracking, base de conocimiento | Prolog, Datalog, Mercury |
| Declarativo | Se describe QUÉ se quiere, no CÓMO | Sin flujo de control explícito | SQL, HTML, CSS, XSLT |
| Multiparadigma | Combina varios paradigmas | Flexibilidad | Python, JavaScript, Scala, Kotlin, C++ |
Por sistema de tipos
| Clasificación | Descripción | Ejemplos |
|---|
| Tipado estático | Los tipos se comprueban en compilación. Cada variable tiene un tipo fijo | Java, C, C++, C#, Go, Rust, TypeScript |
| Tipado dinámico | Los tipos se comprueban en ejecución. Las variables pueden cambiar de tipo | Python, JavaScript, Ruby, PHP, Perl |
| Tipado fuerte | No permite conversiones implícitas entre tipos incompatibles | Python, Java, Haskell, Rust |
| Tipado débil | Permite conversiones implícitas (coerción) entre tipos | JavaScript, C, PHP, Perl |
Examen: Python es dinámico y fuerte (no puedes sumar string + int sin convertir). JavaScript es dinámico y débil ("5" + 3 = "53", coerción implícita). Java es estático y fuerte. C es estático pero más débil (permite casts peligrosos).
COMPILACIÓN: FASES DEL COMPILADOR
Estructura general del compilador
Un compilador traduce código fuente a código objeto (típicamente código máquina o bytecode). Se divide en dos grandes fases:
| Fase | Subfases | Función |
|---|
| Front-end (análisis) | Análisis léxico (scanner) | Convierte el flujo de caracteres en tokens (lexemas) |
| Análisis sintáctico (parser) | Construye el árbol de sintaxis abstracta (AST) según la gramática |
| Análisis semántico | Comprueba tipos, declaraciones, ámbito de variables; tabla de símbolos |
| Middle (intermedio) | Generación de código intermedio | Genera representación intermedia (IR) independiente de la máquina (ej. código de tres direcciones) |
| Back-end (síntesis) | Optimización de código | Mejora el código intermedio (eliminación de código muerto, propagación de constantes, desenrollado de bucles) |
| Generación de código objeto | Produce código máquina para la arquitectura destino. Asignación de registros |
Detalle de cada fase
| Fase | Entrada | Salida | Herramienta/Concepto clave |
|---|
| Análisis léxico | Flujo de caracteres | Flujo de tokens | Autómatas finitos, expresiones regulares. Herramientas: lex, flex |
| Análisis sintáctico | Flujo de tokens | Árbol de sintaxis (AST / parse tree) | Gramáticas libres de contexto (tipo 2 Chomsky). Herramientas: yacc, bison |
| Análisis semántico | AST | AST anotado (con tipos, ámbitos) | Tabla de símbolos, comprobación de tipos, resolución de ámbitos |
| Generación IR | AST anotado | Código intermedio (3-address code, SSA) | Representación independiente de máquina |
| Optimización | Código intermedio | Código intermedio optimizado | Análisis de flujo de datos, grafos de control de flujo |
| Generación código | IR optimizado | Código máquina / bytecode | Selección de instrucciones, asignación de registros, scheduling |
Examen: El análisis léxico usa autómatas finitos (y expresiones regulares). El análisis sintáctico usa gramáticas libres de contexto. Los parsers pueden ser descendentes (top-down: LL, recursive descent) o ascendentes (bottom-up: LR, LALR, SLR). yacc/bison generan parsers LALR(1).
Tabla de símbolos
La tabla de símbolos es una estructura de datos (típicamente hash table) que mantiene información sobre cada identificador del programa: nombre, tipo, ámbito, dirección de memoria, etc. Se construye durante el análisis léxico/semántico y se consulta durante todo el proceso de compilación.
GRAMÁTICAS FORMALES — JERARQUÍA DE CHOMSKY
Noam Chomsky (1956) clasificó las gramáticas formales en 4 tipos según las restricciones de sus reglas de producción:
| Tipo | Nombre | Restricción de producciones | Autómata reconocedor | Uso en compiladores |
|---|
| Tipo 0 | Sin restricciones (recursivamente enumerable) | α → β (sin restricciones) | Máquina de Turing | Modelo teórico general |
| Tipo 1 | Sensibles al contexto | αAβ → αγβ (|lado izq| ≤ |lado der|) | Autómata linealmente acotado | Semántica contextual |
| Tipo 2 | Libres de contexto (CFG) | A → γ (un solo no-terminal a la izquierda) | Autómata de pila (PDA) | Análisis sintáctico |
| Tipo 3 | Regulares | A → aB o A → a (lineal por la derecha/izquierda) | Autómata finito (DFA/NFA) | Análisis léxico |
Examen: Pregunta clásica — qué tipo de gramática usa cada fase del compilador. Léxico → Tipo 3 (regular), reconocido por autómata finito. Sintáctico → Tipo 2 (libre de contexto), reconocido por autómata de pila. La jerarquía es inclusiva: Tipo 3 ⊂ Tipo 2 ⊂ Tipo 1 ⊂ Tipo 0.
BNF y EBNF
| Notación | Descripción | Ejemplo |
|---|
| BNF (Backus-Naur Form) | Notación formal para definir gramáticas libres de contexto | <expr> ::= <term> "+" <expr> | <term> |
| EBNF (Extended BNF) | BNF extendida con repetición (*), opcionalidad (?), agrupación () | expr = term { "+" term } |
GESTIÓN DE MEMORIA EN PROGRAMAS
Regiones de memoria
| Región | Contenido | Gestión | Ciclo de vida |
|---|
| Código (text) | Instrucciones del programa compilado | Fija, solo lectura | Todo el programa |
| Datos estáticos / global | Variables globales y estáticas | Fija, asignada al inicio | Todo el programa |
| Stack (pila) | Variables locales, parámetros, direcciones de retorno, frames de función | Automática (LIFO) | Duración de la llamada a función |
| Heap (montículo) | Objetos y datos asignados dinámicamente | Manual (malloc/free, new/delete) o GC | Hasta que se libere explícitamente o GC lo recoja |
Examen: El stack es rápido pero limitado (tamaño fijo, stack overflow si se excede). El heap es más lento pero flexible (tamaño dinámico). En Java/Python/C# todo objeto va al heap; en C/C++ el programador decide. El stack crece hacia abajo y el heap hacia arriba (en la mayoría de arquitecturas).
Garbage Collection (recolección de basura)
| Algoritmo | Descripción | Ventaja | Desventaja |
|---|
| Conteo de referencias | Cada objeto lleva un contador de referencias. Se libera cuando llega a 0 | Simple, liberación inmediata | No detecta ciclos (A→B→A) |
| Mark and Sweep | Fase 1: marca objetos alcanzables desde raíces (mark). Fase 2: libera los no marcados (sweep) | Detecta ciclos | Pausas (stop-the-world) |
| Mark and Compact | Mark + compacta la memoria (mueve objetos vivos juntos) | Elimina fragmentación | Más lento (mover objetos) |
| Generacional | Divide heap en generaciones (young/old). Los objetos nuevos se recogen con más frecuencia | Eficiente (mayoría de objetos mueren jóvenes — hipótesis generacional) | Complejidad |
| Copying GC | Divide memoria en dos mitades. Copia objetos vivos de una mitad a otra y limpia la fuente | Rápido, sin fragmentación | Solo usa 50% de la memoria |
Examen: Java (JVM) usa GC generacional: Young Generation (Eden + Survivor spaces) + Old Generation (Tenured). Minor GC recoge Young Gen (frecuente, rápido). Major/Full GC recoge Old Gen (infrecuente, más lento). G1GC es el colector por defecto desde Java 9.
TIPOS DE DATOS Y ESTRUCTURAS
Tipos de datos primitivos
| Tipo | Descripción | Tamaño típico (Java) |
|---|
| byte | Entero con signo | 8 bits (-128 a 127) |
| short | Entero con signo | 16 bits (-32.768 a 32.767) |
| int | Entero con signo | 32 bits (-2³¹ a 2³¹-1) |
| long | Entero con signo | 64 bits (-2⁶³ a 2⁶³-1) |
| float | Coma flotante (IEEE 754) | 32 bits (7 dígitos significativos) |
| double | Coma flotante doble precisión | 64 bits (15-17 dígitos significativos) |
| char | Carácter Unicode | 16 bits (UTF-16) en Java, 8 bits en C |
| boolean | Verdadero/falso | 1 bit lógico (implementación varía) |
Paso de parámetros
| Método | Descripción | Lenguajes |
|---|
| Por valor | Se copia el valor del argumento. El original no se modifica | C (primitivos), Java (primitivos) |
| Por referencia | Se pasa la dirección de memoria. La función puede modificar el original | C++ (con &), C# (ref/out), Fortran |
| Por valor de referencia | Se copia la referencia al objeto (no el objeto). El objeto puede modificarse, pero reasignar la referencia no afecta al original | Java (objetos), Python, JavaScript |
| Por nombre | Se sustituye la expresión textual (como una macro). Evaluación perezosa | Haskell (evaluación perezosa), Algol 60 |
Examen: Java siempre pasa por valor. Para primitivos, se copia el valor. Para objetos, se copia la referencia (por valor de referencia). Esto significa que puedes modificar el objeto pero no puedes reasignar la referencia original.
Ámbito (scope) y enlace (binding)
| Concepto | Descripción |
|---|
| Ámbito estático (léxico) | El ámbito se determina por la estructura del código fuente (en tiempo de compilación). Usado por C, Java, Python |
| Ámbito dinámico | El ámbito depende de la pila de llamadas en ejecución. Usado por Bash, Emacs Lisp (antiguo) |
| Binding estático | La asociación variable-tipo/valor se resuelve en compilación |
| Binding dinámico | La asociación se resuelve en tiempo de ejecución (polimorfismo, duck typing) |
PARADIGMA FUNCIONAL — CONCEPTOS CLAVE
| Concepto | Descripción |
|---|
| Función pura | Sin efectos secundarios. El resultado solo depende de los argumentos (misma entrada → misma salida) |
| Inmutabilidad | Los datos no se modifican. Se crean copias con los cambios aplicados |
| Función de orden superior | Función que recibe otra función como argumento o devuelve una función |
| Clausura (closure) | Función que captura variables del ámbito en que fue definida |
| Evaluación perezosa (lazy) | Las expresiones no se evalúan hasta que su valor es necesario |
| Pattern matching | Desestructuración y bifurcación basada en la forma de los datos |
| Map / Filter / Reduce | Operaciones fundamentales sobre colecciones sin bucles explícitos |
| Currying | Transformar una función de múltiples argumentos en una cadena de funciones de un argumento |
| Transparencia referencial | Una expresión puede reemplazarse por su valor sin cambiar el comportamiento del programa |
PARADIGMA LÓGICO — PROLOG
| Concepto | Descripción |
|---|
| Hechos | Afirmaciones sobre el mundo: padre(pedro, juan). |
| Reglas | Inferencias: abuelo(X,Z) :- padre(X,Y), padre(Y,Z). |
| Consultas | Preguntas al motor: ?- abuelo(pedro, Quien). |
| Unificación | Proceso de encontrar valores para las variables que hagan coincidir los términos |
| Backtracking | Si una rama falla, Prolog retrocede y prueba alternativas |
| Negación por fallo | \+ en Prolog: algo es falso si no se puede demostrar verdadero |
HERRAMIENTAS Y ENTORNOS
| Herramienta | Función |
|---|
| Compilador | Traduce código fuente a código máquina (gcc, javac, rustc) |
| Intérprete | Ejecuta código fuente directamente línea a línea (python, ruby, node) |
| Linker (enlazador) | Combina archivos objeto (.o) y librerías en un ejecutable final |
| Loader (cargador) | Carga el ejecutable en memoria para su ejecución |
| Preprocesador | Procesa directivas antes de compilar (#include, #define en C/C++) |
| Depurador (debugger) | Permite ejecutar paso a paso, inspeccionar variables, poner breakpoints (gdb, lldb) |
| Profiler | Analiza el rendimiento: qué funciones consumen más CPU/memoria |
| Linter | Analiza código estáticamente buscando errores, estilo y problemas potenciales |
FUENTES PÚBLICAS
Este resumen ha sido elaborado íntegramente a partir de fuentes de dominio público. No se ha utilizado material con copyright de terceros ni material de preparadores.
| Fuente | Tipo | Referencia |
|---|
| Chomsky, N. (1956) — Jerarquía de gramáticas | Publicación académica | Dominio público |
| Aho et al. — Conceptos de compiladores | Conocimiento académico | Dominio público |
| Documentación Java, Python, C | Documentación oficial | docs.oracle.com, docs.python.org |
| ISO/IEC 9899 — Lenguaje C | Estándar | ISO |