Arboles De Derivacion

Árboles de Derivación y Gramáticas Ambiguas

Una Gramatica Ambigua permite más de una Derivacion para la misma Forma Sentencial por lo que también habrá más de un árbol de derivación para la misma. Por ello basta con encontrar dos árboles derivación distintos para la misma Forma Sentencial para demostrar que una gramática es ambigua.

Ejemplo :

Tal vez la instancia más famosa de una Gramatica Ambigua sea el del else ambiguo, el cual está presente en diversos lenguajes de programación como Pascal, C, y Java. Las sintaxis de las instrucciones if then else en Java puede especificarse con la siguiente gramática BNF simplificada:

<instr> ::= 'if' '(' <expre> ')' <instr> | 'if' <expre> <instr> 'else' <instr> | 'a' ';'

<expre> ::= 'e'

Dada la frase:

if (e) if (e) a; else a;

Pueden obtenerse dos derivaciones para la misma frase. Una es la que corresponde a la interpretación usual de los if anidados en los lenguajes de programación:

if (e)

{

if (e)

a;

else

a;

}

La otra es la que corresponde a la siguiente interpretación:

if (e)

{

if (e)

a;

}

else

a;

...