-1-INF 421 — 08 Luc MarangetExpressions r´eguli`eres(rationnelles)Luc.Maranget@inria.frhttp://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-Plan◮ Qu’est-ce qu’un mot ?◮ Comment d´ecrire des ensembles simples de mots ?◮ Programmation de tout c¸a.` `A quoi c¸a sert ? A jouer aux mots-crois´es (entre autres) ! Maisaussi :`◮ A d´efinir des notations, telles que l’´ecriture des int dans unsource Java.`◮ A effectuer des recherches et des modifications dans du texte.`◮ A nettoyer votre r´epertoire.◮ Donne un bon exemple de la distinction syntaxe/s´emantique.-3-Jeux avec les motsSoient A et B deux humains, A joue aux mots crois´es, B l’aide :◮ A pose une question : il ne manque pas d’air, en sept lettres laseconde est x, l’avant-derni`ere est n ? oxyg`ene◮ Une autre : livre sacr´e en cinq lettres, commence par b ou c ?bible ou coran.Dans les questions de A, il y a une partie typiquement humaine, etune autre plus simple.Si B est un ordinateur, on peut donner des motifs...◮ .x...n. (( . )) est une lettre quelconque).◮ (b|c).... (( | ) est l’alternative).Si on dispose d’un fichiers de mots, on peut extraire les mots quiconviennent par egrep, par exemple egrep -x ’.x...n.’ file-4-La r´ep´etitionPour se donner plus de libert´e, on introduit *◮ .* : tous les mots (r´ep´etition de .).⊲ Les mots qui contiennent (au moins) deux k : .*k.*k.*◮ Si p motif, alors p* : r´ep´etition du motif.⊲ Les mots dont les lettres sont ...
⊲gngadeseomstrfnaai¸cs.La ⋆Σ ={ab . . .}(alphabet usuel, avec accents). ⋆.)pirae´nficiitl,deDis,eime´tneitynoe(irnaonadAcl’de
⊲nbase10.ritureseeged´sceLnaag ⋆Σ ={01 . . . 9}(chiffres). ⋆egenraresirhppee´ranueDipfin✭le chiffre0, ou une suite ´ non-vide de chiffres qui ne commence pas par0✮.
-6-
O´erationssurlesmots p
Un mot est par exemplem=a0a1 an−1(nlongueur dem).