TourDeJeu, le portail des jeux en ligne alternatifs, les articles 
TourDeJeu, le réseau des jeux en ligne alternatifs : jeux web multijoueurs, jeux par forum. En savoir +
En ligne : 491 jeux, 7152 news, 26671 commentaires
 

Recherche de jeu par critères - Un jeu au hasard !

Les Focus

Tech. : Le programmeur écologique
Tech. : automatisation et mails
Salon MondeDuJeu 2002
Revue de presse des JpC
Humour : 1001 raisons pour jouer
Ludique : le joueur parfait
Ludique : découverte du JpC
PHP : accès base de données
PHP : structure du site
Ludique : JpC et Temps réel
Jeux de rôles sans règles
Humour : astrologie du JpC
Tech. : Bases de données
MJ : les joueurs multiples
PHP : utilité pour un JpC
PHP : c'est quoi ?
Tech. : l'analyse des ordres
Ludique : débutants et vétérans
Tech. : archi Ultraball 2100
Ludique : les jeux de pronos
Tech. : le site Web d'un JpC
Humour : football et wargame
Présentation de TourDeJeu

Tech : Analyse syntaxique des ordres

par Touriste

Quiconque a écrit «à la main» un programme d'analyse des ordres envoyés par les joueurs sait le calvaire que c'est. Il faut découper les lignes pour voir si le mot 'Construire' est bien suivi par le mot 'ferme' ou par le mot 'abri', si le premier mot de la ligne est 'Fabriquer' il doit être suivi par un chiffre, lui-même suivi par 'fromage' ou 'plaquette de beurre'. Et ainsi de suite pour les différents ordres possibles. L'horreur à écrire, je vous dis !

«Un bon programmeur est un fainéant»

Pourquoi vouloir réinventer la roue ? Il existe des techniques (et donc des programmes) pour analyser facilement les ordres des joueurs.

La première étape de l'analyse d'une ligne d'ordre est le découpage en mots (aussi nommés unités lexicales, ou lexèmes).

La seconde étape consiste à vérifier que les mots se suivent dans le bon ordre.

Voilà, c'est aussi simple que ça. Maintenant que vous avez tout compris, à vos claviers !

Quoi, comment, vous voulez en savoir plus, l'explication précédente ne vous suffit pas. Bon d'accord, je vais expliquer plus en détail.

«Séparons le bon grain de l'ivraie»

Voyons les ordres présentés plus haut (tirés du jeu «le roi du fromage»)

  Construire ferme
  Construire abri
  Fabriquer N fromage
  Fabriquer N plaquette de beurre

avec N qui représente un nombre entier positif.

Les ordres envoyés par les joueurs doivent contenir seulement les 7 unités lexicales (i.e. 7 mots) suivantes :

  Construire
  ferme
  abri
  Fabriquer
  N (un nombre)
  fromage
  plaquette de beurre

Les mots 'plaquette de beurre' constituent une seule unité lexicale car dans ce jeu, une 'plaquette' est toujours une 'plaquette de beurre'. Tout autre mot présent dans les ordres est invalide, il s'agit d'une erreur.

Le découpage est donc simplifié puisque les ordres sont formés uniquement de ces 7 lexèmes. Les programmes qui effectuent automatiquement ce découpage à partir de la liste des unités lexicales sont appelés «analyseur lexicaux». Le plus connu d'entre eux est sans doute le programme 'lex' et son successeur 'flex'. Vous trouverez ce dernier sur le site du projet GNU à l'url suivante http://www.gnu.org/software/flex/flex.html

Ci dessous, la description pour flex des 7 unités lexicales présentées, à utiliser comme suit :

  flex fromage1.l
  gcc -o fromage1 lex.yy.c -ll

le programme obtenu a pour nom 'fromage1'

- fichier fromage1.flex -


/* ne pas diferencier minuscule et majuscule */
%option case-insensitive

%%
"construire"		{printf ("CONSTRUIRE");}
"ferme"			{printf ("FERME");}
"abri"			{printf ("ABRI");}
"fabriquer"		{printf ("FABRIQUER");}
"fromage"		{printf ("FROMAGE");}
"plaquette de beurre"	{printf ("BEURRE");}
[0-9]+			{printf ("NOMBRE");}
[ \t\n]+	 /* ignorer les espaces */
. printf( "caractère invalide: %s\n", yytext );
%%

int main () {
  yyin = stdin;
  yylex ();
}

«Du bon sens et de l'ordre»

Maintenant que l'on sait découper les ordres en unités lexicales, il faut vérifier leur agencement. Ainsi, la ligne 'Fabriquer ferme' n'est pas un ordre, bien que construite avec des unités lexicales valides.

Ici encore, il existe des méthode qui font le travail pour vous à partir de la liste des ordres possibles -- i.e. la liste des suites de lexemes valides (nommé grammaire). Les programmes mettant en oeuvres ces méthodes sont nommés «analyseur syntaxique».

Pour notre exemple, nous donnons à l'analyseur syntaxique la liste suivante :

  Ordre = <construire> <ferme>
       ou <construire> <abri>
       ou <fabriquer> <nombre> <fromage>
       ou <fabriquer> <nombre> <beurre>

Les mots écrits entre '<' et '>' sont les lexèmes.

Ces outils permettent de décrire des "groupes" d'ordres, par exemple :

  Ordre = Construction
       ou Fabrication

  Construction = <construire> <ferme>
	      ou <construire> <abri>

  Fabrication = <fabriquer> <nombre> <fromage>
	     ou <fabriquer> <nombre> <beurre>

où l'on précise qu'un ordre est soit une construction, soit une fabrication.

L'analyseur syntaxique le plus connu est probablement 'yacc' et son successeur 'bison' qui s'interfacent avec 'lex' et 'flex'. Vous trouverez aussi bison sur le site du projet GNU à l'url suivante : http://www.gnu.org/software/bison/bison.html

Ci dessous, la description pour bison (et le fichier flex associé) de notre grammaire exemple. Les commande à utiliser sont :

  bison -d fromage2.y
  flex fromage2.l
  gcc -o fromage2 fromage2.tab.c lex.yy.c -ll

le programme obtenu a pour nom 'fromage2'

- fichier fromage2.y -

/* la liste des lexemes */
%token CONSTRUIRE FERME ABRI FABRIQUER FROMAGE 
       BEURRE NOMBRE

/* le symbole '|' reprente le 'ou'
 * le ';' la fin d'une regle
 */
%%
/* une liste d'ordre est compose par un ordre 
 * suivi d'une liste d'ordre 
 */
liste_ordres : ordre liste_ordres
	     | /* rien */
	     ;

/* un ordre est soit une construction, 
 * soit une fabrication 
 */
ordre : construction
      | fabrication
      ;

/* on construit soit une ferme soit un abri */
construction : CONSTRUIRE FERME 	
   {printf ("construction d'une ferme\n");}
	     | CONSTRUIRE ABRI		
	{printf ("construction d'un abri\n");}
	     ;

/* on fait soit du fromage, soit du beurre */
fabrication : FABRIQUER NOMBRE FROMAGE	
   {printf ("fabrication de %d fromage\n", $2);}
	    | FABRIQUER NOMBRE BEURRE	
	{printf("fabrication de %d plaquette 
	              de beurre\n", $2);}
	    ;
%%

int main () {
  yyparse ();
}

int yyerror () {
  fprintf (stderr, "Erreur\n");
  exit (1);
}

- fichier fromage2.l -

%{
#include "fromage2.tab.h"
%}
/* ne pas diferencier minuscule et majuscule */
%option case-insensitive

%%
"construire"		return CONSTRUIRE;
"ferme"			return FERME;
"abri"			return ABRI;
"fabriquer"		return FABRIQUER;
"fromage"		return FROMAGE;
"plaquette de beurre"	return BEURRE;
[0-9]+	     { yylval = atoi (yytext);
			  return NOMBRE;
			}
[ \t\n]+	  /* ignorer les espaces */
. printf( "caractère invalide: %s\n", yytext );
%%

Les analyseurs lexicaux et syntaxiques sont fortement liés, c'est pourquoi deux taches sont parfois effectuées par un seul programme, par exemple JavaCC ou bien ANTLR.

Vous l'aurez constaté, les programmes Flex et Bison que j'ai utilisés pour illustrer mon propos génèrent du code C. Pour produire un programme en Java il vous faut utiliser JavaCC ou ANTLR. Il existe probablement d'autres programmes qui génèrent de l'ADA, du C++, ... je vous laisse les chercher.

Les techniques que je vous ai présentées sont issues de la recherche sur les langages de programmation. Ces techniques sont basées sur des théories spécifiques à ce type de langage. Si vous rencontrez des problèmes pour analyser vos ordres à l'aide de ces techniques, c'est probablement que la description de vos ordres (la grammaire) doit être légèrement modifiée. Pour plus d'information sur le sujet, vous pouvez consulter tout ouvrage traitant de "l'analyse syntaxique" ("parsing" en anglais). Il existe de nombreux cours disponibles en ligne (recherchez "cours analyse syntaxique" dans votre moteur de rechercher préféré), ainsi que des livres disponibles au télé-chargement ( exemple).

Précédent - Suivant



Commentaires laissés par les visiteurs

  • melicine, le 21-10-2007
    Besoin d'aide
    Bonjour je suis melicine et je voudrais creer un jeu de simulation genre sim-plage. Mais le probleme c'est que je ne sais pas comment faire !!!Qui pourrais m'aider ? Contactez moi sur l'adresse mail suivante: the-one-createur@hotmail.fr Merci beaucoup d'avance
  • Hugodelire, le 20-02-2007
    Euhh ..........
    Comment trouver un site qui ns heberge ? Faut il payer ?
  • (c) TourDeJeu 2000-2020