Regex passt nicht ab bestimmter Zeichenzahl

[blackbird]

Hallo,

ich bin beim basteln einer RegEx für eine bestimmte Anwendung
auf ein Verhalten meines Ausdruckes gestossen, den ich beim
besten Willen nicht interpretieren kann.

Untenstehender Ausdruck stammte ursprünglich aus einer
Mailadressen-Validierung, ich habe ihn beim Einkreisen des
Problems schon etwas reduziert.

(Ich weiss, dass man mit diesem Muster nicht alle RFC-konformen
Mailadressen erwischt, darum geht es mir nicht. Ich möchte nur
wissen, ob ich den Ausdruck nicht richtig interpretiere oder
ob irgendein Bug (oder Feature) im PHP steckt.)

Basis ist ein Linux mit
Novell SLES 10 SP1
PHP 5.1.2-29.45

Ich verstehe die Regex "muster" aus untenstehenden Programmschnipsel
wie folgt:

- Am Anfang des Strings muss ein "@" stehen.
- Dann kommen ein oder mehrere Buchstaben u/o Ziffern
- Optional folgen beliebig oft, durch "." oder "-" getrennt, weitere Buchstaben/Zifferngruppen
- Hinter dem letzten Punkt muß eine beliebig lange, aber mindestens 2 Zeichen, Buchstabenfolge stehen, bevor das Stringende kommt.

<?php
$teststring = "@xy.ertzgrfrtezgdkjkjkjktzzegt";
$muster = "/^@[A-Za-z\d]+([\.\-]?[a-zA-Z\d]+)*\.[A-Za-z]{2,}$/";
if(preg_match($muster, $teststring))
{
echo "Passt schon\n";
} else
{
echo "Passt net\n";
}
?>

Was ich jetzt nicht verstehe:
Wenn der "teststring" aus meinem Beispielprogramm hinter dem Punkt 2 bis
zu 20 Zeichen hat, passt der Ausdruck. Stehen 21 Zeichen hinter dem
Punkt oder mehr, dann passt er nicht mehr ("Passt net").
Warum gerade ab 21 Zeichen.

Übrigens, wenn ich das gleiche PHP-Programm auf einem Novell Netware
Server (NW6.5 SP6) ausführe, kriege ich einen ABEND im PHP5LIB.NLM
wenn mein Teststring 21 oder mehr Zeichen hinter dem letzten Punkt hat.
Ein ABEND unter Netware ist etwa das, was eine Schutzverletzung in
anderen Betriebssystemen ist.

Schonmal vielen Dank
V. Vogel

[smg]

Vielleicht hast du nen Fehler im Programm, gucks dir nochma genau an:
Hier mein Regex, der ist zwar ineffizient aber er geht:

/^@\w+(?:[-.]\w+)*\.\w{2,}$/

Dein PHP Programm:

<?php
$teststring = "@xy.ertzgrfrtezgdkjkjkjktzzegt121212asw";
$muster = '/^@\w+(?:[-.]\w+)*\.\w{2,}$/';
if(preg_match($muster, $teststring))
{
echo "Passt schon\n";
} else
{
echo "Passt net\n";
}
?>

Vielleicht nimmst du atomare Klammern, könnte evt. mehr Performance bringen:

/^@\w+(?>[-.]\w+)*\.\w{2,}$/
Dein PHP Code:

<?php
$teststring = "@xy.ertzgrfrtezgdkjkjkjktzzegt121212asw";
$muster = '/^@\w+(?:[-.]\w+)*\.\w{2,}$/';
if(preg_match($muster, $teststring))
{
echo "Passt schon\n";
} else
{
echo "Passt net\n";
}
?>

P.S: So wünsch ich mir Poss, ausführlich und gut erklärt, dann kann man auch direkt ne Lösung posten die funktioniert! Viel Spass. :)

[blackbird]

Hi SMG,

vielen Dank für die Antwort.

Vielleicht hast du nen Fehler im Programm, gucks dir nochma genau an:


Eher 'nen Fehler im RegEx, mit Programm ist ja bei dem Schnipsel nicht viel.
Es geht mir auch garnicht mehr um eine Mailadresse, dafür gibt's im Netz genügend Lösungen, z.B. bei regexlib.com

Es ist reiner Forscherdrang, warum der Ausdruck, so wie ich ihn notiert habe, sein Verhalten mit der Länge des letzten Teilstrings ändert. Entweder ist mein Ausdruck falsch, dann frage ich mich, wieso es dann mit 20 Zeichen geht und mit 21 nicht. Oder in der RegEx Engine ist ein Bug.

Das mit dem "\w" aus Deinem Vorschlag geht ja bei Mailadressen, aber stell Dir mal vor, Du müsstest einen String aus einer elektronischen Meßeinrichtung analysieren, wo der Zeichenvorrat nicht so umfangreich ist (z.B. Hexadezimal 0-9 und A-F).

Die Maschine liefert Strings nach dem Muster

"@abc.de3-fg.46.4fa5c" oder "@b4.5f"

Das ist der selbe Aufbau wie bei einer MailDomain, aber mit "\w" ist das nicht zu machen, da muß ich schon "[a-fA-F\d]" schreiben.

Naja, trotzdem nochmal vielen Dank.
V. Vogel

[smg]

Jo klar, ich war halt mal Tippfaul! :)
Kannst ja anpassen, aber der Regex geht ja jetzt wenigsten, oder?

[butterkeks]

wenn das Problem noch besteht:
kannst du wenigstens einen simplen Regex a la

(\w+)

mit beliebig langen Eingaben matchen?

Soweit ich das sehe, müssten dein regex und der von smg ja gehen

[cracki]

ich wuerde vermuten, dass die regexp engine im backtracking irgendwann aufgibt.

immerhin matcht die letzte gruppe nur, wenn die erste nicht bis zum ende frisst. wenn die letzte gruppe aber nur auf etwas sehr langes matcht, muessen die vorherigen schrittweise abbauen. dabei wird zwangsweise jede moeglichkeit probiert.


ich hab folgendes regexp auch in python getestet, welches sehr rechenintensive regexps wohl nicht vorzeitig abbricht:

^([\.]?a+)*\.a{2,}$
auf:
.aaaaaaaaaaaaaaaaaaa

das regexp braucht fuer jedes weitere "a" immer mehr zeit zum matchen.

das ? (und der *) macht der regexp engine dort scheinbar zu schaffen.

php bricht im interesse schneller antwortzeiten einfach ab.

in der php doku zu regexps wird das thema "rechenintensive regexps" auch behandelt. link hab ich nicht, kann mich aber erinnern.

[Jan Krüger]

crackis Vorstoß klingt überzeugend; es funktioniert entsprechend einwandfrei, wenn man das ? entfernt.

[smg]

Ja cracki hat's gut erklärt, das mit dem ? und * Geschachtel sollte man sein lassen, einfach an den stellen atomare Klammern setzen, oder gleich den "Designfehler" beheben. Wenn jemand will kann ich das zu der Kaskade im Regex Buch zitieren von O'Reilly, falls daran jemand Interesse hat suche ich die Stelle raus. In der Tat liegt es am übermäßigen Backtracking.

[blackbird]

Hallo,

vielen Dank für Eure Diskussion. Es scheint wirklich ein Backtracking-Effekt zu sein. Man merkt es, wenn man die Zeit zur Ausführung des Programmes misst, wie mit jedem weiteren Zeichen die Laufzeit anwächst.

Da war ein Fragezeichen zuviel, und somit stimmt es nach der Korrektur im Prinzip mit Euren Vorschlägen überein.

Falsch:

$muster = "/^@[A-Za-z\d]+([\.\-]?[a-zA-Z\d]+)*\.[A-Za-z]{2,}$/";
Korrigiert:

$muster = "/^@[A-Za-z\d]+([\.\-][a-zA-Z\d]+)*\.[A-Za-z]{2,}$/";
Im übrigen wurde mit PHP 5.2.0 (welches ich leider noch nicht zum Spielen habe) eine Funktion "preg_last_error()" eingeführt, die einen Fehlercode der letzten PCRE Regex Ausführung zurückgibt.

PREG_NO_ERROR = 0
PREG_INTERNAL_ERROR = 1
PREG_BACKTRACK_LIMIT_ERROR = 2
PREG_RECURSION_LIMIT_ERROR = 3
PREG_BAD_UTF8_ERROR = 4

Gruß
VV