 |
| Parsing: formule math vers code rebol | |
| François | 11-Mar-2011/16:05:16+1:00 |
| Bonjour, Je cherche a programmer une fonction qui serait capable de parser une formule mathématique exprimée "naturellement" en un bloc de code rebol que l'on pourra exécuter. par exemple, une fonction 'parse-formula renverrait le résultat suivant: >> parse-formula "SQRT(1-x^2)/(1-x)^3" == [divide square-root subtract 1 power x 2 power subtract 1 x 3] J'ai trouver le code suivant dans la documentation officielle que j'essaie actuellement en vain d'exploiter pour atteindre cet objectif:
expr: [term ["+" | "-"] expr | term]
term: [factor ["*" | "/"] term | factor]
factor: [primary "**" factor | primary]
primary: [some digit | "(" expr ")"]
digit: charset "0123456789"
probe parse "1 + 2 * ( 3 - 2 ) / 4" expr
true
J'ai l'intime conviction qu'il est possible d'y arriver avec ce code, mais je butte pour le moment. Merci pour votre aide! | |
| François | 13-Mar-2011/14:28:49+1:00 |
| Bonjour, Ne trouvant rien à ce sujet sur le net, j'ai finalement réussi à développer, tout seul comme un grand, un parser d'équation mathématique que je trouve plutôt élégant  Je finalise le code et je poste tout cela sur rebol.org. A bientôt | |
| François | 13-Mar-2011/14:34:11+1:00 |
POur vous donnez un avant-goût:>> print mold parse-equation "3*(3+x)**sin(2-i)+cos((3*y)**3*(a-b))+1" [add multiply 3.0 power add 3.0 x sine/radians subtract 2.0 i add cosine/radians power multi ply 3.0 y multiply 3.0 subtract a b 1.0] | |
| François | 13-Mar-2011/15:28:43+1:00 |
| Et voilà, Une première version est disponible http://www.rebol.org/view-script.r?script=parse-equation.r | |
| François | 13-Mar-2011/18:15:28+1:00 |
| J'ai un petit truc qui me gène. La représentation standard/naturelle d'une exponentielle est x^y et pas la bizarrerie rebol x ** y. J'aimerais donc que mon dialecte utilise le ^ et pas le **. Mais comme le ^ est reconnu comme le caractère d'échappement par rebol, je bute sur une erreur systématiquement. Y-aurai-t-il un moyen de contourner ce problème? D'avance merci! | |
| guest2 | 13-Mar-2011/19:29:46+1:00 |
| ben faut doubler non ? >> print "1^^2" ==1^2 | |
| François | 13-Mar-2011/20:18:21+1:00 |
Oui... mais pour un utilisateur lamba... encoder 1^^2 pour faire 1^2 n'est pas naturel  | |
| François | 14-Mar-2011/7:05:42+1:00 |
| Et voilà, je pense que maintenant mon script est quasi final. Il ne lui manque plus que la gestion des erreurs syntaxiques afin de renvoyer à l'utilisateur un message utile lorsqu'il fait une erreur dans son equation (per exemple, il oublie de fermer une parenthèse). La dernière version disponible sur http://www.rebol.org/view-script.r?script=parse-equation.r - améliore grandement l'implémentation récursive: le code est plus simple et plus élégant . - apporte le support pour les fonctions mathématiques les plus courantes: abs(), arcos(), acos(), arcsin(), asin(), arctan(), atan(), cos(), exp(), log(), ln(), sin(), sqrt(), tan() - fixe un bug de priorité entre '**' et '*': ainsi, l'équation "3**2*5 retourne bien maintenant [multiply power 3 2 5] et non pas [power 3 multiply 2 5] Bon sang, qu'est-ce que j'aime l'expressivité de rebol Voili, voilou | |
| Didec | 14-Mar-2011/9:59:35+1:00 |
| Bravo ! | |
| François | 14-Mar-2011/21:51:12+1:00 |
| Merci Didec! Un bravo venant d'un expert rebol de ton gabarit... cela fait toujours plaisir Entre-temps, j'ai sorti une nouvelle version qui gère les nombres signés et les expressions signées: Un exemple tiré par les cheveux >> parse-equation "+(1+-x)**-sqrt(-1--x)" == [power add 1.0 negate x negate square-root subtract -1.0 negate x] A bientôt. François | |
| shadwolf | 15-Mar-2011/3:58:15+1:00 |
| voila tout l'interret de parse ... avec juste ton example tu as de quoi a mon avis ecrire un article fort pationnant sur parse et les dialectes métiers :P Bravo françois en tout cas. N'oubli pas de publier ton script sur rebol.org pour la postérité | |
| François | 15-Mar-2011/20:28:48+1:00 |
| Merci Shadwolf pour ton mot d'encouragement. Venant d'un programmeur rebol de la première heure, c'est toujours agréable. Entre-temps, ladislav sur Altme m'a fait remarquer que mon implémentation ne respectait absolument pas l'associativité des opérations d'addition, de soustraction, de multiplication et de division. En effet, 3-2+1 fait 2 et non pas 0. Ors, la version 0.9.3 renvoyait >> parse-equation "3-2+1" == [subtract 3.0 add 2.0 1.0] >> do parse-equation "3-2+1" == 0.0 Ce qui est faut. Et bien en remplaçant simplement 5 'append par des 'insert, j'ai corrigé le bug. La version 0.9.4 (renommée pour l'occasion en parse-expression.r, ce qui est plus correcte d'un point de vue terminologique) renvoit maintenant: >> parse-expression "3-2+1" == [add subtract 3.0 2.0 1.0] >> do parse-expression "3-2+1" == 2.0 Ce qui respecte l'associativité. ATTENTION: du fait de renommage en parse-expression.r, le script est vu par rebol.org comme une nouvelle contribution et est accessible via un nouveau lien: http://www.rebol.org/view-script.r?script=parse-equation.r | |
| trigram | 15-Mar-2011/21:44:37+1:00 |
| Francois, Serais-tu intéressé par l'écriture d'un article sur parse avec ton parse équation comme exemple ? D'avance merci pour ta réponse. Nico | |
| François | 15-Mar-2011/22:19:44+1:00 |
| Avec plaisir, mais difficile de m'engager sur un timing précis dans l'immédiat | |
| trigram | 15-Mar-2011/22:25:46+1:00 |
| Aucun problème, j'ai le temps. L'objectif du nouveau site est de le faire vivre au fil du temps. Merci pour ton aide. Nico | |
| François | 16-Mar-2011/22:51:45+1:00 |
| Bonjour, Une nouvelle version (0.9.5) de parse-expression est disponible sur rebol.org. Cette version fixe deux bugs que j'ai découvert en rédigeant la documentation, elle aussi accessible sur rebol.org http://www.rebol.org/view-script.r?script=parse-expression.r | |
| yos | 3-Apr-2013/8:27:40+2:00 |
| Salut, Toujours besoin d'aide François ? Comme tu le dis au tout début, je pensais aussi comme toi que l'on pouvait exploiter la grammaire et les 5 règles données dans la doc officielle pour générer le code Rebol à partir du texte d'une expression mathématique. Mais, comme chacune de ces règles est récursive à souhait, quand on essaye d'extraire du texte ou de regarder ce qui se passe avec des prints, tous les termes extraits se multiplient et comme toi je n'ai pas réussi à le faire avec parse, tout du moins avec cette grammaire BNF là ! L'idée est donc d'utiliser parse, avec idéalement 1 seule règle récursive qui descendrait dans les sous-expressions entres ( ... ) ou celles des opérations cos( ... ). C'est donc parse qui gère la récursivité, et l'expressivité de Rebol qui nous permet d'empiler les éléments lus et transcrits en mots dans une structure de blocs. La fonction expr? est donc non récursive mais la grammaire BNF utilisée oui. (Je n'ai jamais été fan de récursivité même si il est primordial pour un langage de l'implémenter. Peut-être est elle impressionante dans les autres langages pour les rendre plus beau syntaxiquement mais avec l'expressivité de Rebol je préfère m'en passer ! J'ai aussi une puissante fonction de recherche de fichier non récursive dans mon framework maison mais c'est une autre histoire...). Revenons à la question : En supprimant les 2 ";" du code de la fonction expr? on active le debugage de la première expression : >> do %expr.r 1 * (2 * (3 - sqrt(4 * sqrt(16)) + 5)) [[1.0]] [[multiply 1.0 []] [2.0]] [[multiply 1.0 []] [multiply 2.0 []] [3.0]] [[multiply 1.0 []] [multiply 2.0 []] [subtract 3.0 [square-root]] [4.0]] [[multiply 1.0 []] [multiply 2.0 []] [subtract 3.0 [square-root]] [multiply 4.0 [square-root]] [16.0]] [[multiply 1.0 []] [multiply 2.0 []] [add subtract 3.0 square-root multiply 4.0 square-root 16.0 5.0]] [multiply 1.0 multiply 2.0 add subtract 3.0 square-root multiply 4.0 square-root 16.0 5.0] = 8.0 - Les expressions sont ajoutées dans un bloc les contenant toutes. - L'expression courante (en cours de construction) est la dernière de ce bloc. - Quand on rencontre une "(" c'est le début d'une sous-expression). On réserve à la fin de l'expression courante un bloc vide [] qui contient le cas échéant la fonction mathématique appelée (cos, racine ...) et un nouveau bloc est ajouté à la fin de la liste pour empiler cette nouvelle expression. - Quand on rencontre une ")" c'est la fin de l'expression courante et on la réintègre dans celle précédente puis on l'a supprime de la fin de la liste. On repositionne alors le pointeur expr pour continuer à construire la dernière expression de la liste. François, les exmemples ci-dessous sont inspirés des tiens :
1 * (2 * (3 - sqrt(4 * sqrt(16)) + 5))
[multiply 1.0 multiply 2.0 add subtract 3.0 square-root multiply 4.0 square-root 16.0 5.0]
= 8.0
-1
[negate 1.0]
= -1.0
+1
[1.0]
= 1.0
1 + 2 + 3
[add add 1.0 2.0 3.0]
= 6.0
1 + 2 * 3
[add 1.0 multiply 2.0 3.0]
= 7.0
1 * 2 + 4 * 5
[add multiply 1.0 2.0 multiply 4.0 5.0]
= 22.0
(1 + 2) * 3
[multiply add 1.0 2.0 3.0]
= 9.0
-((1 + 2) * 3)
[negate multiply add 1.0 2.0 3.0]
= -9.0
3 * (1 + 2)
[multiply 3.0 add 1.0 2.0]
= 9.0
SQRT(1-x**2)/(1-x)**3
[divide square-root subtract 1.0 power x 2.0 power subtract 1.0 x 3.0]
= 1.0
3*(3+x)**sin(2-i)+cos((3*y)**3*(a-b))+1
[add add multiply 3.0 power add 3.0 x sine/radians subtract 2.0 i cosine/radians multiply power multiply 3.0 y 3.0 subtract a b 1.0]
= 10.1464122518508
+(1+-x)**-sqrt(-1--x)
[power add 1.0 negate x negate square-root subtract negate 1.0 negate x]
= make object! [
code: 402
type: 'math
id: 'positive
arg1: none
arg2: none
arg3: none
near: [power add 1.0 negate x]
where: none
]
3-2+1
[add subtract 3.0 2.0 1.0]
= 2.0
4/2*2
[multiply divide 4.0 2.0 2.0]
= 4.0
2**3*6
[multiply power 2.0 3.0 6.0]
= 48.0
1-2**3*6
[subtract 1.0 multiply power 2.0 3.0 6.0]
= -47.0
4/5+3**2-(5*6+1)
[subtract add divide 4.0 5.0 power 3.0 2.0 add multiply 5.0 6.0 1.0]
= -21.2
sqrt(3*3)
[square-root multiply 3.0 3.0]
= 3.0
1-x**3
[subtract 1.0 power x 3.0]
= 1.0
(1-x)**3
[power subtract 1.0 x 3.0]
= 1.0
(1+1)/(1-x)**3
[divide add 1.0 1.0 power subtract 1.0 x 3.0]
= 2.0
sqrt(1+1)/(1-x)**3
[divide square-root add 1.0 1.0 power subtract 1.0 x 3.0]
= 1.4142135623731
-(1+1)/(1-x)**3
[negate divide add 1.0 1.0 power subtract 1.0 x 3.0]
= -2.0
+(1+2)/-(1-2)
[divide add 1.0 2.0 negate subtract 1.0 2.0]
= 3.0
1 - 2
[subtract 1.0 2.0]
= -1.0
-(1 + 2)
[negate add 1.0 2.0]
= -3.0
-1/2
[divide negate 1.0 2.0]
= -0.5
(-1)/2
[divide negate 1.0 2.0]
= -0.5
-(1)/2
[negate divide 1.0 2.0]
= -0.5
Ci-dessous le source de la fonction expr? et son jeu de test (rappel: supprimer juste les 2 ";" pour débuguer la première expression). Peut-être avez vous d'autre exemples d'expressions à me fournir pour valider l'exactitude de la méthode utilisée. Merci. Have Fun ! Yos
REBOL []
expr?: func
[ math-expression
/local
exprs fx expr text
digit number parameter primary factor term expression
]
[ exprs: copy []
fx: copy []
append/only exprs expr: copy []
digit: charset "0123456789"
number: [some digit]
parameter: charset "abcdefghijklmnopqrstuvwxyz"
primary:
[ copy text number (append expr to decimal! trim/all text) ; (probe head exprs)
| opt
[ "abs" (fx: copy [abs])
| "acos" (fx: copy [arccosine/radians])
| "arccos" (fx: copy [arccosine/radians])
| "arcsin" (fx: copy [arcsine/radians])
| "arctan" (fx: copy [arctangent/radians])
| "asin" (fx: copy [arcsine/radians])
| "atan" (fx: copy [arctangent/radians])
| "cos" (fx: copy [cosine/radians])
| "exp" (fx: copy [exp])
| "ln" (fx: copy [log-e])
| "log2" (fx: copy [log-2])
| "log10" (fx: copy [log-10])
| "sin" (fx: copy [sine/radians])
| "sqrt" (fx: copy [square-root])
| "tan" (fx: copy [tangent/radians])
]
"("
( append/only expr fx
fx: copy []
append/only exprs expr: copy []
)
expression
")"
( insert head expr last first back back tail exprs
remove back tail first back back tail exprs
temp: tail first back back tail exprs
expr: append first back back tail exprs head expr
remove back tail exprs
expr: temp
)
| "+" expression
| "-" (append expr 'negate) expression
| copy text parameter (append expr to word! trim/all text)
]
factor:
[ primary any
[ [ "**" (insert expr 'power)
| "^^" (insert expr 'power)
| "//" (insert expr 'remainder)
]
primary
]
]
term:
[ factor any
[ [ "*" (insert expr 'multiply)
| "/" (insert expr 'divide)
]
factor
]
]
expression:
[ term any
[ [ "+" (expr: tail insert head expr 'add)
| "-" (expr: tail insert head expr 'subtract)
]
term
]
]
parse math-expression expression
first head exprs
]
a: b: i: x: y: 0
foreach e
[ "1 * (2 * (3 - sqrt(4 * sqrt(16)) + 5))"
"-1"
"+1"
"1 + 2 + 3"
"1 + 2 * 3"
"1 * 2 + 4 * 5"
"(1 + 2) * 3"
"-((1 + 2) * 3)"
"3 * (1 + 2)"
"SQRT(1-x**2)/(1-x)**3"
"3*(3+x)**sin(2-i)+cos((3*y)**3*(a-b))+1"
"+(1+-x)**-sqrt(-1--x)"
"3-2+1"
"4/2*2"
"2**3*6"
"1-2**3*6"
"4/5+3**2-(5*6+1)"
"sqrt(3*3)"
"1-x**3"
"(1-x)**3"
"(1+1)/(1-x)**3"
"sqrt(1+1)/(1-x)**3"
"-(1+1)/(1-x)**3"
"+(1+2)/-(1-2)"
"1 - 2"
"-(1 + 2)"
"-1/2"
"(-1)/2"
"-(1)/2"
]
[ print ""
print e
probe e: expr? e
prin "= "probe either error? err: try [e: first reduce e] [disarm err] [e]
; break
]
print ""
| |
| DocKimbel | 3-Apr-2013/12:29:59+2:00 |
| Bravo, joli travail ! Si tu pouvais pousser ce script sur rebol.org, ça serait bien, on pourrait le réutiliser pour des démos de PARSE (notamment lors des conférences). Je pense que c'est le genre de démo qui peut vraiment attirer l'attention de nouveaux venus sur REBOL et Red. Pour le code, j'ai deux remarques: - Il serait vraiment plus pratique d'adopter un style plus "standard" pour la position des crochets ouvrant, à savoir les positionner en fin de ligne plutôt que d'aller à la ligne. La différence, c'est que le script peut alors être copier/coller dans la console, en l'état ce n'est pas possible, c'est dommage... - Le HEAD final dans `first head exprs` n'est pas utile, tu ne modifies jamais l'index du block pointé par `exprs`. | |
| DideC | 8-Apr-2013/12:32:45+2:00 |
| Je plussois le post de Dockimbel. Jolie travail ! | |
| shadwolf | 8-Apr-2013/20:48:43+2:00 |
| aaaaaah si seulement il y avait une interface graphique digne de ce nom sur r3 on aurait pu faire une tres belle caculatrice scientifique programmable et qui dessine de jolies courbes tout ca... bref un jour peut etre cyphre planche sur le sujet ! | |
| François | 19-Apr-2013/14:57:47+2:00 |
| Bonjour Yos Cela fait très longtemps que j'ai développé parse-expression.r... et je dois avouer que je ne vois pas très bien la différence avec ton implémentation... Cordialement | |
|
Login required to Post. | |