Reguliere expressie

Een reguliere expressie (uit het Engels, regular expression, afgekort tot “regexp”, “regex” of RE) is een manier om patronen te beschrijven waardoor een computer softwarematig tekst kan herkennen. Er bestaat hiervoor een formele syntaxis, die deels is gestandaardiseerd.

Reguliere expressies worden bijvoorbeeld in teksteditors gebruikt om stukken tekst te doorzoeken of te veranderen; in andere programma's worden ze gebruikt om te controleren dat bepaalde patronen voorkomen. Veel programmeertalen ondersteunen reguliere expressies voor tekstmanipulatie. Sommige, zoals Perl en JavaScript, hebben ze zelfs in hun syntaxis ingebouwd. Reguliere expressies zijn bekend geworden door hulpprogramma’s van het besturingssysteem Unix als 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.

Grondbegrippen

Een reguliere expressie omschrijft een verzameling tekenreeksen (strings) zonder ze alle afzonderlijk 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. Sommige tekens hebben een speciale betekenis:

Een punt (.) staat voor een willekeurig teken, behalve het teken voor een newline (\n).
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” of “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 voorafgaande teken ten minste één keer moet voorkomen, bijvoorbeeld “goo+gle” herkent google, gooogle, goooogle, enz.
?: Een vraagteken geeft aan dat het voorafgaande teken ten hoogste één keer mag voorkomen, bijvoorbeeld “De Bruij?n” herkent “De Bruin” en “De Bruijn”.
*: Een sterretje geeft aan dat het voorafgaande 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”.

Deze constructies kunnen worden gecombineerd 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 meestal worden de bovenstaande gebruikt.

Wiskunde

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

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

$\emptyset$ is een reguliere expressie.
$\epsilon$ is een reguliere expressie.
Een symbool $a\in \Sigma$ is een reguliere expressie.
Als $R$ en $S$ reguliere expressies zijn, dan zijn ook
- $(RS)$
- $(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 $\epsilon$ beschrijft de taal bestaande uit alleen de “lege string” $\epsilon$ : $L(\epsilon )=\{\epsilon \}$
de RE $a$ , voor $a\in \Sigma$ beschrijft de taal bestaande uit alleen $a$ : $L(a)=\{a\}$
$L(RS)=L(R)L(S)$ , waarbij voor twee talen $L$ en $L'$ : $LL'=\{xy\mid 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|\epsilon )$
$R+=RR*$

De talen die door reguliere expressies kunnen worden omschreven komen overeen met de reguliere talen.

Zie ook

Commons heeft mediabestanden in de categorie Regex.

Externe links

(en) regular-expressions.info Site over het gebruik van reguliere expressies
(en) Regular Expressions - Referenties van The Open Group

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.