Gramática independiente del contexto

Para la formalización matemática de las técnicas de análisis sintáctico de los Lenguajes de programación se utilizan las gramáticas independientes del contexto y las regulares, porque son las que ofrecen mayor simplicidad para describir su lenguaje y, por otro lado, dan lugar a algoritmos de orden lineal para el análisis.

[!note] Definición Se dice que una gramática ($V_N, V_T$, P, S) es independiente del contexto (GIC) si toda regla en P tiene la forma A → β con A ∈ VN y β ∈ (VN ∪ VT)*. Si la cadena ε pertenece al lenguaje generado, se permite la regla S → ε y en este caso S no puede aparecer como parte derecha de ninguna regla.

Como a partir de este punto solamente se tratarán gramáticas independientes del contexto o la subclase de estas, o sea, las gramáticas regulares, se hará referencia a ellas simplemente como gramáticas, sin especificar cada vez que son gramáticas independientes del contexto.

Convenio notacional

La referencia explícita de una gramática mediante sus cuatro elementos recarga demasiado su notación. Por ello, en la mayoría de los textos se emplean dos notaciones abreviadas que, implícitamente, indican cuáles son los terminales y los no terminales, sin necesidad de expresarlo de manera explícita.

Primera notación

  • Los no terminales se denotan por letras mayúsculas.
  • Los terminales se denotan por letras minúsculas y el resto de los símbolos, tales como: +, -, *, /, (, ), etc.

Notación de Backus

  • Los no terminales se escriben como <clase>, <instruccion>, etc.
  • Los terminales son los símbolos restantes.

En ambas notaciones: - Se considera implícitamente que el símbolo de partida es la parte izquierda de la primera regla que se escribe - Para abreviar la escritura, todas las reglas que tienen la misma parte izquierda se denotan como:

  A → α₁ | α₂ | ... | αₙ

En lugar de escribirlas separadamente:

A → α₁
A → α₂
...
A → αₙ

Diseño de gramáticas independientes del contexto

El problema del diseño de gramáticas independientes del contexto consiste en proponer, dado un lenguaje L, una gramática G tal que su lenguaje generado es exactamente L.

[!note] Corrección y completitud - Decimos que una gramática G es correcta con respecto al lenguaje dado L cuando el lenguaje generado por G no contiene palabras que estén fuera de L, es decir, L(G) ⊆ L - Decimos que G es completa cuando G es capaz de generar al menos las palabras de L, es decir, L ⊆ L(G)

Al diseñar gramáticas es posible cometer dos clases de errores:

  1. Que "sobren palabras", esto es, que la gramática genere algunas palabras que no debería generar. En este caso, la gramática sería incorrecta.

  2. Que "falten palabras", esto es, que haya palabras en el lenguaje considerado para las que no hay ninguna derivación. En este caso, la gramática sería incompleta.

Aun cuando no hay métodos tan sistemáticos para diseñar las gramáticas independientes del contexto como los que hemos visto para diseñar expresiones regulares o autómatas finitos, es posible al menos: - Reutilizar gramáticas ya conocidas para modificarlas y ajustar el lenguaje generado - Combinar varias en una sola

Este último método es particularmente eficaz y lo exploraremos en detalle a continuación.

Adaptación de Gramáticas independientes del contexto

Muchas veces es posible hacer modificaciones sencillas a una gramática conocida para obtener la del lenguaje requerido.

[!example] Ejemplo de adaptación Supongamos que queremos obtener una gramática que genere el lenguaje {aⁿbᵐ|n > m}. Una buena idea sería partir de una sencilla gramática que genera el lenguaje similar {aⁿbⁿ} y cuyas reglas son: 

S → aSb
S → ab

Observamos que es necesario prever alguna regla para producir cualquier cantidad de aes antes de las bes, pues hay palabras como aaaab que necesitan ser generadas. Para esto proponemos una regla S → aS.

Aplicando iteradamente esta regla podemos producir palabras como la mencionada: 

S ⇒ aS ⇒ aaS ⇒ aaaS ⇒ aaaab

Sin embargo, aun añadiendo esta regla subsiste el problema de que podríamos generar palabras incorrectas, pues cualquier palabra con igual cantidad de aes y bes se genera utilizando únicamente las reglas de la gramática para {aⁿbⁿ}.

Hay al menos dos maneras de solucionar este problema:

  1. Solución con símbolo inicial nuevo:
  2. Podemos pensar en que la a que asegura que haya más aes que bes se produzca al inicio de la derivación
  3. Mediante la inclusión de un nuevo símbolo inicial, sea S₀, que produce aS, mediante una regla S₀ → aS

  4. Por ejemplo, generaríamos aaaab del modo siguiente: 

    S₀ ⇒ aS ⇒ aaS ⇒ aaaS ⇒ aaaab

  5. Solución modificando regla final:

  6. Otra manera es producir la a que garantiza más aes que bes al final de la derivación
  7. Remplazando la regla S → ab por S → a
  8. La misma palabra se derivaría como: 
    S ⇒ aS ⇒ aaS ⇒ aaaSb ⇒ aaaab

Gramática independiente del contexto para unión de lenguajes

Muchos lenguajes pueden ser expresados en forma útil como la unión de otros dos lenguajes, para los cuales conocemos las gramáticas que los generan.

[!example] Ejemplo de unión de lenguajes El lenguaje {aⁿbᵐ|n ≠ m} se puede expresar como la unión de los lenguajes:

{aⁿbᵐ|n ≠ m} = {aⁿbᵐ|n < m} ∪ {aⁿbᵐ|n > m}

Para cada uno de los lenguajes que se unen podemos obtener su gramática siguiendo los pasos anteriormente descritos.

[!note] Método de combinación La manera de combinar las dos gramáticas (con símbolos iniciales S₁ y S₂, respectivamente) para producir la unión de los lenguajes originales consiste en: 1. Crear un nuevo símbolo inicial S (S₁ y S₂ dejan de ser iniciales) 2. Tomar las reglas tanto de una gramática como de otra 3. Añadir dos nuevas reglas, S → S₁ y S → S₂

A partir del primer paso, se continúa la derivación utilizando alguna de las dos gramáticas originales, sin utilizar las reglas de la otra.

[!important] Requisito Para garantizar que no haya interferencias entre las gramáticas, se supone que las dos gramáticas originales no tienen ninguna variable en común.

[!note] Definición formal Definimos formalmente la gramática que genera la unión de lenguajes de la manera siguiente. Sean G₁ = (VN₁, VT₁, P₁, S₁) y G₂ = (VN₂, VT₂, P₂, S₂) dos GIC; se puede suponer, sin pérdida de generalidad, que las variables de G₁ y G₂ son disjuntas. La GIC que genera L(G₁) ∪ L(G₂) es:

G = (VN₁ ∪ VN₂ ∪ {S}, VT₁ ∪ VT₂, P₁ ∪ P₂ ∪ {S → S₁, S → S₂}, S)

Mezcla de gramáticas

En ocasiones es necesario combinar dos gramáticas, de una manera similar a la unión que acabamos de presentar, pero permitiendo que las gramáticas que se van a combinar tengan un mismo símbolo inicial. Llamamos a esto mezcla de gramáticas.

[!example] Ejemplo 8 Diseñar una GIC para el lenguaje {aⁿbᵐ, n ≤ m ≤ 2n}, esto es, donde la cantidad de bes es mayor o igual que la de aes, pero menor o igual que el doble de estas.

Las siguientes son palabras del lenguaje: aabbb, aabb y aabbbb.

Una solución es "mezclar" una GIC para el lenguaje {aⁿbⁿ} con otra para el lenguaje {aⁿb²ⁿ}, cuyas GIC son, respectivamente:

{aⁿbⁿ}           {aⁿb²ⁿ}
1. S → aSb       3. S → aSbb
2. S → ε         4. S → ε

La GIC "mezclada" contendría simplemente la unión de todas las reglas de las dos gramáticas. Desde luego, siendo las reglas 2 y 4 idénticas, resultan en una sola regla al unir las gramáticas, pues en los conjuntos no se permite repetición.

Por ejemplo, para generar la palabra aabbb, se tendría la siguiente derivación: 

S ⇒₁ aSb ⇒₃ aaSbbb ⇒₂ aabbb

En esta derivación puede apreciarse que es posible obtener una palabra "intermedia" entre aabb y aabbbb, como es aabbb, simplemente aplicando algunas veces la regla 1 y otras, la regla 3, según se requiera para la palabra que hay que derivar.

Gramáticas independientes del contexto para concatenación de lenguajes

En ocasiones, un lenguaje L puede ser expresado como la concatenación de otros dos L₁ y L₂, esto es, L = L₁L₂.

[!example] Ejemplo de concatenación El lenguaje {aⁿbᵐ|n > m} puede ser expresado como la concatenación de aᵏ con {aⁿbⁿ}, y desde luego es fácil encontrar una gramática para aᵏ, mientras que la de {aⁿbⁿ} ya la conocemos.

Hay una manera de combinar modularmente las gramáticas de L₁ y L₂ para obtener la de L. Ya hemos obtenido la gramática de {aⁿbᵐ|n > m} por modificación de otra gramática, pero el método aquí mostrado tiene la ventaja de que es modular.

[!note] Método de concatenación Para obtener las reglas de la nueva gramática: 1. Juntamos las reglas de las originales (las cuales tienen símbolos iniciales S₁ y S₂) 2. Agregamos una nueva regla S → S₁S₂ 3. Hacemos a S el nuevo símbolo inicial

[!example] Ejemplo 9 - Prefijos palíndromos Definimos el lenguaje de los prefijos palíndromos como aquel formado por palabras que tienen una parte izquierda de más de un carácter que es palíndromo (se lee igual de izquierda a derecha que de derecha a izquierda).

Las palabras aabab, aba y aabaa son prefijos palíndromos (la última puede ser vista de dos maneras distintas como prefijo palíndromo), mientras que las palabras baa, a y abbb no lo son.

El problema parece difícil, pero podemos considerar que cada palabra de este lenguaje está formada por dos partes: 1. La parte palíndroma 2. El resto de la palabra

Dicho de otra forma, el lenguaje LPP de los prefijos palíndromos es igual a la concatenación de LP y LR, donde: - LP es el lenguaje de los palíndromos - LR genera la parte restante de las palabras

El lenguaje de los palíndromos en {a, b} tiene una gramática muy simple: 

S → aSa
S → bSb
S → a     (palíndromos impares)
S → b     (palíndromos impares)
S → ε     (palíndromos pares)

Por otra parte, como la "parte restante" puede ser cualquier cosa, LR es simplemente {a, b}*, que por ser regular es también un LIC, y tiene una GIC con las reglas: 

T → aT
T → bT
T → ε

La GIC de LPP es la combinación de ambas gramáticas, de acuerdo con la fórmula de concatenación dada anteriormente.