Sprawdź, czy dany regex pasuje do niczego.

Question

Czy można sprawdzić, czy dane wyrażenie regularne będzie pasowało do dowolnego ciągu? W szczególności szukam funkcji matchesEverything($regex), która zwraca true iff $regex dopasuje dowolny ciąg.

Przypuszczam, że jest to równoważne z pytaniem: "biorąc pod uwagę wyrażenie r, czy istnieje ciąg znaków, który nie pasuje do r?" i nie sądzę, że można to rozwiązać bez umieszczania granic na zbiorze "wszystkich ciągów". Np. Jeśli założę, że łańcuchy nigdy nie będą zawierały "blahblah", to mogę po prostu sprawdzić, czy r pasuje do "blahblah". Ale co, jeśli nie ma takich granic? Zastanawiam się, czy ten problem można rozwiązać sprawdzając, czy regex r jest równoważne .*.

Answer 1

nie dokładnie odpowiedzieć na to pytanie, ale mam nadzieję, że trochę wyjaśnia, dlaczego prosta odpowiedź jest trudne do zdobycia:

Pierwszy termin „regex” jest nieco mętna, więc po prostu w celu wyjaśnienia, że mają:

• "Ścisłe" wyrażenia regularne, które są równoważne deterministycznym automatom skończonym (DFA).
• Wyrażenia regularne zgodne z Perl (PCRE), które dodają kilka dzwonków i gwizdków, takich jak znaki wyprzedzające, odnośniki itp. Są one również implementowane w innych językach, takich jak Python i Java.
• Rzeczywiste wyrażenia regularne Perla, które mogą stać się jeszcze bardziej szalone, w tym dowolny kod Perla, poprzez konstrukcję ?{...}.

Myślę, że ten problem można rozwiązać przy użyciu ścisłych wyrażeń regularnych. Wystarczy skonstruować odpowiedni DFA i przeszukać ten wykres, aby sprawdzić, czy istnieje jakakolwiek ścieżka do stanu nieprzyjęcia. Ale to nie pomaga w przypadku regexu "realnego świata", którym zwykle jest PCRE.

Nie sądzę, że PCRE jest Turing-complete (choć nie wiem - zobacz też to pytanie: Are Perl regexes turing complete?). Gdyby tak było, to myślę, że jak skomentował Jim Garrison, jest to zasadniczo problem z zatrzymaniem. To powiedziawszy, nie jest łatwo przekształcić je w DFA, czyniąc powyższą metodę bezużyteczną ...

Nie mam odpowiedzi na PCRE, ale należy pamiętać, że wyżej wymienione konstrukcje (backreferences itp.) sprawiłoby, że byłoby to dość trudne, jak sobie wyobrażam. Chociaż waham się powiedzieć "niemożliwe".

Prawdziwe regex Perla z ?{...} w tym jest zdecydowanie Turing-zupełny, więc są smoki, i myślę, że masz pecha.