AccueilAccueil  FAQFAQ  RechercherRechercher  S'enregistrerS'enregistrer  MembresMembres  Connexion  

Partagez | 
 

 Parser GML

Voir le sujet précédent Voir le sujet suivant Aller en bas 
Aller à la page : 1, 2, 3  Suivant
AuteurMessage
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Parser GML   Mer 31 Oct 2012 - 8: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.zip

Merci d'avance :b

_________________
                 


Dernière édition par onilink_ le Mer 31 Oct 2012 - 23:11, édité 2 fois
Revenir en haut Aller en bas
Térence
Utilisateur confirmé: Rang *****
avatar

Messages : 2213
Localisation : Oui

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 8:36

J'ai pas très bien capté : t'as besoins de regex pour coloriser du GML ?
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 8: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

_________________
                 
Revenir en haut Aller en bas
Térence
Utilisateur confirmé: Rang *****
avatar

Messages : 2213
Localisation : Oui

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 8:42

Ah ok... mrgreen2
Mais tu l'as fait comment alors si t'as pas utilisé de regex ? Question
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 8:45

Analyse syntaxique par descente récursive mrgreen2
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

_________________
                 
Revenir en haut Aller en bas
Térence
Utilisateur confirmé: Rang *****
avatar

Messages : 2213
Localisation : Oui

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 8:50

Ah ok... sweat
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 ?" awesome
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 8: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 mrgreen2
-éclaircisseur de syntaxe
-convertisseur GML -> Autre langage
-optimiseur de code
etc

_________________
                 
Revenir en haut Aller en bas
Térence
Utilisateur confirmé: Rang *****
avatar

Messages : 2213
Localisation : Oui

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 9:05

Ah nan, pas d'obsfurcateur, par pitié mrgreen2
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.... awesome
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1320
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 11: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 ^^)


_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 11: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

_________________
                 
Revenir en haut Aller en bas
Morwenn
Très bonne participation
avatar

Messages : 151
Projet Actuel : Icare

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 12: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.
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 12: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 Razz
En revanche elle utiliseras des float et il seras possible d'utiliser des variables :b

_________________
                 
Revenir en haut Aller en bas
arthuro
Utilisateur confirmé: Rang ****
avatar

Messages : 1320
Localisation : Grenoble / Méribel
Projet Actuel : CBNA

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 13: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 ?)

_________________

D'autres jeux :
In The Cube
In the cube 2
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 13:38

4 pour l'instant x)
Je vais corriger ça, et j'ai ajouté la prise en charge des -x Smile

_________________
                 
Revenir en haut Aller en bas
D-z
Utilisateur confirmé: Rang *****
avatar

Messages : 1608
Localisation : Montpellier

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 14: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.
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 14: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

_________________
                 
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Mer 31 Oct 2012 - 19:46

Hop première petite version du parser d'expressions:
http://host-a.net/u/onilink_/parser.zip

Supporté:
+ - * / ( ) << >> & | ^

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.zip
Presque 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 ^^

_________________
                 
Revenir en haut Aller en bas
Morwenn
Très bonne participation
avatar

Messages : 151
Projet Actuel : Icare

MessageSujet: Re: Parser GML   Jeu 1 Nov 2012 - 15: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 Smile

_________________

Dur Dabla, pour qui voudrait écouter un brin de metal celtique.
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Jeu 1 Nov 2012 - 16: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.zip

Le 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)

_________________
                 
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Dim 4 Nov 2012 - 20: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

_________________
                 
Revenir en haut Aller en bas
Caly
Utilisateur confirmé: Rang ****
avatar

Messages : 1279
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.

MessageSujet: Re: Parser GML   Dim 4 Nov 2012 - 21:15

"Me resteplus qu'a parser le GML en entier " Yum!
Revenir en haut Aller en bas
Rem_101
*Excellent utilisateur*
avatar

Messages : 4355
Localisation : chez votre marchand de journaux

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 12:15

Oulalala oni tu oses parler du nombres de lignes de code? Mass n'est plus très loin !
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 13: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 Yum!
Le cleaner de code GML dans un gm6/gmk.

Puis pour le final le langage ODL mrgreen2
(mais ça on y est pas encore ...)

_________________
                 
Revenir en haut Aller en bas
Caly
Utilisateur confirmé: Rang ****
avatar

Messages : 1279
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.

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 14:13

Citation :
parser le GML va se faire d'une traite
Si je comprend bien tu réécrit toutes les fonctions non?
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 16: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 guns

Comme tu peut le voir le parser n'est qu'une étape parmi d'autres mrgreen2

_________________
                 
Revenir en haut Aller en bas
Morwenn
Très bonne participation
avatar

Messages : 151
Projet Actuel : Icare

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 19: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.
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 19: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++.

_________________
                 
Revenir en haut Aller en bas
Caly
Utilisateur confirmé: Rang ****
avatar

Messages : 1279
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.

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 19: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 ?
Revenir en haut Aller en bas
onilink_
Modérateur
avatar

Messages : 8898
Localisation : Montpellier
Projet Actuel : Planet Centauri
OniDev

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 20: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++.

_________________
                 
Revenir en haut Aller en bas
Caly
Utilisateur confirmé: Rang ****
avatar

Messages : 1279
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.

MessageSujet: Re: Parser GML   Lun 5 Nov 2012 - 20:04

Ha ok je comprend mieux, car ça me semblé bizarre, je pensais passer à coter d'un truc révolutionnaire.
Revenir en haut Aller en bas
Contenu sponsorisé




MessageSujet: Re: Parser GML   

Revenir en haut Aller en bas
 
Parser GML
Voir le sujet précédent Voir le sujet suivant Revenir en haut 
Page 1 sur 3Aller à la page : 1, 2, 3  Suivant

Permission de ce forum:Vous ne pouvez pas répondre aux sujets dans ce forum
Forum Le CBNA :: Informations :: Projets-
Sauter vers: