Cours n° 19, 7 avril 2011
La descente récursive
- Le principe illustré
sur deux exemples simples
- La notation
polonaise préfixée
- La notation
complètement parenthésée
- Rôle de la pile dans
la programmation récursive
- Principe de
l'automatisation de la descente récursive
- Prolog et la descente récursive
- Expression d'une grammaire par des
prédicats Prolog
- L'analyse effectuée est descendante
- Prolog effectue une descente
récursive
- Construction de l'arbre de
dérivation
- Transformation de l'arbre de
dérivation en arbre d'expression
- Le tout réuni
But de ce cours :
- Réalisation de l'analyse descendante par un jeu de procédures
co-récursives.
- Justification de l'énoncé : "Prolog effectue naturellement une
analyse descendante".
-
Idée : une grammaire peut se lire comme une définition récursive (cf.
son interprétation en termes d'équations au cours 15).
De cette définition récursive on passe volontiers à une procédure
récursive pour reconnaître les mots du langage...
-
L'idée ci-dessus s'énonce en bon français :
pour savoir si un mot est bien une expression polonaise
préfixée, je lis son premier caractère :
- si c'est un opérateur, je n'ai plus qu'à relancer la
procédure deux fois, une pour l'opérande gauche, l'autre pour
l'opérande droit ;
- si c'est une variable ou une constante, la réponse
est
OUI ;
- dans tout les autres cas la réponse est NON.
Ce qui se traduit ainsi en C++ ainsi (fichier drpref.cpp
)
#include <iostream>
using namespace std;
bool est_pref() {
char carlu ;
cin >> carlu;
switch (carlu) {
case '+' :
case '*' : {
return
est_pref() && est_pref(); // l'un après l'autre
}
case 'x' :
case 'y' :
case 'z' :
case '1' :
case '2' :
case '3' : {
return true;
}
default : {
cout <<
"Erreur : " << carlu << endl;
return false;
}
}
}
int main(void) {
string msg = est_pref()?"OK":"KO";
cout << msg << endl;
return 0;
}
En voici trois variantes, avec les mêmes conventions que
précédemment, et en plus :
-
L'idée ci-dessus devient un peu plus compliquée :
pour savoir si un mot est bien une expression en notation
complètement parenthésée, je lis son premier caractère :
- si c'est une parenthèse ouvrante, je n'ai plus qu'à
- relancer la procédure une première fois, pour
l'opérande
gauche
- lire un opérateur
- relancer la procédure une seconde fois, pour
l'opérande gauche,
- lire une parenthèse fermante ;
- si c'est une variable ou une constante, la réponse
est OUI ;
- dans tout les autres cas la réponse est NON.
Ce qui peut s'écrire d'une manière presqu'automatique en C++
(fichier drcp.cpp
)
#include <iostream>
using namespace std;
bool lireop() {
char carlu ;
cin >> carlu;
switch (carlu) {
case '+' :
case '*' : return true;
default : {
cout <<
"Erreur-op : " << carlu << endl;
return false;
}
}
}
bool lireferm() {
char carlu ;
cin >> carlu;
switch (carlu) {
case ')' : return true;
default : {
cout <<
"Erreur-ferm : " << carlu << endl;
return false;
}
}
}
bool lirecp() {
char carlu ;
cin >> carlu;
switch (carlu) {
case '(' : {
return
lirecp() && lireop() && lirecp() && lireferm();
}
case 'x' :
case 'y' :
case 'z' :
case '1' :
case '2' :
case '3' : return true;
default : {
cout <<
"Erreur-cp : " << carlu << endl;
return false;
}
}
};
int main(void) {
string msg = lirecp()?"OK":"KO";
cout << msg << endl;
return 0;
}
En voici deux variantes, avec les mêmes conventions que
précédemment, et en plus :
-
Une question philosophique se pose devant ces exemples :
- avons-nous affaire à un nouveau mode d'analyse ?
- ou bien s'agit-il d'une réalisation automatique de l'analyse
descendante, avec une seule pile ?
C'est la seconde réponse qui est la bonne.
D'une
manière générale, un programme récursif fonctionne avec une seule pile,
qui est gérée par le code compilé (ou interprété) du programme.
Pour le voir, il faut changer de contexte et aller regarder comment les
choses se passent au niveau de l'assembleur,
car le "langage évolué" (en l'occurrence, C++) a précisément pour rôle
de masquer ces
phénomènes.
Pour s'en faire une idée ultra-simplifiée, on pourra se reporter au
cours suivant :
http://www.formation.jussieu.fr/%7Eperrot/inalco/Maurice/
en particulier au cours du mardi 28 février.
-
L'idée de base est d'associer à chaque non-terminal de la grammaire une
procédure qui va analyser les mots issus de ce
non-terminal.
On obtient ainsi un jeu de procédures co-récursives, la
procédure-maîtresse étant celle qui est associée à l'axiome de la
grammaire.
N.B. Pour obtenir une écriture aussi automatique que possible, il
convient de rédiger des procédures, donc des actions,
qui
s'exécutent en séquence,
plutôt que des fonctions à valeurs booléennes comme on est
tenté de le faire -
et comme nous l'avons fait pour les exemples
simples ci-dessus.
Illustration sur les expressions en notation classique à précédences à
deux niveaux (cf. cours 16) :
- Leur grammaire étant récursive à gauche, il faut la
transformer pour éliminer la récursion à gauche, et la factoriser
(explications détaillées).
On obtient :
E -> T X
X -> + T X
X -> ε ------
interprétation : si le prochain
caractère à lire n'est pas '+
', ne rien faire
T -> F Y
Y -> * F Y
Y -> ε ------
interprétation : si le
prochain
caractère à lire n'est pas '*
', ne
rien faire
F -> ( E )
F -> Var
F -> Cte
- La réalisation programmée (fichier
drPrec.cpp
) suppose qu'on ait la
possibilité de voir le prochain caractère à lire
sans pour
autant le
consommer !
Au contraire des exemples précédents, où le prochain caractère était lu
et aussitôt consommé, par "cin >> carlu
;",
on va
- gérer la chaîne à lire dans une variable globale "
string
lu
;", avec un index également global "int i;
"
- et dissocier la vision du prochain caractère "
carvu
= lu[i];
"
- de sa consommation par l'incrémentation "
i++;
".
Par exemple, la procédure associée au non-terminal X
s'écrira ainsi :
void X(){
char carvu;
carvu = lu[i];
if( carvu == '+' ){
i++; //on avance dans la lecture
T();
X();
}// sinon rien
}
Voici une trace d'exécution (avec un programme modifié pour l'affichage
des appels, fichier drPrecT.cpp
)
:
x+y*((z+3+x*y)+z)*2*z
E
T
F x
Y +
X +
T
F y
Y *
F (
E
T
F (
E
T
F z
Y +
X +
T
F 3
Y +
X +
T
F x
Y *
F y
Y )
X )
Y +
X +
T
F z
Y )
X )
Y *
F 2
Y *
F z
Y
X
-
-
En Prolog, les
grammaires décrivent la structure de listes d'atomes (et
non de chaînes de caractères).
Pour des raisons qui sortent du cadre de ce cours (cf. la théorie des listes différentielles),
on passe par des prédicats à deux arguments :
pred(X, Y)
est vrai si
X
= [a1,
a2, a3,... an | Y]
c'est-à-dire
que X
commence par [a1,
a2, a3,... an]
et que Y
est "la suite" ;
et si
- le début de la liste
X
, à savoir la
liste [a1,
a2, a3,... an]
a la structure
indiquée.
Toute la subtilité de la chose est dans l'idée de travailler sur le
début du 1er argument.
Exemple : à partir de la grammaire de la notation polonaise préfixée,
S -> OpSS
S -> Cte
S -> Vbl
Op -> +
Op -> *
Cte -> 1
Cte -> 2
Vbl -> x
Vbl -> y
comme en Prolog les majuscules sont réservées aux variables logiques, à
chaque nom-terminal on associe un prédicat
dont le nom est préfixé par 'r
' (comme règle).
rS(A, Z) :- rOp(A, B), rS(B, C),
rS(C, Z).
rS(A, Z) :- rCte(A, Z).
rS(A, Z) :- rVbl(A, Z).
rOp([+|Z], Z).
rOp([*|Z], Z).
rCte
([1|Z], Z).
rCte
([2|Z], Z).
rVbl
([x|Z], Z).
rVbl
([y|Z], Z).
Écrivons ceci dans un fichier (ici pp1.pl
)...
C'est un parseur !
Lancement par "rS([+,*,2,x,1], [])
".
?- [pp1].
% pp1 compiled 0.00 sec, 2,848 bytes
true.
?- rS([+,*,2,x,1], []).
true .
?- rS([+,*,2,x,*], []).
false.
-
Deux manières de le
voir :
- en demandant la
trace de l'exécution :
?-
trace, rS([+,*,2,x,1], []).
Call: (7) rS([+, *, 2, x, 1], []) ? creep
Call: (8) rOp([+, *, 2, x, 1], _G156) ? creep
Exit: (8) rOp([+, *, 2, x, 1], [*, 2, x, 1]) ? creep
Call: (8) rS([*, 2, x, 1], _G156) ? creep
Call: (9) rOp([*, 2, x, 1], _G156) ? creep
Exit: (9) rOp([*, 2, x, 1], [2, x, 1]) ? creep
Call: (9) rS([2, x, 1], _G156) ? creep
Call: (10) rOp([2, x, 1], _G156) ? creep
Fail: (10) rOp([2, x, 1], _G156) ? creep
Redo: (9) rS([2, x, 1], _G156) ? creep
Call: (10) rCte([2, x, 1], _G156) ? creep
Exit: (10) rCte([2, x, 1], [x, 1]) ? creep
Exit: (9) rS([2, x, 1], [x, 1]) ? creep
Call: (9) rS([x, 1], _G156) ? creep
Call: (10) rOp([x, 1], _G156) ? creep
Fail: (10) rOp([x, 1], _G156) ? creep
Redo: (9) rS([x, 1], _G156) ? creep
Call: (10) rCte([x, 1], _G156) ? creep
Fail: (10) rCte([x, 1], _G156) ? creep
Redo: (9) rS([x, 1], _G156) ? creep
Call: (10) rVbl([x, 1], _G156) ? creep
Exit: (10) rVbl([x, 1], [1]) ? creep
Exit: (9) rS([x, 1], [1]) ? creep
Exit: (8) rS([*, 2, x, 1], [1]) ? creep
Call: (8) rS([1], []) ? skip
Exit: (8) rS([1], []) ? creep
Exit: (7) rS([+, *, 2, x, 1], []) ? creep
true
- en demandant à
Prolog d'imprimer le numéro de la règle
dès qu'il a fait son choix :
rS(A, Z) :- rOp(A, B), write(1), rS(B, C), rS(C, Z).
rS(A, B) :- rCte(A, B), write(2).
rS(A, B) :- rVbl(A, B), write(3).
les autres règles sans changement.
?-
rS([+,*,2,x,1], []).
11232
true .
Attention à demander l'écriture au moment où la règle est appliquée,
et non pas après la fin de cette application !
Si on écrit :
rS(A, Z) :- rOp(A, B), rS(B, C), rS(C, Z)
,
write(1)
.
on obtient
?-
rS([+,*,2,x,1], []).
23121
true .
c'est-à-dire
la dérivation droite écrite à l'envers.
Exercice : expliquer ce phénomène !
-
Il suffit pour s'en
convaincre de comparer l'interprétation procédurale de la grammaire
écrite en Prolog comme ci-dessus
avec l'exposé "en bon français" de la descente récursive qui précède.
Corollaire : On ne pourra pas écrire en Prolog de
grammaire récursive à gauche...
Et d'une manière plus cachée, la construction de l'arbre syntaxique
(ici, l'arbre d'expression)
ne va pas pouvoir se faire commodément.
Il va falloir passer par la construction de l'arbre de dérivation, qui
se fait sans problème,
et par une transformation explicite de l'arbre de dérivation en arbre
syntaxique
- heureusement que Prolog est le langage idéal pour écrire de telles
transformations !
Exemple de la polonaise préfixée :
-
Il suffit de
"surcharger" les prédicats de la grammaire
en demandant "en plus" de construire un terme représentant l'arbre :
rS(A,
Z, pref1(Op, Ag, Ad)) :- rOp(A, B, Op), rS(B, C, Ag), rS(C, Z, Ad).
rS(A, B, pref2(Cte)) :- rCte(A, B, Cte).
rS(A, B, pref3(Var)) :- rVbl(A, B, Var).
rOp([+|Z], Z, (+)). % la mise entre parenthèses signifie que le
caractère
rOp([*|Z], Z, (*)). %
n'est PAS en position d'opérateur
rCte([1|Z], Z, 1).
rCte([2|Z], Z, 2).
rVbl([x|Z], Z, x).
rVbl([y|Z], Z, y).
Exécution :
?-
rS([+,*,2,x,1], [], X).
X = pref1(+, pref1(*, pref2(2), pref3(x)), pref2(1)) .
?- rS([*,+,x,*,y,+,x,2,+,y,1], [], X).
X = pref1(*, pref1(+, pref3(x), pref1(*, pref3(y), pref1(+, pref3(x),
pref2(2)))), pref1(+, pref3(y), pref2(1))) .
-
immédiat ! faites
un dessin...
pref2exp(pref1(Op,
G, D), E) :- pref2exp(G, Eg), pref2exp(D, Ed), E =.. [Op, Eg, Ed].
pref2exp(pref2(V), V).
pref2exp(pref3(V), V).
Exécution :
?-
pref2exp(pref1(+, pref1(*, pref2(2), pref3(x)), pref2(1)), X).
X = 2*x+1.
?- pref2exp( pref1(*, pref1(+, pref3(x), pref1(*, pref3(y), pref1(+,
pref3(x), pref2(2)))), pref1(+, pref3(y), pref2(1))), X).
X = (x+y* (x+2))* (y+1).
Eh oui,
Prolog reconnaît les arbres dont les opérateurs sont '+
'
et '*
' comme des expressions arithmétiques,
et il les affiche avec les conventions standard !
-
Ajoutons un
prédicat-maître :
rTop(A, E) :- rS(A, [], D), pref2exp(D, E).
(fichier pp1d.pl
)
?- rTop([+,*,2,x,1], X).
X = 2*x+1 .
?- rTop([*,+,x,*,y,+,x,2,+,y,1], X).
X = (x+y* (x+2))* (y+1)
Et le tour est joué !
- Pour en savoir davantage, notamment sur la notation des
grammaires en Prolog dite "DCG",
voir "Les grammaires en Prolog", en particulier
le paragraphe sur le traitement des grammaires récursives à gauche.