정규 표현식에 대한 정적 분석을 제공하는 라이브러리가 있습니까?

Question

구체적으로, 2 개 (또는 그 이상) 정규 표현식이 주어지면 둘 다 일치 할 입력이 존재하는지 알 수있는 라이브러리가 있습니까? Java 또는 .NET를 통해 쉽게 액세스 할 수있는 경우 보너스 포인트이지만 명령 줄도 좋습니다.

Asker 's log, 보충 :

이 알고리즘에 공급되는 일반 표현은 상당히 간단합니다. 나는 전망대가있는 커플이 있다고 생각하지만, 최소 및 최대 길이가 고정 된 문자 또는 문자 클래스의 상당히 간단한 조합입니다.

Answer 1

내가해야 할 일을 할 수있는 파이썬 라이브러리를 찾았습니다.

>>> import reCompiler
>>> fsa1 = reCompiler.compileRE('\d\d\d?\d?a')
>>> fsa2 = reCompiler.compileRE('123a')
>>> fsa3 = reCompiler.compileRE('a23a')
>>> print len(FSA.intersection(fsa1, fsa2).finalStates)
1
>>> print len(FSA.intersection(fsa1, fsa3).finalStates)
0

라이브러리가 호출됩니다 PYFSA. d {2,4}와 같은 진술을 d d d? d?로 전환하려면 전처리를 구현해야하지만, 그 외에는 내 요구에 잘 맞아야합니다. 입력에 감사 드리며 사람들이 다른 언어로이를 구현하는 라이브러리를 찾으면 반드시 포함합니다.

Answer 2

유용한 시간 안에 실행되지 않을 것입니다. Regex를 비교하는 것은 PSPACE 문제입니다

http://en.wikipedia.org/wiki/pspace-complete

REGEX에 추가 제한을 허용 할 수 있다면 운이있을 수 있습니다.

Answer 3

내가 당신을 올바르게 이해한다면, 당신은 2 개의 정규 표현식의 교차로가 빈 세트인지 아닌지 알고 싶습니다. 나는 그것이 어렵다고 생각하지만, 복잡성이 Regex의 길이에서 기하 급수적이라면 놀라지 않을 것입니다 (일부 동정형은 다른 사람들보다 더 쉬울 것입니다).

그럼에도 불구하고 Haskell 구현은 다음과 같습니다.http://sulzmann.blogspot.com/2008/11/playing-with-regular-expressions.html

그리고 프롤로그 구현http://www.let.rug.nl/vannoord/fsa/

Answer 4

이것은 시작할 곳 일 수 있습니다.

http://kedrigern.dcs.fmph.uniba.sk/~riso/papers/kraphd.pdf