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 lex/yacc (mieux serait eli?)
- interpreteur, compilateur, compilateur de compilateurs
- Compilateur produit à partir 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 lex (pareille en eli) 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
Principes de (f)lex
- une liste de règles
- une règle a une expression rationnelle pour un type de suite
de caractères à chercher
- et une instruction C à exécuter quand une suite est
trouvée
- la plus longue partie du fichier d'entrées qui correspond à
une expression est choisie
- et en cas de deux expressions possibles la première
- flex traduit le fichier en un programme C (par défaut lex.yy.c)
File translated from TEX by
TTH,
version 3.05.
On 1 Feb 2005, 10:24.