Automate associé
à une expression rationnelle

Dépendances

CC = gcc
LEX = flex
YACC = bison
LDLIBS = -ly -ll

automate: automate.c autolex.c
	$(CC) -o $@ $@.c $(LDLIBS)

automate.c: automate.y
	$(YACC) -o $@ $<

autolex.c: autolex.l

%%
[a-z]	{yylval = feuille (yytext [0]); return ID; }
[ \t]+	;
.|\n	return yytext [0];

Analyseur syntaxique

• Représentation des ensembles : les attributs premier et dernier sont des ensembles ; on choisit de les représenter sur le modèle des chaînes de caractères, c'est à dire comme des tableaux terminés par une sentinelle (ici -1). Ces tableaux sont alloués à l'intérieur d'un tableau statique de grande taille, nommé ensemble (en utilisant la variable elibre pour cette allocation), et repérés par l'indice de leur base. Les variables premier et dernier sont ainsi de simples entiers.

• Représentation de l'automate : comme l'automate est non déterministe, on le représente comme un tableau statique de grande taille, nommé graphe, constitué d'arcs, définis par leur source et leur but. La variable glibre indique l'indice du premier arc libre.

  L'étiquette d'un arc ne dépend que de son but : un sommet correspond à une occurrence (numérotée) d'une lettre dans l'expression rationnelle. Le tableau lettre établit la correspondance entre les (numéros des) sommets et les étiquettes.

• Union de deux ensembles : la fonction fusion devrait, en principe, veiller à l'élimination des doublons ; mais elle est en fait toujours utilisée pour réaliser l'union de deux ensembles disjoints (frontières de deux sous-arbres frères).

• Etat initial : on ajoute un état initial, numéroté 0, et des transitions de 0 vers les états qui appartiennent à l'attribut premier de l'expression.

• Etats terminaux : ce sont les états qui appartiennent à l'attribut dernier de l'expression.

• Bug : la fonction transition peut ajouter des transitions déjà enregistrées, qui apparaissent donc plusieurs fois.

• Opérateurs *, +, ? : dans le fichier yacc, on utilise le fait que l'attribut du premier symbole dans la partie droite de la règle, devient par défaut, après réduction, l'attribut du symbole de la partie gauche de la règle.

%{
typedef struct {
  int vide, premier, dernier;
} attribut;

#define YYSTYPE attribut

attribut feuille (char id);
attribut noeud (char operateur, attribut gauche, attribut droite);
void init ();
void afficher (attribut a);
void transition (int source, int but);

%}

%token ID

%%
axiome	: axiome expr '\n'	{afficher ($2); init ();}
	| axiome '\n'
	| /* vide */
	;
	
expr	: expr '|' terme	{$$ = noeud ('|', $1, $3); }
	| terme
	;
	
terme	: terme facteur		{$$ = noeud ('.', $1, $2);
				 transition ($1.dernier, $2.premier); }
	| facteur
	;
	
facteur	: facteur '*'		{$$.vide = 1;
				 transition ($1.dernier, $1.premier); }
	| facteur '+'		{transition ($1.dernier, $1.premier); }
	| facteur '?'		{$$.vide = 1; }
	| '(' expr ')'		{$$ = $2; }
	| ID
	;
%%

#include "autolex.c"

#define EMAX 1024
#define GMAX 1024
#define PMAX 64

typedef struct {
  int source, but;
} arc;

static int
  elibre = 0,
  glibre = 0,
  position = 1,
  ensemble [EMAX];

static char lettre [PMAX];
static arc graphe [GMAX];

void debordement (char *s) {
  printf ("Débordement de la table '%s'\n", s);
  exit (1);
}

void init () {
  elibre = glibre = 0;
  position = 1;
}

/* Ne pas appeler une fonction "union": mot réservé en C */

int fusion (int a, int b) {
  int i, debut = elibre;
  
  for (i = a; ensemble [i] >= 0; i++) elibre++;
  for (i = b; ensemble [i] >= 0; i++) elibre++;
  if (elibre >= EMAX)
    debordement ("ensemble");
  
  elibre = debut;
  for (i = a; ensemble [i] >= 0; i++)
    ensemble [elibre++] = ensemble [i];
  for (i = b; ensemble [i] >= 0; i++)
    ensemble [elibre++] = ensemble [i];
  ensemble [elibre++] = -1;
  return debut;
}

void afficher (attribut a) {
  int i, p, q;
  
  printf ("Premier :");
  for (i = a.premier; ensemble [i] >= 0; i++)
    printf ("%3d", ensemble [i]);
  printf ("\n");

  printf ("Dernier :");
  for (i = a.dernier; ensemble [i] >= 0; i++)
    printf ("%3d", ensemble [i]);
  printf ("\n\n");
  
  /* Création de l'état initial */
  
  if (elibre + 2 > EMAX)
    debordement ("ensemble");
  
  ensemble [elibre++] = 0;
  ensemble [elibre++] = -1;
  transition (elibre - 2, a.premier);

  /* Affichage de l'automate */
  
  for (i = 0; i < glibre; i++) {
    p = graphe [i].source;
    q = graphe [i].but;
    printf ("%3d -> %3d (%c)\n", p, q, lettre [q]);
  }
  printf ("\n");
}

attribut feuille (char id) {
  attribut a;
  
  if (elibre + 4 > EMAX)
    debordement ("ensemble");
  
  a.vide = 0;
  a.premier = elibre;
  ensemble [elibre++] = position;
  ensemble [elibre++] = -1;
  a.dernier = elibre;
  ensemble [elibre++] = position;
  ensemble [elibre++] = -1;
  lettre [position] = id;
  
  position++;
  return a;
}

attribut noeud (char operateur, attribut gauche, attribut droite) {
  attribut a;
  
  switch (operateur) {
    case '|':
      a.vide = gauche.vide || droite.vide;
      a.premier = fusion (gauche.premier, droite.premier);
      a.dernier = fusion (gauche.dernier, droite.dernier);
      break;
      
    case '.':
      a.vide = gauche.vide && droite.vide;
      if (gauche.vide)
        a.premier = fusion (gauche.premier, droite.premier);
      else
        a.premier = gauche.premier;
      if (droite.vide)
        a.dernier = fusion (gauche.dernier, droite.dernier);
      else
        a.dernier = droite.dernier;
      break;
  }
  return a;
}

void transition (int source, int but) {
  int i, j, p, q;
  for (i = source; (p = ensemble [i]) >= 0; i++)
    for (j = but; (q = ensemble [j]) >= 0; j++)
      if (glibre < GMAX) {
        graphe [glibre].source = p;
        graphe [glibre].but = q;
        glibre++;
      }
      else
        debordement ("graphe");
}

Jeu d'essais

verlaine% automate
a
Premier :  1
Dernier :  1

  0 ->   1 (a)

a*b
Premier :  1  2
Dernier :  2

  1 ->   1 (a)
  1 ->   2 (b)
  0 ->   1 (a)
  0 ->   2 (b)

a+b
Premier :  1
Dernier :  2

  1 ->   1 (a)
  1 ->   2 (b)
  0 ->   1 (a)

a?b
Premier :  1  2
Dernier :  2

  1 ->   2 (b)
  0 ->   1 (a)
  0 ->   2 (b)

(b|a*x)*a+b
Premier :  1  2  3  4
Dernier :  5

  2 ->   2 (a)
  2 ->   3 (x)
  1 ->   1 (b)
  1 ->   2 (a)
  1 ->   3 (x)
  3 ->   1 (b)
  3 ->   2 (a)
  3 ->   3 (x)
  4 ->   4 (a)
  1 ->   4 (a)
  3 ->   4 (a)
  4 ->   5 (b)
  0 ->   1 (b)
  0 ->   2 (a)
  0 ->   3 (x)
  0 ->   4 (a)

*a
parse error