Enginyeria en Informàtica (3371)

Processadors de Llenguatge I (12463) 

Descripció

Iniciació als estudiants en les tècniques d’anàlisi i traducció de llenguatges formals. Aquestes tècniques normalment han estat desenvolupades per a la realització de compiladors. Malgrat tot són aplicables en tot procés d'interpretació/traducció de qualsevol llenguatge amb una gramàtica ben definida. Així s'incidirà poc en el curs en aquells aspectes més específics dels llenguatges de programació, per centrar-nos en la traducció dels llenguatges formals en general, i deixar aspectes més concrets dels llenguatges de programació per a Processadors de Llenguatge II.

Objectius

Tenir soltura en el managament i comprensió de les gramàtiques així com les tècniques bàsiques de construcció d'intèrprets i compiladors per aquestes.  

Temari

1 Introducció

Que és un processador de llenguatge
Tipus de processadors de llenguatge

2 Llenguatges i gramàtiques

Tipus de gramàtiques
Gramàtiques equivalents.
Reconeixement de gramàtiques

3 Reconeixement d’expressions regulars

Generació de l’autòmat
Transformació d’un autòmat indeterminista a un de determinista
Simulació de l’autòmat: Taules d’estats.

4 Reconeixement de gramàtiques lliures de context

Construcció d’un reconeixedor recursiu descendent LL(1)
Reconeixement LR(0)
Conflictes i recomanacions amb LALR(1)

5 Taula de símbols i representació intermèdia

6 Tractament d’errors

Pràctiques

En les pràctiques es desenvoluparà un cercador de textos amb expressions regulars. Primer es desenvolupa un parser descendent recursiu, i després es fa el mateix usant "flex" i "bison"

Mètode d'avaluació

A través de las pràctiques i un examen. En l'examen hi haurà preguntes sobre la pràctica que es basarà en posar en pràctica els algorismes explicats a teoria i agafar soltura amb el tractament de les gramàtiques. La part pràctica val 4 punts dels quals 2 són el lliurament de les pràctiques i els altres dos surten de les preguntes sobre la pràctica fetes a l'examen La part de Teoria conta 6 punts dels quals 5 són de l'examen i 1 dels exercicis fets a classe de teoria i presentats. Es necessari tenir un 1.5 de pràctiques o un 2.5 de teoria per poder fer mitjana A setembre: Només hi ha examen, en el qual 4 punts són de preguntes sobre les pràctiques i 6 de teoria. Es pot anar a setembre només de les parts suspeses (teoria o pràctica)  

Bibliografia

Bibliografia bàsica

BENNETT, J.P. Introduction to Compiling Techniques - A First CourseUsing Ansi C, Lex and Yacc," McGraw Hill Book Co, 1990, ISBN 0-07-707215-4.

GRUNE,D., JACOBS, C.,Parsing Techniques, A practical guide Ed. Dick Grune, Ceriel Jacobs, 1995

GARRIDO, A. IÑESTA, J.M. MORENO, F. PEREZ, J.A. Diseño de compiladores. Publicaciones de la Universidad de Alicante. ISBN 84-7908-700-5

Bibliografia complementària

AHO, SETHI, and ULLMAN, Compiladores: Principios, Tecnicas, y herramientas

ANDREW W. APPEL Modern Compiler Implementation in (ML, Java, C) Ed. Cambridge University Press , 1998

CHARLES N. FISCHER & RICHARD J. LeBLANC, "Crafting A Compiler", Benjamin Cummings Publishing, Menlo Park, CA, 1988, ISBN 0-8053-3201-4.També en una versió posterior :"Crafting A Compiler in C"

DES WATSON, "High-Level Languages and Their Compilers," International Computer Science Series, Addison-Wesley Publishing Company, Wokingham England, 1989.