| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I Introducción 1.1 Lenguajes y Gramáticas 1.2 Clasificación de las Gramáticas 1.3 Derivaciones y Reducciones

1.4 Árboles de sintaxis

1.5 Gramáticas Ambiguas

1.6 Formas de Backus-Naur (BNF)

UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

1.5 Gramáticas Ambiguas

> Para poder determinar la ambigüedad de la gramática se debe obtener los árboles de derivación. Si para la misma cadena existen dos o más árboles de derivación la gramática es ambigua.

> Dada una gramática G = (N, T, P, S). Una sentencia x T * se denomina ambigua si puede obtenerse por más de un árbol de derivación (o equivalentemente, más de una derivación más a la izquierda o más a la derecha), como se muestra en la siguiente figura:

> Una gramática G se denomina ambigua si el lenguaje que genera contiene alguna sentencia ambigua.

> Observaciones:

> 1. La ambigüedad es una propiedad indecidible.

> 2. La condición de ambigüedad se aplica a las gramáticas y no a los lenguajes. (Un mismo lenguaje puede ser generado por varias gramáticas equivalentes).

> 3. Un lenguaje se denomina inherentemente ambiguo si no existe una gramática no ambigua que lo genere.

> Ambigüedad

> Una gramática es ambigua si existe alguna cadena a la que se pueda asociar dos árboles de análisis sintácticos diferentes. Las gramáticas ambiguas no son adecuadas para especificar lenguajes de programación, ya que árboles sintácticos diferentes generan un código diferente. La utilización de este tipo de gramáticas tiene problemas como:

> – Demostrar que una gramática no es ambigua es muy difícil.

> – Existen construcciones gramaticales que producen ambigüedad.

> Ejemplo:

> Una gramática ambigua para expresiones aritméticas:

> <expr> → <expr> <op> <expr>
> | (<expr>)
> | <id>
> <op> → + | - | * | /
> <id> → a | b | c

> La expresión a * b + c tiene dos árboles sintácticos diferentes, como se muestra en las siguientes figuras:

> Por lo que, basándonos en los antes expuesto, concluimos que esta gramática es ambigua.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello