Arboles de expresiones

Los árboles de expresiones representan el código de nivel del lenguaje en forma de datos. Los datos se almacenan en una estructura con forma de árbol. Cada nodo del árbol de expresión representa una expresión, por ejemplo, una llamada al método o una operación binaria, como x < y.

Árbol de expresiones o árbol semántico. Es una estructura jerárquica en la cual se registran las operaciones que realiza el programa fuente. En cada una de las ramas del el árbol se registra el valor o significado que este debe tener y el análisis se encarga de terminar cuál de los valores registrado en la ramas es aplicable.

Los árboles de expresiones representan el código de nivel del lenguaje en forma de datos. Los datos se almacenan en una estructura con forma de árbol. Cada nodo del árbol de expresión representa una expresión.

FUNCIONES PRINCIPALES

Identificar cada tipo de instrucción y sus componentes
Completar la Tabla de Símbolos
Realizar distintas comprobaciones y validaciones:

Comprobaciones de tipos.
Comprobaciones del flujo de control.
Comprobaciones de unicidad.
Comprobaciones de emparejamiento.

Ejemplos de árboles de expresiones:

Representación de un Árbol: Mediante diagramas de Venn Mediante círculos y flechas Mediante paréntesis anidados:( a ( b (e,f), c, d ) )ab c defac dbe f.

Conceptos Básicos: Si hay un camino de A hasta B, se dice que A es antecesor de B, y que B es sucesor de A. Padre es el antecesor inmediato de un nodo, Hijo, cualquiera de sus descendientes inmediatos. Descendiente de un nodo, es cualquier sucesor de dicho nodo. Hermano de un nodo, es otro nodo con el mismo padre. Generación, es un conjunto de nodos con la misma profundidad.

Tipos de árboles

Árbol ordenado: Es aquel en el que las ramas de los nodos están ordenadas. Los de grado 2 se llaman árboles binarios. Cada árbol binario tiene un subárbol izquierda y subárbol derecha.+- ^3.5/BADC

Árboles de expresión: Representan un orden de ejecución++*BA * EDC*+ -7 12 9(A* B) + C * D + E (7 + 12) * (-9)  -171

Árboles similares: Los que tienen la misma estructura (forma)

Árboles Equivalentes: Son los árboles similares y sus nodos contienen la misma información.

Árboles n-ario: Es un árbol ordenado cuyos nodos tiene N subárboles, y donde cualquier número de subárboles puede ser árboles vacíos1235643987abcefdcihg

Árbol binario completo: Es un árbol en el que todos sus nodos, excepto los del último nivel, tienen dos hijos. Número de nodos en un árbol binario completo= 2h–1 (en el ejemplo h = 4, 15) esto nos ayuda a calcular el nivel de árbol necesario para almacenar los datos de una aplicación.

Árboles Binarios de Búsqueda: Un árbol es un ABB si éste es binario y sus nodos son subárboles de búsqueda binarios y contienen información ordenada de tal que todos los elementos ala izquierda de la raíz son menores a la raíz y todos los elementos a la derecha de la raíz son mayores a la raíz.