Travaux Dirigés et Pratiques d'interprétation et ompilation GLIN604Mi hel Meynard23 janvier 20121 Analyse lexi aleExer i e 1 � Dessiner un AFD distin t pour ha un des langages suivants :1. Langage de mots- lés : Lkey = {if, then, else, throw}.2. Langage des littéraux numériques entiers du C (ou C++, ou Java), dé imaux Lc10, o taux Lc8, hexadé imauxLc16.3. Langage Lid des identi� ateurs omposés d'une lettre au moins, éventuellement suivie de hi�res, de lettreset de �_�.4. Langage des littéraux numériques �ottants dé imaux Lf ; la suite de hi�res à gau he ou à droite du pointdé imal pouvant être vide ; l'exposant entier n'est pas obligatoire. Exemples : 13., 1.7e23, .89E-345. Langage Lsep des séparateurs omposés de blan s (Espa e, \t, \n), des ommentaires à la C et à la C++.� Dessiner un unique AFD à jeton re onnaissant une partie de es langages. Vous re onnaitrez notamment : lemot- lé if, les identi� ateurs, les entiers dé imaux, les �ottants sans exposant, les séparateurs. Utiliser des jetonsnégatifs pour les lexèmes à �ltrer (séparateurs).� E rire dans le � hier afd.h la fon tion reerAfd() orrespondant à et Afd à jeton �ltrant.� Implémenter l'analyseur lexi al en C. Le main() appellera itérativement analex() et a� hera une haîne orres-pondant à l'entier retourné ainsi que le lexème, e i jusqu'à la �n du � hier.Exer i e 2 E rire les expressions régulières orrespondant aux langages réguliers suivants : Lkey , Lc10, Lc8, Lc16, Lid, Lf , Lsep.Exer i e 3 E rire un analyseur lexi al re onnaissant l'ensemble des expressions régulières des exer i es pré édents àl'aide de �ex. L'a tion asso iée à haque lexème re onnu onsiste à retourner le jeton orrespondant au lexème. Touteautre expression d'un ara tère retournera un jeton orrespondant au ode ISO Latin-1 de e ara tère.Exer i e 4 E rire un sour e lex delblan s.l+ �ltrant un � hier en :� supprimant les lignes blan hes (lignes vides ou remplies de blan s (espa e et tabul.)),� suprimant les débuts et �ns de ligne blan s,� remplaçant tous les blan s \t<espa e> multiples par un seul espa e,� remplaçant les tabulations \t par un espa e.Exer i e 5 E rire en �ex, un programme omptant le nombre de lignes, le nombre de mots et le nombre de ara tèresd'un � hier passé en argument (man w ). Un mot est une suite de ara tères séparés par des blan s (tab, espa e, retourligne). Véri�ez que vos résultats sont les mêmes que eux de w .Exer i e 6 Soit l'expression régulière e suivante : e = a((b|c)∗∗|cd)∗b1. Dessiner un automate �ni équivalent à e.2. Cet automate est-il déterministe ? Si oui indiquez pour quelles raisons, sinon déterminisez-le.3. Minimisez et AFD.Exer i e 7 Soit l'automate �ni B = ({a, b, c}, {1, 2, 3, 4}, {1}, {2, 4}, {1a2, 1a3, 2b2, 2c2, 3b4, 4c3, 4b4}).1. Dessiner un automate �ni déterministe équivalent à B.2. Minimisez et AFD.2 Analyse des endante ré ursiveExer i e 8 Soit la grammaire non ré ursive à gau he vue en oursGENR = ({0, 1, . . . , 9,+, ∗, (, )}, {E,R, T, S, F}, X,E)ave les règles de X suivantes :

E → TR

R → +TR|ε

T → FS

S → ∗FS|ε

F → (E)|0|1| . . . |91

Soit le programme C véri�ant un mot du langage L(GENR) :/*============================================================================Nom : analdes . Auteur : Mi hel MeynardMaj : 25/3/02 Creation : 8/1/98Projet : Analyse des endante ré ursive d'expression arithmétique------------------------------------------------------------------------------Spe ifi ation:Ce fi hier ontient un re onnaisseur d'expressions arithmétiques omposée delittéraux entiers sur un ar, des opérateurs +, * et du parenthésage ().Remarque : soit rediriger en entrée un fi hier, soit terminer par deux ara tères EOF (Ctrl-D), un pour lan er la le ture, l'autre omme "vrai" EOF.============================================================================*/#in lude <stdio.h> /* les ma ros sont des blo s : pas de ';' apres */#define AVANCER {jeton=get har();num ar++;}#define TEST_AVANCE(prevu) {if (jeton==(prevu)) AVANCER else ERREUR_SYNTAXE}#define ERREUR_SYNTAXE {printf("\nMot non re onnu : erreur de syntaxe \au ara tère numéro %d, de jeton %d \n",num ar,jeton); exit(1);}void E();void R();void T();void S();void F(); /* dé larations des fon tions */int jeton; /* ara tère ourant du flot d'entrée */int num ar=0; /* numero du ara tère ourant (jeton) */void E(){T(); /* regle : E->TR */R();}void R(){if (jeton=='+') { /* regle : R->+TR */AVANCERT();R();}else ; /* regle : R->epsilon */}void T(){F();S(); /* regle : T->FS */}void S(){if (jeton=='*') { /* regle : S->*FS */AVANCERF();S();}else ; /* regle : S->epsilon */}void F(){if (jeton=='(') { /* regle : F->(E) */AVANCERE();TEST_AVANCE(')')}elseif (isdigit(jeton)) /* regle : F->0|1|...|9 */AVANCERelse ERREUR_SYNTAXE} 2

main(){ /* Fon tion prin ipale */AVANCER /* initialiser jeton sur le premier ar */E(); /* axiome */if (jeton==EOF) /* expression re onnue et rien après */printf("\nMot re onnu\n");else ERREUR_SYNTAXE /* expression re onnue mais il reste des ar */} 1. Sur le modèle du véri� ateur, é rire un programme évaluant la valeur d'une expression arithmétique. Par exemple,evaldes sur la haîne 1+2+(2+1)*3 retournera 12. Attention, on pré isera pour haque opérateur le typed'asso iativité, gau he ou droite, employée dans le programme.2. Sur le modèle du véri� ateur, é rire un programme traduisant une expression arithmétique en sa forme post�xée(polonaise inversée). Par exemple, postdes sur la haîne 1+2+(2+1)*3 retournera 12+21+3*+. On utiliseral'asso iativité à gau he pour l'addition et la multipli ation.3. Sur le modèle du véri� ateur, et en utilisant le type abstrait Arbin implémenté en C, é rire un analyseursyntaxique produisant et a� hant l'arbre abstrait orrespondant à une expression. On utilisera l'asso iativité àgau he pour l'addition et la multipli ation. Par exemple, arbindes sur la haîne 1+2+(2+1)*3 a� hera :++12*+213Voi i le � hier d'en-tête arbin.h :/*=============================================================================Nom: arbin.h auteur: Meynard Mi helMaj: 5/4/1995 Creation: 5/4/95Projet:-------------------------------------------------------------------------------Spe ifi ation:Ce fi hier ontient les de larations de stru tures, de types, de variables defon tions sur les arbres binaires d'entiers.-------------------------------------------------------------------------------utilise par :=============================================================================*/#ifndef _ARBINH#define _ARBINH#ifndef NULL#define NULL 0#endif /* NULL *//*----------------------- Types Unions Stru tures ---------------------------*/typedef stru t Noeudbin * Arbin;/* pointeur sur la ra ine de l'arbre binaire d'entiers */typedef stru t Noeudbin {int val ;Arbin fg;Arbin fd ;} Noeudbin ; /* noeud d'un arbre binaire d'entiers *//*---------------------------FONCTIONS----------------------------------------*/#define reerarbin() (NULL) /* ree un arbin vide (retourne pointeur nul) */3

#define sag(a) ((a)->fg) /* retourne le sous-arbre gau he de a */#define sad(a) ((a)->fd) /* retourne le sous-arbre droit de a */#define videa(a) (a==NULL) /* teste si arbin vide */#define ra ine(a) ((a)->val) /* ra ine d'un arbin *//* remarque : es 5 pseudo-fon tions (ma ros) sont definies quelque soit le type de l'arbin (entier, ar, arbre,...) */void greffergau he(Arbin pere, Arbin filsg);/* rempla e le sag(pere) par filsg et vide l'an ien sag *//* operation MODIFIANTE : ATTENTION aux effets de bord */void grefferdroite(Arbin pere, Arbin filsd);/* rempla e le sad(pere) par filsd et vide l'an ien sad *//* operation MODIFIANTE : ATTENTION aux effets de bord */Arbin onstruire(int ra , Arbin g, Arbin d); /* onstruit un nouvel arbin */Arbin opiera(Arbin a); /* opie a */void videra(Arbin * pa); /* vide *pa (NULL) et ses sous-arbres *//* operation MODIFIANTE : ATTENTION aux effets de bord */void affi hera(Arbin a,int indent); /* affi he a de manière indentée */#endif /* _ARBINH */Exer i e 9 E rire un programme évaluant la valeur d'une expression arithmétique omposée de nombres �ottants nonsignés et des opérateurs (), ^, *, /, +, -. Attention à respe ter les asso iativités des opérateurs ! Vous utiliserez�ex pour la partie analyse lexi ale. Par exemple, al des sur la haîne 5.12-2.56-2^2^3/100 retournera 0.Exer i e 10 On désire é rire un tradu teur d'expression régulière en automate d'état �ni non déterministe parl'algorithme de Thompson. Une expression régulière de base est onstituée d'une lettre minus ule omprise entre a etz (symboles terminaux), du symbole '�' pour représenter epsilon ε, du symbole '0' pour représenter le langage vide ∅.Une expression régulière (er) est de base ou est obtenue par on aténation (impli ite) de deux er, par union de deuxer (symbole |), par l'opération * appliquée à une er. Le parenthésage est permis pour modi�er l'ordre de priorité desopérateurs qui est du plus petit au plus grand : |, on aténation, *, ().1. E rire une grammaire �naturelle� engendrant des expressions régulières et prouver son ambiguïté.2. E rire une grammaire ré ursive à gau he et non ambiguë des expressions régulières (S, E, T, F).3. E rire une grammaire non ré ursive à gau he et non ambiguë des expressions régulières : déré ursivez la gram-maire pré édente (S, X, E, R, T, Y, F).4. E rire un analyseur ré ursif des endant onstruisant l'arbre abstrait orrespondant à une expression régulière.5. Optimiser l'arbre abstrait onstruit en tenant ompte des règles suivantes, e étant une er quel onque :� e**=e*,� �*=�=0*,� �e=e�=e, 0e=e0=0,� 0|e=e|0=e.6. Fabriquer la table d'analyse de l'automate à pile en analyse des endante.7. Dessiner les états su essifs de la pile lors de la re onnaissan e de l'expression ab ∗ |c.8. E rire une fon tion NombreEtat(Arbin a) al ulant le nombre d'état de l'automate �ni non déterministe obtenupar l'algorithme de thompson.9. Programmer l'algorithme de Thompson en implémentant l'automate non déterministe par un tableau dynamiqued'entiers de NombreEtat(a) lignes et 3 olonnes. Chaque ligne orrespond à un état. La première olonne de e4

tableau ontient le symbole (�a-z) de la ou les transitions sortantes. Les deux autres olonnes ontiennent le oules états destinations de la ou des deux transitions possibles.3 Analyse as endante LRExer i e 11 On reprend l'exer i e 10 en analyse as endante.1. En utilisant la grammaire ré ursive à gau he non ambiguë, é rire un sour e bison qui produise et a� he l'arbreabstrait asso ié à une expression régulière (sans utiliser �ex).2. En utilisant la grammaire �naturelle� et les règles de pré éden es pour les opérateurs, é rire un sour e bisontraduisant une expression régulière en un automate d'état �ni par l'algorithme de Thompson. Attention, à la on aténation qui est impli ite !Exer i e 12 En reprenant l'ar hite ture de la al ulette ( al .l et al .y) vue en ours, é rire une al ulette logiqued'ordre 0. Une expression logique de base est onstituée des onstantes 0 ou false ou faux ou 1 ou true ou vrai. Uneexpression logique est de base ou est obtenue par onjon tion (&), disjon tion (|), impli ation (->), équivalen e (==),ou ex lusif (^) de deux expressions logiques, ou en ore par négation ( !) d'une expression logique. Le parenthésage estpermis pour modi�er l'ordre de priorité des opérateurs qui est du plus petit au plus grand : {|,− >,==,^}, &, !, ().Les expressions logiques sont évaluées de gau he à droite.1. E rire logi .l, logi .y pour évaluer une expression logique d'ordre 0.2. Ajouter à ette al ulette la fon tionalité suivante : 26 variables logiques, nommées a-z, permettent de onserverle résultat de al uls pré édents. L'a�e tation de es variables et leur utilisation ressemblera à la syntaxe C. Parexemple, a = 0|1− > 0 puis b = a− > (0|1). Les variables seront implantées dans un tableau global de 26 entiers,réalisant une table des symboles rudimentaire.Exer i e 13 Soit la grammaire GETF = ({0, 1, . . . , 9,+, ∗, (, )}, {E, T, F}, R,E) ave les règles de R suivantes :E → E + T |T

T → T ∗ F |F

F → (E)|0|1| . . . |91. Cal uler la olle tion anonique (AFD) des ensemble d'items LR(0) de la grammaire augmentée asso iée à GETF .2. Construire les tables d'analyse A tion et Su esseur après avoir al ulé les TabSuivants des non terminaux.3. Analyser l'expression (5+3)*2$.4 Analyse et ompilation d'un langage PasadaL'obje tif à réaliser est un ompilateur traduisant des programmes é rits en pasada (Pas al-Ada), dans le langageC. Le ompilateur sera lui-même é rit en C++. Il est don de la forme : pasadaC++C.4.1 Des ription du langage pasada4.1.1 Cara téristiques� Pas de ompilation séparée. Un programme pasada est entièrement lo alisé dans un � hier d'extension .pa.� C'est un langage très fortement typé. Toutes les onversions de types doivent être expli ites. Il existe 4 types : int,bool, string, �oat.� Un programme pasada utilise un ertain nombre de pro édures. Chaque pro édure dé lare un ertain nombre devariables lo ales, puis dé�nit les instru tions qui la réalisent. Chaque pro édure possède un ertain nombre deparamètres typés qui peuvent être soit d'entrée (in : lisibles mais non modi�ables), soit de sortie (out : résultats),soit d'entrée/sortie (inout : lisibles et modi�ables).� Le point d'entrée du programme, dé lare un ertain nombre de variables globales, puis dé�nit les instru tions.� Les entrées/sorties sont très basiques : le ture au lavier et é riture à l'é ran d'une variable typée.� Il n'y a pas de problèmes de référen es en avant : on peut utiliser une pro édure avant qu'elle n'apparaisse dansle � hier.� Il n'y a pas de sur harge de pro édures : haque pro édure a un nom di�érent. Il n'y a pas de on�it de noms devariables : dans une pro , s'il y a on�it sur le nom lo al/global, 'est la variable lo ale qui est prioritaire.� Les stru tures de ontr�le sont : if then else, if then, while begin end, repeat until.� Les opérateurs sont à la pas al : égal (=), di�érent (<>), et (and) évaluation omplète, non (not), a�e tation( :=), . . . 5

4.1.2 Exemple/* les ommentaires à la C et à la C++ sont possibles */pro edure fa t(in int n, out int r) // fa torielle : 2 paramètresint j; // variable lo ale à fa t()begin // début du orps de pro édureif n=0 // pas de parenthèse autour d'une onditionthen r:=1; // affe tation du résultatelsebegin // blo d'instru tionsfa t(n-1,j); // appel ré ursif à fa tr:=n*j; // affe tation du résultatend // fin de blo return; // retour à l'appelantend // fin de pro édureprogram // point d'entrée du programmeint i,j; // variable globalebegin // blo d'instru tions du programmewriteString("Veuillez entrer un entier SVP : "); // affi hagereadInt(i); // pro prédéfinie : readInt(out int i)writeString("Voi i le résultat de fa torielle() : ");fa t(i,j); // al ulwriteInt(j); // pro prédéfinie : writeInt(in int i)end4.2 Développement du ompilateurLe ompilateur pa (pasada ompiler), sera développé en lex, ya , C++.Exer i e 14 E rire la grammaire du langage pasada. N'oubliez pas les pro édures prédé�nies telles que les onversions,la taille d'une haîne, les entrées/sorties, . . .Exer i e 15 E rire un analyseur lex/ya qui réalise uniquement la véri� ation syntaxique sans génération de ode.Exer i e 16 E rire un ompilateur en utilisant les stru tures de données adéquates : arbres abstraits, table dessymboles, . . .Exer i e 17 Améliorer le langage pasada en ajoutant la notion de tableau statique. Un tableau est toujours dé laréave sa taille : int tab[10℄;. Les tableaux sont indi és de 1 à n. Dans une pro édure, un paramètre tableau estdé laré sans sa taille : inout int tableau[℄;. Dans e as, l'opérateur prédé�ni |tableau| renvoie la taille (int) dutableau.Exer i e 18 Améliorer le langage pasada en ajoutant la notion de stru ture C.

6

5 Solutions des exer i esSolution 1 � unique AFD à jeton :\t," ",\n

EINITi

EIf

EIF EID

0−9

JIDENTIFJIFa−zA−Z0−9_

a−zA−Z0−9_

a−zA−Z0−9_EENT

.

0−9 0−9

EP

0−9

.

/

ES ESS/ \n

all−{\n}

EFLOAT

ECOM+

ESE ESEE

*

*

*/

ECOM

JCOM

JCOM+

all−{/,*}

all−{*}

JFLOAT

JIDENTIF

JENT

ESEP

JSEP

a−zA−Z−{i}\t," ",\n

Figure 1 � AFD� afd.h/*============================================================================Nom : afd.h Auteur : Mi hel Meynard | Définition d'un AFD============================================================================*/#define EINIT 0#define EI 1#define EIF 2#define EID 3#define ES 4#define ESS 5#define ECOMP 6#define ESE 7#define ESEE 8#define ECOM 9#define ESEP 10#define EENT 11#define EP 12#define EFLOAT 13#define NBETAT 14int TRANS[NBETAT℄[256℄; /* table de transition */int JETON[NBETAT℄; /* tableau des jetons *//** transitions de ed en ef pour tous les har de d à f */void lasse(int ed, int d, int f, int ef){int i; 7

for(i= d;i<= f;i++)TRANS[ed℄[i℄=ef;}void reerAfd(){ /* Constru tion de l'AFD */int i,j;for (i=0;i<NBETAT;i++){ /* init */for(j=0;j<256;j++) TRANS[i℄[j℄=-1; /* pas de trans */JETON[i℄=0; /* init tous états non finaux */} lasse(EINIT,'0', '9', EENT); /* entiers et flottants */ lasse(EENT,'0', '9', EENT);TRANS[EENT℄['.'℄=EFLOAT;TRANS[EINIT℄['.'℄=EP; lasse(EP,'0', '9', EFLOAT); lasse(EFLOAT,'0', '9', EFLOAT);JETON[EENT℄=300+EENT;JETON[EFLOAT℄=300+EFLOAT; /* jetons à retourner */ lasse(EINIT,'a', 'z', EID); /* IF et ID */ lasse(EINIT,'A', 'Z', EID);TRANS[EINIT℄['i'℄=EI; /* sur harge */ lasse(EI,'a', 'z', EID); lasse(EI,'A', 'Z', EID); lasse(EI,'0', '9', EID);TRANS[EI℄['_'℄=EID;TRANS[EI℄['f'℄=EIF; /* sur harge */ lasse(EIF,'a', 'z', EID); lasse(EIF,'A', 'Z', EID); lasse(EIF,'0', '9', EID);TRANS[EIF℄['_'℄=EID; lasse(EID,'a', 'z', EID); lasse(EID,'A', 'Z', EID); lasse(EID,'0', '9', EID);TRANS[EID℄['_'℄=EID;JETON[EI℄=JETON[EID℄=300+EID;JETON[EIF℄=300+EIF; /* états finaux *//* ommentaires */TRANS[EINIT℄['/'℄=ES;TRANS[ES℄['/'℄=ESS;TRANS[ES℄['*'℄=ESE; lasse(ESE,0,255,ESE); lasse(ESS,0,255,ESS); lasse(ESEE,0,255,ESE);TRANS[ESE℄['*'℄=ESEE;TRANS[ESEE℄['/'℄=ECOM;TRANS[ESEE℄['*'℄=ESEE;JETON[ECOM℄=-1; /* ommentaire C à filtrer */TRANS[ESS℄['\n'℄=ECOMP;JETON[ECOMP℄=-1; /* ommentaire C++ *//* séparateurs */TRANS[EINIT℄[' '℄=TRANS[EINIT℄['\t'℄=TRANS[EINIT℄['\n'℄=ESEP;TRANS[ESEP℄[' '℄=TRANS[ESEP℄['\t'℄=TRANS[ESEP℄['\n'℄=ESEP;JETON[ESEP℄=-1; /* séparateur à filtrer */}� fon tion d'analyse lexi ale : analex.h./*============================================================================Nom : analex.h Auteur : Mi hel Meynard Définition de la fon : analex()retourne un entier négatif si erreur, positif si OK, 0 si fin de fi hierle filtrage est permis gâ e aux jetons négatifs============================================================================*/#in lude <string.h> har lexeme[1024℄; /* lexème ourant de taille maxi 1024 */int DEBUG=0; /* débogage */int analex(){ /* re onnaît un mot sur l'entrée standard */8

int etat=EINIT; /* unique état initial */int efinal=-1; /* pas d'état final déjà vu */int lfinal=0; /* longueur du lexème final */int ; har s [2℄;int i; /* ara tère ourant */lexeme[0℄='\0'; /* lexeme en var globale (pour le main)*/while (( =get har())!=EOF && TRANS[etat℄[ ℄!=-1){ /* Tq on peut avan er */sprintf(s ,"% ", ); /* transforme le har en haine s */str at(lexeme,s ); /* on aténation */if (DEBUG) printf("%i -- % --> %i ;",etat, ,TRANS[etat℄[ ℄);etat=TRANS[etat℄[ ℄; /* Avan er */if (JETON[etat℄){ /* si état final */efinal=etat; /* s'en souvenir */lfinal=strlen(lexeme); /* longueur du lexeme egalement */} /* fin si */} /* fin while */if (JETON[etat℄){ /* état final */unget ( ,stdin); /* rejeter le ar non utilisé */return (JETON[etat℄<0 ? analex() : JETON[etat℄);/* ret le jeton ou bou le*/}else if (efinal>-1){ /* on en avait vu 1 */unget ( ,stdin); /* rejeter le ar non utilisé */for(i=strlen(lexeme)-1;i>=lfinal;i--)unget (lexeme[i℄,stdin); /* rejeter les ar en trop */lexeme[lfinal℄='\0'; /* voi i le lexeme re onnu */return (JETON[efinal℄<0 ? analex() : JETON[efinal℄);/* ret jeton ou bou le*/}else if (strlen(lexeme)==0 && ==EOF)return 0; /* as parti ulier */else if (strlen(lexeme)==0){lexeme[0℄= ;lexeme[1℄='\0'; /* retourner ( , ) */return ;}else {unget ( ,stdin); /* rejeter le ar non utilisé */for(i=strlen(lexeme)-1;i>=1;i--)unget (lexeme[i℄,stdin); /* rejeter les ar en trop */return lexeme[0℄;}}� Prin ipal : analex. ./*============================================================================Nom : analex. Auteur : Mi hel Meynard Prog prin ipal appelant analex()============================================================================*/#in lude <stdio.h>#in lude "afd.h" /* Définition de l'AFD et des JETONS */#in lude "analex.h" /* Définition de la fon : int analex() */int main(){ /* Constru tion de l'AFD */int j; /* jeton retourné par analex() */ har *invite="Saisissez un(des) mot(s) parmi : un entier, un flottant, un identif., le mot lef if, un ommentaire C ou C++, des espa es, tabulations ou retour ligne SVP : "; reerAfd(); /* Constru tion de l'AFD à jeton */printf("%s",invite); /* prompt */while((j=analex())){ /* analyser tq pas jeton 0 */printf("\nRésultat : Jeton = %d ; Lexeme = %s\n%s",j,lexeme,invite);}return 0;}Solution 2 Expressions régulières orrespondant aux langages réguliers :9

1. Langage des mots- lés : Lkey = {if, then, else, throw} = L(if |then|else|throw)2. Langage des littéraux numériques entiers : Lc10 = L((1| . . . |9)(0|1| . . . |9)∗), Lc8 = L(0(0|1| . . . |7)∗), Lc16 =L(0x(0|1| . . . |9|A|B| . . . |F )+). Le signe éventuel est pris en ompte lors de l'analyse syntaxique.3. Langage Lid des identi� ateurs : Lid = L((a|b| . . . |z|A|B| . . . |Z)(a|b| . . . |z|A|B| . . . |Z|0|1| . . . |9|_)∗).4. Langage des littéraux �ottants dé imaux : Lf = L(((0|1| . . . |9) + .(0|1| . . . |9) ∗ |.(0|1| . . . |9)+)(((e|E)(+| −|ε)(0|1| . . . |9)+)|ε))5. Langage des séparateurs : Lsep = L((ESPACE|\t|\n|//[^\n℄*\n|"/*"([^*℄|"*"+[^*/℄)*"*"+/ )+)Solution 3 Sour e lex : /* analflex.l+ */%{#in lude <iostream.h> /* pour out */%} hiffre ([0-9℄)lettre ([a-zA-Z℄)%%if {return 300;}then {return 301;}else {return 302;}throw {return 303;}0[0-7℄+ {return 304;}0x[0-9A-Fa-f℄+ {return 305;}[1-9℄{ hiffre}* {return 306;}{lettre}({lettre}|{ hiffre}|_)* {return 307;}({ hiffre}+\.{ hiffre}*|\.{ hiffre}+)([eE℄[-+℄?{ hiffre}+)? {return 308;}[ \t\n℄+ {/* ne rien faire : filtrer les blan s */}"//".*\n {/* ne rien faire : filtrer les ommentaires C++ */}"/*"([^*℄|"*"+[^*/℄)*"*"+"/" {/* ne rien faire : filtrer les ommentaires C */}. {return yytext[0℄;}%%int main(){int j;while ((j=yylex())!=0) out<<"Jeton : "<<j<<" de lexème : "<<yytext<<endl;}/* autre façon de traiter les ommentaires C gérant la non fin de fi hier !int i,j;do {while ((i=yyinput())!=EOF && i!='*'); // input si Cif (i==EOF){ out<<"Erreur lexi ale : ommentaires à la C non terminé !\n"; exit(1);}if ((j=yyinput())!='/') unput(j);} while (j!='/');*/Solution 4 Sour e lex supprimant les lignes vides, et les blan s multiples :/* delblan s.l+ */%{ #in lude <iostream.h> /* pour out */%}%%^[\t ℄*\n {/* filtrer les lignes blan hes */}^[\t ℄+ {/* filtrer les débuts blan s et les fin de fi blan s */}[\t ℄+$ {/* filtrer les fins blan hes en fin de ligne (\n) */}[\t ℄+ {int ; /* $ ne mat he pas ave EOF ! */if (( =yyinput())!=EOF){unput( ); 10

out<<'_'; // à hanger en espa e !}elsereturn 0;}%%int main(){int i; while (i=yylex());} // tq pas fin de fi hierSolution 5 Comptage des ara tères, des mots et des lignes :%{ /* omptage.l */int nb ar=0; /* nombre de ar */int nbmot=0; /* nombre de mots */int nbligne=0; /* nombre de lignes */%}%%[^\n\t ℄+ {nbmot++;nb ar+=yyleng;}. {nb ar++;}\n {nb ar++;nbligne++;}%%int main(int nbarg, har* argv[℄){if (nbarg==2){FILE *f=fopen(argv[1℄,"r");yyin=f;} /* ouverture du fi hier */yylex();printf("\nnb ar : %d ; nbmot : %d ; nbligne : %d\n",nb ar,nbmot,nbligne);}Solution 6 Soit l'expression régulière e suivante : e = a((b|c)∗∗|cd)∗b1. Un automate �ni équivalent à e : B = ({a, b, c, d}, {1, 2, 3, 4}, {1}, {4}, {1a2, 2b2, 2c2, 2c3, 2b4, 3d2}).2. B non déterministe. BdetEtComplet = ({a, b, c, d}, {1, 2, 23, 24, p}, {1}, {24}, T ) ave T = {1a2, 1(b|c|d)p, 2b24, 2c23, 2(a|d)p, 23b24, 23d2, 23c23, 23ap, 24b24, 24c2324(a|d)p, p(a|b|c|d)p}).3. Bmini = BdetEtComplet.Solution 7 Soit l'automate �ni B = ({a, b, c}, {1, 2, 3, 4}, {1}, {2, 4}, {1a2, 1a3, 2b2, 2c2, 3b4, 4c3, 4b4}).1. Automate �ni déterministe équivalent à B : Bd = ({a, b, c}, {1, 2, 23, 24}, {1}, {2, 23, 24}, T ) ave

T = {1a23, 23b24, 23c2, 24b24, 24c23, 2b2, 2c2}).2. AFD minimal : Bm = ({a, b, c}, {1, 2}, {1}, {2}, {1a2, 2b2, 2c2}).Solution 8 evaldes ave asso iativité à droite des opérateurs +, *./*============================================================================Nom : evaldes . Auteur : Mi hel MeynardMaj : 16/06/2005 Creation : 8/1/98Projet : Evaluation des endante ré ursive d'expression arithmétique------------------------------------------------------------------------------Spe ifi ation:Ce fi hier ontient un évaluateur d'expressions arithmétiques omposée delittéraux entiers sur un ar, des opérateurs +, * et du parenthésage ().On utilise l'asso iativité à doite : 1+2+3=1+(2+3); 1*2*3=1*(2*3)Remarque : soit rediriger en entrée un fi hier, soit terminer par deux ara tères EOF (Ctrl-D), un pour lan er la le ture, l'autre omme "vrai" EOF.============================================================================*/#in lude <stdio.h>#in lude <stdlib.h>#in lude < type.h> 11

/* les ma ros sont des blo s : pas de ';' apres */#define AVANCER {jeton=get har();num ar++;}#define TEST_AVANCE(prevu) {if (jeton==(prevu)) AVANCER else ERREUR_SYNTAXE}#define ERREUR_SYNTAXE {printf("\nMot non re onnu : erreur de syntaxe \au ara tère numéro %d, de jeton %d \n",num ar,jeton); exit(1);}#define INVITE "Veuillez saisir une expression numérique SVP (q pour quitter) : "void X();int E();int R();int T();int S();int F(); /* dé larations des fon tions */int jeton; /* ara tère ourant du flot d'entrée */int num ar=0; /* numero du ara tère ourant (jeton) */void X(){ /* AXIOME */int r;if (jeton=='q'){ /* regle : X -> 'q' '\n' */AVANCER;if (jeton=='\n')return; /* OK */elseERREUR_SYNTAXE; /* q suivi d'autre hose */}else {r=E(); /* regle : X -> E '\n' X */if (jeton=='\n'){printf("Mot re onnu de valeur : %d\n",r);printf(INVITE);num ar=0; /* réinit */AVANCER; /* avan e au pro hain jeton */X(); /* bou le tq pas 'q' */}else ERREUR_SYNTAXE; /* expression re onnue mais reste des ar */}}int E(){ /* regle : E->TR */return R(T());}int R(int g){if (jeton=='+') { /* regle : R->+TR */AVANCER;return R(g+T()); /* asso iativité à gau he *//* return g+R(T()); asso à droite */}else /* regle : R->epsilon */return g; /* ret la partie gau he */}int T(){ /* regle : T->FS */return S(F());}int S(int g){if (jeton=='*') { /* regle : S->*FS */AVANCER;return S(g*F()); /* asso iativité à gau he *//* return g*S(F()); asso à droite */}else /* regle : S->epsilon */return g; /* ret la partie gau he */}int F(){int r; /* resultat */if (jeton=='(') { /* regle : F->(E) */12

AVANCER;r=E();TEST_AVANCE(')');}elseif (isdigit(jeton)) { /* regle : F->0|1|...|9 */r=jeton-'0'; /* valeur omprise entre 0 et 9 */AVANCER;}else ERREUR_SYNTAXE;return r;}int main(){ /* Fon tion prin ipale */printf(INVITE);num ar=0; /* init */AVANCER; /* initialiser jeton sur le premier ar */X(); /* axiome */return 0; /* ne retourne jamais que par X */}postdes ave asso iativité à gau he des opérateurs +, *./*============================================================================Nom : postdes . Auteur : Mi hel MeynardMaj : 8/3/99 Creation : 8/1/98Projet : Tradu tion postfixe des endante ré ursive d'expression arithmétique------------------------------------------------------------------------------Spe ifi ation:Ce fi hier ontient un tradu teur d'expressions arithmétiques infixéesen expressions arithmétiques postfixées. Les expressions d'entrée sont omposées de littéraux entiers sur un ar, des opérateurs +, * et duparenthésage (). Asso iativité à gau he des opérateurs +, *.Remarque : soit rediriger en entrée un fi hier, soit terminer par deux ara tères EOF (Ctrl-D), un pour lan er la le ture, l'autre omme "vrai" EOF.============================================================================*/#in lude <stdio.h> /* les ma ros sont des blo s : pas de ';' apres */#define AVANCER {jeton=get har();num ar++;}#define TEST_AVANCE(prevu) {if (jeton==(prevu)) AVANCER else ERREUR_SYNTAXE}#define ERREUR_SYNTAXE {printf("\nMot non re onnu : erreur de syntaxe \au ara tère numéro %d \n",num ar); exit(1);}void E();void R();void T();void S();void F(); /* dé larations des fon tions */int jeton; /* ara tère ourant du flot d'entrée */int num ar=0; /* numero du ara tère ourant (jeton) */ har r[100℄; /* resultat */ har *p =r; /* pointeur ourant sur la haine resultat */void E(){T(); /* regle : E->TR */R();}void R(){if (jeton=='+') { /* regle : R->+TR */AVANCERT();*p ='+';p ++; /* é riture du + */R();}else ; /* regle : R->epsilon */13

}void T(){F();S(); /* regle : T->FS */}void S(){if (jeton=='*') { /* regle : S->*FS */AVANCERF();*p ='*';p ++; /* é riture du + */S();}else ; /* regle : S->epsilon */}void F(){if (jeton=='(') { /* regle : F->(E) */AVANCERE();TEST_AVANCE(')')}elseif (isdigit(jeton)) { /* regle : F->0|1|...|9 */*p =( har)jeton;p ++; /* é riture du hiffre */AVANCER}else ERREUR_SYNTAXE}main(){ /* Fon tion prin ipale */AVANCER /* initialiser jeton sur le premier ar */E(); /* axiome */if (jeton==EOF) { /* expression re onnue et rien après */*p ='\0'; /* pour pouvoir être affi hé par printf */printf("\nMot re onnu d'é riture postfixe : %s\n",r);}else ERREUR_SYNTAXE /* expression re onnue mais il reste des ar */}arbindes ave asso iativité à gau he des opérateurs +, *./*============================================================================Nom : arbindes . Auteur : Mi hel MeynardMaj : 8/3/99 Creation : 11/01/98Projet :------------------------------------------------------------------------------Spe ifi ation:Ce fi hier analyse une expression arithmétique et affi he l'arbre abstrait orrespondant. Aso iativité à gau he.============================================================================*/#in lude <stdio.h>#in lude "arbin.h"#define AVANCER {jeton=get har();num ar++;}#define TEST_AVANCE(prevu) {if (jeton==(prevu)) AVANCER else ERREUR_SYNTAXE}#define ERREUR_SYNTAXE {printf("\nMot non re onnu; erreur de syntaxe \au ara tère numéro %d, de jeton %d \n",num ar,jeton); exit(1);}Arbin E();Arbin R();Arbin T();Arbin S();Arbin F(); /* dé larations des fon tions */int jeton; /* ara tère ourant du flot d'entrée */int num ar=0; /* numero du ara tère ourant (jeton) */14

Arbin E(){return R(T()); /* regle : E->TR */}Arbin R(Arbin tg){ /* tg est l'arbin du T de gau he */if (jeton=='+') { /* regle : R->+TR */AVANCER;return R( onstruire('+',tg,T()));}elsereturn tg; /* regle : R->epsilon */}Arbin T(){ /* regle : T->FS */return S(F());}Arbin S(Arbin fg){ /* fg est l'arbin du F de gau he */if (jeton=='*') { /* regle : S->*FS */AVANCER;return S( onstruire('*',fg,F()));}elsereturn fg; /* regle : S->epsilon */}Arbin F(){Arbin r; /* resultat */if (jeton=='(') { /* regle : F->(E) */AVANCER;r=E();TEST_AVANCE(')');}elseif (isdigit(jeton)){ /* regle : F->0|1|...|9 */r= onstruire(jeton, reerarbin(), reerarbin());AVANCER;}else ERREUR_SYNTAXE;return r;}main(){ /* Fon tion prin ipale */Arbin r; /* resultat */AVANCER; /* initialiser jeton sur le premier ar */r=E(); /* axiome */if (jeton==EOF){ /* expression re onnue et rien après */printf("\nMot re onnu dont l'arbre abstrait est : \n");affi hera(r,0);}else ERREUR_SYNTAXE; /* expression re onnue mais il reste des ar */}Solution 9 Cal ulette �ottante des endante en C ave �ex :Fi hier C /*============================================================================Nom : al des . Auteur : Mi hel MeynardMaj : 13/6/2005 Creation : 8/3/99Projet : Evaluation des endante ré ursive d'expression arithmétique flottante------------------------------------------------------------------------------Spe ifi ation:Ce fi hier ontient un évaluateur d'expressions arithmétiques ( al ulette) omposée de littéraux flottants, des 5 opérateurs et du parenthésage ().On utilise l'asso iativité à doite pour la puissan e, à gau he pour les autres.Remarque : la le ture d'expression est répétitive, en as d'erreur toute la15

ligne est supprimée.============================================================================*/#in lude <stdio.h>#in lude <math.h>#define AVANCER {jeton=yylex();}#define TEST_AVANCE(prevu) {if (jeton==(prevu)) AVANCER else ERREUR_SYNTAXE}#define ERREUR_SYNTAXE {printf("\nMot non re onnu : erreur de syntaxe \au ara tère numéro %d \n",num ar);while (jeton!='\n') AVANCER;erreur=1;}#define INVITE "Veuillez saisir une expression arithmétique infixée ou q pour quitter S.V.P. :\n"double valeur; /* var globale utilisee par flex */int jeton; /* ara tère ourant du flot d'entrée */int num ar; /* numero du ara tère ourant (jeton) */int erreur; /* booléen indiquant s'il y a eu erreur */int yylex();void X();double E();double R(double);double T();double S(double);double F();double G();double C(); /* dé larations des fon tions */void X(){num ar=1;erreur=0;double r;if (jeton=='q'){ /* regle : X -> 'q' '\n' */AVANCER;if (jeton=='\n')return; /* OK */else {ERREUR_SYNTAXE; /* q suivi d'autre hose */X();}}else {r=E(); /* regle : X -> E '\n' X */if (!erreur && jeton=='\n'){printf("Résultat : %.2f\n\n",r);}else if (!erreur) {ERREUR_SYNTAXE; /* expression re onnue mais il reste des ar */}printf(INVITE);AVANCER;X();}}double E(){return R(T()); /* regle : E->TR */}double R(double tg){ /* tg est le double du T de gau he */if (jeton=='+') { /* regle : R->+TR */AVANCER;return R(tg+T());}elseif (jeton=='-') { /* regle : R->-TR */AVANCER;return R(tg-T());}return tg; /* regle : R->epsilon */} 16

double T(){ /* regle : T->FS */return S(F());}double S(double fg){ /* fg est le double du F de gau he */if (jeton=='*') { /* regle : S->*FS */AVANCER;return S(fg*F());}elseif (jeton=='/') { /* regle : S->/FS */AVANCER;return S(fg/F());}elsereturn fg; /* regle : S->epsilon */}double F(){ /* regle : F->GC */return C(G()); /* asso iatif de droite a gau he */}double C(double gg){if (jeton=='^') { /* regle : C->^GC */AVANCER;return pow(gg,C(G()));}elsereturn gg; /* regle : C->epsilon */}double G(){double e=0;if (jeton=='(') { /* regle : G->(E) */AVANCER;e=E();TEST_AVANCE(')');}else if (jeton==300){ /* regle : G-><flottant> */e=valeur;/* printf("jeton : %f",e);*/AVANCER;}else ERREUR_SYNTAXE;return e;}int main(){ /* Fon tion prin ipale */printf(INVITE);AVANCER; /* initialiser jeton sur le premier ar */X(); /* axiome */return 0; /* ne retourne jamais que par X */}Fi hier �ex /* al des .fl */ hiffre ([0-9℄)%{extern double valeur; /* valeur flottante du lexème */extern int num ar; /* position du ar */%}%%{ hiffre}+\.{ hiffre}*|\.{ hiffre}+|{ hiffre}+ {valeur=atof(yytext);num ar+=yyleng;return 300;}[ \t℄ {num ar+=1; /* filtrer les blan s */}17

.|\n {num ar+=1;return (int)yytext[0℄;}%%int yywrap(){return 1;}make�le al des : al des .o lex. al .o�e ho debut edition de liens de $�$(CC) $(CFLAGS) -o $� $^ -lm�e ho fin édition de liens : vous pouvez exe uter $�lex. al .o : al des .fl�e ho debut $(LEX)- ompil : $^$(LEX) $^�e ho fin $(LEX)- ompil de : $^�e ho debut ompil de lex.yy. $(CC) $(CFLAGS) - -o $� lex.yy. �e ho fin ompil et obtention de $�Solution 10 Tradu teur d'expression régulière en automate d'état �ni.1. Grammaire �naturelle� :E → a|b| . . . |z|@|0|EE|E ∗ |E′|′ECette grammaire est ambiguë : a|b|c peut être générée de 2 façons (asso iativité à gau he ou à droite).2. Grammaire ré ursive à gau he et non ambiguë :

S → S′|′E|E

E → ET |T

T → T ∗ |F

F → (S)|a|b| . . . |z|@|03. Grammaire non ré ursive à gau he et non ambiguë des expressions régulières :S → EX

X → ′|′EX |ε

E → TR

R → TR|ε

T → FY

Y → ∗Y |ε

F → (S)|a|b| . . . |z|@|04. Analyseur ré ursif des endant onstruisant l'arbre abstrait et l'automate non déterministe./*============================================================================Nom : expreg. Auteur : Mi hel MeynardMaj : 11/04/2000 Creation : 11/03/98Projet :------------------------------------------------------------------------------Spe ifi ation:Ce fi hier analyse une expression régulière, affi he l'arbre abstrait orrespondant, puis l'automate non déterministe onstruit par l'algo deThompson. Asso iativité à gau he des opérateurs | et on at============================================================================*/#in lude <stdio.h>#in lude <stdlib.h>#in lude < type.h>#in lude "arbin.h"#in lude "afn.h"#in lude "afd.h"#in lude "afdm.h"#define AVANCER {jeton=get har();num ar++;}18

#define TEST_AVANCE(prevu) {if (jeton==(prevu)) AVANCER else ERREUR_SYNTAXE}#define ERREUR_SYNTAXE {printf("\nMot non re onnu; erreur de syntaxe \au ara tère numéro %d \n",num ar); exit(1);}Arbin S();Arbin X(Arbin);Arbin E();Arbin R(Arbin);Arbin T();Arbin Y(Arbin);Arbin F();/* dé larations en avant des fon tions */afn a; /* l'afn */int jeton; /* ara tère ourant du flot d'entrée */int num ar=0; /* numero du ara tère ourant (jeton) */Arbin S(){ /* union | */Arbin g; /* resultat de E */g=E(); /* regle : S->EX */return X(g);}Arbin X(Arbin g){ /* suite de union */Arbin d;if (jeton=='|') { /* regle : X->|EX */AVANCER;d=E();if (ra ine(g)=='0') /* 0|e=e */g=d;else if (ra ine(d)!='0')g= onstruire('|',g,d); /* g et d non vides 0|e=e|0=e */return X(g);}return g; /* regle : X->epsilon */}Arbin E(){ /* on aténation */Arbin g; /* resultat de T */g=T(); /* regle : E->TR */return R(g);}Arbin R(Arbin g){ /* suite de on at */Arbin d; /* resultat de T */if (jeton=='(' || islower(jeton) || jeton=='0' || jeton=='�'){d=T(); /* regle : R->TR : premiers(T)= premiers(F) */if (ra ine(g)=='�' || ra ine(d)=='0')g=d; /* �.e=e e.0=0 */else if (ra ine(d)!='�' && ra ine(g)!='0')g= onstruire('.',g,d); /* e.z */return R(g);}return g; /* regle : R->epsilon */}Arbin T(){Arbin g; /* resultat de F */g=F();return Y(g); /* regle : T->FY */}Arbin Y(Arbin g){ /* ret vrai (1) si au moins 1 étoile */Arbin d; /* resultat de Y */if (jeton=='*') { /* regle : Y->*Y */AVANCER;if (ra ine(g)=='�'||ra ine(g)=='0')d= onstruire('�', reerarbin(), reerarbin()); /* �*=0*=� */else if (ra ine(g)=='*')d=g; /* e**=e* */ 19

elsed= onstruire('*',g, reerarbin()); /* ni epsilon ni ensemble vide ni * */return Y(d);}else return g; /* regle : Y->epsilon */}Arbin F(){Arbin r; /* resultat */if (jeton=='(') { /* regle : F->(S) */AVANCER;r=S();TEST_AVANCE(')');}elseif (islower(jeton)||jeton=='0'||jeton=='�'){ /* regle : F->a|b|...|z|�|0 *//* � epsilon, 0 ensemble vide */r= onstruire(jeton, reerarbin(), reerarbin());AVANCER;}else ERREUR_SYNTAXE;return r;}int nombreEtat(Arbin a){ /* al ul du nombre d'état de l'afn */if (videa(a))return 0;elseif (ra ine(a)=='.') /* la on at ne rajoute pas d'état */return nombreEtat(sag(a))+nombreEtat(sad(a));else /* union, *, symbole né essitent 2 nouveaux états */return 2+nombreEtat(sag(a))+nombreEtat(sad(a));}int main(){ /* Fon tion prin ipale */Arbin r; /* resultat */int nbetat; /* nombre d'états */afn n;afde d;afd d1,d2;printf("\nVeuillez saisir une expression régulière suivie de <Entrée> S.V.P.\n");AVANCER; /* initialiser jeton sur le premier ar */r=S(); /* axiome */if (jeton=='\n'){ /* expression re onnue et rien après */printf("\nMot re onnu dont l'arbre abstrait est : \n");affi hera(r,0);if (ra ine(r)=='0'){printf("\nLe langage de l'expression régulière est vide !\n");exit(0);}printf("\nConstru tion de l'AFN de %i états ...\n", nbetat=nombreEtat(r));n=afn_ reer(nbetat,r);printf("\nAFN : %s",afn_ haine(n));d=afde_ reer(n);printf("\nAFD : %s\n",afde_ haine(d));d1=afd_ reer(d);printf("\nAFD : %s",afd_ haine(d1));afn_detruire(n);d2=minimiser(d1);printf("\nAFDM : %s\n",afd_ haine(d2));20

}else ERREUR_SYNTAXE; /* expression re onnue mais il reste des ar */return 0;}5. Optimisation déjà réalisée dans le programme pré édent.6. Table d'analyse de l'automate à pile en analyse des endante :VN premiers TabSuivants

S a, ( $, )X ε, | $, )E a, ( |, $, )R ε, a, ( |, $, )T a, ( |, $, ), a, (Y ε, ∗ |, $, ), a, (F a, ( |, $, ), a, (

a ( ) | ∗ $S S → EX S → EX

X X → ε X → |EX X → ε

E E → TR E → TR

R R → TR R → TR R → ε R → ε R → ε

T T → FY T → FY

Y Y → ε Y → ε Y → ε Y → ε Y → ∗Y Y → ε

F F → a F → (S)7. états su essifs de la pile sur ab ∗ |c.Pile F lotd′entre Action

$S ab ∗ |c$ S → EX

$XE ab ∗ |c$ E → TR

$XRT ab ∗ |c$ T → FY

$XRY F ab ∗ |c$ F → a

$XRY a ab ∗ |c$ AV ANCER

$XRY b ∗ |c$ Y → ε

$XR b ∗ |c$ R → TR

$XRT b ∗ |c$ T → FY

$XRY F b ∗ |c$ F → a

$XRY a b ∗ |c$ AV ANCER

$XRY ∗|c$ Y → ∗Y$XRY ∗ ∗|c$ AV ANCER

$XRY |c$ Y → ε

$XR |c$ R → ε

$X |c$ X → |EX

$XE| |c$ AV ANCER

$XE c$ E → TR

$XRT c$ T → FY

$XRY F c$ F → a

$XRY a c$ AV ANCER

$XRY $ R → ε

$XR $ Y → ε

$X $ X → ε

$ $ ACCEPTER8. fon tion NombreEtat(Arbin a) dans le programme suivant.9. Constru tion de Thompson :/*============================================================================Nom : afn.h Auteur : Mi hel MeynardMaj : Creation : 17/2/2003Projet : expreg. ------------------------------------------------------------------------------Spe ifi ation:Ce fi hier dé lare les AFN de Thompson.============================================================================*//* un afn : tableau nbetat-1 lignes par 3 olonnes (nbetat>1) ol 1 : symbole de transsi symbole=epsilon alors 1 ou 2 transitions par epsilon ol 2 : etat destination ol 3 : etat destination*/#ifndef _AFN 21

#define _AFN#in lude "arbin.h"typedef stru t afn_stru t {int **trans; /* trans : un tableau dynamique de nbetat*3 int */int nbetat; /* nombre d'états */int etat; /* état ourant */int etatInit;int etatFin; /* etat initial et final de l'afn */} afn_stru t;typedef stru t afn_stru t * afn;afn afn_ reer(int nbe,Arbin r); /* onstru teur */void afn_detruire(afn a); /* désallouer *//* fon tion ré ursive */void afn_ onstruire(afn a,int *ei,int *ef,Arbin r);/* onstru tion d'un afn non vide à partir d'un arbre binaire (exp reg) */ har * afn_ haine(afn a);#endif/*============================================================================Nom : afn. Auteur : Mi hel MeynardMaj : Creation : 10/06/99Projet : expreg. ------------------------------------------------------------------------------Spe ifi ation:Ce fi hier permet de gérer un AFN de Thompson.============================================================================*/#in lude <stdio.h>#in lude <stdlib.h>#in lude < type.h>#in lude <string.h>#in lude "arbin.h"#in lude "afn.h"afn afn_ reer(int nbe,Arbin r){ /* onstru teur */afn a;int i;a=(afn)mallo (sizeof(afn_stru t));a->trans=(int**) mallo (((a->nbetat=nbe)-1)*sizeof(int));for (i=0;i<a->nbetat-1;i++)a->trans[i℄=(int*) mallo (3*sizeof(int));a->etat=a->etatFin=a->etatInit=-1;afn_ onstruire(a,&(a->etatInit),&(a->etatFin),r);return a;}void afn_detruire(afn a){int i;for (i=0;i<a->nbetat-1;i++)free(a->trans[i℄); /* désallouer */free(a->trans);}/* fon tion ré ursive modifiant l'afn pointé */void afn_ onstruire(afn a,int *ei,int *ef,Arbin r){/* onstru tion d'un afn non vide à partir d'un arbre binaire (exp reg) */int ig,fg,id,fd; /* états initiaux et finaux de g et d */if (islower(ra ine(r))||ra ine(r)=='�'){ /* symbole ou epsilon */a->etat++; /* nouvel état */*ei=a->etat; /* état initial */a->trans[*ei℄[0℄=ra ine(r); /* affe tation du symbole */22

a->etat++; /* nouvel état */a->trans[*ei℄[1℄=a->etat; /* état de transition */*ef=a->etat; /* état final */a->trans[*ei℄[2℄=-1; /* pas de 2ème transition */}else if (ra ine(r)=='.'){ /* on at */afn_ onstruire(a,&ig,&fg,sag(r)); /* ré ursif sur sag() */afn_ onstruire(a,&id,&fd,sad(r)); /* ré ursif sur sad() */a->trans[fg℄[0℄='�'; /* symbole : epsilon */a->trans[fg℄[1℄=id; /* transition epsilon vers init de droite */a->trans[fg℄[2℄=-1; /* pas de 2ème transition */*ei=ig;*ef=fd; /* l'état final reste elui de droite */}else if (ra ine(r)=='|'){ /* union */afn_ onstruire(a,&ig,&fg,sag(r)); /* ré ursif sur sag() */afn_ onstruire(a,&id,&fd,sad(r)); /* ré ursif sur sad() */a->etat++; /* nouvel état initial */a->trans[a->etat℄[0℄='�'; /* affe tation du symbole epsilon */a->trans[a->etat℄[1℄=ig; /* transition epsilon vers init de gau he */a->trans[a->etat℄[2℄=id; /* transition epsilon vers init de droite */*ei=a->etat; /* nouvel état initial */a->etat++; /* nouvel état final */a->trans[fg℄[0℄='�'; /* symbole : epsilon */a->trans[fg℄[1℄=a->etat; /* transition epsilon vers nouveau final */a->trans[fg℄[2℄=-1; /* pas de 2ème transition */a->trans[fd℄[0℄='�'; /* symbole : epsilon */a->trans[fd℄[1℄=a->etat; /* transition epsilon vers nouveau final */a->trans[fd℄[2℄=-1; /* pas de 2ème transition */*ef=a->etat; /* état final */}else if (ra ine(r)=='*'){ /* étoile */afn_ onstruire(a,&ig,&fg,sag(r)); /* ré ursif sur sag() */a->etat++; /* nouvel état initial */a->trans[a->etat℄[0℄='�'; /* affe tation du symbole epsilon */a->trans[a->etat℄[1℄=ig; /* transition epsilon vers init de gau he */*ei=a->etat; /* nouvel état initial */a->etat++; /* nouvel état final */a->trans[*ei℄[2℄=a->etat; /* transition epsilon vers nouveau final */a->trans[fg℄[0℄='�'; /* symbole : epsilon */a->trans[fg℄[1℄=a->etat; /* transition epsilon vers nouveau final */a->trans[fg℄[2℄=ig; /* retour vers l'état initial pour bou lage */*ef=a->etat; /* état final */}} har * afn_ haine(afn a){int etat; har *sd=( har *)mallo (2048),s[128℄; /* ATTENTION */sprintf(sd,"état initial : %4d; état final : %4d\n",a->etatInit,a->etatFin);for(etat=0;etat<a->nbetat-1;etat++){ /* le dernier état est final ! */sprintf(s,"(%4d % %4d),",etat,a->trans[etat℄[0℄,a->trans[etat℄[1℄);str at(sd,s);if (a->trans[etat℄[2℄!=-1){ /* 2 transitions */sprintf(s,"(%4d % %4d),",etat,a->trans[etat℄[0℄,a->trans[etat℄[2℄);str at(sd,s);}}sd[strlen(sd)-1℄='\n';return sd;} 23

/*=============================================================================Nom: afd.h Auteur: Mi hel MeynardMaj: 16/06/2005 Creation: 17/2/2003Projet:-------------------------------------------------------------------------------Spe ifi ation: dé laration utiles à la gestion d'un afd=============================================================================*/#ifndef _AFD#define _AFD#in lude "afn.h"#in lude "../../../../../C/Sd/sd.h"/* -----------------------AFDE----------------------------------------------- *//** Un AFDE est un AFD dont les états dont des Ensembles d'états de l'AFN */typedef stru t afde_stru t { /* Autom d'états finis déterministe */ensg einit; /* état initial (ens d'états) */ensg efinaux; /* ens des ens d'états finaux */assog graphe; /* de lé : un ens d'états;de valeur : une assog( har, ens d'états) */} afde_stru t;typedef stru t afde_stru t * afde;void afde_eps_ferme(ensg e,afn a);/* EpsilonFermeture de e : ajoute les états a essibles par epsilon */afde afde_ reer(afn n); /* onstru teur */ har* afde_ haine(afde a); /* onvertit en haine *//* ------------------------AFD---------------------------------------------- *//** Un AFD est un AFDE dont on a renuméroté haque état par un entier 0..n-1 */typedef stru t afd_stru t { /* Autom d'états finis entiers déterministes */int einit; /* état initial (entier) */ensg efinaux; /* ens d'états finaux */assog graphe; /* de lé : un état;de valeur : une assog( har, état entier) */} afd_stru t;typedef stru t afd_stru t * afd;afd afd_ reer(afde a); /* onstru teur */ har* afd_ haine(afd a);#endif/*=============================================================================Nom: afd. Auteur: Mi hel MeynardMaj: 20/2/2003 Creation: 17/2/2003Projet:-------------------------------------------------------------------------------Spe ifi ation: définitions des fon tions=============================================================================*/#in lude <stdio.h>#in lude <stdlib.h>#in lude "../../../../../C/Sd/sd.h"#in lude "afd.h"int DEBUG=0; 24

afde afde_ reer(afn n){afde a; /* l'afde formé d'ens */assog trans; /* transition ( har, ens), */ensg atraiter,etat,nouvetat; /* ensemble des ens d'états à traiter */ensg_it it; /* itérateur sur l'ens des états à traiter */ har ,*p ; /* har de transition */int *pi,*pj; /* états de l'afn */a=(afde)mallo (sizeof(afde_stru t)); /* allo ation */a->einit=ensg_entier_ reer(10); /* ens d'états initiaux */ensg_ajouter(a->einit,entier_ reer(n->etatInit)); /* unique état init de afn */afde_eps_ferme(a->einit,n);if (DEBUG) printf("\nEtat initial : {%s}\n",ensg_ haine(a->einit));a->efinaux=ensg_ reer(10,/* ensemble d'ensemble d'entiers */(int(*)(void *,void *))ensg_egal,(unsigned int(*)(void *))ensg_hash,( har*(*)(void *))ensg_ haine); /* ensg */a->graphe=assog_ reer(10, /* à haque état (ensg),une assog ( har, état) */(int(*)(void *,void *))ensg_egal,/* lé = ens */(unsigned int(*)(void *))ensg_hash,( har*(*)(void *))ensg_ haine,( har*(*)(void *))assog_ haine /* valeur = asso trans */); /* assog */atraiter=ensg_ reer(10,/* ensg d'ens d'entier */(int(*)(void *,void *))ensg_egal, /* lé ens */(unsigned int(*)(void *))ensg_hash, /* lé entière */( har*(*)(void *))ensg_ haine); /* ensg */ensg_ajouter(atraiter,a->einit); /* au début, que l'état initial */while ((etat=ensg_extraire(atraiter))){ /* BOUCLE PRINCIPALE *//* tq il reste des états non traités */if (DEBUG) printf("Etat ourant : %s\n",ensg_ haine(etat));trans=assog_ reer(10,/* ens des transitions */(int(*)(void *,void *)) ar_egal,/* lé = ar */(unsigned int(*)(void *)) ar_hash,( har*(*)(void *)) ar_ haine,( har*(*)(void *))ensg_ haine /* valeur = ensg etats */);assog_ajouter(a->graphe,etat,trans); /* ajouter l'état et des trans vide */if (ensg_present(etat,entier_ reer(n->etatFin))){ /* si l'état est final*/ensg_ajouter(a->efinaux,etat);}/* pour haque état de l'afn */it=ensg_it_ reer(etat); /* par ourir haque état de l'afn */while((pi=ensg_it_pro hain(it))){ /* *pi est un état afn */if (*pi!=n->etatFin && ( =n->trans[*pi℄[0℄)!='�'){/* si pas final et pas epsilon */pj=entier_ reer(n->trans[*pi℄[1℄); /* état afn destinataire */nouvetat=assog_valeur(trans,& ); /* état déjà présent ? */if (nouvetat==NULL){ /* har pas en ore vu */nouvetat=ensg_entier_ reer(10); /* allo */ensg_ajouter(nouvetat,pj);/* le nouvel état dest */assog_ajouter(trans, ar_ reer( ),nouvetat);if (DEBUG) printf(" trans (% ) --> %s\n", ,ensg_ haine(nouvetat));}else{ /* etat - -> nouvetat dans trans */25

ensg_ajouter(nouvetat,pj); /* 1 état afn */} } /* pour les epsilon, rien à faire */} /* fin du par ours des états de l'afn */assog_it_detruire(it);it=assog_it_ reer(trans); /* par ourir les trans */while(assog_it_pro hain(it,(void**)&p ,(void**)&nouvetat)){/* *p est un har, nouvetat est un ens d'entier */afde_eps_ferme(nouvetat,n); /* fermer epsilon par l'afn */if (DEBUG) printf("epsilon fermeture : %s\n",ensg_ haine(nouvetat));if(ensg_absent(a->graphe,nouvetat)){ /* nouvetat pas en ore traité */ensg_ajouter(atraiter,nouvetat); /* même s'il y était déjà */}}assog_it_detruire(it);} /* atraiter est vide */ensg_detruire(atraiter);return a;}/* afde_ haine(afde a) */ har* afde_ haine(afde a){ haine h;assog_it it,it2; /* itérateur */void* etat,*trans;void* p ,*dest; h= haine_ reer("Afd avant renumérotation ; l'état initial est : {"); h= haine_ at( h,ensg_ haine(a->einit)); h= haine_ at( h,"}");it=assog_it_ reer(a->graphe);while(assog_it_pro hain(it,(void**)&etat,(void**)&trans)){ h= haine_ at( h,"\nEtat : {"); h= haine_ at( h,a->graphe-> le_ haine(etat)); h= haine_ at( h,"} ");if (ensg_present(a->efinaux,etat)){ h= haine_ at( h,"FINAL : ");}else{ h= haine_ at( h,": ");}it2=assog_it_ reer(trans);while(assog_it_pro hain(it2,(void**)&p ,(void**)&dest)){ h= haine_ at( h,"--"); h= haine_ at( h, ar_ haine(p )); h= haine_ at( h,"--> {"); h= haine_ at( h,ensg_ haine(dest)); h= haine_ at( h,"}, ");}assog_it_detruire(it2);}assog_it_detruire(it);return h;}/* EpsilonFermeture de e : ajoute les états a essibles par epsilon */void afde_eps_ferme(ensg e,afn n){int *etat,i,*su ,j; /* état ourant (etat,i), suivant (su ,j) */ensg atraiter; /* ens des états a traiter */26

atraiter=ensg_ lone(e); /* init ave haque état de l'afn */while((etat=ensg_extraire(atraiter))){ /* traiter 1 fois haque état */i=*etat;if (i!=n->etatFin && n->trans[i℄[0℄=='�'){ /* epsilon */j=n->trans[i℄[1℄; /* au moins 1 su esseur */if (ensg_absent(e,&j)){ /* pas en ore traité */ensg_ajouter(e,su =entier_ reer(j));/* ajouter l'état a essible */ensg_ajouter(atraiter,su );/* atraiter est in lus ou égal à e */}if ((j=n->trans[i℄[2℄)!=-1){ensg_ajouter(e,su =entier_ reer(j));/* ajouter l'état a essible */ensg_ajouter(atraiter,su );/* atraiter est in lus ou égal à e */}}}}afd afd_ reer(afde a){ /* NUMEROTATION de a dans a1 */assog trans,nouvtrans; /* transition ( har, ens), */ensg atraiter,etat,nouvetat; /* ensemble des ens d'états à traiter */ har *p ; /* har de transition */int *dest,*sr ,numetat; /* états de l'afd */assog renum;afd a1;a1=(afd)mallo (sizeof(afd_stru t)); /* puis renuméroté et retourné */a1->efinaux=ensg_entier_ reer(10);a1->graphe=assog_ reer(10, /* à haque état ent, une assog ( har, ent) */(int(*)(void *,void *))entier_egal, /* lé entière */(unsigned int(*)(void *))entier_hash,( har*(*)(void *))entier_ haine,( har*(*)(void *))assog_ haine /* valeur asso trans */); /* assog */renum=assog_ reer(10,/* à haque état de a, un entier de a1 */(int(*)(void *,void *))ensg_egal,/* lé ens */(unsigned int(*)(void *))ensg_hash,( har*(*)(void *))ensg_ haine,( har*(*)(void *))entier_ haine /* valeur entière */); /* assog */numetat=0; /* état initial */atraiter=ensg_ reer(10,/* ens d'ens d'entier */(int(*)(void *,void *))ensg_egal, /* lé ens */(unsigned int(*)(void *))ensg_hash, /* lé entière */( har*(*)(void *))ensg_ haine); /* ens des états de l'afd à traiter *//* e qui est dans atraiter est deja numéroté */ensg_ajouter(atraiter,a->einit);a1->einit=numetat;assog_ajouter(renum,a->einit,(entier_ reer(numetat++)));/* {8,0,2} --> 0 *//* pour haque état sour e de trans */while((etat=ensg_extraire(atraiter))){ /* etat ens */sr =assog_valeur(renum,etat); /* état sr dans afd *//*printf("debug:afd_ reer:renum : %s\nsr =%i\n",assog_ haine(renum),*sr ); */27

/* printf("debug:atraiter:%s\n",assog_ haine(atraiter)); */if (ensg_present(a->efinaux,etat)){ensg_ajouter(a1->efinaux,sr ); /* sr est final */}nouvtrans=assog_ reer(10,/* ens des transitions */(int(*)(void *,void *)) ar_egal,/* lé ens */(unsigned int(*)(void *)) ar_hash,( har*(*)(void *)) ar_ haine,( har*(*)(void *))entier_ haine /* valeur asso trans */); trans=assog_valeur(a->graphe,etat); /* transitions a tuelles */while(assog_extraire(trans,(void**)&p ,(void**)&nouvetat)){if ((dest=assog_valeur(renum,nouvetat))==NULL){ /* la dest n'existe pas */assog_ajouter(renum,nouvetat,(dest=entier_ reer(numetat++)));ensg_ajouter(atraiter,nouvetat);/* printf("debug:atraiter:%s\n",assog_ haine(atraiter)); */}assog_ajouter(nouvtrans,p ,dest); /* nouv transition 0 --a--> 1 */}assog_ajouter(a1->graphe,sr ,nouvtrans);}return a1;} har* afd_ haine(afd a){ haine h;assog_it it,it2; /* itérateur */void* etat,*trans;void* p ,*dest; h= haine_ reer("Afd : l'état initial est "); h= haine_ at( h,entier_ haine(&a->einit));it=assog_it_ reer(a->graphe);while(assog_it_pro hain(it,(void**)&etat,(void**)&trans)){ h= haine_ at( h,"\nEtat : "); h= haine_ at( h,a->graphe-> le_ haine(etat)); h= haine_ at( h," ");if (ensg_present(a->efinaux,etat)){ h= haine_ at( h,"FINAL : ");}else{ haine_ at( h,": ");}it2=assog_it_ reer(trans);while(assog_it_pro hain(it2,(void**)&p ,(void**)&dest)){ h= haine_ at( h,"--"); h= haine_ at( h, ar_ haine(p )); h= haine_ at( h,"--> "); h= haine_ at( h,entier_ haine(dest)); h= haine_ at( h,", ");}assog_it_detruire(it2);}assog_it_detruire(it); h= haine_ at( h,"\n");return h;}make�le :expreg : expreg.o arbin.o afn.o afd.o ../../../../../C/Sd/libsd.a28

$(CC) $(CFLAGS) -o expreg $^�e ho fin édition de liens : vous pouvez exe uter $�Solution 11 Exer i e 10 en analyse as endante.1. sour e bison de la grammaire ré ursive à gau he non ambiguë :/* expregasre g.y */%{#in lude "arbin.h"void yyerror( har*);int yylex(); har * invite="\nVeuillez saisir une expression régulière suivie de <Entrée> S.V.P.\n";%}%union { /* YYSTYPE */Arbin typeArbin;int typeInt;}/* definition des jetons */%token<typeInt> SYMBOLE/* definition des types des non terminaux */%type<typeArbin> s e t f%%liste : /* haine vide sur fin de fi hier Ctrl-D */| liste ligne {printf(invite);};ligne : '\n'/* ligne vide : expression vide */| error '\n'{yyerrok; /* après la fin de ligne */}| s '\n'{affi hera($1,0);};s : s '|' e {$$= onstruire('|',$1,$3);}| e {$$=$1;};e : e t {$$= onstruire('.',$1,$2);}| t {$$=$1;};t : t '*' {$$= onstruire('*',$1, reerarbin());}| f {$$=$1;};f : '(' s ')' {$$=$2;}| SYMBOLE {$$= onstruire(yylval.typeInt, reerarbin(), reerarbin());};%%int yylex(){int i=get har();if ((i>='a' && i<='z')||i=='�'||i=='0'){yylval.typeInt=i;return SYMBOLE;}else return i;}void yyerror( har *s) {fprintf(stderr,"%s\n",s);}int main(){/*yydebug=1;*/printf(invite);return yyparse();}2. sour e bison de la grammaire naturelle :/* expregas.y */%{#in lude < type.h>#in lude "arbin.h"#in lude "afnThomp.h"void yyerror( har*);int yylex();int nombreEtat(Arbin); 29

har * invite="\nVeuillez saisir une expression régulière suivie de <Entrée> S.V.P.\n";%}%union { /* YYSTYPE */Arbin a;int i;}%token<i> LETTRE /* definition des jetons */%type<a> expr /* definition des types des non terminaux */%left '|' /* traitement des priorites sur les operateurs du moins au plus */%left CONCAT LETTRE '(' /* symbole virtuel pour la on aténation (impli ite) *//* né essaires pour onflits ave CONCAT */%left '*'%%liste : /* haine vide sur fin de fi hier Ctrl-D */| liste ligne {printf(invite);};ligne : '\n' /* ligne vide : expression vide */| error '\n' {yyerrok; /* après la fin de ligne */}| expr '\n'{ int nbetat;affi hera($1,0);if (ra ine($1)=='0')printf("\nLe langage de l'expression régulière est vide !\n");else{printf("\nConstru tion de l'Automate de %i états ...\n", nbetat=nombreEtat($1));initAfn(nbetat); onstruireAfn($1);affi herAfn();}};expr : '(' expr ')' {$$ = $2;}| expr expr %pre CONCAT{Arbin g,d;g=$1;d=$2; /* CONCAT */if (videa(d))$$= g;else { /* g et d non vides */if (ra ine(g)=='�'){ /* �.e=e.�=e */videra(&g);$$= d;}else if (ra ine(d)=='�'){videra(&d);$$= g;}else if (ra ine(g)=='0'){ /* 0.e=e.0=0 */videra(&d);$$= g;}else if (ra ine(d)=='0'){videra(&g);$$= d;}else $$= onstruire('.',g,d);} 30

}| expr '|' expr{Arbin g,d;g=$1;d=$3; /* UNION */if (videa(d))$$= g;else { /* g et d non vides */if (ra ine(g)=='0'){ /* 0|e=e|0=e */videra(&g);$$= d;}else if (ra ine(d)=='0'){ /* e|0=e */videra(&d);$$= g;}else$$= onstruire('|',g,d);}}| expr '*'{Arbin g=$1; /* ETOILE */if (ra ine(g)=='�'||ra ine(g)=='0'){ /* �*=0*=� */videra(&g);$$= onstruire('�', reerarbin(), reerarbin());}else /* ni epsilon ni ensemble vide */if (ra ine(g)=='*')$$=g;else$$= onstruire('*',g, reerarbin());}| LETTRE {$$= onstruire($1, reerarbin(), reerarbin());};%%int yylex(){int i=get har();if (islower(i)||i=='�'||i=='0'){yylval.i=i;return LETTRE;}else return i;}void yyerror( har *s) {fprintf(stderr,"%s\n",s);}int nombreEtat(Arbin a){ /* al ul du nombre d'état de l'afn */if (videa(a))return 0;elseif (ra ine(a)=='.') /* la on at ne rajoute pas d'état */return nombreEtat(sag(a))+nombreEtat(sad(a));else /* union, *, symbole né essitent 2 nouveaux états */return 2+nombreEtat(sag(a))+nombreEtat(sad(a));}int main(){/*yydebug=1;*/printf(invite);return yyparse();}/*============================================================================Nom : afnThomp.h Auteur : Mi hel MeynardMaj : 13/6/2005 Creation : 13/6/2005Projet : expregas------------------------------------------------------------------------------Spe ifi ation:Fi hier d'en-tête pour gérer un AFN de Thompson.============================================================================*//** retourne un afn : tableau nbetat-1 lignes par 3 olonnes (nbetat>1)31

* ol 1 : symbole de trans* si symbole=epsilon alors 1 ou 2 transitions par epsilon* ol 2 : etat destination* ol 3 : etat destination*/int ** initAfn(int nbetat);/** onstru tion d'un afn non vide à partir d'un arbre binaire (exp reg) */void onstruireAfn(Arbin);/** affi he l'afn */void affi herAfn();/*============================================================================Nom : afnThomp. Auteur : Mi hel MeynardMaj : 13/6/2005 Creation : 10/06/99Projet : expregas------------------------------------------------------------------------------Spe ifi ation:Ce fi hier permet de gérer un AFN de Thompson.============================================================================*/#in lude <stdio.h>#in lude <stdlib.h>#in lude < type.h>#in lude "arbin.h"stati int **afn=NULL; /* afn : un tableau dynamique de nbetat*3 int */stati int nbetat; /* nombre d'états */stati int etat; /* état ourant */stati int etatInit,etatFin; /* etat initial et final de l'afn */int ** initAfn(int nbe){/* retourne un afn : tableau nbetat-1 lignes par 3 olonnes (nbetat>1) ol 1 : symbole de transsi symbole=epsilon alors 1 ou 2 transitions par epsilon ol 2 : etat destination ol 3 : etat destination*/int i;if (afn!=NULL){ /* pas la 1ere fois */for (i=0;i<nbetat-1;i++)free(afn[i℄); /* désallouer */free(afn);}afn=(int**) mallo (((nbetat=nbe)-1)*sizeof(int));for (i=0;i<nbetat-1;i++)afn[i℄=(int*) mallo (3*sizeof(int));etat=-1;return afn;}/* onstru tion d'un afn non vide à partir d'un arbre binaire (exp reg) */void onstruireAfn(Arbin r){int ig,fg,id,fd; /* états initiaux et finaux de g et d */if (islower(ra ine(r))||ra ine(r)=='�'){ /* symbole ou epsilon */etat++; /* nouvel état */afn[etat℄[0℄=ra ine(r); /* affe tation du symbole */etatInit=etat; /* état initial */etat++; /* nouvel état */afn[etatInit℄[1℄=etat; /* état de transition */32

etatFin=etat; /* état final */afn[etatInit℄[2℄=-1; /* pas de 2ème transition */}else if (ra ine(r)=='.'){ /* on at */ onstruireAfn(sag(r)); /* ré ursif sur sag() */ig=etatInit;fg=etatFin; /* états initiaux et finaux de gau he */ onstruireAfn(sad(r)); /* ré ursif sur sad() */id=etatInit;fd=etatFin; /* états initiaux et finaux de gau he */afn[fg℄[0℄='�'; /* symbole : epsilon */afn[fg℄[1℄=id; /* transition epsilon vers init de droite */afn[fg℄[2℄=-1; /* pas de 2ème transition */etatInit=ig; /* l'état final reste elui de droite */}else if (ra ine(r)=='|'){ /* union */ onstruireAfn(sag(r)); /* ré ursif sur sag() */ig=etatInit;fg=etatFin; /* états initiaux et finaux de gau he */ onstruireAfn(sad(r)); /* ré ursif sur sad() */id=etatInit;fd=etatFin; /* états initiaux et finaux de gau he */etat++; /* nouvel état initial */afn[etat℄[0℄='�'; /* affe tation du symbole epsilon */afn[etat℄[1℄=ig; /* transition epsilon vers init de gau he */afn[etat℄[2℄=id; /* transition epsilon vers init de droite */etatInit=etat; /* nouvel état initial */etat++; /* nouvel état final */afn[fg℄[0℄='�'; /* symbole : epsilon */afn[fg℄[1℄=etat; /* transition epsilon vers nouveau final */afn[fg℄[2℄=-1; /* pas de 2ème transition */afn[fd℄[0℄='�'; /* symbole : epsilon */afn[fd℄[1℄=etat; /* transition epsilon vers nouveau final */afn[fd℄[2℄=-1; /* pas de 2ème transition */etatFin=etat; /* état final */}else if (ra ine(r)=='*'){ /* étoile */ onstruireAfn(sag(r)); /* ré ursif sur sag() */ig=etatInit;fg=etatFin; /* états initiaux et finaux de gau he */etat++; /* nouvel état initial */afn[etat℄[0℄='�'; /* affe tation du symbole epsilon */afn[etat℄[1℄=ig; /* transition epsilon vers init de gau he */etatInit=etat; /* nouvel état initial */etat++; /* nouvel état final */afn[etatInit℄[2℄=etat; /* transition epsilon vers nouveau final */afn[fg℄[0℄='�'; /* symbole : epsilon */afn[fg℄[1℄=etat; /* transition epsilon vers nouveau final */afn[fg℄[2℄=ig; /* retour vers l'état initial pour bou lage */etatFin=etat; /* état final */}}void affi herAfn(){int etat;printf("\nL'état initial est l'état %4d et l'état final est %4d\n",etatInit,etatFin);for(etat=0;etat<nbetat-1;etat++){ /* le dernier état est final ! */printf("transition : %4d % %4d\n",etat,afn[etat℄[0℄,afn[etat℄[1℄);if (afn[etat℄[2℄!=-1) /* 2 transitions */printf("transition : %4d % %4d\n",etat,afn[etat℄[0℄,afn[etat℄[2℄);}}Solution 12 Cal ulette logique d'ordre 0 :sour e lex /* logi .l */33

var ([a-z℄)%{#in lude "y.tab.h" /* JETONS rees par ya et definition de yylval */#in lude <stdio.h> /* pour printf */%}%%[ \t℄+ {/* filtrer les blan s */}0|false|faux { yylval=0; return BOOL; }1|true|vrai { yylval=1; return BOOL; }{var} { yylval=yytext[0℄-'a'; return VAR;}& { return AND; }\| { return OR; }\^ { return XOR; }-> { return IMP; }== { return EQ; }! { return NOT; }exit|quit { return (QUIT); }aide|help|\? { return (HELP); }. { return yytext[0℄; /* indispensable ! */}[\n℄ { return yytext[0℄; /* indispensable egalement ! */}%%int yywrap(){return 1;} /* pas de ontinuation sur un autre fi hier */sour e ya /*logi .y */%{ har * invite="\nVeuillez saisir une expression logique suivie de <Entrée> S.V.P.\n";int var[26℄; /* les 26 variables a-z */int yylex();void yyerror( har *);%} /* YYSTYPE est un entier par défaut */%token BOOL VAR AND OR NOT IMP EQ XOR QUIT HELP /* definition des jetons */%left OR IMP EQ XOR /* traitement des priorites des operateurs */%left AND%right NOT%%liste : /* haine vide sur fin de fi hier Ctrl-D */| liste ligne {printf(invite);};ligne : '\n' /* ligne vide : expression vide */| error '\n' {yyerrok; /* après la fin de ligne */}| expr '\n'{ printf("Résultat : %i\n",$1); /* une valeur entière (bool) */}| VAR '=' expr '\n'{ var[$1℄=$3;}| QUIT '\n' {return 0; /* fin de yyparse */}| HELP '\n' {printf(" Aide de la al ulette logique\n");printf(" =============================\n");printf("Taper une expression onstituée de booléens, d'opérations,\n");printf("de variables (de a à z), de parenthèses puis taper <Entrée> \n");printf("Ou taper une ommande suivie de <Entrée>\n\n");printf("Syntaxe des booléens : 0 ou false ou faux \n");34

printf(" ou 1 ou true ou vrai \n");printf("Opérations infixes : & (et), | (ou), -> (impli ation),\n");printf(" == (équivalen e), ^ (ou ex lusif)\n");printf("Opérations préfixes : ! (négation)\n");printf("Commandes : exit ou quit pour quitter la al ulette\n");printf(" aide ou help ou \? pour affi her ette aide\n");printf(" variable = expression\n");};expr : '(' expr ')' {$$ = $2;}| expr AND expr {$$ = $1 && $3;}| expr OR expr {$$ = $1 || $3;}| expr IMP expr {$$ = !$1 || $3;}| expr EQ expr {$$ = $1 == $3;}| expr XOR expr {$$ = $1 != $3;}| NOT expr {$$ = !$2;}| BOOL {$$ = $1;}| VAR {$$ = var[$1℄;};%%void yyerror( har *s) {fprintf(stderr,"%s\n",s);}int main(){/*yydebug=1;*/printf(invite);return yyparse();}make�le logi : logi .y logi .l# d'abord ya pour y.tab.h puis lex puis g �e ho debut $(YACC)- ompil : logi .y$(YACC) $(YACCFLAGS) logi .y�e ho debut $(LEX)- ompil : logi .l$(LEX) logi .l�e ho debut ompil ave edition de liens$(CC) -o logi y.tab. lex.yy. �# attention l'option -g (debug) fait planter�e ho fin ompil : vous pouvez exe uter logi Solution 13 ( f exer i e 13)1. Colle tion anonique (AFD) des ensemble d'items LR(0) de la grammaire augmentée (S → E) asso iée à GETF :I0 = Fermeture({S → .E}) = {S → .E,E → .E + T,E → .T, T → .T ∗ F, T → .F, F → .(E), F → .d}T = {(I0, E, I1)}I1 = Fermeture({E → E.+ T }) = {E → E.+ T, S → E.}T+ = {(I0, T, I2)}I2 = Fermeture({E → T.}) = {E → T., T → T. ∗ F}T+ = {(I0, F, I3)}I3 = Fermeture({T → F.}) = {T → F.}T+ = {(I0, (, I4)}I4 = Fermeture({F → (.E)}) = {F → (.E), E → .E + T,E → .T, T → .T ∗ F, T → .F, F → .(E), F → .d}T+ = {(I4, (, I4), (I4, d, I5), (I4, T, I2), (I0, d, I5)}I5 = Fermeture({F → d.}) = {F → d.}T+ = {(I1,+, I6)}I6 = Fermeture({E → E + .T }) = {E → E + .T, T → .T ∗ F, T → .F, F → .(E), F → .d}T+ = {(I6, F, I3), (I6, (, I4), (I6, d, I5), (I2, ∗, I7)}I7 = Fermeture({T → T ∗ .F}) = {T → T ∗ .F, F → .(E), F → .d}T+ = {(I7, (, I4), (I7, d, I5), (I4, E, I8)}I8 = Fermeture({F → (E.), E → E.+ T }) = {F → (E.), E → E.+ T }T+ = {(I8,+, I6), (I6, T, I9)}I9 = Fermeture({E → E + T., T → T. ∗ F}) = {E → E + T., T → T. ∗ F}T+ = {(I9, ∗, I7), (I7, F, I10)}I10 = Fermeture(T → T ∗ F.}) = {T → T ∗ F.}T+ = {(I8, ), I11)}I11 = Fermeture(F → (E).}) = {F → (E).} 35

2. Tables d'analyse A tion et Su esseur après avoir al ulé les TabSuivants des non terminaux : TabSuivants(E) ={+, $};TabSuivants(T ) = {∗,+, $};TabSuivants(F ) = {∗,+, $};A tion Su .d + * ( ) $ E T F0 S5 S4 1 2 31 S6 A epter2 R(E → T ) S7 R(E → T ) R(E → T )3 R(T → F ) R(T → F ) R(T → F ) R(T → F )4 S5 S4 8 2 35 R(F → d) R(F → d) R(F → d) R(F → d)6 S5 S4 9 37 S5 S4 108 S6 S119 R(E → E + T ) S7 R(E → E + T ) R(E → E + T )10 R(T → T ∗ F ) R(T → T ∗ F ) R(T → T ∗ F ) R(T → T ∗ F )11 R(F → (E)) R(F → (E)) R(F → (E)) R(F → (E))3. Analyse de l'expression (5+3)*2$.Pile Flot d'entrée A tion$0 (5+3)*2$ S4$0(4 5+3)*2$ S5$0(455 +3)*2$ R(F → d)$0(4F3 +3)*2$ R(T → F )$0(4T2 +3)*2$ R(E → T )$0(4E8 +3)*2$ S6$0(4E8+6 3)*2$ S5$0(4E8+635 )*2$ R(F → d)$0(4E8+6F3 )*2$ R(T → F )$0(4E8+6T9 )*2$ R(E → E + T )$0(4E8 )*2$ S11$0(4E8)11 *2$ R(F → (E))$0F3 *2$ R(T → F )$0T2 *2$ S7$0T2*7 2$ S5$0T2*725 $ R(F → d)$0T2*7F10 $ R(T → T ∗ F )$0T2 $ R(E → T )$0E1 $ A epter

36