Parser GML

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

J'ai pas très bien capté : t'as besoins de regex pour coloriser du GML ?

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

Ah ok...
Mais tu l'as fait comment alors si t'as pas utilisé de regex ?

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

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 ?"

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

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....

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

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

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

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

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

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

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.

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

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 ^^

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

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)

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

"Me resteplus qu'a parser le GML en entier "

Oulalala oni tu oses parler du nombres de lignes de code? Mass n'est plus très loin !

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

Citation :

parser le GML va se faire d'une traite

Si je comprend bien tu réécrit toutes les fonctions non?

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

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^^"

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++.

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 ?

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++.

Ha ok je comprend mieux, car ça me semblé bizarre, je pensais passer à coter d'un truc révolutionnaire.