Czy istnieją jakieś narzędzia, które przyjmą określone wyrażenie regularne i zwrócą najgorszy scenariusz pod względem liczby operacji wymaganych dla pewnej liczby znaków, z którymi porównywane jest wyrażenie regularne?Analiza najgorszego przypadku dla wyrażeń regularnych
Na przykład, biorąc pod uwagę (f|a)oo.*[ ]baz, ile kroków może wykonać silnik, aby dopasować 100 znaków?
Byłbym także zainteresowany, jeśli istnieje narzędzie, które może pobrać kilka próbek tekstu i pokazać średnie operacje dla każdego przebiegu.
Zdaję sobie sprawę, że będzie to bardzo zależało od zastosowanego silnika i implementacji - ale nie wiem, jak często to się dzieje. Więc jeśli jest to powszechne w wielu językach (co sprawia, że moje pytanie jest zbyt niejasne), byłbym szczególnie zainteresowany Perl i Python.
Doskonałe pytanie! Oczywiście będzie to zależeć od regex. Dobrze wiadomo, że czyste wyrażenia regularne (nawet jak w przykładzie "(x + x +) + y", o którym mowa poniżej) przyznają automatom automatycznym o stanie skończonym, ale te wspólne biblioteki regex faktycznie implementują te z cofaniem, w dużej mierze wspierając fantazyjne takie rzeczy jak kontekst. Narzędzie, które opisujesz, byłoby świetne w łapaniu http://en.wikipedia.org/wiki/Regular_expression_Denial_of_Service_-_ReDoS –