Árboles de sintaxis abstracta en programación: guía completa

Informatec Digital » Recursos » Árboles de sintaxis abstracta en programación: guía completa

Los árboles de sintaxis abstracta en programación son uno de esos conceptos que, al principio, suenan superteóricos, pero que en cuanto les pillas el truco ves que están por todas partes: compiladores, intérpretes, análisis de código, herramientas de refactorización, incluso en lenguajes de consulta sobre datos estructurados. Son, básicamente, la forma en la que una máquina «entiende» la estructura de un programa más allá del texto plano.

Aunque a veces se confunden con los árboles de análisis sintáctico clásicos, los AST tienen sus propias reglas del juego. Un árbol de sintaxis abstracta no es solo un dibujito bonito: es una estructura de datos compacta y muy bien pensada que elimina todo lo que sobra de la sintaxis concreta (paréntesis, comas, palabras clave redundantes…) y se queda con la chicha: qué operaciones se hacen, sobre qué valores y en qué orden.

Qué es exactamente un árbol de sintaxis abstracta (AST)

En teoría de lenguajes de programación, un árbol de sintaxis abstracta o AST (del inglés Abstract Syntax Tree) es una estructura en forma de árbol que representa la sintaxis de un programa, pero de manera simplificada respecto al árbol de análisis sintáctico concreto. Contiene la misma información esencial que el parse tree, solo que organizada de manera más compacta y manejable.

En un árbol de análisis sintáctico concreto (parse tree) aparecen todas las producciones de la gramática y todos los símbolos terminales, incluidos paréntesis, comas, puntos y coma y otros elementos puramente sintácticos. El AST, en cambio, elimina esos detalles que no aportan significado semántico y conserva únicamente la estructura lógica de las expresiones y sentencias.

En términos de implementación, un AST suele estar formado por objetos nodo con un tipo que indica de qué clase de construcción sintáctica se trata (constante, identificador, aplicación de función, operador binario, etc.), y propiedades adicionales que describen su contenido: valor, nombre, hijos, lista de argumentos y así sucesivamente.

La gracia del AST es que facilita fases posteriores del compilador o intérprete, como la comprobación de tipos, optimizaciones o generación de código, porque ofrece una visión limpia de la estructura del programa sin ruido sintáctico.

Diferencia entre árbol de sintaxis concreto y árbol de sintaxis abstracta

Para entender bien qué aporta un AST, conviene comparar primero el árbol de análisis sintáctico concreto con el abstracto. Imagina una gramática sencilla que reconoce expresiones aritméticas como «a + 4 * 5». El árbol de sintaxis concreto refleja de forma fiel la aplicación de cada regla de la gramática: símbolos no terminales, terminales, paréntesis, operadores, etc.

Ese árbol concreto suele ser profundo y con muchos nodos intermedios que solo sirven para respetar la estructura formal de la gramática. Por ejemplo, puede haber nodos para «Expresión», «Término», «Factor» y luego los símbolos terminales como «+», «*», identificadores y números. Cada producción se transforma en una rama del árbol, lo que aumenta la complejidad estructural.

El árbol de sintaxis abstracta para esa misma expresión, en cambio, se limita a representar las operaciones y operandos reales. Así, en vez de varios niveles de «Expresión» y «Término», podríamos tener un nodo raíz que representa la suma, con dos hijos: a la izquierda un identificador a y a la derecha un nodo de multiplicación cuyos hijos son los valores 4 y 5. Desaparecen nodos puramente gramaticales y se reordenan o condensan partes de la estructura.

Esto significa que el AST y el árbol de sintaxis concreto contienen la misma información semántica, pero el primero la presenta en una versión mucho más directa y compacta. Esa condensación es clave para trabajar eficientemente con el código en herramientas de análisis o ejecución.

Árboles y alfabetos con función de aridad

Para formalizar estos árboles desde un punto de vista matemático, se suele partir de la idea de alfabeto con función de aridad. En lugar de un conjunto de símbolos sin más, se define un alfabeto en el que a cada símbolo se le asocia un número que indica cuántos hijos puede tener en el árbol.

Un alfabeto con función de aridad es, de forma informal, un par formado por un conjunto finito de símbolos y una función que asigna a cada símbolo un número natural (incluido el cero). Ese número indica la aridad del símbolo: si vale 0, el símbolo actuará como hoja; si vale 1, se comportará como nodo unario; si vale 2, será binario; y así sucesivamente. También es habitual permitir símbolos de aridad variable para operadores como listas de argumentos.

Los símbolos de aridad 0 se corresponden con hojas del árbol (por ejemplo, constantes o identificadores). Los símbolos de aridad 1 se utilizan para construcciones que envuelven una sola expresión hija. Los de aridad 2 representan operaciones binarias clásicas como suma, producto, asignación, etc. Y los símbolos de aridad variable permiten modelar constructores que aceptan un número indeterminado de subárboles, como podría ser una llamada de función con múltiples parámetros.

A partir de este alfabeto con aridad se puede definir el conjunto de todos los árboles posibles: empezando por el árbol vacío (cuando se considere), añadiendo todos los símbolos de aridad 0 y variable, y extendiendo inductivamente: si un símbolo es k‑ario, puede situarse como nodo padre de k subárboles ya construidos. Con esto se obtiene el lenguaje de árboles (o término) asociado al alfabeto.

Lenguaje de árboles y noción de nodo

El conjunto de todos los árboles formados con un alfabeto y su función de aridad se denomina, en este contexto, lenguaje de árboles o términos. Es el equivalente, pero para estructuras arbóreas, de lo que el cierre de Kleene es para las cadenas de texto.

Del mismo modo que, cuando analizamos cadenas, hablamos de tokens para referirnos a las apariciones de símbolos del alfabeto dentro de una secuencia, al trabajar con árboles se suele hablar de nodos. Un nodo es, en esencia, una ocurrencia concreta de un símbolo del alfabeto con aridad ubicado en una posición determinada del árbol.

Desde ese punto de vista, este lenguaje de árboles es para los nodos lo mismo que el conjunto de cadenas es para las ocurrencias de tokens. Cada árbol se interpreta como una estructura construida paso a paso a partir del alfabeto, y los nodos son las piezas individuales que materializan físicamente los símbolos del mismo.

Esta forma de verlo resulta muy útil al diseñar analizadores sintácticos y generadores de AST, porque permite razonar sobre las reglas de construcción de dichos árboles de manera análoga a la gramática de cadenas, pero trabajando directamente sobre estructuras jerárquicas.

Aridad de los nodos en un AST concreto: el caso de Egg

Pasando de la teoría a un ejemplo práctico, muchos materiales docentes utilizan el lenguaje Egg para ilustrar la construcción y manejo de AST. En este contexto, se trabaja con varios tipos principales de nodos, cada uno con una aridad bien definida, lo que los hace muy claros de manipular.

En un AST típico de Egg, los nodos de tipo VALUE se consideran hojas: representan literales como cadenas de texto o números. No tienen hijos; solo almacenan un valor. De forma similar, los nodos de tipo WORD, que se usan para identificadores (nombres de variables, funciones, etc.), también se tratan como hojas con una propiedad que guarda el nombre.

El nodo clave en Egg es el tipo APPLY, que representa la aplicación de una función u operador. Este tipo de nodo tiene dos hijos conceptuales: por un lado, un hijo OPERATOR que apunta a la expresión que se aplica; y por otro, un hijo ARGS, que en realidad es un nodo especial de tipo ARRAY encargado de mantener una colección de subárboles, uno por cada argumento.

Los arrays, por tanto, son una forma natural de introducir aridad variable en el AST: un APPLY siempre tiene dos componentes (operador y lista de argumentos), pero esa lista interna puede contener cero, uno o muchos subárboles según la llamada concreta que se esté representando.

Anatomía detallada de los nodos del AST en Egg

A nivel de implementación, los nodos del AST de Egg suelen representarse como objetos con propiedades, lo que encaja perfectamente con lenguajes como JavaScript. Todos los nodos comparten una propiedad común: type, que identifica el tipo de nodo (VALUE, WORD, APPLY, ARRAY, etc.) y, por tanto, la estructura que tendrá el resto del objeto.

Los nodos de tipo VALUE se usan para constantes literales. Contienen una propiedad, a menudo llamada value, donde se almacena el número o la cadena de texto que representan. No tienen hijos adicionales, porque su contenido está completamente descrito por ese literal.

Los nodos de tipo WORD se reservan para los identificadores: nombres de variables, funciones, parámetros y similares. Suelen tener una propiedad name que guarda el identificador en forma de cadena. Igual que en el caso de VALUE, actúan como hojas del árbol, ya que su único cometido es aportar ese nombre.

Los nodos de tipo APPLY representan aplicaciones o llamadas. Incluyen una propiedad operator, que apunta a la expresión (otro nodo) que se está aplicando, y una propiedad args, que enlaza con un nodo de tipo ARRAY. Este último es un nodo particular dentro del AST, cuyo propósito es mantener la lista de argumentos de la aplicación.

El nodo ARRAY se puede entender como un contenedor estructurado de otros nodos, representando una secuencia de subárboles. Desde el punto de vista de la aridad, introduce flexibilidad, porque permite que bajo un mismo APPLY haya llamadas sin argumentos, con uno solo o con varios, sin tener que cambiar la definición del tipo de nodo principal.

Ejemplo de AST: aplicación simple con un valor

Para visualizar todo lo anterior, pensemos en la representación de una instrucción sencilla, como una aplicación de una función X con un único argumento 5. El AST generado por el parser se corresponde con un término construido con nodos VALUE, WORD y APPLY, siguiendo las reglas de Egg.

A nivel conceptual, tendríamos un nodo de tipo APPLY en la raíz. Su propiedad operator apuntaría a un nodo de tipo WORD cuyo nombre es X, y su propiedad args haría referencia a un nodo ARRAY que contiene un solo elemento: un nodo VALUE con valor numérico 5. De este modo, la estructura refleja con claridad quién se aplica y a qué se aplica.

Si quisiéramos hacer explícitos todos los atributos, podríamos escribir una notación más detallada donde se vean el type, operator, args, name y value. Esa notación más verborreica es muy útil para depurar el parser o para entender cómo se traduce una expresión textual en un objeto árbol dentro del intérprete.

En implementaciones reales, este árbol se suele serializar como JSON para poder almacenarlo, transmitirlo o inspeccionarlo fácilmente. De hecho, existen herramientas y módulos, como el paquete evm2term en el ecosistema npm, que permiten obtener representaciones compactas de estos AST para analizarlos o transformarlos con mayor comodidad.

Ejemplo de AST: suma con multiplicación anidada

Otro caso típico es una expresión algo más compleja, del estilo «+(a, *(4, 5))». Aquí tenemos una operación de suma cuyo primer argumento es el identificador a y cuyo segundo argumento es el resultado de una multiplicación de 4 por 5. El AST que surge de esta expresión refleja esa estructura anidada.

En la raíz del árbol, tendríamos de nuevo un nodo APPLY que representa la operación de suma. Su operador sería un nodo WORD con nombre «+», mientras que sus argumentos estarían en un nodo ARRAY con dos elementos: el primero, un WORD con nombre «a»; el segundo, otro nodo APPLY que representa la multiplicación.

Ese segundo APPLY tendría como operador un WORD con nombre «*» y como args un ARRAY con dos nodos VALUE: uno con valor 4 y otro con valor 5. Vista en conjunto, la estructura muestra claramente que el orden de evaluación consiste en multiplicar 4 por 5 y después sumar el resultado a a.

Si ampliamos la notación para incluir todos los atributos, veríamos reflejados los tipos de todos los nodos, sus nombres o valores concretos y las relaciones entre ellos. Esta descripción explícita se corresponde con la implementación real en el intérprete de Egg, donde cada nodo es un objeto con las propiedades mencionadas.

Gramática de árboles y gramática del parser

La forma en la que se generan estos AST no es arbitraria: se basa en lo que se denomina una Gramática Árbol. En una formulación típica, una gramática de este tipo se define como una cuádrupla compuesta por un alfabeto con aridad, un conjunto finito de variables sintácticas (no terminales), un conjunto finito de reglas de producción y un símbolo de arranque.

En cada regla de producción, una variable se reemplaza por un árbol cuya raíz es un símbolo del alfabeto con aridad, y cuyos hijos son a su vez variables o árboles ya definidos. Esta estructura recuerda a las gramáticas regulares o libres de contexto clásicas, pero adaptada a la generación directa de árboles en lugar de cadenas de símbolos.

Relacionada con esa definición más formal, encontramos la gramática específica que utiliza el parser de Egg para producir sus árboles. Dicha gramática, que suele exponerse de forma informal en la documentación, describe exactamente qué combinaciones de palabras clave, operadores, paréntesis y demás se aceptan en el lenguaje y cómo se traducen en nodos de tipo VALUE, WORD, APPLY y ARRAY.

Esta gramática de árboles puede verse como un caso particular de lo que en la literatura se conoce como Regular Tree Grammar. La idea es disponer de reglas bien definidas para pasar de una secuencia de tokens de entrada a un AST estructurado que luego pueda ser interpretado o compilado.

Notación de Dewey: coordenadas dentro de un árbol

Una vez que tenemos el AST, muchas veces necesitamos referirnos a subárboles concretos: por ejemplo, el segundo argumento de una función, el operador de una expresión, etc. Una forma muy elegante de hacerlo es la llamada notación de Dewey, que toma prestado el esquema usado para numerar secciones y subsecciones en documentos.

En esta notación, a partir de un árbol t, un subárbol se denota con una cadena de números separados por puntos. Cada número indica la posición de un hijo (normalmente empezando en 1) y se va bajando por la estructura. Así, una expresión como t/2.1.3 se refiere al tercer hijo del primer hijo del segundo hijo de t.

La definición inductiva de esta notación es sencilla: la cadena vacía hace referencia al propio árbol completo; si una cadena consta de un número seguido de más números separados por puntos, se interpreta tomando primero el subárbol hijo correspondiente al índice indicado y, a continuación, aplicando la misma lógica recursivamente al resto de la cadena.

Por ejemplo, si tenemos un árbol t que representa una expresión como «+(a, *(4,5))», con un nodo raíz APPLY para la suma, un hijo WORD con nombre «+» y otro hijo APPLY para la multiplicación, podemos identificar posiciones concretas. Así, t/1 podría ser el nodo WORD con el operador «+», t/2.1 el identificador «a» y t/2.2.2.1 el VALUE con valor 4, si numeramos los hijos de manera adecuada.

Esta forma de dar «coordenadas» dentro de un AST resulta muy útil para señalar ubicaciones específicas al informar de errores, navegar por el árbol o aplicar transformaciones locales sobre nodos determinados sin ambigüedades.

Notaciones equivalentes en programación y herramientas

La idea detrás de la notación de Dewey no es exclusiva de la teoría de árboles; en realidad, aparece repetida en muchas notaciones prácticas que usamos a diario en programación y manejo de datos estructurados, aunque no siempre seamos conscientes.

Cuando en un lenguaje de programación escribimos expresiones con el operador punto, como objeto.propiedad.subpropiedad, estamos haciendo algo muy similar: caminar por un árbol de objetos anidados, seleccionando en cada paso un hijo mediante un nombre en vez de por un número de posición. A partir de un nodo raíz, vamos descendiendo hacia nodos más internos.

El mismo patrón aparece en los sistemas de archivos tipo Unix, donde se emplea el operador barra (/) para separar directorios: /src/js/tutu.js describe un camino desde la raíz del sistema de archivos hasta un recurso concreto, atravesando sucesivos niveles de una estructura en árbol.

En el mundo de los documentos estructurados, lenguajes como XPath utilizan notaciones muy parecidas para seleccionar nodos dentro de un árbol XML. Una consulta del estilo «A//B/*» elige el primer hijo (sea cual sea su nombre) de cada elemento B que sea descendiente de un elemento A en la posición adecuada respecto al contexto actual, empleando barras simples y dobles para indicar niveles de profundidad.

Otra herramienta conocida, el lenguaje jq, usa un sistema paralelo para navegar por estructuras JSON, permitiendo seleccionar subobjetos mediante rutas compuestas, filtros y expresiones. Todas estas notaciones no dejan de ser formas distintas de expresar rutas en un árbol, muy en la línea de lo que propone la notación de Dewey pero adaptadas a sus respectivos dominios.

Árboles de análisis sintáctico en lingüística y programación

Más allá del mundo de los compiladores, los árboles de sintaxis se utilizan también en lingüística para representar la estructura de las oraciones. Allí se habla de árboles de derivación o parse trees, que muestran cómo se descompone una frase en sintagmas, palabras y categorías gramaticales.

En estos árboles, igual que en programación, encontramos tres tipos de nodos básicos: un nodo raíz, que representa la oración completa o la estructura global; nodos internos o de ramificación, que funcionan como nodos padre y agrupan subconjuntos de la frase; y nodos hoja, que suelen corresponder a las palabras concretas que aparecen en la cadena de entrada.

El nodo raíz es único: toda la estructura del árbol cuelga de él. Los nodos de ramificación se sitúan inmediatamente por debajo de la raíz o de otros nodos padre, y sirven para organizar jerárquicamente las partes de la frase o del programa. Los nodos hoja, por su parte, se encuentran en el último nivel del árbol y no tienen hijos, cerrando la derivación.

Estos árboles se consideran herramientas pedagógicas potentes, porque ayudan a descomponer frases complejas en elementos manejables. En programación pasa lo mismo: un AST bien construido permite ver de un vistazo qué operaciones se encadenan, qué expresiones están anidadas y cómo fluye la evaluación.

En función del objetivo del análisis, podemos encontrar distintos tipos de árboles de análisis. Algunos hacen énfasis en las dependencias entre palabras o componentes (por ejemplo, quién depende de quién en una oración), mientras que otros se centran en la agrupación en sintagmas o constituyentes, lo que da lugar a dos familias principales.

Árboles de sintaxis por dependencia y por circunscripción

Uno de los tipos más conocidos es el árbol de sintaxis basado en la dependencia. En esta variante, todas las palabras de la frase o todos los elementos relevantes se tratan como nodos hoja, y los enlaces entre ellos indican relaciones de dependencia directa (por ejemplo, un verbo principal y su sujeto). Como consecuencia, suelen producirse árboles con menos nodos que en otros esquemas.

Esta simplicidad los hace especialmente cómodos para principiantes y para determinadas tareas de procesamiento del lenguaje, porque la estructura se centra en quién depende de quién sin introducir tantos nodos intermedios. Aplicado a programación, la idea recuerda a quedarse únicamente con las relaciones esenciales, obviando adornos gramaticales.

En el otro extremo tenemos los árboles de sintaxis basados en la circunscripción o en constituyentes, que sí distinguen entre nodo raíz, nodos internos de ramificación y nodos hoja, y hacen visibles todas las agrupaciones relevantes. Estos árboles suelen contener más nodos y reflejan con mayor detalle la estructura jerárquica de la frase o el programa.

Las plantillas de árboles de circunscripción que se ven habitualmente muestran frases largas con numerosos nodos hoja, varios niveles de ramificación y un nodo raíz bien definido. Son especialmente útiles para destripar oraciones complejas o programas en varias capas de estructuras anidadas.

En ambos casos, tanto en árboles de dependencia como de circunscripción, se pueden encontrar ejemplos y recursos visuales preparados como plantillas, que permiten simplemente rellenar los nodos con la información deseada. Esto ahorra tiempo y evita tener que diseñar el esquema de cero cada vez que se quiere ilustrar una estructura.

Aplicaciones prácticas y herramientas relacionadas con los AST

Los AST no son solo un concepto teórico: se utilizan activamente en un montón de herramientas del día a día de cualquier persona que trabaje con código. Compiladores, intérpretes, minificadores, formateadores de código y analizadores estáticos parten casi siempre de un AST para realizar su trabajo.

Un compilador típico toma el código fuente, lo tokeniza, lo parsea y genera un árbol de sintaxis abstracta. A partir de ahí, realiza comprobaciones semánticas (tipos, alcance de variables, usos incorrectos de construcciones) y aplica optimización de código recorriendo y transformando el AST, antes de producir código máquina o bytecode.

Herramientas como linters o formateadores trabajan también sobre AST: analizan la estructura para detectar patrones problemáticos, malas prácticas o incoherencias y proponen cambios que mantienen la estructura semántica del árbol pero ajustan la presentación del código.

En el ecosistema JavaScript, por ejemplo, existen múltiples librerías que exponen el AST en formato JSON, facilitando que otras herramientas se apoyen en él para hacer refactorizaciones, generar documentación automática o crear visualizaciones de la estructura de programas complejos.

Incluso en ámbitos algo más especializados, como la instrumentación para medir cobertura de tests o la transformación de código fuente en otros lenguajes, el AST es la base sobre la que se apoyan muchas soluciones modernas, ya que permite trabajar a un nivel de abstracción muy cómodo entre el texto bruto y el código máquina.

En conjunto, los árboles de sintaxis abstracta son la pieza clave que conecta la gramática formal de un lenguaje, su representación interna en el compilador o intérprete y las herramientas avanzadas que usamos para escribir, analizar y transformar código de forma segura y eficiente. Comprender cómo se construyen, cómo se navega por ellos (con ideas como la notación de Dewey) y qué tipos de nodos intervienen (VALUE, WORD, APPLY, estructuras de aridad fija o variable, etc.) ayuda a ver con mucha más claridad qué está haciendo realmente la máquina cuando procesa un programa.