Download Fichier PDF

8.6. Compilation des stratégies
127
que si l’instance de x est un sous-terme d’un des si , elle est elle aussi en forme normale. Partant de
ces deux idées de base, nous avons étendu la méthode de construction des termes en coloriant certains termes. On distingue alors deux cas :
– à l’exécution, lorsqu’une forme normale fAC (s01 , . . . ,s0m0 ) est atteinte, tous les sous-termes
s01 , . . . ,s0m0 sont coloriés par une même couleur ;
– pour construire le terme fAC (s1 , . . . ,sm ), le symbole fAC est construit puis la fonction mcf
est utilisée pour ajouter successivement les sous-termes si :
– avant chaque insertion, le sous-terme si (qui est irréductible) est colorié par une
couleur différente de celles associées aux s1 , . . . ,si−1 ;
– si l’utilisation de mcf entraı̂ne une étape d’aplatissement et lorsque α sous-termes t
identiques apparaissent, ils sont remplacés par une instance unique tα , mais cette fois,
t se voit décoré d’une couleur particulière bicolore.
Pour savoir si un terme xσ = fAC (s1 , . . . ,sk ) est irréductible, il suffit alors de vérifier que
les couleurs des s1 , . . . ,sk sont bien identiques et qu’aucune d’elles n’est bicolore.
Ce critère, très simple à mettre en œuvre, permet de réduire considérablement le nombre de
renormalisations inutiles. Les résultats obtenus dans la pratique montrent que ce critère permet
de réduire le nombre de renormalisations dans une proportion variant entre 50% et 80%.
8.6 Compilation des stratégies
Dans ce paragraphe, nous nous intéressons à la compilation du langage de stratégie d’ELAN,
mais les idées présentées ont un caractère plus général qui peuvent être réutilisées pour compiler
tout autre langage de stratégie dont les opérateurs agissent sur les stratégies elles-mêmes.
Les paragraphes 8.3, 8.4 et 8.5 ont montré comment compiler les stratégies élémentaires
dc one, dc ou dk(r1 , . . . ,rn ). Étudions maintenant comment compiler les opérateurs agissant sur
des stratégies : dc one,dc,dk(S1 , . . . ,Sn ), S1 ;S2 , repeat*(S) et iterate*(S)).
Tout comme la compilation d’un ensemble de règles, on peut supposer qu’une stratégie S se
compile en une fonction str S qui prend un terme clos s en argument et retourne un nouveau
terme clos s0i correspondant à l’application de la stratégie. Pour extraire les différents éléments s0i
de l’ensemble des termes {s01 , . . . ,s0n } atteignables en appliquant la stratégie S au terme s, il
suffit d’engendrer un fail pour réactiver un point de choix posé pendant l’exécution de str S.
Concaténation. Étant données deux stratégies S1 et S2 , l’opérateur de concaténation S1 ; S2 se
compile facilement. Il suffit d’enchaı̂ner les fonctions str S1 et str S2 : la stratégie S2 est ainsi
appliquée aux résultats de S1 . Lorsque S2 échoue, un nouveau résultat de S1 est extrait, et
lorsque S1 échoue, la stratégie S1 ; S2 échoue également.
Exploration. Étant données n stratégies S1 , . . . ,Sn , la compilation de S = dc one,dc ou dk(S1 , . . . ,
Sn ) s’effectue à l’image de la compilation d’un ensemble de règles, mais sans se soucier de l’étape
de filtrage. Suivant l’opérateur appliqué, il faut retourner un seul ou tous les résultats d’une stratégie Si , ou encore tous les résultats de toutes les stratégies S1 , . . . ,Sn .
La compilation de S consiste à compiler chaque sous-stratégie Si et à essayer d’appliquer
successivement les stratégies S1 , . . . ,Sn . Le code de la fonction str S est alors composé d’une
suite d’appels aux fonctions str Si (si ) où chaque appel est précédé par la pose d’un point de
choix. Lorsqu’un résultat est trouvé pour une sous-stratégie Si , un saut vers l’étape 1 suivante
est effectué :