Concepts des langages de
programmationprogrammation
Implémentation des langages : introduction
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
2
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
3
Comment est défini un langage ?
� Un langage (naturel ou de programmation) est défini par un alphabet, une syntaxe et une sémantique
� L'alphabet sert à la construction des mots du langage� Exemple :
� Langage naturelle : lettres de 'a' à 'z'
� La syntaxe sert à la construction de phrases bien formées� Exemple : � Exemple :
� Phrase = sujet + verbe + complément
� Instruction if : if condition then instruction1 else insturction2
� Affectation : a = 10
� La sémantique d'une phrase est le sens attaché à cette phrase � Pas toutes les phrases de la forme sujet + verbe + complément ont un sens
� Toutes les affectation ne sont pas correctes : � Langage à typage statique : Affecter la valeur d'une variable à une variable non déclarée n'est
pas permis
4
Comment est défini un langage ?
� Le lexique, la syntaxe et la sémantique sont les composants essentiels d'un langage de programmation� Ce sont la spécification du langage� Ce sont la spécification du langage
� Ce qu'on peut faire et comment le faire avec le langage
� Un compilateur est une implémentation qui suit/respecte une spécification
5
Qu’est ce qu’un compilateur ?
� Un compilateur est un traducteur qui permet de transformer un programme écrit en un langage A en un programme écrit en langage B � Le langage B est directement compris par la machine (machine physique ou virtuelle)
� Souvent on s’arrête au langage assembleur ou à un langage d’une machine virtuelle (Java)
6
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
7
Structure d’un compilateur/phases de
compilation
Programme écrit en langage A (code source)
Analyse lexicale
Analyse syntaxiqueAnalyse syntaxique
Analyse sémantique
Former les mots du langage (lexèmes)
Retrouver les relations entre les lexèmes (construire l’arbre
syntaxique)
Donner une signification à l’arbre syntaxique
8
Programme cible écrit en langage B (code machine)
intermédiaireGénération de code
intermédiaire
Optimisation
Génération de code final
Table des symboles Gestion d’erreurs
Générer un code interne au compilateur (sans tenir compte entre autres des contraintes matérielles) ...
phase optionnelle
Tenir compte des caractérisituqes/contraintes matérielles pour générer un code optimisé au matériel
ciblé (processeur physique ou virtuel)
Tenir compte des caractérisituqes/contraintes matérielles pour générer un code optimisé au matériel
ciblé (processeur physique ou virtuel) ... registres, piles, ...
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
9
Exemple 1 : langue naturelle
Il fait beau
Analyse lexicale
À partir d’un alphabet (26 lettres) On distingue 3 mots : « il», «fait»
et «beau»
Structrue grammaticale : phase composé de sujet, verbe, adverbe
10
The weather is fine
Analyse syntaxiqueAnalyse syntaxique
Analyse sémantique
composé de sujet, verbe, adverbe
Unité sémantique : exprimer une condition atmosphérique ... notre cerveau s’occupe du
reste
Exemple 2 : lexicale + syntaxique
Programme source v a r = 7 * v a r + i
Unités lexicales1
(ident.)3
(affect.)2
(nombre)4
(multip.)1
(ident.)5
(plus)1
(ident.)Code de l‘unité
Analyse lexicale
11
Analyse syntaxiqueAnalyse syntaxique
Arbre syntaxique
Ident. = nombre * ident. + ident.
Term
Expression
Statement
Unités lexicales (ident.)"var"
(affect.)-
(nombre)7
(multip.)-
(ident.)"var"
(plus)-
(ident.)"i" Valeur de l‘unité
Exemple 2 : sémantique + optimisation + génération de code
Arbre syntaxique
Ident. = nombre * ident. + ident.
Term
Expression
Statement
Analyse sémantique
12
101011110101000011....
Code machine
Optimisation
Génération de code final
Représentationintermédiaire
Arbre syntaxique, table des symboles, ...
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
13
Analyse Syntaxique /Sémantique
"Programme principal"
Dirige toute la compilation
scanner Génération de code
Fonctionnement d’un compilateur
Code source Code exécutable
Fournit les unités lexicales à
partir du code source
Utilise
Table des symboles
Maintient des informations sur
les variables et types déclarés
Génère le code machine
Flots de données
14
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
15
Outils théoriques et pratiques
Phases de la compilation Outils théoriques Outils pratique
Analyse lexicale (scanner) Expressions régulièresAutomates d’états finis
Ruby/C/Java , (F)Lex
16
Phases d’analyse
Automates d’états finis
Analyse syntaxique(parser)
Grammaires
Yacc, Bison Analyse sémantique Traduction dirigée par la
syntaxe
Phase de production Génération de code Traduction dirigée par la syntaxe
Bison
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
17
Types de compilateurs
� Suivant qu’on analyse une unité lexicale ou plusieurs à la fois, on distingue :
� Compilateurs à une passe � Compilateurs à une passe
� Compilateurs à plusieurs passes
� Compilateurs à deux passes
18
Scanne une unité (mot)
Analyse une unité
Compilateurs à une passe
� Fonctionnement simultané des phases
Analyse une unité
Vérifie une unité
Génère le code pour une unité
Fin du fichier ?non
oui
19
Source
Lexique
Unités lexicales
Syntaxe
Arbre Syntaxique
Sémantique ...
Code
Compilateurs à plusieurs passes
� Les phases de la compilation sont des programmes séparés qui s'exécutent séquentiellement
Source Unités lexicales Arbre Syntaxique Code
� Chaque phase lit à partir d'un fichier et écrit sur un nouveau fichier
� Pourquoi plusieurs passes ?
� Mémoire insuffisante (… ce n’est plus le cas)
� Langage complexe
� Modularité et grande portabilité
20
Passe 1
Lexique
Syntaxe
SémantiqueReprésentation
intermédiaire
Passe 2
Génération
code
Dépendant du language Dépendant de la machine
En général : Compilateurs à deux passes
Java
C
Pascal
PC
Macintosh
SPARC
Toute combinaison possible
� Avantages � Meilleure portabilité
� Optimisations plus simples sur la représentation
intermédiaire que sur le code source
� Inconvénients � Lenteur
� Plus de mémoire
21
Dans quel langage est écrit un compilateur ?
� Le langage à partir duquel sera écrit un compilateur ne dépend pas des langages source et cible considérées
� Pour plus d’efficacité � Choisir un langage de bas niveau (C/C++, assembleur, ..)
� Pour plus de facilité/portabilité/contrôle de la complexitéChoisir un langage de haut niveau� Choisir un langage de haut niveau
� Remarque : pour compiler un langage A, on peut écrire un compilateur en langage A
� Quelques exemples
� Ribinuis est un compilateur Ruby écrit (presque entièrement) en Ruby
� Yarv est un compilateur Ruby écrit en C
� JRuby compilateur Ruby écrit en Java
22
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
23
Compilation VS interprétation
� Compilation
� Programme d’un langage A est entièrement transformé en un programme en langage B
� Compilation doit être achevée avant l’exécution du programme
� Un programme en langage B est généré
� Ex. C, C++, ...
� Interprétation
� Une instruction du programme A est transformée en une instruction en langage B et puis exécutée
� Une instruction (bloc d’instructions) à la fois� Une instruction (bloc d’instructions) à la fois
� Seulement le programme en langage A existe (pas de génération d’un programme en langage B)
� Ex. Ruby, Perl, PHP, Phyton, Javascript, ...
� Langage hybrides : compilation + interprétation � Ex. Java, JRuby, C#, Jython, IronRuby,...
24
Code source en langage X
Code intermédiare (langage Y)
Code machine (langage Z)
compilation interprétation
Compilation VS interprétation (suite)
� Compilation� Avantages
� Détection facile et précoce des erreurs syntaxiques : avant l’exécution
� Exécution rapide� Exécution rapide
� Protection du code source (... quoi que la décompilation réduit cet avantage)
� Inconvénients � Méta programmation difficile
� Moins de flexibilité : l’unité atomique est un programme entier
� À chaque modification du programme, une recompilation est nécessaire
25
Compilation VS interprétation (suite)
� Interprétation� Avantages
� Facilité de la programmation : résultats des changements dans le programme sont immédiats
� Offre plus de flexibilité et de dynamisme : l’unité atomique est une instruction � Offre plus de flexibilité et de dynamisme : l’unité atomique est une instruction du langage
� Implémentation de fonctionnalités réservées à la méta programmation facilité
� Inconvénient � Lenteur à l’exécution
� C’est le code source qui est distribué (problème de protection du code)
26
Plan
� Définition
� Structure d’un compilateurs
� Exemple
� Fonctionnement d’un compilateur� Fonctionnement d’un compilateur
� Outils théoriques et pratiques
� Types de compilateurs
� Compilation versus interprétation
� Récapitulatif
27
Récapitulatif
� Analyse lexicales � Reconnaitre les mots du langage
� Décomposer un texte en mots suivant un alphabet
� En utilisant des expression régulières ou des automates
� Analyse syntaxique � Analyse syntaxique � Reconnaître les phrases bien formées
� S’assurer que la structure du texte est correcte suivant une certaine grammaire
� Analyse sémantique � Vérifier si les phrases ont du sens ou non
� Retrouver la signification des phrases et de leurs composantes
28