Gramáticas Independientes de Contexto



Descargar 5,4 Kb.
Fecha de conversión05.07.2017
Tamaño5,4 Kb.

Gramáticas Independientes de Contexto

  • Capítulo 4

Lenguaje independiente de contexto

  • Dada un gramática G
  • L(G) lenguaje generado por G
  • Cadena w está en L(G)
    • Si S =>+ w
      • S deriva w en uno o más pasos
      • S => w (un paso)
      • S => AB => w (más de un paso)

Lenguajes independientes de contexto

  • Si w está en L(G)
    • w es una frase de L(G)
  • Lenguaje: todas las frases posibles
    • Lenguaje independiente de contexto
  • Si S =>* α

Derivaciones

  • Por la izquierda:
    • (E+E) => (id+E) => (id+id)
  • Por la derecha
    • (E+E) => (E+id) => (id+id)
  • Arbol de análisis sintáctico
    • Representación gráfica de una derivación

Ejemplo

  • While v <> 0 do {x++; v--}
  • Programa
  • Instrucción
  • While
  • Prueba
  • do
  • Programa
  • {
  • Rutina
  • }
  • Instrucción
  • ;
  • Instrucción
  • ++
  • Variable
  • --
  • Variable
  • <>
  • 0
  • Programa -> Instrucción | { Rutina }
  • Rutina -> Instrucción ; Instrucción |
  • Instrucción ; Rutina
  • Instrucción -> nil | Variable ++ |
  • Variable -- |
  • While Prueba do Programa
  • Prueba -> Variable <> 0 |
  • Variable = 0

Arboles de análisis sintáctico

  • Pueden ser derivados:
    • Por la izquierda
    • Por la derecha
  • ¿De forma única?
  • Gramáticas ambiguas

Escritura de Gramáticas

  • ¿Cómo se puede escribir una gramática que requiera que las variables se declaren antes de usarlas?

Escritura de Gramáticas

  • ¿Cómo escribir una donde el número de parámetros de un procedimiento coincide en la llamada y en la definición?

Procedimiento

  • Escribir la gramática G
  • Definir el lenguaje L
  • Demostrar que:
    • Toda cadena generada por G está en L
    • Toda cadena de L está en G

Ejemplo

  • Gramática G:
    • S => (S)S | nil
  • Lenguaje L:
  • Demostración...
    • Libro pp. 178

Lenguajes abstractos

  • L1 = {wcw | w está en (a | b)*}
  • Toda variable debe definirse antes de usarse
  • L2 = {anbmcndm | n >= 1 y m>=1}
  • El número de parámetros en la llamada a un procedimiento debe coincidir con el número en el encabezado

Gramáticas no independientes del contexto

  • Lenguajes abstractos
  • No pueden definirse por gramáticas formales
  • ¿Dependientes del contexto?

Problemas GNIC

  • ¿Cómo comprobar variables y tipos?
  • ¿Cómo verificar match de parámetros?
  • ¿Dimensiones de un arreglo?
  • ¿Existencia de procedimientos?

Análisis Sintáctico

  • Asume gramática independiente de contexto
  • Si la gramática es dependiente del contexto:


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

    Página principal