GoldenLine
Zaloguj się
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Ktoś ma pomysł czemu:

preg_match('`(?(R)b|(?R)a)`is', "", $m);

daje komunikat:

Compilation failed: recursive call could loop indefinitely at offset 10

Wygląda jakby kompilator wyrażeń regularnych podczas wykrywania nieskończonej rekurencji nie do końca rozumiał konstrukcję (?(R) | ) i na skutek tego raportował o możliwości występowania nieskończonej rekurencji podczas gdy jednak nie może ona wystąpić.
Link do wypowiedziLink
Stanisław P.

Stanisław P. Software designer

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Ble - można mnie zignorować - pomyliłem (?(R) z (?:Stanisław Pitucha edytował(a) ten post dnia 09.07.09 o godzinie 15:12
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Tak dokładnie taki regexp daje taki komunikat. Oczywiście nadziałem się na niego na czymś bardziej skomplikowanym, ale zrobiłem sobie uproszczony przypadek testowy eksponujący część, którą podejrzewałem o generowanie komunikatu.

Konstrukcja (?(R)a|b) pasuje do 'a' o ile było rekurencyjne dopasowanie i do 'b' jeżeli jeszcze dopasowanie rekurencyjne nie wystąpiło. Natomiast (?R) to właśnie dopasowanie rekurencyjne czyli coś do czego fragment tekstu pasuje o ile pasuje do całego wzorca.

Udokumentowane jest to tutaj:
http://pl2.php.net/manual/en/regexp.reference.recursiv...
http://pl2.php.net/manual/en/regexp.reference.conditio...

Wzorzec (?(R)b|(?R)a) powinien być prawidłowy i pasować do tekstu 'ba'

Niestety kompilator chyba traktuje konstrukcję (?(R) | ) tak jak ( | ), alarmuje, że istnieje potencjalna możliwość nieskończonej rekurencji podczas próby dopasowania i przerywa pracę.
Link do wypowiedziLink

konto usunięte

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Tu jest przykład z podanej przez Ciebie strony (troszke zmodyfikowany):


preg_match("/\((((?>[^()]+)|(?R))*)\)/is", "ab(cd)ef", $m);

Działa bez problemu.

Teraz wywalamy matchowanie zewnętrznych nawiasów:


preg_match("/(((?>[^()]+)|(?R))*)/is", "ab(cd)ef", $m);


I mamy dokładnie taki błąd o jakim pisałeś.
Nie jestem zbyt dobrze obeznany w regexpach, ale chyba brakuje kontekstu rekurecji. Trzeba mieć w czym szukac, a tu po prostu niczego nie ma... może o to chodzi?
Trzeba by wiedzieć jaki jest szerszy kontekst, bo taka konstrukcja po prostu nie może działać :/
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Aleksander Wons:


preg_match("/(((?>[^()]+)|(?R))*)/is", "ab(cd)ef", $m);


I mamy dokładnie taki błąd o jakim pisałeś.
Nie jestem zbyt dobrze obeznany w regexpach, ale chyba brakuje kontekstu rekurecji. Trzeba mieć w czym szukac, a tu po prostu niczego nie ma... może o to chodzi?
Trzeba by wiedzieć jaki jest szerszy kontekst, bo taka konstrukcja po prostu nie może działać :/

Tu po wywaleniu nawiasów błąd jest wyświetlany jak najbardziej słusznie. Bo jeżeli pierwszy człon alternatywy nie pasuje to trzeba spróbować drugi a drugi jest rekurencyjnie całym wyrażeniem. Więc znowu trzeba by przetestować pierwszy człon a skoro nie pasuje to drugi, a drugi jest rekurencyjnie całym wyrażeniem i tak do końca świata.

Mam wrażenie, że błąd w przypadku, który obserwuję bierze się tak jak napisałem z tego, że podczas analizy możliwości wystąpienia nieskończonej rekurencji kompilator nie rozróżnia konstrukcji (?(R) | ) od innej dowolnej konstrukcji warunkowej np. (?(1) | ) i myśli że będzie trzeba próbować dopasować jedną i druga możliwość zależnie od tego jaki ciąg będzie badany, a skoro tak to istnieje możliwość nieskończonej rekurencji.
Link do wypowiedziLink

konto usunięte

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Kamil Szot:
Mam wrażenie, że błąd w przypadku, który obserwuję bierze się tak jak napisałem z tego, że podczas analizy możliwości wystąpienia nieskończonej rekurencji kompilator nie rozróżnia konstrukcji (?(R) | ) od innej dowolnej konstrukcji warunkowej np. (?(1) | ) i myśli że będzie trzeba próbować dopasować jedną i druga możliwość zależnie od tego jaki ciąg będzie badany, a skoro tak to istnieje możliwość nieskończonej rekurencji.

A jaka jest różnica pomiędzy "(?(1) |)" a "(?(R)|)"?
"(?(1)|)" szuka pierwszego subpatternu. I oczywiście jeśli zastąpimy zadany warunek właśnie tym, to kompilator zaraz się zaźli, bo przecież nie ma pierwszego subpatternu i nie ma do czego spasować.
Z kolei "(?(R)|)" ewaluuje do TRUE tylko wtedy jeśli jesteśmy w rekurencji tak? Czyli w zadanym przypadku nie nastąpi to nigdy ponieważ nie ma kontektue gdzie mogła by natąpić ewaluacja do TRUE. W teori kontrukcja zawsze zwróci FALSE i będzie probowała od początku szukać w całym wyrażeniu, które znowu da FALSE i tak w kółko.

Jeśli tylko damy:


preg_match_all('/b(?(R)b|(?R)a)/is', "bbba", $matches);


to otrzymamy taki wynik:


Array ( [0] => Array ( [0] => bbba ) )


Wydaje mi się, że kompilator całkeim słusznie nie pozwala przejść tej kontrukcji poinważ rzeczywiście prowadziła by ona do zapetlenia w nieskończoność.Aleksander Wons edytował(a) ten post dnia 13.07.09 o godzinie 07:14
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Czy możesz podać przykład ciągu, przy próbie dopasowania którego, do mojego wyrażenia regularnego zaszłaby nieskończona rekurencja?
Link do wypowiedziLink

konto usunięte

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Kamil Szot:
Czy możesz podać przykład ciągu, przy próbie dopasowania którego, do mojego wyrażenia regularnego zaszłaby nieskończona rekurencja?

Wydaje mi się, że każdy string się pod to łapie...
Cytat z dokumentacji perla:


(?R) recurses to the beginning of the whole pattern.

Czyli do czego w Twoim przypadku? No do pustego ciągu i zabawa zaczyna się od początku. Znowu szukamy w pustym ciągu i cofamy się do początku wyrażenia i szukamy w pustym ciągu. Co by nie było za (?R) nigdy nie zostanie spasowane, bo capture buffer będzie zawsze pusty i zawsze będzie wracał do początku wyrażenia.

Twój przykład można by jeszcze bardziej okroić do postaci:


/(?R)a/is
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Aleksander Wons:
Twój przykład można by jeszcze bardziej okroić do postaci:


/(?R)a/is
Nie da rady tak skrócić

(?(R)b|(?R)a) przed pierwszym wywołaniem rekurencyjnym to (?R)a ale po pierwszym wywołaniu rekurencyjnym to po prostu b, więc kolejne wywołanie rekurencyjne po prostu nie może nastąpić.

W opisie konstrukcji (?(condition)yes-pattern|no-pattern)
( na stronie http://pl2.php.net/manual/en/regexp.reference.conditio... ) jest napisane "If the condition is the string (R), it is satisfied if a recursive call to the pattern or subpattern has been made. At "top level", the condition is false." oraz "If the condition is satisfied, the yes-pattern is used; otherwise the no-pattern (if present) is used."
Link do wypowiedziLink

konto usunięte

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Nie daje mi teraz życ to wyrażenie ;)

Spróbuje zinterpretować to krok po kroku bazując na Twoim ciągu znaków.

regexp: (?(R)b|(?R)a)
string 'ba'

Wiemu, że (?R) szuka we wsześniej spawowanym ciągu znaków. Nie szuka w całym strinu a pasującym subpatternie.

Krok 1: Jeśli jesteśm w rekurencji to pattern = '/b/'

Krok 2: Ponieważ nie jesteśmy w rekurencji to pattern = '/(?R)a/' = szukaj rekurencyjnie '/a/' w znalezionym wcześniej subpaternie.

Np ale poprzednio znaleziony subpattern to... empty string. Przecież jeszcze niczego nie znaleźliśmy.
Więc zgodnie z definicją wracamy do punktu wyjścia, czyli to wyrażenia /(?(R)b|(?R)a)/ ?

Krok 3: ... No właśnie. Defacto powinnismy byc spowrotem w kroku 1. I koło się zamyka, bo dalej niczego nie spasowaliśmy i dalej krok 2 będzie szukał w pustym ciągu i cofnie nas do począku patternu.

Dobrze to przeanalizowałem? Jeśli tak to kompilator rzeczywiście prawidłowo wykrywa ewentualną nieskończoną pętle.
Link do wypowiedziLink
Kamil Szot

Kamil Szot PHP, JavaScript -
rozwiązywanie
problemów.
limeline.pl

Temat: Nadwrażliwy kompilator wyrażeń regularnych.

Wg. mnie to przebiega tak:

(?(R)b|(?R)a) - nie w rekurencji więc
(?R)a - rekurencyjne wywołanie więc
(?(R)b|(?R)a)a - w rekurencji więc
ba - do tej pory nie ruszył się w dopasowywanym stringu ani o kawałek, dopiero teraz dopasowuje 'b' do 'b' a 'a' do 'a'
Link do wypowiedziLink
« Wróć do tematów
Odpowiedz

Podobne tematy


Następna dyskusja:

Kompilator PHP




Wyślij zaproszenie do
Anuluj