Universidad Pública de Navarra



Año Académico: 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 semántic top-down y bottom-up. Análisis Semántico: traducciones y rutinas semánticas. Tabla de Simbolos.

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.

 

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

 

Además de estos conocimientos y habilidades, la asignatura pretende la adquisición de las competencias transversales: 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 y 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



Se imparten clases hasta un total de 30 horas presenciales en el aula. En estas clases se imparte la teoría de la asignatura mediante proyector y pizarra. Se presentan ejemplos de aplicación de la teoría mediante problemas concretos. Se propondrán al estudiante colecciones de problemas que deben resolver de forma autónoma y que serán comentados en clase. Se imparten clase prácticas hasta un total de 30 horas presenciales en aula. En estas clases se presentan herramientas y se resuelven ejercicios propuestos con ellas; finalmente se desarrolla una aplicación utilizando dichas herramientas.

Metodología - Actividad
Horas Presenciales
Horas no presenciales
A-1 Clases expositivas/participativas
 30 (aula)
 15 (repaso)
A-2 Prácticas
 30 (laboratorio)
 5 (preparación)
A-4 Elaboración de trabajo
 
  30 (problemas y trabajos)
A-5 Lecturas de material
 
 10 (guiones)
A-6 Estudio individual
 
 24
A-7 Exámenes, pruebas de evaluación
 4
 
A-8 Tutorías individuales
 2
 
 
 
 
Total
 66
 84

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 apñlicació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
50%

 

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 Traducciones 7.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 datos 8.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 15 sesiones de 2 horas de duración con los siguientes contenidos:

 

1. Preparación de bash shell scripts (2 sesiones).

 

2. El lenguaje awk (3 sesiones)

 

3. La utilidad flex (3 sesiones)

 

4. La utilidad bison (4 sesiones)

 

Planificación del semestre

 

Semana
hora1
 hora2 hora3
hora4
 

1
 Presentación
  Presentación  Teoría Tema 1   Teoría Tema 1

2

 Teoría Tema 2

  Teoría Tema 2  Teoría Tema 2
  Teoría Tema 2
3
 Teoría Tema 3
  Teoría Tema 3  Teoría Tema 3
  Teoría Tema 3
4
  Teoría Tema 4
  Teoría Tema 4  Laboratorio Bash Shell  Laboratorio Bash Shell
5  Teoría Tema 5  Teoría Tema 5  Laboratorio Bash Shell 2
  Laboratorio Bash Shell 2
6  Teoría Tema 6
  Teoría Tema 6  Examen Teoría 1
  Examen Teoría 1
7  Teoría Tema 6  Teoría Tema 6  Laboratorio awk
 Laboratorio awk
8  Teoría Tema 6  Teoría Tema 6  Laboratorio awk 2
  Laboratorio awk 2
9  Teoría Tema 6  Teoría Tema 6  Laboratorio awk 3
  Laboratorio awk 3
10  Teoría Tema 7
  Teoría Tema 7
  Laboratorio flex  Laboratorio flex
11  Teoría Tema 7
  Teoría Tema 8
  Laboratorio flex 2
  Laboratorio flex 2
12  Teoría Tema 9
  Teoría Tema 9
  Laboratorio flex 3
  Laboratorio flex 3
13  Laboratorio bison  Laboratorio bison  Laboratorio bison  Laboratorio bison
14  Laboratorio bison  Laboratorio bison  Laboratorio bison  Laboratorio bison
15  Laboratorio bison  Laboratorio bison  Laboratorio bison  Laboratorio bison
16  Laboratorio bison  Laboratorio bison  Examen Teoria 2  Examen Teoría 2
total  12 h T y 4 h L  12 h T y 4 h L  3 h T, 11 h L y 2 h E  3 h T, 11 h L y 2 h E

 

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 sepa

Subir