1 Repaso a las fases

  • Análisis léxico / Lenguajes regulares (autómatas finitos)
  • Análisis sintáctico / Lenguajes libres de contexto (autómatas con pila)
  • Análisis semántico / Lenguajes sensibles al contexto (aunque mejor no)
  • Optimización
  • Generación de código

2 Idea

i = 1;
i = i + 2;

3 Idea

arbol.png

Figura 1: Arbol de derivación

4 ¿Cual es el código al que corresponde esta orden?

arbol_pregunta.png

5 Dificultad con los lenguajes de programación

\begin{equation*} \{(^i)^i\;|\; i\ge 0\}. \end{equation*}
  • Expresiones aritméticas
  • Bucles anidados

6 Dificultad con los lenguajes de programación

Todos los lenguajes de programación se definen recursivamente:

  • Un programa es una orden o un programa seguido de una orden
  • Una expresion es un número o la suma de dos expresiones

7 Recordatorio de gramáticas libres de contexto

Una gramática libre de contexto consiste en:

  • un conjunto de símbolos terminales,
  • un conjunto de símbolos no terminales o variables,
  • una variable inicial,
  • un conjunto de producciones, donde la parte izquierda de la producción tiene una variable.

8 Repaso a las fases

fases.png

Figura 3: Fases de la compilación

9 Ejemplo de construcción un árbol de derivación

Supongamos que la gramática es:

\begin{eqnarray*} S\mapsto (S)|\lambda\\ \end{eqnarray*}

y la entrada es \((())\).

El problema ahora es construir un árbol de derivación de forma que las hojas correspondan a la entrada.

10 Ejemplo de la construcción de un árbol de derivación

Una derivación que me genera la palabra

y con la derivación puedo construir el árbol de derivación.

¿Cómo consigo el árbol de derivación directamente?

11 Ejemplo de la construcción de un árbol de derivación

ejemplo_arbol1.png

12 Ejemplo de la construcción de un árbol de derivación

ejemplo_arbol2.png

13 Ejemplo de la construcción de un árbol de derivación

ejemplo_arbol3.png

14 Estrategias de parsing

Los analizadores LL recorren los datos de izquierda a derecha y construyen la derivación izquierda: en cada momento, la pila contiene lo que se espera ``encontrar'' en la cinta.

Los sucesivos pasos del analizador van leyendo la cinta y va modificando la pila para que tenga un resumen de lo que queda por ver.

15 ¿Cómo consigo el árbol de derivación directamente?

LL.png

Figura 7: Parseo LL

16 Ventajas de los analizadores descendentes

La principal ventaja de los analizadores descendentes es que pueden ser construidos ``fácilmente'', en un programa utilizando recursividad.

También que permiten detectar errores e informar al usuario de donde esta exactamente el error.

La desventaja es que necesitan gramáticas que tengan buenas propiedades.

17 Estrategias de parsing

Existe una estrategia alternativa: el análisis LR, que recorre los datos de izquierda a derecha pero construye la derivación derecha.

Sólo que la hemos de construir ``al revés'', empezando por el final: en cada momento, la concatenación del contenido de la pila con lo que queda por leer reconstruyen una derivación a la derecha de la palabra en orden inverso.

18 Analizadores ascendentes LR y autómatas con pila

Vamos a definir dos símbolos:

  • uno para fin de datos $,
  • otro para fondo de pila, €.

y dos operaciones básicas:

  • Desplazar (shift) un símbolo de la entrada es introducido a la pila;
  • Reducir (reduce) una parte derecha de la regla que hay en la cima de la pila, sustituyéndola por la correspondiente parte izquierda de la misma regla.

19 Analizadores ascendentes LR y autómatas con pila

Nuestros autómatas con pila van a poder:

  • Conocer el próximo símbolo de la cinta sin leerlo.
  • Leer más de un elemento de la pila sin perderlo.

20 Analizadores ascendentes LR y autómatas con pila

\begin{eqnarray*} N &:& D\ \mid\ N\ D\\ D &:& 0\ \mid\ 1\ \mid\ 2\ \mid\ 3\ \mid\ 4\ \mid\ 5\ \mid\ 6\ \mid\ 7\ \mid\ 8\ \mid\ 9 \end{eqnarray*}

Colocar € en el fondo de pila:

  1. si la cima de la pila es un dígito, reducir a D
  2. si la cima de la pila es N D, reducir por N : N D
  3. si la cima de la pila es € D, reducir por N : D
  4. si la cima de la pila es € N y viene $, aceptar
  5. si la cima de la pila es N y no viene $, desplazar
  6. si la cima de la pila es € y no viene $, desplazar

21 Analizadores ascendentes LR y autómatas con pila

\begin{eqnarray*} E &:& N\ \mid\ E\ OP\ \ E\\ N &:& D\ \mid\ N\ D\\ D &:& 0\ \mid\ 1\ \mid\ 2\ \mid\ 3\ \mid\ 4\ \mid\ 5\ \mid\ 6\ \mid\ 7\ \mid\ 8\ \mid\ 9\\ OP&:& +\ \mid\ * \end{eqnarray*}

22 Analizadores ascendentes LR y autómatas con pila

  1. si la cima de la pila es un dígito, reducir a D
  2. si la cima de la pila es + o *, reducir a OP
  3. si la cima de la pila es N D, reducir por N : N D
  4. si la cima de la pila es € D, reducir por N : D
  5. si la cima de la pila es OP D, reducir por N : D
  6. si la cima de la pila es € E y viene $, aceptar
  7. si la cima de la pila es N y viene un operador, reducir por E : N
  8. si la cima de la pila es N y viene $, reducir por E : N
  9. si la cima de la pila es N y viene un dígito, desplazar
  10. si la cima de la pila es OP y viene un dígito, desplazar
  11. si la cima de la pila es € y viene un dígito, desplazar
  12. si la cima de la pila es E OP E, reducir por E : E OP E
  13. si la cima de la pila es E y viene un operador, desplazar