Slides Cours1

Principe d’Interprétation des Langages
Christine Paulin
Christine.Paulin@universite-paris-saclay.fr
Département Informatique, Faculté des Sciences d’Orsay, Université Paris-Saclay
Licence Informatique - 2ème année
2023–24
C. Paulin (Université Paris-Saclay) PIL 2023–24 1 / 303

1–Introduction
1 Motivations
2 Organisation du cours
3 Etapes de l’interprétation
4 Langages formels

Interprétation des langages
modélisation
algorithmique
données
calcul
S’il vous plait,

dessine-moi
un mouton!

Référence
Le petit prince d’Antoine de Saint Exupery

Langages de programmation
Intermédiaires entre l’humain et la machine

exprimer (le plus fidèlement possible) ce que l’humain “souhaite”
être “compris” de manière mécanisée par la machine
Faciliter la programmation
détecter des erreurs
organiser et factoriser les traitements
réutiliser du code (bibliothèques)
effectuer la maintenance et les évolutions
Faciliter le déploiement sur des architectures variées

Du code source au résultat de l’exécution
Transformations successives à partir du code source

Plusieurs langages intermédiaires
Préservation du “sens” du programme (sémantique)
Chaque étape réalise une tâche particulière

Compilateur/Interpréteur
Objectif : produire à partir du programme source et des entrées le

résultat attendu
Des programmes qui prennent en argument et manipulent d’autres
programmes
Compilateur : le compilateur transforme le programme source en un code
binaire que la machine exécute sur différentes entrées
Interpréteur : l’interpréteur est un programme général qui s’exécute sur la
machine, il prend en argument le programme et l’entrée et calcule le
résultat
Méthodes mixtes ( Ocaml, java, python. . .) : le compilateur engendre un
code intermédiaire qui est interprété (machine virtuelle)

Problématique
Nombreuses questions d’efficacité :

efficacité des transformations
efficacité de l’exécution
Résultats théoriques
langages formels (reconnaissance)
sémantique des langages de programmation (typage, modèle d’exécution)
optimisation de programmes
(adaptation à la machine cible, allocation de la mémoire, organisation des
calculs)

1–Introduction
1 Motivations
Analyse lexicale
Analyse syntaxique
Arbre de syntaxe abstraite
Analyse sémantique et évaluation
4 Langages formels
Vocabulaire
Opérations sur les mots
Opérations sur les langages

Objectifs du cours
Etre de meilleurs programmeurs :

mieux comprendre le point de vue de l’ordinateur
mieux appréhender différents langages de programmation
S’initier à la théorie des langages formels
(langages réguliers, langages algébriques) à suivre en L3
Connaître de nouveaux paradigmes de programmation : expressions
régulières, grammaires
Comprendre les rudiments de la sémantique des langages de
programmation

Eléments pratiques
Site
https://ecampus.paris-saclay.fr/course/view.php?id=122122
TD/TP
8 séances de TD, 3 séances de TP
dernière séance : TP noté (a priori le 23 avril)
Evaluation
partiel (semaine du 27 février ou du 5 mars) : 30%
TP(s) et tests notés : 10%
examen final : 60%
Une feuille A4 (recto-verso) manuscrite autorisée au partiel et à l’examen

Plan du cours
1 Introduction à l’interprétation des langages

2 Analyse lexicale : langages réguliers, expressions régulières, automates
finis, outils d’analyse lexicale
3 Analyse syntaxique : grammaires et langages algébriques, analyse
descendante, outils d’analyse syntaxique
4 Analyse sémantique et exécution : portée, typage et évaluation

1–Introduction
1 Motivations
Analyse lexicale
Analyse syntaxique
4 Langages formels
Vocabulaire

Etapes
programme transformations
source
arbre(s)
suite
suite de arbre de de
d’unités résultat
caractères dérivation syntaxe
lexicales
abstraite
analyse analyse analyse exécution

lexicale syntaxique sémantique
Statique Dynamique

Exemple : mini-python (source J.-C. Filliâtre)
Un fichier mini-Python a la structure suivante :

# dé f i n i t i o n ( s ) de f o n c t i o n s
def f i b a u x ( a , b , k ) :
i f k == 0 :
return a
else :
r e t u r n f i b a u x ( b , a+b , k −1)
def f i b ( n ) :
return f i b a u x (0 , 1 , n )
# une ou p l u s i e u r s i n s t r u c t i o n s
p r i n t ( " quelques v a l e u r s : " )
f o r n i n [ 0 , 1 , 11 , 4 2 ] :
print ( f i b (n ) )

Spécification mini-python
Un fichier mini-Python est composé d’une liste optionnelle de déclarations de
fonctions, suivie d’une liste d’instructions.
Les instructions sont :
l’affectation simple (x = e) ou dans un tableau t[e1 ] = e2 ,
la conditionnelle (if/else),
la boucle (for/in),
l’affichage d’une expression avec print,
le renvoi d’une valeur avec return
ou l’évaluation d’une expression.
Les expressions sont :
une constante (booléen, entier ou chaîne de caractères),
l’accès à une variable,
la construction d’une liste (notation [e1 , e2 , . . . , en ]),
l’accès à un élément de liste (notation e[i]),
l’appel d’une fonction (notation f (e1 , . . . , en )),
une des opérations arithmétiques +, -, * ou //, un opérateur de
comparaison ==, !=, <, <=, >, >= ou un opérateur booléen and, or et not
associé à une ou deux expressions (notations unop e et e1 binop e2 ).

Spécification de langages de programmation
On pourra regarder quelques sites donnant les spécifications complètes de

langages de programmation.
On remarquera la complexité d’une définition précise même des objets les
plus simples (identifiants, chaînes de caractères etc...)
Java :
lexical : https://docs.oracle.com/javase/specs/jls/se19/html/jls-3.html
expression :
https://docs.oracle.com/javase/specs/jls/se19/html/jls-15.html
Python :
lexical : https://docs.python.org/fr/3/reference/lexical_analysis.html
expressions : https://docs.python.org/fr/3/reference/expressions.html
Ocaml :
lexical : https://v2.ocaml.org/releases/5.0/htmlman/lex.html
expressions : https://v2.ocaml.org/releases/5.0/htmlman/expr.html

Analyse lexicale
Rôle
Transformer le programme source vu comme une suite de caractères, en
une suite d’objets (appelés unités lexicales, ou lexèmes ou token)
significatifs pour le calcul :
constantes numériques ou textuelles : entiers, flottants, chaînes de
caractères (hello versus "hello")
identifiants (noms donnés à des objets particuliers)
mots clés (suite de caractères participant à la structure du programme, ou
représentant des opérations particulières non utilisables comme identifiant)
symboles spéciaux (opérations numériques, crochets, séparateurs de
liste. . .)
Agréger dans une même catégorie les éléments de même nature d’un
point de vue syntaxique (identifiant, nombre) en gardant la valeur en
réserve pour le reste du calcul.
Supprimer les éléments inutiles au calcul
espaces non significatifs (mais servent à séparer les unités lexicales +=
versus + =)
commentaires

Analyse lexicale
Erreurs détectées
suite de caractères ne correspondant à aucune unité lexicale :
caractère non accepté dans un identifiant,
chaîne de caractère non fermée,
symbole inconnu. . .
Outils
Les unités lexicales sont décrites par des expressions régulières
L’analyse du texte se fait en utilisant des automates finis (associés à des
actions de calcul à chaque étape de reconnaissance)

Unités lexicales : exemple mini-python
Unités lexicales :
en nombre fini, possiblement associées à des valeurs (identifiant, constante)
l’unité lexicale est différente de la chaîne de caractère associé, mais on
utilisera des notations similaires pour faciliter la lecture (en utilisant des
fontes spéciales ou des quotes pour éviter les confusions)
Exemple mini-python
commentaire : commence par le symbole # et se termine au retour à la ligne
mots-clés : def if else return print for in and or not
opérations arithmétiques (avec quotes) : ’+’ ’-’ ’*’ ’//’ ’%’
comparaisons : CMP (une seule unité, associée à l’opérateur de
comparaison)
symboles associés à l’indentation BEG END NL EOF
autres symboles spéciaux (avec quotes) :
’(’ ’)’ ’[’ ’]’ ’,’ ’=’ ’:’
constantes : CST (associé à une valeur entière, flottante ou chaîne de
caractères)
identifiants : ID associé à une représentation de l’identifiant (par exemple
chaîne)

Résultat
NL
# dé f i n i t i o n s de f o n c t i o n s def ID ’(’ ID ’,’ ID ’,’ ID ’)’ ’:’ NL
def f i b a u x ( a , b , k ) : BEG if ID CMP CST ’:’ NL
i f k == 0 : BEG return ID NL
return a END else ’:’ NL
else :
BEG return ID ’(’ ID ’,’ ID ’+’ ID ’,’ ID ’-’ CST ’)’ NL
r e t u r n f i b a u x ( b , a+b , k −1)
def f i b ( n ) : END END def ID ’(’ ID ’)’ ’:’ NL

return f i b a u x (0 , 1 , n ) BEG return ID ’(’ CST ’,’ CST ’,’ ID ’)’ NL
# une ou p l u s i e u r s i n s t r u c t i o n s
p r i n t ( " quelques v a l e u r s : " ) END PRINT ’(’ CST ’)’ NL
f o r n i n [ 0 , 1 , 11 , 4 2 ] : for ID in ’[’ CST ’,’ CST ’,’ CST ’,’ CST ’]’ ’:’ NL
print ( f i b (n ) ) BEG PRINT ’(’ ID ’(’ ID ’)’ ’)’ NL
END NL EOF

Analyse syntaxique
Rôle
Analogie : l’analyse lexicale a transformé la suite de caractères en une
suite de mots, l’analyse syntaxique construit à partir de la suite de mots,
des phrases auxquelles il va être possible de donner un sens.
Expliciter la structure du programme
expressions à calculer
enchaînement des instructions (conditionnelles, boucles)
déclarations et utilisation de fonctions
Lever les ambigüités (choix)
Transformer la suite d’unités lexicales en un arbre qui reflète la structure
logique du programme
Erreurs détectées
suite d’unités lexicales ne correspondant pas à une construction de
programme correcte
Outils
La structure du programme est décrite par une grammaire
L’analyse du texte se fait en utilisant des automates à pile ou des
fonctions d’analyse ad-hoc
Analyse syntaxique : exemple
Expliciter la structure d’un programme correct, pour mini-python :

zéro, une ou plusieurs définitions de fonctions
une définition de fonction est formée ainsi (en séquence)
mot-clé def,
nom de la fonction (identifiant),
parenthèse ouvrante ’(’,
suite de zéro, un ou plusieurs paramètres (identifiants) séparés par des virgules,
parenthèse fermante ’)’,
symbole ’:’,
une “suite d’instructions” qui va être soit une instruction élémentaire suivie d’un
retour à la ligne (NL) soit un retour à la ligne suivi d’un bloc d’instructions
indenté, c’est-à-dire entre un BEG et un END.
au moins une instruction

Analyse syntaxique : instruction et expression
instruction élémentaire
instructions print/return
affectation (variable ou tableau)
expression
instruction générale
instruction élémentaire suivie d’un retour à la ligne
conditionnelle (avec ou sans else) :
mot clé if suivi d’une expression, suivi du symbole ’:’ suivi d’une suite
d’instructions
suivi optionnellement du mot clé else suivi du symbole ’:’ suivi d’une suite
d’instructions
boucle for : mot clé for suivi d’un identifiant, suivi du mot clé in suivi d’une
expression suivi du symbole ’:’ suivi d’une suite d’instructions
expressions
constantes, identifiants, accès tableau
opérateur unaire suivi d’une expression
opérateur binaire entre deux expressions
appel de fonction
liste d’expressions (entre crochets carrés)
expression parenthésée
Grammaire associée
Décrire les suites d’unités lexicales qui correspondent à un programme

bien formé
Introduire des entités intermédiaires (symboles) pour décrire différentes
catégories syntaxiques (choix libre)
entités principales : prog, deffun, instr, expr,
entités auxiliaires :
unop, binop : opérateurs unaires (not, ’-’) et opérateurs binaires
linstr : liste d’instructions (juxtaposition)
simpleinstr : instruction élémentaire
suiteinstr : instruction élémentaire suivie d’un retour à la ligne ou suite
d’instructions dans un bloc
lident : liste possiblement vide d’identifiants séparés par des virgules
lexpr : liste possiblement vide d’expressions séparées par des virgules

Grammaire associée
Décrire par des règles (récursives) comment les entités sont construites
à partir des unités lexicales
deffun ::= def ID ’(’ lident ’)’ ’:’ suiteinstr
Il y a en général plusieurs règles pour la même entité
expr ::= ID
expr ::= CST
expr ::= unop expr
expr ::= expr binop expr
expr ::= ’(’ expr ’)’
expr ::= ID ’(’ lexpr ’)’
expr ::= expr ’[’ expr ’]’
expr ::= ’[’ lexpr ’]’
...
On utilise une notation générale pour couvrir l’ensemble des cas en les
séparant par des barres verticales
expr ::= ID | CST | unop expr | expr binop expr | ’(’ expr ’)’
| ID ’(’ lexpr ’)’ | expr ’[’ expr ’]’ | ’[’ lexpr ’]’

Résultat
La suite d’unités lexicales est acceptée comme une entité valide si on peut
construire un arbre de dérivation dont la racine est le nom de l’entité, dont
chaque nœud interne correspond à une règle et dont les feuilles lues de
gauche à droite correspondent à la suite d’unités lexicales.
On considère juste une instruction et la suite d’unités lexicales associées

f o r n i n [ 0 , 1 , 11 , 4 2 ] : for ID in ’[’ CST ’,’ CST ’,’ CST ’,’ CST ’]’ ’:’ NL
print ( fib (n)) BEG print ’(’ ID ’(’ ID ’)’ ’)’ NL END
Les règles supplémentaires utiles concernant les instructions sont

instr ::= for ID in expr ’:’ suiteinstr
suiteinstr ::= simplinstr NL | NL BEG linstr END
simplinstr ::= print ’(’ expr ’)’

Arbre de dérivation
for ID in ’[’ CST ’,’ CST ’,’ CST ’,’ CST ’]’ ’:’ NL BEG print ’(’ ID ’(’ ID ’)’ ’)’ NL END
instr
for ID in expr ’:’ suiteinstr
’[’ lexpr ’]’ NL BEG linstr END
CST ’,’ CST ’,’ CST ’,’ CST instr
simpleinstr
print ’(’ expr ’)’
ID ’(’ expr ’)’
ID

Ambigüité syntaxique
Certaines suites d’unités lexicales peuvent s’interpréter syntaxiquement
de plusieurs manières
Le choix de l’interprétation peut avoir une incidence sur le calcul
Exemple : CST ’+’ CST ’*’ CST conduit à deux arbres de dérivation
différents :
expr expr
expr binop expr expr binop expr
CST ’+’ expr binop expr expr binop expr ’*’ CST
CST ’*’ CST CST ’+’ CST

Le langage précise (en général) l’interprétation retenue
Modification de la grammaire ou indication de précédence (priorité entre
les opérateurs)

Les choix lexicaux des langages de programmation
1 Que se passerait-il si on autorisait un caractère comme ’-’ ou encore

un espace à apparaître dans un identificateur ?
2 Pourquoi les “mots” qui apparaissent dans un programme ne peuvent-ils
pas faire partie d’un dictionnaire comme celui de la langue française ?
3 Comment l’analyseur interprète-t-il la suite de caractères ifelse ?
Pourquoi ?
4 On dit souvent que les espaces sont non significatifs, qu’est-ce que cela
signifie et quel est leur rôle ? Est-ce vrai dans tous les langages ?
5 Pourquoi traiter les mots-clés différemment des autres identifiants ?
6 On a une seule unité lexicale pour les symboles de comparaison mais
des unités différentes pour les symboles arithmétiques, qu’est-ce qui
peut expliquer cette différence de traitement ?

L’arbre de dérivation contient des informations sur la manière dont le

programme a été analysé syntaxiquement
justifie que le programme respecte la syntaxe du langage
mais informations pas toujours pertinentes pour le sens, puis le calcul.
En pratique on se sert de la dérivation pour reconstruire un arbre plus
abstrait qui se concentre sur la structure logique du programme
Chaque noeud de l’arbre correspond à une construction du programme
Utilisation de listes natives (ou autre construction) du langage de
modélisation
Intégration des valeurs des unités lexicales (identifiants, constantes,
opérateurs. . .)

Arbre de syntaxe abstraite : exemple
for ID in ’[’ CST ’,’ CST ’,’ CST ’,’ CST ’]’ ’:’ NL BEG print ’(’ ID ’(’ ID ’)’ ’)’ NL END
Sfor
ID("n") Elist Sprint
[CST(0),CST(1),CST(11),CST(42)] Ecall
ID("fib") ID("n")

Analyse sémantique
Analyse de portée : faire le lien entre l’utilisation d’un identifiant et sa

“définition”
déclaration de variable, paramètre
appel à des fonctions externes
Repérer des erreurs liées au typage (opérations appliquées à des objets
de nature incompatible)
Désambigüer des opérations en tenant compte du type des arguments
(surcharge)
Cette étape achève la partie d’analyse du programme, son sens est explicité,
on a rejeté tous les programmes “mal écrits”.
On démarre alors une partie synthèse qui transforme le programme en vue
de calculer efficacement le résultat.

Transformations et exécution
Les compilateurs passent par différents langages intermédiaires pour

aboutir à du code assembleur et du code binaire
un enjeu important est le positionnement des données et valeurs
intermédiaires dans la mémoire (registres, pile, tas. . .)
un autre enjeu est le choix des séquences d’instruction et la détection
d’optimisations
il y a une phase d’édition de liens pour associer différents codes compilés
le programme final s’exécute dans un environnement qui peut contenir
d’autres processus comme le Garbage collector (Ramasse-miettes ou
Glaneur de Cellules (GC) en français) qui se charge de libérer la mémoire
non utilisée
On peut transformer le code vers un code de machine virtuelle, souvent
une machine à pile, qui peut ensuite être interprété simplement.
L’interpréteur est un programme (écrit dans le langage de notre choix) qui
prend en argument la syntaxe abstraite du programme et de son entrée,
qui analyse la structure du programme et de l’entrée et calcule le résultat
attendu en respectant la sémantique du programme.

A savoir
Les différentes étapes de l’interprétation d’un langage

Le positionnement des erreurs en fonction des langages par rapport à
ses étapes
Comprendre la description d’une unité lexicale et celle d’une règle de
syntaxe (comme on les trouve dans les manuels de description des
langages)

1–Introduction
1 Motivations
Analyse lexicale
Analyse syntaxique
4 Langages formels
Vocabulaire

Introduction
La première phase de l’interprétation du langage traduit la suite de

caractères en un arbre de syntaxe abstraite qui va correspondre à un
calcul exécutable par un ordinateur
Pour faire correspondre ce que veut l’utilisateur et ce qu’exécute
l’ordinateur, il faut des règles claires de construction du programme
La phase d’analyse doit être rapide (algorithmes efficaces)
La théorie des langages formels est une abstraction de cette
problématique
description synthétique des langages
algorithmes pour reconnaître l’appartenance au langage considéré

Vocabulaire
Alphabet : ensemble (fini) des caractères possibles

analyse lexicale : l’alphabet est l’ensemble des caractères usuels (ascii,
unicode. . .)
analyse syntaxique : l’alphabet est l’ensemble des unités lexicales
Mot : suite finie de caractères de l’alphabet (notée par juxtaposition des
caractères)
analyse lexicale : la suite de caractères correspondant à l’unité lexicale
analyse syntaxique : la suite d’unités lexicales correspondant à la
construction de programme
Le nombre de caractères dans un mot s’appelle la longueur du mot
Il existe un mot sans aucun caractère (longueur 0), appelé mot vide et
noté ε (epsilon).
Tout caractère peut être vu comme un mot de longueur 1
Le langage Ocaml différencie le caractère ’a’ du mot formé d’un seul
caractère ”a” mais ce n’est pas le cas de python.

Langage
Un langage est défini comme n’importe quel ensemble de mots.

Un langage peut être vide, fini ou infini
Un langage est un ensemble dénombrable : union dénombrable
d’ensembles finis (les mots de longueur n sur un alphabet fini)
En interprétation des langages :
analyse lexicale : chaque unité lexicale correspond à un langage
(ensemble des identifiants, ensemble des constantes numériques, . . .)
analyse syntaxique : l’ensemble des programmes syntaxiquement bien
formés est vu comme un langage dont l’alphabet est formé des différentes
unités lexicales.

Exemples
On prend un alphabet avec deux caractères {a, b}.

a, b, aa, ab, bb, ba, bbbabbabb sont des mots sur cet alphabet
{aa, ab, bb, ba} est un langage (fini) que l’on peut caractériser comme
l’ensemble des mots de longueur 2 sur cet alphabet.
L’ensemble des mots de longueur inférieure ou égale à 2 sur cet alphabet
se compose de 7 mots {ε, a, b, aa, ab, bb, ba} .
L’ensemble des mots ne contenant que le caractère a est un langage
(infini) : {ε, a, aa, aaa, . . .}.
L’ensemble des mots qui contient autant de a que de b est un langage
(infini).
L’ensemble vide (∅) est un langage qui ne contient aucun mot, il se
distingue de l’ensemble {ε} qui contient exactement un mot (le mot vide)

Représentation des mots
Soit A un alphabet (ensemble fini) dont les éléments sont des caractères
un mot est une suite finie de caractères
un mot peut se modéliser par un entier naturel n ∈ N qui est la longueur du
mot et une application de [1 . . . n] dans A qui associe à un entier k tel que
1 ≤ k ≤ n la k -ème lettre du mot
d’un point de vue informatique, un mot est un tableau de caractères (mais
indicé à partir de 1)
si w est un mot, on note |w| la longueur du mot et pour k tel que
1 ≤ k ≤ |w|, on note w[k ] la k -ème lettre du mot w.
le mot aabb est de longueur 4, on a aabb[1] = aabb[2] = a et
aabb[3] = aabb[4] = b
si on se donne n caractères a1 , . . . , an ∈ A alors on peut former un mot de
longueur n tel que la k -ème lettre de ce mot est ak . On note cette suite
comme une juxtaposition des caractères qui la composent : a1 . . . an .
On utilisera si nécessaire des espaces pour séparer les caractères entre
eux.

sous-mot : w est un sous-mot de m si w peut s’obtenir en effaçant des

lettres de m.
On a donc |w| ≤ |m| et il existe une application f strictement croissante
de [1 . . . |w|] dans [1 . . . |m|] telle que |w|[k ] = |m|[f (k )] pour tout
k ∈ [1 . . . |w|], on a donc w = m[f (1)]m[f (2)] . . . m[f (|w|)]
Soit le mot abab, les mots ε, a, b, aa, ab, bb, ba, aab, abb, aba, bab, abab
sont des sous-mots de abab. Par contre les mots bba, aabb ne sont pas des
sous-mots.
miroir : l’opération miroir consiste à réarranger les caractères du mot de
droite à gauche. Le mot miroir de w est un mot de même longueur, il est
noté w R et pour tout k ∈ [1 . . . |w|], on a w R [k ] = w[|w| − k + 1]
le mot miroir de abab est le mot baba
appliquer deux fois l’opération miroir revient au mot d’origine : le mot miroir
du mot miroir de w est le mot w
un mot qui est égal à son mot miroir s’appele un palindrome

Opérations sur les mots : concaténation
Les mots se mettent bout à bout pour former de nouveaux mots.

concaténation : Si w1 et w2 sont deux mots, on forme un nouveau mot
correspondant à la concaténation de w1 et w2 et noté par simple
juxtaposition w1 w2 . On a |w1 w2 | = |w1 | + |w2 | et pour tout
k ∈ [1 . . . |w1 | + |w2 |] on a (w1 w2 )[k ] = w1 [k ] si k ≤ |w1 | et
(w1 w2 )[k ] = w2 [k − |w1 |] si |w1 | < k ≤ |w2 | .
La concaténation des mots ab et abba est le mot ababba.
l’absence de signe pour noter la concaténation peut se rapprocher de
l’usage de ne pas noter la multiplication (2x + yz).
On utilisera parfois une notation avec un point w1 · w2
Dans les langages de programmation, la concaténation de chaînes de
caractères utilise un symbole spécifique (+ en python ou Java, ˆ en
Ocaml. . .)
l’opération de concaténation est associative (w1 w2 )w3 = w1 (w2 w3 ),
son élément neutre est le mot vide wε = εw = w,
elle n’est pas commutative (ab ̸= ba)

Opérations sur les mots (préfixe, suffixe)
préfixe : le mot u est un préfixe du mot w si et seulement si il existe un

mot v tel que w = uv (le mot u est un début de w)
le mot ab est un préfixe du mot abba mais n’est pas un préfixe du mot aabb
le mot vide ε est un préfixe de n’importe quel mot
suffixe : le mot u est un suffixe du mot w si et seulement si il existe un
mot v tel que w = vu (le mot u est une fin de w)
le mot ba est un suffixe du mot abba mais n’est pas un préfixe du mot aabb
le mot vide ε est un suffixe de n’importe quel mot

Opérations sur les mots (puissance)
Étant donné un mot w, on peut itérer l’opération de concaténation un nombre

quelconque de fois, cela amène à définir une opération de puissance qui
étant donné un entier n ∈ N renvoie un mot qui correspond à n copies du mot
w qui est noté w n .
la puissance 0 d’un mot est définie comme le mot vide
le mot w à la puissance n + 1 est défini récursivement comme la
concaténation du mot w à la puissance n et du mot w.
On a donc
w0 = ε w n+1 = w n w
On vérifie que la puissance 1 d’un mot est le mot lui-même : w 1 = w

Exemples
(ba)2 = baba (ba)3 = bababa

Opérations ensemblistes sur les langages
Les langages sont des ensembles de mots finis ou infinis qui peuvent se
combiner pour former de nouveaux langages.
Les constructions usuelles d’ensembles s’appliquent aux langages.
union : w ∈ (L1 ∪ L2 ) ssi w ∈ L1 ou w ∈ L2
intersection : w ∈ (L1 ∩ L2 ) ssi w ∈ L1 et w ∈ L2
différence : w ∈ (L1 \L2 ) ssi w ∈ L1 et w ̸∈ L2
complémentaire : w ∈ ∁L1 ssi w ̸∈ L1

Exemples d’opérations ensemblistes
sur l’alphabet {a, b}

L’union de l’ensemble des mots qui commencent par un a et de
l’ensemble des mots qui commencent par un b est l’ensemble des mots
non vides.
L’intersection de l’ensemble des mots qui commencent par un a et de
l’ensemble des mots qui commencent par un b est l’ensemble vide.
Le complémentaire de l’ensemble des mots qui commencent par un a est
formé du mot vide et de l’ensemble des mots qui commencent par b.

Opérations sur les langages : concaténation
La concaténation de deux langages L1 et L2 s’obtient en prenant tous les

mots formés par concaténation d’un mot w1 ∈ L1 et d’un mot w2 ∈ L2 .
w ∈ (L1 L2 ) ssi il existe w1 ∈ L1 et w2 ∈ L2 tels que w = w1 w2
Si L1 est l’ensemble des mots qui commencent par un a et L2 l’ensemble

des mots qui commencent par un b alors L1 L2 est l’ensemble de tous les
mots qui commencent par un a et contiennent au moins un b.
On pourra utiliser le point de manière équivalente pour noter la concaténation
de deux langages L1 · L2

Opérations sur les langages : puissance
La puissance n-ème d’un langage L s’obtient en itérant n fois l’opération de

concaténation.
L0 = {ε} Ln+1 = Ln L
La puissance 0 d’un langage contient exactement un mot à savoir le mot

vide.
L1 = L.
w ∈ Ln ssi il existe w1 w2 . . . wn ∈ L tels que w = w1 . . . wn .
Si w ∈ L alors w n ∈ Ln mais il y a en général beaucoup plus de mots
dans Ln que les puissances des mots de L.
Par exemple si L = {a, b} (langage formé de deux mots, chacun réduit à
un caractère) alors Ln contient tous les mots de longueur n et pas juste
an et bn .

Etoile de Kleene
L’étoile de Kleene d’un langage L consiste à considérer l’union de toutes les

puissances possibles du langage.
[
L∗ = Ln
n∈N
ε ∈ L∗
L ⊆ L∗
Si le langage L contient au moins un mot non vide, alors le langage L∗
contient des mots de longueur arbitrairement grande et est donc infini.
Soit A l’alphabet. A peut se voir comme un langage (ensemble des mots
formés d’un seul caractère).
On montre facilement que An est l’ensemble des mots sur l’alphabet A de
longueur n et A∗ est donc l’ensemble de tous les mots sur l’alphabet A.

Problème de la reconnaissance
Etant donné un langage L peut-on construire un algorithme qui étant donné

un mot w répond vrai ou faux suivant si w ∈ L ?
Si L est un langage fini donné en extension par une énumération des
mots qui le composent (L = {w1 , . . . , wn }) alors répondre à la question
w ∈ L se fait (naïvement) en testant si w = w1 et sinon si w = w2 etc
Les langages infinis sont décrits de manière intensionnelle par exemple
par une propriété logique (L = {w ∈ A∗ | P(w)}).
Exemple : mots de longueur paire, mots qui contiennent la lettre a. . .
Tester si w ∈ L se ramène à tester si la propriété P(w) est vérifiée.
Certaines propriétés ne peuvent être testées par aucun algorithme (on dit
qu’elles sont indécidables).
C’est le cas de la question de savoir si un programme quelconque
termine. Si on considère le langage T qui contient tous les programmes
qui terminent alors il n’y a pas d’algorithme qui teste si un mot w ∈ T .

Reconnaissance effective
On va donc caractériser certaines classes de langages pour lesquels on

va non seulement avoir la décidabilité de l’appartenance mais également
des algorithmes efficaces pour tester cette appartenance.
Cela va être le cas des langages réguliers dont la reconnaissance se fait
avec des automates finis déterministes (en temps linéaire sur la longueur
du mot)
Les langages réguliers étant trop restreints (ils ne permettent pas par
exemple de tester si une expression est bien parenthésée), on étend
cette classe en la classe des langages algébriques décrits par des
grammaires (algébriques) qui est aussi décidable.

A savoir
Le vocabulaire de la théorie des langages formels.

Les opérations principales sur les mots et les langages (en particulier
concaténation, puissance).
Justifier qu’un mot est un élément d’un langage donné.

2–Analyse lexicale
1 Langages réguliers et expressions régulières
2 Automates finis
3 Outil d’analyse lexicale : *lex
4 De l’expression régulière à l’automate
5 Déterminiser un automate
6 Compléments sur les langages réguliers

Crédits
Transparents Alain Denise (responsable du cours jusqu’en 2021-22)

extraits de polycopiés de Sophie Gire, de Michel Termier et de Jean Privat
extraits du cours Claude Marché et Ralf Treinen

Introduction
Objectif de l’analyse lexicale et syntaxique
Entrée : suite de caractères (“ordinaires”)

Sortie : arbre de syntaxe abstraite représentant le programme sous-jacent
Structure intermédiaire : suite d’unités lexicales (lexèmes, tokens)
sert d’alphabet d’entrée à l’analyse syntaxique
Problématique de l’analyse lexicale :
décrire les langages concernés (qu’est-ce qu’un identificateur, une
constante entière ou flottante, une chaîne de caractères. . .)
construire un analyseur efficace (est-ce que l’entrée appartient au
langage, dans quelle catégorie ?)
engendrer automatiquement l’analyseur à partir de la description
Outils théoriques : expressions régulières, langages réguliers

Outils logiciels : outils de la famille Lex, décliné suivant les langages
supports

2 Automates finis

Propriétés des langages réguliers
Lemme de l’étoile
Expression régulière associée à un automate
Solutions

Langages réguliers : définition
On se place sur un alphabet A (ensemble fini de caractères)

Un langage (non vide) est régulier si et seulement si il correspond à une
des situations suivantes :
1 c’est le langage réduit au mot vide {ε}
2 c’est un langage réduit à un mot formé d’une lettre de l’alphabet A {a}
3 c’est l’union L1 ∪ L2 (aussi notée L1 |L2 ) de deux langages réguliers L1 et L2
4 c’est la concaténation L1 L2 (ou L1 · L2 ) de deux langages réguliers
c’est l’étoile notée L∗ (définie comme n∈N Ln ) d’un langage régulier L
S
5
Pour montrer qu’un langage (non vide) est régulier, il faut donc le
décomposer en des langages plus simples en utilisant les opérations
d’union, de concaténation ou d’étoile jusqu’à obtenir une lettre de
l’alphabet ou bien un langage réduit au mot vide.
Par convention le langage vide est également considéré comme un
langage régulier.

Exemples
def
Soit w un mot sur l’alphabet A alors le langage L = {w} est régulier.
Si w est le mot vide ou un mot de longueur 1 c’est par définition des
langages réguliers (cas 1 et 2)
def
Sinon on a w = a1 . . . an avec ai ∈ A et n ≥ 2 on pose Li = {ai } qui est
régulier et on a L = L1 L2 . . . Ln
Tout ensemble fini de mots est régulier
vrai pour l’ensemble vide par définition
vrai pour un langage avec un seul mot par le résultat précédent
def def
si L = {w1 , . . . , wn } avec n ≥ 2 on pose Li = {wi } qui est régulier (résultat
précédent) et on a L = L1 |L2 . . . |Ln (union finie d’ensembles réguliers)
L’opération d’étoile est celle qui va permettre de construire des langages
réguliers infinis.

Expressions régulières : introduction
des notations (finies) pour représenter des langages réguliers

(possiblement infinis)
opérations de base (concaténation, union, étoile) mais aussi
abbréviations pour des situations courantes (option, itérations. . .)
des caractères spéciaux (en particulier ∗ et |) en plus des caractères de
l’alphabet de base
une syntaxe spécifique pour représenter les opérations sur les langages
(avec des règles de priorité, des parenthésage etc...)
dans la vie réelle, certains caractères peuvent avoir deux interprétations
caractère “ordinaire” de l’alphabet
caractère “spécial” pour une opération sur les langages réguliers
usage de caractères d’échappement pour les différentier
suite de deux caractères \* dans l’expression régulière pour représenter un
caractère * de l’alphabet A

Expressions régulières : difficultés
Deux étapes pour décrire un langage par une expression régulière :

identifier la décomposition souhaitée en opérations régulières (souvent
plusieurs possibilités)
utiliser la bonne syntaxe pour traduire ces opérations dans le langage
d’expressions régulières cible.

Expressions régulières : exemple shell
cf cours intro à l’info du L1

Motifs shell
Même base mais syntaxe des motifs différente (*, ?)

syntaxe des expressions régulières GLOB

Expressions régulières “simples” : définition
les expressions régulières sont appelées de manière équivalente

expressions rationnelles
alphabet A (ensemble fini de caractères)
On ajoute les caractères spéciaux suivants : ∗, |, (, ), ε
Les caractères spéciaux ε, |, ∗, (, ) sont différents des caractères de
l’alphabet.
Un mot sur l’alphabet A augmenté des caractères spéciaux va
représenter un langage régulier (L ⊆ A∗ )

Expressions régulières “simples” : notations
ε : décrit le langage réduit au mot vide {ε}

w ∈ A∗ : un mot sur A, décrit le langage réduit au mot w, ie. {w}
si e, e1 , e2 sont déjà des expressions régulières qui correspondent aux
langages L, L1 , L2 alors on peut former de nouvelles expressions
régulières
union : e1 | e2 correspond au langage L1 ∪ L2
concaténation : e1 e2 correspond au langage L1 L2
étoile : e∗ correspond au langage L∗ ( n∈N Ln )
S
des parenthèses (e) permettent de lever les ambigüités sans changer

l’interprétation : on écrira (e1 | e2 )∗ ou e1 | (e2∗ )

Exemple : constantes entières
alphabet des caractères ASCII

entiers non signés (plusieurs tentatives) :
(0|1|2|3|4|5|6|7|8|9)∗ contient le mot vide !
(0|1|2|3|4|5|6|7|8|9)((0|1|2|3|4|5|6|7|8|9)∗ ) des zéros inutiles au début
(1|2|3|4|5|6|7|8|9)((0|1|2|3|4|5|6|7|8|9)∗ ) manque 0
0 | ((1|2|3|4|5|6|7|8|9)((0|1|2|3|4|5|6|7|8|9)∗ ))

Exercice
Enumérer le mots de longueur inférieure ou égale à 3 dans les langages

représentés par les expressions régulières suivantes
1 (a|b|c|d)∗
2 (a|b)∗ (c|d)
3 (a|b)∗ (c|d)∗
4 (a∗ |c)∗
Solution

Exercice
Donner des expressions régulières pour chacun des langages suivants sur
l’alphabet {a, b, c}
1 ensemble des mots qui commencent par abc
2 ensemble des mots qui ne contiennent pas de b
3 ensemble des mots qui commencent par abc ou ac
4 intersection des deux langages précédents
Solution

Exercice
Pour chacun des mots (colonnes) et des expressions régulières (lignes),

déterminer si le mot appartient au langage défini par l’expression :
ε abba a10 b7 aaabbb abbbabbabbabababbababa

∗
aa|(b )
(aa|b)∗
(a∗ )∗
(a∗ b∗ )∗
(a|b)∗
(aab(a∗ |b∗ )baa)
| ba(a∗ )
Solution

Langage régulier
Definition (Langage régulier (définition alternative))

Un langage (non vide) est dit régulier (ou de manière équivalente
rationnel) s’il existe une expression régulière qui le décrit.
Par convention l’ensemble vide de mots ∅ est un langage régulier.
Il existe des langages non réguliers : {an bn |n ∈ N}

(on ne peut pas “compter”)

Expressions régulières étendues
Pour faciliter la description des langages, on introduit des notations

supplémentaires.
Soit e une expression régulière (étendue) qui correspond au langage L
e+ décrit le langage LL∗ ( n>0 Ln )
S
e? décrit le langage L ∪ {ε}

[a1 . . . an ] avec ai ∈ A des caractères, décrit le langage {a1 , . . . , an }
[∧ a1 . . . an ] avec ai ∈ A des caractères, décrit le langage
{b|b ∈ A \ {a1 , . . . , an }}
si a et b sont deux caractères ASCII représentant des chiffres ou bien
deux caractères ASCII représentant des caractères alphabétiques
majuscules ou minuscules, on peut écrire entre les crochets a − b pour
représenter l’ensemble des caractères dont le code ASCII est compris
entre celui de a et celui de b.

Exemples d’expressions régulières étendues
[0 − 9]+ : suite non vide de chiffres

”[∧ ”]∗ ” suite de caractères délimitée par des guillements ”
[a − z A − Z ]([a − z A − Z 0 − 9]+) identifiant ne contenant que des
caractères alphanumériques et commençant par un caractère
alphabétique

Propriété
Les expressions régulières étendues décrivent des langages réguliers

Expressions régulières équivalentes
e+ correspond à l’expression régulière ee∗
e? correspond à l’expression régulière e|ε
[a1 . . . an ] avec ai ∈ A des caractères correspond à l’expression régulière
a1 | . . . |an
[â1 . . . an ] avec ai ∈ A des caractères correspond à l’expression régulière
b1 | . . . |bm avec {b1 , . . . , bm } = A \ {a1 , . . . , an } (l’alphabet est fini)

A savoir
le langage des expressions régulières étendues

le lien entre une expression régulière et le langage associé
la définition d’un langage régulier
trouver le langage associé à une expression régulière
construire l’expression régulière correspondant à un langage

2 Automates finis

Solutions

Analyse : introduction
On a caractérisé une classe de langages dont les éléments sont décrits

simplement par une expression régulière.
On s’intéresse maintenant à des techniques de reconnaissance.
On introduit la notion générale d’automate fini.
Les automates sont utilisés dans de nombreux contextes
modélisation de systèmes interactifs
procédures de décision (ramener un problème à l’appartenance d’un mot à
un langage régulier)
Il existe de nombreuses génératlisation des automates finis (automates
temporisés, automates à pile, . . .)

Automate fini : introduction
Un ensemble fini d’états dont un état initial et plusieurs états finaux

Des transitions entre les états déclenchées par une entrée externe
Question : Est-ce qu’une suite d’entrées peut faire passer de l’état initial
à un état final ?
Variantes :
Version déterministe : pour chaque entrée et chaque état, un seul état cible
possible
Version avec ε-transitions (transitions silencieuses) : le système peut
changer d’état de manière spontanée (sans lire d’entrée)

Automates : extensions
automate à pile : le système dispose d’une mémoire qui lui permet de

stocker des informations sur les transitions prises et de les utiliser pour
choisir la transition à effectuer (grammaires et langages algébriques)
La pile permet de compter
machine de Turing : possibilité de lecture, écriture sur un ruban infini
(tous les langages reconnaissables sur machine)
automates temporisés (transition par passage du temps)
automates d’arbres, de mots infinis
...

Automate fini : définition
Un automate fini est formé de cinq composants présentés comme un

quintuplet (A, Q, q0 , F , δ)
A alphabet, ensemble fini de caractères (entrées)
Q est un ensemble fini appelé ensemble des états
q0 ∈ Q est l’état initial
F ⊆ Q est l’ensemble des état terminaux (on dit aussi état final)
δ (delta) est la fonction de transition.
Elle prend en argument un état q ∈ Q et un élément de A ∪ {ε} (entrée
dans l’alphabet a ∈ A ou transition silencieuse) et renvoie un ensemble
d’états qui correspond à tous les états auxquels on peut arriver à la suite
de q pour l’entrée a ou de manière silencieuse.
Il est possible que cet ensemble soit vide.
alternativement, on peut voir δ comme une relation, sous-ensemble de
Q × (A ∪ {ε}) × Q (les transitions possibles entre les états).
transition : (q1 , a, q2 ) ∈ δ ssi q2 ∈ δ(q1 , a)

Automate fini : exemple
A = {a, b, c} Q = {0, 1, 2, 3, 4, 5} q0 = 0 F = {3, 5}

Transitions
δ(0, c) = {1} δ(1, a) = {2, 4} δ(2, a) = {2}

δ(2, b) = {3} δ(4, c) = {5} δ(5, b) = {1}
δ(n, x) = ∅ sinon
2 3
a b
c
0 1
b
a
4 5
c

Automate fini : représentations
Plusieurs manières de représenter graphiquement les états terminaux

(flèche sortante, croix, . . .)
Représentation de la fonction de transition δ par une table
a b c
0 1
1 2, 4
2 2 3
3
4 5
5 1

Automate fini : représentations
Représentation relationnelle
δ = {(0, c, 1), (1, a, 2), (1, a, 4), (2, a, 2), (2, c, 3), (4, c, 5), (5, c, 1)}
Chaque triplet (q, x, q ′ ) avec q, q ′ ∈ Q des états et x ∈ Q un caractère et

q ′ ∈ δ(q, x) est appelé une transition de l’automate.
En tableau
0 1 2 3 4 5
0 c
1 a a
2 a b
3
4 c
5 b
Plusieurs entrées possibles entre deux états (représentées par une seule
flèche étiquetée par les entrées)
Automates avec ε-transition
A = {a, b, c} Q = {0, 1, 2, 3} q0 = 0 F = {3}
Transitions δ 1
a b
a b c ε
0 1 2
1 3 2 0 ε 3
2 3
3 b c
2
Un automate avec ε-transition est dit asynchrone (réagit même sans

entrée)
Un automate sans ε-transition est dit synchrone

Automates et langages
Chaque automate définit un langage, celui des mots reconnus entre l’état
initial et un état final.
Définitions préalables des notions de chemin et de trace

Chemin dans un automate
Automate A = (A, Q, q0 , F , δ)
Transition : {(q, x, q ′ ) ∈ Q × (A ∪ {ε}) × Q|q ′ ∈ δ(q, x)}
Chemin : suite de transitions consécutives (l’état d’arrivée d’une
transition est l’état de départ de la suivante)
(q1 , x1 , q2 )(q2 , x2 , q3 ) . . . (qn , xn , qn+1 )
Le chemin mène du sommet q1 (origine) au sommet qn+1 (destination)

Le chemin a pour longueur n
On note δ ∗ l’ensemble de toutes les suites de transitions associées à la
fonction δ

Trace d’un chemin
A chaque chemin C on peut associer un mot tr (C) de A∗ en concaténant

les caractères qui apparaissent dans les transitions
Au chemin (q1 , x1 , q2 )(q2 , x2 , q3 ) . . . (qn , xn , qn+1 ), on associe le mot
x1 x2 . . . xn
Ce mot a pour longueur au plus n (moins en cas de ε-transition)

Langage reconnu par un automate
Un mot u ∈ A∗ est reconnu (on dit aussi accepté) par un automate A s’il
existe un chemin C d’origine l’état initial, dont la destination est un état
final et dont la trace est le mot u.
Le langage reconnu par l’automate A est l’ensemble des mots reconnus
par A. Il est noté L(A)
Un langage L est dit reconnaissable s’il existe un automate fini A tel que
L = L(A)
Théorème de Kleene : les langages reconnaissables sont exactement les
langages réguliers
Description par une expression régulière (étendue)
Reconnaissance par un automate fini

Exercice
Soit l’alphabet A = {a, b, c}

Donner un automate fini pour chacun des langages suivants
1 Mots qui commencent par abc
2 Mots qui ne contiennent pas de b Solution
3 Mots qui commencent par abc ou ac

4 Mots contenant au moins trois occurrences successives de a Solution
5 Mots de longueur paire Solution

Automate fini déterministe
Un automate fini est déterministe ssi

il est synchrone (pas de ε-transition)
la relation de transition est fonctionnelle : au plus un état dans δ(q, x)
On a alors une fonction de transition (partielle) δ : Q × A → Q
on peut toujours rendre un automate déterministe mais cela peut faire
grossir exponentiellement le nombre des états (voir suite du cours)

Exercice
construire un automate fini déterministe qui reconnait tous les mots dans
lesquels apparait le mot abc :
un tel mot s’écrit uabcv
on dit que abc est un facteur du mot
(à ne pas confondre avec un sous-mot qui peut effacer des lettres
intermédiaires)
Solution

Automate fini déterministe complet
Un automate fini déterministe est complet ssi la fonction de transition δ

est totale
il y a une transition possible pour chaque état et chaque caractère
il est facile de rendre un automate déterministe complet
ajouter un état puits : ⊥
compléter la fonction de transition partielle δ ∈ Q × A → Q en une fonction
totale δ ∈ (Q ∪ {⊥}) × A → Q ∪ {⊥}
δ ′ (q, x) = δ(q, x) si δ(q, x) est défini
δ ′ (q, x) = ⊥ si δ(q, x) non défini ou q = ⊥
aucune transition ne sort de l’état ⊥ vers un état de Q et ⊥ n’est pas un
état final : aucun chemin de l’état initial à un état final ne passe par ⊥
le langage reconnu n’est pas changé.

Automate fini déterministe complet : exemple
b
b
a 2
a 2
c
1 a
c b, c b
1 a
b
4(⊥) 3
a, c
3
a, b, c

Automate fini déterministe complet : applications
avoir une fonction de transition totale est plus facile à gérer

construction directe de l’automate qui reconnaît le complémentaire du
langage : on inverse les états terminaux et les états non terminaux.
Soit A = (A, Q, q0 , F , δ) un automate déterministe complet qui reconnait
le langage L, alors A = (A, Q, q0 , Q \ F , δ) est un automate déterministe
complet qui reconnaît le langage A∗ \ L.

A savoir
La définition d’un automate fini et le vocabulaire associé (état initial,

terminal/final, transition)
Les différentes catégories d’automates : synchrone/asynchrone,
déterministe ou non, complet ou non
Lien entre le langage reconnu par l’automate et l’automate
les automates finis reconnaissent exactement les langages réguliers
construire un automate pour un langage donné
reconnaître qu’un mot appartient au langage accepté par un automate

Correction
1 (a|b|c|d)∗ : Tous les mots sur l’alphabet {a, b, c, d}

ε, a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, ca, cb, cc, cd, da, db, dc, dd,
aaa, aab, aac, aad, aba, abb, abc, abd, aca, acb, acc, acd, ada, adb, adc, add,
baa, bab, bac, bad, bba, bbb, bbc, bbd, bca, bcb, bcc, bcd, bda, bdb, bdc, bdd,
caa, cab, cac, cad, cba, cbb, cbc, cbd, cca, ccb, ccc, ccd, cda, cdb, cdc, cdd,
daa, dab, dac, dad, dba, dbb, dbc, dbd, dca, dcb, dcc, dcd, dda, ddb, ddc, ddd
2 (a|b)∗ (c|d) : Mots formés de a et b qui se terminent par un c ou un d

c, d, ac, ad, bc, bd, aac, aad, abc, abd, bac, bad, bbc, bbd

Correction
1 (a|b)∗ (c|d)∗ : Mots formés d’une suite (possiblement vide) de a et de b

puis d’une suite (possiblement vide) de c et de d
ε, a, b, c, d, aa, ab, ac, ad, ba, bb, bc, bd, cc, cd, , dc, dd,
aaa, aab, aac, aad, aba, abb, abc, abd, acc, acd, adc, add,
baa, bab, bac, bad, bba, bbb, bbc, bbd, bcc, bcd, bdc, bdd,
ccc, ccd, cdc, cdd, dcc, dcd, ddc, ddd
2 (a∗ |c)∗ : Mots formés juste de a et de c

ε, a, c, aa, ac, ca, cc, aaa, aac, aca, acc, caa, cac, cca, ccc
Retour

Correction
Alphabet {a, b, c}
ensemble des mots qui commencent par abc :
(abc)(a|b|c)∗
ensemble des mots qui ne contiennent pas de b :

(a|c)∗
ensemble des mots qui commencent par abc ou ac:

((abc)|(ac))(a|b|c)∗ ) ou bien a(b|ε)c(a|b|c)∗
intersection des deux langages précédents:

ac(a|c)∗
Retour

Solution
ε abba a10 b7 aaabbb abbbabbabbabababbababa

∗
aa|(b ) O N N O N N
(aa|b)∗ O N O O N N
(a∗ )∗ O N O N N N
(a∗ b∗ )∗ O O O O O O
(a|b)∗ O O O O O O
(aab(a∗ |b∗ )baa) N N N N N N
| ba(a∗ )
Retour

Solution
Mots qui commencent par abc
a, b, c
a b c
0 1 2 3
Mots qui ne contiennent pas de b

a, c
Retour

Solution
Mots qui commencent par abc ou ac
a, b, c
a b c
0 1 2 3
Mots contenant au moins trois occurrences successives de a
b, c a, b, c
b, c
a a a
0 1 2 3
b, c
Retour

Solution
Mots de longueur paire
a, b, c
0 1
a, b, c
Retour

Solution
tous les mots dans lesquels apparait le mot abc :
b, c a, b, c
b
a b c
0 1 2 3
c a
a
Retour

2 Automates finis

Solutions

Rappel
Les expressions régulières sont des notations pour représenter des

langages réguliers
Les automates finis permettent de reconnaître qu’un mot appartient à un
langage régulier

Analyse lexicale des langages de programmation
Plusieurs unités lexicales (mots-clés, symboles, identificateurs,

constantes entières, flottantes, chaîne de caractères. . .) dans une suite
de caractères (le programme en entrée).
Chaque unité lexicale appartient à un langage décrit par une expression
régulière : ei
L’unité est (en général) associée à une classe (comme la classe des
identifiants ou celle des constantes ou celle des symboles de comparaison)
S’il y a plusieurs mots possibles, on associe à la classe une valeur (l’entier,
le flottant, la chaîne. . .)
Certaines parties du texte sont ignorées, elles servent de séparateur
(blancs, commentaires. . .)
Le texte est découpé en unités successives
Langage global reconnu : (e1 | . . . | en )∗
L’analyseur produit un mot sur l’alphabet des classes d’unités lexicales

Générateur d’analyseur
Objectif
Reconnaître dans une suite de caractères des mots tels que décrits par
des expressions régulières
En fonction de l’expression régulière et du mot reconnu, effectuer une
action
Fonctionnalité
Engendrer un automate (déterministe) à partir d’une expression régulière
Fonction de lecture d’une suite de caractères et de reconnaissance
successive des mots

Générateur d’analyseur : Approche
Langage spécifique pour décrire l’analyseur

(expression régulière/action)
Outil spécifique qui engendre le code de l’analyseur
Insertion naturelle du code engendré dans le langage de programmation
cible
Application :
analyse lexicale des langages de programmation
mais aussi : coloriage, extraction d’information, transformation de textes, etc

Programmes *lex
Langage de description avec ses règles lexicales, syntaxiques,
sémantique
Modèle d’exécution ad-hoc
Traiter une suite de caractères (ASCII, unicode) en entrée
Effectuer des actions en fonction de motifs reconnus, décrits par des
expressions régulières
Généraliste
Optimisé pour le traitement efficace de grandes données
Facilités de description des expressions régulières, de repérage dans le
texte initial (ligne, colonne)
Règles opérationnelles
choix de reconnaître la suite de caractères la plus longue possible
priorités entre deux motifs de même longueur
Exploitation de l’automate
superposer plusieurs automates (reconnaissance spécifique des
commentaires ou des chaînes de caractères)
mémoriser des informations via les actions (langages non réguliers)

Jflex
Une approche ancienne (lex pour C, Bell labs, 1975)

Ce cours : utilisation de jflex pour Java
Site https://www.jflex.de/
Un mémento (Télécom Sud-Paris) bien fait :
http://www-inf.telecom-sudparis.eu/cours/CSC4536/web/
?page=Mementos/jflex-memento
D’autres analyseurs sur le même principe : ocamllex, flex . . .

Schéma d’utilisation
Programme source jflex description.jflex
Compilateur jflex > jflex description.jflex
Programme source java Yylex.java
Compilateur java > javac Yylex.java
Programme exécutable Yylex.class
> java Yylex fichier.txt

Format d’un fichier jflex
Trois parties séparées par le symbole %% seul sur une ligne

Commentaires à la Java (de // à la fin de ligne ou /* ... */)
/* Préambule : code utilisateur */
// Déclarations préliminaires : import, package
// Recopié tel quel dans la cible
%%
/* Déclarations et options */
// directives "%..."
// blocs de code auxiliaire "%{" ... "%}"
// abbréviations d’expressions régulières : nom = regexp
%%
/* Règles lexicales */
// Règle sous forme :
// regexp { /* code java de l’action */ }

Exemple
Extraire des adresses mail d’un fichier texte

Spécification des adresses mail (approximation)
suite de caractères alpha-numériques, points et tirets, commence par un
caractère alphabétique
symbole @
suite de caractères alpha-numériques, points et tirets, commence par un
caractère alphabétique
suffixe final : point suivi d’une suite non vide de caractères alphabétiques
Impression des adresses trouvées, reste du texte ignoré

JFlex : exemple
%%
%i n c l u d e . . / TP / J f l e x . i n c l u d e
%s ta n da l o n e
%c l a s s M a i l
%{
v o i d ECHOL( S t r i n g c a t )
{ System . o u t . p r i n t l n ( " [ " + c a t + " : " + y y t e x t ( ) + " ] " ) ; }
%}
AL = [ a−zA−Z ]
OK = { AL } | [ 0 − 9 . − ]
%%
{ AL } {OK} * @ { AL } {OK} * \ . { AL}+
{ ECHOL( " MAIL " ) ; }
[^] { }

JFlex : ligne à ligne
%%
Séparateur entre le préambule (code java import) et les déclarations Jflex

Directive %include pour partager un fichier de configuration
%s t a n d al o ne
Directive %standalone pour engendrer la fonction main (lecture de l’entrée

dans un fichier)
Dans le mode standalone, les caractères qui ne sont pas reconnus sont
renvoyés sur la sortie standard
%class M a i l
Directive %class Mail fixe le nom de la classe engendrée
(par défaut Yylex)

%{
void ECHOL( S t r i n g c a t )
{ System . o u t . p r i n t l n ( " [ " + c a t + " : " + y y t e x t ( ) + " ] " ) ; }
%}
Code Java entre %{ ... %} inséré dans la classe, utilisé dans les
actions
Le code utilise la fonction yytext() qui renvoie dans l’action la chaîne
de caractère reconnue correspondant à l’expression régulière (type
String)
AL = [ a−zA−Z ]
OK = { AL } | [ 0 − 9 . − ]
abbréviations pour les expressions régulières de la forme nom=regexp

le nom sera réutilisé dans d’autres expressions régulières sous la forme
{nom} (ne pas oublier les accolades!)
hhh (((
expression régulière, pas de cycles! ((
PAR
(( =h
((h
(PAR
hhh ))

%%
Séparateur entre la partie déclarations Jflex et les règles lexicales
{ AL } {OK} * @ { AL } {OK} * \ . { AL}+
{ ECHOL( " MAIL " ) ; }
[^] { }
les règles de la forme regexp { code }

les caractères <>{}()[]|!~*+?"^$/.\,- ont un sens particulier dans
la syntaxe Jflex, leur utilisation dans les expressions régulières doit être
échappée (ici \. désigne le point)
l’expression régulière [^] est spécifique à Jflex, elle reconnaît n’importe
quel caractère (les différentes formes de retour à la ligne comprises),
utile en fin de spécification pour traiter ce qui n’aura pas été reconnu par
les autres règles.
possibilité d’action vide (l’entrée est consommée)

Compilation
>jflex mail.jflex
Reading "mail.jflex"
Including "../TP/Jflex.include"
Constructing NFA : 26 states in NFA
Converting NFA to DFA :
........
10 states before minimization, 8 states in minimized DFA
Old file "Mail.java" saved as "Mail.java~"
Writing code to "Mail.java"
>javac Mail.java
>java Mail test-mail.csv
[MAIL:christine.paulin@universite-paris-saclay.fr]
[MAIL:frederic.gruau@universite-paris-saclay.fr]
[MAIL:jeremy.labiche@universite-paris-saclay.fr]
[MAIL:alida.nana-sunji-kouanang@universite-paris-saclay.fr]
[MAIL:nathan.thomasset@universite-paris-saclay.fr]
[MAIL:mathias.loiseau@universite-paris-saclay.fr]
...
Expressions régulières Jflex
Alphabet : dépend du système de caractères (ASCII, unicode. . .)

Expressions régulières étendues
opérations de base : mot, concaténation, union, étoile et extensions
a(bc)*a+b?|aaa
ensemble de caractères :
[1-5] ou exclusif [â-z]
caractère universel . tout caractère sauf les fins de ligne
(\r\n | [\r\n\u2028\u2029\u000B\u000C\u0085])
expression régulière pour les fins de ligne : \R (Jflex)
caractère quelconque : [^] (Jflex)
itérations bornées :
r{N} : répétition exactement N fois
r{N,M} : répétition n fois avec N ≤ n ≤ M

Expressions régulières contextuelles
^r reconnaît r uniquement en début de ligne, le chapeau doit être le

premier caractère de l’expression régulière, sinon c’est un simple
caractère
r$ reconnaît r uniquement en fin de ligne, le chapeau doit être le dernier
caractère de l’expression régulière, sinon c’est un simple caractère, le
retour à la ligne suivant n’est pas consommé
r/s reconnait r uniquement si suivi d’un mot de s mais ne retient que la
partie correspondant à r , usage simultané de / et $ interdit.
Exemples : ^\n : ligne vide, ^[ \t]+$ une ligne blanche non vide
(^[ \t]*$ n’est pas autorisé car [ \t]* contient le mot vide),

Expressions régulières Jflex
Règles de priorité
les opérateurs postfixes *, + et ? sont plus prioritaires que la concaténation
elle-même plus prioritaire que l’union
ab*|c+ correspond à (a(b*))|(c+)
des parenthèses pour des articulations différentes comme ((ab)*|c)+
Caractères réservés
<>{}()[]|!~*+?"^$/.\,-
à protéger dans une chaîne "..." ou avec le caractère d’échappement \
comme dans \.
échappement non nécessaire dans certains contextes comme les classes
de caractères (à l’exception du tiret) ou les caractères ^$ lorsqu’ils ne sont
pas en début ou fin d’expression.
exemples : "(.)" \.\.\. \".*\" [+*/-] [+*-/]

Expressions régulières récapitulatif
ef l’expression e suivie de l’expression f
e|f l’expression e ou l’expression f
e? 0 ou 1 fois l’expression e
e* 0 ou n fois l’expression e (n quelconque)
e+ 1 ou n fois l’expression e (n > 0 quelconque)
e{n} n fois l’expression e (n quelconque)
e{n,m } k fois l’expression e (k quelconque n ≤ k ≤ m)
(e) l’expression e
{D} l’expression correspondant à la définition D
e/f l’expression e si suivie de l’expression f
ê l’expression e en début de ligne
e$ l’expression e en fin de ligne
. tout caractère sauf fin de ligne (\n \r...)
c le caractère c non spécial (fonction du contexte)
\c le caractère c même spécial
"abc" le mot abc même si caractères spéciaux
[abc] les caractères a ou b ou c
[a − c] les caractères de code entre a et c
[âbc] les caractères sauf a et b et c

Interprétation des règles
reconnaître un mot dans le langage associé à l’union des expressions
régulières
chaque état final est associé à la règle concernée
un même état peut être final pour plusieurs règles :
mode glouton : le système choisit la règle qui correspond au mot le plus
long reconnu et, en cas d’égalité, la première règle dans le fichier
état du système :
position de début dans la suite de caractères d’entrée
position du caractère courant
état courant dans l’automate
possiblement dernier état final rencontré et position du caractère associé
lorsque le prochain caractère lu ne permet pas d’avancer :
retour au dernier état final rencontré et au mot reconnu à ce stade
déclenchement de l’action correspondante
reprise de la lecture au caractère qui suit le mot reconnu à partir de l’état
initial de l’automate
en mode %standalone, les caractères non reconnus sont juste transcrits
sur la sortie standard (ajouter une règle balai pour les traiter explicitement)

Jflex : directives
%%
/ / i n t y y l i n e , yycolumn ; l o n g yychar ;
%l i n e
%column
%char
/ / renommage de l a c l a s s e engendrée : MaClasse . j a v a dé f a u t Yylex

/ / e t f o n c t i o n d ’ analyse : " i n t n e xt _ t ok e n ( ) " dé f a u t y y l e x
%c l a s s MaClasse
%i n t
%f u n c t i o n n e x t _ t o k e n

Jflex : directives
%s t a n d a lo n e / / Programme autonome
%cup / / Programme c o u p l é avec CUP
%i n i t { / * code dans l e c o n s t r u c t e u r : a c t i o n i n i t i a l e * /
System . o u t . p r i n t l n ( " Analyse L e x i c a l e Sample0 ( t y p e any t e x t ) : " ) ;
%i n i t }
%e o f { / * code en a c t i o n f i n a l * /
System . o u t . p r i n t l n ( " Bye ! " ) ;
%e o f }
%c a s e l e s s / * confondre minuscules / majuscules */
%s t a t e ETAT , ETAT2 / * É t a t s i n c l u s i f s du super −automate * /
%x s t a t e STATE / * É t a t s e x c l u s i f s du super −automate * /

Jflex : opérations prédéfinies
String yytext() : la valeur du mot reconnu

int yylength() : la longueur du mot reconnu
char yycharat(int pos) : caractère de la chaîne reconnue
long yychar; int yycolumn, yyline si les directives
correspondants sont activées, donne la position courante dans la lecture
(affichage des erreurs)
Actions
La même action peut être partagée entre plusieurs expressions
régulières avec la syntaxe
â * | â * { ECHO ( ) ; }
b*$ | traduit en b * $ { ECHO ( ) ; }
ab / a { ECHO ( ) ; } ab / a { ECHO ( ) ; }

Au delà des langages réguliers
Grace aux actions, on peut se servir d’un outil comme Jflex pour
reconnaître des langages qui ne sont pas réguliers.
Exemple : compter les parenthèses ouvrantes et fermantes
(commentaires imbriqués)

Exemple langage non-régulier
%%
%s t a n d a l o n e
%i n t
%l i n e
%column
%c l a s s Parens
%{
i n t par = 0 ;
i n t erreur ( ) {
System . o u t . p r i n t l n ( " p a r e n t h èse fermante en t r o p l i g n e "
+( y y l i n e +1) +" colonne "+ yycolumn ) ;
return 1;}
%}
%e o f v a l {
i f ( par > 0 ) { System . o u t . p r i n t l n ( par +" p a r e n t h èses o u v e r t e s non ferm ées " ) ;
return 1;}
e l s e { System . o u t . p r i n t l n ( "OK " ) ; r e t u r n 0 ; }
%e o f v a l }
%%
$ { par + + ; }
$ { i f ( par > 0 ) { par − −; } e l s e { e r r e u r ( ) ; } }
[^()] { }

Etats contextes
Les expressions régulières prennent en compte le contexte de manière

limitée (début/fin de ligne, mot suivant)
Lors de l’analyse d’un texte, on peut vouloir utiliser des règles spécifiques
sur une portion de texte
En pratique on introduit plusieurs parcours possibles de l’automate, en
fonction du contexte
Règles étiquetées par l’état contexte si elles s’appliquent lorsqu’on est
dans l’état considéré
Fonction dans les actions pour tester/modifier l’état contexte

états-contexte : mise en œuvre
déclaration par une directive

%state ETAT1
%xstate ETAT2
état-contexte par défaut YYINITIAL
étiquetage d’une ou plusieurs règles par un ou plusieurs états-contexte
<ETAT1> regexp {action}
<ETAT1,ETAT2>{
regexp1 {action1}
regexp2 {action2}
}
fonctions dans les actions yybegin(etat) pour se placer dans le
contexte etat, yystate() pour récupérer l’état courant
les règles non étiquetées s’appliquent dans tous les états inclusifs
(déclaration %state) mais pas aux états exclusifs (déclaration %xstate)
Etat initial par défaut (inclusif) YYINITIAL

Exemple des chaînes de caractères
%%
%s t a n d a l o n e
%c l a s s Chaines
%{
S t r i n g B u f f e r s t r i n g = new S t r i n g B u f f e r ( ) ;
%}
%s t a t e STRING
%%
<YYINITIAL > \ " { s t r i n g . s e t L e n g t h ( 0 ) ; yybegin ( STRING ) ; }
<STRING> {
\" { System . o u t . p r i n t l n ( s t r i n g . t o S t r i n g ( ) ) ;
yybegin ( YYINITIAL ) ; }
[^\n\ r \"\\]+ { s t r i n g . append ( y y t e x t ( ) ) ; }
\\ t { s t r i n g . append ( ’ \ t ’ ) ; }
\\n { s t r i n g . append ( ’ \ n ’ ) ; }
\\ r { s t r i n g . append ( ’ \ r ’ ) ; }
\\\" { s t r i n g . append ( ’ \ " ’ ) ; }
\\ { s t r i n g . append ( ’ \ \ ’ ) ; }
}
[^] { }

Jflex : conclusion
Des outils efficaces mais d’un usage assez technique

Un bel exemple d’interprétation de langage !
Grande sensibilité aux erreurs de syntaxe dans la description jflex
Les erreurs dans le code Java inclus sont seulement détectées à la
compilation du code Java engendré
Des bibliothèques spécialisées pour des tâches de traitement de texte
élémentaires
Partage de la reconnaissance entre expression régulière et action
mots-clés : peut se faire par des expressions régulières spécifiques ou bien
en utilisant l’expression des identifiants puis en reconnaissant les mots-clé
via une table de hashage

A retenir
Les principes généraux des générateurs d’analyseurs lexicaux

Programmer à l’aide d’actions à déclencher sur des mots reconnus par
des expressions régulières
Approfondissement en TP

2 Automates finis

Solutions

Rappel
Les expressions régulières sont des notations pour représenter des

langages dits réguliers
Les automates finis permettent de reconnaître qu’un mot appartient à un
langage qui est alors dit reconnaissable
Les deux notions de langages coïncident
on va montrer que tout langage régulier est reconnaissable
Comment engendrer automatiquement un automate fini (déterministe) à partir

d’une expression régulière ?

Opérations de base des expressions régulières
Alphabet A :
mot vide : ε
caractère : a ∈ A
concaténation : e1 e2
union : e1 | e2
étoile : e1∗
Construction par récurrence sur la structure de l’expression régulière :
On construit les automates pour les cas de base ε et a ∈ A
On suppose construits des automates pour e1 et e2 qui reconnaissent les
langages associés,
on construit alors l’automate pour e1 e2 , e1 | e2 et e1∗
Restrictions (invariant à préserver):
un seul état final
pas de transition qui arrive sur l’état initial ou sort de l’état final

Cas de base
mot vide
expression régulière ε
langage {ε}
automate : ({0}, 0, {0}, ∅)
caractère a ∈ A
expression régulière : a
langage {a}
automate : ({0, 1}, 0, {1}, {(0, a, 1)})
a
0 1

Concaténation
Déjà construits :
expressions régulières ei (i = 1, 2)
langages associés Li (i = 1, 2)
def
automates associés Ai = (Si , 0i , {fi }, Ti ) (i = 1, 2) avec S1 ∩ S2 = ∅
expression régulière : e1 e2
langage L1 L2
automate : (S1 ∪ S2 , 01 , {f2 }, T1 ∪ T2 ∪ {(f1 , ε, 02 )})
ε
01 A1 f1 02 A2 f2

Union
Déjà construits e1 , e2 : (comme pour la concaténation)

expression régulière : e1 | e2
langage L1 ∪ L2
automate : (S1 ∪ S2 ∪ {0, f }, 0, {f },
T1 ∪ T2 ∪ {(0, ε, 0i ), (fi , ε, f )|i = 1, 2})
01 A1 f1
ε ε
0 f
ε ε
02 A2 f2

Etoile
Déjà construit
expression régulière e1
langage associé L1
def
automate associé A = (S1 , 01 , f1 , T1 )
expression régulière : e∗
langage L∗
def
automate : A1 = (S ∪ {0, f }, 0, {f },
T ∪ {(0, ε, 01 ), (f1 , ε, f ), (01 , ε, f1 ), (f1 , ε, 01 )})
ε
ε ε
0 01 A1 f1 f

Preuve
Le fait que les automates construits reconnaissent au moins les mots du

langage régulier associé est immédiat
la propriété d’un seul état terminal et d’absence de transition qui arrive
sur l’état initial ou sort de l’état final est préservé par chaque construction
Il est un peu plus délicat de montrer que l’automate ne reconnait pas plus
de mots
analyse des chemins qui partent de l’état initial jusqu’à l’état final
le fait qu’il n’y ait pas de transition qui sorte de l’état final ou entre dans l’état
initial sert pour la construction étoile

2 Automates finis

Solutions

Déterminiser un automate
Un automate déterministe permet de mener l’analyse d’un mot sans

retour arrière.
Pour tout langage régulier, il est possible de trouver un automate
déterministe qui reconnait ce langage.
Algorithme pour construire à partir d’un automate non-déterministe un
automate déterministe qui reconnait le même langage
Si l’automate initial a n états, l’automate déterministe correspondant peut
avoir jusqu’à 2n états.

Déterminiser un automate synchrone
Soit A = (A, Q, q0 , F , δ) un automate

On construit un nouvel automate sur le même alphabet dont les états
sont des sous-ensembles finis de Q (synthétise l’ensemble des états
possibles en fonction de l’entrée).
Etat initial Q0 = {q0 }
Transitions :
∆({s1 , . . . , sj }, x) = δ(s1 , x) ∪ . . . ∪ δ(sj , x)
On fait l’union des suites possibles des états de la source pour le caractère x
Etats terminaux : contiennent un état terminal de F
En pratique on part de l’état initial, puis pour chaque entrée on calcule
l’état atteignable, on traite ensuite de la même manière tous les états
ainsi engendrés (au plus 2n s’il y a n états dans l’automate initial).

Déterminisation d’un automate synchrone : exemple
a, b
a b
0 0 0, 1 b b
0 1 2
1 2
2
q0 = 0, F = {2}
b
a
b
a b b
{0} {0} {0, 1} {0} {0, 1} {0, 1, 2}
{0, 1} {0} {0, 1} ∪ {2} a
{0, 1, 2} {0} {0, 1} ∪ {2}
q0 = {0}, F = {{0, 1, 2}} a

Cas d’un automate asynchrone
Présence de ε-transition
Possibilité de passer d’un état à l’autre de manière “silencieuse” (sans
entrée)
On associe à un état tous ceux atteignables par une ou plusieurs
ε-transitions
Définition de l’ε-cloture d’un état q ∈ Q : l’ensemble des états q ′ pour
lesquels il existe un chemin de q à q ′ dont la trace est le mot vide ε

ε-cloture : exemple
b a
b
a b ε ε b b
0 0 1 0 1 2 3 4
1 4
2 1, 4 0 ε a ε
3 1
4 3 2
q0 = 0, F = {4}
Etat ε − cloture
0 {0, 1}
1 {1}
2 {0, 1, 2}
3 {3}
4 {0, 1, 2, 4}

Déterminiser un automate asynchrone
1 Calculer l’ε-cloture de chacun des états

2 Construire l’automate déterministe
Etat initial : l’ε-cloture de q0
Transitions :
∆({s1 , . . . , sj }, x) = ε − cloture(δ(s1 , x) ∪ . . . ∪ δ(sj , x))
On fait l’union des ε-clotures des suites possibles des états de la source
pour le caractère x
Etats terminaux : contiennent un état terminal de F

Déterminisation d’un automate asynchrone : exemple
a, b
a b ε
ε−clot
0 0 0 1 ε b b
0 1 2 2 0 0, 1
1 2
1 1
2 3
2 2
3
3 3
q0 = 0, F = {3}
b
a
a b a
{0, 1} {0, 1} {0, 1, 2} b b
{0, 1} {0, 1, 2} {0, 1, 2, 3}
{0, 1, 2} {0, 1} {0, 1, 2, 3}
{0, 1, 2, 3} {0, 1} {0, 1, 2, 3}
q0 = {0, 1}, F = {{0, 1, 2, 3}} a

Exercice
Déterminiser l’automate suivant :
b 1
4 6
ε
0
ε a c a a
a c ε a
2 3 5 7
c
a
Solution

Exercice
Soit A = {a, b} un alphabet.

Construire un automate fini déterministe qui reconnaît le langage des mots
sur A qui contiennent un nombre pair de lettres a et un nombre impair de
lettres b.
Raisonnement plus facile en terme d’états que d’expression régulière
Solution

Retour sur l’analyse lexicale
l e t t e r = [ a−z ]
d i g i t = [0 −9]
id = l e t t e r ( l e t t e r | d i g i t )*
if = " if "
i n t = ( d i g i t )+
f l o a t = ( d i g i t )+ " . " ( d i g i t )+
dot = " . "
bl = (" ")+
On construit un automate unique non-déterministe à partir des

automates de chaque expression régulières
Les états finaux sont distincts et produisent possiblement une sortie
ici : id, if, int, float, dot, les blancs sont ignorés

Automate non déterministe associé
ε ε ε ε ε ε
1 3 6 8 12 14
a-z i 0-9 0-9 . ’ ’
2 7 9 0-9
13 15
id 4 int dot
.
f ’ ’
a-z0-9 0-9 10
5
if 0-9
11 0-9
float

Analyse lexicale : classes de caractères et mots-clés
Au niveau de l’alphabet d’entrée on peut considérer équivallents tous les

caractères qui jouent le même rôle dans les actions (classes de
caractères)
Par exemple 0 − 9
L’alphabet devient alors celui des classes, cela diminue la taille de la table
Les mots clés font partie du langage associé à l’expression régulière des
identifiants
Rendre déterministe un automate union des identifiants et des mots-clés
multiplie le nombre d’états et le nombre de classes de caractères
On utilise souvent une seule règle et une table de hachage qui contient
les mots clés et les léxèmes associés
Au niveau de l’action, on vérifie si l’identifiant reconnu est ou non dans la
table et on renvoie le léxème approprié

A savoir
Connaître l’équivalence entre langages réguliers et reconnaissables

Construire l’automate associé à une expression régulière
Calculer les ε-clotures des états d’un automate asynchrone
Rendre un automate (synchrone ou asynchrone) déterministe

Solution
Calcul de l’ε-clotûre
1 Etat initial {0, 2} : transitions possibles a, b, c
a : état {0, 2}
b : état {0, 1, 2}
c : état {3, 5}
0 0, 2
1 1, 0, 2
2 Etat {0, 1, 2} : mêmes transitions que {0, 2}
2 2 3 Etat {3, 5}: transition possible a vers {4, 6, 7}
3 3, 5 4 Etat {4, 6, 7}: transitions possibles a, c
4 4 a : état {5}
5 5 c : état {3, 5}
6 6 5 Etat {5}: transition possible a vers {6, 7}
7 7 6 Etat {6, 7}: transitions possibles a, c
a : état {5}
c : état {3, 5}
7 Etats terminaux : {6, 7} et {4, 6, 7}

Solution
{0, 1, 2} b
b
a
{0, 2} c
c c
a a a a
{3, 5} {4, 6, 7} {5} {6, 7}
c a
Retour

Solution
Reconnaître qu’un mot contient un nombre pair de a et impair de b.
Le nombre de a et de b dans un mot est soit pair soit impair
4 situations possibles, chacune correspondant à un état de l’automate
1 (0, 0) : nombres pairs de a et de b (initial)
2 (0, 1) : nombre pair de a et impair de b (final)
3 (1, 1) : nombres impairs de a et de b
4 (1, 0) : nombre impair de a et pair de b
(0, 1)
b a
b a
(0, 0) (1, 1)
a b
a b
(1, 0)
Retour

2 Automates finis

Solutions

Par définition
L’union et la concaténation de deux langages réguliers est un langage
régulier
L’étoile d’un langage régulier est un langage régulier
Le complémentaire d’un langage régulier est un langage régulier
L’intersection de deux langages réguliers est un langage régulier

Exercices
Montrer que le complémentaire d’un langage régulier est un langage

régulier
Montrer que l’intersection de deux langages réguliers est un langage
régulier
Solution

Exemple
Soit L1 l’ensemble des mots qui commencent par ab et L2 l’ensemble des

mots qui terminent par bb.
Construire des automates déterministes pour reconnaître ces langages,
leur complémentaire et leur intersection.
Solution

Décision
Soit e une expression régulière, donner un algorithme pour déterminer si

le langage engendré est vide.
Soit deux langages réguliers L1 et L2 , donner un algorithme pour
déterminer si L1 ⊆ L2 .
Solution

Equivalence entre automates
Le même langage peut être décrit par différentes expressions régulières

et différents automates.
Est-il possible de trouver un automate canonique ?
Peut-on reconnaître simplement l’équivalence entre deux automates ?

Equivalence entre états
On introduit une relation d’équivalence entre états.

Deux états p et q sont équivalents, s’il est possible de reconnaître les
mêmes mots à partir de chacun de ces états :
s’il existe un chemin de l’état p jusqu’à un état final dont la trace est
le mot m
alors il existe également un chemin de l’état q jusqu’à un état final
(qui peut être différent) dont la trace est le même mot m.

Equivalence entre états : calcul
Pour calculer les états équivalents, on calcule de manière itérative pour k ∈ N
les états équivalents en k -étapes qui sont ceux à partir desquels on reconnait
les mêmes mots de longueur inférieure ou égale à k
On part d’un automate fini, déterministe et complet : (A, Q, i, F , δ), la
relation ≡k se calcule par récurrence sur k :
Initialement (k = 0) on a deux classes : les couples d’états finaux
(reconnaissent le mot vide) et les couples d’états qui ne sont pas finaux
et donc qui ne reconnaissent pas le mot vide.
On suppose que l’on sait reconnaître les états qui sont équivalents pour
des mots de longueur inférieure ou égale à k (p ≡k q),
Soit p ̸= q tels que p ≡k q, on aura que p ≡k +1 q ssi δ(p, a) ≡k δ(q, a) pour
toutes les lettres de l’alphabet a ∈ A,
On a toujours que si p ≡k +1 q alors p ≡k q (c’est-à-dire ≡k +1 ⊆≡k ).
A une certaine étape l, on aura une égalité : p ≡l q ssi p ≡l+1 q pour tout
couple d’états,
c’est-à-dire que ≡l =≡l+1 .
on aura alors p ≡l q ssi p ≡k q pour k ≥ l ssi p ≡ q

Automate minimal
Si à partir de deux états de l’automate on peut reconnaître les mêmes

mots alors ces deux états peuvent être fusionnés.
La relation ≡ d’équivalence entre états est une relation d’équivalence
On garde un seul état par classe d’équivalence
a a
0 1 2 a
b b b
a a
b 3 4 5 a
b
b
6 a, b
Solution

Compléments sur les langages réguliers
2 Automates finis

Solutions

Comment déterminer si un langage donné L est rationnel ou pas ?

Rationnel : trouver une expression régulière ou un automate qui correspond
au langage
Non rationnel : utiliser le lemme d’itération (ou lemme de l’étoile)
Proposition (Lemme de l’étoile)

Soit un langage L régulier, il existe un entier N qui ne dépend que de L, tel
que tout mot m ∈ L de longueur plus grande que N se décompose en
m = xyz avec
y ̸= ε
|xy | ≤ N
pour tout entier naturel n ∈ N on a m = xy n z ∈ L
Preuve: La preuve vient de l’existence d’une boucle dans tout chemin qui
permet de reconnaître le mot m de longueur strictement supérieure au
nombre d’états de l’automate. □

Langages non réguliers
Proposition
Le langage L = {an bn |n ∈ N} n’est pas régulier.
Preuve:
Si le langage était régulier, soit N la constante du lemme d’itération
Soit m = aN bN on a m = xyz mais comme |xy | ≤ N on a y = ap avec
p>0
On aurait xy 2 z = aN+p bN ∈ L ce qui est contradictoire.
□
Le même argument permet de montrer que le langage formé des mots qui ont
le même nombre de a et de b n’est pas régulier.

2 Automates finis

Solutions

Associer une expression régulière à un automate fini
Il est assez élémentaire de construire un automate (non-déterministe) à

partir d’une expression régulière
Comment faire l’opération inverse de reconstruction de l’expression
régulière à partir de l’automate ?
Plusieurs algorithmes possibles

Elimination des états : idée
On part d’un automate non-déterministe avec un seul état initial sans

transition entrante et un seul état final sans transition sortante (on peut
toujours ajouter un état initial i et un état final f avec des ε-transitions qui
les relient à l’état initial et aux états terminaux de l’automate de départ.
On va transformer le graphe en étiquetant les arètes non plus par des
lettres de l’alphabet mais par des expressions régulières.
Initialement les arètes a ∈ A ou ε peuvent se voir comme des
expressions régulières.
A chaque étape, on supprime un état (qui n’est ni l’état initial, ni l’état
final) jusqu’à ce qu’il ne reste plus que l’état initial et l’état final.
Lorsqu’on supprime un état on met à jour les couples d’arêtes entrante et
sortante sur cet état en tenant compte également d’une éventuelle boucle
Lorsqu’il ne reste que l’état initial et l’état final, l’arète entre ces deux
états est une expression régulière qui correspond au langage reconnu.

Suppression d’un état
e1 e2
s1 s s2
e1 (e)∗ e2

Exemples
b b
a
ε ε
0 1 2 f
a
b b ε
ε a ε b ε
0 1 2 3 4 f
a a
a
Solution

2 Automates finis

Solutions

Solution complémentaire et intersection
Complémentaire
1 Prendre un automate déterministe et le compléter avec des entrées pour
toutes les entrées à l’aide d’un état puits
2 Prendre comme états terminaux de l’automate du complémentaire tous les
états qui ne sont pas terminaux dans l’automate initial (en particulier l’état
puits)
Intersection de deux langages reconnaissables
1 Construire un automate déterministe pour chacun des langages
def
Ai = (Si , 0i , Fi , Ti ) (i = 1, 2)
2 L’automate pour l’intersection a pour état des couples (s1 , s2 ) avec si ∈ Si
3 Etat initial : (01 , 02 )
4 Transition : ((s1 , s2 ), a, (t1 , t2 )) si et seulement si (si , a, ti ) ∈ Ti
5 Etat final : (s1 , s2 ) avec si ∈ Fi
Retour

Exemple : complémentaire et intersection
L1 : mots qui commencent par ab et L2 : mots qui terminent par bb.

1 Automates déterministes pour les deux langages
a a b
a, b
b
b
a b 0 1 2
0 1 2
a
2 Automates complets associés (ajout état puits et transitions pour L1 , L2
complet)
a b
0 1 2 a, b
b
a
−1 a, b

Exemple (suite)
3 Automates des langages complémentaires (inversion des états

terminaux)
A∗ \ L1
a b
0 1 2
b
a
a, b
−1 a, b
A∗ \ L2
a a b
b
b
0 1 2
a

Exemple (suite)
4 Automate produit pour reconnaître l’intersection L1 ∩ L2
(0, 0) a (1, 0) b (2, 1) b (2, 2) b
b a
a
(2, 0) a
Retour

Décision
Un automate reconnaît le langage vide s’il n’y a pas de chemin entre

l’état initial et un état final.
Exemple l’intersection du langage L2 et de son complémentaire, les deux
automates ont les mêmes transitions, les seuls états accessibles sont
(0, 0) (état initial), (1, 1) et (2, 2) mais aucun n’est terminal.
a a b
b
(0, 0) (1, 1) b (2, 2)
a
Soit deux langages réguliers L1 et L2 ,
L1 ⊆ L2 ssi tous les éléments de L1 sont dans L2
ssi il n’y a pas d’élément de L1 qui n’est pas dans L2
ssi l’intersection de L1 et du complémentaire de L2 est vide.
Retour

Solution : Automate minimal
Equivalence
≡0 {0, 1, 2, 4, 5}{3, 6} états terminaux
b b
≡1 {0, 4, 5}{1, 2}{3}{6} 0 → 3, 1 → 4 . . .
b b
≡2 {0}{4, 5}{1, 2}{3}{6} 0 → 3, 4 → 6
≡3 {0}{4, 5}{1, 2}{3}{6}
Automate minimisé :
a
a
0 1, 2
b b
a b
b 3 4, 5 6 a, b
a Retour

b b
a
ε ε
0 1 2 f
a
b|ab∗ a
b∗ a ε
0 2 f
b∗ a(b|ab∗ a)∗
0 f
Retour

Eléments à connaître pour le partiel
Penser à préparer la feuille A4 recto-verso manuscrite autorisée

Phases de l’interprétation des langages
Phases d’analyse lexicale, syntaxique, sémantique et évaluation

quelle entrée et quelle sortie pour chaque phase
rôle des différentes phases
Reconnaître à quelle phase les erreurs de programmation sont identifiées
Reconnaître de possibles ambiguïtés dans l’analyse d’un programme

Vocabulaire et opérations sur les langages
alphabet, caractère, mot, langage

opérations sur les mots : concaténation, puissance
opérations sur les langages : union, intersection, complémentaire,
concaténation, puissance, étoile
savoir dire si un mot appartient à un langage décrit par des opérations

Expressions régulières pour les unités lexicales
Caractérisation récursive des langages réguliers sur un alphabet A
{ε} {a} (si a ∈ A) l1 | l2 l1 l2 l ∗
Syntaxe pour les expressions régulières étendues

Classe de caractères : représente des ensembles de caractères
inclusif [a-z0-9] ou exclusif (tout sauf) [â-z0-9]
Opérations étendues : e+ , e?
Précédences et parenthèses : (e)
Langage associé à une expression régulière
Stratégie de reconnaissance à partir d’expressions régulières dans un
texte (recherche d’une suite d’unités lexicales de taille maximale)

Exemples de questions
Savoir définir un concept par récurrence sur la structure de langage

régulier : calculer contient-vide(e) vrai ssi ε ∈ L(e)
contient-vide(ε) = vrai
contient-vide(a) = faux
contient-vide(e1 | e2 ) = contient-vide(e1 ) ou contient-vide(e2 )
contient-vide(e1 e2 ) = contient-vide(e1 ) et contient-vide(e2 )
contient-vide(e∗ ) = vrai
Expression régulière correspondant à un langage donné :

nombre flottant en java (partiel) : suite de chiffres (entre 0 et 9), suivie du
symbole . suivi d’une suite de chiffres (la suite avant le point ou celle après
le point doit être non vide) suivi de manière optionnelle par un exposant qui
est composé d’un indicateur (e ou E) d’un signe (+ ou -) optionnel et d’une
suite non vide de chiffres.

Exemples de questions (suite)
Soit l’expression régulière %[^\n]*%,

quelle(s) partie(s) du texte suivant est reconnue par un analyseur lexical
comme correspondant à cette expression.
Ceci est un texte % dans lequel
Il % faut retrouver les mots les % plus longs associés % à l’expression % donnée.
Même question avec l’expression régulière %[^\n%]*%,

Solution : reconnaissance lexicale

Automates finis
Définition
Vocabulaire : automates déterministes, complets, (a)synchrones
Répondre à la question si un mot est reconnu ou non par un automate
Construire un automate correspondant à un langage donné
Opérations sur les automates (union, concaténation, étoile,
complémentaire, intersection)
Calculer des ε-clotures, rendre un automate déterministe
Enoncé du théorème de Kleene : langages réguliers = langages
reconnaissables,
Exemple(s) de langage non régulier

Slides Cours1

Transféré par

Droits d'auteur :

Formats disponibles

Slides Cours1

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Slides Cours1

Transféré par

Droits d'auteur :

Formats disponibles

Principe d’Interprétation des Langages

Département Informatique, Faculté des Sciences d’Orsay, Université Paris-Saclay

Licence Informatique - 2ème année

C. Paulin (Université Paris-Saclay) PIL 2023–24 1 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 2 / 303

S’il vous plait,

C. Paulin (Université Paris-Saclay) PIL 2023–24 3 / 303

Le petit prince d’Antoine de Saint Exupery

C. Paulin (Université Paris-Saclay) PIL 2023–24 4 / 303

Intermédiaires entre l’humain et la machine

C. Paulin (Université Paris-Saclay) PIL 2023–24 5 / 303

Transformations successives à partir du code source

C. Paulin (Université Paris-Saclay) PIL 2023–24 6 / 303

Objectif : produire à partir du programme source et des entrées le

C. Paulin (Université Paris-Saclay) PIL 2023–24 7 / 303

Nombreuses questions d’efficacité :

C. Paulin (Université Paris-Saclay) PIL 2023–24 8 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 9 / 303

Etre de meilleurs programmeurs :

C. Paulin (Université Paris-Saclay) PIL 2023–24 10 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 11 / 303

1 Introduction à l’interprétation des langages

C. Paulin (Université Paris-Saclay) PIL 2023–24 12 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 13 / 303

analyse analyse analyse exécution

C. Paulin (Université Paris-Saclay) PIL 2023–24 14 / 303

Un fichier mini-Python a la structure suivante :

C. Paulin (Université Paris-Saclay) PIL 2023–24 15 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 16 / 303

On pourra regarder quelques sites donnant les spécifications complètes de

C. Paulin (Université Paris-Saclay) PIL 2023–24 17 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 18 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 19 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 20 / 303

def f i b ( n ) : END END def ID ’(’ ID ’)’ ’:’ NL

C. Paulin (Université Paris-Saclay) PIL 2023–24 21 / 303

Expliciter la structure d’un programme correct, pour mini-python :

C. Paulin (Université Paris-Saclay) PIL 2023–24 23 / 303

Décrire les suites d’unités lexicales qui correspondent à un programme

C. Paulin (Université Paris-Saclay) PIL 2023–24 25 / 303

C. Paulin (Université Paris-Saclay) PIL 2023–24 26 / 303

On considère juste une instruction et la suite d’unités lexicales associées

Les règles supplémentaires utiles concernant les instructions sont

C. Paulin (Université Paris-Saclay) PIL 2023–24 27 / 303

for ID in expr ’:’ suiteinstr

’[’ lexpr ’]’ NL BEG linstr END

CST ’,’ CST ’,’ CST ’,’ CST instr

print ’(’ expr ’)’

ID ’(’ expr ’)’

C. Paulin (Université Paris-Saclay) PIL 2023–24 28 / 303

expr binop expr expr binop expr

CST ’*’ CST CST ’+’ CST

C. Paulin (Université Paris-Saclay) PIL 2023–24 29 / 303

1 Que se passerait-il si on autorisait un caractère comme ’-’ ou encore

C. Paulin (Université Paris-Saclay) PIL 2023–24 30 / 303

L’arbre de dérivation contient des informations sur la manière dont le

C. Paulin (Université Paris-Saclay) PIL 2023–24 31 / 303

ID("n") Elist Sprint

C. Paulin (Université Paris-Saclay) PIL 2023–24 32 / 303