- 20 April 2006
- 22.680
- 1.315
Danke @Tyrell für diesen ThreadReguläre Ausdrücke
Allgemeine Erklärung und kurze Einweisung zur Nutzung in MySQL und PHP
Im Folgenden wir der Begriff "Reguläre Ausdrücke" mit regA abgekürzt.
Einleitung
Was sind regA?
regA sind ein abstraktes Konstrukt. Sie sind quasi eine Bastelanleitung für eine Sprache. Diese Sprache enthält bestimmte Wörter, die sich mit Hilfe der regA herleiten lassen. Man kann also nach betimmten Vorgaben bestimmte Wörter erstellen. Andersherum kann man überprüfen, ob ein Wort sich durch einen regA erstellen lässt, also Teil der Sprache ist, die durch den regA beschrieben wird.
Achtung: "Sprache" ist in diesem Zusammenhang ein abstrakter Begriff, es handelt sich hierbei nicht um die gesprochenen Sprachen, wie Deutsch oder Englisch sondern um ein theoretisches Konstrukt.
Das ist kompliziert und ich verstehe gar nichts. Soll ich mir den Text echt reinziehen?
regA sind sicherlich nicht einfach. Aber sie sind auch nicht so schwer, dass man es nicht verstehen kann. Ich gehe hier sehr ausführlich auf das Thema ein und behandele es ohne viel Theorie und fast komplett ohne Mathematik. regA sind ein sehr mächtiges Werkzeug und jeder, der sich tiefer mit der Informatik beschäftigen will, kommt nicht darum herum, sie irgendwann mal zu lernen.
Dieser Text ist so geschrieben, dass ihn eigentlich auch Anfänger verstehen können. Einzige Voraussetzung ist: ein wenig logisches Verständis. Aber das braucht man ja sowieso, wenn man in die Programmierung einsteigen möchte.
Wichtig ist, dass ihr euch den Text langsam und komplett durchlest. Das hier ist nichts, was man mal eben in 5 Minuten fertig bringen kann, ein wenig Zeit müsst ihr also auf jeden Fall mitbringen. Vielleicht müsst ihr die ein oder andere Passage 2 oder 3 mal lesen. Lasst euch Zeit, macht zwischendurch etwas anderes und lest euch dann wieder einen Teil durch. Schlaft eine Nacht drüber und lasst die Infos sacken. Irgendwann kommt dann die Erleuchtung.
Wozu braucht man regA denn jetzt mal konkret?
Die Einsatzmöglichkeiten sind sehr vielfältig; in erster Linie werden sie bei der Suche verwendet. Durch regA lassen sich sehr komplexe Suchvorgänge absolut präzise gestalten. Weiterhin kann man Zeichenketten überprüfen, wie z.B. Emailadressen; hier lässt sich nachschauen, ob die Adresse ein korrektes Format hat. Das Gleiche gilt für die Überprüfung von Usernamen auf bestimmte Bedingungen. regA sind ein sehr, sehr mächtiges Werkzeug und es gibt viele Einsatzmöglichkeiten.
Woher kommen die regA?
Die regA sind ein Grundlegendes Werkzeug in der Informatik. Sie kommen z.B. bei endlichen Automaten und akzeptierten Sprachen zum Einsatz und helfen, solche Konstrukte kompakt und präzise zu Modellieren.
Sprachen und Reguläre Ausdrücke, die Theorie.
Was genau ist denn jetzt eine Sprache?
Eine Sprache definiert sich Abstrakt durch die Menge aller Wörter, die zu ihr gehören. Die Wörter setzen sich aus einzelnen Zeichen eines Alphabets zusammen.
Wichtig: Sprache, Wörter und Alphabet haben erstmal nichts mit unserer Sprache, diesen Wörtern und Buchstaben zu tun.
Man kann sich ein Alphabet selber definieren. Für die folgenden Beispiele, die hier noch auftauchen werden, nehmen wir uns ein ganz einfaches Alphabet A, es besteht nur aus den beiden Zeichen 0 und 1.
Formal:
Alphabet A:={0,1}
Nun können wir uns eine formale Sprache definieren. Sie enthält 3 Wörter, die wir aus dem Alphabet zusammensetzen: 10, 01, 001
Formal:
Sprache S1:={10, 01, 001}
Nun haben wir eine Sprache S1, bestehend aus 3 Wörtern bestehend aus einem Alphabet mit 2 Buchstaben. Die Sprache ist definiert durch die Wörter, die man mit ihr bilden kann. Anders gesagt: Alle Wörter einer Sprache definieren die Sprache.
RegA können ebenfalls eine Sprache definieren
Die Schreibweise, alle Wörter einer Sprache aufzuschreiben, um die Sprache zu definieren, ist natürlich lästig. Wenn man jetzt eine Sprache mit 10 Millionen Wörtern hat, wird man die natürlich nicht alle aufschreiben, um die Sprache zu definieren. Hier kommen die regA zum Einsatz.
Fangen wir mit einem Beispiel an. Wir definieren uns die Sprache S2:
S2:={1, 10, 100, 1000}
S2 besteht also aus 4 Wörtern.
Diese Sprache lässt sich jetzt auch als regA schreiben.
Das sähe dann so aus: 1(0)*
Aaaahja, ich raffe gar nichts.
Das ist nicht schlimm, denn hier wird erklärt, wie die regA entstehen.
Schauen wir uns zuerst mal die einzelnen Bestandteile der regA an:
Natürlich sind die Buchstaben unseres Alphabets darin zu finden, also 0 und 1. Dann gibt es noch Klammern und das *-Symbol. Desweiteren gibt es noch ein +-Symbol und ein |-Symbol.
Und wie ließt man jetzt so einen regA?
Generell kann man so einen regA nicht "richtig" lesen. Er enthält eben alle Wörter, die man aus der vom regA definierten Sprache bilden kann. Man kann mit jedem mal "lesen" ein Wort bilden, irgendwann versteht man dann, wie der jeweilige regA funktioniert. Wie das mit dem Lesen geht, das erkläre ich anhand von ein paar Beispielen:
Nehmen wir den regA r1:=1. Das ist also sehr einfach. Er besteht nur aus einem Buchstaben des Alphabets und kann auch nur ein Wort bilden. Das Wort lautet "1".
Man liest den regA also von links nach rechts. Wenn keine Operatoren wie +,* oder | angegeben sind, kann man alle Buchstaben so aneinanderreihen. In diesem Beispiel ist das easy, da nur ein Buchstabe da ist.
Nächstes Beispiel: r2:=010
Auch hier sind keine Operatoren drin, also liest man ihn einfach von links nach rechts. Auch dieser regA kann nur ein Wort bilden, es lautet 010.
Das ist langweilig. Ich dachte, regA könnten eine ganze Sprache definieren und nicht bloß ein Wort!
Klar, das können sie. Dafür gibt es ja noch unsere Operatoren. Und die werden jetzt erklärt.
1. Der |-Operator.
Der |-Operator ist ein "oder"-Operator. Man kann sich also aussuchen, welchen Teil man nimmt. Die Schreibweise schaut so aus: (ausdruck1|ausdruck2|ausdruck3|...)
Der Oder-operator wird also in eine Klammer gepackt. Es lassen sich beliebig viele Ausdrücke aneinanderreihen. Kommt man zu so einer Klammer, kann man also jeweils nur einen der Ausdrücke wählen, um das Wort zu bilden.
Klingt ziemlich kompliziert, ist es aber nicht, darum kommt hier ein Beispiel:
r3:=(0|1)
Dieser regA kann 2 Wörter bilden. Fangen wir an, von links zu lesen. Es kommt also eine Klammer, mit der Auswahl zwischen 0 und 1.
Als erstes wählen wir die 1. Der RegA ist damit abgearbeitet, da ja nicht mehr drin steht. Unser erstes Wort lautet also "1".
Lesen wir den regA nochmal, können wir wieder wählen. Wir können nochmal die 1 nehmen, dann haben wir wieder das Wort "1". Da das langweilig ist, nehmen wir diesesmal die 0. Damit erhalten wir das Wort "0". Also lassen sich mit diesem RegA die Worte 0 und 1 erstellen.
Noch ein Beispiel:
r4:=1(0|1)0
Dieser RegA ist schon ein wenig komplexer. Lesen wir ihn mal. Am Anfang steht eine 1. Danach haben wir die Auswahl zwischen 0 und 1, dann folgt eine 0. Wählen wir eine 1. Dann erhalten wir das Wort
110.
Beim zweiten Durchlauf wählen wir die 0. Dann erhalten wir
100.
Es lassen sich also die Worte 110 und 100 herleiten. Das liegt daran, dass die 1 am Anfang und die 0 am Ende fest sind, in der Mitte haben wir die Wahl zwischen 1 und 0.
Es folgen ein paar Beispiele, um das zu verdeutlichen. Schaut sie euch genau an:
r5:=(0|1)(0|1)
Wörter: 00, 01, 10, 11
r6:=(0|1)0(0|1)
Wörter: 000, 001, 100, 101
Man kann die Ausdrücke natürlich auch verschachteln; Beispiel:
(01|(0|1))
WörteR: 01,0,1
Wenn man also nicht 01 wählt, dann kann man zwischen 0 und 1 wählen.
OK, das habe ich soweit verstanden. Was hat es jetzt mit dem *-Operator auf sich?
Der *-Operator besagt, dass der vorhergehende Ausdruck beliebig oft oder gar nicht in den Wörtern vorkommen kann. Schreibweise: (ausdruck)*
Beispiel:
(0)*
Wörter:
"" <-Leeres Wort, besteht also aus keinem Buchstaben. Ist aber dennoch möglich.
0
00
000
0000
00000
...
Hiermit lassen sich unendlich viele Wörter machen, die jeweils eine Aneinanderreihung von 0 sind.
Weitere Beispiele:
1(0)*1
Wörter:
11
101
1001
10001
100001
...
Hier sieht man deutlich, dass die 0 auch gar nicht vorkommen kann.
Beispiel in Kombination mit |:
((0*)|1)
Wörter:
""
0
00
000
0000
...
1
Man kann also wählen zwischen beliebig vielen 0 und einer 1.
Anders ist es hier:
(0|1)*
Wörter:
0
1
01
10
000
010
0011
1010
1111
0000
....
Hier kann man beliebig oft zwischen 1 oder 0 wählen; der oder-Operator gehört also mit zu dem Teil, der wiederholt wird.
Noch 2 Beispiele:
1(0|1)*0
Worte:
100010000100010010
10
Am Anfang steht eine 1, dann kommt beliebig oft 0 oder 1 und dann eine 0.
Das * bezieht sich auf die Klammer, man kann also die Klammer mit dem 'oder' beliebig oft wiederholen.
1(0*|1)0
Worte:
10
110
100000
Nicht aber 1110 oder 1100
Warum? Es kommt eine 1; dann kommen entweder beliebig oder keine 0en ODER EINE 1 und dann eine 1
Das * bezieht sich also nur auf die eine 0, nicht auf die Klammer.
Wozu ist das + gut?
Das + funktioniert genauso, wie das *, mit dem Unterschied, dass der Ausdruck, auf den sich das + bezieht, mindestens einmal vorkommen muss.
Hier nochmal die Gegenüberstellung:
*: Beliebig oft ODER GAR NICHT
+: Beliebig oft, ABER MINDESTENS EIN MAL.
Beispiele:
0*1
Wort: 1,01, 001....
Die Null kommt gar nicht vor
0+1
Wort: 01, 001, 0001,...
Die Null kommt mindestens einmal vor.
