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

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

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

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

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>

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

- 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