Lenguajes Libres de Contexto: 3.7.- Eliminación de la ambigüedad.

Una GLC es ambigua si existe una cadena w Î L(G) que tiene más de una derivación por la izquierda o más de una derivación por la derecha o si tiene dos o más árboles de derivación. En caso de que toda cadena w Î L(G) tenga un único árbol de derivación, la gramática no es ambigua.

Ejemplo: La gramática S ® aS| Sa | a es ambigua porque aa tiene dos derivaciones por la izquierda

S Þ aS Þ aa S Þ Sa Þ aa

Esta gramática genera el lenguaje a+ que también es el lenguaje generado por la gramática no ambigua S ® aS | a.

EJEMPLO

•La gramática para expresiones aritméticas sobre las variables x y y:

–E ® E + E

–E ® E * E

–E ® x

–E ® y

es ambigua porque la cadena x + y * x tiene dos árboles de derivación:

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.

– El lenguaje de las expresiones no es Ambiguo

– Las expresiones regulares no son ambiguas

Ejemplo de un lenguaje inherentemente ambiguo:

L = {aⁿbⁿc^md^m | n ³ 1, m ³ 1} È {aⁿb^mc^mdⁿ| n ³ 1, m ³ 1}

L es un LLC:

S ® AB | C

A ® aAb | ab C ® aCd | aDd

B ® cBd | cd D ® bDc | bc

La gramática es ambigua: hay cadenas con más de una

derivación más izquierda:

Considere: aabbccdd (m = n = 2)

S ⇒ AB ⇒ aAbB ⇒ aabbB ⇒ aabbcBd ⇒ aabbccdd

S ⇒ C ⇒ aCd ⇒ aaDdd ⇒ aabDcdd ⇒ aabbccdd

- El lenguaje:

- L = {aⁿbⁿc^md^m | n ³ 1, m ³ 1} È {aⁿb^mc^mdⁿ | n ³ 1, m ³ 1}

- La gramática

- S ® AB | C

A ® aAb | ab C ® aCd | aDd

B ® cCd | cd D ® bDc | bc

_ ¿Por qué todas las gramáticas para este lenguaje son

ambiguas?

– Considere cualquier cadena con m = n

– ¡Siempre habrá dos derivaciones para estas cadenas!

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. (Se le 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.

– No existe un algoritmo que nos indique si una GIC es ambigua

– Existen LIC que sólo tienen GIC ambiguas: inherentemente ambiguos

– 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

• No se respeta la precedencia de operadores

• una secuencia de operadores idénticos puede agruparse desde la izquierda y desde la derecha. Lo convencional es agrupar desde la izquierda.