Automatas

Ambigüedad Tema 16
Ambigüedad Dr. Luis A. Pineda ISBN: 970-32-2972-7 Si una gramática genera más de una estructura a partir de la misma raiz y con la misma cosecha (más de una estructura para la misma cadena), dicha gramática es ambigua Dos tipos de ambigüedad – En la gramática – En el lenguaje
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Ambigüedad
Si una gramática esambigua, posiblemente (no necesariamente) existe una gramática no ambigua que genere el mismo lenguaje Un lenguaje es inherentemente ambiguo si todas sus gramáticas son ambiguas ¡No existe un algoritmo que decida si una gramática es ambigua!
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Una gramática ambigua
Exp es una GLC donde P = {E → E + E | E * E | (E) | 1 |…| 9} Una expresiónambigua: – E+E*E Dos derivaciones: – E⇒E+E⇒E+E*E – E⇒E*E⇒E+E*E ¡Son iguales!
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

– Gexp = ({E}, {+, *, (, ), 1,…, 9}, E, P)

Una gramática ambigua
La expresión final es la misma: – E ⇒* E + E * E – E ⇒* E + E * E Pero las derivaciones son diferentes: – E⇒E+E⇒E+E*E – E⇒E*E⇒E+E*E

Una gramática ambigua
A cada derivación le corresponde unaestructura sintáctica: – Derivaciones diferentes pueden generar la misma estructura (para la misma cadena) – La ambigüedad surge cuando derivaciones diferentes generan estructuras diferentes (para la misma cadena)
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

1

Una gramática ambigua
La expresión final es la misma:E ⇒* E + E * E – E ⇒* E + E * E Sus estructuras sintácticas son diferentes:
–
E E E 3

Una gramática ambigua
La diferencia es significativa:
– E ⇒ E + E ⇒ E + E * E ⇒* 3 + 4 * 2 – E ⇒ E * E ⇒ E + E * E ⇒* 3 + 4 * 2
E

Vale 11
E E 2 E 3

Vale 14
E

E

E

+ E

E E E

E

* E

E

+ E 4

* E 4

E 2

*

+

*

+

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN:970-32-2972-7

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

¿De quién es el “defecto”?
Derivaciones diferentes pueden tener la misma estructura: – E⇒E+E⇒3+E⇒3+2 – E⇒E+E⇒E+2⇒3+2
E

Gramáticas ambiguas
Una CFG G = (V, Σ, S, P) es ambigua si existe cuando menos una cadena w en Σ * para la cual hay más de una árbol de parseo o estructura sintáctica, cada una de éstas con raiz S ycosecha w Si toda cadena en el lenguaje de la gramática tiene cuando más un árbol de parseo, la gramática no es ambigua
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

E 3

+

E 2

La ambigüedad surge cuando hay más de una estructura sintáctica para la misma expresión!
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Gramáticas ambiguas
Si G es una GLC ambigua,tal que L = L(G) & existe una Gi no ambigua tal que L = L(Gi), podemos eliminar la ambigüedad reemplazando a G por Gi (usando a Gi en vez de G)

Eliminando la ambigüedad
En general, no existe un algoritmo para eliminar la ambigüedad Hay LLC que sólo tienen gramáticas ambiguas!

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN:970-32-2972-7

2

Eliminando la ambigüedad
En la práctica y para algunas aplicaciones (e.g. definir GLC para lenguajes de programación), es posible eliminar la ambigüedad Para esto es necesario estudiar las causas de la ambigüedad (específicas para una gramática ambigua dada) y proporcionar una gramática alternativa no ambigua!
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Causas dela ambigüedad
Consideremos Gexp: Fuente 1: – La precedencia de los operadores no se respeta Fuente 2: – Una secuencia del mismo operadore se puede agrupar tanto por la izquierda como por la derecha – ¡Esto no afecta si el operador es asociativo!
Dr. Luis A. Pineda, IIMAS, UNAM, 2005. ISBN: 970-32-2972-7

Una gramática ambigua
La precedencia de operadores no se respeta: – E ⇒* E + E * E – E...