Pistes pour un 'parser' de scripts

Version imprimable

24/03/2011, 16h59
poringkiller

Pistes pour un 'parser' de scripts
Bonjour, je suis actuellement en train de développer un jeu en ligne qui fait intervenir des personnages non joués (PNJ ou NPC) pour donner la possibilité de faire des quêtes (entre autre). J'ai dans l'idée que le plus simple pour pouvoir en créer une multitude, qui puissent avoir des fonctionnalités variées, est de créer un langage de script pour les faire dialoguer avec le joueur. Leurs coordonnées, nom, identifiant seraient stockés en base de donnée, ainsi que leur code (dans un champ varchar ou text)

Je désire créer un langage relativement complet, mais non Object Oriented, 'juste' du procédural suffira, incluant des variables, des boucles, des structures conditionnelles etc... Pour cela il faut qu'au moment ou le PNJ est activé par un joueur, il y ai un interpréteur de script qui parse ce code, et l'execute à la volée.

J'ai quelques idées pour commencer à développer ce genre de parser, mais je préfèrerais, avant de me lancer dans le codage de ce petit monstre, avoir l'avis de gens qui se seraient déjà penchés sur un problème similaire.

Pour le moment mes idées sont :
- - créer une methode qui lis des mots (suite de chiffre, lettres, ou underscore) afin de déterminer la commande à executer.
- - si la commande est reconnue on va chercher ses arguments dans la suite, et si ils sont valides on fait nos histoires avec le client et le serveur
- - définir une liste des mots disponibles, et des caractères qui ne peuvent constituer un mot (par exemple ;() {} pour les boucles et arguments)
seulement j'ai des difficultés face à des problèmes relativement simples tels que la commande "say" qui prend une chaine de caractère en argument ex:

say "Bonjour "+getCharName()+" comment vas-tu?";

sachant que getCharName() sera une fonction qui renverra le nom du personnage joué.

peut-etre que la base de mon algorithme n'est pas bonne? Toute idée est la bienvenue

je ne précise pas de langage car toute idée d'implémentation de ce parser est la bienvenue, qu'elle soit en POO ou non

Merci d'avance pour votre aide :roll:
29/03/2011, 19h30
forthx

Bonjour,

Je dirai que tu a plusieures possibilitées. Si tu veu absolument recree un moteur d'execution de script tu a interet a preciser clairement ses limite, l'interet de faire son propore moteur c'est generalement de perdre en généricité, mais de gagner en temps d'execution (parfois) mais surtout d'apporter de la simplicitée lors de l'ecriture des script.

Si tu a besoin d'executer de scriptes complet, avec gestion de variable de different types, boucles, execution conditionnelle, ... Ca peut etre interessant de se pencher sur des langages (et donc interpreteurs) deja existant (comme lua)

Si tu souhaite faire une usine a gaz maison tout de meme, ca pourra peut etre t'aider de regarder ce qui a ete fait.

pour ton exemple c'est en effet une commande simple. si on part du principe que tu appel des fonctions sans paramettres a l'exterieur tu pour envisager la ligne suivante:

Code:

"say: Bonjour [player], comment va?"

tu formalise tout ca pour ton analyse:
- les lettres (char) avant le ":" sont toujour la commande
- les chars entre [] font reference a une fonction (ou une variable a toi de choisir)

ce qui te permet de trier tes chaine rapidement en fonction de la commande dans un premiers temps, puis de remplacer les groupes[*] par leur valeur (que ce soit des variable ou des fonctions) en decoupant ta chaine a l'aide d'expressions regulieres par exemple.
Tu peu aussi adapter la syntaxe pour simplifier ton developpement, a voir avec celui qui va ecrire les scripts ;)
06/04/2011, 17h32
poringkiller

merci pour ces informations :ccool:
tu as raison, avant de définir la méthode pour parser les scripts il faut tout d’abord en définir clairement les règles syntaxiques.

le LUA ne correspond pas vraiment à mes besoins, qui sont en fait très spécifiques, je ne veux pas créer une librairie de fonctions, mais vraiment un langage de programmation, gérant des variables de portée différente, des évènements, et même la possibilité d'utiliser/créer des variables dont les noms sont dynamiques.

c'est aussi (je dois l'avouer) pour le plaisir de la satisfaction intellectuelle de coder ce genre de choses, et c'est pour ça que je prend mon temps pour la phase de réflexion sur l'algorithme à suivre ;)

je pars sur une syntaxe proche du C, avec deux types de variables, entiers et strings, une gestion facilitée des strings (comme pour du java) mais le typage se fera dans le nom de la variable : préfixage d'un symbole (ex: @ ou #) pour la portée, et postfixage (ou non) d'un symbole (ex: le signe $) pour le type

j'ai dans l'idée qu'il sera plus simple de tout (variables, nom/position des npc, nom des labels d'évènements) en base de donnée, ce qui permettra de les retrouver assez rapidement

si vous avez d'autres idées ou suggestions n'hésitez pas :D

Salut !

J'ai fais un langage similaire, et je peux te dire que ça m'a pris 5 essais et quelques années de travail. Je peux te fournir le code si tu est interessé. Redis moi.

Exemple de code :

Code:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
package gPlayer;
 
 
using System;
 
var i = #[ 5.56, 4, 34, 76, #[ "Test", function( ) { return 5; } ] ];
System.Echo( i );
System.Echo( i[4][1]( ) ); // ça devrait afficher 5 :)
 
using System.Math;
 
 
var source		= "System.Echo(\"value: \", val, \"\\n\");\n";
global var val	= "Hello World!";
var compiled	= System.Compile( source );
 
System.Echo( "J'affiche une ligne\n" );
System.Echo( "J'affiche deux ligne\n" );
System.Echo( "J'affiche trois ligne\n" );
 
System.Binder->Bind( 'p', "echo \"H2O Engine rocks !\"" );
System.Shell->ExecuteCommand( "p" );
 
object OPlayer extends System.WorldObject
{
	public method test( nombre )
	{
		nombre = System.ParseInt( System.Shell->GetVarValue( "testVar" ) );
		var str = System.Sprintf( "La racine carree de %i est %3.1f\n", nombre, System.Math.Sqrt( nombre ) );
		System.Echo( str );
	}
};
 
object OTest
{
	public method test( )
	{
		System.Echo( "Test\n" );
	}
};
 
compiled( );
 
global var g_player = new OPlayer;
System.World->SpawnObject( g_player );
g_player = new OPlayer;

et un ptit dernier pour la route

Code:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
package Working;
 
using System;
using System.Draw;
using System.Application;
using System.Math;
 
function RANDOM_FLOAT( v1, v2 )
{
	return v1 + (v2-v1)*(System.Random( )*1.0f)/(1.0f*0x7fff);
}
 
object OStatsMaker
{
	public var _avgFPS;
	public var _bestFPS;
	public var _lastFPS;
	public var _worstFPS;
	public var _bestFrameTime;
	public var _worstFrameTime;
 
	public var _lastTime;
	public var _lastSecond;
	public var _frameCount;
 
	method resetStats( )
	{
		_avgFPS = _bestFPS = _lastFPS = 0.0;
		_worstFPS = 999.0;
		_bestFrameTime = 999999;
		_worstFrameTime = 0.0;
 
		_lastTime = _lastSecond = System.TimeGetTime( );
		_frameCount = 0;
	}
 
	public var AverageFPS
	{
		get { return _avgFPS * 1000000; }
	}
 
	public var BestFPS
	{
		get { return _bestFPS * 1000000; }
	}
 
	public var LastFPS
	{
		get { return _lastFPS * 1000000; }
	}
 
	public var WorstFPS
	{
		get { return _worstFPS * 1000000; }
	}
 
	public var BestFrameTime
	{
		get { return _bestFrameTime; }
	}
 
	public var WorstFrameTime
	{
		get { return _worstFrameTime; }
	}
 
	method updateStats( )
	{
		++_frameCount;
        var thisTime = System.TimeGetTime( );
 
        // check frame time
        var frameTime = thisTime - _lastTime;
        _lastTime = thisTime ;
 
        _bestFrameTime	= System.Math.Min(_bestFrameTime, frameTime);
        _worstFrameTime = System.Math.Max(_worstFrameTime, frameTime);
 
        // check if new second (update only once per second)
        if (thisTime - _lastSecond > 1000) 
        { 
            // new second - not 100% precise
            _lastFPS = _frameCount / ((thisTime - _lastSecond) * 1000.0);
 
            if (_avgFPS == 0)
                _avgFPS = _lastFPS;
            else
                _avgFPS = (_avgFPS + _lastFPS) / 2; // not strictly correct, but good enough
 
            _bestFPS = System.Math.Max(_bestFPS, _lastFPS);
            _worstFPS = System.Math.Min(_worstFPS, _lastFPS);
 
            _lastSecond = thisTime;
            _frameCount  = 0;
        }
	}
};
 
object OObject extends System.Object
{
	public var _position;
 
	public var Position
	{
		set { _position = value; }
		get { return _position;  }
	}
};
 
 
object OCube extends OObject
{
	public var m_size;
	public var m_angleX;
	public var m_angleY;
	public var m_angleZ;
 
	public var r;
	public var g;
	public var b;
 
	public var _lastTime;
	public var _lastSecond;
 
	public var _increasing;
 
	method setSize( size )
	{
		m_size = size;
	}
 
	method getSize( )
	{
		return m_size;
	}
 
	method create( size, position )
	{
		super->Position = position;
		self->setSize( size );
 
		r = g = b = 0.0;
 
		_lastTime = _lastSecond = System.TimeGetTime( );
		_increasing	= @true;
 
		m_angleX = m_angleY = m_angleZ = 0.0;
	}
 
	method RandomColor( a, b, c )
	{
		System.Draw.glColor3f( a, b, c );
	}
 
	method draw( )
	{
		var thisTime = System.TimeGetTime( );
 
        // check frame time
 
        var frameTime = thisTime - _lastTime;
        if (thisTime - _lastSecond > 2000)
      	{
			r = RANDOM_FLOAT( 255, 0 ) / 255;
			g = RANDOM_FLOAT( 255, 0 ) / 255;
			b = RANDOM_FLOAT( 255, 0 ) / 255;
			_lastSecond = thisTime;
      	}	
 
		System.Draw.glPushMatrix( );
 
			System.Draw.glTranslatef( super->Position[0], super->Position[1], super->Position[2] );
			System.Draw.glRotatef( m_angleX, 1.0, 0.0, 0.0 );
			System.Draw.glRotatef( m_angleY, 0.0, 1.0, 0.0 );
			System.Draw.glRotatef( m_angleZ, 0.0, 0.0, 1.0 );
 
		m_angleX += 1.0;
		m_angleY += 10.0;
		m_angleZ += 5.0;
 
		System.Draw.glBegin( 0x0008 );
		System.Draw.glColor3f( r, 0.0, b );
		System.Draw.glVertex3f( -0.5, 0.5, 0.5 );
 
		System.Draw.glColor3f( r, 0.0, 0.0 );
		System.Draw.glVertex3f( -0.5, -0.5, 0.5 );
 
		System.Draw.glColor3f( r, g, b );
		System.Draw.glVertex3f( 0.5, 0.5, 0.5 );
 
		System.Draw.glColor3f( r, g, 0.0 );
		System.Draw.glVertex3f( 0.5, -0.5, 0.5 );
 
		System.Draw.glColor3f( 0.0, g, b );
		System.Draw.glVertex3f( 0.5, 0.5, -0.5 );
 
		System.Draw.glColor3f( 0.0, g, 0.0 );
		System.Draw.glVertex3f( 0.5, -0.5, -0.5 );
 
		System.Draw.glColor3f( 0.0, 0.0, b );
		System.Draw.glVertex3f( -0.5, 0.5, -0.5 );
 
		System.Draw.glColor3f( 0.0, 0.0, 0.0 );
		System.Draw.glVertex3f( -0.5, -0.5,  -0.5 );
 
		System.Draw.glColor3f( r, 0.0, b );
		System.Draw.glVertex3f( -0.5, 0.5, 0.5 );
 
		System.Draw.glColor3f( r, 0.0, 0.0 );
		System.Draw.glVertex3f( -0.5, -0.5, 0.5 );
 
		System.Draw.glEnd( );
 
		System.Draw.glBegin( 0x0007 );
		System.Draw.glColor3f( r, 0.0, b );
		System.Draw.glVertex3f( -0.5, 0.5, 0.5 );
 
		System.Draw.glColor3f( r, g, b );
		System.Draw.glVertex3f( 0.5, 0.5, 0.5 );
 
		System.Draw.glColor3f( 0.0, g, b );
		System.Draw.glVertex3f( 0.5, 0.5, -0.5 );
 
		System.Draw.glColor3f( 0.0, 0.0, b );
		System.Draw.glVertex3f( -0.5, 0.5, -0.5 );
		System.Draw.glEnd( );
 
		System.Draw.glBegin( 0x0007 );
		System.Draw.glColor3f( r, 0.0, 0.0 );
		System.Draw.glVertex3f( -0.5, -0.5, 0.5 );
 
		System.Draw.glColor3f( r, g, 0.0 );
		System.Draw.glVertex3f( 0.5, -0.5, 0.5 );
 
		System.Draw.glColor3f( 0.0, g, 0.0 );
		System.Draw.glVertex3f( 0.5, -0.5, -0.5 );
 
		System.Draw.glColor3f( 0.0, 0.0, 0.0 );
		System.Draw.glVertex3f( -0.5, -0.5,  -0.5 );
			System.Draw.glEnd( );
 
		System.Draw.glPopMatrix( );
	}
}
 
 
var objList = #[ ];
var statsMaker = new OStatsMaker;
 
function addObject( size, position )
{
	var newObj = new OCube;
	newObj->create( size, position );
 
	objList[ lengthof( objList ) ] = newObj;
}
 
function drawList( )
{
	var it;
	foreach( it in objList )
		it->draw( );
}
 
function initializeApplication( )
{
	addObject( 1, #[ 3.5, 3.5, -4.5 ] );
	addObject( 1, #[ 3.5, -3.5, -4.5 ] );
	addObject( 1, #[ -3.5, 3.5, -4.5 ] );
	addObject( 1, #[ -3.5, -3.5, -4.5 ] );
	addObject( 1, #[ 0, 0, -2 ] );
 
	statsMaker->resetStats( );
 
	System.Application.CreateApplication( "Test OOP", 1024, 768, @true );
}
 
function destroyApplication( )
{
	System.Application.DestroyApplication( );
}
 
var g_FrameInterval	= 0.0f;
 
function main( )
{
	initializeApplication( );
 
	var strFrameRate;
	var strBestAndBad;
 
	while( System.Draw.FrameBegin( ) )
	{
		System.Draw.glClearColor( 1.0, 0.71, 0.16, 0.0 );
		System.Draw.glClear( 0x00004000 | 0x00000100 );
 
		drawList( );
		statsMaker->updateStats( );
 
		strFrameRate = System.SPrintf( "FPS : %f\nTest", statsMaker->AverageFPS );
		strBestAndBad = System.SPrintf( "Worst FPS : %f | Best FPS : %f", statsMaker->WorstFPS, statsMaker->BestFPS );
 
		System.Draw.DrawString( #[ (1024/2-120), 700 ], "HHO Engine Is Performant !", #[ 1, 0.5, 1, 1.0 ] );
		System.Draw.DrawString( #[ (1024/2-120), 680 ], strFrameRate, #[ 1, 0.5, 1, 1.0 ] );
		System.Draw.DrawString( #[ (1024/2-120), 660 ], strBestAndBad, #[ 1, 0.5, 1, 1.0 ] );
		System.Draw.FrameEnd( );
		System.Sleep( 7 );
	}
 
	destroyApplication( );
 
	System.Exit( -1 );
	return 1;
}
 
main( );

14/04/2011, 13h08
Acrim

J'ai un lointain souvenir (assez moche :)) d'outils comme Lex et YACC qui permettent de générer des analyseurs lexicaux/syntaxiques à partir de la définition des "mots" et de la syntaxe. Tu pourrais regarder de ce cote éventuellement.
14/04/2011, 16h39
Artiphys

Je l'avais justement fait avec Yacc et Bison ce langage. enfin c'était pour le parsing ... après c'est compilé et executé dans une machine virtuelle!

Citation:

Envoyé par poringkiller

je ne précise pas de langage car toute idée d'implémentation de ce parser est la bienvenue, qu'elle soit en POO ou non

étape 1 : Se documenter sur les expressions EBNF
étape 2 : Utiliser un générateur (genre ANTLR, lex/yacc, ...)
Code:

1 2 3 4 5 6 7 8 9 10 say = SAY expr ('+' expr)* EOL expr = CHAINE | function | NUMBER function = FNAME '(' ')' | FNAME '(' expr (',' expr)* ')' SAY = 'say' NUMBER = [numeric] CHAINE = '"' [ascii]* '"' FNAME = [alphanum]+ EOL = ';'

15/04/2011, 22h01
Graffito
On peut aussi envisager de programmer l'application et les scripts dans un langage comme C# qui peut accepter la compilation dynamique d'un script.

C'est à dire que :
- l'application sera compilée en statique,
- elle pourra compiler en dynamique un script,
- elle lancera l'exécution de ce script (ou appelera des procédures du script).
Le script n'est évidemment pas connu au moment de la compilation "statique" de l'application.
18/04/2011, 15h29
poringkiller

merci beaucoup pour toutes ces pistes de recherche, je n'imaginais pas qu'il puisse exister des outils pour un besoin aussi spécifique, il me semble que cela correspond à mes besoins, et à ceux des gens qui passerons lire ce post.
je marque résolu n.n
19/04/2011, 14h45
gladek

pourquoi ne poas utiliser le xml ???
02/05/2011, 11h00
poringkiller

Citation:

Envoyé par gladek

pourquoi ne poas utiliser le xml ???

car je doute que les développeurs qui utiliserons ce langage apprécient de coder si chaque instruction est encadrée par des "<>" simple question d'ergonomie, mais oui, techniquement, ça répondrait très bien à mes besoins. je n'y avait pas pensé, j'irais aussi chercher dans la direction d'un algo qui conçoit le code sous forme de noeuds, ce pourrait être assez intéressant :)