GRAMATICAS AMBIGUAS

GRAMATICAS AMBIGUAS

1. Institución Universitaria Colegio Mayor del Cauca


Lenguajes Formales






Gramáticas Ambiguas y
Gramáticas Libres de Contexto






Presentado a:

Alvaro Hernan Pito Burbano





Presentado por:

Ehyvarth Alejandro Bolaños Ussa
Javier Andres Solarte Medina








Popayán, Cauca 2 de Noviembre de
2013

2. Gramáticas Ambiguas


Antes de entrar en materia sobre las gramáticas ambiguas, es importante tener
presente que significa la ambigüedad, e ir relacionando el término en el área de la
computación, quizás es un término demasiado común, sin embargo intentaremos
dejarlo claro o llegar a un acuerdo de su significado. Para continuar en la explicación
armoniosa de este tema entendamos que la ambigüedad se da cuando “algo”, tiene
más de dos resultados o interpretaciones, en el caso de las palabras u oraciones se le
conoce como ambigüedad lingüística. De esta manera la ambigüedad se presenta
cuando mediante un conjunto, de palabras, letras, operaciones, símbolos, etc. Esperan
un cierto resultado para ser interpretado de una sola manera, pero por efectos de
ambigüedad resulta que se obtienen más de un resultado, o más de una interpretación,
o más de un camino para llegar a un resultado diferente. Como conclusión del concepto
entenderíamos que la ambigüedad se presenta cuando existen varias respuestas ante
algún factor. Entonces, las gramáticas ambiguas juegan un papel muy importante en la
computación, ya que al tener una cadena de caracteres y al ser generada por esta
gramática lo puede hacer en más de una forma, pues la cadena soporta más de un
árbol sintáctico, o más de una rama izquierda. Este concepto de gramáticas ambiguas
es muy común en los lenguajes libres de contexto (en el que hablaremos más
adelante de estos, acorde vayamos avanzando) ya que todos es tas gramáticas
generan lenguajes ambiguo. En algunos lenguajes de programación la ambigüedad se
hace presente y por tal razón se puede decir que se presenta gramática ambigua, y se
hace algo obvia en muchos casos; teniendo un ejemplo sencillo en el lenguaje de
programación C, tenemos lo siguiente:

X * Y ;
1


Del cual podemos interpretar como:
1- La declaración de un identificador Y y de tipo puntero para X
2- La Expresión de en la que X y Y son multiplicados y su resultado NO es
almacenado

Este tipo de ambigüedades los compiladores resuelven constantemente, el cual al igual
que los analizadores semánticos, sintácticos y léxicos solucionan este problema
mediante la consulta en una tabla de símbolos, esta tabla no es más que una
estructura de datos en la que se guarda la información correspondiente para que los

1
Ejemplo tomado de la siguiente ruta: http://pt.wikipedia.org/wiki/Gramática_ambígua

3. compiladores pueden utilizar, y así poder saber si X fue declarada como el nombre de
un tipo definido, o es un puntero, o está siendo apuntado.

Al existir ambigüedad dentro de la gramática significa que se puede generar más de
una estructura (árboles) a partir de una misma cadena.

Entendiendo que la ambigüedad existe, resulta importante definir lo que son las
Gramáticas libres de Contexto por tal razón lo explicaremos a continuación:

Gramática Libres de Contexto:

La gramática libre de contexto juega un papel muy importante en el uso de los
compiladores, y por tal razón en los lenguajes de programación, ya que nos permite
hacer una descripción de estos lenguajes, debido que los lenguajes de programación
se encuentran definidos por la utilización de gramática libre de contexto o (GLC). De
esta manera las gramáticas libres de contexto definen una serie de reglas que deben
cumplirse para indicar el orden lógico en que se debe leer y/o escribir, las cadenas o
raíces. Por lo tanto, cada regla que se establece debe cumplir de la forma

V → W

V: Símbolo NO terminal
W: Cadena de terminales y/o No terminales

De esta manera al ser libre de contexto V puede ser reemplazado por W sin tener en
cuenta en el contexto en que suceda. Al ser ésta una gramática formal, la gramática
libre o independientemente del contexto se compone de 4 elementos.

T: Símbolos terminales (son aquellos elementos que no generan nada)
V: Símbolos No terminales (los que elementos que se encuentran al lado izquierdo de
una producción, es decir al lado de la flecha →)
P: Conjunto de producciones (Conjunto de sentencias)

De esta manera tenemos que:

(Cabeza) → (Cuerpo)
Variable → Cadena de Símbolos y/o variables

Por lo tanto a todo lo que tenga la forma V→W se le conoce como regla, y se lee
de la siguiente manera: V deriva a W.

4. S: símbolo inicial: (Primer elemento que encontramos en la gramática)

Teniendo en cuenta las variables establecidas anteriormente tendríamos que la
gramática se representaría de la siguiente manera:


Gramática = (No terminales , Terminales , Producciones , Inicial)
G = ( V , T , P , S)


Para expresar formalmente un gramática, lo explicaremos mejor mediante el siguiente
ejemplo:

E → E + E
E → E * E
E → ( E )
E → id

Teniendo en cuenta que G = ( V , T , P , S), entonces la gramática la expresamos como
:

V: { E } Símbolos no terminales
T: { + , * , (,) , id } No terminales
P: P Conjunto de Producciones
S: E Símbolo Inicial

{ { E } , { + , * , (,) , id } , P , E }


Convenciones
2
:

Son “estándares” establecidos, para el correcto uso de las gramáticas, al hacer uso de
las convenciones podemos deducir e identificar fácilmente, cuáles son las variables,
terminales y símbolos de inicio, de esta manera tenemos:


2
Tomado de https://www.youtube.com/watch?v=eHo4Qlqoc3k

5. 1. Las letras mayúsculas A, B ,C , D, E y S, y son denotadas como variables,
igualmente S, es el símbolo de Inicio.
2. Las letras minúsculas a, b, c, d, e, los dígitos, las cadenas en negrillas se utilizan
para denotar terminales.
3. Las mayúsculas X,Y y Z denotan símbolos los cuales pueden ser terminales o
variables
4. Las letras minúsculas u, v, w, x, y, z denotan cadenas terminales
5. Las letras del griegas α , β , γ (alfa, beta y gamma respectivamente) denotan
cadenas variables y terminales

Teniendo en cuenta lo anterior, podríamos establecer la gramática para el ejemplo
visto:
E → E + E
E → E * E
E → ( E )
E → id
La gramática sería: E→ E + E | E * E | ( E | id )

De esta misma manera escribiremos una gramática para un ejemplo hecho en con el
Lenguaje de programación Java, entonces, teniendo una declaración de una variable el
cual consta de tres partes, el tipo de variable en este caso es entera, la letra o palabra
que representa la variable, y por último el punto y coma, para finalizar la sentencia o
linea de código, el cual nos quedaría algo como lo siguiente

int valor;

para escribir su gramática debemos tener presente como la regla V → W, como lo que
queremos en este lenguaje es declarar una variable de tipo entero llamada valor, y
teniendo en cuenta el formato de la regla, tendríamos las siguientes tres reglas:

1. <var> → <tipo> <id> ;
2. <tipo> → int
3. <id> → id

Ahora si tuviéramos lo siguiente:

double valorDouble;

1. <var> → <tipo> <id> ;
2. <tipo> → int | double

6. 3. <id> → id

Vemos que los dos ejemplos son muy similares, salvo el punto 2, ya que se está
diciendo que la segunda regla puede aceptar valores de tipo int, o valores de tipo
double.

Pero las gramáticas no siempre es tan simple como aparentemente parece ser, ya que
su realización depende también de la complejidad de la cadena que vamos a evaluar, y
de la forma en que lo queramos hacer, por tal razón cuando se crea un derivación (V →
W) que en pocas palabras son las producciones de una gramática para obtener una
cadena de terminales, sustituyendo la cabeza por el cuerpo de la producción (cabeza
→ cuerpo) este lo hacemos con el fin de comprobar si las cadenas proporcionadas
cumplen con la gramática del lenguaje. Para hacer uso de la derivación en la
gramática, podemos hacerlo de dos maneras, por medio de la Inferencia Recursiva (del
cuerpo hacia la cabeza), o la Derivación (de la cabeza al cuerpo). Así mismo este
último se puede realizar dos tipos de Derivación, hacia la izquierda y hacia la Derecha,
por medio de la utilización de árboles de derivaciones

Árbol de Derivación: Estos árboles son estructuras, que permiten visualizar de una
manera gráfica, la forma en que se puede derivar una cadena para cierto lenguaje de
programación. y dentro de las propiedades en las que se compone un árbol tenemos:
se compone de una raíz, de Nodos interiores, y de nodos hojas, tal como veremos a
continuación:

7. Derivación por la Izquierda: Sustituye a la hoja no terminal que se encuentra más a
la izquierda
Derivación por la Derecha: Sustituye a la hoja no termina que se encuentra más a la
derecha.

Teniendo el siguiente Ejemplo
3
, en el cual establecen las siguientes reglas:

1. S → ASB
2. A → b
3. aaA → aaBB
4. S → d
5. A → aA
6. B → dcd

Del cuál haciendo el respectivo recorrido y teniendo en cuenta las reglas establecidas
anteriormente, y las convenciones dadas, tendríamos el siguiente árbol:



Del cual haciendo el recorrido por la izquierda tendríamos el siguiente resultado:

1 5 2 4 6
S → ASB → aASB → abSB → abdB → abddcd

Así mismo si hacemos la derivación por la derecha del árbol tendríamos el siguiente
resultado


3
Ejemplo tomado del canal sufilu37, dirección del canal: https://www.youtube.com/watch?v=qkJQpTzYPqs

8. 1 6 4 5 2
S → ASB → ASdcd → Addcd → aAddcd → abddcd


Como podemos ver, los resultados presentados por los dos recorridos son diferentes,
al existir diferentes combinaciones se presenta la ambigüedad, y para ellos también
surge una serie de reglas, condiciones, que se guardan en la tabla de símbolos, así en
el momento que exista o se presente ambigüedad se pueda tomar una decisión y así
el compilador pueda hacer se trabaja, de acuerdo a lo que se encuentre definido, a esta
es lo que conocemos como Gramática Ambigua.

Habiendo ya entendido lo que es la gramática libre de contexto, sus recorridos y
derivaciones, que se obtienen mediante los árboles, y sabiendo además que se
presenta la ambigüedad al hacer cualquiera de sus recorridos, miraremos más a fondo
el comportamiento de la gramática ambigua.



Volviendo a unos de los anteriores y primeros ejemplos, tomamos la expresión de una
gramática libre de contexto:
E + E * E
El cual haciendo sus respectivas derivaciones tendríamos lo siguiente:

E → E + E → E + E * E
E → E * E → E + E * E

Podemos mirar que las derivaciones son diferentes, a pesar de que la expresión es la
misma en ambos casos, pues se ve afectada por el recorrido, si esta es por la derecha
o por la izquierda, por lo tanto a cada derivación le corresponde una estructura
sintáctica.

9. Pero en muchas ocasiones también se presenta cuando las cadenas o expresiones
diferentes, produce la misma estructura.

Sin embargo el uso de la gramática ambigua suele ser muy útil al momento de hacer
construcciones más naturales y concias, también para trabajar en casos particulares.
La utilización de gramáticas ambiguas puede generar lenguajes con reglas para
deshacer dicha ambigüedad, teniendo en cuenta que solo se debe usar en casos
particulares y de manera controlada, para así evitar conflictos.






Bibliografía


http://es.wikipedia.org/wiki/Gram%C3%A1tica_libre_de_contexto
http://pt.wikipedia.org/wiki/Gram%C3%A1tica_amb%C3%ADgua
http://www.virtual.unal.edu.co/cursos/ciencias/2001018/lecciones/Cap4s3.pdf
http://turing.iimas.unam.mx/~luis/cursos/ALF_old/sesiones/tema16c.pdf
http://www.giaa.inf.uc3m.es/docencia/II/PL1/PL1GramaticasAmbiguas.pdf
http://www.materialesdelengua.org/LENGUA/lexico/ambiguedad/ambiguedad.htm
https://www.youtube.com/watch?v=eHo4Qlqoc3k
https://www.youtube.com/watch?v=qkJQpTzYPqs