Un automate à pile est un modèle de calcul qui enrichit l’automate fini d’une mémoire supplémentaire d’un genre particulier, appelée pile. Comme l’automate fini, il lit une suite de symboles de gauche à droite en passant d’un état à un autre, mais il dispose en plus d’une réserve où il peut empiler des symboles et les dépiler ensuite, avec une contrainte stricte: seul le sommet de la pile est accessible à tout moment, si bien que le dernier élément ajouté est toujours le premier à pouvoir être retiré. On compare souvent ce fonctionnement à une pile d’assiettes, où l’on ne peut prendre que celle du dessus. Grâce à cette mémoire, l’automate peut retenir une quantité d’informations non bornée, mais uniquement dans cet ordre très rigide, ce qui lui confère une puissance intermédiaire entre l’automate fini et la machine de Turing.
Ce modèle a été dégagé dans les années 1950 et au début des années 1960, à mesure que se développait l’étude des langages formels, notamment sous l’impulsion des travaux du linguiste Noam Chomsky sur la structure des langues. On établit que les automates à pile reconnaissent exactement la famille des langages dits hors-contexte, ceux que l’on décrit par des grammaires du même nom, capables d’exprimer des structures emboîtées comme des parenthèses correctement appariées. C’est précisément cette capacité à gérer l’emboîtement, hors de portée d’un automate fini dépourvu de mémoire, qui fait tout l’intérêt de la pile et marque la frontière entre les deux modèles.
L’application la plus importante des automates à pile concerne l’analyse syntaxique des langages de programmation. Lorsqu’un compilateur ou un interpréteur doit vérifier qu’un code respecte la grammaire du langage, il s’appuie sur un mécanisme de ce type pour suivre les imbrications de parenthèses, d’accolades, de blocs et d’expressions, qui sont par nature des structures emboîtées les unes dans les autres. On retrouve la même idée dans le traitement des formats de données hiérarchiques et dans l’évaluation des expressions mathématiques, où l’ordre des opérations et des parenthèses doit être respecté. La pile, structure élémentaire mais puissante, demeure ainsi l’un des outils fondamentaux dès qu’il s’agit de manipuler correctement de l’information organisée en niveaux imbriqués.
Laisser un commentaire