Cours sur les expressions régulières (rationnelles)
51 pages
Français
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres

Cours sur les expressions régulières (rationnelles)

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

Description

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

Sujets

Informations

Publié par
Nombre de lectures 42
Langue Français

Exrait

-1-
INF 421 — 08
Luc Maranget
Expressionsr´eguli`eres (rationnelles)
Luc.Maranget@inria.fr http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/
-2-
Qu’est-ce qu’un mot ?
Plan
deestsmo?derirce´dtnemmoCplimsslembseenes
ogra ¸ Pr mmation de tout ca.
` ` Aquoi¸casert?Ajouerauxmots-croise´s(entreautres)!Mais aussi :
` sederce´rutit,leoisneulelqsnirAd´eotatdesnintdans un source Java.
` A effectuer des recherches et des modifications dans du texte.
` eroyttneA.ioereptrree´ovrt
e.qutieladplednctiistitnxanoysmena/e´sexemnbonnneuDo
-3-
Jeux avec les mots
SoientAetBdeux humains,Acsorsie´euuamxtojos,Bl’aide :
A  ilne manque pas d’air, en sept lettres lapose une question : seconde estxnaval,i`t-destereen?` rnoxygene
uartUennceparlqnirttec,seemmolie:esvrr´acnceebouc? bibleoucoran.
Dans les questions deAy a une partie typiquement humaine, et, il une autre plus simple.
SiBest un ordinateur, on peut donner desmotifs. . .
.x...n.(.est une lettre quelconque).
(b|c)....(|est l’alternative).
Si on dispose d’un fichiers de mots, on peut extraire les mots qui conviennent paregrep, par exempleegrep -x ’.x...n.’file
-4-
Lare´´etition p
Poursedonnerplusdeliberte´,onintroduit*
.*noitite´edtouslesmots(r´ep:.).
mots qui contiennent (au moins) deuxLes k:.*k.*k.*
Sipmotif, alor*´:it.fudomitnoe´it sprep
Les mots dont les lettres sont prises dansabcd: (a|b|c|d)*.
Lettres prises dansabcdetefgh alternativement :|b|c((|af|g|)de(*|h)).
Essayez pour voir :
# egrep -x ’.*k.*k.*’ /usr/share/dict/french bookmaker bookmakers ...
-5-
Les mots
Soit Σ unalphabetes).t`ermelbe(snracadece
Lesmots(ensemble Σacartce`er.sssleteuinisdees)tnos
Unlangageest un sous-ensemble de Σ.
gngadeseomstrfnaai¸cs.La Σ ={ab . . .}(alphabet usuel, avec accents). .)pirae´nciitl,deDis,eime´tneitynoe(irnaonadAclde
nbase10.ritureseeged´sceLnaag Σ ={01 . . . 9}(chiffres). egenraresirhppee´ranueDipnle chiffre0, ou une suite ´ non-vide de chiffres qui ne commence pas par0.
-6-
O´erationssurlesmots p
Un mot est par exemplem=a0a1  an1(nlongueur dem).
re`ectracediinduc´pRe´elacrerek:ak.
oCene´tacnaule.trrtleudnreire`errdeuxmots:lesmet
mm=a0a1  an1a0a1  an1
e.ativsocionasaritpOe´ t`eechauage`treuntneme´le´edivtoMdaortie (ǫm=mǫ=m). Danst=mm,mest unexe´rpdet,mest unsuffixedet.
ioatotNg´´ebrna:eet=mm.
Notation des sous-mots :
m[i  j[=aiai+1  aj1
-7-
Lesmotssontdeschaˆınes La classeStringa)´erdutfaime(agckpa´ertpoapud,java.lang.
Mot vide :"".
eicup´ererlPourr´ecredeidnceraca`tk. public charcharAt(intindex)
euxcnerdat´eConcse:ahni String t=m0+m1;
Oume´thodeconcat. String t=m0.concat(m1) ;
exusteemalceva,eodth´eDe´composerenpr´exsubstring. String pref=m.substring(0,k)//m[0  k[ String suff=m.substring(k)//m[k  n[
a
http://java.sun.com/j2se/1.5.0/docs/api/java/lang/String.html
-8-
Op´erationssurleslangages
Union ensembliste.
noncCotina´eat
itar.noIt´e
L1L2={m1m2|m1L1m2L2}
L0={ǫ}
Autrement dit :
Ln+1=LnL
L=[Li iN
mL⇐⇒m=m1m2  mnavecmiL
-9-
Lesexpressionsr´egulie`res
Unerepre´sentationpd’un langageL.
Le mot videǫeprreentse{ǫ}. ´
acareLertce`ceseneprrte{c}. ´
Lvetiltanaerp1|p2etnpereserL1L2.
´ noat´enatiLaconcp1p2persenetreL1L2.
noititep´´earLp*se´rperenteL.
Pourlinformaticien,lade´nitionme´riteuned´ecompositionen syntaxeetequtiname´s.
-10-
Syntaxedesexpressionsr´eguli`eres
Un motifp.sidtsene´niai
Le mot videǫest un motif.
ct`erenUacarcest un motif.
Sip1etp2 . .sont des motifs, alors. ivernatalteLp1|p2est un motif. na´eonticoLaatncp1p2est un motif.
Sipest un motif, alors. . .
aL´rpee´ititnop*est un motif.
Importantitinednoenute´daedrerbrusturctdsepsuls,naCes ´ isio prec ns.
P={ǫ} ⊎Σ(P× {| × }P)(P× {*})
-11-
a
Exemple de motif
*
b
|
Enpratiqueon´ecrit(syntaxeconc`te) re
b
*
a
(a(b*))|(b(a*)) ou plus simplementab*|ba*
  • Accueil Accueil
  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • BD BD
  • Documents Documents