Problemas del Árbol Concreto #

Se ha visto en el capítulo anterior el porqué se va a generar un árbol. Y en un capitulo anterior a ese se había visto el árbol concreto. Sin embargo, como ya se adelantó, no será este árbol el que se genere en esta asignatura. El motivo es que presenta dos problemas importantes:

• Es redundante.
• Está acoplado a la gramática.

Redundancia #

Para ilustrar el primer problema, supóngase la siguiente gramática.

programa ⟶ sentencia | sentencia programa       (1+ss)

sentencia ⟶ escritura
            | while

escritura ⟶ PRINT ID ‘;’

while ⟶ WHILE ID ‘{‘ programa ‘}’

Lo siguiente sería una entrada válida.

print a;
while a {
    print b;
}

Y el árbol concreto de la misma sería el siguiente.

En este árbol hay tres grupos de símbolos redundantes. En la imagen posterior se identifican dichos símbolos:

• Sobran los tokens que ayudaron a identificar una estructura (tokens PRINT y WHILE — tachados en rojo). Ya no son necesarios ya que su nodo padre ya indican qué estructuras son (escritura y while respectivamente).
• Sobran los tokens que ayudan a delimitar las estructuras (las llaves y los punto y coma — tachados en azul). Las llaves, por ejemplo, se utilizaban para indicar qué va dentro del while y qué va fuera. Ahora ya no son necesarias, ya que la propia estructura del árbol deja claro qué sentencias están dentro del mismo.
• Sobran los no-terminales necesarios para definir las producciones de la gramática pero que son redundantes en el árbol (sentencia y algunos programa — tachados en amarillo). Por ejemplo, no aporta nada que encima de un nodo escritura haya otro nodo indicando que es una sentencia.

Este es el primer problema de utilizar un árbol concreto. Hay mucho nodo innecesario que:

• Si se elimina, no va a suponer una pérdida de información para las fases posteriores del traductor.
• Pero si se deja supone:
  • Un gasto de memoria.
  • Y, lo que es más importante, complicaría la implementación de las siguientes fases, ya que tienen que implementar recorridos de más nodos de los necesarios.

Acoplamiento #

El segundo problema de los árboles concretos, el acoplamiento, supone un problema aún mayor que el primero. Para ilustrar este problema, supóngase la siguiente gramática:

Supóngase que el sintáctico, en vez de pasar un AST, les pasara el árbol concreto a las fases posteriores. Por tanto, todas las fases posteriores del traductor se implementarían en función de dicha estructura de árbol.

Supóngase que, una vez implementadas las demás fases, se decide refactorizar la gramática (recuérdese que de un mismo lenguaje existen infinitas gramáticas equivalentes). Por tanto, sin cambiar el lenguaje a reconocer, se opta por reconocerlo con una nueva gramática. En la siguiente imagen se ve a la izquierda la gramática antigua con el árbol concreto que generaba y a la derecha la nueva gramática con el árbol concreto que genera para la misma entrada.

El lenguaje no se ha cambiado. Y se debería esperar que las consecuencias del cambio sean nulas para las siguientes fases. Sin embargo, dado el acoplamiento que tiene el árbol concreto con la gramática (ya que usa los mismos símbolos y estructura que esta), el árbol que se genera es distinto. Por ejemplo, ahora aparece un nodo mt que antes no estaba. Esto supone que habría que cambiar todas las fases posteriores del traductor ya que ha cambiado el árbol y hay que adaptarlas para que recorran los nuevos nodos (y que dejen de recorrer los que desaparezcan).

Si el lenguaje no ha cambiado, no debería cambiar tampoco la estructura del árbol — aunque se hubiera cambiado la gramática. Las reglas que utilice un sintáctico debería ser un asunto interno del mismo que no debería afectar a otras fases. No tiene sentido dividir el trabajo de un traductor en fases si luego tienen un acoplamiento tan grande con el sintáctico. Este es el principal problema de usar un árbol concreto.