Wyrażenia regularne

Mechanizm dopasowania w Perlu

Poniższy opis działania mechanizmu dopasowania w Perlu jest skróconym i nieco zmodyfikowanym opisem tego mechanizmu, który został szczegółowo omówiony w pracy magisterskiej Roberta Ospary pt. Wizualizacja dopasowania wyrażeń regularnych Perla z użyciem biblioteki Gtk+ (Toruń, 2009).

Wyrażenia regularne wyrosły z badań teoretycznych wraz z rozwojem algebry formalnej na początku lat 50. XX wieku. Są dwie metody ich realizacji: jako deterministyczne automaty skończone, DFA (Deterministic Finite Automata) oraz niedeterministyczne automaty skończone, NFA (Nondeterministic Finite Automata). Automat to dynamiczny system matematyczny zbudowany ze stanów i przejść pomiędzy nimi. Zasada działania systemu jest prosta. Na wejściu wczytywane są jakieś znaki, a zdefiniowana w automacie funkcja przejścia określa do jakiego stanu nastąpi przeskok przy danym znaku jako argumencie. Każdy automat posiada wyszczególnione dwa typy stanów: początkowy, od którego zaczyna pracę oraz końcowy, na którym pracę swą kończy.

Perl używa silnika NFA, czyli wykorzystuje automat niedeterministyczny, podobnie jak wiele innych języków i programów. Z silnika NFA korzystają edytory vi i GNU emacs, edytor strumieniowy sed, expect, tradycyjne wersje programu grep; języki: Python, Tcl oraz awk (gawk używa silników NFA i DFA).

Pierwszą rzeczą jaką robi Perl w celu dopasowania jest kompilacja wyrażenia. Jest ono analizowane, sprawdzane są wszelkie błędy składniowe, po czym następuje redukcja do postaci wewnętrznej, czyli silnika NFA właśnie, który może zostać użyty do wielokrotnego sprawdzania dopasowania dla różnych łańcuchów podanych na jego wejściu. Następnie uruchamiany jest proces dopasowywania, czyli przechodzenia w strukturze automatu ze stanu do stanu, aż przeczytane zostaną wszystkie znaki. Na koniec automat, znając wszystkie swoje stany końcowe, stwierdza czy cały proces doprowadził do~jednego z nich czy nie. Jeżeli tak to dopasowanie zakończyło się sukcesem, a porażką w przeciwnym wypadku. Przechodzenie od stanu do stanu jest kierowane pewnymi zasadami.

Zasada 1. Dopasowanie, które zaczyna się wcześniej ma pierwszeństwo przed dopasowaniem, które zaczyna się później.

Mamy proste wyrażenie /”.*”/, które dopasowuje cudzysłów, po nim następujący dowolny ciąg znaków, a następnie znowu cudzysłów. Weźmy następujący tekst:

And then "Right," said Fred, "at 12:00" and he was gone.

Co zostanie dopasowane? Gdzie rozpocznie się dopasowanie? Mamy kilka różnych możliwości:

And then "Right," said Fred, "at 12:00" and he was gone.
         |<---->|<---------->|<------>|
         |<-----|----------->|        |
         |<-------------------------->|

Zasada numer 1, mówi nam, że dopasowanie rozpocznie się od napotkanego pierwszego cudzysłowu, ale w tym przypadku mamy nadal trzy możliwości dopasowania:

And then "Right," said Fred, "at 12:00" and he was gone.
         <----->
         <------------------->
         <--------------------------->

Można wyobrazić sobie silnik wyrażeń regularnych Perla jako system złożony z kółek połączonych strzałkami. Aktualny stan automatu oznaczamy kładąc żeton na jednym z kółek. Jeśli w tym stanie można dopasować kolejny znak tekstu, to przenosimy żeton do kolejnego stanu podążając wzdłuż jednej ze ścieżek. W przypadku wyrażenia regularnego /”.*”/ odpowiadający mu automat NFA ma do dyspozycji dwie ścieżki (dwa stany): A i B. Stan A odpowiada dopasowaniu cudzysłowu, a B – dowolnego znaku z wyjątkiem znaku nowej linii. Próbując dopasować kolejne znaki tekstu dochodzimy do momentu, kiedy trafiamy na pierwszy cudzysłów. Wtedy ze stanu A przechodzimy do stanu B, gdzie można już dopasować dowolny znak (oprócz znaku nowej linii).

Często zdarza się też, że w automacie jest wiele ścieżek prowadzących od aktualnego stanu do stanu końcowego. W wyrażeniu regularnym może wystąpić podwyrażenie opcjonalne, więc trzeba rozstrzygnąć, czy najpierw następuje próba dopasowania z użyciem tego podwyrażenia, czy też jest ono najpierw pomijane. W przypadku wystąpienia alternacji trzeba określić kolejność dopasowywania kolejnych opcji. Zatem pracą silnika NFA muszą kierować odpowiednie reguły, które określone są przez kolejną zasadę.

Zasada 2. Wybór ścieżki zależy od użytych w wyrażeniu regularnym metaznaków zachłannych, metaznaków leniwych lub metaznaku alternatywy.

Rozważmy, po kolei, co się dzieje w przypadku stosowania metaznaków zachłannych, leniwych i alteracji:

• ?, *, + oraz {min,max} to tak zwane zachłanne metaznaki lub metaznaki maksymalnego dopasowania. Ich obecność przy podwyrażeniu wyrażenia regularnego sprawia, że zawsze następuje próba dopasowania części obarczonej tym metaznakiem i dopasowania możliwie największą liczbę razy.

• ??, *?, +? oraz {min,max}? to tak zwane leniwe metaznaki lub metaznaki minimalnego dopasowania. Ich obecność w podwyrażeniu wyrażenia regularnego sprawia, że silnik najpierw próbuje pominąć takie podwyrażenie przy dopasowaniu globalnym. Jeżeli takie dopasowanie się nie powiedzie, to nastąpi próba dopasowania znaku lub znaków z podwyrażenia niezachłannego, ale tak, aby dopasowanie zakończyło się sukcesem przy jak najmniejszej liczbie znaków podwyrażenia.

• | to alternatywa, która jest realizowana w porządku od lewej do prawej, dlatego pierwsza opcja zostanie wypróbowana jako pierwsza, druga jako druga, itd.

Zasada 3. Pierwsze osiągnięte dopasowanie wygrywa.

Zatem zaczynając dopasowywanie od zastosowania zasady nr 1, a następnie stosując zasadę nr 2, dochodzimy w pewnym momencie do sytuacji, w której całe wyrażenie jest dopasowane, tzn. wszystkie podwyrażenia z metaznakami zostały dopasowane zgodnie z ich charakterystyką. W takiej sytuacji mechanizm dopasowywania Perla już nie będzie starał się znaleźć innych dopasowań. Silnik NFA kończy swoją pracę. Chociaż być może byłyby możliwe inne dopasowania od tego samego miejsca z inną liczbą dopasowanych podwyrażeń opcjonalnych. Ostatnia zasada mówi, że pierwsze osiągnięte dopasowanie wygrywa, co nie oznacza, że najkrótsze dopasowanie wygrywa, albo pierwsze dopasowanie, które dostrzega albo ma nadzieję dopasować programista, ale pierwsze, które znalazł mechanizm NFA.

Wniosek z tego jest taki, że wszystkie decyzje pomiędzy pierwszym i ostatnim dopasowaniem, którą drogę obrać w grafie równoważnym danemu wyrażeniu, będą miały zasadniczy skutek dla ostatecznego dopasowania.

Gdyby nie mechanizm wycofywania stosowany przez silnik NFA Perla, to w zasadzie na tym można by zakończyć objaśnianie sposobu działania mechanizmu dopasowywania. Obecność tego mechanizmu powoduje, że sprawa znajdowania dopasowania nieco się komplikuje.

Kiedy silnik NFA staje przed wyborem jednej spośród kliku możliwych ścieżek, to wybiera dokładnie jedną, a inne oznacza jako niewypróbowane. Jeśli później okaże się, że wybrana ścieżka prowadzi do porażki w globalnym dopasowaniu, to mechanizm powraca do momentu, w którym musiał dokonać wyboru i podejmuje kolejną próbę wybierając (kolejną) ścieżkę oznaczoną jako niewypróbowaną. Ten proces nazywa się wycofaniem.

Wróćmy do przykładu dopasowania wyrażenia /”.*”/ do tekstu:

And then "Right," said Fred, "at 12:00" and he was gone.

W naszej analizie dotarliśmy do miejsca między pierwszym napotkanym cudzysłowem, a słowem Right, czyli do stanu A. Wiemy, że podwyrażenie /.*/ jest zachłanne, czyli chce dopasować jak najwięcej znaków. Zatem mechanizm NFA przechodzi do B, dopasowuje kolejny znak na wejściu, wraca do stanu A i ponownie idzie do B dopasowując kolejny znak. Oczywiście za~każdym razem, gdy dokonywany jest wybór między dopasowaniem dowolnego znaku a cudzysłowu, mechanizm NFA zapamiętuje ten fakt. Dzięki temu w razie niepowodzenia w lokalnym dopasowaniu będzie istniała możliwość powrotu do miejsc, w których zmiana decyzji o wyborze ścieżki może doprowadzić do globalnego dopasowania. W ten sposób mechanizm dopasowania dociera do końca łańcucha wejściowego, a dokładnie za kropkę w słowie gone zapamiętując po drodze sporo stanów. Spójrzmy na nie w odwrotnej kolejności:

was gone.
was gone
was gon
was go
was g
was
...
Right
Righ
Rig
Ri
R

Tym razem w stanie B nie można dopasować czegokolwiek, gdyż jesteśmy na końcu łańcucha przed znakiem nowej linii, gdyż (domyślnie) metaznak ‘.’ znaku nowej linii nie dopasuje (można to zmienić stosując modyfikator s). Gdyby to był końcowy stan naszego automatu, to znalezione dopasowanie byłoby tym czego szukaliśmy. Tak jednak nie jest. Mamy tylko do czynienia z lokalnym niedopasowaniem i mechanizm musi się wycofać. Zatem trzeba powrócić do ostatnio zapamiętanej sytuacji, próbując dopasować cudzysłów w wyrażeniu regularnym dla końca łańcucha w tekście. Okazuje się, że tutaj także dopasowanie kończy się porażką, gdyż cudzysłów nie pasuje do znaku nowej linii. Ale to nas nie powinno martwić, ponieważ mamy jeszcze mnóstwo zapamiętanych, lecz niesprawdzonych stanów. Kolejne wycofanie prowadzi do stanu:

was gone

w którym także mamy do czynienia z porażką, bo cudzysłów nie dopasowuje do kropki. Łatwo zauważyć, że musimy wykonać cały szereg kolejnych wycofań tego typu, aż dotrzemy do sytuacji:

at 12:00

W tym stanie można dopasować cudzysłów, co pociąga za sobą sukces w dopasowaniu globalnym i zakończeniu procesu dopasowania.

And then "Right," said Fred, "at 12:00" and he was gone.
         <---------------------------->

Oczywiście w dalszym ciągu mechanizm NFA dysponuje niewypróbowanymi ścieżkami, które także mogłyby doprowadzić do globalnego dopasowania. I tak jest w rozważanym tutaj przypadku, ale zgodnie z zasadą 3. pierwsze dopasowanie wygrywa.

Warto zauważyć, że z przedstawionych zasad dopasowania wynika, że wyrażenie, którego wszystkie podwyrażenia są opcjonalne zawsze zostanie dopasowane do dowolnego tekstu. Np. wydaje się, że wyrażenie /-?[0-9]*\.?[0-9]*/ nadaje się do dopasowania liczby rzeczywistej z jedną cyfrą po kropce. Rozkładając jednak to wyrażenie na poszczególne składowe: /-?/, /[0-9]*/, /\.?/ oraz /[0-9]*/ można zauważyć, że wszystkie podwyrażenia są opcjonalne. Oznacza to, że jeśli nie pasują do aktualnie wczytanego znaku, to dopasowują znak pusty. Dopasowanie rozpocznie się od pozycji przed pierwszym znakiem łańcucha wejściowego. Dla wyrażenia /-?[0-9]*\.?[0-9]*/ niepowodzenie w dopasowaniu którejś ze składowych oznacza, że będzie podjęta próba dopasowania kolejnej składowej z wyłączeniem aktualnej, która dopasowała znak pusty. Więc jeżeli poczynając od pozycji przed pierwszym znakiem łańcucha wejściowego, żadna składowa nie pasuje, to całe wyrażenie dopasuje znak pusty, czyli nic i dopasowanie kończy się sukcesem.

Zob. także:

• wregex - How Regular Expression Engines Work

• Jeffrey E.F. Friedl, Mastering Regular Expressions

• https://regexper.com

• https://regex101.com/