Gramáticas Ambiguas

Gramática ambigua

Es un Gramática libre del contexto para la que existe una cadena que puede tener más de una derivación a la izquierda, mientras una gramática no ambigua es una Gramática libre del contexto para la que cada cadena válida tiene una únicaderivación a la izquierda. Muchas lenguajes admiten tanto gramáticas ambiguas como no ambiguas, mientras otros lenguajes admiten solo gramáticas ambiguas.

Eliminación de ejecución de izquierda

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

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!

Derivación más izq:

E ⇒ E + T ⇒ T + T ⇒ F + T ⇒ I + T ⇒ a + T ⇒ a + (T * F) ⇒ a + (F * F) ⇒ a + (I * F) ⇒ a + (a * F) ⇒ a + (a * I) ⇒ a + (a * a)  Teorema: Para toda gramática G = (V, T, S, P) & cadenas w en T * , w tiene dos árboles de parseo distintos si y sólo si tiene dos derivaciones más izquierdas a partir de S  Prueba: si no fuera el caso una variable más izquierda se podría expandir en más de una forma

Árbol de síntesis