Reguliere expressie

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

Een reguliere expressie (afgekort tot “regexp”, “regex” of RE) is een manier om patronen te beschrijven waarmee een computer tekst kan herkennen. Er bestaat hiervoor een formele syntaxis, die grotendeels is gestandaardiseerd.

Reguliere expressies worden bijvoorbeeld in teksteditors gebruikt om stukken tekst te doorzoeken, te manipuleren, 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 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.

Grondbegrippen[bewerken]

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, 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[bewerken]

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[bewerken]

Externe links[bewerken]

Bronnen, noten en/of referenties