Eliminacion de ambiguedad

Solo disponible en BuenasTareas
  • Páginas : 4 (972 palabras )
  • Descarga(s) : 0
  • Publicado : 16 de enero de 2011
Leer documento completo
Vista previa del texto
Eliminación de la Ambigüedad

Una gramática ambigua permite más de una derivación para la misma forma sentencial por lo que también habrá más de un [árbol de derivación] para la misma. Por ellobasta con encontrar dos [árboles derivación] distintos para la misma forma sentencial para demostrar que una gramática es ambigua.

A continuación se presentan conceptos importantes dentro del estudiode las características de las gramáticas:

AMBIGÜEDAD:

Sea G = { N , T , P , S } una gramática libre de contexto y sea L(G) el lenguaje generado por esa gramática.

Si existe un string w (dondew oe L(G) ) para el cual existen dos ó más formas de realizar la derivación de más a la izquierda (S ˘ w) ó existen dos ó más formas de realizar la derivación de más a la derecha (S ¿ w), entonces sedice que: G es una gramática ambigua.

TIPOS DE AMBIGÜEDAD:

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

Ambigüedad Inherente: Lasgramá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 laambigüedad que presentan.

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 loanterior, 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 noaceptan 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 (distintasalternativas 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...
tracking img