Arbres de syntaxe abstraite en programmation : un guide complet

Informatec Digital » Ressources » Arbres de syntaxe abstraite en programmation : un guide complet

Les arbres de syntaxe abstraite en programmation font partie de ces concepts qui paraissent de prime abord très théoriques, mais une fois assimilés, on se rend compte de leur omniprésence : compilateurs, interpréteurs , analyse de code, outils de refactoring, et même langages de requêtes de données structurées. Ils constituent, en substance, la manière dont une machine « comprend » la structure d’un programme au-delà du simple texte.

Bien que parfois confondus avec les arbres d'analyse syntaxique classiques, les arbres de syntaxe abstraite (AST) possèdent leurs propres règles. Un arbre de syntaxe abstraite n'est pas qu'un simple schéma : c'est une structure de données compacte et bien conçue qui élimine tout élément superflu de la syntaxe concrète (parenthèses, virgules, mots-clés redondants, etc.) et se concentre sur l'essentiel : quelles opérations sont effectuées, sur quelles valeurs et dans quel ordre.

Qu'est-ce qu'un arbre de syntaxe abstraite (AST) exactement ?

En théorie des langages de programmation, un arbre de syntaxe abstraite (AST) est une structure arborescente qui représente la syntaxe d'un programme, mais sous une forme simplifiée par rapport à un arbre d'analyse syntaxique concret. Il contient les mêmes informations essentielles qu'un arbre d'analyse syntaxique, mais organisées de manière plus compacte et plus facile à gérer.

Un arbre d'analyse syntaxique contient toutes les productions grammaticales et tous les symboles terminaux, y compris les parenthèses, les virgules, les points-virgules et autres éléments purement syntaxiques. L'AST, en revanche, supprime ces détails qui n'apportent pas de sens sémantique et ne conserve que la structure logique des expressions et des phrases.

En termes d'implémentation, un AST est généralement composé d' objets nœuds avec un type qui indique le type de construction syntaxique qu'il représente (constante, identificateur, application de fonction, opérateur binaire, etc.), et des propriétés supplémentaires qui décrivent son contenu : valeur, nom, enfants, liste d'arguments, etc.

L'avantage de l'AST est qu'il facilite les phases ultérieures du compilateur ou de l'interpréteur, telles que la vérification des types, les optimisations ou la génération de code , car il offre une vue claire de la structure du programme sans bruit syntaxique.

Différence entre un arbre de syntaxe concrète et un arbre de syntaxe abstraite

Pour bien comprendre l'apport d'un arbre syntaxique abstrait (AST), il est utile de comparer d'abord son arbre d'analyse syntaxique concret avec son arbre abstrait. Prenons l'exemple d'une grammaire simple qui reconnaît des expressions arithmétiques comme « a + 4 * 5 » . L'arbre d'analyse syntaxique concret reflète fidèlement l'application de chaque règle grammaticale : symboles non terminaux, terminaux, parenthèses, opérateurs, etc.

Cet arbre particulier est généralement profond et comporte de nombreux nœuds intermédiaires qui servent uniquement à maintenir la structure formelle de la grammaire. Par exemple, il peut y avoir des nœuds pour « Expression », « Terme », « Facteur », puis des symboles terminaux comme « + » , « * » , des identificateurs et des nombres. Chaque production devient une branche de l'arbre, augmentant ainsi sa complexité structurelle.

L'arbre de syntaxe abstraite de cette même expression, en revanche, se limite à la représentation des opérations et des opérandes proprement dits . Ainsi, au lieu de plusieurs niveaux d'« Expression » et de « Terme », on pourrait avoir un nœud racine représentant l'addition, avec deux enfants : à gauche, un identificateur « a » et à droite, un nœud de multiplication dont les enfants sont les valeurs 4 et 5. Les nœuds purement grammaticaux disparaissent et certaines parties de la structure sont réorganisées ou condensées.

Cela signifie que l'arbre de syntaxe abstraite (AST) et l'arbre syntaxique concret contiennent les mêmes informations sémantiques , mais que le premier les présente sous une forme beaucoup plus directe et compacte. Cette condensation est essentielle pour travailler efficacement avec du code dans les outils d'analyse ou d'exécution.

Arbres et alphabets avec fonction d'arité

Pour formaliser ces arbres d'un point de vue mathématique, on utilise généralement l'idée d'un alphabet muni d'une fonction d'arité . Au lieu d'un simple ensemble de symboles, on définit un alphabet dans lequel chaque symbole est associé à un nombre indiquant le nombre d'enfants qu'il peut avoir dans l'arbre.

Un alphabet muni d'une fonction d'arité est, de manière informelle, un couple composé d'un ensemble fini de symboles et d'une fonction qui associe à chaque symbole un nombre naturel (y compris zéro). Ce nombre indique l'arité du symbole : s'il vaut 0, le symbole se comporte comme une feuille ; s'il vaut 1, il se comporte comme un nœud unaire ; s'il vaut 2, il est binaire ; et ainsi de suite. Il est également courant d'autoriser des symboles d'arité variable pour les opérateurs en tant que listes d'arguments.

Les symboles d'arité 0 correspondent aux feuilles de l'arbre (par exemple, les constantes ou les identificateurs). Les symboles d'arité 1 sont utilisés pour les constructions ne comportant qu'une seule expression enfant. Les symboles d'arité 2 représentent les opérations binaires classiques telles que l'addition, la multiplication, l'affectation, etc. Enfin, les symboles d'arité variable permettent de modéliser des constructions acceptant un nombre indéterminé de sous-arbres, comme un appel de fonction à plusieurs paramètres.

À partir de cet alphabet d'arité k, on définit l'ensemble de tous les arbres possibles : en partant de l' arbre vide (lorsqu'il est considéré), en ajoutant tous les symboles d'arité 0 et variable, et en procédant par induction : si un symbole est k-aire, il peut être placé comme nœud parent de k sous-arbres déjà construits. On obtient ainsi le langage arborescent (ou terme) associé à l'alphabet.

Langage arborescent et notion de nœud

L'ensemble de tous les arbres formés à partir d'un alphabet et de sa fonction d'arité est appelé, dans ce contexte, langage arborescent ou langage de termes . Il est l'équivalent, pour les structures arborescentes, de la fermeture de Kleene pour les chaînes de caractères.

De même que, lors de l'analyse de chaînes de caractères, on utilise le terme « tokens » pour désigner les occurrences de symboles alphabétiques au sein d'une séquence, lorsqu'on travaille avec des arbres, on utilise généralement le terme « nœuds » . Un nœud est, en substance, une occurrence spécifique d'un symbole alphabétique, caractérisée par une arité donnée, située à une position particulière dans l'arbre.

Dans cette perspective, ce langage arborescent est aux nœuds ce qu'un ensemble de chaînes de caractères est aux occurrences de symboles. Chaque arbre est interprété comme une structure construite étape par étape à partir de l'alphabet, et les nœuds sont les éléments individuels qui matérialisent physiquement ses symboles.

Cette façon d'envisager les choses est très utile lors de la conception d'analyseurs syntaxiques et de générateurs d'AST , car elle permet de raisonner sur les règles de construction de ces arbres d'une manière analogue à la grammaire des chaînes de caractères, mais en travaillant directement sur des structures hiérarchiques.

Arité des nœuds dans un AST spécifique : le cas d’Egg

Passant de la théorie à la pratique, de nombreux supports pédagogiques utilisent le langage Egg pour illustrer la construction et la manipulation des AST. Dans ce contexte, plusieurs types de nœuds principaux sont utilisés, chacun ayant une arité bien définie , ce qui facilite grandement leur manipulation.

Dans un arbre de syntaxe abstraite (AST) Egg classique, les nœuds VALUE sont considérés comme des feuilles : ils représentent des littéraux tels que des chaînes de caractères ou des nombres. Ils n’ont pas d’enfants ; ils stockent uniquement une valeur. De même, les nœuds WORD , utilisés pour les identificateurs (noms de variables, noms de fonctions, etc.), sont également traités comme des feuilles possédant une propriété stockant le nom.

Dans Egg, le nœud clé est de type APPLY , qui représente l'application d'une fonction ou d'un opérateur. Ce type de nœud possède deux enfants conceptuels : un enfant OPERATOR qui pointe vers l'expression appliquée ; et un enfant ARGS , qui est en réalité un nœud ARRAY spécial chargé de maintenir une collection de sous-arbres, un pour chaque argument.

Les tableaux constituent donc un moyen naturel d'introduire une arité variable dans l'AST : un APPLY comporte toujours deux composants (opérateur et liste d'arguments), mais cette liste interne peut contenir zéro, un ou plusieurs sous-arbres selon l'appel spécifique représenté.

Anatomie détaillée des ganglions AST dans l'œuf

Au niveau de l'implémentation, les nœuds AST d'Egg sont généralement représentés comme des objets dotés de propriétés , ce qui convient parfaitement aux langages comme JavaScript. Tous les nœuds partagent une propriété commune : `type` , qui identifie le type du nœud (VALUE, WORD, APPLY, ARRAY, etc.) et, par conséquent, la structure du reste de l'objet.

Les nœuds VALUE sont utilisés pour les constantes littérales . Ils contiennent une propriété, souvent appelée valeur , où est stocké le nombre ou la chaîne de caractères qu'ils représentent. Ils n'ont pas d'enfants supplémentaires car leur contenu est entièrement décrit par cette valeur littérale.

Les nœuds de type « mot » sont réservés aux identificateurs : noms de variables, de fonctions, de paramètres, etc. Ils possèdent généralement une propriété `name` qui stocke l’identificateur sous forme de chaîne de caractères. À l’instar des nœuds de type « valeur », ils jouent le rôle de feuilles dans l’arbre, leur unique fonction étant de fournir ce nom.

Les nœuds Apply représentent des applications ou des appels. Ils comprennent une propriété operator , qui pointe vers l'expression (un autre nœud) appliquée, et une propriété args , qui renvoie vers un nœud ARRAY. Ce dernier est un nœud spécifique de l'AST, dont le rôle est de contenir la liste des arguments de l'application .

Le nœud ARRAY peut être vu comme un conteneur structuré pour d'autres nœuds, représentant une séquence de sous-arbres. Du point de vue de l'arité, il offre une grande flexibilité car il permet des appels sans argument, avec un argument ou avec plusieurs arguments au sein d'une même instruction APPLY, sans qu'il soit nécessaire de modifier la définition du type de nœud principal.

Exemple d'AST : application simple avec une seule valeur

Pour visualiser tout ce qui précède, pensons à la représentation d'une instruction simple, telle qu'une application d'une fonction X avec un seul argument 5. L'AST généré par l'analyseur syntaxique correspond à un terme construit avec des nœuds VALUE, WORD et APPLY , suivant les règles d'Egg.

Conceptuellement, nous aurions un nœud APPLY à la racine. Sa propriété operator pointerait vers un nœud WORD nommé X, et sa propriété args ferait référence à un nœud ARRAY contenant un seul élément : un nœud VALUE avec la valeur numérique 5. Ainsi, la structure reflète clairement à qui et à quoi s’applique la requête.

Si nous souhaitions expliciter tous les attributs, nous pourrions utiliser une notation plus détaillée indiquant le type, l'opérateur, les arguments, le nom et la valeur. Cette notation plus verbeuse est très utile pour déboguer l'analyseur syntaxique ou pour comprendre comment une expression textuelle est traduite en un objet arborescent au sein de l'interpréteur.

Dans la pratique, cet arbre est généralement sérialisé au format JSON pour faciliter son stockage, sa transmission et son analyse. De fait, des outils et modules, comme le package evm2term de l'écosystème npm, offrent des représentations compactes de ces AST pour simplifier leur analyse et leur transformation.

Exemple d'AST : addition et multiplication imbriquées

Un autre cas typique est une expression légèrement plus complexe, telle que « +(a, *(4, 5)) » . Il s'agit ici d'une opération d'addition dont le premier argument est l'identifiant a et le second le résultat de la multiplication de 4 par 5. L'AST résultant de cette expression reflète cette structure imbriquée.

À la racine de l'arbre, nous aurions à nouveau un nœud APPLY représentant l'opération d'addition. Son opérateur serait un nœud WORD nommé « + », tandis que ses arguments seraient dans un nœud ARRAY avec deux éléments : le premier, un nœud WORD nommé « a » ; le second, un autre nœud APPLY représentant la multiplication.

Cette deuxième fonction APPLY aurait pour opérateur un mot nommé « * » et pour arguments un tableau avec deux nœuds VALUE : l’un avec une valeur de 4 et l’autre avec une valeur de 5. Vue dans son ensemble, la structure montre clairement que l’ordre d’évaluation consiste à multiplier 4 par 5 puis à ajouter le résultat à a.

Si l'on étend la notation à tous les attributs, on verrait les types de tous les nœuds, leurs noms ou valeurs spécifiques, et les relations entre eux. Cette description explicite correspond à l'implémentation réelle dans l'interpréteur Egg, où chaque nœud est un objet possédant les propriétés susmentionnées.

Grammaire arborescente et grammaire d'analyse syntaxique

La méthode de génération de ces AST n'est pas arbitraire : elle repose sur ce que l'on appelle une grammaire arborescente . Dans une formulation typique, une telle grammaire est définie comme un quadruplet composé d'un alphabet d'arité n, d'un ensemble fini de variables syntaxiques (non terminales), d'un ensemble fini de règles de production et d'un symbole initial.

Dans chaque règle de production, une variable est remplacée par un arbre dont la racine est un symbole de l'alphabet muni d'une arité, et dont les enfants sont eux-mêmes des variables ou des arbres déjà définis. Cette structure rappelle les grammaires régulières ou hors contexte classiques, mais adaptée à la génération directe d'arbres plutôt que de chaînes de symboles.

Liée à cette définition plus formelle, la grammaire spécifique utilisée par l'analyseur syntaxique d'Egg pour générer ses arbres est décrite ci-dessous. Cette grammaire, généralement présentée de manière informelle dans la documentation, détaille les combinaisons de mots-clés, d'opérateurs, de parenthèses, etc., acceptées par le langage et leur traduction en nœuds de type VALUE, WORD, APPLY et ARRAY.

Cette grammaire arborescente peut être considérée comme un cas particulier de ce que l'on appelle dans la littérature une grammaire arborescente régulière . L'idée est de disposer de règles bien définies pour convertir une séquence de jetons d'entrée en un AST structuré, qui peut ensuite être interprété ou compilé.

Notation Dewey : coordonnées à l’intérieur d’un arbre

Une fois l'AST obtenu, nous avons souvent besoin de faire référence à des sous-arbres spécifiques : par exemple, le deuxième argument d'une fonction, l'opérateur d'une expression, etc. Une manière très élégante de procéder est la notation décimale de Dewey, qui reprend le système utilisé pour numéroter les sections et les sous-sections des documents.

Dans cette notation, à partir d'un arbre t, un sous-arbre est représenté par une suite de nombres séparés par des points . Chaque nombre indique la position d'un enfant (généralement à partir de 1) et la séquence se parcourt dans l'arbre. Ainsi, une expression comme t/2.1.3 désigne le troisième enfant du premier enfant du deuxième enfant de t.

La définition inductive de cette notation est simple : la chaîne vide fait référence à l’arbre entier lui-même ; si une chaîne est composée d’un nombre suivi d’autres nombres séparés par des points, elle est interprétée en prenant d’abord le sous-arbre enfant correspondant à l’indice indiqué, puis en appliquant la même logique de manière récursive au reste de la chaîne.

Par exemple, si nous avons un arbre t représentant une expression comme « +(a, *(4,5)) », avec un nœud racine APPLY pour l'addition, un nœud enfant WORD nommé « + » et un autre nœud enfant APPLY pour la multiplication, nous pouvons identifier des positions spécifiques. Ainsi, t/1 pourrait être le nœud WORD avec l'opérateur « + », t/2.1 l'identificateur « a » et t/2.2.2.1 le nœud VALUE avec la valeur 4, si nous numérotons correctement les enfants.

Cette manière de fournir des « coordonnées » au sein d'un AST est très utile pour indiquer des emplacements précis lors du signalement d'erreurs, de la navigation dans l'arbre ou de l'application de transformations locales à des nœuds spécifiques sans ambiguïté.

Notations équivalentes en programmation et outils

L'idée derrière la notation de Dewey n'est pas exclusive à la théorie des arbres ; en fait, elle apparaît à maintes reprises dans de nombreuses notations pratiques que nous utilisons quotidiennement en programmation et en traitement de données structurées, même si nous n'en sommes pas toujours conscients.

Lorsque nous écrivons des expressions avec l' opérateur point dans un langage de programmation , comme objet.propriété.sous-propriété, nous effectuons une opération très similaire : parcourir un arbre d'objets imbriqués, en sélectionnant un enfant à chaque étape par son nom plutôt que par son numéro de position. En partant d'un nœud racine, nous descendons vers des nœuds plus internes.

Le même modèle apparaît dans les systèmes de fichiers de type Unix, où l' opérateur de barre oblique (/) est utilisé pour séparer les répertoires : /src/js/tutu.js décrit un chemin de la racine du système de fichiers vers une ressource spécifique, en traversant les niveaux successifs d'une structure arborescente.

Dans le monde des documents structurés, des langages comme XPath utilisent des notations très similaires pour sélectionner des nœuds au sein d'une arborescence XML. Une requête telle que « A//B/* » sélectionne le premier enfant (quel que soit son nom) de chaque élément B descendant d'un élément A à la position appropriée dans le contexte actuel, en utilisant des barres obliques simples et doubles pour indiquer les niveaux de profondeur.

Un autre outil bien connu, le langage jq , utilise un système parallèle pour parcourir les structures JSON, permettant la sélection de sous-objets via des chemins composites, des filtres et des expressions. Toutes ces notations ne sont que différentes manières d'exprimer les chemins dans un arbre , très proches de la notation décimale de Dewey mais adaptées à leurs domaines respectifs.

Arbres d'analyse syntaxique en linguistique et en programmation

En dehors du domaine de la compilation, les arbres syntaxiques sont également utilisés en linguistique pour représenter la structure des phrases. On les appelle alors arbres de dérivation ou arbres d'analyse syntaxique ; ils montrent comment une phrase est décomposée en syntagmes, mots et catégories grammaticales.

Dans ces arbres, tout comme en programmation, on trouve trois types de nœuds de base : un nœud racine , qui représente la phrase complète ou la structure globale ; des nœuds internes ou de ramification, qui fonctionnent comme des nœuds parents et regroupent des sous-ensembles de la phrase ; et des nœuds feuilles, qui correspondent généralement aux mots spécifiques qui apparaissent dans la chaîne d’entrée.

Le nœud racine est unique : toute la structure arborescente en est rattachée. Les nœuds de branchement se situent immédiatement en dessous de la racine ou d’autres nœuds parents et servent à organiser hiérarchiquement les parties de la phrase ou du programme. Les nœuds feuilles, quant à eux, se trouvent au niveau le plus bas de l’arbre et n’ont pas d’enfants, fermant ainsi la structure arborescente.

Ces arbres sont considérés comme de puissants outils pédagogiques car ils permettent de décomposer les phrases complexes en éléments plus faciles à gérer. Il en va de même pour la programmation : un AST bien construit permet de voir d’un coup d’œil quelles opérations sont enchaînées, quelles expressions sont imbriquées et comment se déroule l’évaluation.

Selon l'objectif de l'analyse, on distingue différents types d' arbres d'analyse . Certains mettent l'accent sur les dépendances entre les mots ou les composants (par exemple, qui dépend de qui dans une phrase), tandis que d'autres se concentrent sur le regroupement en syntagmes ou en constituants, ce qui donne lieu à deux grandes familles.

Arbres syntaxiques par dépendance et par constituant

L'un des types les plus connus est l' arbre syntaxique basé sur les dépendances . Dans cette variante, tous les mots de la phrase ou tous les éléments pertinents sont traités comme des nœuds terminaux, et les liens entre eux indiquent des relations de dépendance directe (par exemple, un verbe principal et son sujet). De ce fait, on obtient souvent des arbres comportant moins de nœuds que dans d'autres schémas.

Cette simplicité les rend particulièrement pratiques pour les débutants et pour certaines tâches de traitement du langage, car la structure met l'accent sur les dépendances sans introduire de nombreux nœuds intermédiaires. Appliquée à la programmation, l'idée est de ne retenir que les relations essentielles, en omettant les fioritures grammaticales.

À l'autre extrême, on trouve les arbres syntaxiques basés sur les constituants, qui distinguent les nœuds racines, les nœuds de ramification internes et les nœuds feuilles, et rendent visibles tous les groupements pertinents. Ces arbres contiennent généralement plus de nœuds et reflètent plus précisément la structure hiérarchique de la phrase ou du programme.

Les modèles d'arbres de constituants les plus courants présentent de longues phrases comportant de nombreux nœuds terminaux, plusieurs niveaux de ramification et un nœud racine bien défini. Ils sont particulièrement utiles pour analyser des phrases complexes ou des programmes comportant de multiples structures imbriquées.

Dans les arbres de dépendance et les arbres de constituants, des exemples et des ressources visuelles sont disponibles sous forme de modèles, vous permettant de renseigner facilement les nœuds avec les informations souhaitées. Cela représente un gain de temps et évite de devoir concevoir le diagramme de A à Z à chaque fois que vous souhaitez illustrer une structure.

Applications pratiques et outils liés à l'AST

Les AST ne sont pas qu'un concept théorique : ils sont activement utilisés dans une multitude d' outils du quotidien par tous ceux qui travaillent avec du code. Les compilateurs, les interpréteurs, les minificateurs, les formateurs de code et les analyseurs statiques s'appuient presque toujours sur un AST pour fonctionner.

Un compilateur classique prend le code source, le tokenise, l'analyse syntaxique et génère un arbre de syntaxe abstraite. À partir de là, il effectue des vérifications sémantiques (types, portée des variables, utilisation incorrecte des constructions) et optimise le code en parcourant et en transformant l'arbre de syntaxe abstraite avant de produire le code machine, ou bytecode.

Des outils tels que les linters ou les formateurs fonctionnent également sur l'AST : ils analysent la structure pour détecter les schémas problématiques, les mauvaises pratiques ou les incohérences et proposent des modifications qui maintiennent la structure sémantique de l'arbre tout en ajustant la présentation du code.

Dans l'écosystème JavaScript, par exemple, il existe de nombreuses bibliothèques qui exposent l'AST au format JSON, ce qui permet à d'autres outils de s'en servir pour effectuer des refactorisations, générer une documentation automatique ou créer des visualisations de la structure de programmes complexes.

Même dans des domaines un peu plus spécialisés, comme l'instrumentation pour mesurer la couverture des tests ou la transformation du code source en d'autres langages, l'AST constitue le fondement sur lequel reposent de nombreuses solutions modernes, car il permet de travailler à un niveau d'abstraction très confortable entre le texte brut et le code machine.

Les arbres de syntaxe abstraite constituent l'élément clé qui relie la grammaire formelle d'un langage, sa représentation interne dans le compilateur ou l'interpréteur, et les outils avancés utilisés pour écrire, analyser et transformer du code de manière sûre et efficace. Comprendre leur construction, savoir s'y repérer (grâce à des concepts comme la notation décimale de Dewey) et identifier les types de nœuds impliqués (VALEUR, MOT, APPLIQUER, structures d'arité fixe ou variable, etc.) permet de mieux appréhender le fonctionnement réel de la machine lors de l'exécution d'un programme.