Capítulo 5: Lenguajes y gramáticas independientes del contexto 5.1 Gramáticas independientes del contexto

5.1.1 Un ejemplo informal 5.1.2 Definición de las gramáticas independientes del contexto 5.1.3 Derivaciones utilizando una gramática5.1.4 Derivaciones izquierda y derecha 5.1.5 Lenguaje de una gramática 5.1.6 Formas sentenciales

5.2 Árboles de derivación 5.2.1 Construcción de los árboles de derivación 5.2.2 Resultado de un árbol de derivación 5.2.3 Inferencia, derivaciones y árboles de derivación

5.3 Aplicaciones de las gramáticas independientes del contexto 5.3.1 Analizadores sintácticos

5.4 Ambigüedad

Capítulo 5: Lenguajes y gramáticas independientes del contexto

5.1 Gramáticas independientes del contexto

5.1.1 Un ejemplo informal

Consideremos el lenguaje de los palíndromos. Una cadena w es un palíndromo si y sólo si w = wR. Consideremos únicamente los palíndromos descritos con el alfabeto {0, 1}. El lenguaje Lpal de los palíndromos formados por ceros y unos no es un lenguaje regular, según se demuestra por el lema del bombeo, con la contante n y w = 0n10n. Existe una definición recursiva y natural que nos dice cuándo una cadena de ceros y unos pertenece a Lpal. Se parte de un caso básico estableciendo que unas cuantas cadenas obvias pertenecen a Lpal, y luego se aplica la idea de que si una cadena es un palíndromo, tiene que comenzar y terminar con el mismo símbolo. Además, cuando el primer y último símbolo se eliminan, la cadena resultante también tiene que ser un palíndromo. Es decir,

Base. ε, 0 y 1 son palíndromos.Paso inductivo. Si w es un palíndromo, también lo son 0w0 y 1wl. Ninguna cadena es un palíndromo de ceros y unos, a menos que cumpla el caso base y esta regla de inducción.

Una gramática independiente del contexto es una notación formal que sirve para expresar las definiciones recursivas de los lenguajes. Una gramática consta de una o más variables que representan las clases de cadenas, es decir, los lenguajes. En este ejemplo sólo necesitamos una variable P, que representa el conjunto de palíndromos; ésta es la clase de cadenas que forman el lenguaje Lpal. Existen reglas que establecen cómo se construyen las cadenas de cada clase. La construcción puede emplear símbolos del alfabeto, cadenas que se sabe que pertenecen a una de las clases, o ambos elementos.

Ejemplo 5.1. Las reglas que definen los palíndromos, expresadas empleando la notación de la gramática independiente del contexto son:

Las tres primeras reglas definen el caso básico. Establecen que la clase de palíndromos incluye las cadenas ε, 0 y 1. Ninguno de los lados de la derecha de estas reglas (la parte que sigue a las flechas) contiene una variable, razón por la que constituyen el caso básico de la definición. Las dos últimas reglas forman la parte inductiva de la definición.

5.1.2 Definición de las gramáticas independientes del contexto

Existen cuatro componentes importantes en una descripción gramatical de un lenguaje:

l. Un conjunto finito de símbolos que forma las cadenas del lenguaje que se está definiendo; denominamos a este conjunto alfabeto terminal o alfabeto de símbolos terminales. En ejemplo 5.1: {0,1}.

2. Un conjunto finito de variables, denominado también en ocasiones símbolos no terminales o categorías sintácticas. Cada variable representa un lenguaje; es decir, un conjunto de cadenas. En ejemplo 5.1: {P}.

3. Una de las variables representa el lenguaje que se está definiendo; se denomina símbolo inicial. Otras variables representan las clases auxiliares de cadenas que se emplean para definir el lenguaje del símbolo inicial. En ejemplo 5.1 P es la variable Inicial.

1

4. Un conjunto finito de producciones o reglas que representan la definición recursiva de un lenguaje. Cada producción consta de:

a) Una variable a la que define (parcialmente) la producción. Esta variable a menudo se denomina cabeza de la producción.b) El símbolo de producción →.c) Una cadena formada por cero o más símbolos terminales y variables. Esta cadena, denominada cuerpo de la producción, representa una manera de formar cadenas pertenecientes al lenguaje de la variable de la cabeza. De este modo, dejamos los símbolos terminales invariables y sustituimos cada una de las variables del cuerpo por una cadena que sabemos que pertenece al lenguaje de dicha variable.

Estos cuatro componentes definen una gramática independiente del contexto, (GIC), o simplemente una gramática, o en inglés CFG, context-free grammar. G = (V, T, P, S) representa una GIC G, donde V es el conjunto de variables, T son los símbolos terminales, P es el conjunto de producciones y S es el símbolo inicial.

Ejemplo 5.2. La gramática Gpal para los palíndromos se representa: Gpal = ({P}, {0, 1}, A, P), donde A representa el conjunto de las cinco producciones mostradas.

Ejemplo 5.3. La siguiente GIC representa una simplificación de las expresiones de un lenguaje de programación típico. Vamos a limitarnos a los operadores + y *. Establecemos que los argumentos sean identificadores. Todo identificador debe comenzar por a o b, y deberá ir seguido por cualquier cadena perteneciente a {a, b, 0, l}*. En esta gramática necesitamos dos variables. E, representa expresiones, se trata del símbolo inicial y representa el lenguaje de las expresiones que se van a definir. La otra variable, I, representa los identificadores. Su lenguaje, que es regular, es el de la expresión regular: (a + b)(a + b + 0 + l )*.

No vamos a emplear expresiones regulares directamente en las gramáticas. En lugar de ello, utilizaremos un conjunto de producciones que prácticamente es lo mismo que una expresión regular. La gramática para expresiones se define formalmente como G = ({E, I}, T, P, E), donde T es el conjunto de símbolos {+, *, (, ), a, b, 0, l} y P es el conjunto de producciones mostrado en la figura:

5.1.3 Derivaciones utilizando una gramática

Aplicamos las producciones de una GIC para inferir que determinadas cadenas pertenecen al lenguaje de una cierta variable. Para llevar a cabo esta inferencia hay disponibles dos métodos.

El primero consiste en emplear las reglas para pasar del cuerpo a la cabeza: tomamos cadenas que sabemos que pertenecen al lenguaje de cada una de las variables del cuerpo, las concatenamos en el orden apropiado con cualquier símbolo terminal que aparezca en el cuerpo e inferimos que la cadena resultante pertenece al lenguaje de la variable de la cabeza. Este procedimiento lo denominaremos inferencia recursiva.

El otro método que permite definir el lenguaje de una gramática es en el que se emplean las producciones desde la cabeza hasta el cuerpo. El símbolo inicial se expande utilizando una de sus producciones. A continuación, expandimos la cadena resultante reemplazando una de las variables por el cuerpo de una de sus producciones, y así sucesivamente, hasta obtener una cadena compuesta totalmente por terminales. El lenguaje de la gramática son todas las cadenas de terminales que se pueden obtener de esta forma. Este uso de las gramáticas se denomina derivación.

Ejemplo 5.4. Aquí se muestran algunas cadenas obtenidas mediante inferencia recursiva de la gramática del ejemplo 5.3

2

El proceso de derivación de cadenas aplicando producciones desde la cabeza hasta el cuerpo requiere la definición de un nuevo símbolo de relación . Supongamos que G = (V, T, P, S) es una GIC. Sea αAβ una cadena de símbolos terminales y variables, siendo α y β cadenas de (V + T)* y A una variable. Sea A→γ una producción de G. Entonces decimos que

, o si solo estamos trabajando con G que . Un paso de derivación reemplaza cualquier variable de

cualquier parte de la cadena por el cuerpo de una de sus producciones. Podemos extender la relación para representar cero, uno o más pasos de derivaciones, utilizaremos el símbolo * para indicar "cero o más pasos", como sigue:

Base. Para cualquier cadena α de símbolos terminales y variables, decimos que . Es decir, cualquier cadena se

deriva de sí misma.

Paso inductivo. Si y se cumple .

Si la gramática G se sobreentiende, entonces empleamos en lugar de .

Ejemplo 5.5. La inferencia de que a*(a + b00) está en el lenguaje de la variable E se puede reflejar en una derivación de dicha cadena, partiendo de la cadena E.

3

Se han seguido las producciones 3, 1, 5, 4, 2, 1, 5, 1, 9, 9, 6.

Podemos emplear la relación para condensar la derivación: E a*(a + b00). Los dos puntos de vista, inferencia

recursiva y derivación, son equivalentes. Es decir, se infiere que una cadena de símbolos terminales w pertenece al lenguaje

de cierta variable A si y sólo si A w.

Notación compacta para produccionesEs conveniente pensar que una producción "pertenece" a la variable que aparece en su cabeza. A menudo se usará "las producciones de A" o "producciones-A" para hacer referencia a las producciones cuya cabeza es la variable A. Otra forma de escribir varias producciones pertenecientes a la misa variable, A→α1, A→α2… A→α3n es A→α1|α2|…|αn.

Notación para las derivaciones de las GIC1. Las letras minúsculas del principio del alfabeto (a, b,…), dígitos y otros caracteres como el signo más (+) o los paréntesis son símbolos terminales.2. Las letras mayúsculas del principio del alfabeto (A, B…) son variables.3. Las letras minúsculas del final del alfabeto, como w o z, son cadenas de símbolos terminales.4. Las letras mayúsculas del final del alfabeto, como X o Y, son símbolos terminales o variables.5. Las letras griegas minúsculas, como α y β, son cadenas formadas por símbolos terminales y/o variables.

5.4 Derivaciones izquierda y derecha

Con el fin de clarificar la sustitución realizada en una derivación, a menudo se obliga a que la variable reemplazada sea

la situada más a la izquierda; dicha derivación se denomina derivación más a la izquierda, y se representa mediante o

. También se puede hacer por la derecha, con la derivación más a la derecha representada mediante o .

Ejemplo 5.6. Se realizará la misma derivación que en el ejemplo 5.6, pero por la izquierda y por la derecha:

Para cualquier derivación existe una derivación más a la izquierda equivalente y una derivación más a la derecha equivalente.

5.1.5 Lenguaje de una gramática

Si G(V, T, P, S) es una GIC, el lenguaje de G, designado como L(G), es el conjunto de cadenas terminales que tienen

derivaciones desde el símbolo inicial. Es decir, L(G) = {w pertenece a T* | S w}.

Si un lenguaje L es el lenguaje de cierta gramática independiente del contexto, entonces se dice que L es un lenguaje independiente del contexto o LIC (CFL, context-free language).

5.1.6 Formas sentenciales

Las derivaciones a partir del símbolo inicial producen cadenas que desempeñan un papel especial y se conocen como

"formas sentenciales". Es decir, si G = (V, T, P, S) es una GIC, entonces cualquier cadena α de (V U T)* tal que S α es

una forma sentencial. Si S α, entonces α es una forma sentencial por la izquierda y si S α entonces α es una forma

sentencial por la derecha. Observe que el lenguaje L(G) está formado por aquellas formas sentenciales que pertenecen a T*, es decir, que solamente constan de símbolos terminales.

Ejemplo 5.8. Considere la gramática para las expresiones del ejemplo 5.5. Por ejemplo, E*(I + E) es una forma sentencial, dado que existe una derivación: , aunque no es una derivación más a la izquierda ni a la derecha, ya que en el último paso se sustituye la variable central. Ejemplos de formas sentenciales por la izquierda o la derecha serían:

5.2 Árboles de derivación

Existe una representación de árbol para las derivaciones. El árbol, conocido como "árbol de derivación", cuando se emplea en un compilador, es la estructura de datos que representa el programa fuente. En un compilador, la estructura del

árbol del programa fuente facilita la traducción del programa fuente a código ejecutable permitiendo que el proceso de traducción sea realizado por funciones naturales recursivas.

5.2.1 Construcción de los árboles de derivación

Sea G = (V, T, P, S) una gramática. Los árboles de derivación para G son aquellos árboles que cumplen las condiciones siguientes:

l. Cada nodo interior (con hijo/s) está etiquetado con una variable de V.

2. Cada hoja está etiquetada bien con una variable, un símbolo terminal o ε. Sin embargo, si la hoja está etiquetada con ε, entonces tiene que ser el único hijo de su padre.

3. Si un nodo interior está etiquetado como A y sus hijos están etiquetados como: X1, X2,…, Xk respectivamente, comenzando por la izquierda, entonces A → X1X2…Xk es una producción de P. Observe que el único caso en que una de las X puede reemplazarse por ε es cuando es la etiqueta del único hijo y A→ε es una producción de G.

Ejemplo 5.9. Árbol de derivación que utiliza la gramática del ejemplo 5.5, que utiliza las reglas de producción E → E + E y E → I.

Ejemplo 5.10. Árbol de derivación que usa la gramática de los palíndromos, que usa las producciones P → 0P0, P → 1P1, P → ε.

5.2.2 Resultado de un árbol de derivación

Si nos fijamos en las hojas de cualquier árbol de derivación y las concatenamos empezando por la izquierda, obtenemos una cadena denominada resultado del árbol, que siempre es una cadena que se deriva de la variable raíz. Aquellos árboles de derivación tales que: el resultado es una cadena terminal, es decir, todas las hojas están etiquetadas con un símbolo terminal o con ε, y la raíz está etiquetada con el símbolo inicial, son los árboles de derivación cuyos resultados son cadenas pertenecientes al lenguaje de la gramática subyacente.

Ejemplo 5.11. Árbol con una cadena terminal como resultado y el símbolo inicial en la raíz, basado en la gramática de expresiones del ejemplo 5.5, y cuyo resultado es la cadena a * (a + b00). Este árbol de derivación es una representación de dicha derivación.

5.2.3 Inferencia, derivaciones y árboles de derivación

Dada una gramática G = (V, T, P, S), las siguientes afirmaciones son equivalentes:

1. La inferencia recursiva determina que la cadena terminal w pertenece al lenguaje de la variable A.

2. A w.

3. A w.

4. A w.

5. Existe un árbol de derivación cuya raíz es A y cuyo resultado es w.

Excepto para el uso de la inferencia recursiva, que sólo hemos definido para cadenas terminales, todas las demás condiciones también son equivalentes si w es una cadena que contiene variables.

La siguiente figura muestra un esquema de demostración de todas estas equivalencias; cada arco del diagrama indica que existe un teorema que establece que si w cumple la condición en la cola del arco, entonces también la cumple en el origen del mismo.

Teorema 5.12. Sea G = (V, T, P, S) una GIC. Si el procedimiento de la inferencia recursiva nos dice que la cadena terminal w pertenece al lenguaje de la variable A, entonces existe un árbol de derivación con raíz A y resultado w.

Teorema 5.14, 5.16. Sea G = (V, T, P, S) una GIC y supongamos que existe un árbol de derivación con una raíz etiquetada con la variable A y resultado w, donde w pertenece a T*.

Entonces existe una derivación más a la izquierda A w en la gramática G.

Entonces existe una derivación más a la derecha A w en la gramática G.

Teorema 5.18. Sea G = (V, T, P, S) una GIC, y supongamos que existe una derivación A w, donde W pertenece a T*.

Entonces el procedimiento de inferencia recursiva aplicado a G determina que w pertenece al lenguaje de la variable A.

5.3 Aplicaciones de las gramáticas independientes del contexto

Aunque concebidas inicialmente para intentar describir los lenguajes naturales por N. Chomsky, posteriormente las GIC se emplearon como una forma de describir instancias de conceptos definidos recursivamente en las ciencias de la computación. Unos de estos usos son:

1. Las gramáticas se utilizan para describir lenguajes de programación. Lo más importante es que existe una forma mecánica de convertir la descripción del lenguaje como GIC en un analizador sintáctico, el componente del compilador que descubre la estructura del programa fuente y representa dicha estructura mediante un árbol de derivación.

2. El desarrollo del XML, del cual una de sus partes fundamentales, el DTD (Document Type Definition) principalmente es una gramática independiente del contexto que describe las etiquetas permitidas y las formas en que dichas etiquetas pueden anidarse.

5.3.1 Analizadores sintácticos

Muchos aspectos de un lenguaje de programación tienen una estructura que puede describirse mediante expresiones regulares. Sin embargo, también hay algunos aspectos importantes de los lenguajes de programación típicos que no pueden representarse sólo mediante expresiones regulares.

Ejemplo 5.19. Los lenguajes típicos emplean paréntesis y/o corchetes de forma equilibrada y anidada. Es decir, hay que emparejar un paréntesis abierto por la izquierda con el paréntesis de cierre que aparece inmediatamente a su derecha, eliminar ambos y repetir el proceso. Si al final se eliminan todos los paréntesis, entonces la cadena estaba equilibrada y si no se pueden emparejar los paréntesis de esta manera, entonces es que estaba desequilibrada. Una gramática Gbal = ({B}, {(, )} , P, B) genera todas las cadenas de paréntesis equilibrados (y únicamente éstas), donde P consta de las producciones: B

→ BB | (B) | ε. El conjunto de cadenas de paréntesis equilibrados no es un lenguaje regular, como puede demostrarse por el lema del bombeo, considerando la cadena equilibrada w = (n)n, y descomponiéndola en xyz, y al quedarnos con xz, al menos perderíamos un paréntesis abierto, con lo que la cadena no estaría equilibrada y no pertenecería al lenguaje.

Muchos aspectos de un lenguaje de programación típico se comportan como los paréntesis equilibrados, como los elementos que marcan el principio y el final de los bloques de código, como begin y end en Pascal, o las llaves {} en C.

Existe un caso que se presenta ocasionalmente en el que los "paréntesis" pueden ser equilibrados, pero también pueden existir paréntesis abiertos no equilibrados. Un ejemplo sería el tratamiento de if y else en C. Puede existir una cláusula if desequilibrada o equilibrada por la cláusula else correspondiente. Una gramática que genera las secuencias posibles de if y else (representadas por i y e, respectivamente) es: S → ε | SS | iS | iSe.

Ejemplo 5.20. Consideremos la cadena iee. La primera e se corresponde con la i que haya su izquierda. Ambas se eliminan, dejando la cadena e. Puesto que hay otro símbolo e, continuamos. Sin embargo, no hay una i a su izquierda, por lo que iee no pertenece al lenguaje, lo mismo que ocurre en C, donde no podemos tener más instrucciones else que if. Veamos otro ejemplo, consideremos iieie. La primera e se corresponde con la i situada a su izquierda, y queda iie. Emparejando la e que queda con la i de su izquierda, queda i. Ya no hay más elementos e, por lo que la prueba se ha pasado con éxito.

5.4 Ambigüedad en gramáticas y lenguajes

Como hemos visto, las aplicaciones de las GIC a menudo confían en la gramática para proporcionar la estructura de los archivos. La suposición tácita es que una gramática determina de manera unívoca la estructura para cada cadena del lenguaje. Sin embargo, veremos que no todas las gramáticas proporcionan estructuras únicas. Cuando una gramática falla en proporcionar estructuras únicas, a veces es posible rediseñar la gramática para hacer que la estructura sea única para cada cadena del lenguaje. Sin embargo, existen algunos lenguajes independientes del contexto que son "inherentemente ambiguos"; cualquier gramática para dicho lenguaje proporciona más de una estructura a algunas cadenas del lenguaje.

5.4.1 Gramáticas ambiguas

La gramática de la construcción de expresiones aritméticas nos permite generar expresiones con cualquier secuencia de los operadores * y + y las producciones E → E + E | E * E nos permiten generar estas expresiones en cualquier orden que elijamos.

Ejemplo 5.25. Consideremos la forma sentencial E + E * E. Existen dos derivaciones de E: 1. E E + E E + E * E; 2. E E * E E + E * E.

En la derivación (1), la segunda E es reemplazada por E * E, mientras que en la derivación (2), la primera E es reemplazada por E + E.

La diferencia entre estas dos derivaciones es significativa. En lo que se refiere a la estructura de las expresiones, la derivación (1) establece que la segunda y la tercera expresiones se multiplican, y el resultado se suma a la primera expresión, mientras que la derivación (2) suma las dos primeras expresiones y multiplica el resultado por la tercera. La primera de ellas, y no la segunda, se corresponde con nuestra idea de cómo agrupar correctamente las expresiones aritméticas.

Dado que la gramática proporciona dos estructuras diferentes para cualquier cadena de símbolos terminales que se haya derivado reemplazando las tres expresiones de E + E * E por identificadores, vemos que esta gramática no es adecuada para proporcionar una estructura única. En concreto, puede proporcionar cadenas con la agrupación correcta como expresiones aritméticas, pero también proporciona agrupaciones incorrectas. Para utilizar esta gramática de expresiones en un compilador, tendríamos que modificarla de manera que sólo proporcionara las agrupaciones correctas.

Por otro lado, la mera existencia de diferentes derivaciones para una cadena (en oposición a diferentes árboles de derivación) no implica que la gramática sea defectuosa.

Ejemplo 5.26. Utilizando la misma gramática de expresiones, vamos a determinar que la cadena a + b tiene muchas derivaciones diferentes, por ejemplo: 1. E E + E I + E a + E a + I a + b; 2. E E + E E + I E + b

I + b a + b. Sin embargo, no existe ninguna diferencia real entre las estructuras proporcionadas por estas derivaciones; ambas especifican que a y b son identificadores y que sus valores deben sumarse. De hecho, ambas derivaciones dan como resultado el mismo árbol de derivación.

Los dos ejemplos anteriores sugieren que no es la multiplicidad de derivaciones lo que causa la ambigüedad, sino la existencia de dos o más árboles de derivación. Por tanto, decimos que una GIC G = (V, T, P, S) es ambigua si existe al menos una cadena w de T* para la que podemos encontrar dos árboles de derivación diferentes, teniendo cada uno de ellos una raíz S y un resultado w. Si cada una de las cadenas tiene como máximo un árbol de derivación en la gramática, entonces la gramática es no ambigua.

Existen algunas derivaciones ambiguas que pueden ser transformadas para dejar de serlo, mientras que otras son “inherentemente” ambiguas.

5.4.3 Derivaciones más a la izquierda como forma de expresar la ambigüedad

Las derivaciones no son necesariamente únicas, incluso aunque la gramática no sea ambigua; no obstante, en una gramática no ambigua, tanto las derivaciones más a la izquierda como las derivaciones más a la derecha serán únicas.

Teorema 5.29. Para cada gramática G = (V, T, P, S) y cadena w de T*, w tiene dos árboles de derivación distintos si y sólo si w tiene dos derivaciones a la izquierda distintas desde S.

5.4.4 Ambigüedad inherente

Un lenguaje independiente del contexto L se dice que es inherentemente ambiguo si todas sus gramáticas son ambiguas. Si una sola gramática de L es no ambigua, entonces L no es un lenguaje ambiguo.

El lenguaje L = {anbncmdm | n ≥ 1, m ≥ 1} U {anbmcmdn | n ≥ 1, m ≥ 1} es inherentemente ambiguo. Una gramática sería:

5.5 Resumen del Capítulo 5

+ Gramáticas independientes del contexto. Una GIC es una forma de describir lenguajes mediante reglas recursivas denominadas producciones. Una GIC consta de un conjunto de variables, un conjunto de símbolos terminales y una variable inicial, así como de producciones. Cada producción consta de una variable de cabeza y un cuerpo formado por una cadena de cero o más variables y/o símbolos terminales.

+ Derivaciones y lenguajes. Partiendo del símbolo inicial, derivamos las cadenas terminales sustituyendo de forma repetida una variable por el cuerpo de una producción cuya cabeza sea dicha variable. El lenguaje de la GIC es el conjunto de las cadenas terminales que podemos derivar de esta manera y se dice que es un lenguaje independiente del contexto.

+ Derivaciones más a la izquierda y más a la derecha. Si siempre sustituimos la variable más a la izquierda (más a la derecha) en una cadena, entonces la derivación resultante es una derivación más a la izquierda (más a la derecha). Toda cadena de un lenguaje de una GIC tiene al menos una derivación más a la izquierda y una derivación más a la derecha.

+ Formas sentenciales. Cualquier paso en una derivación da lugar una cadena de variables y/o símbolos terminales. Si parte del símbolo inicial denominamos a la cadena forma sentencial. Si la derivación es más a la izquierda (o más a la derecha), entonces la cadena es una forma sentencial por la izquierda (o por la derecha).

+ Árboles de derivación. Un árbol de derivación es un árbol que muestra los fundamentos de una derivación. Los nodos internos se etiquetan con variables y las hojas se etiquetan con símbolos terminales o ε. Para cada nodo interno, tiene que existir una producción tal que la cabeza de la misma es la etiqueta del nodo y las etiquetas de sus hijos, leídas de izquierda a derecha, forman el cuerpo de dicha producción.

+ Equivalencia de árboles de derivación y derivaciones. Una cadena terminal pertenece al lenguaje de una gramática si y sólo si es el resultado de al menos un árbol de derivación. Luego la existencia de derivaciones más a la izquierda, derivaciones más a la derecha y árboles de derivación son condiciones equivalentes que definen de forma exacta las cadenas pertenecientes al lenguaje de una GIC.

+ Gramáticas ambiguas. Para algunas GIC, es posible determinar una cadena terminal con más de un árbol de derivación, o lo que es lo mismo, más de una derivación más la izquierda o más de una derivación más a la derecha. Una gramática así se dice que es una gramática ambigua.

+ Eliminación de la ambigüedad. Para muchas gramáticas útiles, como aquellas que describen la estructura de programas en un lenguaje de programación típico, es posible determinar una gramática no ambigua que genere el mismo lenguaje. Lamentablemente, la gramática no ambigua frecuentemente es más compleja que la gramática ambigua más simple para el lenguaje. También existen algunos lenguajes independientes del contexto, habitualmente bastante artificiales, que son inherentemente ambiguos, lo que significa que cualquier gramática de dicho lenguaje es ambigua.

+ Analizadores sintácticos. Las gramáticas independientes del contexto describen un concepto fundamental para la implementación de compiladores y otros procesadores de lenguajes de programación.

+ DTD, definiciones de tipos de documentos. El estándar XML para compartir información a través de documentos Web utiliza una notación, conocida como DTD, que permite describir la estructura de dichos documentos mediante el anidamiento de etiquetas semánticas dentro del documento. Las DTD son en esencia gramáticas independientes del contexto cuyo lenguaje es una clase de documentos relacionados.