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.)
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.
Odpowiedzi:
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).źródło
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.
źródło