Cours n° 19, 7 avril 2011

Jean-François Perrot

La descente récursive

Le principe illustré sur deux exemples simples
1. La notation polonaise préfixée
2. 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

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".

Le principe illustré sur deux exemples simples
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...
1. La notation polonaise préfixée
  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 :
  - la traduction en postfixée : fichier drpref2post.cpp
  - la traduction en notation complètement parenthésée : fichier drprefCp.cpp
  - la génération de l'arbre d'expression : fichier drprefArb.cpp
2. La notation complètement parenthésée
  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'à
    1. relancer la procédure une première fois, pour l'opérande gauche
    2. lire un opérateur
    3. relancer la procédure une seconde fois, pour l'opérande gauche,
    4. 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 :
  - la traduction en postfixée : fichier drcpPost.cpp
  - la génération de l'arbre d'expression : fichier drcpArb.cpp
Rôle de la pile dans la programmation récursive
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.
Principe de l'automatisation de la descente récursive
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) :
1. 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
2. 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
Prolog et la descente récursive
1. Expression d'une grammaire par des prédicats Prolog
  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
  1. X = [a₁, a₂, a₃,... a_n | Y] c'est-à-dire que X commence par [a₁, a₂, a₃,... a_n] et que Y est "la suite" ;
    et si
  2. le début de la liste X, à savoir la liste [a₁, a₂, a₃,... a_n] 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,
  1. S -> OpSS
  2. S -> Cte
  3. S -> Vbl
  4. Op -> +
  5. Op -> *
  6. Cte -> 1
  7. Cte -> 2
  8. Vbl -> x
  9. 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.
2. L'analyse effectuée est descendante
  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 !
3. Prolog effectue une descente récursive
  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 :
  - Construction de l'arbre de dérivation
    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))) .
  - Transformation de l'arbre de dérivation en arbre d'expression
    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 !
  - Le tout réuni
    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é !
4. 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.