Cours sur les expressions régulières

Description

-1-INF 421 Luc MarangetExpressions r´eguli`eres(rationnelles)[e-mail]://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/-2-Les mots◮ Soit Σ un alphabet (ensemble de caract`eres).∗◮ Les mots (ensemble Σ ) sont les suites finies de caract`eres.∗◮ Un langage est un sous-ensemble de Σ .⊲ Langage des mots franc¸ais.⋆ Σ ={a,b,...} (alphabet usuel, avec accents).⋆ D´efini par, le dictionnaire (de l’Acad´emie, si on y tient).⊲ Langage des ´ecritures en base 10.⋆ Σ ={0,1,...,9} (chiffres).⋆ D´efini par une p´eriphrase genre ( le chiffre 0, ou une suitenon-vide de chiffres qui ne commence pas par 0 ).-3-Op´erations sur les motsUn mot est par exemple m = a a a (n longueur de m).0 1 n−1◮ R´ecup´erer le caract`ere d’indice k : a .k◮ Concat´ener deux mots : les mettre l’un derri`ere l’autre.′ ′ ′ ′mm = a a a a a a ′0 1 n−10 1 n −1⊲ Op´eration associative.⊲ Mot vide ´el´ement neutre a` gauche et a` droite(ǫm = mǫ = m).′ ′⊲ Dans t = mm , m est un pr´efixe de t, m est un suffixe de t.′◮ Notation abr´eg´ee : t = mm .◮ Notation des sous-mots :m[ij[= a a ai i+1 j−1-4-Les mots sont des chaˆınesaLa classe String , du package (import´e par d´efaut) java.lang.◮ Mot vide : "".◮ Pour r´ecup´erer le caract`ere d’indice k.public char charAt(int index)◮ Concat´ener deux chaines :String t = m0 + m1 ;Ou m´ethode concat.String t = m0.concat(m1) ;◮ D´ecomposer en pr´efixe et suffixe, avec la m´ethode ...

Sujets

• informatique
• informaticien

Informations

• Publié par: Shueh
• Nombre de lectures: 75
• Langue: Catalan

Extrait

-1-

INF 421

Luc Maranget

Expressionsre´guli`eres (rationnelles)

[e-mail] http://www.enseignement.polytechnique.fr/profs/ informatique/Luc.Maranget/421/

-2-

Les mots

◮Soit Σ unalphabetre`tcaracedelbme(ens).es

◮Lesmots(ensemble Σ ∗ etiuinfisedsearac)ntsosslect`eres.

◮Unlangageest un sous-ensemble de Σ ∗ .

⊲ s. ¸Lang g a e des mots francai ⋆Σ ={ab . . .}(alphabet usuel, avec accents). ⋆tiicnaonariped,lDnfie´ient).e,sionytcAdae´imri(eed’l

⊲0.e1asnbsereutirce´sedegagnaL ⋆Σ ={01 . . . 9}(chiffres). ⋆arriupnhefipni´pegDen´rerasee✭le chiffre0, ou une suite non-vide de chiffres qui ne commence pas par0✮.

-3-

Op´erationssurlesmots

Un mot est par exemplem=a 0 a 1   a n−1 (nlongueur dem).

◮act`ered’indicece´Re´pulrerracek:a k .

◮er.a’tueleri`rrdeunl’rettemsel:stomxuedCnoac´tnere

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

⊲veti.ssnaiaocre´poitaO ⊲ucheet`adurtoriet`eagae´emtnenvtdi´eleMo (ǫm=mǫ=m). ⊲Danst=mm ′ ,mest unefix´eprdet,m ′ est unsuffixedet.

◮egeabr´tionNota:et=mm ′ . ´

◮Notation des sous-mots :

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

-4-

Lesmotssontdeschaıˆnes La classeString a acup,drape´tropmi(egakd´efaut)java.lang.

◮Mot vide :"".

◮erpleerrroucu´e’deridniarace`tcecPk. ´ public charcharAt(intindex)

◮Concatener deux chaines : ´ String t=m0+m1;

Oum´ethodeconcat. String t=m0.concat(m1) ;

◮ce´Dpoomreser´npxeefiedohtem´laecave,ffixsuetsubstring. 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

-5-

Ope´rationssurleslangages

◮Union ensembliste.

◮oncaCnoitane´t

◮Iert´ioatn.

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

-6-

Lesexpressio´eglie`res ns r u

Une representationpd’un langageL. ´

◮Le mot videǫr´esrepetne{ǫ}.

◮caraceLeert`cntse´eprree{c}.

◮ivelaetnrta’Lp 1 |p 2 represenetL 1 ∪L 2 .

◮nent´ioatcaLacnop 1 p 2 ntse´reepreL 1 L 2 .

◮e´pe´raLnoititp*esereprnteL ⋆ . ´

Pourl’informaticien,lade´finitionm´eriteunede´compositionen syntaxeetse´amtnqieu.

-7-

Syntaxedesexpressionsre´guli` eres

Un motifpd´efiniainsi.ets

◮Le mot videǫest un motif.

◮Uarnct`aceercest un motif.

◮Sip 1 etp 2  . .sont des motifs, alors. ⊲vetinaertla’Lp 1 |p 2 est un motif. ⊲acLcaonnne´toitap 1 p 2 est un motif.

◮Sipest un motif, alors. . . ⊲nioitetp´´earLp*est un motif.

Important’derrbraas,elpsndeused´estunC’ecuutsertoidnnfiti precisions. ´

P={ǫ} ⊎Σ⊎(P× {| × }P)⊎(P× {*})

-8-

a



Exemple de motif

*

b

|

Enpratiqueon´ecrit(syntaxeconcre`te)

b



*

a

(a(b*))|(b(a*)) ou plus simplementab*|ba*

-9-

Priorite´sdesope´rateurs

C’estcommepourlesexpressionsarithme´tiques.Parordre croissantdepriorit´e.

◮La’tlreantive✭|✮(comme l’addition).

◮aLocncat´enation✭✮oc(lemmlumalpitaticn,ioutpetrˆee omis).

◮pee´aL´rontiti✭*✮mmoc,exfi`esimalessuiapal).ceanpost(

Donc

◮ab*se comprend commea(b*).

◮ab|cse comprend comme(ab)|c.

◮ab*|cse comprend comme(a(b*))|c.

-10-

Encore plus pr´ is ec

◮ab*se comprend commea(b*).

a



◮ab|cse comprend comme(ab)|c.

|  a b

* b

◮ab*|cse comprend comme(a(b*))|c.

a



| * b

c

c

-11-

Lespriorite´sner´esolventpastout

Comment comprendreabc, commea(bc)ou(ab)c?

a



b



c

a





b

c

Celan’aaufinalpasd’importance,enraisondel’associativit´ede laconcate´nation.

Mais il y a bien deux arbres possibles.

Undernierd´etail:onpeutrepr´esenterlemotifvidepar().