Árbol de Análisis Gramatical (o Concreto) #

En el capítulo anterior se vio que un analizador sintáctico tiene que buscar un camino para llegar, mediante transformaciones, desde el símbolo inicial hasta la cadena de entrada. Si se encuentra, la forma de indicar cuál es dicho camino (el mapa con los pasos a seguir) es lo que se denomina árbol de análisis gramatical o, informalmente, árbol concreto (por contraposición al árbol abstracto que aparecerá en temas posteriores).

La forma de obtener este árbol es relativamente sencilla. Se construye a la vez que se realizan las transformaciones. De hecho, cada vez que se realiza una transformación, basta con añadir al árbol, como hijos del símbolo sustituido, los símbolos por los que ha sido sustituido.

Por ejemplo, supóngase la siguiente gramática G:

s ⟶ e
e ⟶ e + e
e ⟶ e * e
e ⟶ LITENT

Supóngase que se quiere saber si la entrada 3 + 4 * 5 es válida según dicha gramática. Para ello, se encuentra la derivación de s que lleva a dicha cadena (a la izquierda de la imagen). Lo que se hace en el árbol de la derecha es ir anotando qué símbolo se ha sustituido por qué otros en cada transformación:

De esta manera, se obtiene el árbol concreto correspondiente a la entrada.

Nótese que en un árbol concreto se cumple que:

• La raíz del árbol será el símbolo raíz de la gramática.
• Todo nodo terminal será un token.
• En todo subarbol formado por un padre y sus hijos:
  • El padre será el antecedente de una producción de la gramática.
  • Los hijos serán el consecuente de dicha producción.

Nótese que lo que no registra un árbol concreto es el orden en el que se han hecho las transformaciones. Es decir, en el ejemplo anterior, no se sabe si en la cadena e + e, se realizó primero la sustitución de la primera e por LITENT o se realizó primero la de la segunda e por e * e. El motivo es que no es relevante en qué orden se realicen las transformaciones de los no-terminales de una cadena; sólo es relevante saber por qué símbolos se sustituyó cada uno.