Introduction
Le compilateur
1
Un compilateur est un programme qui :
prend en entrée une donnée textuelle source (programme, donnée xml, fichier
de configuration, etc)
la reconnaît (l’analyse) pour vérifier sa correction
émet éventuellement un message d’erreur
le traduit dans un langage cible
A quoi sert la THL en compilation
2
Permet de définir rigoureusement(exactement) et reconnaître algorithmiquement (pour
les langages source et cible) :
leur vocabulaire ou lexique : les mots autorisés
⇒ analyse lexicale
⇒ automates à nombre fini d’états, expressions régulières
leur syntaxe : la structure des phrases autorisées
⇒ analyse syntaxique
⇒ automates à pile, grammaires algébriques
leur sémantique : la signification des phrases autorisées
⇒ analyse sémantique
⇒ grammaires attribuées
Chapitre 1: langage
Alphabet - Definition
1
Un alphabet est un ensemble fini, non vide de symboles.
Exemples :
Les nombres romains : ∑1 = {I, V, X, L, C, D, M}
N L'ensemble des entiers n'est pas un alphabet.
Les nombres binaires : ∑2 = {0,1}
Mot - Definition
1
Un mot est une suite (séquence) finie de symbole de l'alphabet X.
Exemples:
W1= I I W2= I X
mot vide
2
Le mot vide noté ε est un mot particulier qui ne contient aucun symbole.
longueur de mot
3
La longueur d'un mot w (notée |w|) est le nombre de symboles qui
constituent ce mot
Exemples :
W = 0101 |W|=4
W= ε |W|=0
La fermeture de kleene
4
L’ensemble de mots sur un alphabet X est noté X* (fermeture transitive).
exemples :
Soit ∑1, ∑1*={ ε, I,II,III,IV,V,VI, ...}
Soit ∑2, ∑2*={ ε, 0,1,10,11,100, ...}
Notations
5
soit w appartient à X
X est l’alphabet
x est une lettre de X
|w|X est le nombre d’occurrences de x dans w.
Exemple : avec X ={a,b}
|abb|a = 1
|abb|b = 2
Opérations sur les mots :
La concaténation
1
Soient w1 et w2 deux mots définis sur l'alphabet ∑,
w1 = a1...an; w2 = b1...bm.
La concaténation de w1 et w2 est un mot w définis sur le même
alphabet. w = a1...an.b1...bm.
exemple :
si W1=001 et W2=1010
Alors W1.W2=001.1010 W2.W1=1010.001
La puissance
2
Soit un alphabet X et w2 appartient à X*.
W^n= { ε si n=0
et
{ W.W^(n-1) si n>0
exemples :
soit w1=01 (w1)³=010101, (w1)°=ε
soit w2=abb (w2)²=abbabb
L'egalite
3
Deux mots sont égaux si :
ils sont de même longueur.
ils ont des lettres identiques de positionnements identiques.
Soit un alphabet X et w1, w2 appartient à X* tels que :
w1 = x1x2 ...xn Ɐ i ∈ {1,2,....n}, xi ∈ X
w2 = y1y2 ...yp Ɐ i ∈ {1,2,....p} yi ∈ X
On a w1 = w2 si et seulement si p = n et Ɐ i ∈ [1; n] : xi = yi.
Facteurs (préfixe et suffixe):
4
Soit un alphabet X et w, u deux mots appartiennent à X*.
u est un préfixe de w ⇔ il existe v ∈ X* tel que w = u.v
u est un suffixe de w ⇔ il existe v ∈ X* tel que w = v.u
Exemple :
soit X={0,1}, w=01100
Les préfixes de w sont : ε, 0, 01, 011, 0110, 01100
Les suffixes de w sont : ε, 0, 00, 100, 1100, 01100
Cas spécial (facteur propre) :
4
u est un facteur propre de w ⇔ u est un facteur de w et w ≠ u
Si on reprend l’exemple précédent w=01100:
Les préfixes propres de w sont : ε, 0, 01, 011, 0110
Les suffixes propres de w sont : ε, 0, 00, 1100, 1100
mot miroir :
4
Si W = a1a2...an, le mot miroir est : Wr = an...a2a1.
Exemple :
Wr=bbca Wr=acbb
language-Definition :
1
Un langage sur un alphabet X est une partie de X*. C’est donc un
ensemble de mots.
L ⊂ X* ou L ∈ P(X*)
Exemple:
Soit X = {a,b} un alphabet.
- ∅ est un langage
- { ε } est un langage
- {a, ba, bba} est un langage
Opérations sur les langages :
2
Soit L1, L2, A ∈ ∑*
Union:
L1 ⋃ L2 ou L1 + L2 = {x | x ∈ L1 ou x ∈ L2}Intersection :
L1 ⋂ L2 = {x|x ∈ L1 et x ∈ L2}Différence :
L1 - L2 = {x|x ∈ L1 et x ∉ L2}Complémentaire :
Ā={x|x ∈ ∑* et x ∉ A}Concaténation :
L1.L2 = {xy|x ∈ L1 et y ∈ L2}L’égalité entre deux langages :
Deux langages A, B ⊆ X* sont égaux, noté A =B ⇔( A ⊆ B et B ⊆ A).Produit de langages :
Soit deux langages A, B ⊆ X*.
Le produit de A et B est noté :
A◦ B ={u.v|u ∈ A et v ∈ B}.