Conocidas también como gramáticas de tipo 2 o
gramáticas independientes del contexto, son las que generan los lenguajes
libres o independientes del contexto.
Los lenguajes libres del contexto son aquellos que
pueden ser reconocidos por un autómata de pila determinístico o no
determinístico.
Las Gramáticas Libres de Contexto (Context-Free
Languages) o CFL’s jugaron un papel central en el lenguaje natural desde los
50’s y en los compiladores desde los 60’s
Forman
la base de la sintaxis BNF (Backus-Naur form), son actualmente importantes para
XML y sus DTD’s (document type definition)
Son útiles para describir bloques anidados en
lenguajes de programación ya que describen su sintaxis, además, son llamadas
así porque el elemento no terminal del lado derecho se puede sustituir sin
importar el contexto en que este.
Puede
ser definida mediante la 4-tupla G = (N, T, P, S), siendo
-
N es un conjunto finito de símbolos no terminales (disjunto de T)
-
T es un conjunto finito de símbolos terminales
-
P es un conjunto finito de producciones o reglas gramaticales, de la forma A à a, donde A es un elemento de N y a es
un elemento de (T U N)* (una secuencia posiblemente vacia de terminales y no
terminales)
-
S es el símbolo inicial, distinguido o axioma del conjunto N
Ejemplo 1
Una
simple gramatica libre de contexto es: SàaSb
| ε
Esta gramatica genera el lenguaje no regular {anbn:n
> 0}
Ejemplo 2
Gramática libre de contexto para expresiones enteras
algebraicas sintácticamente correctas sobre las variables x, y y z:
S à x | y | z | S +
S | S – S | S * S | S / S | (S)
Cadena (x + y) *x – z *y / (x + x) valida
Ejemplo 3
Lenguaje consistente en todas las cadenas que se pueden
formar con las letras a y b, habiendo un número diferente de una que de otra,
seria:
S → U | V
U → TaU | TaT
V → TbV | TbT
T → aTbT | bTaT | ε
T genera todas las cadenas con la misma
cantidad de letras a que b, U genera todas las cadenas con más letras a, y V
todas las cadenas con más letras b.
Ejemplo 4
Gramática libre de
contexto para el lenguaje
{anbmcm+n:n
> 0, m > 0}
S → aSc | B
B → bBc | ε
Ejemplo 5
La gramática G = ({E,T,F}, {a,+,*,(,)}, S, P) P:
E→E + T | T
T→T * F | F
F →( E ) | a
