Wyrażenia regularne nie są

Zapytaj nawet kogoś, kto ma doświadczenie w informatyce, co to jest wyrażenie regularne, a odpowiedź prawdopodobnie wykroczy poza ograniczenie bycia w zasięgu automatu skończonego.

Na przykład „wyrażenie regularne”

/^1?$|^(11+?)\1+$/

stworzona przez znaną osobowość Perla Abigail (i część zestawu testów Perla od 2002 r.) opisuje maszynę, która akceptuje tylko złożone liczby jednoargumentowe, ale ćwiczenie 4.5 (b) w trzecim wydaniu An Linuksa i Automaty Petera Linza wykorzystuje czytelnik lemat pompowania , aby udowodnić, że

$\mathcal{L} = \left\{ a^n : n\ \mathrm{is\ not\ a\ prime\ number} \right\}$

nie jest zwykłym językiem.

W kontekście, w którym rozróżnienie jest ważne, co powinniśmy nazwać wyrażeniami ściśle potężniejszymi?

Larry Wall zaproponował, abyśmy użyli „wyrażenia regularnego” dla formalizmu zaproponowanego przez Kleene i „regex” dla wyrażeń dla powszechnie używanych rozszerzeń. Jest to dość powszechnie stosowana konwencja. Jeśli chcesz wyjaśnić, że mówisz o wyrażeniach regularnych w sensie języków formalnych, zazwyczaj nie jest trudno przetłumaczyć je na mówienie o językach regularnych.

Potęga wyrażeń regularnych pochodzi z cofania się, a także pracowano nad automatami dla zwykłych języków z cofaniem. Zobacz w szczególności Becchi i Crowley, 2008, Rozszerzanie skończonych automatów do skutecznego dopasowywania wyrażeń regularnych zgodnych z Perl .

Wyrażenia te zostały zbadane przez Aho (Handbook of Theoretical Computer Science, Vol. A, Chp. 5) i Campeanu, Salomaa, Yu („Formalne studium praktycznych wyrażeń regularnych”, International Journal of Foundations of Computer Science, 14: 1007 –1018, 2003), a także niektóre prace uzupełniające.

Aho nazywa bardziej zaawansowane wyrażenia „rewbr” (wyrażenie regularne z odniesieniami wstecznymi), Campeanu i in. użyj „rozszerzonego wyrażenia regularnego” oraz „praktycznego wyrażenia regularnego”. Jak się wydaje, „rozszerzona ekspresja regularna” jest terminem najczęściej używanym w najnowszej literaturze.

Opierając się na terminach „racjonalne wyrażenie” ze szkoły francuskiej i biorąc pod uwagę fakt, że te wyrażenia są używane w prawdziwym świecie, ja sam lubię „prawdziwe wyrażenie”.

Dodatek: Rozdział w mojej pracy doktorskiej dotyczy tej klasy języków formalnych (odpowiedni artykuł ma pojawić się na STACS 2011). Pisząc ten rozdział i artykuł, eksperymentowałem z różnymi terminami. W końcu zdecydowałem się użyć rozszerzonych wyrażeń regularnych dla modelu z referencjami wstecznymi oraz odpowiednich wyrażeń regularnych dla ładnych i normalnych wyrażeń regularnych. Ponieważ dość denerwująca jest zmiana terminologii w dokumencie, który jest już całkowicie (lub głównie) pisany, myślę, że niektórzy mogą być zainteresowani doświadczeniami, które doprowadziły do ​​mojego wyboru:

Po pierwsze, wyrażenia regularne i przewijane tak naprawdę nie przewracają się po języku, a używanie ich raz po raz w ciągu całego artykułu bardzo męczyło się w pisaniu i czytaniu, zwłaszcza przy użyciu dowolnej z możliwych form liczby mnogiej. Wyrażenia regularne podobne do PERL również były nieporęczne. Oczywiście nie jestem językiem ojczystym, więc YMMV.

Po drugie, gdy tylko chce się mówić o obu modelach, wygodnie jest używać terminów, które są odmianą wyrażenia regularnego , ponieważ pozwala to na podkreślenie podobieństwa lub różnic w razie potrzeby (np. „Wyrażenie regularne, czy to właściwe, czy rozszerzony"). Co więcej, pozwala to łatwo podkreślić specjalny przypadek „rozszerzonych wyrażeń regularnych bez odwołań wstecznych”, mówiąc o specjalnych przypadkach w całej klasie, zamiast porównywać różne modele.

Po trzecie, wolałem używać terminu, który jest już używany w literaturze, zamiast nowego terminu, który pozostawił mi wybór między rozszerzonymi wyrażeniami regularnymi a praktycznymi wyrażeniami regularnymi . Drugi wybór sugerował (przynajmniej domyślnie), że właściwe wyrażenia regularne są w jakiś sposób niepraktyczne, co wydawało się dość dziwne (zwłaszcza, że ​​RE2 Google'a nie używa odnośników zwrotnych i wydaje się być całkiem praktyczny).

Oczywiście ten wybór jest tylko moim „osobistym maksimum lokalnym”, a w zależności od potrzeb inne wybory mogą być bardziej odpowiednie.

Wiadomo, że tak zwane wyrażenie regularne perla jest wystarczająco potężne, aby zakończyć Turinga; istnieje nawet kompilator ze zwykłego programu do perl regexp.

Dlatego wątpię, czy warto szukać nazwy tego rodzaju „wyrażeń regularnych”.

Spójrz na przykład na http://search.cpan.org/~asavige/Acme-EyeDrops-1.62/lib/Acme/EyeDrops.pm

Myślę, że najlepszym terminem na „wyrażenie regularne w kontekście automatów” jest „wyrażenie racjonalne”, jak to się stosuje, powiedzmy, w „Elementach teorii automatów” Sakarovitcha lub Handbook of Weighted Automata.

Biorąc pod uwagę inne odpowiedzi, sugerowałbym, że „języki regularne” są bezpieczne, a po krótkim zaznaczeniu różnicy mówić o „praktycznych wyrażeniach regularnych” dla wyrażeń regularnych (z cofaniem).

Zauważ też, że ten sam wyrażenie regularne, zarówno jako wyrażenia regularne, jak i praktyczne, może mieć różną semantykę, ponieważ w tym drugim przypadku semantyka jest definiowana w kontekście cofania, z różnymi wynikami. Szczegóły byłyby nie na temat, ale odpowiem, jeśli zadasz kolejne pytanie (może raczej na SO, niż tutaj, nie wiem) i powiadomisz mnie poprzez komentarz.

Możemy nazwać je wyrażeniami wzorcowymi . Może to wprowadzać zamieszanie w językach wzorcowych, ale przynajmniej są one mniej powszechne.