Théorie des langages : Cours compilation langages de programmation
Télécharger PDFLangages de programmation
Les langages de programmation se classent en plusieurs catégories :
Langage machine
Code binaire directement exécutable par un ordinateur.
Langage assembleur
Utilise des mnémoniques pour coder les instructions (add, mul, bra, etc.). Il est très proche du langage machine.
Langage de haut niveau
Utilise des structures de contrôle (tests, boucles, appels de fonctions, etc.). Le programme est proche du langage naturel.
Styles de programmation
Différents paradigmes existent pour structurer un programme :
Programmation structurée / impérative
Un programme est un ensemble de procédures et de fonctions qui opèrent sur des structures de données.
Exemples : C, Pascal, Fortran, Basic, Cobol, Algol.
Programmation fonctionnelle
Basée sur le paradigme d’évaluation de fonctions mathématiques.
Exemples : Lisp, Scheme, Caml, Haskell.
Programmation logique
On définit une base de faits (propositions vraies) et une base de règles (relations logiques). Un moteur d’inférence permet d’extraire les réponses justes à une requête.
Exemples : Prolog.
Programmation orientée objet
Un programme est un ensemble d’objets qui coopèrent pour réaliser les fonctions du système logiciel.
Exemples : Java, C++, OCaml, Objective-C, Ada, Simula, Smalltalk.
Exemple : Calcul de la factorielle
En programmation structurée (C) :
#include <stdio.h>
main() {
int n, k, res;
scanf("%d", &n);
res = 1;
for(k = 2; k <= n; k++)
res *= k;
printf("%d", res);
}En programmation logique (Prolog) :
predicates factorielle(integer, integer)
clauses
factorielle(1, 1).
factorielle(n, res) :- n > 1,
k = n - 1,
factorielle(k, resk),
res = resk * n.
Goal : factorielle(3, X)
X = 6En programmation fonctionnelle (Scheme) :
(define factorielle (lambda (n)
(if (zero? n) 1
(* n (factorielle(- n 1))))))Remarque : Le seul langage directement exécutable par l’ordinateur est le langage machine (code binaire).
Qu’est-ce qu’un compilateur ?
Un compilateur est un programme qui lit un programme écrit dans un langage source et le traduit en un programme équivalent dans un langage cible. Il repère et signale également les erreurs évidentes commises par le programmeur.
Exemples de langages compilés
Fortran, Basic, C, Pascal, C++, Simula, Smalltalk, Cobol.
Différence entre un compilateur et un interpréteur
Un compilateur traduit entièrement le programme source en code machine avant son exécution, tandis qu’un interpréteur analyse et exécute les instructions une par une.
Exemples d’interpréteurs
Lisp, Prolog, Matlab, Shell de Unix, Scheme.
Analogie avec les langages naturels
Un compilateur répond à une question complète (ex : "Quelle heure est-il ?") par une réponse finale ("Il est 9h35"). Un interpréteur traite chaque instruction séparément (ex : "Quelle heure est-il ?" → "Il est 9h35").
Phases d’un compilateur
Le processus de compilation se divise en deux grandes parties : l’analyse et la synthèse.
Partie analyse (frontend)
Scinde le texte du programme source en ses constituants et crée une représentation intermédiaire.
Partie synthèse (backend)
Construise le programme cible à partir de la représentation intermédiaire.
Modules de la partie analyse
L’analyseur lexical (scanner), l’analyseur syntaxique (parser), et l’analyseur sémantique (vérificateur de types).
Modules de la partie synthèse
La génération de code intermédiaire, l’optimisation, la génération de code cible, l’assemblage et l’édition de liens.
La table des symboles
La table des symboles enregistre les identifiants (variables) et leurs attributs (emplacement mémoire, type, portée). Chaque nouvel identificateur est ajouté par l’analyseur lexical, tandis que les attributs sont calculés ultérieurement par l’analyseur sémantique.
L’analyseur lexical
L’analyseur lexical prend en entrée le flot de caractères du programme source et produit les unités lexicales (tokens). Il ignore les espaces, les commentaires et les caractères superflus.
Exemple de tokenisation
Pour l’instruction position = origine + vitesse * 60;, les tokens générés sont :
- L’identificateur "position"
- L’opérateur d’affectation "="
- L’identificateur "origine"
- L’opérateur d’addition "+"
- L’identificateur "vitesse"
- L’opérateur de multiplication "*"
- Le nombre 60
- Le séparateur ";"
Détection des erreurs lexicales
L’analyseur lexical signale une erreur si un mot n’est pas reconnu par le langage, comme :
- Un mot-clé mal orthographié (ex : "Main" au lieu de "main")
- Un identificateur commençant par un chiffre (ex : "1position")
- Un caractère non alphanumérique dans un identificateur (ex : "position@")
Analogie avec les langages naturels
L’analyse lexicale correspond à l’analyse orthographique : la phrase "Tu manger de le confiture chaud" est correcte au niveau lexical mais incorrecte grammaticalement et sémantiquement.
L’analyseur syntaxique
L’analyseur syntaxique prend en entrée le flot d’unités lexicales et produit les unités syntaxiques (arbres syntaxiques). Il vérifie la grammaire du programme en appliquant des règles de production.
Exemple de règles syntaxiques
Pour l’instruction position = origine + vitesse * 60;, les règles suivantes sont appliquées :
- Tout identificateur ou nombre est une expression.
- Une combinaison d’expressions avec des opérateurs (addition, multiplication) est aussi une expression.
- Une affectation d’un identificateur à une expression est une instruction valide.
Arbre syntaxique abstrait (AST)
L’analyseur syntaxique produit un AST compact, sans les nœuds de règles, mais uniquement les opérateurs et opérandes. Exemple :
= position
+ origine
* vitesse
60L’analyseur sémantique
L’analyseur sémantique vérifie la cohérence des types et des opérations dans le programme. Il utilise l’AST pour identifier les erreurs comme :
- Multiplication entre un entier et un réel (nécessite une conversion explicite).
- Division par zéro ou calculs sur des valeurs invalides.
- Utilisation d’un identificateur hors de sa portée.
- Doubles déclarations d’identifiants.
- Erreurs de flot d’exécution (ex : "break" hors d’une boucle).
Exemple de vérification de type
Pour l’instruction position = origine + vitesse * 60;, si "position", "origine" et "vitesse" sont de type réel, l’analyseur sémantique détecte la multiplication entre un entier (60) et un réel (vitesse). Il ajoute une conversion explicite dans l’AST.
Le générateur de code intermédiaire
Après l’analyse sémantique, certains compilateurs produisent une représentation intermédiaire (ex : code à 3 adresses) pour simplifier la traduction en langage cible.
Exemple de code à 3 adresses
Pour l’instruction position = origine + vitesse * 60;, le code intermédiaire est :
temp1 := EntierVersRéel(60);
temp2 := vitesse * temp1;
temp3 := origine + temp2;
position := temp3;L’optimiseur de code intermédiaire
L’optimiseur améliore le code intermédiaire pour accélérer l’exécution et réduire l’espace mémoire. Il peut fusionner des opérations ou simplifier des conversions.
Exemple d’optimisation
Le code optimisé pour position = origine + vitesse * 60; devient :
temp1 := vitesse * 60.0;
position := origine + temp1;Le générateur de code cible
La dernière phase produit le code cible (assembleur ou machine) en allouant la mémoire et en traduisant les instructions intermédiaires.
Exemple de code assembleur
Pour le code optimisé, une traduction possible avec les registres R1 et R2 est :
MOVF vitesse, R2
MULF #60.0, R2
MOVF origine, R1
ADDF R2, R1
MOVF R1, positionLes cousins du compilateur
D’autres outils interviennent dans le processus de compilation :
Les préprocesseurs
Ils transforment le texte source avant la compilation, par exemple en incluant des fichiers ou en remplaçant des macros.
Les assembleurs
Ils traduisent le code assembleur (mnémoniques) en code machine binaire.
Les éditeurs de liens
Ils combinent plusieurs fichiers binaires pour créer un programme exécutable unique.
Outils pour la compilation
Des outils spécifiques existent pour générer les modules d’un compilateur :
- Analyseurs lexicaux : Lex, Flex, Ocamlex, JFlex, TPlex, PLY.
- Analyseurs syntaxiques : Yacc, Bison, CUP.
Caractéristiques d’un bon compilateur
Un compilateur efficace doit produire un code correct, rapide et optimisé. Il doit également offrir des messages d’erreurs précis, un temps de réponse court et des fonctionnalités de débogage.
FAQ
Qu’est-ce qu’un langage de haut niveau ?
Un langage de haut niveau utilise des structures proches du langage naturel, comme des boucles, des tests et des fonctions, pour faciliter la programmation.
Comment un compilateur diffère-t-il d’un interpréteur ?
Un compilateur traduit tout le programme source en code machine avant son exécution, tandis qu’un interpréteur exécute chaque instruction directement sans traduction complète.
À quoi sert la table des symboles dans un compilateur ?
La table des symboles enregistre les identifiants et leurs attributs pour vérifier la cohérence des types et des portées lors de l’analyse sémantique.