1.1 Árboles de expresiones

 1.1 Árboles de Expresiones

Árbol de expresiones
Los árboles de expresiones representan el código de nivel del lenguaje en forma de datos.

¿Qué son?

Son estructuras de datos que definen código. Se basan en las mismas estructuras que usa un compilador para analizar el código y generar el resultado compilado.


Un árbol de expresión es un árbol binario con las siguientes propiedades:
  • Cada hoja es un operando
  • Los nodos raíz y los nodos internos son operadores
  • Los subárboles son subexpresiones cuyo nodo raíz es un operador.

Función

Representar expresiones aritméticas en memoria, esencialmente en compiladores de lenguajes de programación.
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.

Árboles de expresiones en detalle


Veamos un ejemplo sencillo. Aquí tiene una línea de código:

Si fuera a analizarlo como un árbol de expresión, el árbol contiene varios nodos. El nodo más externo es una instrucción de declaración de variable con asignación (var sum = 1 + 2;). Ese nodo exterior contiene varios nodos secundarios: una declaración de variable, un operador de asignación y una expresión que representa el lado derecho del signo igual. Esa expresión se subdivide aún más en expresiones que representan la operación de suma, y los operandos izquierdo y derecho de la suma.

Vamos a profundizar un poco más en las expresiones que constituyen el lado derecho del signo igual. La expresión es 1 + 2. Se trata de una expresión binaria.
Concretamente, es una expresión binaria de suma. Una expresión binaria de suma tiene dos elementos secundarios, que representan los nodos izquierdo y derecho de la expresión de suma. En este caso, ambos nodos son expresiones constantes: el operando izquierdo es el valor 1 y el operando derecho es el valor 2.

Visualmente, toda la instrucción es un árbol: puede empezar en el nodo raíz y desplazarse a cada uno de los nodos del árbol para ver el código que compone la instrucción:
  • Instrucción de declaración de variable con asignación (var sum = 1 + 2;)
    • Declaración de tipo de variable implícita (var sum)
      • Palabra clave var implícita (var)
      • Declaración de nombre de variable (sum)
    • Operador de asignación (=)
    • Expresión binaria de suma (1 + 2)
      • Operando izquierdo (1)
      • Operador de suma (+)
      • Operando derecho (2)
Además de traducir algoritmos para ejecutarlos en otros entornos, se pueden usar árboles de expresiones para que resulte más fácil escribir algoritmos que inspeccionen el código antes de ejecutarlo. Puede escribir un método cuyos argumentos sean expresiones y, luego, examinar esas expresiones antes de ejecutar el código.

Creación de Árbol de Sintaxis Abstracta (AST)
Recorrido y evaluación del AST

Elaborado por: Joseph Aldahir López Hernández

Referencias

Computacionales, I. e. (s.f.). Árboles. Recuperado el 12 de Febrero de 2022, de www.it.uc3m.es: https://www.it.uc3m.es/java/gitt/units/arboles/guides/2/guide_es.html#idm4835080

Docs, M. (08 de Febrero de 2022). Árboles de expresiones en detalle. Recuperado el 12 de Febrero de 2022, de Microsoft: https://docs.microsoft.com/es-es/dotnet/csharp/expression-trees-explained

Elkan, M. (10 de Septiembre de 2019). Arboles de expresiones. Recuperado el 12 de Febrero de 2022, de Lenguajes Automatas II: https://miguelangelperezautomatas.blogspot.com/2019/09/arboles-de-expresiones.html

Mendez, I. (s.f.). Árboles de Expresion. Recuperado el 12 de Febrero de 2022, de ISC. MENDEZ-PORTAFOLIO: https://sites.google.com/site/iscmendezportafolio/arboles-de-expresion