next up previous contents index
Next: Forme canonique Up: Règles de réécriture Previous: Ensemble de règles   Contents   Index

Définition des règles

Avant d'étudier le fonctionnement des règles en détail, il faut signaler quelques points importants :

L'algorithme de fonctionnement des ensembles de règles est très simple. Chaque règle d'un ensemble contient une partie gauche (lhs, pour left hand side) et une partie droite (rhs, pour right hand side). Les étapes de la réécriture sont les suivantes :

  1. si la partie gauche correspond à l'adresse, sélectionner la règle, réécrire la règle suivant la spécification de la partie droite, puis recommencer en 1 avec la même règle ;

  2. si la partie gauche ne correspond pas à l'adresse, prendre la règle suivante si elle existe, et recommencer en 1 ;

  3. s'il n'y a plus de règle dans l'ensemble, il est terminé. L'adresse obtenue est le résultat de l'ensemble.

Cet algorithme définit implicitement une boucle pour chaque règle (l'adresse est réécrite tant que cela est possible). Ce fonctionnement itératif peut être éliminé pour certaines règles (opérateur $:). De même, le fonctionnement est séquentiel : après avoir fini d'utiliser une règle, on continue dans la suivante. Ce comportement peut également être éliminé, une règle pouvant terminer un ensemble (opérateur $@).

Figure 2.4: Fonctionnement des réécritures dans sendmail
\begin{figure}\hrule \vspace {3mm}
\begin {center}
\epsfig {figure=algo.ps}
\end {center}
\vspace {2mm}
\vspace {2mm}
\hrule\end{figure}

Cet algorithme est illustré sur la figure 2.4. Étant donné l'ensemble 15 comportant deux règles, et l'adresse a%b%c%d, la première règle ($+%$+) correspond et l'adresse est réécrite en a@b%c%d. Cette nouvelle adresse est comparée à la partie gauche de la première règle à nouveau, et elle est réécrite une deuxième fois pour donner a@b@c%d. Après un troisième passage dans cette règle, on obtient a@b@c@d. À ce stade, la première règle ne peut plus correspondre, et on passe à la seconde. Celle-ci s'applique, elle aussi, itérativement pour donner à la fin a%b%c@d. Comme il n'y a pas de troisième règle, l'ensemble 15 est terminé.


next up previous contents index
Next: Forme canonique Up: Règles de réécriture Previous: Ensemble de règles   Contents   Index
Pierre DAVID 2001-11-26