هل هناك مكتبة توفر تحليلا ثابتا للتعبيرات العادية؟

Question

على وجه التحديد، هل هناك مكتبة، عند إعطاء تعبيرات 2 (أو أكثر)، يمكن أن تخبر ما إذا كان موجودا مدخلات سيتطابق كلاهما؟ نقاط المكافأة إذا كان يمكن الوصول إليها بسهولة عبر Java أو .NET، ولكن سطر الأوامر سيكون على ما يرام أيضا.

سجل Asker، التكميل:

التعبيرات المنتظمة التي ستغذي إلى هذه الخوارزمية بسيطة إلى حد ما. بينما أعتقد أن هناك زوجين مع Lookaheads، فهي جميعها مجموعات بسيطة إلى حد ما من الحرفيات أو فصول الأحرف ذات الأدلة الثابتة والحد الأقصى للأطول.

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 (على الرغم من أن بعض Regexes ستكون أسهل من غيرها من غيرها)

بغض النظر، إليك تنفيذ 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/apapers/kraphd.pdf.