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

19

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?

Dan Monego
źródło
2
Blisko powiązane pytanie: czy mamy coś interesującego między „wyrażeniami regularnymi z odwołaniami wstecznymi” a „wyrażeniami regularnymi, które mogą zawierać dowolny kod programu”? Na przykład, czy wyrażenia regularne z odniesieniami wstecznymi i lookahead / lookbehind są bardziej wyraziste niż wyrażenia regularne z backreferencjami, ale nie ma lookahead / lookbehind? Co z „Specjalnymi czasownikami kontrolującymi cofanie” w Perlu?
Jukka Suomela,
Powiązane (i prawdopodobnie niepoprawne): stackoverflow.com/questions/2974210/…
Aryabhata

Odpowiedzi:

18

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 nb nb 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.anbanban

Ł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.

Neel Krishnaswami
źródło
9

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 } KL={ww|wΣ}wKLK={ww|wΣ,w∣≤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).

Suresh Venkat
źródło
Czy {ww | w ∈ Σ ∗, ∣w∣≤K} nie byłby rozpoznawalny CSL lub TM?
dhruvbird
arggh. powinienem był zrobić ww ^ R. naprawi. dzięki
Suresh Venkat
Właściwie miałem o to pytanie. Czy ww CSL jest rozpoznawalny? Nie byłem (jeszcze) w stanie wymyślić dla niego LBA, więc po prostu zastanawiam się ...
dhruvbird
1
{ww:wΣ}
5

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.

Blaisorblade
źródło
3

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.

Jakob
źródło