Introduction

Le problème : Homme et machine n'utilisent pas la même langage.

Homme Machine
langage de programmation langage machine
basé s/ modèles mathématiques reflète architecture matérielle
Structuration, modularité au niveau binaire, manipulation de registres

⇒ besoin de réaliser la traduction d'un langage source vers un langage cible.

Les Différents Niveaux de Langage

langage machine

suite binaire directement interprétable par la machine. Les opérations et opérands de chaque instruction du jeu d'instructions sont spécifiés par un code machine, par une suite de 0 et 1.

langage d'assemblage

proche du langage machine mais on remplace les codes machine par des symboles mnémoniques qui sont beaucoup plus facile à retenir.

exemple

ADDF  R1,R2

nécessite une traduction (vers langage machine) et le traducteur est appelé assembleur.

langage de haut niveau

Basés sur un modèle mathématique, bien adaptés à l'expression des algorithmes et des structures de données. En plus, indépendants des jeu d'instruction de la machine. Ils nécessitent une traduction dont la complexité et “proportionnelle” au niveau du langage. Le traducteur est appelé compilateur.

langage de commande

Permet de communiquer avec le système d'exploitation. Son rôle essentiel est de lancer les executables (écrit en langage machine).

Les Outils de Traduction

On peut distinguer deux types d'outil:

  1. Interpreteur
    1. traduit un code écrit dans un langage source en un code écrit dans un langage intermédiaire (plus haut niveau que le langage machine)
    2. execute le code intermédiaire
  2. Traducteur
    1. prend en entrée un code écrit dans un langage source et produit en sortie un code objet qui contient du code machine et d'autres informations nécessaires à l'éditeur de liens et au débogage.
    2. le traducteur est appelé assembleur lorsque le langage source est un langage d'assemblage et compilateur lorsque le langage source est de haut niveau.

Les Cousins du Compilateur

Avec l'utilisation de techniques de génie logiciel (modularité, généricité) la création d'un code exécutable nécessite plusieurs autres outils.

  • Le pré-processeur : Le programme source est morcelé, stocké dans des fichiers separés. La tâche est de reconstituer le programme source.
  • L'éditeur de liens : son rôle est de regrouper les codes objets (éventuellement issus de plusieurs compilateurs différents) en un code exécutable.

Niveaux de Compréhension d'un Texte

Il existe plusieurs niveaux de compréhension d'un texte (ou d'un programme). Initialement, un texte écrit est une suite de caractères.

Analyse Lexicale

Au premier niveau, il s'agit de reconnaître les mots, déterminer si chaque groupe de caractères appartient à un lexique; puis transformer la suite de caractères en suite de mots (analyse lexicale).

Analyse Syntactique

Au deuxième niveau, il s'agit d'exhiber la structure du texte, déterminer si le texte est conforme à une syntaxe ou grammaire; puis transformer la suite de mots en une structure hierarchique (analyse syntaxique).

Analyse Sémantique

Au troisième niveau, on cherche à appréhender le sens du texte; on parle alors de analyse sémantique.

Structure d'un Compilateur

Une décomposition typique d'un compilateur comporte six phases.

  • Les trois premières forment le coeur de l'analyse d'un compilateur et correspondent aux différents niveaux de compréhension d'un texte : analyse lexicale, analyse syntaxique, analyse sémantique.
  • Les trois phases suivantes sont:
    1. générateur de code intermédiaire
    2. optimisation du code intermédiaire
    3. générateur de code (objet)
  • Deux autres taches interagissent avec les six phases; elles sont
    • la gestion de la table des symboles
    • le traitement des erreurs.
programme source
gestion table
de symboles
analyse lexicale traitement
des erreurs
↓ suite de mots
gestion table
de symboles
analyse syntaxique traitement
des erreurs
↓ structure hiérarchique
gestion table
de symboles
analyse sémantique traitement
des erreurs
↓ arbre décoré
gestion table
de symboles
génération de code intermédiaire traitement
des erreurs
↓ code intermédiaire
gestion table
de symboles
optimisation de code traitement
des erreurs
↓ code intermédiaire “optimisé”
gestion table
de symboles
génération de code traitement
des erreurs
code objet

Gestion de la table des symboles

Cette tache essentielle consiste à enregistrer les identificateurs utilisés dans le programme source et à collecter les informations associées à ces identificateurs (type, portée, …)

Une table de symboles : une structure de données qui contient un enregistrement pour chaque identificateur, muni d'un certain nombre de champs permettant de stocker des information associées à cet identificateur. Elle est construite de manière à accéder rapidement à ces informations.

Traitement des Erreurs

Chaque phase peut rencontrer des erreurs. Cependant, une phase doit traiter ces erreurs de façon à ce que la compilation puisse continuer et que d'autres erreurs puissent être détectées 1).

Analyse Lexicale (//scanning//)

Transforme un flot de caractères en un flot d'unités lexicales2) dont chacune représentera une suite de caractères. Une unité lexicale peut être un mot-clef, un identificateur, une constante, un opérateur, ou un séparateur.

 position := initiale + vitesse * 60

Analyse : ID AFF ID PLUS ID MULT ID CST

Certaines unités lexicales comme les identificateurs ou les constante ont une valeur lexicale qui est la suite de caractères qu'elles représentent. Lorsqu'on intègre cet aspect, l'analyse devient:

(ID,"position")  AFF  (ID,"initial")  PLUS  (ID,"vitesse")  MULT (CST,"60")

Lorsqu'un identificateur est rencontré, il est entré dans la table de symboles (s'il n'y est pas déjà).

Analyse Syntaxique (//parsing//)

Cette phase

  • vérifie que la suite d'unités lexicales est une construction permise, c'est à dire conforme à la grammaire définissant le langage source.
    Ex. CST AFF PLUS MULT ID ID ID est une construction incorrecte (pour les langages auxquels nous sommes habitués).
  • rend explicite la structure hiérarchique, par exemple, à l'aide de rajout de parenthèses :
    ID AFF (ID PLUS (ID MULT CST) )

Représentation en arbre de syntaxe abstraite (et syntaxe abstraite != syntaxe concrète)

    AFF
  /     \
ID       PLUS
        /    \
     ID      MULT
            /    \
          ID      CST

Analyse Sémantique

Cette phase vérifie la cohérence des types (et éventuellement décore et enrichit l'arbre de syntaxe abstraite par des opérations de conversion de type).

      AFF
    /     \
  ID       PLUS
          /    \
        ID      MULT
               /    \
             ID      EntierVersReel
                           |
                          CST

Génération de Code Intermédiaire

Cette phase construit un représentation intermédiaire du programme source. C'est un code pour une machine abstraite, dont les instructions sont de plus haut niveau que les instruction du langage machine.

Ce code peut prendre plusieurs formes. Parmi elles, le code à trois adresses , une séquence d'instructions dont chaque instruction a au plus 3 opérands 3) :

tmp1  :=  EntierVersReel(60)
tmp2  :=  id1 * tmp1
tmp3  :=  id2 + tmp2
 id3  :=  tmp3

Optimisation du Code Intermédiaire

Tente d'amèliorer l'efficacité du code intermédiaire.

Exemple : le code précedent peut être allégé en supprimant le passage par la variable tmp3

 tmp2  :=  id1 * 60.0  // on réécrit 60 entier en 60.0 réel
  id3  :=  id2 + tmp2

Génération de Code (objet)

Production du code objet implique :

  1. choisir emplacements en mémoire pour les données
  2. sélectionner du code machine pour implémenter les instructions du code intermédiaire
  3. allouer les registres (un aspect important.
 MOVF  id1,R2
 MULF  #60.0,R2
 MOVF  id2,R1
 ADDF  R2,R1
 MOVF  R1,id3

Regroupement de Phases

En pratique, il arrive souvent que l'on regroupe plusieurs phases.

Parties Frontale et Finale

Les différentes phases sont souvent réunies en une partie frontale 4) (indépendante de la machine) et une partie finale 5) (dépendante de la machine. ⇒ la frontière se situe entre génération de code intermédiaire et optimisation du code (? hésitation

Passes

On implémente habituellement plusieurs phases en une seule passe (la lecture d'une repésentation intermédiaire du texte source et l'écriture d'une autre représentation intermédiaire). Il est préférable d'avoir peu de passes pour réduire le temps de compilation. On peut souvent regrouper les quatre premières phases en une seule passe.


Navigation

1) un compilateur qui s'arrête à la première erreurs n'est pas très utilisable
2) “tokens” en anglais
3) comme assembleur?
4) frontend en anglais
5) backend en anglais
 
m1ilc/compil_1.txt · Dernière modification: 2009/10/09 18:44 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki