Árbol de análisis sintáctico

Un árbol de análisis sintáctico se puede considerar como una representación gráfica de una derivación que no muestra la elección relativa al orden de sustitución.

La etiqueta de un nodo pertenece a ().

La etiqueta de un nodo siempre es un terminal.

La etiqueta de los nodos que no son hoja, son no terminales.

La raíz del árbol es el símbolo inicial de la gramática.

Si un nodo tiene como etiqueta el símbolo B y sus nodos hijos tienen como etiquetas los símbolos , entonces la producción B→ , pertenece al conjunto de producciones de la gramática.

Si un nodo está etiquetado con la palabra vacía, entonces es un nodo hoja del árbol y el único hijo de dicho nodo.

En la siguiente figura (Figura 36) se muestra el árbol de análisis sintáctico para una entrada de la gramática anterior.

Figura 36: árbol de análisis sintáctico de “5-1+3”

Si se encuentran dos árboles sintácticos distintos para una misma cadena de entrada, entonces la gramática es ambigua. Normalmente en el análisis sintáctico no interesa trabajar con gramáticas ambiguas, ya que para una misma cadena de entrada, se generan dos árboles sintácticos distintos.