Blog

Rekursja w wyrażeniach regularnych

Podczas porządków na dysku odnalazłem mój stary kod obsługujący format BBcode. Ciekawostką jest zastosowany mechanizm obsługi zagnieżdżania tagów oparty na jednym, z pozoru jedynie skomplikowanym, wyrażeniu regularnym.

$code = preg_replace_callback('# \[('.$allowedTags.')(\s=?.+?|=.+?)?\] ( (?: (?(R) [^\[]++ | [^\[]*+) | (?R)) *) \[/\\1\] #x', array($this, 'parseTag'), $code);

Pojawiają się tutaj dziwne oznaczenia ?(R) oraz (?R). Spróbujmy je rozszyfrować.

Czym jest rekursja?

Rekursja, zwana również rekurencją polega na tym, że funkcja wykonuje samą siebie. Dla przykładu ciąg Fibonacciego za pomocą rekurencji moglibyśmy zapisać tak:

F_n := \begin{cases} 0 & \text{dla } n = 0, \\ 1 & \text{dla } n = 1, \\ F_{n-1}+F_{n-2} & \text{dla } n > 1. \end{cases}

`Aby obliczyć F_{13} potrzebujemy najpierw obliczyć F_{12} oraz F_{11}. Aby obliczyć F_{12} potrzebujemy obliczyć F_{11} oraz F_{10} itd. Nie jest to zbyt wydajne rozwiązane i raczej nie zaleca się jego stosowania w przypadku problemów o dużej złożoności ponieważ szybko może się okazać, że nastąpi przepełnienie stosu (ang.stack overflow) lub po prostu zabraknie nam pamięci. O ile to możliwe, najlepszym rozwiązaniem jest sprowadzenie rozwiązania rekurencyjnego do postaci iteracyjnej. Nie będę przedstawiał konkretnych metod, ale jeśli ktoś jest zainteresowany matematyką dyskretną, to polecam na początek zajrzeć tutaj. W przypadku ciągu Fibbonaciego znany jest wzór Eulera-Bineta (szybki test):

F_n=\frac{1}{\sqrt{5}} \left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]

Zastosowanie go znacząco poprawia wydajność. Oczywiście nie zawsze możliwe jest przekształcenie rozwiązania rekurencyjnego na iteracyjne. Czasami także, po prostu się to nie opłaca np. gdy brakuje nam czasu na dodatkową pracę nad rozwiązywaniem rekurencji, a jednocześnie nie spodziewamy się wielu zagnieżdżeń.

Podstawowa składnia

Mechanizmu rekurencji w wyrażeniach regularnych możemy użyć stosując konstrukcję (?R). Zapis ten oznacza, że w jego miejsce zostanie wstawione ponownie całe wejściowe wyrażenie regularne. Pozwala to na wielopoziomowe wyrażenia. Wyobraźmy sobie tekst zawierający dodatkowe znaczniki:

Lorem ==ipsum== dolor sit ===amet=, consectetur ==adipiscing==== elit.

Spróbujmy odnaleźć wszystkie wyrazy otoczone znakami równości. Ważne aby z lewej i prawej strony mieć dokładnie tyle samo znaków „=”.

=([a-zA-Z]+|(?R))=

Działanie możecie szybko podejrzeć tutaj: https://regex101.com/r/gb1V3o/1

Spróbujmy skomplikować nasz przykład aby zamiast znaku równości akceptowane były litery otaczające pojedynczą literę. Dzięki temu odnajdziemy wyrazy będące palidromami np. „kajak”, „ono”, „oko”, „php”.

([a-z])((?R)|[a-z])\1

https://regex101.com/r/CcCof7/1

Brakuje nam jedynie obsługi wyrazów w których pojedyncza środkowa litera nie występuje np. „saas”. Wystarczy, że naszą wewnętrzną literę oznaczymy jako element opcjonalny.

([a-z])((?R)|[a-z]?)\1

Skomplikujmy sytuację jeszcze bardziej. Palidromy to nie tylko pojedyncze wyrazy ale również dłuższe teksty. Istotne jest to w jaki sposób je czytamy, a nie to w jaki zostały zapisane. Świetnym przykładem jest palindrom „A to kanapa pana Kota”, który w przypadku naszego wyrażenia nie zostanie odnaleziony ze względu na dodatkowe spacje. Dodajmy ich obsługę:

 ?(([a-z])((?R)| ?[a-z]?) ?\2)

https://regex101.com/r/BrY5Bb/1

Rekurencja fragmentu wyrażenia

Grupa 1. zawiera zawsze poprawnie znalezione palidromy. W zasadzie problem jest rozwiązany ale pełny wynik zawiera czasami spację na początku. Spróbujmy w ramach ćwiczeń się jej pozbyć dodając pojedynczą literę na początku i na końcu wyrażenia.

([a-z])(TUTAJ NASZE POPRZEDNIE WYRAŻENIE)\1

Pojawia się pewien problem. W poprzednim wyrażeniu użyliśmy oznaczenia (?R), które dodaje kolejne zagnieżdżenie korzystając z całego wyrażenia. W naszym wypadku potrzebujemy zagnieżdżać jedynie wewnętrzną część nowego wyrażenia. Na szczęście jest na to sposób. Zamiast litery R, możemy użyć numeru grupy, która ma zostać użyta do rekurencji np. (?1). W naszym przypadku należy użyć drugiej grupy.

([a-z])( ?([a-z])(?:(?2)| ?[a-z]?) ?\3|[a-z]?)\1

https://regex101.com/r/ALnotT/1

W ramach ćwiczeń proponuję rozwinąć wyrażenie jeszcze bardziej aby odnajdowało jedynie palindromy nie będące fragmentami wyrazów np. „Adam” mimo, że zawiera palindrom „ada” sam nie jest palindromem.

Instrukcja warunkowa

W przykładzie z początku artykułu pojawił się jeszcze jeden zapis ?(R). Jest to fragment instrukcji warunkowej odnoszącej się do rekurencji . Przypomnijmy podstawową składnię:

(?(condition)then|else)

W miejsce warunku możemy wstawić R. Jest to specjalny przypadek, w którym warunek będzie spełniony tylko jeżeli jesteśmy wewnątrz wywołania rekurencyjnego. Prosty przykład:

<(strong|div)>((?R)|)<\/\1>

To wyrażenie odnajduje zarówno <strong> wewnątrz <div>, jak i <div> wewnątrz <strong>. Dodajmy warunek, który znajdzie jedynie znaczniki <strong> otoczone znacznikiem <div>, nigdy odwrotnie.

<((?(R)strong|div))>((?R)|)<\/\1>

https://regex101.com/r/ATY31J/1

Uważaj na wydajność

Przy ogromnej wygodzie i możliwości wyrażeń regularnych należy pamiętać, że ich użycie nie zawsze jest idealnym rozwiązaniem, szczególnie gdy korzystamy z mechanizmu rekursji. W wielu przypadkach warto zastosować klasyczne podejście np. podczas obróbki dużych partii tekstu. Niestety od zawsze jest z tym problem w PHP i przy zbyt rozbudowanych wyszukiwaniach może dojść do wspomnianego wcześniej przepełnienia stosu na poziomie PCRE (biblioteki obsługującej wyrażenia regularne w PHP) . Prosty przykład powodujący błąd:

<?php

// budujemy string o treści {{{{…{{{a}}}…}}}}
$textBefore = $textAfter = '';
for($i=0;$i<9999;$i++) {
    $textBefore .= '{';
    $textAfter .= '}';
}
$text = $textBefore.'a'.$textAfter;

// szukamy wyniku wyrażenia
$result = preg_match("/{(?:(?R)|a)}/", $text, $matches);
if ($result === 1) {
    print_r($matches);
} else {
    $pcre_err = preg_last_error();
    switch ($pcre_err) {
        case PREG_NO_ERROR:
            $msg = 'No error (Non-match)';
            break;
        case PREG_INTERNAL_ERROR:
            $msg = 'PREG_INTERNAL_ERROR';
            break;
        case PREG_BACKTRACK_LIMIT_ERROR:
            $msg = 'PREG_BACKTRACK_LIMIT_ERROR';
            break;
        case PREG_RECURSION_LIMIT_ERROR:
            $msg = 'PREG_RECURSION_LIMIT_ERROR';
            break;
        case PREG_BAD_UTF8_ERROR:
            $msg = 'PREG_BAD_UTF8_ERROR';
            break;
        case PREG_JIT_STACKLIMIT_ERROR:
            $msg = 'PREG_JIT_STACKLIMIT_ERROR';
            break;
        case PREG_BAD_UTF8_OFFSET_ERROR:
            $msg = 'PREG_BAD_UTF8_OFFSET_ERROR';
            break;
    }
    echo 'ERROR('.$pcre_err.'): '.$msg."\n";
}

Na mojej maszynie lokalnej dostaję błąd ERROR(6): PREG_JIT_STACKLIMIT_ERROR

Biorąc pod uwagę problemy wydajnościowe, to czy w ogóle warto korzystać z rekurencji? Oczywiście, że tak. Rekurencja jest bardzo wygodnym rozwiązaniem. Wystarczy zachować zdrowy rozsądek. Jeżeli planujemy jej użycie w wyrażeniu regularnym, po prostu sprawdźmy najpierw długość przeszukiwanego tekstu.

Wsparcie

Należy pamiętać, że implementacji wyrażeń regularnych jest kilka i nie wszystkie funkcjonalności są dostępne wszędzie. Wyrażenia regularne są dostępne w m.in.:

  • PHP (PCRE)
  • C (PCRE)
  • R (PCRE)
  • C++ (Boost)
  • Ruby
  • .NET
  • Perl (z tą różnicą, że dopasowania rekursywne są nieatomowe)
  • Python (zamiast standardowego modułu re należy użyć modułu regex)

Dodaj komentarz