2_Gramáticas_formales - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

9 
 
GRAMÁTICAS 
FORMALES 
 
 
10 
 
Introducción 
En los lenguajes naturales, como el español, entendemos como gramática al conjunto de 
reglas que nos permiten hablar y escribir correctamente, es decir, cómo se combinan las 
palabras del lenguaje para formar oraciones. Por ejemplo: 
 
Reglas gramaticales: 
1. <oracion>::=<sujeto><predicado> 
2. <sujeto>::=<articulo><sustantivo> 
3. <predicado>::=<verbo><complemento> 
4. <predicado>::=<verbo> 
5. <articulo>::=el 
6. <articulo>::=la 
7. <sustantivo>::=perro 
8. <sustantivo>::=gata 
9. <verbo>::=corre 
10. <verbo>::=come 
11. <complemento>::=rápidamente 
12. <complemento>::=mucho 
 
El objetivo es llegar a tener una secuencia correcta de símbolos (en este caso son: el, la, 
perro, gata, etc.) partiendo de un determinado símbolo, que llamamos inicial, (<oracion> 
en el caso del ejemplo), y utilizando algunas de las reglas definidas. 
 
A estas reglas se les conoce también como producciones o reglas de derivación. Una 
producción definida sobre un alfabeto Σ, es el par ordenado de palabras (x,y) donde x,y ∈ 
Σ*, y se representa x::=y. Se dice que x es la parte izquierda de la producción y que y es la 
parte derecha. 
Definición de gramática formal 
Se llama gramática formal definida sobre un alfabeto Σ a una tupla de la forma G = ( ΣT, ΣN, 
S, P ) donde: 
 ΣT es el alfabeto de símbolos terminales 
 ΣN es el alfabeto de símbolos no terminales 
 S es el símbolo inicial de la gramática 
 P es un conjunto de producciones 
 
Hay que tener en cuenta que: 
S ∈ ΣN 
ΣN ∩ ΣT = Ø 
Σ = ΣN U ΣT 
 
 
 
 
11 
 
Ejemplo: 
G = ( {c,d}, {S,A,T}, S, P ), P= { S ::= λ | cA, A ::= d | cA | Td, T ::= Td | d } 
Clasificación de las gramáticas formales 
Noam Chomsky clasificó las gramáticas en cuatro grupos (Tipo 0, 1 ,2 y 3) donde cada uno 
contiene al siguiente. La diferencia entre cada grupo se centra en la forma de las 
producciones. La misma clasificación puede ser aplicada a los lenguajes, es decir, los 
lenguajes de tipo 0 son los generados por las gramáticas de tipo 0 y así sucesivamente. 
Gramáticas tipo 0 
También se les llama gramáticas sin restricciones o recursivamente enumerables. Las 
producciones de este tipo de gramáticas tienen la forma: 
xAy ::= v donde A ∈ ΣN, x,y,v ∈ Σ* 
Ejemplo: 
AB1::=01BC, 1A::=DE0, B::=01, D::=0C, EA::=1 
¿Qué pasa si agregamos la regla E::= λ? 
Gramáticas tipo 1 
También se les llama gramáticas dependientes del contexto. Las producciones de este tipo 
de gramáticas tienen la forma: 
xAy ::= xvy donde A ∈ ΣN, x,y ∈ Σ*, v ∈ Σ+ 
Todas las gramáticas de tipo 1 son también gramáticas de tipo 0, pero en este caso hay 
una restricción añadida y es que no debe ser decreciente, es decir, no debe contener 
producciones o reglas compresoras. 
Se dice que una producción es compresora si la longitud de su parte derecha es menor 
que la de la parte izquierda. 
 
Ejemplo: 
S::=aAB |aB, B::=Dc, CD::=CE, DE::=Dc, A::=aAC | aC, D::=b, CE::=DE, Cc::=Dcc 
Si agregamos la regla EA::=c deja de ser tipo 1 y se convierte en tipo 0, ya que esta regla es 
una regla compresora. |c| < |EA| 
¿Qué pasa si agregamos la regla E::= λ? 
Gramáticas tipo 2 
También se les llama gramáticas libres de contexto o independientes de contexto. Las 
producciones de las gramáticas tipo 2 son aún más restrictivas que las de tipo 1. En este 
caso, la parte izquierda de la producción está formada por un único símbolo no terminal, 
por lo tanto las producciones tienen la forma: 
A ::= v donde A ∈ ΣN, v ∈ Σ* 
 
Todas las gramáticas de tipo 2 son también gramáticas de tipo 1. En este tipo de 
gramáticas, la conversión de A en v se realiza independientemente del contexto en que se 
encuentre A, de ahí su nombre. 
 
 
 
12 
 
Ejemplo: 
S::=aAB |aB, B::=Dc, D::=CE | b, E::=Dc, A::=aAC | aC, C::=DEAa 
¿Qué pasa si agregamos la regla E::= λ? 
Gramáticas tipo 3 
Son el grupo más restringido de las gramáticas y también se les conoce con el nombre de 
gramáticas regulares. 
 
Al igual que las gramáticas tipo 2, este tipo de gramáticas tiene la restricción de que la 
parte izquierda de la producción debe estar formada por un único símbolo no terminal, 
pero además se añaden restricciones en la parte derecha de las producciones, que 
deberán estar formadas por máximo dos símbolos. 
 
Hay dos tipos de gramáticas regulares y sus producciones pueden ser de la siguiente 
forma: 
 
1. Gramáticas lineales por la derecha (GLD): 
A ::= a, A ::= aV, S ::= λ 
dónde A,V,S ∈ ΣN, a ∈ ΣT y S es el símbolo inicial de la gramática 
 
2. Gramáticas lineales por la izquierda (GLI): 
A ::= a, A ::= Va, S ::= λ 
dónde A,V,S ∈ ΣN, a ∈ ΣT y S es el símbolo inicial de la gramática 
 
Estos dos grupos de gramáticas tienen el mismo poder generativo, es decir, cualquier 
lenguaje de tipo 3 o lenguaje regular puede ser generado tanto por una gramática líneal 
por la derecha como por una lineal por la izquierda. 
 
Es importante mencionar que en una gramática tipo 3 no puede existir combinación de 
reglas lineales por la derecha y lineales por la izquierda, si esto sucede la gramática es tipo 
2. 
 
Ejemplo: 
S::=aA |aB, A::=aB | a, B::=b S es el símbolo inicial de la gramática 
¿Qué pasa si agregamos la regla B::= λ? ¿Qué pasa si agregamos la regla S::= λ? 
¿Cómo sería la gramática lineal por la izquierda? 
Lenguaje generado por una gramática 
Sea una gramática definida como G = { ΣT, ΣN, S, P } llamamos lenguaje generado por dicha 
gramática a L = { x ∈ ΣT* | S x}. 
 
Por lo tanto, las palabras del lenguaje estarán formadas por cadenas de símbolos 
terminales generadas a partir del símbolo inicial de la gramática, utilizando las 
producciones que la definen. 
 
 
13 
 
Gramáticas equivalentes 
Dos gramáticas son equivalentes cuando generan el mismo lenguaje. Es evidente que, 
para que esto suceda, deben estar definidas sobre el mismo ΣT. 
Caracterización de una gramática - ¿Cómo determinar el lenguaje que genera una 
gramática? 
Consiste en expresar las características del lenguaje producido por una gramática, 
preferentemente por medio de una expresión formal, o bien, por medio de enunciados en 
lenguaje natural si lo anterior no es posible. 
 
No existen métodos generales para caracterizar los lenguajes pero se debe tener en 
cuenta el orden en el que se aplicarían las composiciones y cuántas veces se usaría cada 
una de ellas. La caracterización es una derivación general, que abarca todas las posibles 
derivaciones en particular. 
 
Ejemplo: 
Caracterizar u obtener la el lenguaje que genera la gramática 
G = { {a,b}, {S}, S, {S::=ab|aSb} } 
 
S => ab 
 aSb => aabb 
 aaSbb => aaabbb 
 aaaSbbb => … anbn donde n>0 
El lenguaje que genera es: 
L(G) = {anbn | n > 0 } 
 
Se recomienda usar árboles o cadenas de derivación para hacer el proceso más sencillo. 
Árboles y cadenas de derivación 
Cadenas de derivación 
Las derivaciones o cadenas de derivación se utilizan para inferir las palabras que 
pertenecen a un lenguaje. En éstas, el símbolo inicial se expande utilizando una de sus 
producciones (es decir, mediante una producción cuya cabeza sea el símbolo inicial). A 
continuación, expandimos la cadena resultante reemplazando uno de los símbolos no 
terminales por el lado derecho de una de sus producciones, y así sucesivamente, hasta 
obtener una cadena compuesta totalmente por símbolos terminales. 
 
Ejemplo: 
Sea la gramática definida por G = ({E,I},{a,b,0,1},R,E), con las reglas de producción 
siguientes, que produce cadenas de expresiones algebraicas que involucran suma y 
multiplicación. 
 
 
14 
 
E→I 
E→E+E 
E→E∗E 
E → (E) 
I → a 
I → b 
I → Ia 
I → Ib 
I→ I0 
I→ I1 
 
Dada la palabra 𝑎 ∗ (𝑎 + 𝑏00), es posible encontrar una derivación a partir de la variable 
E, como se muestra en la siguiente cadena de derivación. 
𝐸 ⇒ 𝐸 ∗ 𝐸 ⇒ 𝐼 ∗ 𝐸 ⇒ 𝑎 ∗ 𝐸 ⇒ 𝑎 ∗ (𝐸) ⇒ 𝑎 ∗ (𝐸 + 𝐸) ⇒ 𝑎 ∗ (𝐼 + 𝐸) ⇒ 𝑎 ∗ (𝑎 + 𝐸)
⇒ 𝑎 ∗ (𝑎 + 𝐼) ⇒ 𝑎 ∗ (𝑎 + 𝐼0) ⇒ 𝑎 ∗ (𝑎 + 𝐼00) ⇒ 𝑎 ∗ (𝑎 + 𝑏00) 
Derivaciónizquierda y derecha 
Con el fin de restringir el número de opciones disponibles en la derivación de una cadena, 
a menudo resulta útil requerir que en cada paso se reemplace la variable más a la 
izquierda por uno de los cuerpos de sus producciones. Tal derivación se conoce como 
derivación por izquierda, la cual se indica mediante las relaciones 
𝑙𝑚
⇒ y 
∗
⇒, para uno o más 
pasos, respectivamente. 
De forma similar, se puede hacer que en cada paso se reemplace la variable más a la 
derecha por uno de los cuerpos de sus producciones. En este caso, se trata de una 
derivación por la derecha y se utilizan 
𝑟𝑚
⇒ y 
∗
⇒ para indicar una o más derivaciones por la 
derecha, respectivamente. 
Ejemplo derivación por la izquierda (tomando la gramática de la página anterior): 
E
lm
⇒ E ∗ E 
lm
⇒ I ∗ E
lm
⇒ a ∗ E
lm
⇒ a ∗ (E)
lm
⇒ a ∗ (E + E)
lm
⇒ a ∗ (I + E)
lm
⇒ a ∗ (a + E) 
 
lm
⇒ a ∗ (a + I) 
lm
⇒ a ∗ (a + I0) 
lm
⇒ a ∗ (a + I00)
lm
⇒ a ∗ (a + b00) 
Ejemplo derivación por la derecha (tomando la gramática de la página anterior): 
𝐸
𝑟𝑚
⇒ 𝐸 ∗ 𝐸
𝑟𝑚
⇒ 𝐸 ∗ (𝐸)
𝑟𝑚
⇒ 𝐸 ∗ (𝐸 + 𝐸)
𝑟𝑚
⇒ 𝐸 ∗ (𝐸 + 𝐼)
𝑟𝑚
⇒ 𝐸 ∗ (𝐸 + 𝐼0)
𝑟𝑚
⇒ 𝐸 ∗ (𝐸 + 𝐼00) 
 
𝑟𝑚
⇒ 𝐸 ∗ (𝐸 + 𝑏00)
𝑟𝑚
⇒ 𝐸 ∗ (𝐼 + 𝑏00)
𝑟𝑚
⇒ 𝐸 ∗ (𝑎 + 𝑏00)
𝑟𝑚
⇒ 𝐼 ∗ (𝑎 + 𝑏00)
𝑟𝑚
⇒ 𝑎 ∗ (𝑎 + 𝑏00) 
 
 
15 
 
Estas dos derivaciones son importantes porque cualquier analizador sintáctico o 
compilador (es decir, un programa que trata de construir una derivación para una palabra 
dada) debe utilizar una de ellas. 
Árboles de derivación 
Existe una representación de árbol para las derivaciones que ha demostrado ser 
extremadamente útil. Este árbol muestra claramente cómo se agrupan los símbolos de 
una cadena terminal en subcadenas, que pertenecen al lenguaje de una de las variables 
de la gramática. Pero lo más importante es que 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. 
Sea G = (V,T,P,S) una gramática. Los árboles de derivación para G son aquellos árboles que 
cumplen las condiciones siguientes: 
1. Cada nodo interior está etiquetado con una variable de V . 
2. Cada hoja está etiquetada 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 ::= X1, X2, ...Xk 
es una producción de P. Observe que el único caso en que una de las X puede 
reemplazarse por ε es cuando dicha X contiene un único hijo y A → ε es una 
producción de G. 
 
El árbol de derivación de la expresión 𝑎 ∗ (𝑎 + 𝑏00) se muestra a continuación: