Quantoren

Aus Siduction Wiki DE
Wechseln zu: Navigation, Suche

Überblick: Reguläre Ausdrücke

Greedy-Quantoren

Jedes Grundelement kann mit einem Quantor versehen werden, der die Anzahl der Elemente festlegt:

  • '*' bedeutet beliebig oft, also auch 0-mal
    • Di.*r findet Dir oder Dieter oder Dichtungsringhalter
  • '+' bedeutet mindestens einmal
    • D.+r findet Dur oder Direktor, aber nicht Dr
  • {n} bedeutet genau n-mal. n ist eine Ganzzahl.
    • datei_[0-9]{3}.txt passt auf datei_001.txt oder datei_973.txt, aber nicht auf datei_1.txt
  • {m,n} bedeutet zwischen m und n mal. m und n sind Ganzzahlen.
    • Kapitel_[0-9]{1,3} passt auf Kapitel_0 oder Kapitel_23 oder Kapitel_999
  • {m,} bedeutet mindestens m-mal.
    • .{5,} passt auf alles, was mindestens 5 Zeichen lang ist.
  • {,n} bedeutet höchstens n-mal.
    • .{,5} passt auf alles, was höchstens 5 Zeichen lang ist.
  • '?' ist die Abkürzung für {,1}, also 0 oder einmal.
    • Alles? passt auf Alle oder Alles

Übung:

  • In einer Datei stehen Briefköpfe ähnlich folgendem Beispiel. Mit welchem Muster findet man 1) Die Anrede 2) die Orte
    • Frau Saubermann
    • Schlüsselblumenstr. 3
    • 01234 Buxtehude

Reluctant-Quantoren

Die Quantoren '*' und '+' sind greedy (gierig): Sie versuchen immer, möglichst viele Zeichen "zu schlucken".

Es gibt die zusätzlichen Quantoren '*?' und '+?', die als "non-greedy" oder "reluctant" bezeichnet werden: Sie schlucken möglichst wenig Zeichen:

Greedy:

  • Text: datei.txt.txt
  • Muster: .*.txt
  • Gefunden: datei.txt.txt

Non-Greedy:

  • Text: datei.txt.txt
  • Muster: d.*?\.txt
  • Gefunden: datei.txt
  • \s White-Spaces: [ \t\v\f\n\r] Leerzeichen, Tabulatoren, Zeilenvorschub
  • \S Alles außer "White-Spaces"

Possessiv-Quantoren

Der Greedy-Quantor verhält sich so, wie es intuitiv als "richtig" empfunden wird: Er schluckt möglichst viele Zeichen, jedoch nur soviele, dass nachfolgenden Bedingungen immer noch erfüllt werden können.

Die Suche läuft so ab:

  • Der Vergleich beginnt mit dem ersten Element des Musters und wird elementweise mit dem jeweils rechten Nachbarelement fortgesetzt.
  • Jeder Greedy-Quantor wird maximal expandiert.
  • Ist das Ende des Musters erreicht: Abbruch, wenn gefunden
  • Wenn nicht, wird von rechts beginnend jede von einem Greedy-Quantor "geschluckte" Zeichenkette um eins verkürzt und der Vergleich der nachfolgenden Muster-Elemente wiederholt.

Beispiel:

  • Muster: B\w*n.*a
  • Text: Banane
Text || Muster ||Kommentar
B B B passt
Banane B\w+ Greedy-Quantor schluckt alles
Banane B\w+n n passt nicht, also Eingabe von \w+ um ein Zeichen kürzen:
Banan B\w+n n passt. Vergleich mit nächstem Musterelement: .*
Banane B\w+n.* n passt. Quantor schluckt alles, also e
Banane B\w+n.*a a passt nicht: Also ein Zeichen zurück
Banan B\w+n.*a a passt nicht. Das Element .* ist ausgeschöpft (kein Zeichen), daher Reduktion beim vorigen Greedy \w+ ein Zeichen zurück
Bana B\w+n n passt nicht. Ein Element zurück
Ban B\w+n n passt. Nächstes Element: .*
Banane B\w+n.*a a passt nicht. Ein Element zurück
Banan B\w+n.*a a passt nicht. Ein Element zurück
Bana B\w+n.*a a passt. Ende

Dieses Verfahren wird Backtracking genannt.

Das ist eine sehr bequeme Methode für den Benutzer, aber auch sehr aufwändig: Die Anzahl der Suchpfade wächst exponentiell mit der Zahl Zeichen der Eingabe und der Anzahl der Greedy-Operatoren.

Will man diese Ineffizienz vermeiden und trotzdem ein "längstes Auftreten" eines Musters erreichen, so leisten dies die Possessiv-Quantoren, die ohne Backtracking arbeiten. Sie schlucken alle Zeichen, die auf den Ausdruck passen, ohne Ausnahme.

Syntax: Dem Quantor wird ein '+' nachgestellt: *+, ++

  • Sinnlose Anwendung: x.*+y
    • .*+ schluckt alle Zeichen, danach kann also nie 'y' kommen.
  • Sinnvolle Anwendung: x\w*+!
    • \w*+ schluckt alle alphanumerischen Zeichen. Danach kann ein '!' stehen.
    • Das erste Zeichen nach einem Posessivquantor darf nicht in der Menge der Elemente des Possessivqnantors enthalten sein.
  • Sinnvolle Anwendung: \([^)]++\)
    • Das Element des Quantors ist die Negation des Zeichens nach dem Quantor.

Hinweis: Gute RExpr-Interpreter erkennen, wann ein Possessivquantor möglich ist, und wandelt dann einen Greedy-Quantor in den effizienteren Possessivquantor um.