RE, Greedy-Verhalten

Hallo,

in "perldoc perlre" steht, daß ich in einem RE  .* durch nachstellen des ?
erreiche daß .* nur noch die "minmal mögliche Anzahl Zeichen frißt".
Das ist dann doch "höchstens ein Zeichen" und der RE ist dann doch
gleich zu .?

Da Verhalten ist ja anders, das ist mir klar.  Wie kann man denn
am Besten beschreiben wie weit der Greedy-Operator Zeichen frißt?

Frißt er soweit bis der folgende RE paßt?  Oder probiert er alle
Möglichkeiten durch bis der ganze RE komplett paßt?

Ich habe schon diverse male den Greedy-Operator verwendet. Aber
wie beschreibt man eigentlich genau, wie weit der Daten frißt?


Danke für Tips,
Torsten.

Re: RE, Greedy-Verhalten

Torsten Mohr schrieb:
> Hallo,
>
> in "perldoc perlre" steht, daß ich in einem RE .* durch nachstellen des ?
> erreiche daß .* nur noch die "minmal mögliche Anzahl Zeichen frißt".
> Das ist dann doch "höchstens ein Zeichen" und der RE ist dann doch
> gleich zu .?

Nein.
Es ist die minimal mögliche Anzahl, sodass die RE noch matcht.

Beispiel:
$_ = 'ababab';
print /(.*)b/, "\n";
print /(.*?)b/, "\n";

REs versuchen immer, von links nach rechts zu matchen. Die erste RE
nimmt also beim Punkt das erste Zeichen und frisst dann auch alle
weiteren Zeichen bis zum Stringende. Da dann aber noch ein b folgen
muss, gibt der * ein Zeichen zurück - und die RE kann erfüllt werden.

Mit .*? wird zunächst am Anfang probiert, 0 Zeichen zu matchen. Dann
folgt aber kein b. Also matcht man 1 Zeichen mehr. Und dann folgt ein b,
also passt die RE.

> Da Verhalten ist ja anders, das ist mir klar. Wie kann man denn
> am Besten beschreiben wie weit der Greedy-Operator Zeichen frißt?

perldoc -q greedy

Wolf

Re: RE, Greedy-Verhalten

Torsten Mohr schrob:
> Hallo,
>
> in "perldoc perlre" steht, daß ich in einem RE .* durch nachstellen des ?
> erreiche daß .* nur noch die "minmal mögliche Anzahl Zeichen frißt".
> Das ist dann doch "höchstens ein Zeichen" und der RE ist dann doch
> gleich zu .?

Nein, * heißt ja "0 oder mehr Dinge". Der Unterschied liegt darin, in
welcher Reihenfolge die Möglichkeiten durchprobiert werden.

* alleine frisst soviele wie möglich und rückt sie nur wieder heraus,
wenn der Rest der Regex sonst nicht passen würde.

*? frisst erstmal 0 Zeichen, nimmt aber auch mehr, wenn sonst der Rest
der Regex nicht mehr passen würde.

Z.B.:

"Das Salz verzehrt den Leib des Mohren" =~ /(.*)/;
=> $1 = "Das Salz verzehrt den Leib des Mohren"

"Das Salz verzehrt den Leib des Mohren" =~ /(.*?)/;
=> $1 = ""

"Das Salz verzehrt den Leib des Mohren" =~ /(.*)e/;
=> $1 = "Das Salz verzehrt den Leib des Mohr"

"Das Salz verzehrt den Leib des Mohren" =~ /(.*?)e/;
=> $1 = "Das Salz v"

Das heißt auch, dass .*? am Ende einer Regex immer 0 Zeichen frisst.

HTH, Lukas

Re: RE, Greedy-Verhalten

Hallo,

>> in "perldoc perlre" steht, daß ich in einem RE .* durch nachstellen des ?
>> erreiche daß .* nur noch die "minmal mögliche Anzahl Zeichen frißt".
>> Das ist dann doch "höchstens ein Zeichen" und der RE ist dann doch
>> gleich zu .?
>
> Nein, * heißt ja "0 oder mehr Dinge". Der Unterschied liegt darin, in
> welcher Reihenfolge die Möglichkeiten durchprobiert werden.
>
> * alleine frisst soviele wie möglich und rückt sie nur wieder heraus,
> wenn der Rest der Regex sonst nicht passen würde.
>
> *? frisst erstmal 0 Zeichen, nimmt aber auch mehr, wenn sonst der Rest
> der Regex nicht mehr passen würde.

Danke für die Erklärung.

Das wirft für mich aber eher weitere Fragen auf. Ich habe jetzt gerade
kein Beispiel zur Hand, aber ich denke es läßt sich eins konstruieren:

Wenn jetzt nach einem Greedy weitere RE-Teile kommen, die auch davon
abhängen können wie weit denn schon gefressen wurde, dann sind ja
mehrere Aufteilungen des getesteten Strings auf $1, $2, $3 usw. möglich.

Wie werden die denn dann verteilt?

Versuch eines Beispiels:

"abcAdefAghiAjkl" =~ /^(\w*?)A(\w*?)$/;

$1 ?
$2 ?

Hierbei würden doch mehrere Verteilungen von $1 und $2 dazu führen
daß der RE passt, oder?

Heißt das jetzt daß $1 'abc' ist und $2 'defAgh...' ist?

Eine andere Verteilung ($1 = 'abcAdef', $2 = 'ghiAjkl')
würde doch auch passen.

Im Test kommt Variante 1 heraus. Ist der Algorithmus jetzt so
daß der jeweilige Greedy soweit frißt bis der nächste RE paßt?
Falls der nicht paßt frißt der erste Greedy weiter bis er wieder
eine Stelle gefunden hat bis der nächste RE paßt und dann wird
wieder getestet ob der Rest noch paßt?

Das würde dann doch bedeuten daß wirklich alle Möglichkeiten
durchprobiert werden bis eine gefunden wurde die paßt, richtig?


Grüße,
Torsten.

Re: RE, Greedy-Verhalten

Torsten Mohr schrob:

> "abcAdefAghiAjkl" =~ /^(\w*?)A(\w*?)$/;
>
> $1 ?
> $2 ?
>
> Hierbei würden doch mehrere Verteilungen von $1 und $2 dazu führen
> daß der RE passt, oder?
>
> Heißt das jetzt daß $1 'abc' ist und $2 'defAgh...' ist?
>
> Eine andere Verteilung ($1 = 'abcAdef', $2 = 'ghiAjkl')
> würde doch auch passen.
>
> Im Test kommt Variante 1 heraus. Ist der Algorithmus jetzt so
> daß der jeweilige Greedy soweit frißt bis der nächste RE paßt?
> Falls der nicht paßt frißt der erste Greedy weiter bis er wieder
> eine Stelle gefunden hat bis der nächste RE paßt und dann wird
> wieder getestet ob der Rest noch paßt?
>
> Das würde dann doch bedeuten daß wirklich alle Möglichkeiten
> durchprobiert werden bis eine gefunden wurde die paßt, richtig?

Im Prinzip ja:

$ perl -Mre=debug -e '"abcAdefAghiAjkl" =~ /^(\w*?)A(\w*?)$/'
Freeing REx: `","'
Compiling REx `^(\w*?)A(\w*?)$'
size 19 Got 156 bytes for offset annotations.
first at 2
synthetic stclass `ANYOF[0-9A-Z_a-z{unicode_all}]'.
1: BOL(2)
2: OPEN1(4)
4: MINMOD(5)
5: STAR(7)
6: ALNUM(0)
7: CLOSE1(9)
9: EXACT (11)
11: OPEN2(13)
13: MINMOD(14)
14: STAR(16)
15: ALNUM(0)
16: CLOSE2(18)
18: EOL(19)
19: END(0)
floating `A' at 0..2147483647 (checking floating) stclass `ANYOF[0-9A-Z_a-z{unicode_all}]' anchored(BOL) minlen 1
Offsets: [19]
1[1] 2[1] 0[0] 6[1] 5[1] 3[2] 7[1] 0[0] 8[1] 0[0] 9[1] 0[0] 13[1] 12[1] 10[2] 14[1] 0[0] 15[1] 16[0]
Guessing start of match, REx `^(\w*?)A(\w*?)$' against `abcAdefAghiAjkl'...
Found floating substr `A' at offset 3...
Does not contradict STCLASS...
Guessed: match at offset 0
Matching REx `^(\w*?)A(\w*?)$' against `abcAdefAghiAjkl'
Setting an EVAL scope, savestack=3
0 <> | 1: BOL
0 <> | 2: OPEN1
0 <> | 4: MINMOD
0 <> | 5: STAR
Setting an EVAL scope, savestack=3
ALNUM can match 3 times out of 3...
3 | 7: CLOSE1
3 | 9: EXACT
4 | 11: OPEN2
4 | 13: MINMOD
4 | 14: STAR
Setting an EVAL scope, savestack=3
4 | 16: CLOSE2
4 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
5 | 16: CLOSE2
5 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
6 | 16: CLOSE2
6 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
7 | 16: CLOSE2
7 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
8 | 16: CLOSE2
8 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
9 | 16: CLOSE2
9 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
10 | 16: CLOSE2
10 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
11 | 16: CLOSE2
11 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
12 | 16: CLOSE2
12 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
13 | 16: CLOSE2
13 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
14 | 16: CLOSE2
14 | 18: EOL
failed...
ALNUM can match 1 times out of 1...
15 <> | 16: CLOSE2
15 <> | 18: EOL
15 <> | 19: END
Match successful!
Freeing REx: `"^(\\w*?)A(\\w*?)$"'


Wie man sieht, ist perl schlau genug, zuerst das erste "A" zu suchen.
Die zweite Klammer wird aber Zeichen für Zeichen durchprobiert, bis das
Ende erreicht ist. Schlüge nun auch das fehl, würde perl die erste
Klammer auf "abcAdef" erweitern, dann wieder den Rest durchprobieren,
usw.

perl -Mre=debug bzw. perl -Mre=debugcolor ist recht nützlich, wenn man
solche Dinge ausprobieren will.

HTH, Lukas