Théorie des Langages
et Compilation
I/Introduction Générale
Introduction
Langages compilés : Se sont des langages où toutes les instructions sont
traduites en code objet avant d’être exécutées
Langages interprétés : Se sont les langages dont les instructions sont
décodées et exécutées instruction/instruction lors de l’exécution
Un compilateur traduit un langage source en langage cible.
La compilation comporte 2 phases principales :
Analyse :
• Découpe le programme en éléments (constituants).
• Produit une représentation intermédiaire.
• Construit un arbre syntaxique abstrait (AST) :
o Chaque nœud = une opération. Les fils = les arguments de l’opération.
Synthèse :
• Génère le programme cible à partir de la représentation intermédiaire.
Rôle important : détecter et signaler les erreurs dans le programme
source.
Analyse lexicale (Scanner)
• Rôle : Découper le programme en unités lexicales (tokens).
• Produit une suite de tokens.
Types de tokens :
• Identificateurs (noms de variables, constantes créés par l’utilisateur)
• Mots clés (propres au langage : for, if, …)
• Constantes (valeurs numériques, etc.)
• Opérateurs (+, −, *, /, et, ou, non, …)
• Séparateurs (; , , …)
• Affectation (:= , =)
Table des symboles :
Stocke les éléments définis par l’utilisateur (identificateurs, constantes).
Codification :
Chaque token = (type, vallex)
• type : catégorie (id, constante, opérateur…)
• vallex : valeur du token (ex : nom d’identificateur)
Analyse Syntaxique (Analyse grammaticale)
• Vérifie si la suite de tokens respecte la grammaire du langage.
• Construit l’arbre syntaxique (structure hiérarchique du
programme).
Exemple :
Soit l’Expression :
position := initial + rate * 60
• position, initial, rate → expressions
• 60 → expression
• rate * 60 → expression
• initial + rate * 60 → expression
➔L’analyse syntaxique vérifie la structure correcte selon la grammaire.
Analyse Sémantique
• Vérifie les erreurs sémantiques du programme source.
• Utilise l’arbre syntaxique produit par l’analyse syntaxique.
• Identifie correctement opérateurs et opérandes.
➔Assure la cohérence logique et typée du programme.
Production du code intermédiaire
• Généré après l’analyse syntaxique et sémantique.
• Code simple, proche du machine, facile à traduire.
Optimisation du code
Améliore : Temps d’exécution, Mémoire et Taille du code
Optimisations courantes :
• Élimination des variables temporaires inutiles
• Suppression des conversions inutiles
• Suppression du code inaccessible
Génération du code
• Produit le code final (souvent assembleur).
• Assigne les emplacements mémoire aux variables.
• Traduit le code intermédiaire en code machine.
Gestion de la table des symboles
• Structure utilisée par toutes les phases.
• Contient : identificateurs, types, fonctions, arguments…
Gestion des erreurs
Deux stratégies :
1. Arrêt immédiat à la première erreur.
2. Continuer et détecter plusieurs erreurs (meilleure méthode).
⚠ Inconvénient : erreurs secondaires possibles dues à une erreur
initiale.
II/ Analyse lexicale
Rôle de l’analyseur lexical (Scanner)
• Lit le programme source caractère par caractère.
• Produit une suite de TOKENS pour l’analyseur syntaxique.
• Les tokens sont générés progressivement pendant la lecture.
Types d’unités lexicales
Unités propres au langage
• Mots clés (ex: float, if, for)
• Opérateurs (+, -, *, =, …)
• Séparateurs (; , ( ) { } …)
Unités personnalisées (créées par le programmeur)
• Identificateurs (noms de variables, fonctions…)
• Constantes (nombres, chaînes…)
Définitions essentielles
Token
• Une paire (nom, valeur optionnelle)
• Nom = catégorie (id, mot clé, constante…)
• Valeur = information associée (ex : nom réel d’un identificateur)
Lexème
• Suite de caractères du programme
• Instance concrète d’un token
Exemple :
• float → mot clé
• pi → identificateur (lexème)
• = → opérateur
• 3.14 → constante
• ; → séparateur
Attributs des unités lexicales
• Chaque token possède un attribut.
• La table contient : nom, type, valeur, etc.
Exemple (Fortran) :
E = M * C ** 2
Tokens générés :
• <id, ptr(E)>
• <op_affectation>
• <id, ptr(M)>
• <op_multiplication>
• <id, ptr(C)>
• <op_exposant>
• <nombre, 2>
➡ Les identificateurs pointent vers leur entrée dans la table.
Mots réservés
• Les mots clés ne peuvent pas être utilisés comme identificateurs.
• Ils sont préinstallés dans la table des symboles.
Exemples : Pascal, C
Erreurs lexicales
➡ L’erreur lexicale concerne surtout la forme invalide des mots.
Spécification des unités lexicales
• Décrites par des expressions régulières.
• Chaque expression régulière décrit un modèle.
• Elles sont transformées en automates finis pour l’implémentation.
Notions fondamentales : Mots et Langages
Alphabet
Ensemble fini de symboles. Exemple : A = {a,b,c,1,3,h}
Mot (chaîne)
• Suite finie de symboles de l’alphabet.
• A⁺ : ensemble des mots non vides.
Soit :
• L = {a…z, A…Z} (lettres)
• C = {0…9} (chiffres)
Expression Signification
L∪C Lettres et chiffres
LC Lettre suivie d’un chiffre
L⁴ Mot de 4 lettres
L* Tous les mots de lettres (y compris ε)
L(L ∪ C)* Identificateur (commence par lettre)
C⁺ Nombre (au moins un chiffre)
III) Expressions Régulières
Définition générale
Une expression régulière (ER) est une notation formelle permettant de
décrire un ensemble de chaînes (langage).
Chaque expression régulière r définit un langage noté : L(r)
Règles de base
Soit un alphabet Σ :
• ε est une ER → L(ε) = {ε} (mot vide)
• Si a ∈ Σ, alors → L(a) = {a}
Règles de construction (Induction)
Expression Signification Langage
r|s Union L(r) ∪ L(s)
rs Concaténation L(r)L(s)
r* Fermeture de Kleene (L(r))*
(r) Parenthèses L(r)
Priorité des opérateurs
1. * plus haute priorité
2. Concaténation
3. | plus faible priorité
Exemple :
a|b*c ≡ a | (b* c)
Exemples importants
Soit Σ = {a, b}
• a|b → {a, b}
• (a|b)(a|b) → {aa, ab, ba, bb}
• a* → {ε, a, aa, aaa, ...}
• (a|b)* → tous les mots formés de a et b
Propriétés algébriques essentielles
Loi Signification
r|s=s|r Commutativité
r | (s | t) = (r | s) | t Associativité
r(s|t)=rs|rt Distributivité
εr = rε = r Élément neutre
r* = (r|ε)* ε inclus dans fermeture
r** = r* Idempotence
Exemple 1 : Identificateur en C
Version longue :
lettre → A|B|...|Z|a|...|z|_
chiffre → 0|1|...|9
id → lettre(lettre|chiffre)*
Version simplifiée (avec classes) :
lettre → [A-Za-z_]
chiffre → [0-9]
id → [A-Za-z_][A-Za-z0-9_]*
Extensions modernes
Opérateur Signification
r+ Une ou plusieurs occurrences
r? Zéro ou une occurrence
[abc] a ou b ou c
[a-z] intervalle
Formules importantes :
• r* = r+ | ε
• r+ = rr*
• r? = r | ε
Des exercices du TD1 et 2 :
Exercice :
Soient 𝐿1 = {𝑎𝑏, 𝑏𝑎, 𝜀} et 𝐿2 = {𝑏𝑎, 𝑎𝑎, 𝑏𝑏}.
1. Trouvez 𝐿1 ∪ 𝐿2, 𝐿1 ∩ 𝐿2, et 𝐿1⁄𝐿2.
Réponses : 𝐿1 ∪ 𝐿2 = {𝑎𝑏, 𝑏𝑎, 𝜀, 𝑎𝑎, 𝑏𝑏}, 𝐿1 ∩ 𝐿2 = {𝑏𝑎}, et 𝐿1 \𝐿2 = {𝑎𝑏, 𝜀}.
2. Vérifiez si 𝐿2 ⊆ 𝐿1. Justifiez.
Réponses : non, car 𝑎𝑎 𝑒𝑡 𝑏𝑏 appartiennent à 𝐿2 mais pas à 𝐿1.
Exercice :
Trouvez 𝐿1 𝐿2, où 𝐿1 = {𝑎, 𝑎𝑏} et 𝐿2 = {𝑏, 𝑏𝑏}.
Réponses : 𝐿1 𝐿2 = {𝑎𝑏, 𝑎𝑏𝑏, 𝑎𝑏𝑏𝑏}
Calculez 𝐿 2 et 𝐿 3 pour 𝐿 = {𝑎, 𝑏}.
Réponses : 𝐿 2 = {𝑎𝑎, 𝑎𝑏, 𝑏𝑏, 𝑏𝑎} et 𝐿 3 = {𝑎𝑎𝑎, 𝑎𝑎𝑏, 𝑎𝑏𝑎, 𝑎𝑏𝑏, 𝑏𝑎𝑎, 𝑏𝑎𝑏, 𝑏𝑏𝑎,
𝑏𝑏𝑏}.
Donnez une description de 𝐿 ∗ pour 𝐿 = {𝑎, 𝑏}
Réponse : 𝐿 ∗ contient tous les mots (y compris le mot vide) formés à partir de 𝑎
𝑒𝑡 𝑏 : 𝐿 ∗ = {𝜀, 𝑎, 𝑏, 𝑎𝑎, 𝑎𝑏, 𝑏𝑎, 𝑏𝑏, 𝑎𝑎𝑎, 𝑎𝑏𝑏, … }.
Exercice :
Exercice :
Exercice :
Exercice :
Exercice :
Écrivez une expression régulière qui reconnaît les numéros de téléphone tunisiens
sous les formats suivants : − XX XXX XXX (8 chiffres, sans indicatif) − +216 XX XXX
XXX (avec indicatif international) − 00216 XX XXX XXX (avec indicatif international
alternatif)
Écrivez une expression régulière qui valide une adresse e-mail selon les critères
suivants : − Un nom d'utilisateur composé de lettres, chiffres, points (.), tirets (-),
ou underscore (_). − Un @ obligatoire. − Un nom de domaine composé de lettres
et de points (.). − Une extension de 2 à 6 lettres (ex: .com, .fr).
Partie Signification
^ Début de chaîne
[A-Za-z0-9._-]+ Nom d’utilisateur : lettres, chiffres, ., _, - (au moins 1 caractère)
@ Symbole obligatoire
[A-Za-z.]+ Nom de domaine : lettres et points
\. Point avant l’extension
[A-Za-z]{2,6} Extension de 2 à 6 lettres
$ Fin de chaîne
Exercice :
• Mots de longueur ≤ 2: (a|b){0,2}
• Mots de longueur paire: ((a|b)(a|b))*
• Mots contenant la séquence ab mais pas ba : a+ b+
• Mots contenant au plus l’une des deux séquences ab ou ba a*b* | b*a*
• Chaînes sur {a,b} avec nombre pair de a et nombre impair de b
(aa|bb|(ab|ba)(ab|ba))* b (aa|bb|(ab|ba)(ab|ba))*
• Chaînes formées des 5 voyelles majuscules en ordre : AEIOU
Exercice :
Décrire les langages dénotés par les expressions régulières suivantes :
1. a(a|b)*a
Ensemble des mots :
• qui commencent par a
• qui finissent par a
• et contiennent n’importe quelle combinaison de a et b au milieu
2. ((" |a)*)* €
équivalent à : a*
3. (a|b)*a(a|b)(a|b)
Ensemble des mots sur {a,b} :
• de longueur ≥ 3
• dont le troisième caractère à partir de la fin est ‘a’