Jedzenie czerwonych wiśni daje ci możliwość jedzenia niebieskich duchów. Pomysł, że pochodne mogą być używane do tworzenia algorytmu dopasowywania wyrażeń regularnych, jest prawie równie absurdalny. Pozwólcie, że wyjaśnię, jak działa ten algorytm i jaki ma związek z Pac-Manem.

W 1964 roku Brzozowski opublikował pierwszą pracę na temat pochodnych wyrażeń regularnych . To zdecydowanie jeden z moich ulubionych algorytmów. Korzystając z pochodnych wyrażeń regularnych, możemy zaimplementować algorytm dopasowywania wyrażeń regularnych. Ten algorytm jest bardzo:

• prosty
• funkcjonalny
• łatwo rozszerzalny o własnych operatorów

W tym artykule pokażę, jak dopasować łańcuch znaków do wyrażenia regularnego, używając tylko dwóch czystych funkcji i kilku analogii do Pac-Mana. Jeśli wolisz, możesz obejrzeć poniższy film zamiast czytać artykuł, ponieważ obejmuje on ten sam materiał:

Podsumowanie wyrażeń regularnych

Najpierw zróbmy szybki przegląd wyrażeń regularnych, aby upewnić się, że jesteśmy na tej samej stronie. Wyrażenie a(a|b)*dopasowuje ciąg rozpoczynający się od a, po którym następuje dowolna liczba as i bs.

• Ciąg abbędzie pasować a(a|b)*. Wskażemy to jadalnym niebieskim duchem.
• Ciąg aabbbarównież pasuje a(a|b)*, ponieważ zaczyna się od an ai następuje po nim kilka a„i b”.
• Następnie ciąg acnie pasuje a(a|b)*, ponieważ wyrażenie regularne nie pasuje do żadnych c, a nasze wyrażenie regularne nie dopasowuje żadnego podłańcucha. Wskażemy to czerwonym duchem ścigającym Pac-Mana.
• Wreszcie ciąg barównież nie pasuje a(a|b)*, ponieważ nie zaczyna się od a.

Przegląd algorytmu

Zanim zagłębimy się w szczegóły, zobaczmy, jak działa ten algorytm. Wymyśliłem dziwną grę Pac-Man, w której można zjeść duchy tylko wtedy, gdy zje się owoc w kolejności zgodnej z wyrażeniem regularnym. Nasz Pac-Man reprezentuje wyrażenie regularne aba*. Ma następujący ciąg owoców do zjedzenia: jabłko, potem banan, a potem jabłko: aba.

1. Kiedy zaczynamy, goni nas duch, a wyrażenie regularne, które pozostało do dopasowania, to aba*.
2. Zjadamy pierwsze jabłko, a wyrażenie regularne, które mamy teraz do dopasowania, to ba*. Duch wciąż nas goni, ponieważ owoc, który do tej pory zjedliśmy, jabłko, nie pasuje do wyrażenia regularnego.
3. Następnie jemy banana. Wyrażenie regularne, które pozostało do dopasowania, to a*. Teraz duch zaczyna uciekać, ponieważ technicznie rzecz biorąc, abjuż pasuje aba*.
4. Możemy spróbować zjeść ducha lub zjeść kolejne jabłko, w takim przypadku wyrażenie regularne, które pozostało do dopasowania, to still a*. Duch wciąż ucieka, ponieważ abapasuje również do wyrażenia regularnego aba*.

Działa tu jeszcze jedna funkcja. Funkcja sprawdza, czy duch goni Pac-Mana, czy Pac-Man już dopasował wyrażenie regularne i goni ducha. Ta funkcja jest nazywana funkcją dopuszczającą wartość null; sprawdza, czy wyrażenie regularne, które pozostało do dopasowania, pasuje do pustego ciągu. Może to zrobić, ponieważ jeśli wyrażenie regularne, które pozostało do dopasowania, pasuje do pustego łańcucha, owoc, który zjadł, musiał już wystarczyć, aby spełnić wyrażenie regularne.

Algorytm dopasowywania pochodnych

Oznacza to, że do napisania algorytmu dopasowywania pochodnych potrzebujemy tylko dwóch funkcji:

1. funkcja pochodna
2. funkcja zerowa

Jeden w Golang dla imperatywnych programistów:

i inny w Haskell dla programistów funkcjonalnych:

Te dwie funkcje są równoważne i po prostu napisane w różnych stylach programowania. W kodzie Haskella, foldlzwanym także w innych językach krotnie w lewo lub zmniejszaniem, wykonuje za ciebie pętlę for. Ponadto w Haskell nie potrzebujemy przecinków do przekazywania parametrów do funkcji; ponieważ aplikacja funkcji jest najczęstszą operacją w funkcjonalnym języku programowania, używamy spacji do oddzielania parametrów.

Teraz zagłębimy się w sposób implementacji funkcji dopuszczających wartość null i funkcji pochodnych.

Dygresja fabularna Pac-Mana Origin

Ale zanim to zrobimy, nie wiem, czy kiedykolwiek zastanawialiście się nad historią powstania Pac-Mana. Twierdzę, że nie było beczki z odpadami nuklearnymi, do której wpadł Pac-Man, w wyniku czego Pac-Man zyskał moc zjadania duchów. Logika jest dużo prostsza.

Pac-Man to owoc! Kiedy Pac-Man zjada inne owoce, Pac-Man jest kanibalem. Więc jeśli kiedykolwiek ściga cię duch, musisz zjeść trochę ludzkiego mięsa, a duch powinien, przynajmniej tymczasowo, zacząć od ciebie uciekać. Sam tego nie próbowałem, ale logika wydaje się rozsądna.

To wyjaśnia, dlaczego zombie zawsze gonią ludzi. Jak powiedział kiedyś David Attenborough:

„Ścigające nas zombie same są ścigane przez duchy, których nie widzimy. Po tym, jak zombie zjedzą trochę naszego ludzkiego mięsa, zobaczysz, jak zachowują się dziwnie, gryząc powietrze, to jest zombie zjadający ducha, który ścigał go wcześniej.

Podstawowe operatory

Implementacja funkcji dopuszczających wartość null i funkcji pochodnych wymaga od nas najpierw zdefiniowania podstawowych operatorów dostępnych w naszych wyrażeniach regularnych.

Możemy myśleć o wyrażeniu regularnym jako opisując zestaw łańcuchów.

• Oznacza to, że pusty zestaw reprezentuje operator, który nie pasuje do żadnych łańcuchów.
• Pusty ciąg reprezentuje pojedynczy zestaw pojedynczego ciągu, który pasuje tylko do pustego ciągu.
• Znak reprezentuje również zestaw singleton, który pasuje tylko do pojedynczego znaku a.
• Następnie możemy połączyć te podstawowe wyrażenia regularne za pomocą operatorów, takich jak: or, concatenationoraz Kleene star, gdzie ri sreprezentuje dwa wyrażenia regularne, które łączymy.

Funkcja dopuszczająca wartość null

Możemy zacząć od funkcji nullable. Przyjrzyjmy się kilku przykładom i dowiedzmy się, które z tych wyrażeń regularnych pasuje do pustego ciągu, aby uzyskać wgląd w sposób implementacji tej funkcji.

• a*pasuje do pustego łańcucha, ponieważ zero lub więcej zawiera zero.
• (a*|b)pasuje do pustego ciągu, ponieważ lewa strona lub pasuje do pustego ciągu.
• abnie pasuje do pustego ciągu, ponieważ pasuje tylko do ciąguab
• ab*również nie pasuje do pustego ciągu, ponieważ ab*wymaga ciągu, który zaczyna się od ana
• (a|b)nie pasuje do pustego łańcucha, ponieważ ani lewa, ani prawa strona nie orpasuje do pustego ciągu.

Oto implementacja funkcji nullable. Lewa strona reprezentuje wartości, które są przekazywane do funkcji, a prawa strona reprezentuje implementację funkcji w tym przypadku. Czerwone duchy reprezentują fałsz, a niebieskie duchy prawdę:

• Pusty zestaw nie pasuje do pustego ciągu, ponieważ nie pasuje do żadnego ciągu.
• Pusty ciąg pasuje do pustego ciągu, ponieważ pasuje tylko do pustego ciągu.
• Znak anie pasuje do pustego łańcucha, ponieważ pasuje tylko do znaku a.
• Jeśli mamy logiczne or, musimy sprawdzić obie strony. Jeśli którykolwiek z nich pasuje do pustego ciągu, logiczny orpasuje do pustego ciągu.
• Aby concatenationdwa wyrażenia regularne pasowały do ​​pustego łańcucha, oba muszą pasować do pustego ciągu.
• I wreszcie, jeśli mamy zero or morecoś, to zawiera zero, co oznacza, że ​​zawsze pasuje do pustego łańcucha.

1. Naszym głównym operatorem jest orto, co oznacza, że ​​musimy sprawdzić możliwość zerowania lewej i prawej strony: bi a*.
2. Sprawdzamy i widzimy, że znak bpo lewej stronie nie jest pusty: false.
3. Następnie sprawdzamy i widzimy, że a*po prawej stronie można zerować: true.
4. Teraz wróciliśmy falsei truemożemy orje zdobyć true.

Ćwiczenia zerowe

Spróbuj przejść przez implementację i sprawdź, czy następujące wyrażenia regularne dopuszczają wartość null. Możesz je kliknąć, aby sprawdzić swoją odpowiedź:

1. a
2. a*(b*|∅)
3. εa
4. ∅*
5. (∅|b)*(abc|ε)

Zanim przyjrzymy się implementacji funkcji, spójrzmy na przykłady pochodnej. Tutaj weźmiemy pochodną kilku wyrażeń regularnych, wszystkie w odniesieniu do znaku a:

• Wyrażenie regularne, które pozostaje do dopasowania po a*zjedzeniu ajabłka, to still a*.
• Pochodną ab*względem ajest b*, ponieważ dopasowaliśmy już przedrostek a.
• Pochodna (a|b)bwzględem ajest b.
• Pochodna b|(a*b)względem ajest a*b. Lewa bnie pasowała, więc mogliśmy ją wyrzucić i azostała pochłonięta przez te zero or more apo prawej.
• Następnie mamy ab*, ten jest nieco trudny. Po zjedzeniu jabłka, wyrażenie regularne, które pozostaje do dopasowania, to b(ab)*. Ponieważ dopasowaliśmy tylko a, spodziewamy się zobaczyć co najmniej jeszcze jeden b.

• Pochodna zbioru pustego jest zawsze zbiorem pustym. Nie ma sposobu na odzyskanie, ponieważ pusty zestaw nie pasuje do niczego.
• Pochodna pustego łańcucha dotycząca dowolnego znaku jest zbiorem pustym. Nie spodziewał się, że będzie pasować do postaci. Dopasuje tylko pusty ciąg.
• Pochodna pojedynczego znaku do podobnego znaku (w tym przypadku apple) jest pustym łańcuchem, ponieważ po dopasowaniu samego siebie pozostaje tylko pusty ciąg.
• Pochodna znaku względem innego znaku, który nie jest równy, w tym przypadku banana, jest zbiorem pustym, ponieważ nie dopasowaliśmy określonego znaku.
• Pochodna orwyrażenia jest orpochodną. Po prostu zrzuca problem na swoje dzieci.
• Pochodna concatwyrażenia musi rozważyć, czy może pominąć pierwsze wyrażenie. Może pominąć pierwsze wyrażenie tylko wtedy, gdy pierwsze wyrażenie pasuje do pustego łańcucha i dopuszcza wartość null. Więc pierwszą rzeczą, którą robimy, jest sprawdzenie tego. Pomyślmy o przypadku, w którym nie można pominąć pierwszego wyrażenia, gdy wyrażenie rnie dopuszcza wartości null. Wtedy pochodna jest pochodną pierwszego wyrażenia concatenatedz drugim wyrażeniem s. Jeśli możemy pominąć pierwsze wyrażenie regularne, musimy rozważyć alternatywę, która jest tylko pochodną drugiego wyrażenia. Możemy wtedy skorzystać orz dwóch alternatyw: przeskakiwania ri nie przeskakiwania r, i w rezultacie zwrócić to.
• Wreszcie mamy staroperatora. Dopasowuje wyrażenie zero lub więcej razy. Ponieważ przekazujemy znak, nie jest to przypadek zerowy. Musimy więc rozważyć one or moresprawę. Oznacza to, że musimy wziąć pochodną wyrażenia wewnątrz stari concatenateponownie z tym zero or morewyrażeniem.

Przykład pochodny 1

Weźmy pochodną (ab)*względem a.

(ab)*jest zero or morewyrażeniem, więc patrzymy na zero or moreregułę. Widzimy, że wymaga to wzięcia pochodnej wyrażenia wewnątrz star.

To jest concatenationz ai b. Sprawdzamy więc, czy lewa strona jest dopuszczalna, a znak anie jest dopuszczalny. Oznacza to, że nie możemy go pominąć. Musimy wziąć pochodną awzględem a. Ale to jest pusty łańcuch, więc jeśli mamy concatenatepusty ciąg z prawą stroną, czyli b, otrzymamy b.

Teraz wracamy z powrotem do zero or more, pamiętajmy, że wzięliśmy pochodną abwzględem ai otrzymaliśmy z powrotem a b. Teraz możemy (ab)*ponownie połączyć to z i otrzymamy b(ab)*.

Przykład pochodny 2

Weźmy pochodną (a*ba)względem b.

• a*jest konkatenowany ba, więc przyjrzyjmy się regule konkatenacji.
• Sprawdzamy, czy lewa strona a*jest zerowa, co jest prawdą. Oznacza to, że możemy to pominąć, co oznacza również, że musimy utworzyć orpochodną z dwóch pochodnych.
• Lewa strona nie pasuje, ponieważ a*nie pasuje b.
• Na szczęście mamy alternatywę ba. Pochodna bawzględem bjest i a.

Pominąłem tu kilka szczegółów. Potraktuj to jako ćwiczenie, aby sprawdzić moją pracę, samodzielnie przechodząc przez funkcję.

Ćwiczenia pochodne

Spróbuj przejść przez implementację i sprawdź, jakie są pochodne poniższych wyrażeń regularnych względem b. Możesz je kliknąć, aby sprawdzić swoją odpowiedź:

1. εb
2. b*(b|c)
3. a*(b|c)
4. bεb
5. ∅* b

Mam nadzieję, że teraz rozumiesz, dlaczego jedzenie czerwonych wiśni daje ci możliwość jedzenia niebieskich duchów i jak zaimplementować dopasowanie wyrażeń regularnych za pomocą algorytmu pochodnego.

Omówiliśmy tutaj podstawowy działający algorytm, ale istnieje wiele sposobów na ulepszenie tego algorytmu za pomocą bardzo małych poprawek. W tym poście oszukaliśmy i przemilczeliśmy zasady upraszczania, używając ich bez wyjaśnienia, co stanie się szczególnie oczywiste, jeśli przejdziesz przez ćwiczenia. Nie rozmawialiśmy również o tym, jak można wykorzystać zapamiętywanie do leniwego zbudowania wydajnego automatu.

Możemy również łatwo rozszerzyć algorytm o nowe operatory, takie jak, not, interleavea nawet obsługiwać gramatyki bezkontekstowe. Niektóre z tych tematów omówię w następnym artykule .

W międzyczasie chciałbym zobaczyć twoją implementację tego algorytmu w języku programowania, z którym czujesz się najlepiej. Proszę o przesłanie linku w komentarzu.

Dziękuję Ci

• Brink van der Merwe za poświęcenie czasu na wyjaśnienie mi tego algorytmu.

• Brzozowski, Janusz A. „Pochodne wyrażeń regularnych”. Dziennik ACM (JACM) 11.4 (1964): 481–494.
• Owens, Scott, John Reppy i Aaron Turon. „Pochodne wyrażeń regularnych ponownie zbadane”. Dziennik programowania funkcjonalnego 19.2 (2009): 173–190.