Un compilateur transforme un programme écrit en langage évolué en
une suite d'instructions élémentaires exécutables par une machine.
La construction de compilateurs a longtemps été considérée comme
une des activités fondamentale en programmation, elle a suscité le
développement de très nombreuses techniques qui ont aussi donné
lieu à des théories maintenant classiques. La compilation d'un
programme est réalisée en trois phases, la première (analyse
lexicale) consiste à découper le programme en petites entités:
opérateurs, mots réservés, variables, constantes numériques,
alphabétiques, etc. La deuxième phase (analyse syntaxique) consiste
à expliciter la structure du programme sous forme d'un arbre, appelé
arbre de syntaxe, chaque n
ud de cet arbre correspond à un
opérateur et ses fils aux opérandes sur lesquels il agit. La
troisième phase (génération de code) construit la suite
d'instructions du micro-processeur à partir de l'arbre de syntaxe.
Nous nous limitons dans ce chapitre à l'étude de l'analyse syntaxique. L'étude de la génération de code, qui est la partie la plus importante de la compilation, nous conduirait à des développements trop longs. En revanche, le choix aurait pu se porter sur l'analyse lexicale, et nous aurait fait introduire la notion d'automate. Nous préférons illustrer la notion d'arbre, étudiée au chapitre 4, et montrer des exemples d'arbres représentant une formule symbolique. La structure d'arbre est fondamentale en informatique. Elle permet de représenter de façon structurée et très efficace des notions qui se présentent sous forme d'une chaîne de caractères. Ainsi, l'analyse syntaxique fait partie des nombreuses situations où l'on transforme une entité, qui se présente sous une forme plate et difficile à manipuler, en une forme structurée adaptée à un traitement efficace. Le calcul symbolique ou formel, le traitement automatique du langage naturel constituent d'autres exemples de cette importante problématique. Notre but n'est pas de donner ici toutes les techniques permettant d'écrire un analyseur syntaxique, mais de suggérer à l'aide d'exemples simples comment il faudrait faire. L'ouvrage de base pour l'étude de la compilation est celui de A. Aho, R. Sethi, J. Ullman [3]. Les premiers chapitres de l'ouvrage [32] constituent une intéressante introduction à divers aspect de l'informatique théorique qui doivent leur développement à des problèmes rencontrés en compilation.