Concepts des langages de programmationdift2035/e2009/cours/implementation_… · Une instruction du programme A est transformée en une instruction en langage B et puis exécutée

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


� Exemple





� 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


� Exemple





� 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


� Exemple





� 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 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


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


� Exemple





� 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


� Exemple





� 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


� Exemple





� 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


� Exemple





� 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


� Exemple





� 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

Documents

Concepts des langages de programmationdift2035/e2009/cours/implementation_… · Une instruction du programme A est transformée en une instruction en langage B et puis exécutée