Árbol de análisis en el diseño del compilador

Aquí estudiaremos el concepto y los usos de Parse Tree en Compiler Design. Primero, veamos dos términos:

• Analizar: significa resolver (una oración) en sus partes componentes y describir sus roles sintácticos o simplemente es un acto de analizar una string o un texto.
• Árbol: un árbol puede ser un tipo de datos abstractos ampliamente utilizado que simula una estructura de árbol jerárquico, con un valor raíz y subárboles de jóvenes con un Node principal, representado como un grupo de Nodes vinculados.

Árbol de análisis:

• El árbol de análisis es la representación jerárquica de terminales o no terminales.
• Estos símbolos (terminales o no terminales) representan la derivación de la gramática para generar strings de entrada.
• En el análisis, la string salta usando el símbolo de inicio.
• El símbolo de inicio de la gramática se debe utilizar como raíz del árbol de análisis.
• Las hojas del árbol de análisis representan terminales.
• Cada Node interior representa producciones de una gramática.

Reglas para dibujar un árbol de análisis:

1. Todos los Nodes hoja deben ser terminales.
2. Todos los Nodes interiores deben ser no terminales.
3. El recorrido en orden da la string de entrada original.

Ejemplo 1: Tomemos un ejemplo de Gramática (Reglas de Producción).

S -> sAB
A -> a
B -> b

La string de entrada es «sab», luego el árbol de análisis es:

 

Ejemplo-2: Tomemos otro ejemplo de gramática (reglas de producción).

S -> AB
A -> c/aA
B -> d/bB

La string de entrada es «acbd», luego el árbol de análisis es el siguiente: 

 

Usos del árbol de análisis:

• Ayuda a realizar análisis de sintaxis al reflejar la sintaxis del idioma de entrada.
• Utiliza una representación en memoria de la entrada con una estructura que se ajusta a la gramática.
• Las ventajas de usar árboles de análisis en lugar de acciones semánticas: hará varias pasadas sobre la información sin tener que volver a analizar la entrada.