• Author / Uploaded
• Irais Menchaca Gomez

Citation preview

Universidad Católica de Cuyo Facultad de Filosofía y Humanidades

Carrera: Sede: Trabajo:

Especialización en la Enseñanza de la Educación Superior Universidad Católica de Santiago del Estero Final del Módulo IV “La Práctica de la Enseñanza”

Enseñanza para la comprensión en Compiladores e Intérpretes

Alumno: Salvador Valerio Cavadini

– Junio de 2004 –

Enseñanza para la comprensión en Compiladores e Intérpretes

Introducción Este trabajo tiene como finalidad presentar una propuesta didáctica para la enseñanza de “Teoría de Lenguajes Formales”, tópico correspondiente a la Unidad II del programa de la asignatura Compiladores e Intérpretes1 en la cual ejercemos la docencia. Hemos elegido esta unidad pues el concepto de lenguaje formal y las nociones asociadas a él –i.e. símbolo, alfabeto, gramática, sintaxis, semántica, etc.– son medulares al contenido de la asignatura. Esta propuesta se realizó teniendo en cuenta las orientaciones conceptuales de la Enseñanza para la Comprensión. En las siguientes secciones de este trabajo expondremos brevemente los cuatro componentes claves de la enseñanza para la comprensión: metas para la comprensión, tópicos generativos, desempeños para la comprensión y evaluación continua. Seguidamente presentaremos una serie de desempeños para la comprensión de los contenidos de la unidad “Teoría de Lenguajes Formales”.

Metas para la compresión Las metas para la compresión son aquellos objetivos, que como docentes, deseamos sean alcanzados por nuestros alumnos. Estos objetivos son un conjunto de conceptos, procesos, habilidades, ideas, etc. que esperamos sean comprendidos por los estudiantes. Las metas de compresión correspondientes a cada unidad de la asignatura se denominan submetas y deben estar en sintonía con las metas propuestas para las metas planteadas para la asignatura completa. Estas últimas, denominadas hilos conductores, resumen la esencia de la materia. Es por esto que, antes de presentar las metas para la comprensión de la unidad tratada en este trabajo, detallaremos las metas de comprensión de la asignatura. Hilos conductores de la obligación académica “Compiladores e Intérpretes” establecidos en la planificación de la asignatura para el año 2004 son: 1. Comprender los conceptos fundamentales de la teoría de los lenguajes formales, la teoría de autómatas y las gramáticas generativas, relacionarlos y aplicarlos en la resolución de problemas. 2. Comprender los procesos de conversión de los lenguajes formales de alto nivel a código de máquina y el funcionamiento de los compiladores e intérpretes. 3. Identificar, dominar y aplicar las técnicas que guían los procesos de diseño y las herramientas básicas que se utilizan en la construcción de las partes constitutivas fundamentales de un traductor. 4. Desarrollar cooperativamente traductores utilizando herramientas de generación automática. Metas para la comprensión de la unidad “Teoría de Lenguajes Formales”: 1. Los alumnos comprenderán el concepto de “lenguaje” 2. Los alumnos establecerán similitudes y diferencias entre los lenguajes formales (artificiales) y los naturales. 3. Los alumnos comprenderán los inconvenientes que plantea la ambigüedad de los lenguajes naturales. 4. Los alumnos comprenderán que para procesar con una computadora las oraciones de un lenguaje es necesaria una representación finita y no ambigua de los mismos. 1

Materia anual perteneciente al cuarto año de las carreras de Analista de Sistemas y de Ingeniero en Computación que se imparten en la Facultad de Matemática Aplicada. El programa de la asignatura se encuentra detallado en el Apéndice A. El sitio web de la asignatura es www.ucse.edu.ar/fma/compiladores

2

Enseñanza para la comprensión en Compiladores e Intérpretes

5. Los alumnos comprenderán los conceptos básicos de la Teoría de Lenguajes Formales: símbolo, alfabeto, hilera y operaciones relacionadas. 6. Los alumnos comprenderán el concepto de gramáticas generativas y su utilidad para representar lenguajes tanto finitos como infinitos. 7. Los alumnos serán capaces de identificar a qué nivel de la Jerarquía de Chomsky pertenece una gramática/lenguaje.

Tópico generativo La enseñanza para la comprensión propone la utilización de tópicos generativos como herramienta para estimular y facilitar el acceso a los nuevos conocimientos por parte de los alumnos. Los tópicos generativos son conceptos, ideas, temas, etc., centrales del dominio de conocimiento de una disciplina y deben proveer conexiones y variedad de perspectivas en un grado suficiente como para apoyar el desarrollo de comprensiones profundas de los alumnos. Además, el tópico generativo debe resultar de interés para los alumnos y docentes, debe poder vincularse con facilidad con las experiencias y conocimientos previos de los alumnos y permitir ser abordado a través de una gran variedad de medios. El tópico generativo elegido para esta unidad es el concepto de lenguaje. Este concepto reúne las características necesarias para ser un tópico generativo ya que permite su abordaje desde las nociones básicas que tiene los alumnos sobre él y desde él se puede llegar a los demás conceptos vinculados que conforman la unidad “Teoría de Lenguajes Formales”. En la figura 1 puede observarse un mapa conceptual que vincula la noción de lenguaje con los contenidos de la unidad abordada y de otras unidades de la asignatura.

Desempeños para la compresión Una vez elegido el tópico generativo, el docente debe diseñar una serie de actividades que ayuden al alumno a explorar y establecer conexiones entre los nuevos conceptos que se le van presentado y sus saberes precedentes. Estas actividades se denominan desempeños para la comprensión. Cabe destacar que no cualquier actividad es un desempeño para la comprensión. La actividad debe plantearle un desafío cognitivo –accesible– al estudiante que lo estimule a utilizar sus saberes para poder culminar la actividad. Esta actividad además debe diseñarse en función de las metas para la comprensión plateadas para la unidad. Como dijimos, los desempeños de comprensión se diseñan en serie, es decir, debe ser una sucesión coordinada de actividades que le brinde al alumno una guía y ejercitación gradual y constante consistente en retos cognitivos cada vez más complejos. Los investigadores clasificaron los desempeños en tres categorías: • Desempeños preliminares: son actividades relativamente simples que se desarrollan al inicio de la unidad en la etapa de exploración y le permiten a los alumnos tomar contacto con el tópico generativo para comenzar a explorarlo. Además sirven al docente para identificar y dimensionar los conocimientos previos relacionados de los alumnos.

3

Enseñanza para la comprensión en Compiladores e Intérpretes

INTÉRPRETES

COMPILADORES compuestas de

CADENAS

son

TRADUCTORES

de

de

se b

asa e

reconocen

ALFABETO

es un

son utilizados como

n

de un

CONJUNTO

es un

TEORÍA DE LA COMPLEJIDAD

SÍMBOLOS

LENGUAJES

son diferentes a

LENGUAJES FORMALES

TEORÍA DE CONJUNTOS LENGUAJES NATURALES

AUTÓMATAS

se basa en

estudia

generan

TEORÍA DE LA COMPUTABILIDAD

estudia

GRAMÁTICAS estudia LINGÜÍSTICA

de FORMAS NORMALES

define

JERARQUÍA

se dedica a la

de

de

NOAM CHOMSKY

Figura 1: Mapa conceptual para el tópico generativo Lenguaje • Desempeños de investigación guiada: son actividades que se ejecutan al promediar la unidad, luego de haber concluido la etapa de exploración y tienen por objeto el desarrollo de la comprensión de problemas o aspectos concretos del tópico generativo. • Desempeños finales de síntesis: es un conjunto de actividades más complejas tendientes a posibilitar que los estudiantes sinteticen y demuestren la comprensión lograda a través de los desempeños anteriores. Deben ser actividades que requieran al alumno la síntesis e integración de los saberes que se han desarrollado en la unidad.

Evaluación para la comprensión El marco conceptual de la enseñanza para la comprensión hace evidente la necesidad de que la evaluación vaya más allá de un examen sumativo a fin de cada unidad o del curso. Los estudiantes precisan de oportunidades para reflexionar sobre sus desempeños durante el aprendizaje de nuevos conceptos o habilidades cognitivas y no sólo al final de este aprendizaje. Estas reflexiones deben realizarse teniendo en cuenta las metas para la comprensión planteadas y siguiendo los criterios e información brindada por el docente. Esta modalidad de evaluación se denomina evaluación continua y fue pensada como una herramienta que brinda oportunidades para mejorar la enseñanza a través del continuo análisis del progreso de los alumnos en pos de las metas de comprensión. Para que el alumno pueda autoevaluarse es necesario que conozca las metas para la comprensión que el docente espera que alcance y los criterios con los que evaluará su desempeño. Esto, más una realimentación y reflexión conjunta regular durante el proceso de aprendizaje permitirá que la evaluación se convierta en una herramienta que proporcione información que permita comprender el proceso de enseñanza y el de aprendizaje y replantear las prácticas docentes a fin de lograr más y mejores aprendizajes.

4

Enseñanza para la comprensión en Compiladores e Intérpretes

Propuesta didáctica para “Teoría de Lenguajes Formales” En esta sección presentaremos una propuesta didáctica confeccionada a partir de los lineamientos establecidos por la enseñanza para la comprensión. Como mencionamos, la propuesta comprende una serie de desempeños orientados a alcanzar las metas para la comprensión establecidas para la unidad “Teoría de Lenguajes Formales”. Antes de describir los desempeños para la comprensión diseñados, creemos que es importante detallar las condiciones áulicas en las cuales estas actividades se desarrollarán, para esto hemos resumido algunos datos relevantes de la asignatura Compiladores e Intérpretes en el siguiente cuadro. Cantidad de alumnos por cohorte Cantidad de docentes Cantidad de horas de clase

entre 15 y 25 3 7 por semana

A continuación detallamos una serie de 8 desempeños para la comprensión diseñados con el objeto de alcanzar las metas para la comprensión de la unidad II de la asignatura.

5

Enseñanza para la comprensión en Compiladores e Intérpretes

DESEMPEÑO N°1

DETALLE METAS PERSEGUIDAS

1

DESEMPEÑOS DE COMPRENSIÓN 1.a Los alumnos, de manera individual, redactan una definición de “lenguaje” 1.b Los alumnos acuerdan, en grupos de 2 ó 3, una definición de “lenguaje” 1.c Se exponen a la clase las definiciones de cada grupo y se identifican los elementos en común y se negocia una nueva definición. 1.d Los docentes proveen una definición de “lenguaje” obtenida en un diccionario de la lengua castellana. Los alumnos comparan la definición del diccionario con la redactada por el curso. EVALUACIÓN CONTINUA CRITERIOS : calidad de las RETROALIMENTACIÓN: informal definiciones aportadas por los entre los alumnos y los alumnos. Nivel de participación docentes. y compromiso en las actividades. RECURSOS DIDÁCTICOS • Definición de “lenguaje” obtenida en un diccionario de la lengua castellana. • Pizarra y fibrones. • Tiempo: 20 minutos.

6

Enseñanza para la comprensión en Compiladores e Intérpretes

DESEMPEÑO N°2

DETALLE METAS PERSEGUIDAS

1, 2

DESEMPEÑOS DE COMPRENSIÓN 2.a Los alumnos, organizados en grupos de 2 ó 3, confeccionan una lista de los lenguajes que conocen. Luego se socializan las listas y se confecciona una única lista en la pizarra. 2.b Los docentes proveen definiciones básicas de “lenguaje formal/artificial” y “lenguaje natural” 2.c Los alumnos clasifican en “formales” y “naturales” los elementos de la lista de la pizarra. 2.d Los alumnos identifican las características comunes de los lenguajes formales y las de los lenguajes naturales. EVALUACIÓN CONTINUA CRITERIOS : variedad de los RETROALIMENTACIÓN: informal ejemplos aportados. Corrección entre los alumnos y los de la clasificación. Calidad y docentes. cantidad de las características comunes identificadas. Nivel de participación y compromiso en las actividades. RECURSOS DIDÁCTICOS • Pizarra y fibrones. • Definiciones básicas de lenguaje formal y natural. • Tiempo: 30 minutos.

7

Enseñanza para la comprensión en Compiladores e Intérpretes

DESEMPEÑO N°3

DETALLE METAS PERSEGUIDAS

2,3

DESEMPEÑOS DE COMPRENSIÓN 3.a Se separa a los alumnos en dos grupos. A uno de los grupos se le provee una definición coloquial (en lenguaje natural) de un conjunto de números, al otro grupo se le provee una definición formal del “mismo” conjunto y se les pide que elaboren un lista de números que pertenecen al conjunto y otra de números que no pertenecen. 3.b Se copian las listas de cada grupo en la pizarra y se discute la “pertenencia” o “no pertenencia” de los números de las listas. Durante esta discusión los docentes destacan las posibles ambigüedades que puede platear la definición coloquial al tiempo que esta situación de ambigüedad no se produce con la definición formal. EVALUACIÓN CONTINUA CRITERIOS : Nivel de RETROALIMENTACIÓN: informal participación y compromiso en entre los alumnos y los las actividades. docentes. RECURSOS DIDÁCTICOS • Pizarra y fibrones. • Definiciones de conjuntos de números. • Tiempo: 15 minutos.

8

Enseñanza para la comprensión en Compiladores e Intérpretes

DESEMPEÑO N°4

DETALLE METAS PERSEGUIDAS

4, 5, 6

DESEMPEÑOS DE COMPRENSIÓN 4.a (pre-presencial) Los docentes proveen bibliografía y se solicita que los alumnos, en grupos de 2 ó 3, confeccionen una breve monografía en la que se expliquen los conceptos de símbolo, alfabeto e hilera y sus operaciones relacionadas, y que con esos conceptos elaboren una definición de “lenguaje”. 4.b (presencial) Los docentes repasan con los alumnos los conceptos de símbolo, alfabeto e hilera y socializan las definiciones de “lenguaje” de cada grupo. 4.c Se solicita que los alumnos comparen y relacionen los conceptos y operaciones de la Teoría de Lenguajes Formales con los conceptos de la Teoría de Conjuntos. 4.d De ser necesario, los docentes introducen la noción de lenguaje como “conjunto de hileras”. 4.e Se discuten con los alumnos los retos técnicos que plantea la representación de conjuntos en una computadora. 4.f Se les solicita que propongan métodos de representación para conjuntos infinitos (lenguajes infinitos). 4.g Los docentes introducen el concepto de gramática generativa y destacan su utilidad para representar lenguajes finitos e infinitos. EVALUACIÓN CONTINUA CRITERIOS : calidad de las monografías y las definiciones aportadas. Calidad de los métodos propuestos. Nivel de participación y compromiso en las actividades.

RETROALIMENTACIÓN: los docentes harán comentarios por escrito de cada una da las monografías elaboradas por los alumnos. Informal entre los alumnos y los docentes.

RECURSOS DIDÁCTICOS • Material bibliográfico sobre lenguajes formales (libros, papers, web links, etc) • Pizarra y fibrones. • Tiempo: 50 minutos.

9

Enseñanza para la comprensión en Compiladores e Intérpretes

DESEMPEÑO N°5

DETALLE METAS PERSEGUIDAS

6, 7

DESEMPEÑOS DE COMPRENSIÓN 5.a (pre-presencial) Se solicita que los alumnos, en grupos de 2 ó 3, investiguen sobre Noam Chomsky, la “Jerarquía de Gramáticas” propuestas por él y elaboren una breve monografía al respecto. 5.b (presencial) Los docentes repasan con los alumnos la jerarquía de gramáticas propuesta por Chomsky (Jerarquía de Chomsky). 5.c Los alumnos participan del juego El Intruso (ver Apéndice B) EVALUACIÓN CONTINUA CRITERIOS : calidad de las monografías. Desempeño en el juego. Nivel de participación y compromiso en las actividades.

RETROALIMENTACIÓN: los docentes harán comentarios por escrito de cada una da las monografías elaboradas por los alumnos. Informal entre los alumnos y los docentes.

RECURSOS DIDÁCTICOS • Tarjetas para el juego El Intruso. • Pizarra y fibrones. • Tiempo: 50 minutos.

10

Enseñanza para la comprensión en Compiladores e Intérpretes

DESEMPEÑO N°6

DETALLE METAS PERSEGUIDAS

6, 7

DESEMPEÑOS DE COMPRENSIÓN 6.a Los participan del juego Encontrando el Compañero (ver Apéndice B) 6.b Los alumnos conforman grupos de 3 ó 4 integrantes. La mitad de los grupos debe dar ejemplos de lenguajes que no pueden ser generados por gramáticas regulares (nivel 3 de la Jerarquía de Chomsky). La otra mitad debe elaborar y fundamentar ejemplos de lenguajes que sí pueden ser generados por dichas gramáticas. 6.c Los alumnos identifican –con la ayuda necesaria por parte de los docentes– los aspectos que hacen imposible la generación con una gramática regular de los lenguajes aportados por la primera mitad de grupos. 6.d Los alumnos infieren desde los ejemplos de la actividad 6.b y los aspectos identificados en la actividad 6.c las limitaciones de las gramáticas regulares. Se repiten las actividades 6.b, 6.c y 6.d para las gramáticas libres de contexto (nivel 2 de la Jerarquía de Chomsky). EVALUACIÓN CONTINUA CRITERIOS : Desempeño en el RETROALIMENTACIÓN: Informal juego. Capacidad de entre los alumnos y los identificación de las docentes. limitaciones de las gramáticas. Nivel de participación y compromiso en las actividades. RECURSOS DIDÁCTICOS • Tarjetas para el juego Encontrando el Compañero. • Pizarra y fibrones. • Tiempo: 50 minutos.

11

Enseñanza para la comprensión en Compiladores e Intérpretes

DESEMPEÑO N°7

DETALLE METAS PERSEGUIDAS

1,2,3,4,5,6,7

DESEMPEÑOS DE COMPRENSIÓN 7.a A cada alumno se le asigna un par de lenguajes para los cuales deberá: • Dar 5 ejemplos de hileras que pertenezcan al lenguaje y 5 de hileras que no pertenezcan. • Indicar y justificar el nivel de la Jerarquía de Chomsky a la que pertenece el lenguaje. • Diseñar la gramática de menor potencia que lo genere. EVALUACIÓN CONTINUA CRITERIOS : calidad y variedad de RETROALIMENTACIÓN: los alumnos los ejemplos aportados. Calidad coevalúan los ejemplos, las de las justificaciones. Calidad justificaciones y las gramáticas. de las gramáticas diseñadas RECURSOS DIDÁCTICOS • Lenguajes • Pizarra y fibrones. • Tiempo: 50 minutos.

12

Enseñanza para la comprensión en Compiladores e Intérpretes

DESEMPEÑO N°8

DETALLE METAS PERSEGUIDAS

1,2,3,4,5,6,7

DESEMPEÑOS DE COMPRENSIÓN 8.a (extraáulico) Cada alumno deberá elaborar una monografía en donde se comparen y analicen las diferencias entre la jerarquía propuesta originalmente por Noam Chomsky en 1958 y las jerarquías “de Chomsky” descriptas en la bibliografía recomendada por la cátedra. EVALUACIÓN CONTINUA CRITERIOS : calidad y RETROALIMENTACIÓN: los docentes profundidad del análisis harán comentarios por escrito descripto en la monografía. de cada una da las monografías elaboradas por los alumnos. Informal entre los alumnos y los docentes. RECURSOS DIDÁCTICOS • Material bibliográfico. • Tiempo: • 1 semana para la realización de la monografía. • 30 minutos para la discusión (retroalimentación) en el aula.

13

Enseñanza para la comprensión en Compiladores e Intérpretes

Bibliografía * Blythe, Tina y cols. 1999. “La enseñanza para la comprensión. Guía para el docente”. Editorial Paidós. Buenos Aires. ∗ Camilloni, Alicia W. de; Celman, Susana; Litwin, Edith; Palou de Maté, María del Carmen. 1998. “La evaluación de los aprendizajes en el debate didáctico contemporáneo”. Editorial Paidós. Buenos Aires. ∗ Camilloni, Alicia W. de; Davini, María Cristina; Edelstein, Gloria; Litwin, Edith; Souto, Marta y Barco, Susana. 1998. “Corrientes didácticas contemporáneas”. Cuestiones de Educación. Editorial Paidós. Buenos Aires. ∗ Doyle, Walter. 1997. “Trabajo Académico”. Mimeo. Buenos Aires. ∗ Nieto Gil, Jesús M. 1996. “La autoevaluación del profesor. Cómo evaluar y mejorar su práctica docente.” Editorial Praxis. Segunda Edición. Barcelona. ∗ Ontoria, A. y otros. 1995. “Mapas conceptuales. Una técnica para aprender”. Editorial Narcea, S. A. de Ediciones. Madrid. ∗ Perkins, David. 1998. “Enseñanza para la comprensión. Introducción a la teoría y su práctica”. Mimeo. Harvard University. ∗ Santos Guerra, Miguel Angel. 1998. “Evaluar es comprender”. Editorial Magisterio del Río de la Plata. Buenos Aires. ∗ Sitio web en Internet del grupo de Investigación Proyecto Zero. http://www.pz.harvard.edu ∗ Stone Wiske, Martha (compiladora). 1999. “La enseñanza para la comprensión. Vinculación entre la investigación y la práctica”. Editorial Paidós. Buenos Aires.

14

Enseñanza para la comprensión en Compiladores e Intérpretes

Apéndice A

15

Enseñanza para la comprensión en Compiladores e Intérpretes

Universidad Católica de Santiago del Estero Facultada de Matemática Aplicada Compiladores e Intérpretes Programa de la asignatura Año 2004 UNIDAD I: TRADUCTORES, COMPILADORES E INTÉRPRETES. Traductores. Historia de los Traductores. El compilador Fortran.Estructura de un traductor. Front-End o Análisis y Back-End o Síntesis. Definición sintética de las fases de un compilador: análisis lexicográfico, análisis sintáctico, análisis semántico, generación de código intermedio, optimización de código, generación de código final. Tabla de símbolos y manejo de errores. El agrupamiento de las fases. Pasadas. Arquitectura de los traductores: su evolución. Clasificación de Traductores. Compiladores e Intérpretes. Emuladores. Máquinas Virtuales. Diseño de compiladores, lenguajes y computadoras. Compiladores de Compiladores. Bootstrapping (Arranque). Cross-Compilers (Compiladores Cruzados). Compiladores Just-in-time. Compiladores on-the-fly. Decompiladores. UNIDAD II: TEORÍA DE LENGUAJES FORMALES. Lenguajes Naturales y Lenguajes Formales. Sintaxis y Semántica de los lenguajes. Teoría de Conjuntos. Teoría de lenguajes formales. Conceptos elementales: símbolo, alfabeto, hilera o cadena. Operaciones sobre hileras. Lenguajes: definición y operaciones sobre lenguajes. Metalenguajes. Gramáticas. Gramáticas formales. Notación. No terminales y Producciones. Derivaciones. Derivaciones canónicas: derivaciones leftmost (por izquierda) y rightmost (por derecha). Sentencias y formas sentenciales. Representación de las derivaciones. Grafos, árboles de derivación -parse tree- y árboles sintácticos -sintax tree-. Clasificación de gramáticas: la Jerarquía de Chomsky. Gramáticas Regulares y Lenguajes Regulares. Propiedades de los Lenguajes Regulares. Pumping Lema (Lema de bombeo). Gramáticas Libres de Contexto y Lenguajes Libres de Contexto. Propiedades de los Lenguajes Libres de Contexto. Gramáticas Sensibles al Contexto. Gramáticas no Restringidas. Higienización de Gramáticas Libres de Contexto. Gramáticas propias. Forma Normal de Noam Chomsky. Forma Normal de Sheila Greibach. Propiedades. Ambigüedad. Tipos. Eliminación de Ambigüedad. Precedencia y asociatividad. Representaciones formales de la sintaxis de los lenguajes libres de contexto. Forma de Backus-Naur. Diagramas sintácticos. Ventajas del uso de gramáticas. UNIDAD III: TEORÍA DE AUTÓMATAS. Autómatas. Definición. Componentes. Operación. Diagramas de transición. Su relación con las gramáticas. Autómatas finitos. Definición formal. Representación Matricial. Condición de determinismo. Autómatas finitos determinísticos, no determinísticos y de estados mínimos. Definiciones formales. Algoritmos de conversión: Construcción de subconjuntos. Diseño de Autómatas Finitos. Autómatas de pila. Definición formal. Determinismo en Autómatas de Pila. Autómatas limitados linealmente. Máquinas de Turing. Decidibilidad. Los autómatas y su relación con la Jerarquía de Chomsky. Los compiladores como autómatas. UNIDAD IV: ANÁLISIS LEXICOGRÁFICO. El rol del analizador lexicográfico. Tokens, patrones y lexemes. Atributos de los tokens. Expresiones Regulares, gramáticas regulares y autómatas finitos. Equivalencia entre los modelos. Derivadas de Expresiones Regulares. Algoritmo de McNaughton-Yamada-Thompson. Diseño de analizadores 16

Enseñanza para la comprensión en Compiladores e Intérpretes

lexicográficos. Diagramas de transición. Operaciones asociadas: bypass, getchar, concat e install. Lookahead y Pushback. Espacios en blanco: políticas y tratamiento. Criterios de diseño. Implementación de analizadores lexicográficos. Algoritmos greedy (glotón) y no greedy. Palabras reservadas. Comentarios. El subsistema de entrada. Buffers. Lookahead multicaracter. Fin de la entrada. El analizador léxico de Fortran. Recuperación de errores léxicos. Token de error. Herramientas para la generación de analizadores lexicográficos. Lex. Flex. TP Lex. UNIDAD V: ANÁLISIS SINTÁCTICO. Análisis sintáctico y gramáticas libres de contexto. Técnicas de parsing: generales, ascendentes y descendentes. Parsing determinístico y no determinístico. Parsing Top-Down. Gramáticas LL(k) y sus limitaciones. Modificación de gramáticas. Recursividad izquierda directa e indirecta. Factorización. Ciclos. Tablas del parser top-down: Conjuntos First, Follows y Selection. El problema If-Then-Else en el parsing LL(k). Parsers predictivos y recursivos descendentes. Parsers top-down y autómatas de pila. Propiedades del parsing LL(1). Análisis sintáctico Bottom-Up. Parsers shift-reduce. Técnicas de precedencia: Precedencia de Operadores y Precedencia Simple. Técnica LR(0). Tablas LR(0). Conflictos shift-reduce y reduce-reduce. Técnica SLR(k). Técnica LR(k). Técnica LALR(k). El problema If-Then-Else en el parsing LR(k). Propiedades del parsing LR(1). Parsing bottom-up versus parsing top-down. Análisis comparativo. Técnicas Generales. Método de Unger. Método CYK. Algoritmo de Jay Earley. Herramientas para la generación de analizadores sintácticos ascendentes. Generadores LALR(1). Yacc. TP Yacc. Generadores LALR(k). Control de ambigüedad en parsers determinísticos. Análisis de conflictos en parsing LR(k). Tratamiento de dependencias de contexto en parsers libres de contexto. Recuperación de errores sintácticos. Modo Pánico. Producciones de error. UNIDAD VI: ANÁLISIS SEMÁNTICO Y CÓDIGO INTERMEDIO. Traducción dirigida por la sintaxis. Definiciones dirigidas por la sintaxis. Atributos heredados y sintetizados. Cálculo y flujo de los valores de los atributos. Definiciones S-atribuídas y L-atribuídas. Acciones semánticas. Esquemas de traducción dirigidos por la sintaxis. Gramáticas Aumentadas. Limitaciones de las gramáticas libres de contexto. Tabla de símbolos. Función. Primitivas. Consideraciones de diseño. Técnicas de implementación: estática y dinámica. Listas encadenadas, árboles binarios, tablas hash. Función de hashing. La tabla de símbolos y los lenguajes de bloques. El espacio string. Representación de campos y registros. Representación de tipos predefinidos y abstractos. Errores semánticos. Recuperación de errores semánticos. Rutinas Semánticas en parsers LL y en parsers shift-reduce. Pila semántica controlada por el parser. Código intermedio. Máquinas abstractas. Representación de operaciones, flujo de datos y flujo de control. Formas de Representaciones intermedias: Árboles, grafos, notación postfijo y código de tres direcciones. Triplas y cuádruplas. Tuplas. Lenguajes de programación como Representaciones intermedias. Análisis comparativo de las diferentes representaciones. Portabilidad. Representación intermedia versus generación directa. Alternativas de organización de un compilador. Compiladores de una pasada. Compiladores multipasada. Familias de compiladores. Compiladores multilenguajes y multi-target. UNIDAD VII: TRADUCCIÓN Y GENERACIÓN DE CÓDIGO. Procesamiento de declaraciones. Atributos. Procesamiento de expresiones y asignaciones. Left-value y Right-value. Chequeo de tipos. Identificadores simples, constantes, registros, arrays, cadenas. Precedencia y asociatividad de operadores. Traducción de las estructuras de control. Su traducción en compiladores de una o más pasadas. El problema "Forward Branch" (salto hacia adelante). El problema "Backward Branch" (salto hacia atrás). Labels. Backpatching. Estructuras de loop: sentencias while, repeat-until, for, loop. Estructuras de ejecución condicional: sentencias if-then, if-then-else, case. Expresiones Boolenas y Operaciones Relacionales. Métodos de traducción. Evaluación "Short-circuit". Estructuras de transferencia directa de control: exit, goto. Traducción de Rutinas y Funciones. Stack y Heap. Ámbitos. Paso de parámetros. Stack Frames. Registros de Activación. Encadenamiento estático y dinámico. Displays. Valores de retorno. UNIDAD VIII: OPTIMIZACIÓN Y GENERACIÓN DE CÓDIGO FINAL. 17

Enseñanza para la comprensión en Compiladores e Intérpretes

Compiladores Optimizadores. Tipos de Optimización. Ámbitos de optimización: local, interprocedural, global. Optimización de código intermedio. Principales fuentes de optimización. Bloques Básicos. Bloques Básicos Extendidos. Grafo de Flujo de Control (CFG). Grafo de Dependencias de Control (PDG). Algoritmos para su construcción. Constant folding y Propagación de constantes. Variables muertas. Eliminación de código muerto. Eliminación de subexpresiones comunes. Grafos acíclicos dirigidos. Algoritmo número-valor. Optimizaciones del flujo de control. Análisis de flujo de datos. Ecuaciones. Generación de código final. Consideraciones sobre la máquina objeto: pipeline, caches, arquitectura superescalar, arquitecturas RISC. Scheduling de instrucciones. Algoritmo de Sethi-Ullman. Asignación de registros. Técnicas de coloreado de grafos. Gestión de variables temporales. Máquina de pila. Selección de instrucciones y modos de direccionamiento. Optimización del código objeto. Técnicas Peep-hole. Reducción de potencia. Simplificaciones algebraicas.

18

Enseñanza para la comprensión en Compiladores e Intérpretes

Apéndice B

19

Enseñanza para la comprensión en Compiladores e Intérpretes

EL INTRUSO El juego consiste en descubrir qué elemento está incorrectamente agrupado con otros. El docente determina desde el principio cuántas rondas se jugarán, en cada ronda se entrega a los participantes una ficha con un conjunto de elementos (gramáticas, def. de lenguajes) y se pide que indique qué elemento no pertenece al conjunto y justifique por qué. El docente define un tiempo límite para resolver cada problema, cumplido el plazo, cada participante entrega solución al docente quien explica en la pizarra cuál era la solución correcta. Aquellos que hayan contestado acertadamente obtienen un punto. Luego de la última ronda, se suman los puntos de cada participante y se designan los ganadores. Ejemplo 1

S S A A B

    

a A a a B a A b A

S S A A B C C

      

1 0 0 0 0 1 1 B

C A B A C

S A A B B C

     

A A A B C c

a b a b b

S S A A B B B

      

C

b a a a b b c D

B A B A A B

Solución: El intruso es la gramática C porque es lineal a izquierda a diferencia de las demás que son lineales a derecha. Ejemplo 2

E E T T T

    

E + T T T * F F id

E  E + E E  E * E E  id

A

E E E E

   

E + E E  E + E E * E E  E * E ( id ) E  ( E ) id

B

C

D

Solución: El intruso es la gramática D porque genera un lenguaje libre de contexto a diferencia de las demás que siendo gramáticas libres de contexto, generan lenguajes regulares. Ejemplo 3

P  ( P ) P  ( ) A

P  ( C C  P ) C  ) B

P  ( P ) P P  λ

P  ( C ) C  ( ) C C  ( )

C

D

Solución: El intruso es la gramática D porque genera un lenguaje regular a diferencia de las demás que generan lenguajes libres de contexto.

20

Enseñanza para la comprensión en Compiladores e Intérpretes

ENCONTRANDO EL COMPAÑERO El juego consiste en determinar pares de elementos relacionados. El docente define desde el principio cuántas rondas se jugarán, en cada una se entrega a los participantes una ficha con elementos relacionados de a pares. Aquel que encuentre los pares relacionados se hace acreedor a un punto (si la solución aportada es incorrecta, se le resta un punto). Luego de la última ronda, se suman los puntos de cada participante y se designan los ganadores. Ejemplo

L={ai bi con i>0}

•

•

S  a A b S  a A S b A  a

S  a S b S S  a b

•

•

S  a S b S  a b

•

S S A B

   

A S b B A b B a a b

•

•

S S S B

   

a a S b

•

•

S  a A B S  a B B  b b

L={ai bi con i>0}

•

•

S  a A b S  a A S b A  a

S  a S b S S  a b

•

•

S  a S b S  a b

•

S S A B

   

A S b B A b B a a b

•

•

S S S B

   

a a S b

•

•

S  a A B S  a B B  b b

i

2i

2i

i

L={a b

L={a

con i>0}

b con i>0}

L={a2i b2i con i>0}

•

A b B S

Solución

i

2i

2i

i

L={a b

L={a

con i>0}

b con i>0}

L={a2i b2i con i>0}

•

21

A b B S