GUÍA 02-11-26 Teoría de la Computación

NE111 · lunes 02/11/2026 · 16:00-17:15 · Sesión 24

Diseño de gramáticas · Árboles de derivación y ambigüedad

EL ÁRBOL DE DERIVACIÓN

Representa la estructura de una derivación: la raíz es S, los nodos internos son variables, y las hojas leídas de izquierda a derecha forman la cadena. Es el objeto que un compilador construye y sobre el que genera código.

ÁRBOL Y DERIVACIÓN

Un mismo árbol admite muchas derivaciones según el orden en que se expandan las variables, pero corresponde a exactamente una derivación por la izquierda y una por la derecha. Por eso lo que captura la estructura es el árbol, no la derivación.

AMBIGÜEDAD

Una gramática es ambigua si alguna cadena de su lenguaje tiene dos o más árboles de derivación distintos. Es un defecto grave: significa que el significado del programa no queda determinado por su texto.

EL EJEMPLO CLÁSICO

Con E → E+E | E*E | id, la cadena id+id*id tiene dos árboles: uno agrupa (id+id)*id y el otro id+(id*id). Dan resultados numéricos distintos, y un compilador tendría que elegir arbitrariamente.

CÓMO SE RESUELVE

Se reescribe la gramática con niveles que codifican precedencia y asociatividad.

• E → E + T | T
• T → T * F | F
• F → ( E ) | id

La multiplicación queda más abajo en el árbol y por lo tanto se evalúa primero; la recursión por la izquierda impone asociatividad izquierda. El lenguaje generado es el mismo y la gramática deja de ser ambigua.

EL DANGLING ELSE

La otra ambigüedad famosa: en «if C1 then if C2 then S1 else S2» no queda claro a cuál if pertenece el else. Los lenguajes lo resuelven por convención —el else se asocia al if más cercano— y la gramática se reescribe para forzarla.

DISEÑAR UNA GRAMÁTICA: RECOMENDACIONES

• Un nivel de no terminal por cada nivel de precedencia.
• Recursión izquierda para asociatividad izquierda, derecha para la derecha.
• Probar siempre con la cadena más corta y con una que combine todos los operadores.

AMBIGÜEDAD INHERENTE

Hay lenguajes para los que toda gramática es ambigua. Además, decidir si una gramática dada es ambigua es indecidible: no existe algoritmo general. Es una aplicación directa del bloque de computabilidad a este bloque.

EJERCICIO

Mostrar dos árboles para una cadena en una gramática ambigua y reescribirla eliminando la ambigüedad.