Universidad Pública de Navarra



Año Académico: 2014/2015 | Otros años:  2013/2014 
Graduado o Graduada en Ingeniería Informática por la Universidad Pública de Navarra
Código: 240702 Asignatura: PROCESADORES DEL LENGUAJE
Créditos: 6 Tipo: Obligatoria Curso: 4 Periodo: 1º S
Departamento: Ingeniería Matemática e Informática
Profesorado:
FARIÑA FIGUEREDO, FEDERICO   [Tutorías ]

Partes de este texto:

 

Descripción/Contenidos

En esta asignatura se describe el proceso de compilación. Se muestran las etapas del proceso de compilación, las funciones y los problemas asociados a cada una de ellas. Las técnicas empleadas para la construcción de compiladores se usan actualmente en un ámpio abanico de aplicaciones, como el tratamiento y transformación de ficheros de texto (html, xml), el manejo sintáctico y semántico de páginas web (motores de búsqueda), el procesamiento de lenguaje natural (traductores automáticos), el reconocimiento de formas (visión artificial), etc.
 
En las clases de teoría se presentan técnicas para la construcción de analizadores lexicográficos, sintácticos y semánticos. Dichas técnicas se basan en las teorías de autómatas finitos, expresiones regulares, autómatas a pila y gramáticas independientes del contexto. También se trabaja con técnicas de síntesis basadas en traducción dirigida por la sintáxis. En las clases prácticas se presentarán utilidades que pueden emplearse para tratar cadenas de texto, como tr, grep, awk, etc. También se trabaja con las utilidades flex y bison para la construcción de reconocedores de lenguajes.
 
Los resultados de aprendizaje que se van a alcanzar con esta asignatura son:
(1) Entender el funcionamiento de un compilador
(2) Construir analizadores léxicos
(3) Construir analizadores sintácticos
(4) Analizar la semántica de un lenguaje

Subir

Descriptores

Compiladores: funciones y fases; preprocesadores; generación de código. Análisis Léxico: automatas de estados finitos; construcción de analizadores léxicos. Análisis Sintáctico: gramaticas independientes del contexto, análisis sintáctico top-down y bottom-up; análisis semántico: traducciones y rutinas semánticas; la tabla de símbolos.

Subir

Competencias genéricas

Las competencias genéricas que un estudiante debe adquirir en esta asignatura son:

G1- Capacidad para concebir, redactar, organizar, planificar, desarrollar y firmar proyectos en el ámbito de la ingeniería en informática que tengan por objeto la concepción, el desarrollo o la explotación de sistemas, servicios y aplicaciones informáticas.

G2- Capacidad para dirigir las actividades objeto de los proyectos en el ámbito de la informática

G4- Capacidad para definir, evaluar y seleccionar plataformas hardware y software para el desarrollo y la ejecución de sistemas. servicios y aplicaciones informáticas.

G6- Capacidad para concebir y desarrollar sistemas o arquitecturas informáticas centralizadas o distribuidas integrando hardware, software y redes.

G9- Capacidad para resolver problemas con iniciativa, toma de decisiones, autonomía y creatividad. Capacidad para saber comunicar y transmitir los conocimientos, habilidades y destrezas de la profesión de Ingeniero Técnico en Informática.

G10- Conocimientos para la realización de mediciones, cálculos, valoraciones, tasaciones, peritaciones, estudios, informes, planificación de tareas y otros trabajos análogos de informática

T1- Capacidad de análisis y síntesis.

T3- Comunicación oral y escrita.

T4- Resolución de problemas.

T5- Toma de decisiones.

T6- Trabajo en equipo.

T8- Aprendizaje autónomo.

T9- Creatividad.

 

Subir

Competencias específicas

Las competencias específicas que un estudiante debe adquirir en esta asignatura son:
C1- Capacidad para tener un conocimineto profundo de los principios fundamentales y modelos de la computación y saberlos aplicar para interpretar, seleccionar, valorar, modelar y crear nuevos conceptos, teorías, usos y desarrollos tecnológicos re lacionados con la informática.
C2- Capacidad para conocer los fundamentos teóricos de los lenguajes de programación y las técnicas de procedsamiento léxico, sintáctico y semántico asociadas, y saber aplicarlas para la creación, diseño y procesamiento de lenguajes.

Subir

Metodología

 
Metodología - Actividad
Horas Presenciales
Horas no presenciales
A-1 Clases magistrales
 30
  
A-2 Sesiones prácticas en grupos reducidos    
 15
 
A-3 Aprendizaje basado en problemas y/o casos en grupos reducidos 
 7,5
  
A-4 Preparación de presentaciones de trabajos, proyectos, etc. 
 
  7,5
A-5 Programación/experimentación u otros trabajos en ordenador/laboratorio 
 
 22,5
A-6 Estudio autónomo    
 
 30
A-7 Actividades de evaluación    
 4,5
 
A-8 Tutorías en grupos muy reducidos    
 3
 
A-9 Elaboración de trabajos y/o proyectos y escritura de memorias 
 
 15
A-10 Resolución de problemas, ejercicios y otras actividades de aplicación   
 15
Total
 60
 90

Subir

Evaluación

La evaluación de la parte teórica de la asignatura se realizará mediante dos exámenes de dos horas de duración distribuidos durante el semestre. La evaluación de las prácticas se realizará de forma contínua a lo largo del semestre mediante entregas previamente programadas. 

Cada parte, contenidos teóricos (N1) y prácticos (N2) tendrá una nota entre 0 y 10 puntos. La nota final (N) se obtiene según el procedimiento:

N = min(N1, N2) si N1 < 4,5 o N2 < 4,5

N = (N1+N2)/2 si N1 >=4,5 y N2 >= 4,5

Superarán la asignatura los estudiantes cuya nota final N sea mayor o igual que 5,0.

La nota N2 se calcula en base a dos parámetros (N2a y N2b en el cuadro inferior). La parte N2a es recuperable mediante trabajos adicionales. La parte N2b no es recuperable. 

 

Aspecto
 
Criterios
 
Instrumento de evaluación
 
Peso (%)
 

Evaluación de competencias:

 

 

 

Contenidos teóricos
 Comprensión de los conocimientos teóricos y su aplicación a la resolución de problemas de forma correcta.
 
Capacidad de análisis y síntesis.
 
Respuesta en tiempo y forma y adecuación de contenidos.
 
Aplicación de conocimientos a supuestos prácticos.
 
Capacidad de comunicación.
 Exámenes a lo largo del semestre
 
 
 
 
 Entrega de ejercicios propuestos
40%
 
 
 
 
10%

 

Evaluación de competencias (N2a):

 

 

 

Contenidos prácticos recuperables

 

Aplicación de los conocimientos teóricos al desarrollo de aplicaciones correctas con criterios de calidad exigibles a este nivel

 

Utilización adecuada de herramientas

 

Creatividad y capacidad de análisis y síntesis

 
 
Capacidad de comunicación.
 Participación activa en las clases de prácticas, pruebas durante las prácticas y entrega de prácticas
 
 
25%

 

Evaluación de competencias (N2b):

 

Contenidos prácticos NO recuperables
 
 
Respuesta en tiempo y forma y adecuación de contenidos.
 
Asistencia
 

 

Entrega de prácticas según el calendario y formatos establecidos

 

Control de firmas de asistencia
25%
   
 
  

Subir

Temario

 

Programa de teoría: Las clases de teoría se organizan en 15 sesiones de 2 horas de duración con los siguientes contenidos

 

Tema 1. Introduccion a la compilación: 1.1 ¿Que es un compilador? 1.2 En el principio. 1.3. Estructura de un compilador. !.4. Construcción de compiladores.

Tema 2. Autómatas y Lenguajes: 2.1 Conceptos fundamentales. 2.2 Descripción informal de autómatas finitos. 2.3 Autómatas finitos deterministas. 2.4 Automatas finitos no deterministas. 2.5 Equivalencia entre AFNs y AFDs. 2.6 Equivalencia y minimización de autómatas.

Tema 3. Especificación de lenguajes regulares: 3.1 Expresiones regulares. 3.2 Obtención de un AFD que reconoce una expresión regular 3.3 Gramáticas regulares. 3.4 Jerarquia de Chömsky.

Tema 4. Análisis lexicográfico: 4.1 Funciones del analizador léxico. 4.2 Componentes léxicos 4.3 Especificación de componentes léxicos. 4.4 Reconocimiento de componentes léxicos.

Tema 5. Especificación sintáctica de un lenguaje independiente del contexto: 5.1 Gramáticas independientes del contexto. 5.2 Derivaciones. 5.3 Árboles de derivación. 5.4 Ambigüedad.

Tema 6. Analisis sintáctico: 6.1 Parsers. 6.2 Parsers Top-Down y Bottom-Up 6.3 Análisis recursivo descendente y el parser LL. 6.4 Gestión de errores en el parser LL. 6.5 La familia de parsers LR(k). 6.6 La familia de parsers LALR(k). 6.7 Errores en los parsers LALR(k)

Tema 7. Traducción dirigida por la sintaxis: 7.1 Rutinas semánticas. 7.2 Traducciones7.3 Representación intermedia del código. 7.4 Algunos ejemplos de gfeneración de código intermedio

Tema 8. La tabla de símbolos: 8.1 Contenido de la tabla de símbolos. 8.2 Posibles estructuras de datos8.3 Representación del ámbito de validez

Tema 9. Otras cuestiones a considerar: 9.1 Ambientes de ejecución. 9.2 Optimización de código

 

Programa de prácticas: Las prácticas se organizan en sesiones de 2 horas de duración. Durante estas sesiones el alumno irá construyendo partes de un compilador. El alumno irá tomando decisiones que afectarán a las características de su compilador. Al final de cada práctica el alumno entregará un pequeño informe que permitirá al docente ir evaluando su progresión:

 

1. La utilidad flex

2. Uso de flex para construir un scanner

3. La utilidad bison

4. Construcción de un analizador sintáctico con bison

5. Creación de una tabla de símbolos

6. Análisis semántico y rutinas semánticas

 

 

Subir

Bibliografía

Acceda a la bibliografía que el profesorado de la asignatura ha solicitado a la Biblioteca.


Bibliografía básica

 

- A. V. Aho, M. S. Lam, R. Sethi, J. D. Ullman: Compiladores: Principios, técnicas y Herramientas; Addison-Wesley Iberoaméricana, 2008.

 

Bibliografía complementaria

 

- D. Grune, H. E. Bal, C. J. H. Jacobs, K. G. Langendoen; Diseño de Compiladores Modernos; McGraw-Hill, 2007.

- K. C. Louden; Construcción de compiladores: principios y prácyica; Thomson, 2004.

- A. W. Appel, J. Palsberg; Modern Compiler Implemrntation in Java; Cambridge University Press, 2002.

- A. Garrido, J. M. Iñesta, F. Moreno, J. A. Pérez; Diseño de compiladores; Servicio de publicaciones de la Universidad de Alicante, 2002.

- A. V. Aho, R. Sethi, J. D. Ullman; Compiladores: Principios, técnicas y Herramientas; Addison-Wesley Iberoaméricana, 1990.

- A. V. Aho, J. D. Ullman; Principles of compiler design; Addison-Wesley, 1977

 

Bibliografía para la parte práctica

 

- GNU; Bison 1,35; GNU, 2002

- V. Paxson; Flex version 2.5: A fast scanner generator; GNU, 1995.

- J. P. Bennett; Introduction to compiling techiniques: A first course using ANSI C, LEX & YACC; McGraw-Hill, 1990.

- J. R. Levine; T. Manson; D. Brown; Lex & Yacc; O'Reilly & Associates Inc. 1992.

 

Otros recursos

 

- M. E. Lesk, E. Schmidt; Lex - A lexical analyzer generator; (Documento original de los autores de Lex), http://www.cs.uaf.edu/%7Ecs631/lex-docs.txt

- S. C. Johnson; Yacc: Yet another compiler-compiler; AT&T Bell Laboratories, (Documento original de los autores de Yacc), http://www.cs.uaf.edu/%7Ecs631/yacc-docs.txt

 

Material Docente

 

El alumno puede encontrar en el aulario virtual los siguientes materiales: 

- Transparencias que se usan en clase.

- Apuntes de la teoría

- Enunciados de ejercicios

- Guiones de prácticas

 

Subir

Idiomas

Español

Subir

Lugar de impartición

Se publicara en el aulario virtual cuando se conozcan

Subir