Gramáticas
Independientes de
Contexto
Capítulo 4
Lenguaje independiente
de contexto

Dada un gramática G
– Con símbolo inicial S
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 =>* α
– α se deriva en 0 o más pasos
– α puede contener no terminales
– α es una forma de frase de G
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
{
Variable <> 0
Programa
Rutina
Instrucción
Variable
++
;
}
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
Instrucción
Variable
--
Arboles de análisis
sintáctico

Pueden ser derivados:
– Por la izquierda
– Por la derecha
¿De forma única?
 Gramáticas ambiguas

– Más de un árbol para una frase
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:
– Cadenas de paréntesis balanceados

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:

– Se reduce a una independiente
– Se verifica en el análisis semántico
Descargar

Gramáticas Independientes de Contexto