Download Fichier PDF

viii
II
Sommaire
Compilation de la réécriture
4 Méta-conception
51
53
4.1
Interpréteur, Compilateur et Machine abstraite . . . . . . . . . . . . . . . . .
53
4.2
Pourquoi choisir un compilateur . . . . . . . . . . . . . . . . . . . . . . . . .
56
4.3
Compilation de la réécriture . . . . . . . . . . . . . . . . . . . . . . . . . . .
58
5 Compilation du filtrage syntaxique
61
5.1
Termes vus comme des chaı̂nes de symboles . . . . . . . . . . . . . . . . . . .
62
5.2
Automate de filtrage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
63
5.3
Clôtures d’un ensemble de motifs . . . . . . . . . . . . . . . . . . . . . . . . .
66
5.4
Clôture réduite d’un ensemble de motifs . . . . . . . . . . . . . . . . . . .
70
5.5
Automate de filtrage à mémoire . . . . . . . . . . . . . . . . . . . . . . . . .
72
5.6
Automate de filtrage avec jumpNode . . . . . . . . . . . . . . . . . . . . . . .
75
5.7
Comparaison des différentes approches . . . . . . . . . . . . . . . . . . . . . .
78
6 Compilation du filtrage associatif-commutatif
81
6.1
Termes en forme canonique . . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
6.2
Approche one-to-one . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
83
6.3
Approche many-to-one . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
84
6.4
Classes de motifs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
88
6.5
Spécialisation utilisant une structure compacte . . . . . . . . . . . . . . . . .
88
6.6
Raffinement glouton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
6.7
Calcul des substitutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
94
6.8
Extension à l’ensemble des motifs . . . . . . . . . . . . . . . . . . . . . . . .
95
6.9
Synthèse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
97
7 Gestion du non-déterminisme
99
7.1
Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
7.2
Basic choice point primitives . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
7.3
Known choice point implementations . . . . . . . . . . . . . . . . . . . . . . 102
7.4
New choice point management . . . . . . . . . . . . . . . . . . . . . . . . . . 103
7.5
Imperative programming with backtracking . . . . . . . . . . . . . . . . . . . 109
7.6
Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
8 Compilation des règles et des stratégies
113
8.1
Tour d’horizon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
8.2
Solution retenue pour ELAN . . . . . . . . . . . . . . . . . . . . . . . . . . . 115