Wyrażenia regularne nie są

36

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

L={an:n is not a prime number}

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?

Greg Bacon
źródło

Odpowiedzi:

46

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 .

Charles Stewart
źródło
5
Zgadzam się, coś w stylu „Perl regex” („POSIX regex” itp.) Vs. „zwykły język” powinno być wystarczająco jasne, aby zapobiec jakiejkolwiek możliwości błędnej interpretacji.
Jukka Suomela
Wyrażenia regularne Perla mają o wiele więcej dodatkowych funkcji niż tylko cofanie się.
reinierpost
@reinierpost To prawda, ale myślę, że powrót jest najważniejszy z formalnego punktu widzenia języków. Wyrażenia regularne w Perlu mają takie funkcje jak wykonywanie dowolnego kodu Perla, ale myślę, że wyrażenia regularne należy interpretować luźno jako obejmujące PCRE. PCRE zawierają takie dziwactwa jak wzorce rekurencyjne, ale są to mroczne sztuki, które zabierają cię daleko poza sferę zwykłych języków. Mogę jednak zaktualizować swoją odpowiedź, aby je uwzględnić.
Charles Stewart
18

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.

Dominik D. Freydenberger
źródło
7
Niestety, termin przedłużony wyrażenie regularne jest już zajęta przez POSIX, który rozróżnia podstawowe wyrażenie regularne (BRE) oraz rozszerzone wyrażenie regularne (ERE) , z których oba są rozszerzone wyrażenia regularne w zależności od definicji.
Jörg W Mittag
@ Jörg: Właściwie, zgodnie z tym, ani rozszerzone, ani podstawowe wyrażenia regularne POSIX nie mają większej mocy niż wyrażenia regularne. I czysty (inny niż GNU) BRE wydaje się być faktycznie mniej wydajny niż wyrażenia regularne (brakuje operatora alternacji).
sepp2k
Zobacz „Rozszerzone wyrażenia regularne” Carle i Narendran (2009), aby uzyskać najnowsze wyniki dotyczące tego „rewbr”: portal.acm.org/citation.cfm?id=1533235
Jakob
Kolejne ostatnie wyniki w tej klasie językowej: „Na przecięciu języków regularnych z językami regularnymi” Campeanu i Santean (TCS 410, 2009) „Test wielomianu w czasie dla dużych klas rozszerzonych wyrażeń regularnych” Reidenbacha i Schmida (CIAA 2010 ) oraz „Rozszerzone wyrażenia regularne: zwięzłość i rozstrzygalność” (przeze mnie, które pojawią się na STACS 2011).
Dominik D. Freydenberger,
6

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

Arthur MILCHIOR
źródło
Czy masz jakieś wskazówki?
András Salamon
5
@ András: Myślę, że Arthur mówi o ?{CODE}dyrektywie Perla , która pozwala wyrażeniom wzorcowym przeplatać kod programu w wyrażeniach regularnych. Rozumiem, że PCRE są zwykle definiowane jako „deklaratywna” część języka, a cały język nazywany jest językiem wzorcowym. Według WP, Aho, 1990, „Algorytmy wyszukiwania wzorców w ciągach znaków” pokazują, że problem członkostwa dla zwykłych języków z cofaniem jest NP zakończony. Nie ma innych twardych funkcji dla deklaratywnych PCRE.
Charles Stewart
Dodałem link; Nie patrzyłem na kod źródłowy, więc tak naprawdę nie wiem, jak to działa i czy jest jakiś dowód, że kompilacja jest naprawdę poprawna.
Arthur MILCHIOR
1
Przepraszamy, ale zgodnie z twoim argumentem, ponieważ rachunek lambda jest zakończony metodą Turinga, wyszukiwanie jego nazwy nie miało sensu. To samo dotyczy wszystkich innych formalizmów i języków obliczeniowych Turinga. Co więcej, kompletność Turinga nie opisuje, jak ekspresyjny jest język, więc nie ma sensu identyfikować języków tylko dlatego, że są one kompletne. Oczywiście mój przykład dotyczący rachunku lambda był ekstremalny.
Blaisorblade,
2

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.

Michaël Cadilhac
źródło
1
Niezbyt często używane, IMHO.
Blaisorblade,
Jest / jest / szeroko stosowany w teorii ważonych automatów, patrz en.wikipedia.org/wiki/Rational_language . Sporo razy widziałem to także w dziedzinie języków w grupach.
Michaël Cadilhac,
1

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.

Blaisorblade
źródło
0

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

Raphael
źródło
2
Zasadniczo zgadzam się z twoim rozumowaniem, ale Campeanu, Santean i Yu już użyli terminu wyrażenia wzorców do oznaczenia podobnej klasy języków z „czystszą” definicją (patrz „Wyrażenia wzorców i automaty wzorców”, IPL 92 (2004) )
Dominik D. Freydenberger,