Lenguajes Libres de Contexto Preparado por



Descargar 2,99 Mb.
Página1/10
Fecha de conversión14.03.2017
Tamaño2,99 Mb.
  1   2   3   4   5   6   7   8   9   10

Lenguajes Libres de Contexto

  • Preparado por
  • Manuel E. Bermúdez, Ph.D.
  • Profesor Asociado
  • University of Florida
  • Curso de Compiladores

Gramáticas Libres de Contexto

  • Definición: Una gramática libre de contexto (GLC) es una tupla G = (, , P, S), donde todas las producciones son de la forma
  • A  , donde A   y   (u )*.
  • Derivación Izquierda: En cada paso, el símbolo no-terminal más a la izquierda es el que se re-escribe.
  • Derivación Derecha: En cada paso, el símbolo no-terminal más a la derecha es el que se re-escribe.

Árboles de Derivación

  • Un árbol de derivación describe las re-escrituras, en forma independiente del orden (izquierdo o derecho).
  • Cada rama del árbol corresponde a una producción en la gramática.

Árboles de Derivación

  • Notas:
    • Hojas en el árbol son símbolos terminales.
    • El “contorno” inferior es la sentencia.
    • Recursividad izquierda causa ramificación a la izquierda.
    • Recursividad derecha causa ramificación a la derecha.

Metas del Análisis Sintáctico

  • Examinar la hilera de entrada , y determinar si es legal o no en el lenguaje, i.e. si S =>* .
  • Esto es equivalente a (intentar) construir el árbol de derivación.
  • Beneficio adicional: si el inento es exitoso, el árbol refleja la estructura sintáctica de la hilera de entrada.
  • Por lo tanto, el árbol debiera ser único (para una hilera dada).

Ambigüedad en Gramáticas

  • Definición: Una GLC es ambigua si existen dos derivaciones derechas (o izquierdas, pero no ambas) para alguna sentencia z.
  • Definición (equivalente) : Una GLC es ambigua si existen dos árboles de derivación diferentes, para alguna sentencia z.

Ambigüedad en Gramáticas

  • Dos ambigüedades clásicas (al menos en lenguajes de programación):
    • Recursividad simultánea izquierda/derecha:
    • E → E + E
    • Problema del “else colgante”:
    • S → if E then S
    • → if E then S else S

Reducción de Gramáticas

  • ¿ Qué lenguaje genera esta gramática ?
  • S → a D → EDBC
  • A → BCDEF E → CBA
  • B → ASDFA F → S
  • C → DDCF
  • Respuesta: L(G) = {a}
  • Problema: Algunos no-terminales (y producciones) son “inútiles”: no se pueden usar en la generación de ninguna sentencia.

Reducción de Gramáticas

  • Definición: Una GLC es reducida sii para todo A  Ф,
  • a) S =>* αAβ, para algunos α, β  V*,
  • (decimos que A es generable), y
  • b) A =>* z, para algún z  Σ*
  • (decimos que A es terminable)
  • G es reducida sii todo símbolo no-terminal A es generable y también terminable.

Reducción de Gramáticas

  • Ejemplo: S → BB A → aA
  • B → bB → a
  • B no es terminable, porque
  • B =>* z, para ningún z  Σ*.
  • A no es generable, porque
  • S =>* αAβ, para ningunos α,βV*.

Reducción de Gramáticas

  • Para encontrar cuáles no-terminales son generables:
  • Construir el grafo (Ф, δ), donde (A, B)  δ sii
  • A → αBβ es una producción.
  • Verificar que todos los nodos son alcanzables desde S.

Reducción de Gramáticas

  • Ejemplo: S → BB A → aA
  • B → bB → a
  • A no es generable,
  • porque no es alcanzable
  • desde S.
  • S
  • B
  • A

Reducción de Gramáticas

  • Algoritmo 1: Calcular no-terminales generables
  • Generable := {S}
  • while(Generable cambia) do
  • para cada A → Bβ do
  • if A  Generable then
  • Generable := Generable U {B}
  • od
  • { Ahora, Generable contiene los
  • no-terminales que son generables
  • }

Reducción de Gramáticas

  • Para encontrar cuáles no-terminales son terminables:
  • Construir el grafo (2Ф, δ), donde
  • (N, N U {A})  δ sii
  • A → X1 … Xn es una producción, y para
  • todo i,
  • Xi  Σ o bien Xi  N.
  • Verificar que el nodo Ф (todos los no-terminales) es alcanzable desde el nodo ø (vacío).

Reducción de Gramáticas

  • Ejemplo: S → BB A → aA
  • B → bB → a
  • {A, S, B} no es alcanzable desde ø ! Solo {A} es alcanzable desde ø. Conclusión: S y B no son terminables.
  • {A,B}
  • {B}
  • {B,S}
  • {S}
  • ø
  • {A}
  • {A,S}
  • {A,S,B}

Reducción de Gramáticas

  • Algoritmo 2: Calcular no-terminales terminables:
  • Terminable := { };
  • while (Terminable cambia) do
  • para cada A → X1…Xn do
  • if todo no-terminal entre los X’s
  • está en Terminable then
  • Terminable := Terminable U {A}
  • od
  • { Ahora, Terminable contiene los
  • no-terminales que son terminables.
  • }

Reducción de Gramáticas

  • Algorithmo 3: Reducción de una gramática:
  • Encontrar todos los no-terminales generables.
  • Encontrar todos los no-terminales terminables.
  • Eliminar cualquier producción A → X1 … Xn
  • si a) A is not generable
  • o si b) algún Xi no es terminable.
  • Si la nueva gramática no es reducida, repetir el proceso.


Compartir con tus amigos:
  1   2   3   4   5   6   7   8   9   10


La base de datos está protegida por derechos de autor ©absta.info 2019
enviar mensaje

    Página principal