7_LyGLC - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

18 
 
LENGUAJES Y 
GRAMÁTICAS 
LIBRES DE 
CONTEXTO 
 
 
19 
 
Introducción 
Las gramáticas libres de contexto (en adelante G.L.C) son una herramienta para describir 
un conjunto de lenguajes más amplio que el descrito por las expresiones regulares. Una de 
sus características principales es que pueden describir estructuras recursivas. La primera 
aplicación de las G.L.C. fue en el estudio del lenguaje humano, más específicamente, en la 
descripción de las estructuras de frases y de las palabras de un lenguaje. 
Algunos otros ejemplos donde podemos encontrar el uso de las G.L.C. es en la 
caracterización y compilación de lenguajes de programación. En los compiladores e 
intérpretes, encontramos un componente, conocido como parser, que extrae los 
componentes léxicos de un texto y los reorganiza utilizando otra estructura (e.j. árboles de 
derivación) para su posterior análisis. Por otro lado, las G.L.C. también se han utilizado 
para describir formatos de documentos XML, usados para el intercambio de información 
en la web, a través de ”Esquemas XML”. 
Definición 
Las G.L.C. es una 4 − tupla (ΣN, ΣT, R, S), donde: 
1. ΣN es un conjunto finito de elementos llamados variables o símbolos no terminales 
2. ΣT es un conjunto finito de elementos, disjunto de ΣN , llamados símbolos 
terminales 
3. R es el conjunto finito de reglas, donde cada regla está compuesta de variables y 
terminales. 
4. S ∈ ΣN es la variable o símbolo inicial 
 
La estructura de las reglas de producción para esta gramática está definida por la siguiente 
expresión: 
A ::= v donde A ∈ ΣN y v ∈ (ΣN U ΣT)* 
1. La parte izquierda de la producción está formada por un único símbolo no 
terminal. 
2. No hay restricciones respecto de la parte derecha de la producción. 
3. La conversión de A en v se realiza independientemente del contexto en que se 
encuentra A, de ahí su nombre. 
 
Por lo tanto, definimos como un Lenguaje Libre de Contexto a aquellos lenguajes 
producidos por una G.L.C. 
 
 
 
20 
 
Ejemplo: 
Supóngase que queremos construir la G.L.C que genere cadenas del lenguaje: 
L = { an(ab)mbn | m, n ≥ 0 } 
La gramática para dicho lenguaje estaría dada por G1 = ({S}, {a, b}, R, S) donde R está dada 
por las siguientes reglas: 
S ::= aSb | A | ε 
A ::= abA | ab 
Algunas de las cadenas aceptadas serán: abab, aaabbb, aababb y ε 
 
Ejemplo: 
Un ejemplo más comúnmente usado es el de las expresiones algebraicas. Con la siguiente 
G.L.C podremos construir el lenguaje de las expresiones algebraicas que contengan 
operaciones de suma, multiplicación y su combinación. 
G2 = ({⟨EXPR⟩, ⟨TERMINO⟩, ⟨FACTOR⟩}, {a,+,X,(,)}, R, ⟨EXPR⟩) donde R está dada por las 
siguientes reglas: 
⟨EXPR⟩ ::= ⟨EXPR⟩ + ⟨TERMINO⟩ | ⟨TERMINO⟩ 
⟨TERMINO⟩ ::= ⟨TERMINO⟩ X ⟨FACTOR⟩ | ⟨FACTOR⟩ 
⟨FACTOR⟩ ::= ( ⟨EXPR⟩ ) | a 
 
Dos de las cadenas que construye dicha gramática son : a + a X a ó (a + a) X a 
Diseño de gramáticas libres de contexto 
El diseño y construcción de gramáticas es una cuestión de práctica y creatividad. En 
general construir gramáticas es más difícil que construir autómatas, ya que estamos 
acostumbrados a programar máquinas que realicen tareas específicas más que diseñar 
una gramática. A continuación se presentan algunas sugerencias para hacer más simple la 
construcción de G.L.C. 
 
 
 
21 
 
Cadenas envueltas y lenguajes recursivos 
Existen ciertos lenguajes libres de contexto que están formados por cadenas envueltas 
entre otras dos subcadenas; de tal forma que, es necesario que el lenguaje recuerde una 
cantidad ilimitada de información de una de las subcadenas para verificar que 
corresponda con la otra subcadena. 
Ejemplo: 
Un ejemplo de este tipo de lenguajes es el siguiente: 
L={0n1n | n ≥ 0} 
En este lenguaje la gramática necesita recordar el número de 0′s para posteriormente 
verificar que corresponda con el número de 1′s. En las gramáticas libres de contexto se 
puede manejar esta situación utilizando la regla. 
R ::= uRv
 
que genera cadenas en las que la porción contenida de u′s corresponde a la porción 
contenida de v′s. 
Dividir el problema 
En ocasiones los lenguajes que se pretenden describir con una G.L.C. resultan ser la unión 
de dos lenguajes más simples. Dividir el lenguaje en dos o más, construir una gramática 
para cada uno y finalmente unirlos, podría facilitar la construcción de la G.L.C. Las 
gramáticas individuales puedes ser mezcladas para formar la gramática del lenguaje 
original creando una nueva regla que unifique a las demás. 
S ::= S1|S2|...|Sk 
Ejemplo: 
Sea el lenguaje definido por:
L={0n1n |n≥0}∪{1n0n |n≥0} 
Primero se construyen las gramáticas para cada de los elementos de la unión. La 
gramática del lenguaje {0n1n | n ≥ 0} es: 
S1 ::= 0S11 | ε 
La gramática para el lenguaje {1n0n | n ≥ 0} es: 
S2 ::= 1S20 | ε 
 
 
22 
 
Por último agregamos una nueva regla S ::= S1 | S2 para obtener una gramática como la 
siguiente: 
S ::= S1 | S2 
S1 ::= 0S11 | ε 
S2 ::= 1S20 | ε 
 
 
Ambigüedad 
Una gramática es ambigua cuando, al derivar una cadena w, obtenemos dos o más 
árboles de derivación. 
Ejemplo: 
Considere la cadena 𝑎 + 𝑏 ∗ 𝑎. Existen dos árboles de derivación a partir de E: 
 
(a) 𝐸 ⇒ 𝐸 + 𝐸 ⇒ 𝐴 + 𝐸 ⇒ 𝑎 + 𝐸 ⇒ 𝑎 + 𝐸 ∗ 𝐸 ⇒ 𝑎 + 𝐴 ∗ 𝐸 ⇒ 𝑎 + 𝑏 ∗ 𝐸 ⇒ 𝑎 + 𝑏 ∗ 𝐴 
 ⇒ 𝑎 + 𝑏 ∗ 𝑎 
(b) 𝐸 ⇒ 𝐸 ∗ 𝐸 ⇒ 𝐸 + 𝐸 ∗ 𝐸 ⇒ 𝐴 + 𝐸 ∗ 𝐸 ⇒ 𝑎 + 𝐸 ∗ 𝐸 ⇒ 𝑎 + 𝐴 ∗ 𝐸 ⇒ 𝑎 + 𝑏 ∗ 𝐸 
 ⇒ 𝑎 + 𝑏 ∗ 𝐴 ⇒ 𝑎 + 𝑏 ∗ 𝑎 
 
 
23 
 
La diferencia entre estas dos derivaciones es significativa. En lo que se refiere a la 
estructura de las expresiones, la derivación (a) 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 (b) suma las dos primeras expresiones y multiplica el resultado por la tercera. 
Más concretamente, la primera derivación sugiere que 1 + 2 ∗ 3 deberían agruparse como 
1 + (2 ∗ 3) = 7, mientras que la segunda derivación dice que la misma expresión debería 
agruparse como (1 + 2) ∗ 3 = 9. Obviamente, 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 utilizada 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, aunque puede proporcionar cadenas con 
la agrupación correcta como expresiones aritméticas, 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 ambigua. A 
continuación se proporciona un ejemplo. 
(a) 𝐸 ⇒ 𝐸 + 𝐸 ⇒ 𝐼 + 𝐸 ⇒ 𝑎 + 𝐸 ⇒ 𝑎 + 𝐼 ⇒ 𝑎 + 𝑏 
(b) 𝐸 ⇒ 𝐸 + 𝐸 ⇒ 𝐸 + 𝐼 ⇒ 𝐼 + 𝐼 ⇒ 𝐼 + 𝑏 ⇒ 𝑎 + 𝑏 
 
 
 
 
 
 
 
(a) (b) 
E 
E E 
+ 
I I 
a b 
E 
E E 
+ 
I I 
a b 
 
 
24 
 
Se dice que un lenguaje independiente de contexto L es inherentemente ambiguo si todas 
sus gramáticas son ambiguas. Si una sola gramática nos es ambigua, entonces L no es un 
lenguaje ambiguo. 
Formas Normales 
Una forma normal es un intento de estandarizar las producciones de una G.L.C. y 
conseguir que todas tengan una apariencia similar. Una G.L.C. puede ser transformada en 
una equivalente (que genera el mismo lenguaje) en Forma Normal de Chomsky (FNC) o 
Forma Normal de Greibach. 
Forma Normal de Chomsky (FNC) 
Una de las características principales de la FNC es que el árbol de derivación resultante es 
binario, excepto en las hojas. Esto resulta útil al momento de diseñar programaspara leer 
y ordenar árboles. 
Una GLC se considera en FNC si todas sus reglas de producción tienen alguna de las 
siguientes formas: 
1. 𝐴 → 𝐵𝐶 donde A, B, C son variables No-Terminales. 
2. 𝐴 → 𝑎 donde A es No-Terminal y a es Terminal. 
Ejemplo: 
S→ZS | AB 
A→ CA| b 
B→CB | CA 
C→a 
Z→z 
Cualquier GLC se puede transformar a FNC de acuerdo a lo siguiente: 
A. Simplificación o limpieza de gramáticas 
 
El orden seguro para realizar dicha simplificación es el siguiente: 
1. Eliminar 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖𝑜𝑛𝑒𝑠 − 𝜀 
2. Eliminar producciones unitarias 
3. Eliminar los símbolos inútiles 
 
1. Eliminación de producciones − ε 
Considere la gramática 
 
 
25 
 
S → AB
 
A → aAA | ε 
B → bBB | ε 
En primer lugar, determinamos las reglas que tienen en su parte derecha 𝜀 como único 
símbolo. En el ejemplo podemos identificar las dos siguientes reglas: 
A → ε 
B → ε 
Para eliminar estas producciones es necesario localizar las producciones que tienen a A y B 
en la parte derecha. Tomamos primero la regla A → 𝜀 y las reglas que contienen A del lado 
derecho: 
S → AB
 
A → aAA 
Para cada una de ellas, vamos a añadir una producción equivalente por cada una de las 
posibles combinaciones cuando A toma el valor de 𝜀. 
S → AB | B
 
A → aAA | aA | aA | a 
Para el caso similar de la regla B → 𝜀 identificamos las reglas que la contienen en su parte 
derecha: 
S → AB | B 
B → bBB 
Para cada una de ellas, vamos a añadir una producción equivalente por cada una de las 
posibles combinaciones cuando B toma el valor de 𝜀. 
S → AB | B | A | ε 
 
B → bBB | bB | bB | b 
La nueva gramática sin 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖𝑜𝑛𝑒𝑠 − 𝜀, queda como sigue: 
S → AB | A | B
| ε 
 
 
26 
 
A → aAA | aA | a 
B → bBB | bB | b 
Ahora considere la siguiente gramática: 
𝑆 → 𝐴𝑆𝐵 | 𝜀 
𝐴 → 𝑎𝐴𝑆 | 𝑎 
𝐵 → 𝑆𝑏𝑆 |𝐴 | 𝑏𝑏 
La producción S → 𝜀 no puede eliminarse de ninguna gramática ya que es imprescindible 
si se pretende que el lenguaje generado contenga la palabra vacía, por lo tanto, la 
gramática anterior sin 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖𝑜𝑛𝑒𝑠 − 𝜀 queda exactamente igual. 
2. Eliminación de producciones unitarias o unarias 
Una producción unitaria es una producción de la forma A → B, donde A y B son símbolos 
no terminales. Las producciones unitarias pueden complicar determinadas 
demostraciones e introducir también pasos adicionales en las derivaciones que 
técnicamente no tienen por qué incluir. 
 
Considere las siguientes reglas: 
I → a | b | Ia | Ib | I0 | I1 
F → I|(E)
 
T → F|T∗F
 
E → T|E+T 
Primero identificamos las producciones unarias, en este caso: 
F → I 
T → F 
E → T 
Para eliminar estas producciones, debemos añadir producciones equivalentes en donde se 
reemplacen los símbolos no terminales que vamos eliminando. Siguiendo el ejemplo 
vamos a eliminar la regla F → I reemplazando el símbolo no terminal I por todos los 
valores en los que deriva el mismo: 
F→ a | b | Ia | Ib | I0 | I1 
Eliminado la regla T → F tendríamos: 
 
 
27 
 
T→ a | b | Ia | Ib | I0 | I1 | (E) 
Ahora, eliminando la regla E → T tenemos: 
E→ | b | Ia | Ib | I0 | I1 | (E) | T∗F 
La nueva gramática sin 𝑝𝑟𝑜𝑑𝑢𝑐𝑐𝑖𝑜𝑛𝑒𝑠 𝑢𝑛𝑖𝑡𝑎𝑟𝑖𝑎𝑠, queda como sigue: 
I → a | b | Ia | Ib | I0 | I1 
F→ a | b | Ia | Ib | I0 | I1 |(E) 
T→ a | b | Ia | Ib | I0 | I1 | (E) | T∗F
 
E→ a | b | Ia | Ib | I0 | I1 | (E) | T∗F | E+T 
 
3. Eliminación de producciones inútiles 
Para eliminar símbolos y producciones inútiles: 
1. Símbolos no generativos: eliminar los símbolos no terminales a partir de los cuales 
no puede derivarse ninguna cadena de símbolos terminales y las producciones en 
las que aparezcan. 
2. Símbolos inaccesibles: eliminar aquellos símbolos que no sean alcanzables desde el 
símbolo inicial, y las producciones en las que aparecen. 
 
Ejemplo: 
Considere la gramática 
𝑆 → 𝐴𝐵 | 𝑎 | 𝑎𝐶 
𝐴 → 𝑏 
𝐶 → 𝑐 
Todos los símbolos excepto B son generativos. S genera a, A genera b y C genera c. Si 
eliminamos el símbolo B, tenemos que eliminar la producción S → AB, quedando la 
gramática: 
𝑆 → 𝑎 | 𝑎𝐶 
𝐴 → 𝑏 
𝐶 → 𝑐 
Ahora comprobamos que S y C son accesible, ya que podemos llegar a ellos desde el 
símbolo inicial. Sin embargo A es inaccesible quedando la gramática: 
 
 
28 
 
𝑆 → 𝑎 | 𝑎𝐶 
𝐶 → 𝑐 
Estas producciones generan el lenguaje {a, ac}, igual que el lenguaje de la gramática 
original. 
B. Adecuar la forma de las reglas de producción 
 
Una vez que se realizó la simplificación de la gramática, para que ésta sea considerada en 
FNC es necesario adecuar las reglas de producción a la forma correspondiente. 
El principal objetivo es conseguir que: 
1. Conseguir que todas las cadenas (parte derecha de la producción) de longitud 2 o 
mayor estén formados sólo por No-Terminales. 
2. Descomponer todas las cadenas de longitud 3 o mayores en una cascada de 
producciones, donde cada producción estará formada por cadenas con dos 
símbolos No-Terminales 
 
El algoritmo para el punto 1 es el siguiente: para todo símbolo terminal a que aparezca en 
una cadena de longitud 2 o superior, creamos un nuevo símbolo No-Terminal, por ejemplo 
A, que deriva en a (A → a). Ahora empleamos A en lugar de a en cualquier lugar que 
aparezca esta última dentro de una cadena de longitud 2 o superior. En este punto, toda 
producción tendrá una parte derecha formada por un sólo símbolo terminal o por al 
menos dos No-Terminales. 
Para el paso 2, tenemos que descomponer dichas producciones A → B1 B2 · · · Bk , para k ≥ 
3, en un grupo de producciones con dos No-Terminales en cada cadena. Introducimos k−2 
nuevos simbolos No-Terminales, C1,C2,…,Ck−2. La producción original se reemplaza por las 
k – 1 producciones: 
A → B1C1, C1 → B2C2,…,Ck−3 → Bk−2Ck−2, Ck−2 → Bk−1Bk 
Ejemplo: 
Convertir la siguiente gramática libre de contexto (simplificada) en otra equivalente en 
FNC: 
𝐺 = ({𝐴, 𝐵 𝐶, 𝑆, 𝐷, 𝐸}, {𝑥, 𝑦, 𝑧}, 𝑆, 𝑃) 
𝑃 = {S→ 𝑧𝑆 | 𝐴𝐵 
𝐴 → 𝐶𝐸 | 𝐶𝐷𝐸 | 𝑧𝐷 
 
 
29 
 
𝐵 → 𝐴𝐵𝐴 
𝐶 → 𝐵𝐴 | 𝑥𝐴 | 𝑦𝑧 
𝐷 → 𝑥𝑦𝑧 
𝐸 → 𝐸𝐸 | 𝑧𝐵 } 
Paso 1: Conseguir que todas las cadenas de longitud 2 o mayor, estén formadas sólo de 
elementos No-Terminales. 
𝑆 → 𝑍𝑆 | 𝐴𝐵 
𝐴 → 𝐶𝐸 | 𝐶𝐷𝐸 | 𝑍𝐷 
𝐵 → 𝐴𝐵𝐴 
𝐶 → 𝐵𝐴 | 𝑋𝐴 | 𝑌𝑍 
𝐷 → 𝑋𝑌𝑍 
𝐸 → 𝐸𝐸 | 𝑍𝐵 
𝑍 → 𝑧 
𝑋 → 𝑥 
𝑌 → 𝑦 
Paso 2: Descomponer todas las cadenas de longitud 3 o mayores en una cascada de 
producciones, donde cada producción estará formada por cadenas con dos símbolos No-
Terminales. 
𝑆 → 𝑍𝑆 | 𝐴𝐵 
𝐴 → 𝐶𝐸 | 𝐶𝑀 | 𝑍𝐷 
𝑀 → 𝐷𝐸 
𝐵 → 𝐴𝑁 
𝑁 → 𝐵𝐴 
𝐶 → 𝐵𝐴 | 𝑋𝐴 | 𝑌𝑍 
𝐷 → 𝑋Ñ 
Ñ → 𝑌𝑍 
𝐸 → 𝐸𝐸 | 𝑍𝐵 
𝑌 → 𝑦 
𝑍 → 𝑧 
𝑋 → 𝑥