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];
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.
%{
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");
}
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 errorverlaine%