Reguliere Expressies ☞ Een reguliere expressie (regexp, regex, regxp) is een string (een woord) die, volgens bepaalde syntaxregels, een verzameling strings (een taal) beschrijft ☞ Reguliere expressies worden veel gebruikt in Unix texteditors, tools, programmeertalen, voor het zoeken naar patronen in tekst, en voor substitutie van strings
1/15
18 oktober 2004
Geschiedenis ☞ Theorie van formele talen ☞ Kleene’s algebra van reguliere verzamelingen ☞ Ken Thompson introduceerde de notatie in de Unix editor ed ☞ Regex worden nu gebruikt in bijvoorbeeld grep, awk, emacs, vi, lex, perl.
2/15
18 oktober 2004
Reguliere expressies in de theorie van formele talen (1) Een reguliere expressie representeert een verzameling strings/woorden (een taal). Reguliere expressies worden opgebouwd uit constanten en operaties. Zij gegeven een eindig alfabet Σ, dan zijn de volgende constanten gedefinieerd: ☞ (lege verzameling) ∅ representeert de lege verzameling ∅ ☞ (lege string) representeert {} ( is een string met lengte 0) ☞ (literals) een karakter a in Σ representeert de verzameling {a}
3/15
18 oktober 2004
Reguliere expressies in de theorie van formele talen (2) De operaties (voor reguliere expressies R en S): ☞ (concatenatie) RS representeert de verzameling {αβ | α ∈ R, β ∈ S}. ☞ (vereniging) R ∪ S representeert de vereniging van R en S ☞ (Kleene star) R∗ representeert de afsluiting van R onder concatenatie, i.e., R∗ = ∪ R ∪ RR ∪ RRR ∪ · · · Bindingsterkte: Kleene star > concatenatie > vereniging. Haakjes worden weggelaten als dat kan: (ab)c wordt geschreven als abc, en a ∪ (b(c∗)) als a ∪ bc∗
4/15
18 oktober 2004
Reguliere expressies in de theorie van formele talen (3) Voorbeelden. Laat Σ = {0, 1}. ☞ De expressies 00 en 0100100 representeren respectievelijk de verzamelingen {00} en {0100100} ☞ De expressies 0 ∪ 1 en 10 ∪ 01, representeren respectievelijk de verzamelingen {0, 1} en {10, 01} ☞ De expressies 0∗ en (01)∗ representeren respectievelijk de verzamelingen {, 0, 00, 000, . . .} en {, 01, 0101, 010101, . . .} ☞ De expressie (0 ∪ 00)1∗ representeert {0, 00, 01, 001, 011, 0011, . . .} ☞ (0 ∪ 00)1∗ = 01∗ ∪ 001∗
5/15
18 oktober 2004
Reguliere expressies in de theorie van formele talen (4) Meer voorbeelden. ☞ a ∪ b∗ representeert {a, , b, bb, bbb, . . .} ☞ (a ∪ b)∗ representeert de verzameling van alle strings bestaande uit a’s en b’s, inclusief de lege string ☞ b∗(ab∗)∗ idem ☞ ab∗(c ∪ ) representeert de verzameling van strings die beginnen met een enkele a, gevolgd door nul of meer b’s, en eindigend met optioneel een c
6/15
18 oktober 2004
Reguliere talen ☞ De talen die door reguliere expressies kunnen worden gerepresenteerd noemen we de reguliere talen ☞ Daarmee corresponderen ze met de zogenaamde “type 3” grammatica’s in de Chomsky hierarchy ☞ Ze zijn minder expressief dan context-vrije grammatica’s (CFGs) zoals BNF (Backus-Naur Form) grammatica’s ☞ Zo kun je bijvoorbeeld in reguliere expressies geen nesting definieren ☞ Noot: de syntax van Perl is veel rijker dan die van reguliere expressies; strict genomen zijn de reguliere expressies van Perl niet regulier. Deze expressivieteit kan ten koste gaan van de effectiviteit: worstcase complexiteit van matchen van een string tegen een Perl regex is 7/15
18 oktober 2004
exponentieel in de lengte van de input. (In de praktijk valt dit gelukkig mee.)
8/15
18 oktober 2004
Voorbeeld BNF grammatica
::= 0 | 1 <expr> ::= | (<expr> + <expr>) | (<expr> * <expr>) Deze BNF grammatica genereert o.a. de strings 0, 1, (0 + 1), (1 * (1 + 1)) Noot: de taal die gegenereerd wordt door deze grammatica is context-vrij, maar niet regulier; je kunt de expressies van deze taal niet met een reguliere expressie karakteriseren
9/15
18 oktober 2004
Unix regexps (1) De volgende syntax is min of meer standaard voor veel Unix tools en programmeertalen. Basisregels: 1. Ieder afdrukbaar ASCII karakter dat geen metakarakter is, is een reguliere expressie die zichzelf representeert. 2. . representeert ieder enkel karakter 3. ˆrepresenteert het begin van een regel 4. $ representeert het einde van een regel 5. \ gevolgd door een metakarakter representeert dat karakter zelf. Dus: \. representeert een punt (.) 10/15
18 oktober 2004
6. [ ] representeert een enkel karakter. Tussen de haken staat een karakterisering. ➢ [a] representeert karakter a ➢ [abc] representeert karakter a, b, of c ➢ [a−z] representeert een karakter in de range a–z (karakters geordend volgens hun ASCII codering) ➢ [A−Za−z0−9] representeert een cijfer of letter ➢ [ˆE] representeert ieder karakter dat niet door [E] gerepresenteerd wordt ➢ [acq−z] representeert a, c, of een karakter in q–z.
11/15
18 oktober 2004
Unix regexps (2) Inductieve regels: Als A en B reguliere expressies zijn, dan 1. AB is een reguliere expressie (concatenatie), 2. A|B is een reguliere expressie (keuze/vereniging), 3. A∗ is een reguliere expressie (Kleene star) 4. A+ is een reguliere expressie (´e´en of meer geconcateneerde voorkomens van A) 5. A? is een reguliere expressie (nul of ´e´en voorkomens van A) 6. (A) is een reguliere expressie (Perl) 7. \(A\) is een reguliere expressie (vi) 12/15
18 oktober 2004
8. (Perl) A{m, n} voor integers m en n representeert m tot n geconcateneerde voorkomens van A. 9. (Perl) A{m} voor integer m representeert m geconcateneerde voorkomens van A. 10. Concatenatie bindt sterker dan keuze, dus A | BC = A | (BC)
13/15
18 oktober 2004
Voorbeelden Wat staat hier (perl)? $timeStr =~ s/([0-9]+):([0-5][0-9]):([0-5][0-9])/\2 min., \3 sec. after \1/;
En hier (vi)? s/\([0-9]+\):\([0-5][0-9]\):\([0-5][0-9]\)/\2 min., \3 sec. after \1/;
14/15
18 oktober 2004
Meer voorbeelden ➢ .ap representeert o.a. aap, lap, kap ➢ [al]ap representeert aap en lap ➢ [ˆa]ap representeert o.a. lap en kap, maar niet aap ➢ ˆ[al]ap representeert aap en lap, maar alleen aan het begin van een regel ➢ [al]ap$ representeert aap en lap, maar alleen aan het einde van een regel ➢ [al]+ap representeert o.a. aap, lap, aaap, alap, laap, llap, etc. ➢ [al]?ap representeert ap, aap en lap ➢ [aA]ap | [nN ]oot representeert aap, Aap, noot, en Noot ➢ .\.(\(|\)) representeert o.a. a.) 15/15
18 oktober 2004
