| Parser GML | |
|
+4Morwenn arthuro Térence onilink_ 8 participants |
|
Auteur | Message |
---|
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Parser GML Mer 31 Oct 2012 - 9:15 | |
| Bonjour, je suis actuellement en train de coder un parser GML et j'aurais besoin d'aide au niveau du débogage. Pour l'instant je code l'évaluateur d'expression, et j'aurais besoin d'expressions bien grosses et farfelues pour voir s'il arrive bien a les évaluer. Par exemple: 1 + 2*(3 - 2*(3 - 2)*((2 - 4)*5 - 22/(7 + 2*(3 - 1)) - 1)) + 1 Sachant qu'il ne prend en compte que des entiers et les opérateurs suivants, pour l'instant: + - * / ( ) << >> & | ^ ~ ! == != <> < > <= >= && || ^^ Vous pouvez tester directement le parser: http://host-a.net/u/onilink_/parser.zipMerci d'avance :b
Dernière édition par onilink_ le Jeu 1 Nov 2012 - 0:11, édité 2 fois |
|
| |
Térence Utilisateur confirmé: Rang *****
Messages : 2213 Localisation : Oui
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 9:36 | |
| J'ai pas très bien capté : t'as besoins de regex pour coloriser du GML ? |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 9:40 | |
| Non, j'ai besoin de grosses expressions comme celle que j'ai montré plus haut pour vérifier si mon parser déconne pas x) Et faire un parser GML a coup de regex c'est du suicide :b
|
|
| |
Térence Utilisateur confirmé: Rang *****
Messages : 2213 Localisation : Oui
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 9:42 | |
| Ah ok... Mais tu l'as fait comment alors si t'as pas utilisé de regex ? |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 9:45 | |
| Analyse syntaxique par descente récursive Le nom fait peur mais c'est plutôt simple. Actuellement mon parser fait même pas 200 lignes, et est bien aéré :b |
|
| |
Térence Utilisateur confirmé: Rang *****
Messages : 2213 Localisation : Oui
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 9:50 | |
| Ah ok... Faut que j'apprenne à utiliser cette technique comme ca je pourrais me la pèter au lycée : "Ouais ce week-end j'ai fait un analyseur syntaxique par descente récursive et toi ?" |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 9:56 | |
| Intéresse toi au parsing tout court alors, y a que des mots du genre dans ce domaine x) Par exemple un truc que j'essaye de faire depuis quelques jours mais que j'arrive pas a implémenter: un arbre de syntaxe abstraite (ou AST: Abstract Syntax Tree). Le but serais de créer un arbre a partir d'un code GML, pour pouvoir ensuite le bidouiller comme je veux. Ça permettrait de faire des trucs comme un: -obfuscateur -éclaircisseur de syntaxe -convertisseur GML -> Autre langage -optimiseur de code etc |
|
| |
Térence Utilisateur confirmé: Rang *****
Messages : 2213 Localisation : Oui
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 10:05 | |
| Ah nan, pas d'obsfurcateur, par pitié Bah j'ai cherché et je capte rien ; tant pis quand on me demandera ce que j'ai fais ce week-end je dirais que j'ai fini angry birds ; c'est déjà pas mal.... |
|
| |
arthuro Utilisateur confirmé: Rang ****
Messages : 1482 Localisation : Paris Projet Actuel : Diagon https://arthursonzogni.com/Diagon
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 12:18 | |
| voila quelques testes :
1/2/2 = 1/4 1/2/2/2/2 = 1/16 1/(2/2) = 1 1 + -1 = 0 -1*-1 = 1 ((2*2)+(2/2))-(2+2) = -1 5<<1<<1 = 1 5<<(1<<1) = 5 5<<1>>1 = 5 5<<2>>2 = 4 5+((2)) = 7 1----------1 = 2 1/-1 = -1
Alors quel est ton score sur 13 ? ( pas le droit de tricher ^^)
|
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 12:34 | |
| Merci Arthuro pour les expressions :b
1/2/2: 1 1/2/2/2/2: 1 1/(2/2): 1 1 + -1 : Erreur 1*-1 : Erreur ((2*2)+(2/2))-(2+2): 1 Les opérateurs binaires sont pas encore implémentés 5+((2)) : 7 1----------1 : erreur 1/-1 : erreur
Donc pour les divisions c'est normal, vu que c'est que des divisions entières je sais pas trop ce que ça devrait donner. 1/2 = 0 ? Pour tout ce qui est de la forme -x ça ne fonctionne pas, car je ne l'ai pas encore définis. Sinon pour ce qui est parenthèses, additions et soustractions tout a l'air bon :b
Donc pour l'instant ça fait pas beaucoup de tests réussis x)
Voici la grammaire que j'utilise: valeur := chiffre | '(' expression ')' produit := valeur { '*'|'/' produit } somme := produit { '+'|'-' produit } expression := somme { '&&' | '||' | '^^' | '==' | '!=' | '<>' | '<' | '<=' | '>' | '>=' expression }
Etant donné que j'ai enfiiin réussi a construire mon AST, je vais refaire une grammaire plus simple qui gère au moins les nombre négatifs et les nombres flottants :b
|
|
| |
Morwenn Très bonne participation
Messages : 151 Projet Actuel : Icare
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 13:29 | |
| Histoire de tester les opérateurs de comparaison de manière rigolote :p
(1+2 == 3) != (4+5 == 8)
J'ai aussi une ou deux lignes qui venaient d'un vieux parser :
5*(3+3!) // 45 232/2-69/2 // 81.5 _________________ Dur Dabla, pour qui voudrait écouter un brin de metal celtique. |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 13:35 | |
| Le premier fonctionne bien, mais j'ai pas définis factoriel, et pour le dernier j'obtient 82 :b Sinon la j'essaye de définir une nouvelle grammaire en reprenant du début, mais je galère un peu a l'implémenter correctement En revanche elle utiliseras des float et il seras possible d'utiliser des variables :b |
|
| |
arthuro Utilisateur confirmé: Rang ****
Messages : 1482 Localisation : Paris Projet Actuel : Diagon https://arthursonzogni.com/Diagon
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 14:30 | |
| Pas mal, sachant que j'ai fais tout ce que je pouvais pour faire des erreur.
Ça donnerais quoi:
4/2/2 ? ( 1 ou 4 ?) |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 14:38 | |
| 4 pour l'instant x) Je vais corriger ça, et j'ai ajouté la prise en charge des -x |
|
| |
D-z Utilisateur confirmé: Rang *****
Messages : 1611 Localisation : Montpellier
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 15:26 | |
| Je comprends pas vraiment comment fonctionne ta méthode... Perso je découperais l'expression par ordre de précédence, en commençant par les plus petites, pour avoir un arbre de sous-expressions où les opérations les plus précédentes sont les plus profondes. Lorsque deux opérateurs de précédence minimale sont adjacents, il faut les résoudre de gauche à droite (donc les parcourir de droite à gauche)
Table des précédences arithmétiques (pour les binaires je me souviens plus mais ça change rien à l'algo) :
4: () (parenthèses, opérateur unaire) 3: ^ (exposant) 2: * et / 1: + et -
Ex :
(3*5-4/2/2)/2 [O] Opérateur de précédence minimale : / Fils : (3*5-4/2/2) [G] et 2 [D]
(3*5-4/2/2) [G] OPM : () Fils unique : 3*5-4/2/2 [GU]
2 [D] Valeur, on le laisse en feuille.
3*5-4/2/2 [GU] OPM : - Fils : 3*5 [GUG] et 4/2/2 [GUD]
3*5 [GUG] OPM : * Fils : 3 [GUGG] et 5 [GUGD], qui sont des feuilles.
4/2/2 [GUD] OPM : /, on choisit celui le plus à droite ! Fils : 4/2 [GUDG] et 2 [GUDD], feuille.
4/2 [GUDG] OPM : / Fils : 4 [GUDGG] et 2 [GUDGD], feuilles.
Et voilà, tu as un arbre qui par récursion remontante te donnera le résultat correct ! L'astuce est de balayer l'expression de droite à gauche pour repérer l'OPM le plus à droite, et toujours couper comme ça. _________________ Home is not a place, it's a feeling.
|
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 15:26 | |
| Hop, j'ai corrigé tout ce qu'il faut on dirait:
1/2/2: 0 1/2/2/2/2: 0 1/(2/2): 1 1 + -1 : 0 1*-1 : -1 ((2*2)+(2/2))-(2+2): 1 5+((2)) : 7 1----------1 : 2 1/-1 : -1 4/2/2 : 1
Un parfait avec tout ça, me reste plus qu'a ajouter les opérateurs de comparaison :b
Edit: D-z > Arf on a posté en même temps. Ben je procède par analyse descendante récursive. C'est un algo étudié spécialement pour le parsing, mais même s'il parait simple a implémenter on peut faire quelques petites erreurs comme le fait de traiter les x/n/n comme x/(n/n).
En gros tu définis une grammaire, pour moi c'est : facteur := chiffre | '-' chiffre | '(' somme ')' produit := facteur { '*' | '/' produit } somme := produit { '+' | '-' produit }
Et pour chaque règle tu code une fonction. J'ai donc codé somme(), produit() et facteur(), puis au final quand tu appelle somme() ça te construit un AST qui te permet de traiter ton expression.
Après bien sur pour les précédences faut faire gaffe. Je vais essayer de faire un algo hybride plus tard voir si ça simplifie pas la tache :b |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Mer 31 Oct 2012 - 20:46 | |
| Hop première petite version du parser d'expressions: http://host-a.net/u/onilink_/parser.zipSupporté: + - * / ( ) << >> & | ^ Si personne ne trouve de bugs je continuerais avec: ! ~ == != <> < > <= >= Pour quitter le programme il suffit de faire une erreur de syntaxe :p Edit: Ne supporte pas +n, comme +1 par exemple, pas la peine de le signaler. Edit2: http://host-a.net/u/onilink_/parser.zipPresque finis, supporte tous les opérateurs courants : + - * / ( ) << >> & | ^ ~ ! == != <> < > <= >= && || ^^ Reste juste a ajouter le support des mots clé and, or, xor, et éventuellement mod et div. Edit2: bugs repérés avec les opérateurs && || et ^^ |
|
| |
Morwenn Très bonne participation
Messages : 151 Projet Actuel : Icare
| Sujet: Re: Parser GML Jeu 1 Nov 2012 - 16:29 | |
| Les opérateurs || et && sont censés faire des raccourcis et n'évaluer que la première partie de l'expression si le résultat est déjà prévu, peut-être est-ce de là que viennent les bugs ? :p Après, oui, j'avais zappé que j'avais une factorielle qui trainait dans un exemple, désolé -___- Pour la précédence des opérateurs, en général, je me base sur les tableaux de précédence trouvés dans les docs du C, C++, Perl, Python, etc... Je regarde les usages les plus courants, et j'adapte en fonction de ça. Ça donne des trucs assez intuitifs la plupart du temps _________________ Dur Dabla, pour qui voudrait écouter un brin de metal celtique. |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Jeu 1 Nov 2012 - 17:31 | |
| Pour la précédence j'ai définis ça en fonction de ce que j'ai vu dans la plupart des langages: Basse < > & | ^ << >> + - * / ( ) Haute Pour les bugs c'est réglé, tout fonctionne désormais, j'ai re up: http://host-a.net/u/onilink_/parser.zipLe problème était du fait que le C++ traite les expressions de manière paresseuse, et je ne l'avais pas pris en compte ouai. Quand je faisais un x = x or fonction(), ben si x était considéré comme un false, fonction() n'était pas exécuté, et ça me faisait une boucle infinie (c'était dans un while true). Donc la tout les opérateurs de GM sont désormais supportés (a part = qui est le ==, div et mod). Pour la suite, il me faudra travailler uniquement sur mon AST, traiter les fonctions utilisées dans les expressions, ainsi que les variables. Puis viendra la grosse difficulté, implémenter le langage en lui même x) (je compte créer un interpréteur en même temps que le parser, tant qu'a faire :b) |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Dim 4 Nov 2012 - 21:58 | |
| Gère désormais - Code:
-
-Opérateurs arithmétique de base + - * / ( )
-Opérateurs binaires << >> & | ^ ~
-Opérateurs de comparaison ! == != <> < > <= >= && || ^^ and or xor
Fonctions supportées: sqrt(x) sqr(x) pow(x, n) min(a, b, ..) max(a, b, ..) hello() exit()
Me reste plus qu'a parser le GML en entier d'un coté, et faire mon interpréteur de l'autre :b |
|
| |
Caly Utilisateur confirmé: Rang ****
Messages : 1285 Localisation : Haute Normandie Projet Actuel : Capturer, apprivoiser et dresser des Pokémons sauvages pour faire des spectacles de rue et en faire mon métier.
| Sujet: Re: Parser GML Dim 4 Nov 2012 - 22:15 | |
| "Me reste plus qu'a parser le GML en entier " |
|
| |
Rem_101 *Excellent utilisateur*
Messages : 4356 Localisation : chez votre marchand de journaux
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 13:15 | |
| Oulalala oni tu oses parler du nombres de lignes de code? Mass n'est plus très loin ! |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 14:33 | |
| Ben non vu que c'était pour prouver que c'est plutôt simple a implémenter x) Caly > Contrairement a ce que l'on pourrais croire, en fait dans un langage le truc le plus ****** a parser ben c'est les expressions x) Donc dès que j'ai le temps de m'y mettre, parser le GML va se faire d'une traite, et je vais pouvoir coder les milles applications que je voulais faire o/ La première étant la conversion GML -> C++ :b Puis viendra l'obfuscateur qui me permettra de sortir facilement des exos pour la compétition Le cleaner de code GML dans un gm6/gmk. Puis pour le final le langage ODL (mais ça on y est pas encore ...) |
|
| |
Caly Utilisateur confirmé: Rang ****
Messages : 1285 Localisation : Haute Normandie Projet Actuel : Capturer, apprivoiser et dresser des Pokémons sauvages pour faire des spectacles de rue et en faire mon métier.
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 15:13 | |
| - Citation :
- parser le GML va se faire d'une traite
Si je comprend bien tu réécrit toutes les fonctions non? |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 17:46 | |
| Non, le parser sert juste a analyser. Mon parser crée un arbre de syntaxe abstraite a partir du code qu'il a reçu en entrée. Avec cet arbre, je peut faire un traitement des données, les transformer, sans prendre en compte les fonctions, mis a part peut être leur nom et nombre d'argument (histoire de vérifier les éventuelles erreurs). Une fois que je serais capable de convertir un gm6 en c++, la par contre il faudra réécrire les fonctions et les mettre dans une librairie gml pour compiler, mais ça c'est le moins important. Puis c'est simple a faire, juste long a écrire. Donc la, étape 1: parser le GML Etape 2: utiliser l'AST qui a été crée pour isoler les variables de chaque objet, créer les classes, générer le code pour chaque event. Etape 3: coder la lib GML avec toutes les fonctions de GM, et qui peut utiliser les données de GM comme les sprites/paths/rooms. Etape 4: compiler Comme tu peut le voir le parser n'est qu'une étape parmi d'autres |
|
| |
Morwenn Très bonne participation
Messages : 151 Projet Actuel : Icare
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 20:04 | |
| Après, la transformation GML/C++ demande quand même quelques (voire beaucoup de) variables globales supplémentaires, non ? Ne serait-ce que pour transformer correctement les expressions basées sur with, ça t'oblige de maintenir des listes globales de pointeurs sur tous les objets instanciés^^" _________________ Dur Dabla, pour qui voudrait écouter un brin de metal celtique. |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 20:14 | |
| Oui le with est LE truc chiant du GML.
J'ai noté une solution quelque part mais elle n'est pas très élégante. Surtout que with peut avoir soit un id d'instance en paramètre, soit un id d'objet, soit même quelque mots clé spéciaux...
Bref si quelqu'un a une bonne idée pour gérer ça ... x)
D'ailleurs certains cas devront être interdits... car impossibles a implémenter en C++. |
|
| |
Caly Utilisateur confirmé: Rang ****
Messages : 1285 Localisation : Haute Normandie Projet Actuel : Capturer, apprivoiser et dresser des Pokémons sauvages pour faire des spectacles de rue et en faire mon métier.
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 20:53 | |
| Donc en fait tu parse un code déjà exécuté? car je pige pas comment tu peut récupérer le retour d'une fonction si elle n’est pas connus ? |
|
| |
onilink_ Modérateur
Messages : 9180 Localisation : Montpellier Projet Actuel : Planet Centauri
OniDev
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 21:01 | |
| Dans la console y a un retour pour montrer que le parser marche, mais en fait le parser ne retourne aucune valeur, il se contente de créer l'AST, qui seras ensuite transformé en C++. |
|
| |
Caly Utilisateur confirmé: Rang ****
Messages : 1285 Localisation : Haute Normandie Projet Actuel : Capturer, apprivoiser et dresser des Pokémons sauvages pour faire des spectacles de rue et en faire mon métier.
| Sujet: Re: Parser GML Lun 5 Nov 2012 - 21:04 | |
| Ha ok je comprend mieux, car ça me semblé bizarre, je pensais passer à coter d'un truc révolutionnaire. |
|
| |
Contenu sponsorisé
| Sujet: Re: Parser GML | |
| |
|
| |
| Parser GML | |
|