Compilation

Bruno Delb http://www.brunodelb.com Date : 12/11/1997

Compilation

Sommaire

ASSEMBLEUR.......................................................................................................3

RÉFÉRENCE AVANT............................................................................................................................3Deux passes.............................................................................................................................3Une passe.................................................................................................................................3

ETAPES...............................................................................................................4

ALLOCATION....................................................................................................................................4SUBSTITUTION..................................................................................................................................4GÉNÉRATION....................................................................................................................................4PLACE LES VARIABLES UTILISÉES DANS DES REGISTRES............................................................................4

LES TYPES DE LANGAGE.......................................................................................5

LANGAGE SANS STRUCTURE PARENTHÉSÉE............................................................................................5LANGAGE AVEC STRUCTURE PARENTHÉSÉE............................................................................................5

LES AUTOMATES RÉCURSIFS (À PILE D'ÉTATS).......................................................6

NOTATION.......................................................................................................................................6EXEMPLE.........................................................................................................................................6

LA GRAMMAIRE....................................................................................................7

AMBIGUITÉ......................................................................................................................................7Définition..................................................................................................................................7Exemple...................................................................................................................................7

RÉCURSIVITÉ À GAUCHE.....................................................................................................................7Définition..................................................................................................................................7Exemple...................................................................................................................................7

DISJONCTION AVEC PREMIERS COMMUNS...............................................................................................8Définition..................................................................................................................................8Exemple...................................................................................................................................8

FORME NORMALE..............................................................................................................................8PREMIER.........................................................................................................................................8SUIVANT.........................................................................................................................................8

Définition..................................................................................................................................8Exemple...................................................................................................................................8

L'AUTOMATE........................................................................................................9

CONSTRUCTION................................................................................................................................9

LA GRAMMAIRE..................................................................................................10

SIMPLIFICATION..............................................................................................................................10Principe..................................................................................................................................10Exemple.................................................................................................................................11

FORME NON NORMALE REPRÉSENTABLE..............................................................................................11Définition................................................................................................................................11Exemple.................................................................................................................................11

DISJONCTION DANS UNE CONJONCTION...............................................................................................11Définition................................................................................................................................11Exemple.................................................................................................................................11

L'AUTOMATE......................................................................................................12

REPRISE SUR ERREUR......................................................................................................................12

1


Compilation

Actions sémantiques.............................................................................................................12Exemple.................................................................................................................................12Format....................................................................................................................................13But..........................................................................................................................................13Inconvénients.........................................................................................................................13

2


Compilation

Assembleur

Référence avant

Deux passes

Le premier parcours constitue la table des symboles et traduit les codes-opérations.

Le deuxième parcours remplit les parties adresses des instructions.

Une passe

Si l'assembleur rencontre un identificateur inexistant dans la table des symboles, il l'installe tout de même dans la table et lui affecte une liste d'attente. Il existe donc encore dans le texte objet des instructions incomplètes.

Les langages évolués travaillent en une seule passe.

3


Compilation

Etapes

Allocation

Elle détermine pour chaque objet du dictionnaire une adresse relative au début du programme objet.

Le compilateur doit engendrer en liste d'instructions symboliques des appels une allocation d'espace mémoire.

Substitution

Substitue les pointeurs de la liste d'instructions symbolique par des adresses dans le texte-objet.

Génération

Elle traduit les instructions symboliques par des instructions machine de l'ordinateur cible.

On peut à ce niveau améliorer le texte (OPTIMISATION).

Place les variables utilisées dans des registres

Le texte objet est placé dans un fichier en format binaire translatable.

Mais les problèmes ne sont pas résolus pour les traducteurs :

remplir les parties-adresses par des CALL

les adresses sont relatives au début du texte-objet, le compilateur ne sait donc pas où sera implanté le programme lors de son exécution.

4


Compilation

Les types de langage

Langage sans structure parenthésée

L'analyseur syntaxique est fondé sur un automate d'états finis.

Ce sont des analyseurs très rapides.

Langage avec structure parenthésée

L'automate doit faire appel à des inclusions sémantiques comptant les parenthèses. +-----------------------------+ ¦ ¦ + ¦ a ¦ b ¦ - ¦ <> ¦ ¦ S0 ¦ S1 ¦ e ¦ e ¦ e ¦ e ¦ ¦ S1 ¦ ¦ S2 ¦ S2 ¦ S1 ¦ ¦ +-----------------------------+

e = message " Reprise sur erreur "

S1, S2 = nom de sous-programme qui fait appel à un sous-programme qui voit si cette variable est dans le sous-programme ou non.

5


Compilation

Les automates récursifs (à pile d'états)

Notation-> = avancer dans le texte suivant = PTEXTE := PTEXTE + 1 . = passer à l'état (ligne) suivant = PILE (SP) := PILE (SP) + 1 v = dépiler = SP := SP - 1 ^ = empiler = ¦ SP := SP + 1 ¦ PILE (SP := n e = cas d'erreur = ¦ afficher un message d'erreur ¦ algorithme de reprise sur erreur end = arrêt de l'analyse = mot syntaxiquement correct omission = arrêt de l'analyse = omission de caractères surplus = arrêt de l'analyse = surplus de caractères /// = cas impossible = situation impossible de l'automate

Exemple+--------------------------------------------------+ ¦ ^3 ¦ e ¦ e ¦ e ¦ omission ¦ +---------+---------+---------+---------+----------¦ ¦ surplus ¦ surplus ¦ surplus ¦ surplus ¦ end ¦ +---------+---------+---------+---------+----------¦ ¦ -> . ¦ /// ¦ /// ¦ /// ¦ /// ¦ +---------+---------+---------+---------+----------¦ ¦ ^7 ¦ ^7 ¦ e ¦ e ¦ omission ¦ +---------+---------+---------+---------+----------¦ ¦ e ¦ e ¦ -> . ¦ e ¦ omission ¦ +---------+---------+---------+---------+----------¦ ¦ v . ¦ v . ¦ v . ¦ v . ¦ v . ¦ +---------+---------+---------+---------+----------¦ ¦ ^3 ¦ -> . ¦ /// ¦ /// ¦ /// ¦ +--------------------------------------------------+

La suite de la pile d'états est : 7 8 3 4 4 4 5 6 7 7 7 7 7 7 7 8 3 4 4 4 4 4 4 4 4 4 5 6 1 1 1 1 1 1 1 1 1 1 1 1 1 2 ((x))?! => surplus (?!) => arrêt de l'analyseur

6


Compilation

La grammaire

Ambiguité

Définition

Une règle est ambigue si et seulement si règle et si Premier (<a>) _ Suivant (<A>) <> 0.

Exemple <A> -> b ¦ * -> ba<C> ¦ L = (ba) b <C> -> _¦ ¦

On peut alors :

modifier le langage ou

modifier la grammaire (exemple : <A> -> b)

laisser venir l'erreur

faire un branchement inter-automates

Récursivité à gauche

Définition

Il y a récursivité à gauche si un élément de V est son propre premier.

Exemple

Exemple : <A> -> <A>¦<C> devient <A> -> <C><T> <T> -> _¦<T>

7


Compilation

Disjonction avec premiers communs

Définition

Il y a disjonction si et seulement si deux termes ont au moins un premier commun.

Exemple <A> -> ¦<C> devient <A> -> <C><T> <T> -> _ ¦<T>

Forme normale

Disjonction et conjonction :

<A> -> xy¦z devient <A> -> ¦z -> xy

Premier

v Premier de <A> ó v _ Premier (<A>) ó il existe une règle du type : ¦ <A> -> <X > ...

¦ 1 ¦ <X > -> <X > ... ¦ 1 2 ¦ .... -> .... ¦ <X > -> v ... ¦ n

Suivant

Définition

v suivant de <A> ó il existe une règle du type : ¦ <S> -> ... <T> ...

¦ <X > -> ... <X > ¦ 1 2 ¦ .... -> .... ¦ <X > -> v ¦ n

Exemple

¦ <A> -> x ¦ <T> -> y<C>d ¦ <C> -> _¦y

ð Suivant () = { x, <C>, Premier (C), d } = { x, <C>, y, d }

8


Compilation

L'automate

Construction

Codage d'un élément de V = ^n

Avec :

n = premier état du sous-automate correspondant à l'élément de V

. = dans les colonnes des premiers de l'élément de V

^ = sortie de sous-automates autres que l'axiome

" surplus " = sortie d'axiome sauf dans la colonne de

" end " (marque de fin de texte)

X = premières lignes de sous-automates autres que

l'axiome (cas impossible)

. = ligne comportant un appel à une règle comportant

" omission " = colonne de " end "

0 = reste (erreur)

9


Compilation

La grammaire

Simplification

Principe

Règle du type <A> -> :

<A> différent de l'axiome

supprimer <A>

remplacer <A> par 

Règle utilisée une seule fois dans une règle de même forme :

la remplacer dans cette dernière règle

la supprimer

10


Compilation

Exemple

<A> -> b<C>d => <A> -> bxyzd <C> -> xyz

Forme non normale représentable

Définition

<A> -> _¦xy

Exemple

<A> -> _¦xy

Disjonction dans une conjonction

Définition

La disjonction de terminaux joue le même rôle. ð suppression de l'automate qui les traite

Exemple

<A> -> xya¦b¦cz

11


Compilation

L'automate

Reprise sur erreur

Actions sémantiques

mémoriser le type

parcours du dictionnaire : nom existant ?

oui => " erreur : double déclaration "

non => placer le nom avec son descripteur (variable, type) dans le dictionnaire

parcours du dictionnaire : identificateur existant ?

oui => mémorisation de son type

non => " erreur : identificateur inexistant "

parcours du dictionnaire : identificateur existant ?

oui => comparer les deux types : identiques ?

oui -> création en LIS d'un appel à un sous-programme de conversion

non => " erreur "

Exemple

Enoncé : entier A, réel B , B <- A

Préexistant :

Dictionnaire :

+-------- descripteur ----------------+ +-------------------------------------+ ¦ Aux ¦ Var ¦ Réel Real ¦ Procedure ¦ +-------------------------------------+ +---------- identificateur -----------+

LIS :

+----------------+ ¦ point d'entrée ¦ +----------------+

12


Compilation

Procédure REAL

Traduction :

AUX <- CALL (A) ¦ => B <- A B <- AUX ¦

Dictionnaire :

+-----------------------------------+ ¦ A ¦ Var ¦ Entier B ¦ Var ¦ Réel ¦ +-----------------------------------+

LIS :

+------ AUX <-> CALL (A) -------+ +---- B <- AUX ----+ +------------------------------------------------------+ ¦ CALL ¦ point d'entrée ¦ A ¦ Aux Affecter ¦ B ¦ Aux | +------------------------------------------------------+

Format

Une unité de programme est un couple module (programme principal, texte-objet, sous-programme) (format « source) et descripteur de module (nom, taille, ...) (format « binaire exécutable).

But

Faire accepter, alternativement, sur la ligne de l'erreur et la suivante, les caractères du texte.

Inconvénients

Erreurs de l'algorithme possibles ð diagnostiques aberrants possibles

13

Technology

Compilation