INTRODUCTION
- Nom J.M. (Mike) Robson
- mail robson@labri.u-bordeaux.fr
- Compilation
- Philosophie Comprendre comment nos programmes en langages évolués
peuvent être exécutés par des machines avec jeu d'instructions
et architecture simples
- Projet: date? coefficient?
- Transparents:
http://www.labri.fr/~robson/Compilation/
- Livres: Le Dragon et autres
- Langage et langue: Algol-6X, Pascal, CPL, BCPL, C, java
STRUCTURE d'UN COMPILATEUR
Plusieurs phases:
- Analyse lexicale
- Analyse syntaxique
- Verification de règles non-syntaxiques
- Génération de code (intermédiaire)
- Génération de code (vrai)
- Optimisation (Assemblage de plusieurs modules)
en principe indépendantes mais...
communication entre phases
L'UTILISATION DE LOGICIELS GENERAUX
En l'occurrence eli (préféré à lex/yacc)
- interpreteur, compilateur, compilateur de compilateurs
- Compilateur produit d'une description (non-algorithmique) du langage
et du code à générer
- simple pour analyse lexicale
- bien compris pour analyse syntaxique
- utilité: séparation de concernes
ANALYSE LEXICALE
- Entités lexicales décrites par expressions rationnelles
- e.g. identificateurs
- e.g. constantes numériques
- e.g. commentaires
- ad hoc: <= || if ...
- Ecriture d'expressions rationnelles en eli (pareille en lex) raccourcis
mais complications dues au fait que la même police de caractères
est utilisée pour l'alphabet et les opérateurs...
ANALYSE SYNTAXIQUE (début)
- Décider si le programme est construit selon la grammaire donnée
et (si oui) construire une representation de sa structure syntaxique
- (arbre syntaxique concret ou abstrait)
- Mal défini si la grammaire est ambigue (mais ...)
- Algorithmes spécifiques pour classes restreintes de grammaires
- Cette semaine nous regardons un algorithme plus général
mais plus lent.
- Préalablement modifier la grammaire da façon à
ne jamais avoir plus de 2 symboles à la droite d'une production
- Méthode de programmation dynamique:
- Trouver pour chaque sous-mot (section du programme) toutes les analyses
possibles
- En ordre croissant de la longueur des sous-mots
Temps de calcul de l'analyse
dynamique
- En principe W(n3)
- Mais O(n2) pour une grammaire non-ambigue
- Et, en pratique, mieux
enddocument
File translated from TEX by
TTH,
version 3.05.
On 26 Jan 2004, 16:00.