Discussion :

[Black Templar]

Bonjour à tous.

Je suis en train de me familiariser avec les règles de grammaire de Prolog (sicstus) : les DCGs

J'ai essayé de faire un petit programme pour interpréter une chaine de caractère contenant une expression mathématique.
ça marche très bien si on fait la somme, différence, produit ou rapport de chiffre, mais dès qu'on essaye de mettre un nombre, ça plante (le programme boucle à l'infini)

Voila le code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
calcul(Z) --> expr(X), "-", term(Y), part_exp(W), {Z is X - Y + W}.
calcul(Z) --> expr(X), "-", term(Y), {Z is X - Y}.
calcul(Z) --> expr(Z).
 
part_exp(Z) --> "+", calcul(Z).
part_exp(Z) --> "-", calcul(X), {Z is -X}.
 
expr(Z) --> term(X), part_exp(Y), {Z is X + Y}.
expr(Z) --> term(Z).
 
term(Z) --> number(X), "*", term(Y), {Z is X * Y}.
term(Z) --> number(X), "/", term(Y), {Z is X / Y}.
term(Z) --> number(Z).
 
number(C) --> "+", nb(C,_).
number(C) --> "-", nb(X,_), {C is -X}.
number(C) --> nb(C,_).
 
nb(C,A) --> digit(X), nb(Y,A1), {pow(10,A1,R), C is X*R+Y, A is A1+1}.
nb(C,1) --> digit(C).
 
digit(X) --> [C], {"0"=<C, C=<"9", X is C - "0"}.
 
pow(Nb, 1, Nb).
pow(Nb, P, R):-
	P1 is P-1,
	pow(Nb, P1, R1),
	R is R1*Nb.

Si on essaye d'exécuter

phrase(calcul(Z), "-1-2*2+2*3+1").

Tout marche bien et on obtient bien Z = 2

Par contre, ça plante si on fait simplement

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

phrase(calcul(Z), "421").

J'ai isolé un peu le problème
Si on teste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

phrase(nombre(Z), "421").

Tout marche bien. Z vaut 421
Par contre, si on teste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

phrase(term(Z), "421").

Là, ça boucle...

Je ne comprend pas bien pourquoi. Auriez-vous une idée ??
Black Templar

P.S. : Ma fonction pow est naïve, je ne l'ai pas encore optimisé, c'est normal.

[Trap D]

Bonjour

Il y a un bon outil qui s'appelle le debug, je ne sais pas comment il se lance avec sictus, mais renseigne toi, cela permet de trouver les erreurs.
Je ne suis pas spécialistes des grammaires mais elle me parait un peu bizarre.
J'ai "résolu" ton problème en mettant un cut à la fin de la dernière clause de number/2 mais ce n'est pas satisfaisant.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
number(C) --> "+", nb(C,_).
number(C) --> "-", nb(X,_), {C is -X}.
number(C) --> nb(C,_), !.

[Black Templar]

Oh mon dieu !!!

Il me prend un bon millier d'étapes rien que pour me parser "421" !!!!
J'ai vraiment intérêt à comprendre comment ça marche en interne avant de vouloir l'utiliser :/

Le cut ne résous pas tous les problèmes. si je force le backtracking, il me sort d'autres réponses !
Sinon, pour le mode debug sous Sicstus, il faut activer la "trace", mais c'est assez dégueulasse à lire...

Merci pour l'idée du cut ! J'ai encore pas mal de boulot :/
++

[Trap D]

Je pense que tu aurais intérêt à te pencher sur la grammaire des expressions algébriques, il en traîne un peu partout sur le web.

[Black Templar]

Ok, merci, je vais regarder ça. (le but n'étant pas de faire un interpréteur d'expressions arithmétiques, mais juste de comprendre comment fonctionne les DCGs)

Voila le code un peu remanier :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
calcul(Z) --> term(X), part_expr(Y), {Z is X + Y}.
calcul(Z) --> term(Z).
calcul(Z) --> part_expr(Z).
 
part_expr(Z) --> "+", calcul(Z).
part_expr(Z) --> "-", term(Y), {Z is -Y}.
part_expr(Z) --> "-", term(Y), calcul(X), {Z is -Y+X}.
 
term(Z) --> number(X), "*", term(Y), {Z is X * Y}.
term(Z) --> number(X), "/", term(Y), {Z is X / Y}.
term(Z) --> number(Z).
 
number(Z) --> nb(Z,_).
nb(C,A) --> digit(X), nb(Y,A1), {pow(10,A1,R), C is X*R+Y, A is A1+1}.
nb(C,1) --> digit(C).
 
digit(X) --> [C], {"0"=<C, C=<"9", X is C - "0"}.
 
pow(Nombre, Puissance, Resultat):-
	pow_1(Nombre,Puissance,Resultat,1).
pow_1(_,0,R,R):-!.
pow_1(Nombre,Puissance,Resultat,Accumulateur):-
	P1 is Puissance-1,
	Accumulateur1 is Accumulateur*Nombre,
	pow_1(Nombre, P1, Resultat, Accumulateur1).