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.
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.
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.
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.
Permet de communiquer avec le système d'exploitation. Son rôle essentiel est de lancer les executables (écrit en langage machine).
On peut distinguer deux types d'outil:
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.
Il existe plusieurs niveaux de compréhension d'un texte (ou d'un programme). Initialement, un texte écrit est une suite de caractères.
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).
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).
Au troisième niveau, on cherche à appréhender le sens du texte; on parle alors de analyse sémantique.
Une décomposition typique d'un compilateur comporte six phases.
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 |
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.
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).
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à).
Cette phase
CST AFF PLUS MULT ID ID ID
est une construction incorrecte (pour les langages auxquels nous sommes habitués).Représentation en arbre de syntaxe abstraite (et syntaxe abstraite != syntaxe concrète)
AFF / \ ID PLUS / \ ID MULT / \ ID CST
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
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
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
Production du code objet implique :
MOVF id1,R2 MULF #60.0,R2 MOVF id2,R1 ADDF R2,R1 MOVF R1,id3
En pratique, il arrive souvent que l'on regroupe plusieurs phases.
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
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.