Gdzie większość implementacji REGEX przypada na skalę złożoności?

Większość współczesnych implementacji wyrażeń regularnych, takich jak Perl lub .NET, wykracza poza klasyczną informatyczną definicję REGEX z funkcjami takimi jak lookahead i lookbehind. Czy te funkcje umożliwiają analizowanie instrukcji, których nie można opisać za pomocą skończonego automatu bez odpychania? Jak bardzo zbliża się do ukończenia Turinga, jeśli to możliwe?

Nie sądzę, że prawdziwym problemem jest pytanie, co oznacza nieograniczony; nie jest to gorsze niż jakakolwiek inna sytuacja w parsowaniu.

Problem polega na scharakteryzowaniu odwołań wstecznych, które są zarówno bardzo potężne, jak i bardzo ograniczone: umożliwiają opis niektórych języków bezkontekstowych, bez uwzględnienia niektórych języków bezkontekstowych. Na przykład, wyrażenie regularne (a*)b\1b\1dopasowuje ciągi postaci n ⋅ b ⋅ n ⋅ b ⋅ n , i można użyć lematu pompowania, aby pokazać ten nie jest językiem bezkontekstowych. Jednak z drugiej strony wyrażenia regularne z odniesieniami wstecznymi nie wydają się wystarczające do dopasowania do zrównoważonego języka nawiasów, który jest prototypowym językiem bezkontekstowym.$a^n \cdot b \cdot a^n \cdot b \cdot a^n$

Łatwo jest podać semantykę denotacyjną mówiącą, jakie ciągi znaków są w języku do wyrażenia regularnego, ale podanie dobrej charakterystyki teoretycznej automatu wydaje się o wiele trudniejsze. Jest to coś w rodzaju maszyny rejestrującej, do której rejestrów można skopiować podłańcuchy danych wejściowych i której można użyć do przetestowania bieżącego ciągu, ale dla której nie ma możliwości modyfikowania tych rejestrów.

Ludzie zajmujący się teorią modeli skończonych mają wiele funky modeli maszyn i byłoby interesujące wiedzieć, czy odpowiada to którykolwiek z ich modeli.

Problem z odpowiedzią na to pytanie polega na uchwyceniu pojęcia „nieograniczony” w rzeczywistej implementacji. Na przykład wyrażenie regularne /(.*)\1/przechwytuje język , który nie jest kontekstowy. W praktyce mogą obowiązywać ograniczenia stosu (np. nie może być dłuższy niż jakaś duża liczba ), co skutecznie zmienia język na , który dla każdego ustalonego jest ponownie wyrażeniem regularnym.w K L K = { w w | w ∈ Σ ∗ , ∣ w ∣ ≤ K } $L = \{ ww | w \in \Sigma^*\}$$w$$K$$L_K = \{ ww | w \in \Sigma^*, \mid w \mid \le K\}$$K$

Ale w zasadzie wyrażenia regularne, jak określono, są potężniejsze niż zwykłe języki, ponieważ to pokrewne pytanie dyskutuje o wiele bardziej szczegółowo (z dobrym przykładem).

Ciekawym rezultatem, wziętym z tego drugiego pytania , również powiązanego przez Suresha Venkata, jest to, że „praktyczne” wyrażenia regularne są NP-zupełne, a zatem powinny być równoważne pod względem mocy SAT.

Ponieważ nie jestem ekspertem, choć zgadzam się z tym, że intuicyjnie „wyrażenia regularne z odniesieniami wstecznymi nie wydają się wystarczające, aby dopasować zrównoważony język nawiasów”, dzieje się coś dziwnego. Kompletność NP oznacza, że ​​każdy problem NP może być wielomianowo zredukowany do wyrażenia regularnego, więc prawdopodobnie istnieje tylko wielomianowa redukcja z języka „zrównoważonych nawiasów” do języka rozpoznawalnego z wyrażeniami regularnymi. Ale znowu, może być jakiś absurdalny regexp do parsowania CFL, ponieważ mogą nawet parsować niepierwotne liczby jednoargumentowe!

Prawdopodobnie lekcja jest taka, że ​​klasy złożoności i klasy językowe nie są w ogóle porównywalne. Co również sugeruje przeformułowanie twojego pytania, aby odwołać się raczej do hierarchii Chomsky'ego niż do „skali złożoności” (nawet jeśli, szczerze mówiąc, nie byłem tym zaskoczony).

Charles Stewart pisze:

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.

Częściowy podgląd (przynajmniej oświadczenie) można znaleźć w Książkach Google na stronie 289, a bibliograficzne odniesienie do artykułu można znaleźć tutaj . Należy zauważyć, że w artykule rewbr oznacza wyrażenie regularne z odwołaniami wstecznymi.

PCRE, najpopularniejsza implementacja „wyrażeń regularnych”, implementuje również wzorce rekurencyjne, które wykraczają poza odniesienia wsteczne. Pytanie o ich złożoność zostało właśnie zadane w Stackoverflow. Zgodnie z praktyczną, dogłębną odpowiedzią Perla guru briana d foya, czyni to PCRE tak potężnym, jak gramatyki bezkontekstowe. Jednak składnia jest okropna w porównaniu z formą Backus-Naur.