Un árbol de sintaxis abstracta o en inglés: abstract syntax tree en inglés (AST), es una estructura de datos que se utiliza en ciencia de la computación para representar una pieza de código.
Para entender exactamente como funcionan es necesario entender como funciona una estructura de datos de tipo árbol.
Un árbol como estructura de datos
Un árbol esta compuesto completamente de nodos y puede estar vació o contener 1, 2 o n nodos.
El primer nodo de un árbol se llama raíz.
Las conexiones entre cada nodo se llaman ramas.
Los árboles tiene una estructura vertical y los nodos que salen de las ramas de uno se denominan como nodos hijo. Por supuesto los nodos de donde salen dichas ramas son nodos padre.
Esto significa que los nodos raíz son intrínsecamente nodos padre.
Los nodos hijos de cada uno son los que salen directamente de los mismos.
*Nada evita que un nodo sea tanto nodo hijo como nodo padre, Por ejemplo el nodo 2 del árbol C es hijo del nodo 1 y padre del nodo 3.
Por último los nodos sin hijos. Se denomina como hojas.
Hay muchas mas características y conceptos importantes que conciernen al tema de estos árboles. Sin embargo este resumen es suficiente para poder abordar los Abstract Syntax Trees.
Ejemplo de AST
Ok ahora veamos un ejemplo de un AST creado a partir de una sección de código de Javascript.
function sum(numA, numB) {
const result = numA + numB;
console.log("sum ~ result:", result);
return sum;
}
sum(3, 7);El AST que verás a continuación es un paso que se hace durante el parseo de JS.
Este proceso es muy importante por qué es lo que permite convertir el código que escribes a código máquina y por ende es lo que hace que funcione en el navegador.
No vamos a ahondar en detalles pero debes saber que antes de armar el AST, el navegador debe generar tokens del código. Esto no quiere decir nada mas que se separa cada elemento para poder identificar que significa.
[
"function",
"sum",
"(",
"numA",
",",
"numB",
")",
"{",
"{",
"const",
"result",
"=",
"numA",
"+",
"numB",
";",
"console",
".",
"log",
"(",
"\"sum ~ result:\"",
",",
"result",
")",
";",
"return",
"sum",
";",
"}",
"sum",
"(",
"3",
",",
"7",
")",
";",
]
Y con esta información estamos listos para explorar como se crea un AST.
Program
Primero lo simple el código o programa anterior se puede dividir en 2 partes:
Una declaracion de función (Function Declaration) y una expresión de tipo llamada (Call Expression)
Function Declaration
function sum(numA, numB) {
const result = numA + numB;
console.log("sum ~ result:", result);
return sum;
}Expression Statement – Call Expression
sum(3, 7);Veamos como se compone cada uno.
Function Declaration
Function Declaration tiene 3 nodos hijos: id, params y body.
id
La palabra utilizada como identificador de la función. En este caso sum.
params
Hace referencia a otros 2 nodos de tipo id. Cada uno representa a las variables que se utilizan como parámetros en la función: numA y numB.
Si hubieramos definidio más argumentos para sum, aquí estarían.
body
El cuerpo (body) de la función es todo el código que se encuentra dentro de la misma
const result = numA + numB;
console.log("sum ~ result:", result);
return sum;Body – Block Statement
Tenemos 3 líneas dentro del nodo body.
Variable Declaration
const result = numA + numB;Expression Statement
console.log("sum ~ result:", result);Return Statement
return sum;Variable Declaration
La parte del arbol que corresponde a la declaración de varaible (Variable Declaration) es algo mas compleja de lo que uno esperaría.
Si observas hay un nodo llamado declarations. Pero a su vez ese hijo tiene un objeto llamado Variable Declarator. Parece un poco inútil, ¿no?
La realidad es que ese nodo de declarations podría tener mas hijos si hubieramos declarado más de una variable en una misma línea. Algo parecido a esto
const result = numA + numB, example = "example";*Serian 2 variables result y example cada 1 con diferentes valores asignados pero ambas declaradas con const.
Pero no es el caso. Asi que sigamos adelante con los nodos hijos del nodo Variable Declarator: id e init.
id
Así como anteriormente se identificó la palabra sum como tipo Identifier para guardar la referencia a la función , ahora se identifica la variable result como tipo Identifier para ser referenciada y guardar el valor de la operación.
init
Este objeto es de tipo expresión binaria (BinaryExpression) y define un operador + para utilizarlo en una operación. Dicha operación se compone de 2 partes, lo cual se expresa en sus nodos hijos:
left, right
Los valores izquierdo y derecho utilizados en la operacion. Respectivamente numA y numB.
Expression Statement
Este nodo contiene solo una expresión, la cual es una expresión de llamada (Call Expression).
A su vez la expresión cuenta con 2 propiedades:
callee
Representa la función llamada. En este caso tiene 2 nodos hijos:
object
La referencia al objeto que contiene a la función que se quiere llamar. console
property
La referencia a la función que se quiere llamar. log
arguments
Los argumentos que se pasan a la función.
En este caso estamos pasando 2 argumentos:
string literal
"sum ~ result:"id
La referencia a la variable result. Que se definio dentro del Variable Declarator anterior.
Return Statement
La expresión de retorno (return statement) solo regresa lo que hay en la variable de sum.
Expression Statement – Call Expression
Por último estos nodos corresponden a la última línea del código.
sum(3, 7);callee
La función que se llama es sum. La función no se encuentra definida dentro de otro objeto como fue el caso de console.log, por lo que este nodo es de tipo Identifier en vez de MemberExpression.
arguments
Los argumentos que se pasan a la función son 2 literales numéricos:
3, 7
Esto es un ejemplo de lo que es un AST. Su utilidad por supuesto va más alla de solo representar código. También es la forma en la que un lenguaje de programación lo convierte a lenguaje binario. En Javascript este AST sería el objeto que nuestro compilador o interpretador estaría esperando para poder realizar dicha conversión.
*Si no estas familiarizado con el tema de un compilador/intepretador puedes darte una idea con: Las diferencias entre un lenguaje compilado e interpretado en 10 minutos.
Es importante que tengas en en cuenta que a pesar de que el ejemplo de AST que vimos esta estructurado con los tipos de llamadas y variables esto no quiere decir que todos los ASTs de todos los lenguajes de programación sean así. Un árbol de este tipo contiene la información en cada nodo que se necesite. Esta información puede ser algo tan simple como los números que estaban en los ejemplos del principio o estructuras de datos mucho más complejas.