"Trochę" "upojnego" debugowania doprowadziło mnie do znalezienia
błędu, który został popełniony przy pisaniu regexpa. Oryginalny był
baaardzo długi i skomplikowany, tu pokażę samo "mięsko".

W założeniu miał łapać sekwencję:
("wyraz" jeden lub więcej razy, "separator") jeden lub więcej razy,
napis "xyz". "wyraz" to literki, "separator" to kropka lub podkreślenie.

No i napisano:
([A-z]+[._])+xyz

Po czym regexp trafił na długi ciąg podkreśleń i... zawisł. Tu dam
spoiler, gdyby ktoś chciał samodzielnie pokombinować 8-)

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

[A-z] to miał być skrót [A-Za-z] (tak można, użyć klas znaków, ale
komuś się nie chciało zajrzeć do dokumentacji). Niestety [A-z] to
[A-Z\[\\\]\^_`a-z] (znaki "[\]^_`" oprócz liter). Dla przypadku szukania
w ciągu podkreśleń można całe wyrażenie zredukować do: "(_+_)+xyz".
Automat próbuje:
- _+ dopasowało się do całego ciągu (zachłannie), ale ciąg się skończył
- _+ dopasowało się do całego ciągu -1 znak, _ dopasowało się do
ostaniego _, ale nie ma xyz
- _+ dopasowało się do całego ciągu -2 znaki, _ dopasowało się do
przedostaniego _, próbujmy jeszcze raz z _+ - dopasowało się, ale nie
ma _
- _+ dopasowało się do całego ciągu -3 znaki, _ dopasowało się do
_ 2 znaki od końca, próbujmy jeszcze raz z _+ - dopasowało się do
dwóch _ z końca, ale nie ma _
- _+ dopasowało się do całego ciągu -3 znaki, _ dopasowało się do
_ 2 znaki od końca, próbujmy jeszcze raz z _+ - dopasowało się do
przedostaniego _, _ dopasowało się do ostatniego _, ale nie ma xyz
... i tak dalej - drzewo poszukiwań rośnie szybko, a zawsze na końcu
brakuje tego "xyz", a trzeba różnych kombinacji dopasowań "(_+_)+".

Cały problem powstaje zawsze, gdy dla (R1+R2)+ jest taki ciąg, do
którego można dopasować zarówno R1 jak i R2, i taki ciąg wystąpi wiele
razy po sobie.

--
Paweł Kierski
n...@p...net

do góry

On 21 Maj, 11:04, Paweł Kierski <n...@p...net> wrote:
>
>    [A-z] to miał być skrót [A-Za-z] (tak można, użyć klas znaków, ale
> komuś się nie chciało zajrzeć do dokumentacji). Niestety [A-z] to
> [A-Z\[\\\]\^_`a-z] (znaki "[\]^_`" oprócz liter). Dla przypadku szukania
> w ciągu podkreśleń można całe wyrażenie zredukować do: "(_+_)+xyz".

Czemu nie /(_+)+xzy/ ?

--
Pozdrowienia,
Marcin 'Malcom' Malich
m...@m...pl
http://malcom.pl

do góry

Marcin 'Malcom' Malich wrote:
> On 21 Maj, 11:04, Paweł Kierski <n...@p...net> wrote:
>> [A-z] to miał być skrót [A-Za-z] (tak można, użyć klas znaków, ale
>> komuś się nie chciało zajrzeć do dokumentacji). Niestety [A-z] to
>> [A-Z\[\\\]\^_`a-z] (znaki "[\]^_`" oprócz liter). Dla przypadku szukania
>> w ciągu podkreśleń można całe wyrażenie zredukować do: "(_+_)+xyz".
>
> Czemu nie /(_+)+xzy/ ?

Bo to wynikło z pomyłki - miało być /([A-Za-z]+[._])+xyz/. Zapisane
zostało jako /([A-z]+[._])+xyz/, czyli w przybliżeniu
/([A-Z_a-z]+[._])+xyz/, co dla ciągu "__________________" zachowuje się
jak /(_+_)+xyz/

--
Paweł Kierski
n...@p...net

do góry

Dnia 21.05.2009 Paweł Kierski <n...@p...net> napisał/a:

> W założeniu miał łapać sekwencję:
> ("wyraz" jeden lub więcej razy, "separator") jeden lub więcej razy,
> napis "xyz". "wyraz" to literki, "separator" to kropka lub podkreślenie.
>
> No i napisano:
> ([A-z]+[._])+xyz
>
> Po czym regexp trafił na długi ciąg podkreśleń i... zawisł. Tu dam
> spoiler, gdyby ktoś chciał samodzielnie pokombinować 8-)

15 sekund bez patrzenia w spoiler. Kto da mniej? ;)

--D. (jednak nie jest ze mną tak źle... chyba.)

--
Daniel 'Nathell' Janus, m...@n...korpus.pl, http://danieljanus.pl
Nothing smells more like a slaughterhouse than a graduate seminar.
-- Leonard Cohen, "The Favourite Game"

do góry

napisz jeszcze, z jakiej biblioteki regexp korzystales, bo tak w ogole
to mozna tak zrobic kompilator wyrazen regularnych, zeby rowniez takie
wzorce wyszukiwaly sie efektywnie.

--
ms

do góry

matmis wrote:
> napisz jeszcze, z jakiej biblioteki regexp korzystales, bo tak w ogole
> to mozna tak zrobic kompilator wyrazen regularnych, zeby rowniez takie
> wzorce wyszukiwaly sie efektywnie.

Fakt - boost::regex. Choć pewnie można również dla dowolnego
kompilatora znaleźć taką kombinację wyrażenie-ciąg, że wyszukiwanie się
pokaszani.

--
Paweł Kierski
n...@p...net

do góry

Daniel Janus wrote:
> Dnia 21.05.2009 Paweł Kierski <n...@p...net> napisał/a:
>
>> W założeniu miał łapać sekwencję:
>> ("wyraz" jeden lub więcej razy, "separator") jeden lub więcej razy,
>> napis "xyz". "wyraz" to literki, "separator" to kropka lub podkreślenie.
>>
>> No i napisano:
>> ([A-z]+[._])+xyz
>>
>> Po czym regexp trafił na długi ciąg podkreśleń i... zawisł. Tu dam
>> spoiler, gdyby ktoś chciał samodzielnie pokombinować 8-)
>
> 15 sekund bez patrzenia w spoiler. Kto da mniej? ;)
>
> --D. (jednak nie jest ze mną tak źle... chyba.)

Nieźle! 8-) Choć po uproszczeniu to jednak inna liga: w oryginale ciąg
podkreśleń był "schowany" w kilkusetznakowym ciągu, a wyrażenie
zawierało między innymi wzorce dla wszystkich TLD i IP - było w czym
szukać 8-)

--
Paweł Kierski
n...@p...net

do góry

On 22 Maj, 09:51, Paweł Kierski <n...@p...net> wrote:
>    Fakt - boost::regex. Choć pewnie można również dla dowolnego
> kompilatora znaleźć taką kombinację wyrażenie-ciąg, że wyszukiwanie się
> pokaszani.

w rzeczy samej! dlatego warto by jeszcze sprawdzic, czy ten problem
wystepuje przy samym /(_+)+xzy/, czy tez tylko przy tym oryginalnym,
bardzo dlugim i skomplikowanym regexpie.

-ms

do góry

matmis wrote:
> On 22 Maj, 09:51, Paweł Kierski <n...@p...net> wrote:
>> Fakt - boost::regex. Choć pewnie można również dla dowolnego
>> kompilatora znaleźć taką kombinację wyrażenie-ciąg, że wyszukiwanie się
>> pokaszani.
>
> w rzeczy samej! dlatego warto by jeszcze sprawdzic, czy ten problem
> wystepuje przy samym /(_+)+xzy/, czy tez tylko przy tym oryginalnym,
> bardzo dlugim i skomplikowanym regexpie.

Przy dowolnej tego typu konstrukcji. To co podałem, to właśnie wynik
analizy i debugowania oryginalnego przypadku.

--
Paweł Kierski
n...@p...net

do góry