La syntaxe pousse sur les arbres

Arbres de syntaxe abstraits

Il y a plusieurs façons de considérer le code informatique. La plus évidente est de le voir comme du texte, forme écrite d’un langage de programmation que la machine comprend et peut exécuter. Mais si l’on veut raisonner sur le code, comme nous l’avons fait avec l’analyse de durée de vie, il nous faut une représentation du code plus abstraite qui nous permette de raisonner sur les variables et les instructions. Plus généralement, nous allons découvrir comment est-ce que l’on définit un langage de programmation.

Un nouveau langage

Pour la première fois, nous allons définir notre propre langage de programmation. Celui-ci sera très simple, mais nous permettra de mieux comprendre comment un simple fichier contenant du texte peut être interprété comme un programme informatique. Dans notre langage qui opérera uniquement sur des entiers, on pourra :

  • additionner et soustraire des expressions;
  • assigner une expression à une variable;
  • retourner un expression à la fin du programme.

Maintenant que nous avons définit ce que notre langage peut faire, il nous faut décider d’une manière d’écrire ce langage dans un fichier test. Plus formellement, ceci va définir la syntaxe de notre langage, et nous avons un certain degré de liberté dans nos choix. Par exemple, on pourrait choisir de noter « la valeur 3 plus y est assignée à x » par x y 3 + := (en notation polonaise inverse pour les connaisseurs). Mais ce qui doit guider notre choix est avant tout la lisibilité du code pour le programmeur, qui nous pousse à définir des opérateurs infixes (comme ceux que l’on manipule habituellement en mathématiques). Voilà donc un exemple de programme écrit dans notre nouveau langage avec sa syntaxe:

x = 3;
y = 4;
z = x + y;
x = y - z;
return x;

Mais même une fois que l’on a choisi notre syntaxe, il nous faut un moyen de la décrire proprement. En effet, même si on pourrait s’en tirer avec une description en français avec notre exemple simple, je présente la méthode systématique et explicite qui peut être utilisée pour décrirer la plupart des syntaxes des langages de programmation.

Syntaxe d’un langage

Ironiquement, c’est en utilisant un autre langage de programmation que l’on va décrire la syntaxe de notre nouveau langage de programmation! Ce méta-langage est appelé forme de Backus-Naur (abbrégé BNF), et voilà la description de notre syntaxe en BNF:

exp ::= var | const | exp "+" exp | exp "-" exp | "(" exp ")"
stm ::= var "=" exp ";" | "return" exp ";"

Après ce galimatias de symboles, il est temps de faire une pause et d’expliquer ce qui se passe. Les deux lignes du dessus définissent deux concepts de notre langages : les expressions (exp) et les déclarations (stm de l’anglais statement). Commençons par analyser la définition d’une expression : les barres verticales | indiquent, comme dans un type somme de langage fonctionnel, le fait qu’une expression peut être de plusieurs formes, les formes étant ce qu’il y a entre les |. Ici, var et const signifient qu’une expression peut être une variable (comme x) ou une constante, c’est-à-dire ici un nombre entier (comme 3). exp "+" exp est plus intéressant. Il indique qu’une expression peut être formée par deux expressions séparée par le signe +. Cette définition est récursive, car on définit les expressions en fonction d’autres expressions. Cette récursivité est nécessaire pour donner un sens à des expressions complexes comme 2 + 3 * y - 8 * x. On voit sur ce dernier exemple que cette définition récursive n’est pas suffisante : il nous faut aussi définir « comment rajouter les parenthèses manquantes » pour donner un sens unique à cette expression, qui peut ainsi devenir (2 + 3) * y - 8 * x ou encore 2 + (3 * y - 8) * x avec des résultats complètement différents. Je laisserai ce sujet technique de côté, pour nous concentrer sur les concepts les plus importants. exp "-" exp est similaire à l’addition, et "(" exp ")" indique que l’on peut mettre une expression entre parenthèses.

Les déclarations quant à elles sont plus simples, elles correspondent aux deux types d’instructions de notre langage : l’assignation d’expressions à des variables et la valeur de retour de notre programme. Il est nécessaire de faire la différence entre expressions et déclarations afin de ne pas autoriser des programmes comme 1 + x = return (1 - y), où expressions et déclarations sont mélangées. Car la syntaxe, en plus de décrire comment le langage s’écrit, agit comme un ensemble de règles qui nous dit si un programme est « valide » ou non. C’est pour cette raison que les compilateurs ou interpréteurs renvoient le fameux message Syntax error lorsque le texte du programme ne correspond pas à la définition de la syntaxe du langage.

Arbres de syntaxe

Maintenant que notre syntaxe est précisément définie, nous pouvons donner de la structure au code informatique. En effet, puisque le texte de nos programmes suit les règles de la syntaxe, il est possible d’utiliser cette information pour représenter le code dans une structure de données informatique. À cause de la nature récursive de la définition de la syntaxe, la structure de données que nous allons utiliser est un arbre, appelé arbre de syntaxe abstrait. Quel est l’arbre de syntaxe abstrait correspondant à notre exemple?

Comme nous nous sommes servis du méta-langage de la BNF pour décrire notre syntaxe, il nous faut choisir un méta-langage pour décrire notre arbre de syntaxe abstrait. Nous pourrions le décrire en termes purement mathématiques, mais il se trouve que les langages de programmation fonctionnels sont très bien adaptés pour décrire ce genre de structures de données récursives. En revanche, décrire ce genre de structure de données dans un langage de programmation orienté objet est très pénible et nécessite de créer autant de classes que de « variantes » d’expressions ou de déclarations. Voilà donc comment définir notre arbre de syntaxe abstrait en OCaml :

type exp =
    | Var of string
    | Const of int
    | Plus of exp * exp
    | Minus of exp * exp
    | Parenthesis of exp
type stm =
    | Assignment of string * exp
    | Return of exp
type program = stm list

Ici nous avons choisi de représenter les noms de variables par des chaînes de caractères (string), ce qui colle au plus près de la représentation textuelle. Un programme program est représenté par une liste de déclarations stm list, ce qui correspond également à la représentation textuelle. Les points-virgules ";" ont disparu car ils servaient uniquement à délimiter les déclaration, ils n’influent pas sur les calculs effectués par le programme.

Remarquons que l’on pourrait aussi retirer la ligne | Parenthesis of exp de notre arbre de syntaxe abstrait. En effet, les parenthèses servaient uniquement à préciser l’ordre dans lequel effectuer les opérations. Mais l’information concernant l’ordre des opérations est déjà encodée naturellement dans notre arbre! En effet, 4 + 5 va devenir Plus (4,5), et 4 + (5 - x) va devenir Plus (4, Minus (5,x)) (en omettant Const et Var pour plus de lisibilité). 5 - x est l’argument de droite du premier +, et le sens des parenthèses est respecté.

Grâce à cet arbre de syntaxe abstrait, nous disposons d’une représentation logique des programmes de notre nouveau langage de programmation. Cette représentation est classiquement l’aboutissement de la première phase d’un compilateur, et le premier pas vers la traduction de notre nouveau langage vers un assembleur dans lequel nous pourront exécuter nos programmes. Mais transformer le texte d’un programme en arbre de syntaxe abstrait permet aussi d’analyser le programme!

C’est sur cet arbre de syntaxe abstrait que s’effectue la vérification du typage (si le langage est typé), mais également l’analyse des possibilités d’autocomplétion par les Environnements de Développement Intégrés (IDE en anglais), fonctionnalité très utile au développeur.

Analyse syntaxique

J’ai délibérément passé sous silence un point pourtant très important : étant données les règles de la syntaxe que doit suivre le programme sous forme texte, quels sont les algorithmes qui permettent de transformer le texte en un arbre de syntaxe abstrait (opération de parsing)? Il se trouve que ces algorithmes sont d’une technicité importante, même s’ils se fondent (encore une fois) sur de fascinantes théories mathématiques. En voici un résumé très grossier et incomplet.

Premièrement, on utilise des expressions régulières pour transformer le texte en une série de tokens, un token correspondant peu ou prou à un mot-clé ou caractère de contrôle. Ceci a également pour effet de supprimer tous les espaces et sauts de lignes qui ne sont pas sémantiquement pertinents (sauf en Python…). Cette phase est appelée lexing.

La deuxième phase s’appelle le parsing : elle consiste à transformer une série de tokens en un arbre de syntaxe abstrait, suivant un ensemble de règles de grammaire. Je ne détaillerais pas plus cette étape car elle est très technique et repose sur tout une sous-discipline à la frontière entre mathématiques et informatique. Ce que l’on peut néanmoins retenir, c’est qu’il existe des algorithmes permettant d’effectuer le parsing en temps linéaire par rapport à la longueur du texte en entrée, moyennant quelques limitations sur la manière dont on définit sa grammaire.

Conclusion

L’arbre de syntaxe abstrait et la première représentation abstraite d’un langage de programmation, et c’est également celle qui est la plus proche du texte. Néanmoins, elle permet déjà de considérer un programme comme une donnée que l’on peut traiter dans d’autres programmes, comme des compilateurs ou des analyseurs.

Par la suite, nous allons nous appuyer sur ces représentations abstraites des programmes afin d’expliquer ce qui se passe lorsque l’on ordonne à nos compilateurs d’« optimiser » le code avec les options -O1, -02, etc. Bientôt, vous saurez pourquoi votre programme tourne 10 fois plus vite lorsqu’il est compilé avec l’option -O3!

Pour aller plus loin

  • Nous avons décrit notre petit langage jouet en utilisant la BNF, mais de « vrais » langages sont également définis en BNF, par exemple ML (dont OCaml est une variante) ou SQL.
  • La phase de lexing utilise des expressions régulières : maîtriser les expressions régulières est un talent très utile dès lors que l’on écrit du texte. En effet, la plupart des éditeurs de texte proposent un rechercher et remplacer à l’aide d’expressions régulières qui offre une grande puissance de manipulation de texte.
  • Pour un éclairage alternatif (et avec plus de dessins d’arbres!) sur ce que j’ai raconté dans ce billet, on pourra consulter le livre Wikipedia traitant des mêmes sujets.
  • Pour ceux qui veulent plus de détails sur la théorie des grammaires et leur parsing, ce cours d’une université irlandaise satisfera les curiosités les plus avides en une quarantaine de pages.
  • Cette démarche de décrire une grammaire et de construire un parseur pour produire des AST peut être utile au delà des développeurs de compilateurs. En effet, lorsque l’on a besoin de décrire des configurations complexes dans son domaine de travail (réseaux de neurones, réglages d’instruments, requêtes dans des bases de données, etc.) il est possible de définir un langage dédié (Domain Specific Language). Ainsi, on écrit plus lisiblement son problème dans ce nouveau langage qui est ensuite transformé en arbre de syntaxe abstrait que l’on peut analyser ou compiler.
  • Il existe pour la plupart des langages de programmation des librairies de parsing permettant de spécifier sa grammaire puis construire la machine à état. On peut citer Bison et Flex qui est le couple (lexing/parsing) standard. Mais ces libraires possèdent un défaut notoire, qui est que les messages d’erreurs indiquant des inconsistances dans la déclaration de la grammaire de l’utilisateur sont incompréhensibles. Aussi la libraire Menhir pour OCaml a-t-elle été développée précisément pour guider la création de la grammaire à l’aide de messages d’erreurs lisibles par un être humain.