많은 파서 (시간이 모두 & 인 메모리)를 파열시키는 병리학 적 정규 표현식은 무엇입니까? 그리고 어떤 파서? 보너스는 정규식이 더 기본적이고 표준 일수록 악의적이지 않은 사용자가 무고하게 그것을 내놓을 가능성이 높다는 것을 나타냅니다. 실제 시간 및 메모리 데이터와 파서 버전을 자유롭게 게시하십시오. 러스 콕스의 우수한 article에서병리학 적 정규 표현식 (시간과 기억)?
:
내 시스템에 40 + 초 정도 걸립니다perl -e '$n=29; ("a" x $n) =~ (("a?" x $n).("a" x $n))'
. 그런 다음 $n++을 기하 급수적으로 증가 시키십시오.
모든 정규식 엔진이이를 최적화하지 않는 것은 이상합니다. 'a? '를'a {, 2}'로 줄이는 것은 매우 기본이기 때문에 수업에서 가르칩니다. –
종합적인 예이지만 언어를 통한 비교가 가능한 유용한 에세이. – smci
: $ perl -e '("a" x 100000) =~ /^(ab?)*$/;' :
()는 PERL에서 역 추적이 일을했다, 또는 적어도 다른 건 할하는 데 사용됩니다.? 나는 과도한 lookbehind 주장 또는 (EDIT이 기억하는 것). 이것은 분명히 segfault를 야기합니다. 이 기사에는 더 많은 내용이 있습니다.
파이썬과 GNU grep은 이것에 문제가 없습니다. 're.match (r '^ (ab?) * $', 'a'* 10000000)' –
이것은 내 perl 5.10.1 설치에 문제를 일으키지 않았고, 5.8 http : //codepad.org/hFlqUWk8 –
@Eric Strom : 저자가 perl 5.8.7을 테스트하고 있다고 생각합니다. – MAK
난 항상 PHP에서 PHP 또는 자바 스크립트 소스 코드의 내부 문자열을 일치하도록이 정규식을 사용
~'(\\.|[^'])*'|"(\\.|[^"])*"~s
을 그리고 그것은 거의 항상 매우 긴 문자열에 실패 (약 50000 문자 긴 할 것입니다). 기사 Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)의 첫 번째 예에서 적응
두 따옴표 유형을 모두 포함하므로 ~ 구분 기호를 사용합니다. 그것을 테스트하기 위해 파이썬 정규 표현식으로 변환하려고 시도했지만 이스케이프는 나를 괴롭힌다. 누구든지 그것을 변환 할 수 있습니까? – smci
주로 Tim Peters (http://stackoverflow.com/questions/1472047/regex-for-triple-quote)의 s 수정자를 제외한이 접근법을 사용하여 변환했습니다 (점마다 모든 문자가 일치합니까?) ... 나는 그것이 그것을 더 나쁘게 만든다고 생각한다. – smci
[이 포스터] (http://stackoverflow.com/questions/7004023/translate-the-intent-of-this-php-regex-for-multiline-strings-into-python-perl/7006231#7006231) 향상된 정규식의 효율성을 확인해보십시오! – smci
거의 모든 NFA 기반 정규식 엔진은 주제와 패턴을 모두 제어 할 수 있다면 준 - 무한 역 추적으로 속일 수 있습니다. DFA 기반 엔진은 역 추적을 할 필요가 없으므로 이러한 함정에 시달리지 않습니다. 다음 질문에 대한 대답은 "DFA는 일반적으로 NFA가 수행 할 수있는 기능을 지원할 수 없기 때문입니다." –