DFA, automate virtuel

Un DFA (Deterministic Finite-state Automaton), en français automate déterministe à états finis est un programme dont le résultat dépend uniquement des données de départ et ne dépend d'aucun évènement, d'aucune action d'un utilisateur.
Un DFA peut servir à programmer une machine, réaliser un compilateur.

Ordinogramme

Cela peut aussi s'appeller Finite State Machine: machine à états finis. Mais DFA peut aussi signifier Data Flow Analysis ce qui n'est pas le sujet de cet article.

Le DFA peut se concevoir comme une collection d'états avec des transitions entre états. Les transitions sont des actions qui font passer d'un état à l'état suivant.
Il suppose une "machine", un programme qui fait passer d'un état à un autre.

Dans le cas de la génération de code, le DFA est généré par un parseur spécialisé à partir de la définition de la grammaire d'un langage. Cela produit un programme capable de compiler des codes sources conformes à cette grammaire pour produire un code objet.

Déterminisme

Le résultat dépend entièrement du code fourni et de l'application des règles de l'automate. Il n'y a pas d'entrée de données par l'utilisateur ni aucune sorte d'évènement qui puisse influer sur le résultat.

Etats finis

Le nombre d'états est fini, de même que le nombre de transitions entre états.

Ces deux propriétés impliquent qu'il est toujours possible de résoudre les cas que peut présenter un programme syntaxiquement correct parceque la grammaire prévoit tous les cas sans ambiguité. Il n'est pas possible que dans un état donné de la compilation on puisse arriver à des résultats différents.

Ordinogramme

L'ordinogramme, ou organigramme, nom plus générique, est la représentation visuelle des étapes d'une programme. Les flèches correspondent aux états tandis que les rectangles contiennent les actions. Il comporte aussi des conditions représentées dans des losanges.
On peut présenter une condition multiple (comme une structure switch) en décomposant les conditions en éléments à deux états.

Le déroulement d'un programme, ne dépend pas que des états, il dépend d'interventions extérieures telle que les mouvements de la souris. Dans le cas d'un jeu par exemple, le déroulement difficilement prévisible. L'ordinogramme est une vue simplifiée et nécessairement déterministe du déroulement d'un programme.

Si l'ordinogramme peut fournir une représentation d'un DFA ou d'un programme, un programme n'est pas un DFA car il dépend d'interventions extérieures. Le programme est au DFA ce que le robot est à l'automate.

Grammaire

Une grammaire est l'expression de la syntaxe d'un langage sous forme de règles écrites selon des conventions reconnues par un parseur. Un DFA peut décrire la grammaire d'un langage humain comme celle d'un langage informatique.

Exemple de grammaire informatique:

exp : ( id | addition )
addition: id '+' exp  

Ces règles, qui sont récursives dans cet exemple, sont reconnues par le parseur YACC.

• Bison.
  Version libre de YACC par le GNU. Convertit le langage source d'un programme en langage binaire en se basant sur la grammaire du langage (représentée par un DFA) dans lequel est écrit le programme.