Techniques de compilation

Ce document couvre les techniques fondamentales de compilation destinées aux étudiants en informatique. Il présente les concepts clés liés à la théorie des langages, à l’analyse syntaxique, sémantique, ainsi qu’à la génération de code intermédiaire et machine. Il s’adresse à ceux qui souhaitent comprendre le fonctionnement interne des compilateurs et leur construction.

Introduction à la compilation

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 signale également les erreurs présentes dans le programme source. L’évolution des langages de programmation a conduit des langages machine et assembleur vers des langages évolués comme C, PASCAL, ADA, PROLOG, et des langages de 4ème génération.

Les phases principales d’un compilateur sont :

• Analyse lexicale
• Analyse syntaxique
• Analyse sémantique
• Traduction en code intermédiaire
• Optimisation de code
• Génération de code machine

Le processus est divisé en une partie frontale (analyse) et une partie terminale (génération de code). La partie frontale est indépendante de la machine cible, ce qui permet de ne modifier que la partie terminale lors d’un changement de machine.

Grammaires non contextuelles

Une grammaire non contextuelle est un quadruplet G = (V, T, S, R) où :

• V est l’ensemble des symboles non terminaux
• T est l’ensemble des symboles terminaux
• S est le symbole de départ (axiome)
• R est l’ensemble des règles de production de la forme A → u où u ∈ (V ∪ T)*

Exemples de grammaires :

Expressions arithmétiques

Grammaire générant les expressions avec opérateurs +, * et chiffres 0 à 9 :

Exp → Exp + Exp
Exp → Exp * Exp
Exp → (Exp)
Exp → 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Expressions booléennes

Grammaire générant les expressions booléennes avec opérateurs arithmétiques, relationnels et booléens :

Expb → non(Expb)
Expb → Expb et Expb
Expb → Expb ou Expb
Expr → Expa oprel Expa
Expa → id | nb | (Expa) | Expa oparith Expa

avec oprel ∈ {<, >, <=, >=, <>, =} et oparith ∈ {+, *, /, -}

Programme simple

Grammaire générant un programme avec déclarations, instructions conditionnelles et affectations :

Program id S_DCL Début S_INST Fin

S_DCL → DCL | DCL S_DCL
DCL → Var L_id : TYPE ;
L_id → id | id , L_id
TYPE → entier | réel

S_INST → INST | INST S_INST
INST → id := Expa ;
     | Si Expb alors S_INST Fin Si
     | Si Expb alors S_INST Sinon S_INST Fin Si

Expb, Expr, Expa comme précédemment

Exemple de programme généré :

Program test
Var a, b : entier;
Début
a := 10;
Si a >= 10 alors a := 20; Fin Si
Fin

Phases de compilation détaillées

Analyse lexicale

Cette phase lit le flot de caractères du programme source et le segmente en unités lexicales (UL), qui sont des suites de caractères ayant une signification collective (mots clés, identificateurs, nombres, opérateurs, etc.). Ces unités lexicales sont les terminaux de la grammaire.

Exemple : pour l’expression position := initiale + vitesse * 60, l’analyse lexicale produit :

Lexème	Unité lexicale
position	id
:=	opaff
initiale	id
+	oparith
vitesse	id
*	oparith
60	nb

Analyse syntaxique

Cette phase vérifie que la suite d’unités lexicales est conforme à la grammaire du langage. Elle construit un arbre syntaxique dont les feuilles correspondent aux unités lexicales parcourues de gauche à droite.

Analyse sémantique

Elle vérifie la cohérence du programme (contrôle de type, portée des identificateurs, etc.). Par exemple, dans l’expression vitesse * 60, si vitesse est réel et 60 un entier, la conversion de 60 en réel est nécessaire.

Traduction en code intermédiaire

Le programme est traduit en instructions dans un langage intermédiaire, par exemple un langage pour machine à pile ou un langage proche du C.

Optimisation et génération de code machine

Le code intermédiaire est optimisé puis traduit en code machine spécifique à la cible.

Analyse lexicale : Automates finis et expressions régulières

L’analyseur lexical utilise des automates finis pour reconnaître les unités lexicales. Chaque unité lexicale correspond à un modèle défini par une expression régulière.

Exemple d’automate pour reconnaître l’opérateur >= :

État 0 --(>)--> État 1
État 1 --(=)--> État 2 (reconnaît >=)
État 1 --(autre)--> État 3 (reconnaît >, recule d’un caractère)

Un autre automate peut reconnaître les identificateurs et mots clés :

État 0 --(lettre)--> État 1
État 1 --(lettre ou chiffre)--> État 1
État 1 --(autre)--> État 2 (fin de l’identificateur, recule d’un caractère)

Les fonctions RangerId() et UnilexId() permettent de gérer la table des symboles en différenciant mots clés et identificateurs.

Spécification des unités lexicales par expressions régulières

Les expressions régulières sont utilisées pour définir formellement les unités lexicales :

• Lettre = A|B|...|Z|a|b|...|z
• Chiffre = 0|1|...|9
• id = Lettre (Lettre | Chiffre)*
• nb = Chiffre+

Exemple : id correspond à une chaîne commençant par une lettre suivie de lettres ou chiffres.

Reconnaissance des unités lexicales

Considérons la grammaire partielle :

Instr → si expr alors instr
       | si expr alors instr sinon instr
       | id opaff id pv
       | id opaff nb pv

expr → terme oprel terme | terme
terme → id | nb

Les unités lexicales sont définies par :

• si, alors, sinon : mots clés
• oprel : opérateurs relationnels < (<, <=, =, <>, >, >=)
• id : identificateurs (lettre suivie de lettres ou chiffres)
• nb : nombres (suite de chiffres)
• opaff : opérateur d’affectation :=
• pv : point-virgule ;

Exemple d’analyse lexicale pour la phrase :

si a1 >= b alors a1 := 10;

Retourne la séquence d’unités lexicales :

Lexème	Unité lexicale	Attribut
si	si	0
a1	id	1
>=	oprel	PGE
b	id	2
alors	alors	0
a1	id	1
:=	opaff	0
10	nb	10
;	pv	0

Code C d’un analyseur lexical simplifié

#include <stdio.h>
#include <ctype.h>

int NumLigne = 1;
int ValLex = -1; // Valeur lexicale

int AnalLex() {
    int T;
    while (1) {
        T = getchar();
        if (T == ' ' || T == '\t')
            ; // Ignore espaces et tabulations
        else if (T == '\n')
            NumLigne++;
        else if (isdigit(T)) {
            ValLex = T - '0';
            T = getchar();
            while (isdigit(T)) {
                ValLex = ValLex * 10 + (T - '0');
                T = getchar();
            }
            ungetc(T, stdin);
            return NB; // Retourne unité lexicale nombre
        } else {
            ValLex = -1;
            return T; // Retourne caractère lu
        }
    }
}

Compilateur en une seule passe

Un compilateur en une seule passe parcourt le fichier source une seule fois. L’analyseur lexical fournit simultanément :

• Les unités lexicales à l’analyseur syntaxique
• Les types des identificateurs à l’analyseur sémantique
• Les attributs des unités au traducteur en code intermédiaire (valeur des nombres, opérateurs, etc.)

Définition de la syntaxe par grammaire non contextuelle

Une grammaire G = (V, T, S, R) définit la syntaxe d’un langage :

• V : symboles non terminaux
• T : symboles terminaux (unités lexicales)
• S : axiome (symbole de départ)
• R : règles de production A → u avec u ∈ (V ∪ T)*

Exemple de grammaire pour instructions d’affectation :

V = {INST, EXP}
T = {id, :=, +, -, *, /, (, ), ;}

INST → id := EXP ;
EXP → id | nb | (EXP) | EXP + EXP | EXP * EXP | EXP - EXP | EXP / EXP

Exemple de mot généré :

id := id + (id * nb);

Ce mot est généré par la dérivation :

INST
→ id := EXP ;
→ id := EXP + EXP ;
→ id := id + EXP ;
→ id := id + (EXP) ;
→ id := id + (EXP * EXP) ;
→ id := id + (id * EXP) ;
→ id := id + (id * nb) ;

Glossaire des termes clés

• Analyse lexicale (AL) : phase qui segmente le programme source en unités lexicales.
• Analyse syntaxique (AS) : phase qui vérifie la conformité des unités lexicales à la grammaire et construit l’arbre syntaxique.
• Analyse sémantique (Asem) : phase qui vérifie la cohérence sémantique du programme (types, portée, etc.).
• Unité lexicale (UL) : élément lexical minimal (mot clé, identificateur, nombre, opérateur).
• Lexème : suite de caractères correspondant à une unité lexicale.
• Grammaire non contextuelle : ensemble de règles définissant la syntaxe d’un langage, où les règles sont indépendantes du contexte.
• Automate fini : modèle mathématique utilisé pour reconnaître des unités lexicales.
• Expression régulière : notation formelle pour décrire des ensembles de chaînes de caractères (modèles d’unités lexicales).
• Table des symboles : structure contenant les identificateurs et leurs attributs (type, adresse, etc.).
• Compilateur en une seule passe : compilateur qui analyse et traduit le programme source en une seule lecture.

Points clés à retenir

• La compilation est un processus en plusieurs phases : analyse lexicale, syntaxique, sémantique, puis génération de code.
• Les unités lexicales sont reconnues grâce à des automates finis basés sur des expressions régulières.
• Une grammaire non contextuelle définit la syntaxe du langage et permet de vérifier la correction syntaxique.
• La table des symboles est essentielle pour gérer les identificateurs et leurs attributs.
• Un compilateur en une seule passe optimise le traitement en fournissant toutes les informations nécessaires à chaque phase dès la première lecture.
• L’analyse sémantique assure la cohérence des types et peut insérer des conversions automatiques.