Guía docente 2023_24 Escuela Técnica Superior de Ingeniería

Contenidos

tema	Subtema
1. Introducción	1.1. Los lenguajes de programación como lenguajes formales. 1.2. Nociones básicas de lenguajes formales: definición, descripción, y reconocimiento de lenguajes formales. 1.3. Estructura básica de un compilador.
2. Lenguajes regulares	2.1. Expresiones regulares. 2.2. Autómatas finitos: deterministas, no deterministas y con lambda-movimientos. 2.3. Equivalencia entre expresiones regulares y autómatas finitos. 2.4. Generadores de analizadores léxicos: flex.
3. Lenguajes independientes del contexto	3.1. Gramáticas independientes del contexto. 3.2. Autómatas de pila. 3.3. Equivalencia entre gramáticas independientes del contexto y autómatas de pila. 3.4. Generadores de analizadores sintácticos: bison.
4. Otros lenguajes formales	4.1. Clasificación de los lenguajes formales: jerarquía de Chomsky. 4.2. Máquinas de Turing. 4.3. Lenguajes recursivos y lenguajes recursivamente innumerables.
5. Calculabilidad y complejidad	5.1. Tesis de Church-Turing. 5.2. Máquina de Turing universal. 5.3. Problemas indecidibles: problema de parada 5.4. Introducción a la teoría de la complejidad. 5.5. Los problemas P, NP y NP-completos.
6. Procesadores de lenguajes formales	6.1. Tabla de símbolos. 6.2. Análisis léxico. 6.3. Análisis sintáctico. 6.4. Análisis semántico. 6.5. Generación de código intermedio. 6.6. Generación de código objeto.