Thread Frage zu Perlfaq6: "Can I use Perl regular expressions to match balanced text?" (7 answers)
Opened by Gast at 2009-10-14 09:36

sid burn
 2009-10-14 13:12
#126965 #126965
User since
2006-03-29
1520 Artikel
BenutzerIn

user image
Quote
Bei beiden Beispielen bekomme ich mit (wie es geschrieben steht) und ohne dem "possesive +" das gleiche ausgegeben. Wird das possesive + gesetzt, damit es schneller geht?

Ja und nein zugleich.
Wenn du einen String hast der komplett richtig ist, sprich wodrauf die Regex auch matcht, dann macht das possesive + in der Regel gar keinen Unterschied.

Wenn das aber nicht der Fall ist, dann versucht die Regex Engine durch Backtracking eine andere Lösung zu finden. Und im extremfall können hier "Millionen" versuche entstehen. Daher bei einem String wo die Regex nicht matchen würde, beendet sich die Regex Engine früher und spart deutliche Ressourcen.

Ansonsten verändert sich dadurch auch das Regex Verhalten wodurch sich das Match verhalten ändern kann. Und nur um es zu erwähnen das doppel plus is equivalent zu "(?> )" nur eine kürzere schreibweise.

Simples Beispiel:
Code: (dl )
1
2
3
4
my $str = 'abcdefgha';

print $str =~ m/\A\w+a/ ? "MATCHED\n" : "NO MATCH\n";
print $str =~ m/\A\w++a/ ? "MATCHED\n" : "NO MATCH\n";


Das wird "MATCHED" und dann "NO MATCH" ausgeben. Wenn die Regex Engine anfängt dann wird das "\A\w+" im ersten Beispiel den vollständigen String "abcdefgha" konsumieren. Danach erwartet die Regex Engine ein Literales "a". Da der komplette String schon konsumiert wurde, gibt es nun ein backtracking. Daher vom "\w+" wird ein zeichen wieder freigegeben. Wodurch "\w+" nun "abcdefgh" konsumiert. Danach wird die Regex Engine weiter ausgeführt und es muss ein Literales "a" kommen. Das tut es auch also ist die Regex erfüllt.

Bei "++" oder "(?> )" löscht du die backtracking Informationen daher ein "\w++" gibt keine zeichen mehr frei. Daher im zweiten beispiel konsumiert "\w++" ebenfalls "abcdefgha". Danach erfordert die Regex wieder ein Literales "a". Da wir aber schon am String Ende angekommen sind und kein backtracking geschieht und es auch kein "a" mehr gibt (weil Stringende) schlägt diese Regex Fehl. generell gibt es keine Möglichkeit wie "\w++a" Überhaupt matchen kann. Soetwas schlägt immer fehl.

Ohne "++" und stell dir vor du hast ein 100 zeichen langen string das kein "a" enthält würde die Regex Engine für "\w+" also insgesamt 5050 Kombinationen ausprobieren bis es fehlschlägt nur für das "\w+".

Ansonsten brauch man das löschen des Backtracking manchmal auch damit eine Regex überhaupt korrekt etwas erkennen kann, oder manchmal wirklich um zu verhindern das die Regex Engine unnötige Operationen tut. Als Beispiel.

"\A\w+:"

Liest alle Alphanumerischen Zeichen und erfordert danach ein Doppelpunkt. Match diese Regex nicht. Würde es wieder Backtracking machen immer wieder ein Zeichen frei geben und schauen ob ":" Matcht.

In diesem Fall ist das aber sinnlos da ein zeichen aus "\w" nie ein Doppelpunkt sein kann. "\w++:" ist also klüger da es alle alphanumerischen zeichen einliest und danach ein Doppelpunkt erfordert. Ist es nicht vorhanden. Kann die Regex sofort abbrechen ohne ein backtracking zu machen.

Im Fehlerfall spart es also einiges.

Im korrekten Fall hat es in der regel gar keine Auswirkung. Zum Beispiel der String "hallo:" würde von "\w+:" oder "\w++:" gleich performant gelesen werden. nämlich zuerst erkennen sie die alphanumerischen bereich und dann das Doppelpunkt. backtracking findet nicht statt.
Nicht mehr aktiv. Bei Kontakt: ICQ: 404181669 E-Mail: perl@david-raab.de

View full thread Frage zu Perlfaq6: "Can I use Perl regular expressions to match balanced text?"