Eliminación De Ambiguedad

Eliminacion de ambiguedad

Eliminación de ambigüedad:

Ambigüedad: Una gramática es ambigua si derivando de forma diferente con el mismo tipo de derivación se llega al mismo resultado.

Un lenguaje es inherentemente ambiguo si todas sus gramáticas son ambiguas:

Exp es una GLC

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

donde P = {E ïƒ E + E | E * E | (E) | 1 |…| 9}

Una expresión ambigua:

1.- E + E * E

Dos derivaciones:

1.- E⇒ E + E⇒ E + E * E

2.- E⇒ E * E⇒ E + E * E

¡Son iguales!

TIPOS DE AMBIGÜEDAD

Dentro del estudio de gramáticas existen dos tipos fundamentales de ambigüedad, los cuales son:

AMBIGÜEDAD INHERENTE:

Las gramáticas que presentan este tipo de ambigüedad no pueden utilizarse para lenguajes de programación, ya que por más transformaciones que se realicen sobre ellas, nunca se podrá eliminar completamente la ambigüedad que presentan.

Un lenguaje L es inherentemente ambiguo si todas sus gramáticas son ambiguas; si existe cuando menos una gramática no ambigua para L, L no es ambiguo.

1.- El lenguaje de las expresiones no es Ambiguo

2.- Las expresiones regulares no son ambiguas

AMBIGÜEDAD TRANSITORIA:

Este tipo de ambigüedad puede llegar a ser eliminada realizando una serie de transformaciones sobre la gramática original. Una vez que se logra lo anterior, la gramática queda lista para ser reconocida por la mayor parte de los analizadores sintácticos. (Sele considera "ambigüedad" porque existen métodos para realizar análisis sintáctico que no aceptan gramáticas con estas características)

Dónde se presenta la Ambigüedad Transitoria generalmente la ambigüedad se presenta cuando existen producciones con factores comunes (distintas alternativas para un símbolo no-terminal que inician de la misma forma); ó cuando existen producciones que son recursivas izquierdas (producciones para un símbolo no-terminal en las cuales el primer símbolo de su forma sentencial es ese mismo símbolo no-terminal).

¿Cómo solucionar el problema de la Ambigüedad Transitoria?

Para eliminar este tipo de ambigüedad, es necesario, primero eliminar:

- Factores comunes izquierdos inmediatos y No-inmediatos.

- Recursividad izquierda inmediata y No-inmediata.

ELIMINACIÓN DE LA AMBIGÜEDAD.

1.- No existe un algoritmo que nos indique si una GIC es ambigua

2.- Existen LIC que sólo tienen GIC ambiguas: inherentemente ambiguos

3.- Para las construcciones de los lenguajes de programación comunes existen técnicas para la eliminación de la ambigüedad

Ejemplo: causas de ambigüedad en la siguiente gramática

a) No se respeta la precedencia

...