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

• Principe

  Une grammaire context-free (CF) s'interprète en termes logiques
  en associant un prédicat à chacun des symboles non-terminaux de la grammaire.
  Le non-terminal étant vu comme le nom d'une catégorie grammaticale,
  le prédicat associé désigne l'appartenance de son mot-argument à la catégorie en question.
  
  Prolog est donc a priori un cadre adéquat pour programmer des grammaires et des analyseurs

• Écriture naïve d'une grammaire context-free

  Dire qu'une chaîne de caractères (= liste de codes) a une certaine structure
  revient à dire que cette liste est la concaténation de plusieurs sous-listes :
  par exemple pour la polonaise préfixée, la règle  "S -> OpSS" se traduit :
  rS(Chn) :- rOp(Chn1), rS(Chn2), rS(Chn3), append(Chn1, Chn2, T), append(T, Chn3, Chn).
  
  On peut ainsi écrire une grammaire complète :

  S -> OpSS
S -> Cte
S -> Vbl
Cte -> 1 | 2
Vbl -> x | y

  se traduit par

  rS(Chn) :- rOp(Chn1), rS(Chn2), rS(Chn3), append(Chn1, Chn2, T), append(T, Chn3, Chn).
rS(Chn) :- rCte(Chn).
rS(chn) :- rVbl(Chn).
rOp("+").
rOp("*").
rCte("1").
rCte("2").
rVbl("x").
rVbl("y").


  qui boucle désespérément...
  
  Il faut sans doute indiquer à Prolog que la chaîne lue a une fin !
  Y ajouter un marqueur ? Cela fera un append de plus...
  Meilleure solution : les listes différentielles.
  

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

• Définition

  Une liste différentielle  est formée de deux listes A et B, où B est une portion finale de A, par exemple  [1,2,3,4] et [3,4].
  On la note "A - B".
  Elle  représente la liste obtenue en enlevant de A sa portion fnale B, e.g., "[1,2,3,4]-[3,4]" représente la liste "[1,2]".
  Évidemment, si les deux listes A et B sont complètement instanciées, cette notion n'a aucun intérêt. Mais c'est avec des variables logiques et en jouant sur l'unification qu'on obient des résultats intéressants. En l'occurrence,
  
  on représentera la liste "[1,2]" avec la liste différentielle "[1,2|X]-X".
  
  Traduction liste <--> liste différentielle (P. Taillibert)
  list_to_dlist([T|Q], DL - Z) :-
    DL\== Z,    % pour ne pas évaluer cette clause si l'appel est fait avec une dlist vide
    DL=[T|QDL],
    list_to_dlist(Q, QDL-Z).
list_to_dlist([], X-X) :- var(X).
    % pour éviter la création d'un arbre infini au backtrack lors d'un appel dans le sens dlist --> list
     
  N.B.    Le test sur le paramètre de la dlist est nécessaire si l'on veut appeler le prédicat dans tous les sens
  (exclusivité des clauses lorsque le premier argument est une variable).
  
  L'intérêt majeur des listes différentielles est d'éliminer l'orientation "gauche-droite" des listes standard :
  comme on sait,
  
  • les listes sont naturellement gérées en pile (lifo), et non en file (fifo), 
  • en raison de la dissymétrie entre l'ajout d'un élément
    
    • en tête de liste, par le constructeur de listes (Res = [A | S]) en temps constant
    • et en queue de liste par append(S, [A], Res) qui demande un parcours complet de la liste.
      
  Avec des listes différentielles
  
  • on peut écrire append "en un coup" :  append_dl(A - B, B - C, A - C).
    à condition que la queue de la première et la tête de la seconde soient unifiables
    (ce qui est toujours le cas si la queue en question est une variable) :

?- append_dl([a,b,c|X]-X, [1,2]-[], Y).
X = [1, 2],
Y = [a, b, c, 1, 2]-[].

    N.B. la valeur de A qui était initialement [a,b,c|X] devient [a, b, c, 1, 2] par suite de l'instanciation de X = [1, 2] !
    
    
  • et de même l'ajout à la fin :
ajouter(X, A-[X|B], A-B).

?- ajouter(d, [a,b,c|U]-U, V).
U = [d|_G310],
V = [a, b, c, d|_G310]-_G310.

On trouvera ce principe mis en œuvre dans un générateur de code pour les expressions arithmétiques.

  


• Exemples d'utilisation

  Tous les programmes où append dans le sens "direct" joue un rôle important sont candidats à une réécriture plus efficace
  avec des listes différentielles. Cette réécriture recoupe la transformation de programme classique employant un accumulateur
  (fondée sur l'associativité d'append).
  

  1. Renverser une liste (prédicat standard reverse) :

     en style naïf (cf. Cours n° 1) :
     renverser([], []).
renverser([A|S], R) :- renverser(S,T), append(T, [A], R).
     
     avec accumulateur :
     renverser(X, Y) :- renv_a(X, [], Y).
renv_a([], X, X).
renv_a([P|S], A, Y) :- renv_a(S, [P|A], Y).

     avec listes différentielles :
     rverse(A, B) :- reverse_dl(A, B-[]).
reverse_dl([], X-X).
reverse_dl([X|S], Y-Z) :- reverse_dl(S, Y-[X|Z]).
     
     

  2. Aplatir une liste (prédicat standard flatten) :

     en style naïf :
     aplatir([], []).
aplatir(X, [X]) :- atomic(X), X \=[].
aplatir([P|S],R) :- aplatir(X, Y), aplatir(S, Z), append(Y, Z, R).

     
     avec accumulateur :
     aaplatir(X, Y) :- platir(X, [], Y).
platir([], X, X).
platir(X, A, [X|A]) :- atomic(X), X \=[].
platir([P|S], A, Y) :- platir(S, A, Z), platir(P, Z, Y).
     
     avec listes différentielles :
     apltir(U,V) :- flatten_dl(U, V-[]).
flatten_dl([], X-X).
flatten_dl(X, [X|T]-T) :- atomic(X), X \=[].
flatten_dl([X|S], Y-Z) :- flatten_dl(X, Y-Y1), flatten_dl(S, Y1-Z).

     

• Écriture des grammaires

  Elle se fait très naturellement en termes de listes différentielles,
  en exprimant que la spécification vise la tête de la liste, ce qui permet de se passer de append :
  notre exemple précédent devient :

  rS(A-Z) :- rOp(A-B), rS(B-C), rS(C-Z).
rS([Car|Z]-Z) :- rCte(Car). % Car est un code de caractère
rS([Car|Z]-Z) :- rVbl(Car).
rOp([43|Z]-Z).
rOp([42|Z]-Z).
rCte(49).
rCte(50).
rVbl(120).
rVbl(121).


  et sa mise en œuvre se fait par exemple ainsi rS("+*2x1"-[]).
  
  Notez que la même intention peut s'exprimer sans recourir à la notation spécifique des listes différentielles,
  en gérant la tête et la queue dans deux variables distinctes.
  

  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([43|Z], Z).
rOp([42|Z], Z).
rCte(49).
rCte(50).
rVbl(120).
rVbl(121).


  avec mise en œuvre par rS("+*2x1", []).

  

La notation DCG en Prolog

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
   
   • la stratégie d'analyse, qui engendre un parcours de l'arbre de dérivation
     (ici, c'est la stratégie descendante qui fonctionne) 
   • et la stratégie de transformation qui produit l'arbre de l'expression à partir de l'arbre de dérivation.
     Cette transformation-là n'est pas toujours simple,
     et il n'y a aucune raison qu'elle s'accommode du parcours d'analyse.
     
     
   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

   • Principe

     Les grammaires DCG lues comme des parseurs suivent la stratégie de descente récursive.
     Il s'ensuit que toute règle récursive à gauche (directement ou indirectement) provoque une descente infinie.
     
     Le remède classique est de modifier la grammaire de manière à éliminer la récursion à gauche,
     sur la base du lemme d'Arden :
     Une règle récursive à gauche de la forme A --> AX, A --> Y engendre une structure de la forme YX*.
     Cette structure est aussi bien engendrée par A --> Y, A --> YB, B --> XB, B --> X.
     où la récursion à gauche a été remplacée par une récursion à droite, que les analyseurs descendants traitent sans difficulté.
     
     Naturellement, les arbres de dérivation sont modifiés, mais sans perte d'information (notamment, sans introduire d'ambiguïté).
     Leur exploitation sera seulement un peu plus compliquée...
     

   • Exemple : la notation polonaise postfixée

      E --> E E Op, E --> Var, E --> Cte   se transforme en
     
     1. E --> Var, 
     2. E --> Cte, 
     3. E --> Var S, 
     4. E --> Cte S,  
     5. S --> E Op S, 
     6. S --> E Op.
     
     Le calcul des arbres d'expression à partir des arbres de dérivation de cette grammaire transformée s'écrit
     

     post2arb(post1(V), V).
post2arb(post2(C), C).
post2arb(post3(V, S), E) :- postAux(V, S, E).
post2arb(post4(C, S), E) :- postAux(C, S, E).

postAux(EG, post5(CD, Op, S), E) :- post2arb(CD, ED), EG1 =.. [Op, EG, ED], postAux(EG1, S, E).
postAux(EG, post6(CD, Op), E) :- post2arb(CD, ED), E =.. [Op, EG, ED].

     d'où la grammaire
     

     pTop(E) --> pE(A), {post2arb(A, E)}.
pE(post1(V)) --> vbl(V).
pE(post2(C)) --> cte(C).
pE(post3(V, S)) --> vbl(V), pS(S).
pE(post4(C, S)) --> cte(C), pS(S).
pS(post5(CD, Op, S)) --> pE(CD), pOp(Op), pS(S).
pS(post6(CD, Op)) --> pE(CD), pOp(Op).
pOp(+) --> [+].
pOp(*) --> [*].
cte(1) --> [1].
cte(2) --> [2].
vbl(x) --> [x].
vbl(y) --> [y].

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


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.