Compilation.md

Compilation

Mise en forme par Marek Felsoci.

L'USAGE DE CE RÉSUMÉ DE COURS NE PEUT ÊTRE QU'ACADÉMIQUE

Crédits

Ce résumé s'appuie sur les notes du cours de Compilation dispensé par Philippe CLAUSS à l'Université de Strasbourg.

Introduction

Langage de haut niveau → Compilation (tous les mécanismes de traduction et de transformation et les mécanismes utilisés dans d'autres contextes) → Langage machine

Langage intermédiaire

C'est une forme propre à un compilateur comme par exemple GIMPLE et GENERIC utilisés par GCC, LLVM IR utilisé par CLANG ou encore BYTECODE utilisé par Java VM.

Langage d'assemblage

C'est une représentation du code machine à l'aide des symboles mnémoniques traduite à l'aide d'un assembleur.

Applications de type « compilation »

• interpréteur : traduction à la volée des instructions en langage source, lors de l'exécution
• machine virtuelle : interprète les instructions et compile à la volée celles qui sont souvent utilisées
• compilateur statique : tout le programme est compilé avant d'être exécuté (gcc, clang)

Niveau de compréhension de texte d'entrée

1. On appelle une analyse lexicale la reconnaissance de mots dans le texte d'entrée selon une lexique. Les mots reconnus sont alors appelés des unités lexicales, symboles ou encore tokens
2. L'analyse syntaxique représente la vérification de la structure du texte et sa conformité par rapport à une syntaxe définie par une grammaire.
3. Enfin, la compréhension du sens du texte se fait lors de l'analyse sémantique.

Structure de compilateur

La compilation comprend six phases principales :

La table des symboles contient une entrée par identificateur plus les informations liées (type, valeur numérique, valeur lexicale, etc.)

Analyse lexicale

Cette pahse est effectuée par un analyseur lexical qui prend en entrée une suite de caractères et en produit une suite de tokens. Comme par exemple des mots clés, délimiteurs, identificateur, constantes, opérateurs, etc.

Implémentation d'analyseur lexical

La description des unités lexicales se fait à l'aide des expressions rationnelles permettant de les reconnaître par des automates à états finis. L'exécution d'actions liées à la reconnaissance de tokens est en fait une association d'actions sous forme de programmes.

Communication avec l'analyseur syntaxique

Deux possibilités existent pour faire communiquer l'analyseur syntaxique avec l'analyseur lexical. Soit ce dernier est une entité séparée et produit une liste de tokens soit les deux analyseurs forment une seule entité.

Types de tokens

Les tokens peuvent être définis uniquement par un type :

• opérateur d'affectation
• opérateur d'addition
• mot réservé

Mais aussi par un type et une valeur :

• identificateur avec comme valeur son nom (en général une valeur correspond à un pointeur vers la table des symboles)
• entier avec sa valeur

Description de tokens

Différentes façon sont possibles :

• expressions rationnelles
• automates déterministes

Exemple

Reconnaissance d'un identificateur qui est une lettre suivie de lettres ou de chiffres :

Soit L l'ensemble de lettres et N l'ensemble de chiffres. Alors l'expression rationnelle correspondante est L(L|N)^*. Cette dernière décrit l'automate suivant :

Si maintenant on veut reconnaître également des constantes entières ainsi que le mot clé « ELSE » :

Les mots clés sont traités comme des identificateurs en ayant été au préalable installés dans la table des symboles. Lors de la reconnaissance d'un mot clé une entrée correspondate existera déjà dans la table des symboles. Ainsi il n'y a plus besoin de traitement particulier pour les mots clés.

Générateur d'analyseur lexical

On fournit au générateur une description des tokens (expressions rationnelles) ainsi que des actions liées aux tokens (écriture des instructions à exécuter).

Par exemple, pour le langage C on outilise le générateur LEX.

Analyse syntaxique

L'analyse syntaxique a pour but de :

• assurer la conformité d'une suite de tokens par rapport à une grammaire
• effectuer une exhibition de la hiérarchie du texte en établissant un arbre de syntaxe abstraite
• repérer et éventuellement corriger des erreurs
• accéder à la table des symboles
• vérifier les types

Exemple d'arbre de syntaxe abstraite

Soit la suite de tokens suivante :

ID AFF(ID PLUS(ID MULT CST))

Voici alors l'arbre de syntaxe abstraite correspondant :

De plus elle génère le code intermédiaire que l'on appelle aussi le code à trois adresses. C'est le code pour machine abstraite défini comme une séquence d'instructions qui ont au plus trois opérandes.

Il existe deux classes de méthode d'analyse syntaxique :

• les méthodes descendantes ou top-down parsing
• les méthodes ascendantes ou bottom-up parsing notamment utilisées par les générateurs d'analyseurs syntaxiques

Exemple de grammaire

Soit une grammaire G₀ décrivant les expressions arithmétiques :

E → E + T | T
T → T * F | F
F → (E) | id

Notons que les symboles terminaux sont en minuscules tandisque les symboles non-terminaux sont en majuscules.

Analyse syntaxique descendante

La méthode descdendate a une représentation d'un arbre allant de la racine jusqu'aux feuilles. Elle est basée sur les dérivations gauches de tokens d'entrée. Il s'agit de remplacer le symbole terminal se trouvant le plus à gauche.

Exemples d'analyse descedante

Soit (id + id) * id l'expression d'entrée. Alors la liste d'opérations de construction sera comme suit :

gE ⇒ gT ⇒ g * F ⇒ gF * F ⇒ g(E) * F ⇒ g(E + T) * F ⇒ g(T + T) * F ⇒ g(F + T) * F ⇒ g(id + T) * F ⇒ g(id + F) * F ⇒ g(id + id) * F ⇒ g(id + id) * id

Voici l'arbre de syntaxe abstraite résultant :

Prenons maintenant la grammaire suivante :

S → cAd
A → ab | a

Voici le déroulement de l'analyse de la chaîne cad et la construction de l'arbre de syntaxe abstraite :

Problème des retours en arrière

Les retours an arrière lors de l'analyse sont très coûteux. Ces derniers sont dûs à des règles de la forme A → αΒ₁ | ... | αΒ_n avec le même début en partie droite parmi lesquelles l'analyseur ne sait pas choisir.

Ces règles peuvent être supprimées à l'aide de la factorisation à gauche comme suit :

A → αA'
A' → Β₁ | ... | Β_n

Problème de la récursivité à gauche

La récursivité à gauche risque de provoquer des bouclages infinis qui sont alors dûs à la présence de règles récursives à gauche. La récursivité peut être :

• directe : A → Aα
• indirecte : A → Bα et B → Aβ

Dans le cas simple il est possible de dérécursiver une règle de la forme A → Aα | Β en la séparant en deux règles telles que A → ΒA' et A' → αA' | ε.

Si on généralise alors tout règle de la forme A → Aα₁ | ... | Aα_n | Β₁ | ... | Β_k peut être transformée en :

A → Β₁A' | ... | Β_kA'
A' → α₁A' | ... | α_mA' | ε

Exemple de la dérécursivation de grammaire

Reprenons la grammaire G₀ des expressions arithmétiques :

E → E + T | T
T → T * F | F
F → (E) | id

Après la dérécursivation décrite plus haut on obtient la grammaire équivalente suivante :

E → TE'
E' → +TE' | ε
T → FT'
T' → *FT' | ε
F → (E) | id

Pour éliminer des récursivités indirectes l'idée est pour toutes les règles de la forme A → Bα et B → AΒ d'anticiper les règles problématiques A → AΒα puis éliminer la récursivité directe avec la méthode précédente.

Dans le cas général on applique l'algorithme suivant :

Soit A[1] | ... | A[n] une liste ordonnée des symboles non-terminaux.

POUR i DE 1 À n FAIRE
    POUR j DE 1 À n-1 FAIRE
        SI A[i] --> A[j]a existe ALORS
            remplacer la règle par A[i] --> B[1]a | ... | B[m]a avec A[j] --> B[1] | ... | B[m]
        FIN SI
    FIN POUR    
    éliminer la récursivité directe
FIN POUR    

Problème de coût

L'algorithme précédant est coûteux comme il implique la recherche des règles applicables ainsi que des opérations de modification de l'arbre.

La première solution est l'analyse par descente récursive.

Exemple

Prenons la grammaire suivante :

S → cAd
A → ab | a

FONCTION S {
    match(c); A; match(d);
}

FONCTION A {
    match(a);
    SI token_courant == b ALORS
        match(b);
    FIN SI    
}

FONCTION match(t) {
    SI token_courant == t ALORS
        token_courant = token_suivant;
    SINON
        erreur;
    FIN SI;
}

La deuxième solution est l'utilisation d'une pile comme dans l'analyse itérative LL(1).

Analyse LL(1)

Le premier L de l'appelation LL(1) signifie l'analyse à droite, le deuxième L indique la dérivation à gauche et le 1 veut dire que l'on lit un token d'avance.

Les principes de cette méthode sont les suivants :

• utilisation d'un pointeur sur le token courant
• terminaison de la chaîne d'entrée par $
• utilisation des symboles terminaux et non-terminaux dans la pile
• utilisation d'une table d'analyse T

La table d'analyse contient une ligne par symbole terminal ou non-terminal. On notera T[A, a] la règle de grammaire à appliquer lorsque A est au somment de la pile et a est le token courant. Ensuite à chaque itération on applique l'algorithme suivant :

SI le sommet X est un terminal ALORS
    SI X == token_courant == $ ALORS
        terminer avec succès
    SINON SI X == token_courant != $ ALORS
        dépiler X et avancer le pointeur
    SINON  
        erreur
    FIN SI
SINON SI X est un non-terminal ALORS
    SI T[X, token_courant] == {X --> Y[1]...Y[n]} ALORS
        on dépile X et on empile la prtie droite de la règle dans l'ordre inverse Y[n]...Y[1]
    SINON SI T[X, token_courant] est vide ALORS
        erreur
    FIN SI
FIN SI

Exemple d'analyse LL(1)

Reprenons la grammaire G₀ dérécursivée des expressions arithmétiques :

E → TE'
E' → +TE' | ε
T → FT'
T' → *FT' | ε
F → (E) | id

Soit la table d'analyse suivante :

	id	+	*	(	)	$
E	E → TE'			E → TE'
E'		E → +TE'			E' → ε	E' → ε
T	T → FT'			T → FT'
T'		T' → ε	T' → *FT'		T' → ε	T' → ε
F	F → id			F → (E)

Analysons l'expression id + id * id :

Pile	Chaîne d'entrée
$E	id + id * id$
$E'T	id + id * id$
$E'T'F	id + id * id$
$E'T'id
$E'T'	+id * id$
$E'	+id * id$
$E'T+
$E'T	id * id$
$E'T'F
$E'T'id
$E'T'	*id$
$E'T'F*
$E'T'F	id$
$E'T'id
$E'T'	$
$E'	$
$	$

Table d'analyse

Avant de pouvoir construire la table d'analyse il faut déterminer deux ensembles associés à la grammaire qui sont l'ensemble First et l'ensemble Follow. Pour la suite nous allons utiliser une chaîne de terminaux et non-terminaux α et un non-terminal A.

First représente l'ensemble des symboles terminaux qui peuvent se trouver au début des dérivations de α. D'autre part l'ensemble Follow contient des symboles terminaux qui peuvent se trouver juste après A dans une des dérivations.

Soit une grammaire G = (V, Σ, R, S) où V est l'ensemble de non-terminaux, Σ l'ensemble des terminaux, R les règles et S le symbole le plus général. Nous avons alors :

First(α) = { a ∈ Σ | ∃ β ∈ (V ∪ Σ), α ⇒ aβ }
Follow(A) = { a ∈ Σ | ∃ α, β ∈ (V ∪ Σ), S ⇒ αAaβ } ∪ { $, si ∃ α ∈ (V ∪ Σ)^*, S ⇒ αA }_{si A est à la fin de chaîne on inclut aussi $}

Calcul de l'ensemble First

Soit a un symbole terminal quelcoonque.

• First(x) :
  • si x ∈ Σ alors First(x) = { x }
  • si x ∈ V alors : pour toutes les règles de la forme X → Y₁...Y_n ajouter a si ∃ i ∈ [1...n] | ε ∈ (First(Y₁) ∩ ... ∩ First(Y_{i - 1})) et a ∈ First(Y_i)
• First(x₁...x_n) :
  • ajouter tous les terminaux de First(x₁)
  • ajouter tous les terminaux de First(x₂) ⇔ ε First(x₁)
  • ajouter tous les terminaux de First(x₃...x_n) ⇔ ε ∈ (First(x₁) ∩ ... ∩ First(x_{n - 1}))

Exemple de calcul de First

Reprenons la grammaire G₀ dérécursivée des expressions arithmétiques :

E → TE' (si T pouvait se dériver en ε on devrait vérifier aussi E) E' → +TE' | ε
T → FT' (T ne commence pas par un terminal mais il faut regarder toutes les dérivations possibles de T donc on vérifie F) T' → *FT' | ε
F → (E) | id

First(F) = {(, id}
First(T') = {*, ε}
First(T) = {(, id} = First(F)
First(E') = {+, ε}
First(E) = {(, id} = First(F)

Calcul de l'ensemble Follow

• En premier, il faut inclure $ dans Follow(S).
• S'il existe une règle de la forme A → αBβ alors on ajoute First(β) - {ε} à Follow(B).
• S'il existe une règle de grammaire de la forme A → αB ou de la forme A → αBβ avec ε ∈ First(β) alors on ajoute Follow(A) à Follow(B).

Exemple de calcul de Follow

Reprenons la grammaire G₀ de l'exemple précédent :

Nous allons rechercher les règles où E apparait ) droite de quelque chose.

Follow(E) = {), $} car E = S
Follow(E') = {), $} = Follow(E) Follow(T) = {+, ), $} Follow(T') = {+, ), $} = Follow(T) (T' va être réduit en T donc tout ce qui suit T' suit aussi T) Follow(F) = {*, +, ), $} (ε ∈ T' donc tout ce qui suit F suit aussi T)

Construction de la table d'analyse

Pour chaque règle de la forme A → α affecter A rarr; α à T[A, a] pour tout a appartenant à First(α) - {ε}. Si ε appartient à First(α) affecter α à T[A, b] pour tout b appartenant à Follow(A).

	id	+	*	(	)	$
E	E → TE'			E → TE'
E'		E → +TE'			E' → ε	E' → ε
T	T → FT'			T → FT'
T'		T' → ε	T' → *FT'		T' → ε	T' → ε
F	F → id			F → (E)

Remarque : S'il y a plus qu'une règle par case de la table alors la grammaire est ambiguë !

Analyse syntaxique ascendante

La méthode descdendate a une représentation d'un arbre allant des feuilles jusqu'à la racine. Elle est basée sur les dérivations droites de tokens d'entrée. Il s'agit de remplacer le symbole terminal se trouvant le plus à droite.

Exemple d'analyse ascedante

Soit (id + id) * id l'expression d'entrée. Alors la liste d'opérations de construction sera comme suit :

g(id + id) * id ⇒ g(id + id) * F ⇒ g(id + F) * F ⇒ g(id + T) * F ⇒ g(F + T) * F ⇒ g(T + T) * F ⇒ g(E + T) * F ⇒ g(E) * F ⇒ gF * F ⇒ g * F ⇒ gT ⇒ gE

Voici l'arbre de syntaxe abstraite résultant :

À chaque étape on examine le sommet de la pile en prenant en compte plusieurs de ses éléments à la fois. Ces éléments au sommet doivent correspondre au préfixe des parties droites d'une ou de plusieurs règles de grammaires. C'est ce que l'on appelle un préfixe viable. Au cas où aucun préfixe ne correspond au sommet on effectue l'action shift qui correspond à l'empilement du token courant et l'avancement du pointeur sur la chaîne d'entrée. Au cas où une partie droite correspond au sommet on effectue à la fois les actions shift et reduce. Autrement dit, on dépile tous les éléments correspondant à la partie droite et on empile le symbole de la partie gauche.

Exemple

On procède par retours-arrière éventuels jusqu'à ce qu'il ne reste plus que S dans la pile et plus de tokens à l'entrée.

Exemple

Reprenons la grammaire G₀ sans multiplication :

E → E + T E → T T → (E) T → id

pile	chaîne d'entrée	action	règle
	id + (id + id)	shift
id	+ (id + id)	reduce	T → id
T	+ (id + id)	reduce	E → T
E	+ (id + id)	shift
E+	(id + id)	shift
E+(	id + id)	shift
E+(id	+ id)	reduce	T → id
E+(T	+ id)	reduce	E → T
E+(E	+ id)	shift
E+(E+	id)	shift
E+(E+id	)	reduce	T → id
E+(E+T	)	reduce	E → E + T
E+(E	)	shift
E+(E)		reduce	T → (E)
E+T		reduce	E → E + T
E

Problèmes à résoudre

• Comment choisir entre shift et reduce ?
• Comment choisir entre plusieurs reduce ?

Solution

L'analyseur doit non seulement prendre en compte le token courant et le sommet de la pile mais également tout le reste de la pile. Cette stratégie implique l'utilisation d'états qui représentent toute la pile et donc les situations que l'on peut rencontrer au niveau de la pile au cours d'analyse. Voir L'analyse LR (Left-to-right, Rightmost).

Analyse LR

Ce type d'analyse implique l'utilisation d'un pointeur sur la chaîne d'entrée suffixée par $ ainsi que d'une pile avec des états décrivant le contenu de la pile qui est de la forme S₀X₀S₁X₁...X_{m - 1}S_m où S est un état et X un symbole terminal ou non-terminal ou encore $.

Analyse LR utilise également une table d'analyse ayant deux parties.

La partie ACTION comprend une ligne par état et une colonne par symbole terminal. Ainsi ACTION[S_i, a] peut contenir :

• shift S_j où S_j est un état : on empile a puis S_j et on avance le pointeur
• reduce r_k où k est le numéro d'une règle : soit A → β la k^e règle et soit L la longueur de β alors on dépile L éléments, on empile A et on empile l'état GOTO[S_i, A] où S_i est l'état courant
• accept
• erreur

La partie GOTO comprend une ligne par état et une colonne par symbole non-terminal. Ainsi GOTO[S_i, A] contient le nouvel état à empiler.

Analyse SLR

C'est la version simplifiée de l'analyse LR.

Grammaire augmentée

Il s'agit du remplacement de la grammaire G par une grammaire G' telle que G' = (V ∪ {S'}, Σ, R ∪ {S' → S}, S').

Règle pointée

C'est l'utilisation d'un point dans la partie droite des règles afin de représenter ce qui a déjà été reconnu par l'analyse autrement dit ce qui a déjà passé par le sommet de la pile (A → α . β).

État

L'état est représenté par un ensemble de règles pointées susceptibles d'être appliquées dans la suite de l'analyse avec le même préfixe viable.

Construction de l'état initial

Pour construire l'état initial on utilise une opération de fermeture sur les règles pointées.

Si A → α . Bβ appartient à l'état S alors on s'attend à rencontrer une sous-chaîne dérivable à partir de Bβ. Donc s'il existe une règle B → γ alors on s'attend à rencontrer une sous-chaîne dérivable à partir de γ. B → . γ doit appartenir à l'état S.

L'opération de fermeture consiste à ajouter à un état S toutes les règles pointées qui doivent s'y trouver. L'état initial est égal à la fermeture de {S' → .S} où S est la règle la plus générale de la grammaire augmentée.

Exemple

Soit G₀ une grammaire augmentée composée des règles suivantes :

E' → E
E → E + T
E → T
T → T * F
T → F
F → (E)
F → id

L'état initial S₀ est égal à la fermeture({E' → .E}) qui correspond à {E' → .E, E → .E + T, E → .T, T → .T * F, T → .F, → .(E), F → .id}.

Construction des états suivants

Dans cette phase on utilise l'opération GOTO. L'idée est que si S est un état qui correspond à un préfixe viable α alors GOTO(S, X) est un état qui correspond au préfixe viable αX. GOTO(S, X) est égal à la fermeture de toutes les règles de la forme A → αX.β et telles que A → α.Xβ ∈ S.

Exemple

En reprenant l'exemple précédent on calcule les états suivants comme suit :

s₁ = GOTO(s₀, E) = {E' → E., E → E. + T} (pas de fermeture à appliquer étant donné que le point est suivi de ε et d'un non-terminal)

s₂ = GOTO(s₀, T) = {E → T., T → T. * F}

s₃ = GOTO(s₀, F) = {T → F.}

s₄ = GOTO(s₀, « ( ») = {F → (.E), E → .E + T, E → .T, T → .T * F, T → .F, F → .(E), F → .id}

s₅ = GOTO(s₀, id) = {F → id}

s₆ = GOTO(s₁, +) = {E → E +. T, T → .T * F, T → .F, F → .(E), F → .id}

s₇ = GOTO(s₂, *) = {T → T *. F, F → .(E), F → .id}

s₈ = GOTO(s₄, E) = {F → (E.), E → E. + T}

s₉ = GOTO(s₆, T) = {E → E + T., T → T. * F}

s₁₀ = GOTO(s₇, F) = {T → T * F.}

s₁₁ = GOTO(s₈, « ) ») = {F → (E).}

Construction de la table d'analyse

La partie ACTION :

• Si A → α.aβ ∈ s_i alors ACTION[s_i, a] = shift s_j où s_j = GOTO(s_i, a).
• Si A → α. ∈ s_i et si A ∉ s' alors ACTION[s_i, a] = reduce r_k où k est le numéro de la règle A → α et ∀a ∈ Follow(A).
• Si S' → S ∈ s_i alors ACTION[s_i, $] = accept.

La partie GOTO :

• GOTO(s_i, A) = s_j où s_j est un état obtenu en appliquant l'opération GOTO(s_i, A).