Jakie języki rozpoznają wyrażenia regularne zgodne z Perl?

23

Jak mówi tytuł, spędziłem kilka godzin w zeszły weekend, próbując podsumować klasę języków pasujących do wyrażeń regularnych kompatybilnych z Perl, z wyłączeniem dowolnego dopasowującego operatora, który pozwala na wykonanie dowolnego kodu wewnątrz wzorca .

Jeśli nie wiesz, co to są PCRE, przeczytaj to i to .

Problem polega na tym, że zasoby dostępne w Internecie w dużej mierze kończą się na językach bezkontekstowych, a PCRE mogą się różnić od tych (patrz poniżej); ale tak naprawdę nie wiem, gdzie znaleźć więcej twierdzeń lub artykułów na ten temat.

W szczególności: PCRE są oczywiście nadzbiorem zwykłych języków (ponieważ składnia PCRE zawiera wszystkie operatory języków zwykłych).

Każde CFG można umieścić w normalnej formie Greibacha, co usuwa lewą rekurencję. Myślę, że można tego użyć za pomocą (?(DEFINE)...)grup do „przetłumaczenia” gramatyki na pasujące podprogramy, unikając zadławienia się lewą rekurencją, tłumacząc:

  • nieterminalny na czele każdej produkcji staje się podprogramem (?<HEAD>...)
  • treść każdej produkcji jest umieszczana w podprogramie; terminale pozostają niezmienione, nieterminale stają się wywołaniami procedur (tj. (?&NONTERMINAL));
  • wszystkie produkcje z tym samym nieterminalem co głowa są ORedowane razem za pomocą |operatora (plus dodatkowe grupowanie z (?:...), jeśli to konieczne)
  • wzorzec staje się następnie (?(DEFINE)...)grupą zawierającą wszystkie „przetłumaczone” produkcje i wywołanie procedury symbolu początkowego w celu dopasowania całego łańcucha, tj.^(?(DEFINE)...)(?&START)$

To powinno poradzić sobie z każdym CFG. Dlatego PCRE powinny być w stanie dopasować dowolny CFL.

Jest więcej: weźmy prosty język tj. język napisów powtórzony dwukrotnie. Ten język nie jest CFL - lemat pompowania dla CFL zawodzi. (Zwróć szczególną uwagę na to, że , więc nie możesz po prostu pompować początków lub końców dwóch powtarzających się łańcuchów.)

L.={ww|wΛ}
|vxw|p

Jednakże, ten język jest łatwo dopasowane przez PCRE: ^(.*)\1$. Dlatego jesteśmy zdecydowanie powyżej CFL.

Ile wyżej? Cóż, jak powiedziałem, nie mam pojęcia. Nie mogłem znaleźć żadnych zasobów na temat CSL ani innych klas pośrednich, które mogłyby podjąć decyzję. Każdy ekspert chce o tym dyskutować?

Dodatek: Poproszono mnie o dokładne określenie, który podzbiór składni PCRE musi być dozwolony. Jak napisałem na początku postu, chciałem wykluczyć dowolnego operatora, który pozwala na wykonanie dowolnego kodu wewnątrz wzorca, takiego jak ??{}.

Dla dobra tego argumentu, myślę, że możemy trzymać się składni zdefiniowanej przez stronę podręcznika pcresyntax (3) , która jest rozsądnym podzbiorem tego, co oferuje Perl 5.10-5.12, pomijając objaśnienia (ponieważ nie są zawarte we wzorcu). Nie jestem pewien, czy dodanie lub usunięcie czasowników sterujących cofaniem zmienia język, który możemy rozpoznać; jeśli tak, dobrze byłoby dowiedzieć się, jakie zajęcia otrzymujemy z tymi i bez nich.

peppe
źródło
2
W pytaniu proszę podać wybraną definicję PCRE, ponieważ zmieniła się ona między wersjami. Prawdziwe wyrażenia regularne Perla mogą zawierać dowolny kod Perla, co czyni je kompletnymi Turinga.
Gilles 'SO - przestań być zły'
Na końcu dodałem notatkę, mam nadzieję, że to wyjaśni ten punkt.
peppe

Odpowiedzi:

7

Znalazłem również ten post na blogu niezwykle interesujący http://nikic.github.io/2012/06/15/The-true-power-of-regular-expressions.html . Zapewnia to ten sam dowód, który podałem wcześniej o tym, że wyrażenia regularne rozpoznają CFL (przepisując gramatykę przez DEFINEbloki), a nawet niektóre CSL (jak język powtarzanych ciągów); opiera się na tym i kontynuuje, dając dowód, że wyrażenia regularne z referencjami wstecznymi są trudne do NP (poprzez redukcję 3-SAT do wyrażeń regularnych).

peppe
źródło
2
Kiedy autor mówi „NP-zupełny”, powinien powiedzieć „NP-trudny”. Nie dostarczają żadnego dowodu, że klasa języków PCRE jest zawarta w NP.
András Salamon
To prawda, że ​​jest to również odnotowane w komentarzach.
peppe
5

Decydują co najwyżej o językach kontekstowych (które, jak zauważyłeś, to nadzbiór języków bezkontekstowych). Zobacz ten post mnisi perl .

Podstawowa wiedza jest taka, że ​​„pamięć” maszyny to liczba grup przechwytywania, która jest ograniczona liniowo.

Xodarap
źródło
5
Argument podany w drugim akapicie wyjaśnia, dlaczego PCRE nie może zaakceptować więcej niż CS, ale nie dlaczego to włączenie jest dokładne (co sugerujesz w pierwszym akapicie). Nie wydaje się też, żeby linkowany artykuł również to potwierdził.
Raphael
Cóż, nie można grupować więcej niż to, co znajduje się w ciągu wejściowym, a liczba grup jest ustalona w danym wzorcu, więc masz górny (liniowy) limit pamięci używanej przez wzorzec. Mimo to brakuje mi formalnego dowodu PCRE -> transformacja automatu ograniczona liniowo ...
peppe
Tak, wy dwaj macie rację. Zmodyfikowałem odpowiedź.
Xodarap,
Zobacz także perlmonks.org/?node_id=406253, aby uzyskać wcześniejszą dyskusję.
András Salamon