Reguliere expressie

Een reguliere expressie (afgekort tot “regexp”, “regex” of RE) is een manier om patronen te beschrijven waarmee een computer tekst kan herkennen.

Reguliere expressies worden in veel editors en hulpprogramma’s gebruikt om stukken tekst te doorzoeken en te manipuleren op basis van bepaalde patronen. Veel programmeertalen ondersteunen reguliere expressies voor tekstmanipulatie. Sommigen, zoals Perl en JavaScript, hebben ze zelfs in hun syntaxis ingebouwd. Reguliere expressies zijn vooral populair geworden door de hulpprogramma’s van het besturingssysteem Unix, zoals sed en grep.

Een eenvoudige variant van de reguliere expressie is in veel besturingssystemen te vinden als de jokertekens die gebruikt kunnen worden bij het zoeken naar bestandsnamen.

Inhoud

[bewerk] Basisconcepten

Een reguliere expressie omschrijft een verzameling tekenreeksen (strings) zonder ze allemaal op te noemen. De drie strings Handel, Händel en Haendel kunnen bijvoorbeeld beschreven worden met het patroon “H(a|ä|ae)ndel”.

Gewone letters en cijfers in de reguliere expressie herkennen hetzelfde teken in de te vinden tekenreeks. Een aantal tekens hebben speciale betekenis:

Een punt (.) staat voor een willekeurig teken.
Vierkante haken geven een lijst van mogelijke tekens: [abc].
- Binnen vierkante haken staat een minteken voor een reeks: [a-zA-Z] is het patroon waarmee alle letters “gevangen” worden.
- Een dakje als eerste teken binnen de vierkante haken verandert de tekenverzameling in het omgekeerde: [^0-9] herkent alles wat geen cijfer is.
Een dakje (^) staat voor het begin van de regel.
Een dollarteken ($) staat voor het eind van de regel.

Deze basiselementen kunnen worden gecombineerd met de volgende constructies:

Keuze

Een verticale balk scheidt de alternatieven, bijvoorbeeld “groen|rood” herkent “groen” en “rood”.

Kwantificatie

Een kwantor achter een teken geeft aan hoe vaak dat teken voor mag komen. De meest voorkomende kwantoren zijn +, ? en *:

+: Een plusteken geeft aan dat het ervoorstaande teken tenminste één keer moet voorkomen, bijvoorbeeld “goo+gle” herkent google, gooogle, goooogle, enz.
?: Een vraagteken geeft aan dat het ervoorstaande teken ten hoogste één keer mag voorkomen, bijvoorbeeld “De Bruij?n” herkent “De Bruin” en “De Bruijn”.
*: Een sterretje geeft aan dat het ervoorstaande teken nul of meer keer mag voorkomen, bijvoorbeeld “0*42” herkent 42, 042, 0042, enzovoort.; Een veelvoorkomende constructie is .*, dat alle tekst vindt.

Groepering: Haakjes maken een eenheid van het patroon waar ze omheen staan, bijvoorbeeld “(va|moe)der” is hetzelfde als “vader|moeder” en “(groot)?vader” herkent zowel “vader” als “grootvader”.

Al deze constructies kunnen gecombineerd worden in hetzelfde patroon, zodat “H(ae?|ä)ndel” hetzelfde is als “H(a|ae|ä)ndel”.

De precieze syntaxis varieert enigszins tussen de verschillende programma’s, maar de bovenstaande komen het meeste voor.

[bewerk] Wiskunde

De reguliere expressies komen voort uit de wiskundige logica, meer bepaald de theorie van de formele talen. Ze zijn uitgevonden door de Amerikaanse wiskundige Stephen Kleene als methode om reguliere talen te beschrijven.

De verzameling reguliere expressies over een alfabet (verzameling symbolen) $Σ$ wordt als volgt inductief gedefinieerd:

$\emptyset$ is een reguliere expressie.
$ε$ is een reguliere expressie.
Een symbool $a \in \Sigma$ is een reguliere expressie.
Als R en S reguliere expressies zijn, dan zijn ook
- $(R S)$
- $(R | S)$
- en $R *$

reguliere expressies.

De taal $L$ die beschreven wordt door een reguliere expressie (de verzameling strings die “herkend” worden door een patroon) wordt ook inductief gedefinieerd:

de RE $\emptyset$ beschrijft de lege taal: $L(\emptyset) = \emptyset$
de RE $ε$ beschrijft de taal bestaande uit alleen de “lege string” $ε$ : $L (ε) = {ε}$
de RE $a$ , voor $a \in \Sigma$ beschrijft de taal bestaande uit alleen $a$ : $L (a) = {a}$
$L (R S) = L (R) L (S)$ , waarbij voor twee talen $L$ en $L'$ : $LL' = \{xy | x \in L \text{ en } y \in L'\}$
$L(R|S) = L(R) \cup L(S)$
$L(R*) = L(\epsilon) \cup L(RR*) = L(\epsilon) \cup L(R) \cup L(RR) \cup L(RRR) \cup \ldots$

De kwantoren ? en + kunnen als volgt gedefinieerd worden om hun gebruikelijke gedrag te veroorzaken:

$R ? = (R | ε)$
$R + = R R *$

Het blijkt dat de taal $L (R)$ van een reguliere expressie $R$ altijd een reguliere taal is.

[bewerk] Zie ook

Stephen Kleene, Henry Spencer
ed, expr, awk, Emacs, vi, lex, Apache, POSIX
SNOBOL, Perl, Python, PHP
eindigetoestandsautomaat, reguliere taal, Kleene-ster

[bewerk] Bronnen, noten en/of referenties

Bronnen, noten en/of referenties:

Jeffrey Friedl. Mastering Regular Expressions, O’Reilly, ISBN 0-596-00289-0
John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001).Introduction to Automata Theory, Languages, and Computation. Addison Wesley.

[bewerk] Externe links

analyser.oli.tudelft.nl Tutorial van TUDelft
(en) www.regexlib.com Bibliotheek met expressies
(en) www.regular-expressions.info Site over het gebruik van reguliere expressies