Langages de programmation et compilation
23 pages
Français

Langages de programmation et compilation

Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
23 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Description

  • cours - matière potentielle : langages formels
  • cours - matière potentielle : langages formels
Ecole Normale Superieure Langages de programmation et compilation Jean-Christophe Filliatre Cours 5 / 3 novembre 2011 Jean-Christophe Filliatre Langages de programmation et compilation 2011–2012 / cours 5 1 / 90 Analyse lexicale Quandj'etaisenfant,onm'avaitditquelePereNoeldescendaitpar lacheminee,etquelesordinateursseprogrammaientenbinaire.J'ai apprisdepuisquelaprogrammationsefaisaitdepreference dansdeslangagesdehautniveau,plusabstraitsetplusexpressifs. Jean-Christophe Filliatre Langages de programmation et compilation 2011–2012 / cours 5 2 / 90 Analyse lexicale Quand j'etais enfant, on m'avait dit que le Pere Noel descendait par la cheminee, et que les ordinateurs se programmaient en binaire.
  • automate fini
  • langages de programmation
  • funx
  • let start
  • fun
  • analyse lexicale
  • pos
  • espace espace
  • espace en espace
  • constantes entieres constantes
  • app app
  • expression reguliere
  • lexemes
  • analyzer autom
  • fun des identificateurs
  • input
  • inputs
  • expression
  • expressions
  • mots
  • mot

Sujets

Informations

Publié par
Nombre de lectures 37
Langue Français

Extrait

Analyse lexicale
´Ecole Normale Sup´erieure
Langages de programmation Quandj’´etaisenfant,onm’avaitditqueleP`ereNo¨eldescendaitpar
lachemin´ee,etquelesordinateursseprogrammaientenbinaire.J’aiet compilation
apprisdepuisquelaprogrammationsefaisaitdepr´ef´erence
dansdeslangagesdehautniveau,plusabstraitsetplusexpressifs.
Jean-Christophe Filliˆatre
Cours 5 / 3 novembre 2011
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 1 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 2 / 90
Analyse lexicale Analyse lexicale
Quand j’´etais enfant, on m’avait dit que le P`ere No¨el descendait par la
l’analyse lexicale est le d´ecoupage du texte source en mots
chemin´ee, et que les ordinateurs se programmaient en binaire. J’ai appris
depuis que la programmation se faisait de pr´ef´erence dans des langages de de mˆeme que dans les langues naturelles, ce d´ecoupage en mots facilite le
haut niveau, plus abstraits et plus expressifs. travail de la phase suivante, l’analyse syntaxique
introduction de la th`ese de X. Leroy ces mots sont appel´es des lex`emes (tokens)
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 3 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 4 / 90Analyse lexicale : exemple Les blancs
...source = suite de caract`eres
les blancs (espace, retour chariot, tabulation, etc.) jouent un rˆole dans↓
l’analyse lexicale ; ils permettent notamment de s´eparer deux lex`emesanalyse syntaxique
fun x → (* ma fonction *)
(semaine prochaine)
x+1 ainsi funx est compris comme un seul lex`eme (l’identificateur funx) et↓
fun x est compris comme deux lex`emes (le mot cl´e fun et
syntaxe abstraite↓ l’identificateur x)
analyse lexicale
Fun
↓ de nombreux blancs sont n´eanmoins inutiles (comme dans x + 1 )
"x" App et simplement ignor´es
suite de lex`emes
App Const
les blancs n’apparaissent pas dans le flot de lex`emes renvoy´e
fun x -> x + 1 Op Var 1
... + "x"
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 5 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 6 / 90
Les blancs Les commentaires
les commentaires jouent le rˆole de blancs
fun(* et hop *)x → x + (* j’ajoute un *) 1
les conventions diff`erent selon les langages,
et certains des caract`eres blancs peuvent ˆetre significatifs
ici le commentaire (* et hop *) joue le rˆole d’un blanc significatif
(s´epare deux lex`emes) et le commentaire (* j’ajoute un *) celui d’un
blanc inutile
exemples :
les tabulations pour make
note : les commentaires sont parfois exploit´es par certains outilsretours chariot et espaces de d´ebut de ligne en Python ou en Haskell
(ocamldoc, javadoc, etc.), qui les traitent alors diff´eremment dans leur(l’indentation d´etermine la structure des blocs)
propre analyse lexicale
val length : α list → int
(** Return the length (number of elements) of ...
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 7 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 8 / 90Quels outils Expressions r´eguli`eres : syntaxe et s´emantique
pour r´ealiser l’analyse lexicale, on va utiliser r ::= ∅ L(∅) =∅
| L() ={}des expressions r´eguli`eres pour d´ecrire les lex`emes
| a L(a) ={a}des automates finis pour les reconnaˆıtre
| r r L(r r ) ={w w | w ∈ L(r )∧ w ∈ L(r )}1 2 1 2 1 1 2 2
| r| r L(r | r ) = L(r )∪ L(r )1 2 1 2S
n 0 n+1 n| r? L(r?) = L(r ) ou` r = , r = r rn≥0on exploite notamment la capacit´e `a construire automatiquement un
automate fini d´eterministe reconnaissant le langage d´ecrit par une
expression r´eguli`ere (cf. cours langages formels)
conventions : l’´etoile a la priorit´e la plus forte, puis la concat´enation, puis
enfin l’alternative
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 9 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 10 / 90
Exemples Reconnaissance de lex`emes
expression
sur l’alphabet{a, b}
lex`eme r´eguli`ere automate
mots de trois lettres f u n
0 1 2 3(a|b)(a|b)(a|b) mot cl´e fun f u n
mots se terminant par un a
+
0 1(a|b)? a symbole + +
mots alternant a et b
- >(b|)(ab)? (a|) 0 1 2
symbole -> ->
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 11 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 12 / 90Constantes enti`eres Identificateurs
identificateurs compos´es de lettres, de chiffres et du soulign´e, et
constantes enti`eres d´ecimales, ´eventuellement pr´ec´ed´ees de z´eros
commen¸ cant par une lettre
expression r´eguli`ere
expression r´eguli`ere
(0|1|2|3|4|5|6|7|8|9) (0|1|2|3|4|5|6|7|8|9)?
(a|b|...|z|A|B|...|Z ) (a|b|...|z|A|B|...|Z||0|1|...|9)?
automate
automate
0..9
0 1 a..zA..Z
0 1
0..9
a..zA..Z 0..9
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 13 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 14 / 90
Constantes flottantes Commentaires
constantes flottantes de Caml
les commentaires de la forme (* ... *), mais non imbriqu´es, peuvent
´egalement ˆetre d´efinis de cette mani`ere
expression r´eguli`ere
expression r´eguli`ere
d d? (.d?| (|.d?)(e|E ) (| +|−)d d?)

( * * ? a| b ? * * ? )
ou` d = 0|1|...|9
ou` a = tous les caract`eres sauf * et )automate
et b = tous les caract`eres sauf *
+,-
3 4
automate fini
e,E 0..9e,E 0..9 *
( )*
0 1 2 3 4
0..9 . a0 1 2 5
b *
0..9 0..9 0..9
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 15 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 16 / 906
6
6
Commentaires imbriqu´es Analyseur lexical
un analyseur lexical est un automate fini pour la r´eunion de toutes les
expressions r´eguli`eres d´efinissant les lex`emes
les expressions r´eguli`eres ne sont pas assez expressives pour d´efinir les
commentaires imbriqu´es (le langage des mots bien parenth´es´es n’est pas
le fonctionnement de l’analyseur lexical, cependant, est plus complexe quer´egulier)
la simple reconnaissance d’un mot par un automate, car
on expliquera plus loin comment contourner ce probl`eme il faut d´ecomposer un mot (le source) en une suite de mots reconnus
il peut y avoir des ambigu¨ıt´es
il faut construire les lex`emes (les ´etats finaux contiennent des actions)
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 17 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 18 / 90
Ambigu¨ıt´es Analyseur lexical
exemple : le mot cl´e fun et les identificateursle mot funx est reconnu par l’expression r´eguli`ere des identificateurs,
mais contient un pr´efixe reconnu par une autre expression r´eguli`ere (fun)
f u n
0 1 2 3⇒ on fait le choix de reconnaˆıtre le lex`eme le plus long possible
=u
=n a..z=f
le mot fun est reconnu par l’expression r´eguli`ere du mot cl´e fun mais
4aussi par celle des identificateurs
a..z⇒ on classe les lex`emes par ordre de priorit´e
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 19 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 20 / 90Analyseur lexical Un peu de programmation
programmons un analyseur lexical
on introduit un type d’automates finis d´eterministes
type automaton = {l’analyseur lexical doit donc m´emoriser le dernier ´etat final rencontr´e, le
initial : int; (* etat´ = entier *)cas ´ech´eant
trans : int Cmap.t array; (* ´etat -> char -> etat´ *)
action : action array; (* ´etat -> action *)lorsqu’il n’y a plus de transition possible, de deux choses l’une :
}
aucune position finale n’a ´et´e m´emoris´ee⇒ ´echec de l’analyse lexicale
avec
on a lu le pr´efixe wv de l’entr´ee, avec w le lex`eme reconnu par le
type action =
dernier ´etat final rencontr´e⇒ on renvoie le lex`eme w, et l’analyse
| NoAction (* pas d’action = pas un ´etat final *)
red´emarre avec v pr´efix´e au reste de l’entr´ee
| Action of string (* nature du lex` eme *)
et
module Cmap = Map.Make(Char)
Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 21 / 90 Jean-Christophe Filliˆatre Langages de programmation et compilation 2011–2012 / cours 5 22 / 90
Un petit analyseur lexical Un petit analyseur lexical
l’objectif est d’´ecrire une fonction analyzer qui prend un automate et une
chaˆıne `a analyser, et renvoie une fonction de calcul du prochain lex`eme
la table de transitions est pleine pour les ´etats

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents