Procesadores de Lenguajes

3º. 2º cuatrimestre. Itinerario de Computación. Grado en Ingeniería Informática. ULL


Organization ULL-ESIT-PL-1920   Github Classroom ULL-ESIT-PL-1920   Campus Virtual PL   Chat Chat   Profesor Casiano

Table of Contents

Recorrido del árbol en un ADPR

¿En que forma es recorrido el árbol de análisis sintáctico concreto en un analizador descendente predictivo recursivo? ¿En que orden son visitados los nodos?

Factores Comunes

Si se tiene una variable con producciones:

Aαβαγ

Las dos producciones tienen un máximo factor común en la izquierda de su parte derecha α. Asumimos que FIRST(β)FIRST(γ)=.

  1. ¿Cómo puede modificarse la gramática para obtener una nueva gramática que cumpla la condición de que las partes derechas tienen conjuntos FIRST(γi) disjuntos?

  2. ¿Puede modificarse la técnica APDR para que funcione sobre gramáticas con este tipo de producciones?.

Derivaciones a vacío

Surge un problema cuando Aγ1γn y la palabra vacía está en alguno de los conjuntos FIRST(γi). ¿Que hacer entonces?

Nótese que si Aγ y ϵFIRST(γ) es porque existe una derivación γϵ.

¿Que terminales podemos legalmente encontrarnos cuando estamos en la subrutina A?

Consideremos una derivación desde el símbolo de arranque en la que se use la producción Aγ.

Dicha derivación forzosamente tendrá la forma:

SβA aμβγ aμβ aμ.

Cualquier terminal aΣ que pueda aparecer en una derivación desde el símbolo de arranque inmediatamente a continuación de la variable A es susceptible de ser visto cuando se esta analizando A y se aplicó Aγ con

γϵ.

Esto nos lleva a la definición del conjunto FOLLOW(A) como conjunto de terminales que pueden aparecer a continuación de A en una derivación desde el símbolo de arranque:

Dada una gramática G=(Σ,V,P,S) y una variable AV se define el conjunto FOLLOW(A) como:

FOLLOW(A)={bΣ: SαAbβ}E(A)

donde

E(A)={{$}si SαAen otro caso

Aqui $ denota el final de la entrada

Si Aγ1γn dado que los conjuntos FIRST(γi) han de ser disjuntos para que un analizador predictivo APDR funcione, sólo una parte derecha puede contener la palabra vacía en su FIRST. Supongamos que es γn. Podemos reformular la construcción del procedimiento para la variable A siguiendo este seudocódigo:

    function A() {
      if (lookahead in FIRST(gamma_1)) { imitar gamma_1 }
      elsif (lookahead in FIRST(gamma_2)) { imitar gamma_2 }
      ...
      else (lookahead in FIRST(gamma_n) or lookahead in FOLLOW(A)) { imitar gamma_n }
    }

Un caso particular de γnϵ es que γn=ϵ.

En tal caso, y como es obvio, el significado de imitar gamma_n es equivalente a ejecutar una sentencia vacía.

Construcción de los conjuntos de Primeros y Siguientes

Construcción de los conjuntos FIRST(X)

Repita el siguiente conjunto de reglas hasta que no se puedan añadir mas símbolos terminales o a ningún conjunto FIRST(X):

  1. Si XΣ entonces FIRST(X)=X
  2. Si Xϵ entonces FIRST(X)=FIRST(X){ϵ}
  3. SiXV y XY1Y2YkP entonces
    i = 1;
    do FIRST(X) = FIRST(X) U FIRST*(Y_i);
     i++; 
    while (i <= k and  in FIRST(Y_i))
    
  4. Añadir ϵ a FIRST(X) si ik y ϵFIRST(Yk)

Aqui FIRST(Y) denota al conjunto FIRST(Y){ϵ}.

Este algoritmo puede ser extendido para calcular FIRST(α) para α=X1X2Xn(VΣ). El esquema es anólogo al de un símbolo individual.

Construcción de los conjuntos FOLLOW(A) AV:

Repetir los siguientes pasos hasta que ninguno de los conjuntos FOLLOW cambie:

  1. FOLLOW(S)={$} ($ representa el final de la entrada)

  2. Si AαBβ entonces FOLLOW(B)=FOLLOW(B)(FIRST(β){ϵ})

  3. Si AαB)o\(AαBβ y ϵFIRST(β) entonces FOLLOW(B)=FOLLOW(B)FOLLOW(A)

Gramáticas LL(1)

Una gramática G=(Σ,V,P,S) cuyo lenguaje generado L(G) puede ser analizado por un analizador sintáctico descendente recursivo predictivo se denomina LL(1). Una gramática es LL(1) si y sólo si para cualesquiera dos producciones Aα y Aβ de G se cumple:

  1. FIRST(α)FIRST(β)=
  2. Si ϵFIRST(α), entonces FIRST(β)FOLLOW(A)=

¿De donde viene el nombre LL(1)?

La primera L hace alusión al hecho de que el flujo de terminales se lee de izquierda a derecha, accediendo a la entrada por su izquierda (Left).

La segunda L se refiere a que el método de análisis predictivo construye una derivación a izquierdas.

El número entre paréntesis indica el número de terminales que debemos consultar para decidir que regla de producción se aplica. Asi, en una gramática LL(2) la decisión final de que producción elegir se hace consultando los dos terminales a la entrada.

Ejercicio

Cuando se dice que una gramática es LL(1) si, y sólo si:

  1. FIRST(α)FIRST(β)=
  2. Si ϵFIRST(α), entonces FIRST(β)FOLLOW(A)=

se asume que los conjuntos FIRST(α) no son vacíos.

Ambiguedad y LL(1)

¿Puede una gramática LL(1) ser ambigua?. Razone su respuesta.

term factor ‘*’ term | factor factor ‘(‘ expression ‘)’ | ID | NUM | STR idlist ID ‘,’ idlist | ID —————————————————————————–

Recursión por la Izquierda

Una gramática es recursiva por la izquierda cuando existe una derivación AAα.

En particular, es recursiva por la izquierda si contiene una regla de producción de la forma AAα. En este caso se dice que la recursión por la izquierda es directa.

Cuando la gramática es recursiva por la izquierda, el método de análisis recursivo descendente predictivo no funciona. En ese caso, el procedimiento A asociado con A ciclaría para siempre sin llegar a consumir ningún terminal.

Eliminación de la Recursión por la Izquierda en la Gramática

Es posible modificar la gramática para eliminar la recursión por la izquierda. En este apartado nos limitaremos al caso de recursión por la izquierda directa. La generalización al caso de recursión por la izquierda no-directa se reduce a la iteración de la solución propuesta para el caso directo.

Consideremos una variable A con dos producciones:

AAαβ

donde α,β(VΣ) no comienzan por A. Estas dos producciones pueden ser sustituidas por:

AβR RαRϵ

eliminando así la recursión por la izquierda.

La producción RαR se dice recursiva por la derecha. También podemos usar el operador de repetición y reducir la solución a una única regla Aβα

Las producciones recursivas por la derecha dan lugar a árboles que se hunden hacia la derecha. Es mas difícil traducir desde esta clase de árboles operadores como el menos, que son asociativos a izquierdas.

Ejercicio

Elimine la recursión por la izquierda de la gramática

exprexprNUM exprNUM

Your Comments

Comment with Disqus