Tema 3: Análisis sintáctico

Horas de trabajo estimadas y calendario de clases

Posible planificación del trabajo al ritmo de las clases presenciales:

19/11 - 26/11 - 03-10/12 - 17/12 - Para saber más

Plan de trabajo y bibliografía recomendada

• 3.1 Gramáticas libres de contexto y análisis sintáctico.

  Semana del 19/11/2009

  • Los contenidos de la asignatura II20 que supondremos conocidos son los del capítulo 5 del libro "Introducción a la teoría de autómatas, lenguajes y computación".

  • Haz una primera lectura (sin preocuparte si de momento no entiendes todo) del capítulo 3 "Gramáticas libres de contexto y análisis sintáctico" del libro "Construcción de compiladores" de Louden, incluyendo la presentación y al menos estos apartados:

    1. El proceso del análisis sintáctico.

    2. Gramáticas libres de contexto.
       En inglés se denominan CFG (Context-Free Grammars). En castellano se conocen también como GIC (Gramáticas Independientes del Contexto) y gramáticas incontextuales.

    3. Arboles de análisis gramatical y árboles sintácticos abstractos.
       Mira también los ejemplos de las páginas 136-138.
       Los árboles de análisis gramatical son conocidos también como árboles de derivación. Los árboles sintácticos abstractos son conocidos como AST (Abstract Syntax Trees).

    4. Ambigüedad.

    5. Notaciones extendidas: EBNF y diagramas de sintaxis.
       En nuestro curso no utilizaremos los diagramas de sintaxis ni la notación EBNF, sino la de las expresiones regulares. Esto lo veremos en clase. En cualquier caso, lee ese apartado.

    6. Propiedades formales de los lenguajes libres de contexto.

  • Un primer objetivo importante del tema es tener claros los conceptos de prioridad, asociatividad y orden de evaluación de los operadores, y cuándo se aplican (para luego poder reflejar eso en las gramáticas y en los AST). Por ello, resuelve los ejercicios de este cuestionario sobre expresiones y su evaluación (solución en clase).

  • Un segundo objetivo importante del tema es aprender a leer y a escribir lo que denominamos Gramáticas con Partes Derechas Regulares (GPDR), y a transformarlas en GIC equivalentes. En ellas utilizaremos la misma notación de las expresiones regulares del tema 2 en vez de la notación EBNF. En la práctica 1 ya has trabajado con un primer ejemplo y varias ampliaciones, dándote la gramática hecha. Ahora debes aprender a escribirlas tú. Tras la explicación de esto en clase, intenta resolver en primer lugar los ejercicios 5, 7.A y 11 de este boletín de modelado sintáctico de la asignatura IG29, y después compara tu solución con éstas:

    Abrir solución del ejercicio 5.

    Abrir solución del ejercicio 7 (nos interesa de momento el 7.A).

    Abrir solución del ejercicio 11.

  Semana del 26/11/2009

  • Resuelve ahora los ejercicios 9, 8, 2 y 1 de ese boletín, comparando tu solución con éstas tras completar cada uno:

    Abrir solución del ejercicio 9.

    Abrir solución del ejercicio 8.

    Abrir solución del ejercicio 2.

    Abrir solución del ejercicio 1.

  • Hay ocasiones en las que resulta natural modelar algunas restricciones en el nivel semántico, y difícil o imposible hacerlo a nivel sintáctico con gramáticas incontextuales. Esto lo entenderás mejor cuando acabemos el tema 4. Los ejercicios 3, 6 y 10 del boletín enterior nos permitirán más adelante reflexionar sobre esto. Intenta resolverlos ahora empleando gramáticas, y luego compara tu solución con éstas:

    Abrir solución del ejercicio 3.

    Abrir solución del ejercicio 6.

    Abrir solución del ejercicio 10.

• 3.2 Análisis sintáctico descendente.

  • 3.2.1 Análisis sintáctico LL(1) y RLL(1).

    Semanas del 03/12/2009 y del 10/12/2009

    • Nos basaremos ahora en el capítulo 4 "Análisis sintáctico descendente" del libro "Construcción de compiladores" de Louden, aunque formalizaremos los conceptos y métodos de otro modo.

    • El tercer objetivo importante del tema es aprender a implementar analizadores sintácticos descendentes predictivos.

      Lee la presentación del capítulo 4 y el apartado 4.1 "Análisis sintáctico descendente mediante método descendente recursivo". Intenta reconocer el método de análisis que has implementado, con otra notación y otro lenguaje, siguiendo la guía de desarrollo de la práctica 1. Debes aplicar el mismo método para implementar la calculadora de la práctica 2.

    • El cuarto objetivo importante del tema es aprender a reconocer si una gramática es adecuada para poder emplear el método de análisis anterior.

      Lee el apartado 4.3 "Conjuntos Primero y Siguiente". En clase modificaremos ligeramente la notación, para ver más explícitamente qué partes derechas son anulables, y veremos cómo utilizar el mismo método para averiguar si una gramática con partes derechas regulares es RLL(1).

      Los siguientes ejercicios incluyen ejemplos de aplicación de eso a una gramática dada para saber si es LL(1) o RLL(1):

      • Ejercicio A1.

        Abrir solución.

      • Ejercicio A2.

        Abrir solución.

      • Ejercicio A3.

        Abrir solución.

      • Ejercicio A4.

        Abrir solución.

      • Ejercicio A5.

        Abrir solución.

      • Ejercicio A6 (publicado el 12/12/2009; incluye ejemplo visto en una clase previa).

      • Ejercicio A7 (publicado el 18/12/2009; incluye ejemplo visto en una clase previa).

      En el apartado 4.2 "Análisis sintáctico LL(1)", los subapartados 4.2.1 y 4.2.2 describen la versión del método de análisis sintáctico LL(1) que emplea una pila explícita. Léelos también, aunque la versión que más nos interesa es el método descendente recursivo.

    • En los siguientes ejercicios, se trata de razonar sobre la veracidad o falsedad de lo que se afirma sobre gramáticas LL(1) o RLL(1) (los apartados sobre gramáticas LR y SLR no nos interesan ahora), y con ello de entender mejor los conceptos involucrados:

      • Pregunta 4 en el examen de diciembre 2006.

        Abrir solución (sesión de refuerzo del 07/06/2010).

      • Pregunta 4 en el examen de diciembre 2005.

        Abrir solución.

      • Pregunta 4 en el examen virtual de mayo 2005.

        Abrir solución (examen completo).

      • Pregunta 4 en el examen de diciembre 2004.

        Abrir solución.

      • Pregunta 4 en el examen de septiembre 2004.

        Abrir solución.

      • Pregunta 3 en el examen de diciembre 2002.

        Abrir solución.

      • Pregunta 3 en el examen virtual de junio 2002.

        Abrir solución.

  • 3.2.2 Modelado sintáctico LL(1) y RLL(1). Modelado RLL(1) de expresiones.

    Semana del 17/12/2009

    • El último objetivo importante del tema es aprender a escribir gramáticas LL(1) o RLL(1) con las que poder aplicar las técnicas de análisis descendente predictivo. Esto incluye escribir gramáticas LL(1) o RLL(1) que modelen expresiones formadas con operadores de diferentes prioridades y asociatividades, quizás lo más complejo del tema.

      En la práctica 2 se ha planteado un problema bastante completo de modelado teniendo en cuenta todo eso.

      También querremos escribir gramáticas que no sean ambiguas. El problema de la ambigüedad es indecidible pero, afortunadamente, las gramáticas LL(1) y RLL(1) no son ambiguas: si demostramos que una gramática es LL(1) o RLL(1), estaremos seguros de que no es ambigua; y si tiene conflictos LL(1), no sabremos si es ambigua o no, pero nos dará igual, la descartaremos. Antes de seguir, intenta resolver estos dos ejercicios, en los que se pide averiguar si una gramática dada es ambigua (más adelante se plantean otras reflexiones y ejercicios sobre ese tema):

      • Pregunta 3 en el examen de diciembre 2007 (dificultad: muy baja).

        Abrir solución.

      • Pregunta 4 en el examen de diciembre 2001 (y en el examen de febrero 2002; dificultad: alta).

        Abrir solución.

      Tras la explicación de los conceptos básicos sobre modelado RLL(1) de expresiones en clase, lee el apartado 4.2.3 "Eliminación de recursión por la izquierda y factorización por la izquierda". Aunque la explicación sea algo confusa, debes entenderla. A continuación intenta resolver los siguientes ejercicios, que están pensados para terminar de aclarar algunos conceptos tratados ahí:

      • Ejercicio 4 de este boletín de modelado sintáctico de la asignatura IG29.

        Abrir solución.

      • Ejercicio 7.B de ese mismo boletín.

        Abrir solución.

      • Ejercicio M1.

        Abrir solución.

      • Ejercicio M2 (sesión de refuerzo del 13/04/2010; ver Louden ej. 4.1 en p. 158, y texto p. 160-162 vs. 146-151).

      • Ejercicio M3 (ver Louden ej. 4.2 en p. 159).

      • Ejercicio M4 (ver Louden ej. 4.6 en p. 165).

      • Ejercicio M5 (publicado el 19/12/2009; resolver tras M2-M3-M4; después revisar práctica 1).

      • Ejercicio M6 (ver Louden p. 156, ej. 4.5 en p. 164, etc.).

      • Ejercicio M7.

        Abrir solución (sesión de refuerzo del 03/05/2010).

      • Otro ejercicio sobre análisis LL(1) de la asignatura IG29 (sesión de refuerzo del 19/04/2010; requiere tener muy claro cómo se modelan los niveles de prioridad de operadores binarios, y extender las ideas para aplicarlas a un operador ternario; es muy bueno).

      • Control de análisis sintáctico del grupo TE2 del curso 2007/2008 (asignaciones múltiples).

        Abrir solución del primer apartado.

  • Ejercicios adicionales.

    Semana del 17/12/2009

    Intenta resolver cada uno de los siguientes ejercicios, sin dedicar más de 45 minutos a cada ejercicio de examen:

    • Pregunta 3 en el examen de junio 2009.

      Abrir solución (sesiones de refuerzo del 26/04/2010 y del 03/05/2010).

    • Pregunta 3 en el examen de septiembre 2008.

      Abrir solución (sesión de refuerzo del 14/06/2010).

    • Pregunta 3 en el examen de diciembre 2009.

    • Ejercicio A8 (publicado el 18/12/2009).

    • Ejercicio A9 (publicado el 18/12/2009).

    Ten en cuenta también que la pregunta del examen final correspondiente a las prácticas requiere explicar todas las modificaciones que habría que hacer en el compilador de la práctica 4 a nivel léxico, sintáctico, semántico, y de generación de código. Eso incluye por tanto, entre otras cosas, qué modificaciones habría que hacer en la gramática, y el resultado debe ser RLL(1). Mira, por ejemplo, la pregunta 1 del examen de diciembre 2009 y las notas obtenidas por los estudiantes. Al finalizar el tema 5 resolveremos algunas de los últimos cursos.

  • Evaluación del tema 3 en el itinerario A (grupo TE2): jueves 18/02/2010.

    • Enunciado.

    • Solución (con ejemplos de errores; sesiones de refuerzo del 29/03/2010 y del 26/04/2010).

    • Notas.

  • Otros ejercicios opcionales.

    Resto del curso

    Los siguientes ejercicios no se incluyen en las hora previstas, pero se pueden discutir en tutorías o en las sesiones de refuerzo con quien quiera seguir practicando.

    • Pregunta 3 en el examen de junio 2008.

      Abrir solución (sesión de refuerzo del 03/05/2010).

    • Pregunta 3 en el examen de septiembre 2009.

      Abrir solución (sesión de refuerzo del 07/06/2010).

    • Pregunta 3 en el examen de diciembre 2008.

      Abrir solución.

    • Pregunta 4 en el examen de septiembre 2007.

      Abrir solución (sesión de refuerzo del 07/06/2010).

    • Pregunta 4 en el examen de junio 2007.

    • Pregunta 3 en el examen de diciembre 2003.

      Abrir solución.

    • Pregunta 3 en el examen de julio 2001.

      Abrir solución.

    • Pregunta 2 en el examen virtual de junio 2001.

      Abrir solución (examen completo; ten en cuenta que, en ese curso, no se utilizaba la función anulable; para indicar que una forma sentencial es anulable, lo que se hacía es meter la cadena vacía en su conjunto de primeros, tal como se hace en el libro de Louden; el paso de una notación a otra es sencillo).

  • Estudio final.

    Relee los capítulos 3 y 4 del libro "Construcción de compiladores" de K. Louden, asegurándote de que entiendes lo que no entendieses en la primera lectura.

  • Otras fuentes de información.

    Si quieres ver explicaciones alternativas y complementarias de este tema, estas son aconsejables:

    • El tema 4 (páginas 1 a 22) y el tema 5 (páginas 23 a 62) de los apuntes "Análisis Sintáctico en Procesadores de Lenguaje" de la Universidad de Oviedo. Hay apartados que no hemos visto, y nosotros hemos visto otras cosas, pero deberías ser capaz de entenderlo todo. Les sigue el tema 6, en el que puedes encontrar una introducción al análisis sintáctico ascendente, y una comparación con el descendente (páginas 69-70).

    • El tema 4 del libro "Compiladores : principios, técnicas y herramientas" (2008) de A. Aho, M. Lam, R. Sethi y J. Ullman, aunque la traducción no es muy buena y ha introducido alguna errata; el libro "Compilers : principles, techniques, and tools" es la versión original en inglés.

    • Este apartado 2.3.2.4 "Extended CF Grammars" del libro "Parsing techniques: a practical guide" introduce las GPDR y habla de dos posibles interpretaciones de las clausuras, una iterativa y otra recursiva por la derecha (nosotros seguimos la iterativa).

    En el LLEU y en la biblioteca de la UJI puedes encontrar otros libros sobre Procesadores de Lenguaje, en todos ellos encontrarás explicaciones sobre el análisis descendente, posiblemente con enfoques diferentes.

  ---