Edytuj 2: Dla praktycznego pokazania, dlaczego jest to ważne, nie szukaj dalejwłasna przerwa spowodowana wyrażeń regularnych przez stackoverflow (2016-07-20)!

Edytować: To pytanie znacznie się zmieniło od czasu, gdy go o to zapytałem. Zobacz poniżej dwie szybkie i kompatybilne, ale nie w pełni funkcjonalne implementacje. Jeśli znasz więcej lub lepsze implementacje, wspomnij o nich, nadal nie ma jeszcze idealnej implementacji!

Gdzie mogę znaleźćniezawodnie szybka implementacja Regex?

Czy ktoś wie o normalnymbez cofania się (System.Text.RegularExpressions backtracks) liniowa implementacja wyrażenia regularnego dla .NET lub natywnego i rozsądnie używana z .NET? Aby było użyteczne, musiałoby:

miećnajgorszy przypadek złożoność czasowa oceny wyrażeń regularnychO (m * n) gdzie m to długość wyrażenia regularnego, a n długość wejścia.miećnormalna złożoność O (n), ponieważ prawie żadne wyrażenia regularne nie wyzwalają wykładniczej przestrzeni stanów lub, jeśli mogą, tylko w niewielkim podzbiorze wejścia.miećrozsądna prędkość budowy (tj. brak potencjalnie wykładniczych DFA)być przeznaczone do użytku przez ludzi, a nie przez matematyków - np. Nie chcę ponownie implementować klas znaków Unicode:Klasy znaków w stylu .NET lub PCRE to plus.Punkty bonusowe:punkty bonusowe dla praktyczności, jeśli implementuje funkcje oparte na stosie, któreniech obsługuje zagnieżdżanie kosztem zużycia pamięci O (n + m) zamiast pamięci O (m).punkty bonusowe zazarówno przechwytywanie podwyrażeńlub zamienniki (jeśli istnieje wykładnicza liczba możliwych dopasowań podwyrażenia, a następnie wyliczaniewszystko z nich jest z natury eksponencjalny - ale wyliczenie pierwszych kilku nie powinno być, i podobnie dla zamienników). Możesz obejść brak jednej z tych funkcji, używając drugiej, więc posiadanie jednego z nich jest wystarczające.punkty bonusowe lotsa zatraktowanie wyrażeń regularnych jako wartości pierwszej klasy (więc możesz wziąć unię, przecięcie, konkatenację, negację - w szczególności negację i przecięcie, jak to jest bardzo trudne do wykonania przez manipulację łańcuchową w definicji regex)leniwe dopasowanie tj. dopasowanie na nieograniczonych strumieniach bez umieszczania ich w pamięci jest plusem. Jeśli strumienie nie obsługują wyszukiwania, przechwytywanie podwyrażeń i / lub zamienników nie jest (w ogóle) możliwe w jednym przebiegu.Referencje są wyłączone, są zasadniczo niewiarygodne; tj. zawsze może wykazywać wykładnicze zachowanie przy patologicznych przypadkach wprowadzania.

Takie algorytmy istnieją (Jest to podstawowa teoria automatów ...) - ale czy są one praktycznie użytecznewdrożenia dostępny z .NET?

Tło: (możesz pominąć to)

Lubię używać Regexa do szybkich i brudnych porządków tekstu, ale wielokrotnie natrafiałem na problemy, w których wspólne wdrażanie NFA wykorzystywane przez perl / java / python / .NET pokazuje wykładnicze zachowanie. Przypadki te są niestety dość łatwe do uruchomienia, gdy tylko zaczniesz automatycznie generować wyrażenia regularne. Nawet nie-wykładnicza wydajność może stać się wyjątkowo słaba, gdy zmienia się wyrażenia regularne, które pasują do tego samego prefiksu - na przykład, w bardzo podstawowym przykładzie, jeśli weźmiesz słownik i zamienisz go w wyrażenie regularne, oczekuj strasznej wydajności.

Aby dowiedzieć się, dlaczego istnieją lepsze implementacje od lat 60., zobaczDopasowywanie wyrażeń regularnych może być proste i szybkie.

Niezbyt praktyczne opcje:Prawie idealny: Zestaw narzędzi FSA. Potrafi skompilować wyrażenia regularne do szybkich implementacji C DFA + NFA, umożliwia także przetworniki (!), Które mają klasy regex (enkapsulacja yay!), W tym składnię dla przecięcia i parametryzacji.Ale jest w prologu... (dlaczego coś z tego rodzaju praktycznymi funkcjami nie jest dostępne w głównym nurcie języka ???)Szybki, ale niepraktyczny: pełny parser, taki jak doskonałyANTLR ogólnie obsługuje niezawodnie szybkie wyrażenia regularne. Jednak składnia antlr jest o wiele bardziej szczegółowa i oczywiście pozwala na konstrukcje, które mogą nie generować poprawnych parserów, więc trzeba znaleźć jakiś bezpieczny podzbiór.Dobre wdrożenia:RE2 - biblioteka Google Open Source mająca na celu rozsądną kompatybilność z PCRE, bez referencji. Myślę, że jest to następca uniksowego portu regex lib plan9, podanego autorowi.TRE - także w większości kompatybilny z PCRE, a nawet wykonuje backreferences, chociaż używając tych tracisz gwarancje prędkości. I ma bardzo fajny przybliżony tryb dopasowania!

Niestety obie implementacje są C ++ i wymagałyby interop do korzystania z .NET.