Chapitre 2. Langages et automates - univ-reims.frmathinfo.univ-reims.fr/IMG/pdf/chap2.pdf · 2014-10-07 · Transformation d’un AFN vers un AFD équivalent Un AFD est équivalent

Langages et Compilation Chap. 2. Langages et automates

Chapitre 2. Langages et automates

1. Quelques définitions et description d’un langage.

2. Les expressions régulières.

3. Les automates fini déterministes et non-déterministes.

4. Construction automatique d’un analyseur lexical.

M. KRAJECKI 1 Licence Informatique


1. Alphabets, mots

Pour représenter un problème, nous devons définir un ensemble fini desymboles appelé alphabet (par la suite, noté

�).

Définition 1 (alphabet) Un alphabet est un ensemble fini de symbolesappelés caractères.

En fait, la seule caractéristique essentielle est sa taille, les caractères choisisne sont pas importants (construction d’une bijection entre les symboles).Exemple, alphabet de taille 3 : �� ; �� ; ��

Définition 2 (mot, longueur) Un mot est une séquence finie d’éléments(chaîne) issus d’un même alphabet. La longueur du mot � (notée � �� ) estdéfinie par le nombre de caractères composant ce mot. Le mot vide, noté � aune longueur égale à 0.

Exemple : �� , �� , �� sont des mots de l’alphabet �� .



2. Description d’un langage

Définition 3 (langage) Un langage est un ensemble de mots définis sur lemême alphabet.

Exemple : soit l’alphabet � � �� , l’ensemble des mots � �� est un langage sur cet alphabet.

Attention : le langage vide, noté�, est différent du langage �� .

Description d’un langage :– langage fini � énumération de tous les mots ;– langage infini � définition directe des langages simples + composition.



Description d’un langage

Définition 4 (Union de 2 langages) �� est le langage contenant tousles mots de �� et de �� :

�� ou ��

Définition 5 (Concaténation de 2 langages) �� est le langagecontenant tous les mots formés d’un mot de �� suivi d’un mot de �� :

�� et ��

Définition 6 (Fermeture itérative (ou de Kleene) de � ) La fermetureitérative est définie par l’ensemble des mots formés par une concaténationfinie des mots de �

�� "!�#%$ et ��&�'�(� ��)*�� tels que �� +�'�(� ��) �



Langages réguliers et expressions régulières

Définition 7 (Langages réguliers) L’ensemble�

des langages régulierssur un alphabet

�est le plus petit ensemble des langages satisfaisant les

conditions suivantes :

1.�

� ��

2. �� pour tout ��

3. si � �� alors � �� *�� et � � � � �

Les expressions régulières sont une notation qui indique commentl’ensemble régulier est construit à partir des ensembles réguliers

élémentaires.



Expressions régulières

Définition 8 (Expressions régulières) Les expressions régulières pour unalphabet

�sont les expressions formées par les règles suivantes :

1.�, � et les éléments de

�sont des expressions régulières

2. Si � et � sont des expressions régulières, alors � � �� , � �� et �� sontdes expressions régulières.

Le langage � �� représenté par l’expression régulière � est défini ainsi :

1. �� , ��

2. �� pour tout �� 3. �� 4. �� 5. ��



Expressions régulières : exemples

L’ensemble de tous les mots définis à partir d’un alphabet�� est dénoté par l’expression régulière� ��

. Cette expression est souvent abrégée en� �

.

L’ensemble de tous les mots non vides ( !� de " ) est noté� �� #�� , noté

�$� �ou�$%

.

� �&��'(��)' � �&��'(��définit l’ensemble des mots composés par

�et'

contenant au moins un'.



3. Les automates finis

Les automates finis sont très utilisés en informatique. Pour la compilation :recherche de chaîne de caractères dans un texte.

Abstraction d’un ordinateur, un ordinateur est composé de :– un processeur avec des registres (compteur de programme) ;– une mémoire pour stocker le programme ;– une mémoire pour les données.Exécution d’un programme :

1. Chargement de l’instruction indiquée par le compteur de programme.

2. Exécution de l’instruction � modification des registres et / ou de lamémoire de données.

3. Le compteur de programme est modifié.



Automate fini déterministe

Pour prévoir l’effet d’un cycle (l’exécution d’une instruction), il suffit de

connaître l’état de la mémoire + registres.

Un état est défini par le contenu de la mémoire et des registres del’ordinateur.

À chaque cycle, l’état de la machine est modifiée. La transformation de cetétat est une fonction (appelée fonction de transition) de l’ensemble des étatsde la machine vers elle-même.

Si, de plus, nous connaissons l’’état initial de la machine, nous pouvons endéduire l’exécution exacte de la machine.



Automate fini déterministe : définition informelle

Un automate fini déterministe se compose ainsi :– un ruban d’entrée sur lequel est placé le mot (les données) à traiter. Le

ruban est composé d’un ensemble de cases, chaque case contenant uncaractère. L’automate utilise une tête de lecture pour connaître le

caractère suivant.– Un ensemble d’états dont un état initial (état au début de l’exécution) et

des états d’acceptation qui définissent les mots acceptés par l’automate.

– Une fonction de transition qui indique pour chaque état et symbole lu, leprochain état de l’automate.



Automate fini déterministe : définition

Définition 9 (Automate fini déterministe) Un Automate Fini Déterministe(noté AFD) est défini formellement par un quintuplet

� � �� où :– � est un ensemble fini d’états ;–

�est un alphabet ;

– �� est la fonction de transition ;– �� est l’état initial (start) ;– �� est l’ensemble des états accepteurs.

Définition 10 (Configuration d’un AFD) Une configuration d’un AFD estune paire composée de l’état de l’automate plus la partie du mot restant àtraiter : �� .



Dérivation

Définition 11 (Dérivation) La configuration �� est dérivable en uneétape de �� par

�(noté �� ) si :

– � �! � � ( � �, est le premier caractère de � et � � est égal à � privé

de ).– � � �"�� ( � � est le prochain état déterminé par la fonction de transition

pour � et ).Une configuration est dérivable (en plusieurs cylces) d’une autre, si elle peutêtre obtenue par une séquence finie de dérivations en une étape : �� est dérivable par

�de �� (noté �� ) s’il existe !�# $ et des

configurations ��$#��%# �� $'&�()& ! telle que :– ��+* ��,* � �� – ��)��) �� – -.( �0/ $ � !1 � ��+# � �%# �� +#32 � ��,#42 � .



Exécution d’un automate

Donc, nous pouvons en déduire l’exécution d’un automate :

�� (�(� � �� où � est l’état initial et � le mot vide.

Il n’y a qu’une exécution possible pour chaque mot.Définition 12 (Acceptation) Un mot � est accepté si le dernier état de lamachine est un état accepteur :

� est accepté par�

si �� et �*� ��

Le langage accepté par�

(noté �� ) est défini par l’ensemble des motsacceptés par

�:

�� et �*� � � �



Représentation par un graphe

– À chaque état, on associe un nœud du graphe.– La relation de transition est représentée par des arcs valués : si� �� , il existe un arc entre les sommets � et �� .

– L’état initial est signalé par une flèche et les états accepteurs par desdoubles cercles.

�

��

��

�

Voici un automate :��

��

��

��

��

� � �� !�� Accepte tous les mots se terminant par�

:� �#" � �%$ � .



Simulation du comportement d’un AFD

SIMULATIONAFD �� 1 �� ( � ( � � $ {début du mot}2 while �� 3 do if � �� 4 then return � ��5 else if � �� est défini6 then �� 7 else return � ��8

�� ( � ( � � �� +( � ( �� {on a traité un symbole}9 if ��

10 then return �� (11 else return � ��



Les automates finis non déterministes

Les automates finis non déterministes sont des automates où lesconstructions suivantes sont autorisées :

– plusieurs transitions correspondent au même caractère (ousymbole) dans chaque état ;

– des transitions sur le mot vide sont autorisées ;– des transitions sur des mots de longueur supérieur à 1 sont

possibles (regroupement de transition).



Automate fini non déterministe

Définition 13 (Automate fini non déterministe) Un Automate Fini Nondéterministe (noté AFN) est défini formellement par un quintuplet� � �� où :– � est un ensemble fini d’états ;–


–�� est la relation de transition ;

– �� est l’état initial (start) ;– �� est l’ensemble des états accepteurs.

� nouvelle définition de la dérivation :�� est dérivable en une étape par

�de �� si :

– � � �� ;– �� (le triplet �� est un élément de la relation de transition).



Remarques sur les AFN

Un mot est accepté par un automate non détermnisite s’il existe unedérivation qui accepte ce mot. Nous laissons l’automate “choisir” labonne dérivation.

Le non déterminisme permet de construire facilement des automatesutilisant la disjonction et l’itération, mais ne reconnaît pas plus delangages que les automates déterministes.



Exemple d’un AFN

��

��

Les mots �� et �� sontacceptés par cet automate.

a � �

��

� ��

�

�



Simulation d’un AFN

Problème : il existe plusieurs dérivations pour un même mot !

1. Il faut vérifier si l’une d’entre elles permet d’accepter le mot.

2. Il faut être en mesure de revenir en arrière (backtrack).

�

� �

��

� � � � � �

0 1

3

2

0, aabb

1, abbéchec

0, abb

1, bb

2, b

3, �le mot est accepté

0, bbéchec

Utilisation de la récursivité.



Principe de la simulation d’un AFN

SIMULATIONAFN � � � � � � � 1 {on commence avec e=start et p=0}2 if �� 3 then return � � � � �4 else �� 5 if � états pour

� � � �� notés � *�� &�'�(� � � �6 then7 ( � $8 while � �� et ( � 9 do

10 �� SIMULATIONAFN � � � # �� 11 ( � ( � �12 return � � � � �



Construction d’un AFN qui reconnait le langage d’uneexpression regulière

La construction se fait sur la syntaxe de l’expression régulière.

� �

� � ��

��

� :� :

l’AFN de� � et celui de

��par

Soit� � et

��, 2 epxressions régulières, on représente par

� �� :

Remarque : on ajoute un arc étiqueté � depuis l’état accepteur de� � vers

l’état initial de��

.

�

��




Solution : on ajouteun nouvel état accepteur.

Pb : si " � � � "��

:

nouvelle étatd’acceptation

��

�

� �

� �

��

�

�

�

�� " �� :




��

�

�

��

�

�

�

��

Exemple :� �#" � � $��

� $ :

{ permet d’accepter le mot vide }



Transformation d’un AFN vers un AFD équivalent

Un AFD est équivalent à un AFN s’il accepte le même langage.

�� 1)

�

�

� �

�

��

� �

��

� ��

2) On simule "en parallèle" les 2 états possibles pour une transition de � � sur � .



� -closure

Définition 14 �� . Soit � � � un ensemble d’états d’un AFN�

.L’ � -closure(A) est alors défini par l’ensemble des états de

�accessibles

depuis tout état � � � par des � -transitions uniquement.

Remarque : � � �� .Il est donc possible, en utilisant cette définition, de construire

automatiquement un AFD équivalent à un AFN donné. À partir de l’ � -closurede l’état initial (qui correspondra à l’état initial de l’AFD), on construit deproche en proche (en suivant les transitions de l’AFN) les états de l’AFD

correspondant.



Algorithme de transformation AFN vers AFD

AFNVERSAFD � 1 �$* � �� {s est l’état initial de M}2 � � � �� * � � ��

� �MARQUE �� * � � � � � �

3 while � � �� tel que � MARQUE � 4 do MARQUE � � � � � �5 for - � � �6 do

� � �� 7 � � �� 8 if � �� 9 then � � � � � ��

10 MARQUE �� 11 � � �� 12 � � � ��



Exemple

Exemple :� �#" � � $��

E est le seul état accepteur caril contient l’état 10 de l’AFN.

0 1

3

5

6 7 8 9 10

4

2�

��

�

�

�

��

A

DB

C E

�

�

��

��

�

� ��



Exécution de l’algorithme

x M(x) T y �A={0,1,2,4,7} V A

� {3,8} {3,8,6,1,7,2,4} A

� B

B={3,8,6,1,7,2,4} F V A�

{5} {5,6,7,1,2,4} A�

C

C={1,2,4,5,6,7} F V B�

{3,8} B�

B

B�

{5,9} {5,9,6,7,1,2,4} B�

D

D={1,2,4,5,6,7,9} F V C�

{3,8} C�

B

C�

{5} C�

C

D�

{3, 8} D�

B

D�

{5, 10} {5,6,1,2,4,7,10} D�

E

E={1,2,4,5,6,7,10} F V E�

{3, 8} E�

B

E�

{5} E�

C



Partitionnement

Soient � et � deux états de � et � une partition de � . � et � sont équivalentsdans � si et seulement si pour tout symbole � � �

, les états � et � ont destransitions vers des états appartenant au même bloc de � .

Définition 15 Équivalence entre deux états. Soit � � � � � �&�(�(� ��) � unepartition, c’est à dire :– -.(��#�� ;– -.(��# ��

et -.(� � ��( �� #��

;– � )#� � ��# � � .Les états � et � sont équivalent dans � ( �� ) si et seulement si :

- �� et � � � � �

Le but du partitionnement est de réduire le nombre d’états d’un AFD.



Algorithme de minimisation des états

MINIMISATION � 1 �� 2 while � � �� 3 do � � ��

4 for - � � �5 do � positionner B en sous bloc B’ tel que 2 états s et t de B sont �6 � dans le même bloc s’ils sont équivalents pour � �7 while � �� 8 do � � �� 9 while � � � � � � �$� �'�

10 do � � �� 11 if � ��

12 then � � �� 13 � � � �



Exemple (suite)

��

� � � � ��

� ��

� �On doit sortir à cause de la transition sur � . Donc :

� � ��

� � � � ��

� ��



Exemple (suite)

On doit sortir � (transition sur � ). On en déduit :

� � ��

� � � � � ��

� �Donc � et � sont équivalents.

�

� ��

�

��

�

�

�

��

�



4. Construction automatique d’un analyseur lexical

L’analyseur lexical est la première composante de la phase d’analysenécessaire à un compilateur.

Le rôle de l’analyseur lexical (AL) :– AL lit les caractères en entrée (le prog. source) et reconnait des lexèmes.– Le résultat de l’AL est une suite de lexèmes qui propose une première

structuration du programme.– Il existe une interaction très forte entre l’AL et l’analyseur syntaxique.

Analyseursyntaxique

Table dessymboles

lexème

obtenir un

programme

source

lexème

Analyseurlexical



Construction automatique de l’AL à l’aide d’automates

L’analyse lexicale permet :

1. Une simplification de la phase d’analyse.

2. Efficacité du compilateur accrue.

3. Portabilité du compilateur.

Objectifs : construire un AL qui accepte

unités lexicales notées� � � ��&�(�(� � � � � � .

1. Représenter chaque unité lexicale par une expression régulière.

2. Construire un AFN pour chaque expression régulière.

3. Transformer chaque AFN en AFD (optimisation).

4. Réduire le nombre d’états des AFD (optimisation).




ANALYSEURLEXICAL 1 � on essaie � � � � �2 if

� !3 then return � � � �4 else � on essaie � � � � �5 if

� !6 then return � � � �+�(�(�7 else � on essaie � � � � �8 if

��

9 then return � � � �




En pratique, on cherche à reconnaître le lexème le plus grand (qui comportele plus grand nombre de caractères).

Attention :

1. Un lexème est différent d’une unité lexicale : une unité lexicale définit un

langage régulier représenté par une expression régulière ; un lexèmeest un mot de ce langage.

2. L’ordre de définition des unités lexicales est important : si 2 unitéslexicales peuvent être choisies pour un même lexème, c’est l’unitélexicale définie le plus tôt qui est choisie.



5. Limite des expressions régulières et automates à pile

On ne peut pas définir tous les langages à l’aide d’expressions régulières.

Exemple : L = { � � �� # $ } ne peut être défini par une expressionrégulière. Preuve : voir TD.

Un automate à pile non déterministe est composé des mêmes élémentsqu’un AFN :– un ruban d’entrée et une tête de lecture ;– un ensemble d’états dont on distingue un état initial et un ensemble

d’états d’acceptation ;– une relation de transition.On ajoute à ces composantes, une pile de capacité infinie initialement vide.

À chaque étape du calcul, l’automate à pile consulte le sommet de la pile etla remplace par une autre suite de symboles.



Automate fini non déterministe à pile

Définition 16 Un Automate fini non déterministe à pile est défini par :

� �� Où :– � est un ensemble fini d’états ;–


–�

est l’aphabet de la pile ;–�

est la relation de transition :� � �� ;

– � est le symbole initial de la pile ;– � est l’état initial ;– � est l’ensemble des états d’acceptations.



Configuration et dérivation d’un automate à pile

Remarque :� �� &�� ) � ��&� ��

signifie que :– l’automate passe de l’état

�à l’état

sur le mot

�si la chaîne

�est

au sommet de la pile ;– à l’état

, le sommet de la pile

�a été remplacé par

�.



Configuration et dérivation d’un automate à pile

Définition 17 Configuration et dérivation. Une configuration d’un automateà pile est définie par un triplet ( état, mot en entrée, contenu de la pile) :�� .

La configuration �� est dérivable en une étape de �� par�

( �� ) si :– � � �� (le mot � commence par le préfixe � ) ;

– � � �� (avant la transition, le sommet de la pile contient � � � � ) ;– � � � � � (après la transition, � est enlevé du sommet de la pile et il est

remplacé par � ) ;

– ��



Exécution d’un automate à pile

Une configuration � � est dérivable en plusieurs étapes de la configuration �par

�( � � �� ) s’il existe ! # $ et des configurations intermédiaires

� *�� (�'� � ��) telles que :– � � � * ;

– � � � ��) ;– � # � � � #42�� pour $'&�()&%! .

Une exécution d’un automate à pile sur un mot � est une suite deconfigurations :

�� (�'� � ��

( � est l’état initial et � , le symbole initial au sommet de la pile).



Acceptation d’un mot par un automate à pile

Un mot � est accepté par un automate à pile� � �� si (

acceptation sur état final) :

�� avec� � ��

Ou bien (acceptation sur pile vide) :�

accepte � s’il existe une exécutionsur � menant à une configuration où la pile est vide :

��

Les deux définitions sont équivalentes (i.e. les automates reconnaissent les

mêmes langages).



Exemple

Définition de�

, l’automate à pile qui reconnaît � � �� # $�� sur pile

vide.� � �� * ��+� �� * �� $* � � � �� $* � � � �� * �� (on empile le symbole � )

��$* � � � � ��+� � � (on dépile)

�� +� � � (on dépile)

Exécution pour �� :��$* � �� * �� $* �� $* � �� +� �� +� �� +� �� est accepté.


Documents

Chapitre 2. Langages et automates - univ-reims.frmathinfo.univ-reims.fr/IMG/pdf/chap2.pdf · 2014-10-07 · Transformation d’un AFN vers un AFD équivalent Un AFD est équivalent