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

Description

-1-INF 421 — 08 Luc MarangetExpressions r´eguli`eres(rationnelles)[e-mail]://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 ...

Informations

• Publié par: Mocher
• Nombre de lectures: 42
• Langue: Français

Extrait

-1-

INF 421 — 08

Luc Maranget

Expressionsr´eguli`eres (rationnelles)

[e-mail] 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,leoisneu’lelqsfinirAd´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 estxnava’l,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.sssleteuinisfidees)tnos

◮Unlangageest un sous-ensemble de Σ ∗ .

⊲gngadeseomstrfnaai¸cs.La ⋆Σ ={ab . . .}(alphabet usuel, avec accents). ⋆.)pirae´nficiitl,deDis,eime´tneitynoe(irnaonadAcl’de

⊲nbase10.ritureseeged´sceLnaag ⋆Σ ={01 . . . 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=a 0 a 1   a n−1 (nlongueur dem).

◮re`ectracediind’uc´pRe´elacrerek:a k .

◮oCene´tacnaul’e.trrtleu’dnreire`errdeuxmots:lesmet

mm ′ =a 0 a 1   a n−1 a ′ 0 a ′ 1   a ′ n ′ −1

⊲e.ativsocionasaritpOe´ ⊲t`eechauage`treuntneme´le´edivtoMdaortie (ǫm=mǫ=m). ⊲Danst=mm ′ ,mest unexfie´rpdet,m ′ est unsuffixedet.

◮ioatotNg´´ebrna:eet=mm ′ .

◮Notation des sous-mots :

m[i  j[=a i a i+1   a j−1

-7-

Lesmotssontdeschaˆınes La classeString a )´erdutfaime(agckpa´ertpoapud,java.lang.

◮Mot vide :"".

◮eicup´ererlPourr´ecredei’dnceraca`tk. public charcharAt(intindex)

◮euxcnerdat´eConcse:ahni String t=m0+m1;

Oume´thodeconcat. String t=m0.concat(m1) ;

◮exffiusteemalceva,eodth´eDe´composerenpr´efixsubstring. 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

L 1 L 2 ={m 1 m 2 |m 1 ∈L 1 ∧m 2 ∈L 2 }

L 0 ={ǫ}

Autrement dit :

L n+1 =L n L

L ⋆ = [ L i i∈N

m∈L ⋆ ⇐⇒m=m 1 m 2   m n avecm i ∈L

-9-

Lesexpressionsr´egulie`res

Unerepre´sentationpd’un langageL.

◮Le mot videǫeprreentse{ǫ}. ´

◮acareLertce`ceseneprrte{c}. ´

◮Lvetilt’anaerp 1 |p 2 etnpereserL 1 ∪L 2 .

´ ◮noat´enatiLaconcp 1 p 2 persenetreL 1 L 2 .

◮noititep´´earLp*se´rperenteL ⋆ .

Pourl’informaticien,lade´finitionme´riteuned´ecompositionen syntaxeetequtiname´s.

-10-

Syntaxedesexpressionsr´eguli`eres

Un motifp.sidtsenfie´niai

◮Le mot videǫest un motif.

◮ct`erenUacarcest un motif.

◮Sip 1 etp 2  . .sont des motifs, alors. ⊲ivernatalteL’p 1 |p 2 est un motif. ⊲na´eonticoLaatncp 1 p 2 est un motif.

◮Sipest un motif, alors. . .

⊲aL´rpee´ititnop*est un motif.

Importantitinednoenutfie´d’aedrerbrusturctdsepsuls,naC’es ´ 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*