EPITA

Introdution à Prolog, cours n° 4

Jean-François Perrot

Grammaires en Prolog

  1. Le problème
    1. Principe
    2. Écriture naïve d'une grammaire context-free

  2. La solution : les listes différentielles (en anglais difference-lists)
    1. Définition
    2. Exemples d'utilisation
      1. Renverser une liste (prédicat standard reverse) :
      2. Aplatir une liste (prédicat standard flatten) :
    3. Écriture des grammaires

  3. La notation DCG en Prolog
    1. Notation de base
    2. Surcharge de la notation de base
      1. Construction de l'arbre de dérivation
      2. Construction d'un arbre dérivé de l'arbre de dérivation : l'arbre de l'expression (première version)
      3. Autre exemple : la grammaire des exp. complètement parenthésées.
    3. Transformation explicite de l'arbre de dérivation
      1. Écriture séparée des règles de transformation : exemple
      2. Autre exemple : la notation complètement parenthésée (suite)

  4. Traitement des grammaires récursives à gauche
    1. Le problème et sa solution
      1. Principe
      2. Exemple : la notation polonaise postfixée
    2. La notation traditionnelle à précédences
      1. Traitons d'abord le cas simple à un seul niveau de priorité.
      2. La situation usuelle à deux niveaux de priorité

Le problème

La solution : les listes différentielles (en anglais difference-lists)

La notation DCG en Prolog


DCG = Definite Clause Grammar (Warren & Pereira), alias Grammaires de métamorphose (Colmerauer)

  1. Notation de base

    Attention ! Elle vise non plus des listes de codes-caractères, mais des listes d'atomes.
    On pourra commodément convertir les listes de codes-caractères (engendrées automatiquement par la notation entre guillemets)
    en listes d'atomes par le prédicat tokenize_atom :

    ?- tokenize_atom("+*2 x3 y4", X).
    X = [+, *, 2, x3, y4].

    (ce prédicat fait partie de la bibliothèque porter_stem, très probablement en place,
    si tel n'est pas le cas, chargez-la par la directive :- use_module(library(porter_stem)) )

    Notre exemple favori devient :
    rS --> rOp, rS, rS.
    rS --> rCte.
    rS --> rVbl.
    rOp --> [+].
    rOp --> [*].
    rCte --> [1].
    rCte --> [2].
    rVbl --> [x].
    rVbl --> [y].
    lancement par rS([+,*,2,x,1], []).

    Cette écriture est strictement équivalente à
    rS(A, Z) :- rOp(A, B), rS(B, C), rS(C, Z).
    rS([Car|Z], Z) :- rCte(Car).
    rS([Car|Z], Z) :- rVbl(Car).
    rOp([+|Z], Z).
    rOp([*|Z], Z).
    rCte
    ([1|Z], Z).
    rCte([2|Z], Z).
    rVbl([x|Z], Z).
    rVbl([y|Z], Z).
    comme on peut le vérifier en demandant le listing de chaque paquet de clauses :

    ?- listing(rS).
    rS(A, D) :-
        rOp(A, B),
        rS(B, C),
        rS(C, D).
    rS(A, B) :-
        rCte(A, B).
    rS(A, B) :-
        rVbl(A, B).

    true.



    et d'une manière globale (sur l'ensemble des prédicats présents dans la base) :

    ?- listing.

    %   Foreign: rl_read_history/1

    rS(A, D) :-
        rOp(A, B),
        rS(B, C),
        rS(C, D).
    rS(A, B) :-
        rCte(A, B).
    rS(A, B) :-
        rVbl(A, B).

    %   Foreign: rl_write_history/1

    rOp([+|A], A).
    rOp([*|A], A).

    %   Foreign: rl_add_history/1

    rCte([1|A], A).
    rCte([2|A], A).

    %   Foreign: rl_read_init_file/1

    rVbl([x|A], A).
    rVbl([y|A], A).
    true.




  2. Surcharge de la notation de base

    Les prédicats issus des non-terminaux de la grammaire peuvent recevoir des arguments supplémentaires.
    Ces arguments viennent avant les deux arguments implicites associés à la notation.
    Nous illustrons ce procédé avec la réalisation d'"actions sémantiques" au cours de l'analyse.
    1. Construction de l'arbre de dérivation
      L'arbre de dérivation est représenté naturellement comme un terme dont
      • les foncteurs sont en bijection avec les règles de la grammaire.
        Ici, nous considérons que ces règles sont au nombre de 3
        1. S -> opSS 
        2. S -> cte
        3. S -> vbl
      • l'arité de chaque foncteur est égale à la longueur du membre droit de la règle.
        Nous convenons ici de les désigner par un préfixe suivi du numéro de la règle.
      Par exemple, le terme "pref1(+, pref1(*, pref2(2), pref3(x)), pref2(1))"
      représente avec ces conventions l'arbre de dérivation de [+,*,2,x,1].

      On surcharge la grammaire ci-dessus :
      rS(pref1(Op, Ag, Ad)) --> rOp(Op), rS(Ag), rS(Ad).
      rS(pref2(Cte)) --> rCte(Cte).
      rS(pref3(Vbl)) --> rVbl(Vbl).
      rOp(+) --> [+].
      rOp(*) --> [*].
      rCte(1) --> [1].
      rCte(2) --> [2].
      rVbl(x) --> [x].
      rVbl(y) --> [y].
      Exécution :
      rS(A, [+,*,2,x,1], []).
      A = pref1(+, pref1(*, pref2(2), pref3(x)), pref2(1))
      true ;
      false.


      Ça marche parce que les foncteurs de l'arbre de dérivation sont connus a priori, donc exprimables par des constantes "en dur"
      que l'on peut insérer tels quels dans la grammaire.
      Voyons une opération plus intéressante du point de vue sémantique.
    2. Construction d'un arbre dérivé de l'arbre de dérivation : l'arbre de l'expression (première version)
      Il s'agit de retrouver le terme représentant l'expression en syntaxe Prolog, dans notre exemple "2*x+1".
      Là, il en va différemment, les foncteurs doivent être calculés, on fera donc appel à un constructeur :
      mkarb(Foncteur, Liste, Arbre, X, Y) :- Arbre =..[Foncteur | Liste].
       N-B : Les variables postiches X et Y sont nécessaires pour permettre l'appel de "mkarb" dans la règle de grammaire !!!  

      L'écriture directe donne :
      rS(A) --> rOp(Op), rS(Ag), rS(Ad), mkarb(Op, [Ag, Ad], A).
      rS(Cte) --> rCte(Cte).
      rS(Vbl) --> rVbl(Vbl).
      rOp(+) --> [+].
      rOp(*) --> [*].
      rCte(1) --> [1].
      rCte(2) --> [2].
      rVbl(x) --> [x].
      rVbl(y) --> [y].
      Elle fonctionne comme prévu sur des arbres "à droite" :
      ?- rS(A, [*,1,+,2,*,y,x], []).
      A = 1* (2+y*x) ;
      false.


      mais elle boucle sur les arbres "à gauche" :
      ?- rS(A, [*,+,2,x, 1], []), write(A).
      ERROR: Out of local stack
         Exception: (97,331) rS(_L4185036, _G97955, _L4185037) ? abort
      % Execution Aborted


    3. Autre exemple : la grammaire des exp. complètement parenthésées.
      Forme de base :
      expCP --> parouv, expCP, oper, expCP, parfer.
      expCP --> variable.
      expCP --> constante.
      parouv --> ['('].
      parfer --> [')'].
      oper --> [+].
      oper --> [*].
      variable --> [x].
      variable --> [y].
      variable --> [z].
      constante --> [1].
      constante --> [2].
      ?- expCP(['(', x, +, '(', y, *, z, ')', ')'], []).
      true ;
      false.

      Avec calcul de l'arbre :
      expCP(A) --> parouv, expCP(G), oper(Op), expCP(D), parfer, mkarb(Op, [G, D], A).
      expCP(V) --> variable(V).
      expCP(C) --> constante(C).
      parouv --> ['('].
      parfer --> [')'].
      oper(+) --> [+].
      oper(*) --> [*].
      variable(x) --> [x].
      variable(y) --> [y].
      variable(z) --> [z].
      constante(1) --> [1].
      constante(2) --> [2].
      Ça marche "à droite" :
      ?- expCP(A, ['(', x, +, '(', y, *, z, ')', ')'], []), write(A).
      x+y*z
      A = x+y*z ;
      false.

      mais ça boucle "à gauche" :
      ?- expCP(A, ['(', '(',x, +, y,')', *, z, ')'], []), write(A).
      ERROR: Out of local stack
         Exception: (160,961) expCP(_L4185035, _G181668, _L4185036) ? abort
      % Execution Aborted

  3. Transformation explicite de l'arbre de dérivation

    Cette mésaventure n'est qu'une manifestation du conflit entre
    On est donc conduit à construire l'arbre de dérivation d'abord et à le transformer ensuite.

    1. Écriture des règles de transformation : exemple
      Pour notre exemple de la notation polonaise préfixée :
      pref2exp(pref1(Op, G, D), E) :- pref2exp(G, Eg), pref2exp(D, Ed), E =.. [Op, Eg, Ed].
      pref2exp(pref2(V), V).
      pref2exp(pref3(V), V).
      Ces règles ne font pas intervenir les deux paramètres supplémentaires nécessaires à leur mise en œuvre au sein de la grammaire,
      comme illustré ci-dessus, et (dans un souci de modularité et de réutilisation),
      on ne souhaite pas les compliquer en introduisnt ces paramètres.

      On intègre alors le prédicat pref2exp à la grammaire avec une notation supplémentaire "entre accolades" :
      rTop(E) --> rS(A), {pref2exp(A, E)}.
      rS(pref1(Op, Ag, Ad)) --> rOp(Op), rS(Ag), rS(Ad).
      rS(pref2(Cte)) --> rCte(Cte).
      rS(pref3(Vbl)) --> rVbl(Vbl).
      rOp(+) --> [+].
      rOp(*) --> [*].
      rCte(1) --> [1].
      rCte(2) --> [2].
      rVbl(x) --> [x].
      rVbl(y) --> [y].
      ?- rTop(A, [*,+,2,x, 1], []).
      A = (2+x)*1 ;
      false.

      ?- rTop(A, [*,1,+,2,*,y,x], []).
      A = 1* (2+y*x) ;
      false.

    2. Autre exemple : la notation complètement parenthésée (suite)
      cp2arb(cp1(G, Op, D), E) :- cp2arb(G, Eg), cp2arb(D, Ed), E =.. [Op, Eg, Ed].
      cp2arb(cp2(V), V).
      cp2arb(cp3(C), C).

      topCP(A) --> expCP(E), {cp2arb(E, A)}.
      expCP(cp1(G, Op, D)) --> parouv, expCP(G), oper(Op), expCP(D), parfer.
      expCP(cp2(V)) --> variable(V).
      expCP(cp3(C)) --> constante(C).
      parouv --> ['('].
      parfer --> [')'].
      oper(+) --> [+].
      oper(*) --> [*].
      variable(x) --> [x].
      variable(y) --> [y].
      variable(z) --> [z].
      constante(1) --> [1].
      constante(2) --> [2].

      ?- topCP(A, ['(', '(',x, +, y,')', *, z, ')'], []).
      A = (x+y)*z ;
      false.

      ?- topCP(A, ['(', x, +, '(', y, *, z, ')', ')'], []).
      A = x+y*z ;
      false.


    3. Cette notation allégée n'est pas réservée à l'écriture des grammaires,
      elle peut s'employer chaque fois que le calcul est piloté par une liste différentielle.
      Exemple ci-joint : un générateur de code pour les expressions arithmétiques.

Traitement des grammaires récursives à gauche

  1. Le problème et sa solution

  2. La notation traditionnelle à précédences

    La règle d'association à gauche de la syntaxe traditionnelle se traduit par des règles récursives à gauche.
    1. Traitons d'abord le cas simple à un seul niveau de priorité.
      La grammaire "naturelle" : E -> E Op T, E -> T,  T -> ( E ), T -> Var, T -> Cte
      se transforme en
      1. E -> T S, 
      2. E -> T, 
      3. S -> Op T S, 
      4. S -> Op T, 
      5. T -> ( E ), 
      6. T -> Var
      7. T -> Cte .

      Le calcul des arbres d'expression à partir des arbres de dérivation de cette grammaire transformée s'écrit
      (avec le préfixe "prec1" pour l'identifier)
      prec12arb(prec11(G, D), E) :- term12arb(G, TG), prec1Aux(TG, D, E).
      prec12arb(prec12(T), E) :- term12arb(T, E).

      term12arb(prec15(F), E) :-prec12arb(F, E).
      term12arb(prec16(V),V).
      term12arb(prec17(C),C).

      prec1Aux(TG, prec13(Op, CD, S), E) :- term12arb(CD, TD), TG1 =.. [Op, TG, TD], prec1Aux(TG1, S, E).
      prec1Aux(TG, prec14(Op, T), E) :- term12arb(T, TD), E =.. [Op, TG, TD].

      D'où la grammaire
      prec1Top(A) --> prec1E(D), {prec12arb(D, A)}.
      prec1E(prec11(G, D)) --> prec1T(G), prec1S(D).
      prec1E(prec12(T)) --> prec1T(T).
      prec1S(prec13(Op, CD, S)) --> prec1Op(Op), prec1T(CD), prec1S(S).
      prec1S(prec14(Op, CD)) --> prec1Op(Op), prec1T(CD).
      prec1T(prec15(F))  --> prec1parouv, prec1E(F), prec1parfer.
      prec1T(prec16(V))  --> prec1var(V).
      prec1T(prec17(C))  --> prec1cte(C).
      prec1parouv --> ['('].
      prec1parfer --> [')'].
      prec1var(x) --> [x].
      prec1var(y) --> [y].
      prec1cte(1) --> [1].
      prec1cte(2) --> [2].
      prec1Op(+) --> [+].
      prec1Op(*) --> [*].
      ?- prec1Top(A, ['(', x, +, y, *, 2, ')', +, 1, *, 2 ], []).
      A = ((x+y)*2+1)*2 ;
      false.

    2. La situation usuelle à deux niveaux de priorité
      E -> E Opadd T, E -> T,  T -> T Opmul F, T -> F, F -> ( E ), F -> Var, F -> Cte
      se transforme en
      1. E -> T S1, 
      2. E -> T, 
      3. S1 -> Opadd T S1, 
      4. S1 -> Opadd T,
      5. T -> F S2, 
      6. T -> F, 
      7. S2 -> Opmul F S2,   
      8. S2 -> Opmul F,
      9. F -> ( E ), 
      10. F -> Var, 
      11. F -> Cte

      Le calcul des arbres d'expression à partir des arbres de dérivation de cette grammaire transformée s'écrit
      (avec le préfixe "prec2" pour l'identifier)
      prec22arb(prec21(T, S1), A) :- term22arb(T, TG), prec2Aux1(TG, S1, A).
      prec2arb(prec22(T), A) :- term22arb(T, A).

      term22arb(prec25(F, S2), A) :- fac22arb(F, FG), prec2Aux2(FG, S2, A).
      term22arb(prec26(F), A) :- fac22arb(F, A).

      fac22arb(prec29(E), A) :- prec22arb(E, A).
      fac22arb(prec210(V), V).
      fac22arb(prec211(C), C).

      prec2Aux1(TG, prec23(Oa, T, S1), A) :- term22arb(T, TD), TG1 =.. [Oa, TG, TD], prec2Aux1(TG1, S1, A).
      prec2Aux1(TG, prec24tOa, T), A) :- term22arb(T, TD), A =.. [Oa, TG, TD].

      prec2Aux2(FG, prec27(Om, F, S2), A) :- fac22arb(F, FD), FG1 =.. [Om, FG, FD], prec2Aux2(FG1, S2), A).
      prec2Aux2(FG, prec28(Om, F), A) :- fac22arb(F, FD), A =.. [Om, FG, FD].
      D'où la grammaire opérationnelle :
      prec2Top(A) --> prec2E(D), {prec22arb(D, A)}.
      prec2E(prec21(G, D)) --> prec2T(G), prec2S1(D).
      prec2E(prec22(T)) --> prec2T(T).
      prec2S1(prec23(Opadd, CD, S)) --> prec2Oa(Opadd), prec2T(CD), prec2S1(S).
      prec2S1(prec24(Opadd, CD)) --> prec2Oa(Opadd), prec2T(CD).
      prec2T(prec25(F, S))  --> prec2F(F), prec2S2(S).
      prec2T(prec26(F))  --> prec2F(F).
      prec2S2(prec27(Opmul, CD, S)) --> prec2Om(Opmul), prec2F(CD), prec2S2(S).
      prec2S2(prec28(Opmul, CD)) --> prec2Om(Opmul), prec2F(CD).

      prec2F(prec29(E))  --> prec2parouv, prec2E(E), prec2parfer.
      prec2F(prec210(V))  --> prec2var(V).
      prec2F(prec211(C))  --> prec2cte(C).
      prec2parouv --> ['('].
      prec2parfer --> [')'].
      prec2var(x) --> [x].
      prec2var(y) --> [y].
      prec2cte(1) --> [1].
      prec2cte(2) --> [2].
      prec2Oa(+) --> [+].
      prec2Om(*) --> [*].
      ?- prec2Top(A, ['(', x, +, y, *, 2, ')', +, 1, *, 2 ], []).
      A = x+y*2+1*2 ;
      false.