Perl/Wyrażenia regularne

Wyrażenia regularne Perla

Definicja

Wyrażenie regularne ( z ang. Regular Expression lub Regex) jest łańcuchem symboli, który określa lub dopasowuje zbiór łańcuchów, poprzez konkretne reguły. Ich pierwotna struktura dzieli się na znaki i metaznaki, czyli znaki o specjalnym znaczeniu.

Podstawowe pojęcia

Symbol jest pojęciem predefinowalnym (czyli takim, którego nie da się zdefiniować). Przykładami są litery i cyfry.

Łańcuch (słowo) - jest skończonym ciągiem zestawionych razem symboli.

NFA to skrót angielskiej nazwy : Nondeterministic Finite Automaton (niedeterministyczny automat skończony). Określa mechanizm używany w procesie dopasowania wyrażenia regularnego do danego tekstu. Mechanizm ten kieruje się zhierarchizowanym zbiorem reguł, których poznanie umożliwia sprawne posługiwanie się w.r. i kontrolę nad przebiegiem dopasowania, poprzez konstruowanie odpowiednich w.r. do celu, w jakim zamierzaliśmy ich użyć.

Zastosowanie

Są niezastąpionym narzędziem w dziedzinie wyszukiwanie danych w dokumentach tekstowych dla ich ewentualnej modyfikacji.

Przykład 1) Wyrażenie a* = { $\epsilon$ , a , aa , aaa , aaaa , ...} - czyli określa zbiór słów dowolej długości złożonych tylko z symbolu a ( małej litery a). Tu * ( gwiazdka) jest metaznakiem powiązanym z sylbolem a, określającym zbiór po prawej stronie równości. Gwiazdka "mówi" nam: Weź to z czym jestem powiązana tyle razy ile się da, zero razy w szczególności. $\epsilon$ (epsilon) - jest znakiem pustym lub słowem pustym długości 0, czyli takim, które niczego nie określa.

Przykład 2) Wyrażenie (0|1)* = { $\epsilon$ , 0 , 1 , 00 , 01 , 10 , 11 , 000 , 001 , ... } - zbiór słów złożonych z symboli 0 i 1 ( cyfr zero i jeden) dowolnej długości. Tu | ( pionowa kreska) oznacza alternatywę rozłączną. Powiedzmy, że nawiasy okrągłe grupują cały ciąg symboli: 0, | i 1, do których odnosi się gwiazdka.

Przykład 3 Polecenie rename BASHa wykorzystuje wyrażenia regularne Perla.

Zbiory znaków,metaznaków i metasekwencji Perla

Jeśli coś nie jest metaznakiem lub metasekwencją to na ogół jest znakiem literalnym, lecz istnieją jeszcze sekwencje niezdefiniowane np. “**”.

        . (kropka) dowolny znak oprócz znaku nowego wiersza, lub dowolny znak w przypadku użycia 
        modyfikatora /s

        | alternacja

        Kwantyfikatory zachłanne:
               * + ? {n} {min,} {min , max}
     
        Kwantyfikatory niezachłanne:
               *?    +?    ??    {n}?    {min}?    {min,max}?

        Komentarze:
               (?#...)
               #... ­ komentarz aż do końca wiersza lub aż do końca wyrażenia (w przypadku 
                     obecności modyfikatora /x)

        Modyfikatory wewnętrzne:
               (?mod)    i    x    m    s

        Zwykłe grupowanie i przechwytywanie:
               (...)

        Tylko zwykłe grupowanie:
               (?:...)

        Przewidywanie pozytywne:
               (?=...)

        Przewidywanie negatywne:
               (?!...)

        Punkty zakotwiczenia wzorca:
               \b \B ­ zakotwiczenie w słowie lub poza słowem
               ^ $    początek lub koniec łańcucha (albo początek lub koniec wiersza logicznego)
               \A \Z ­ początek lub koniec łańcucha
               \G     koniec poprzedniego dopasowania
                         
                         

        Tekst dopasowany poprzednio w nawiasach przechwytujących:
               \1    \2    ...

        Normalna i zanegowana klasa znaków:
               [...]    [^...]

        Symboliczny zapis znaku:
               \b \t \n \r \f \a \e \liczba \xliczba \cznak

        Symboliczny zapis klasy:
               \w \W \s \S \d \D

        Modyfikacja tekstu na gorąco:
               \l \L \u \U \Q \E

Realizacja dopasowania

Reguła 1.

Mechanizm próbuje dopasować wzorzec jak najbliżej lewej strony napisu, tak by całe wyrażenie regularne zostało dopasowane zgodnie z regułą 2. Mechanizm rozpoczyna dopasowanie tuż przed pierwszym znakiem i próbuje od tego miejsca dopasować cały wzorzec. Cały wzorzec pasuje wtedy,gdy mechanizm dojdzie do końca wzorca, zanim dojdzie do końca napisu. Jeżeli wzorzec zostanie dopasowany, mechanizm natychmiast kończy działanie nie próbuje szukać “lepiej” pasującego napisu,nawet jeśli wzorzec można dopasować na kilka sposobów. Jeżeli wzorca nie da się dopasować od pierwszej pozycji w napisie, mechanizm przyznaje się do przegranej bitwy i przesuwa się o jedną pozycję do przodu ­ między pierwszy a drugi znak ­ i ponownie wypróbowuje wszystkie możliwości. Mechanizm uznaje, że nie można w ogóle dopasować wzorca, dopiero wtedy, kiedy przeprowadzi próby dopasowania wyrażenia regularnego w każdej pozycji w napisie, łącznie z tą za ostatnim znakiem.

Reguła 2.

Gdy mechanizm napotka zbiór alternatyw, niezależnie od tego, czy znajduje się na najwyższym poziomie, czy na bieżącym poziomie pofragmentowania, wypróbowuje je kolejno od lewej do prawej, zatrzymując się przy pierwszej, która pozwoli na dopasowanie całego wzorca. Sukces w dopasowniu alternatywy wiąże się z regułą 3, a w przypadku porażki mechanizm wraca do reguły 1 albo 4 lub 6, jeśli operujemy na fragmencie wzorca.

Reguła 3.

Każda alternatywa zostanie dopasowana jeśli każdy jej element zostanie dopasowany zgodnie z regułami 4 i 5, tak aby dopasowane zostało całe wyrażenie regularne. Element składa się albo z asercji, której dotyczy reguła 4, albo skwantyfikowanego atomu, którego dotyczy reguła 5.

Reguła 4.

Jeżeli asercja nie zostanie dopasowana w bieżącej pozycji, mechanizm wraca do reguły 3 i próbuje w inny sposób dopasować elementy w kolejności od lewej do prawej.

Reguła 5.

Żeby dopasować skwantyfikowany atom,mechanizm musi dopasować atom tyle razy, ile określa kwantyfikator. Atom jest dopasowywany zgodnie z regułą 6.

Reguła 6.

Każdy atom jest dopasowywany zgodnie z semantyką charakterystyczną dla jego typu. Jeżeli atomu nie można dopasować (lub można ale nie pozwala to na dopasownie reszty wzorca), mechanizm powraca do reguły 5 i wypróbowuje następną możliwość dopuszczoną przez kwantyfikator. Atomy są dopasowywane odpowiednio do ich typu:

              1) “ (...) ”
              2) “ . ”
              3) “ [...] ”
              4) litera poprzedzona odwrotnym ukośnikiem dopasowuje określony znak lub 
                  znak specjalny Perla np. “/n”
              5) inny znak poprzedzony odwrotnym ukośnikiem dopasowuje ten znak 
                  np.”//”
              6) każdy nie wymieniony powyżej znak dopasowuje sam siebie

Ach te “trybiki”. Wyobraźmy sobie,że nasz mechanizm to zbiór połączonych ze sobą trybów, które można przekręcać. Mechanizm dopasowania przekręca je dotąd, aż cały wzorzec zostanie dopasowany.Reguły mówią o tym w jakiej kolejności mechanizm może przekręcać tryby. To, że mechanizm preferuje dopasowanie wzorca jak najbliżej lewej strony, oznacza, że trybik początkowej pozycji obracany jest najwolniej. Wycofywanie się mechanizmu to proces przekręcania trybu, który został wcześniej odkręcony, w celu odkręcenia trybu o wyższym priorytecie, tzn. tego, którego położenie jest zmieniane rzadziej.