2010-09-01 10 views
27

नियमित अभिव्यक्ति सीखने में मुझे आश्चर्य हुआ कि अंतर्निहित इंजन कैसे काम करता है। शायद अधिक विशेष रूप से, मैं इस बारे में अधिक जानना चाहता हूं कि यह कैसे evalutates, प्राथमिकताओं और अभिव्यक्ति का विश्लेषण करता है। मुझे लगता है कि रेगेक्स इंजन मेरे लिए एक ब्लैकबॉक्स है, और मैं वास्तव में इसे समझने का आनंद लेता हूं।कैसे एक RegEx इंजन

तो मैं पूछना चाहूंगा कि क्या कुछ महान संसाधन हैं जिन्हें मैं रेगेक्स इंजन सिद्धांत पर चर्चा कर सकता हूं।

* नोट: मुझे इंजन बनाने में दिलचस्पी नहीं है, बस इसके आंतरिक कार्यों को सीखना।

+1

मास्टरिंग नियमित अभिव्यक्तियां एक महान पुस्तक है हालांकि यह उस विषय पर केंद्रित नहीं है, लेकिन इसमें कई अध्याय हैं जो प्रत्येक रेगेक्स इंजन से व्यवहार करते हैं। (हालांकि यह इंजन के विवरण का विश्लेषण करने के बजाय व्यावहारिक तरीके से अधिक है) – NorthGuard

+0

मैं वास्तव में उस पुस्तक के चारों ओर पोकिंग कर रहा हूं लेकिन उन अध्यायों के बारे में नहीं जानता था। धन्यवाद! – Robb

+1

एक उत्कृष्ट कलाकृति है: [कैसे रेगएक्स काम करता है] (http://perl.plover.com/Regex/article.html) – PHPst

उत्तर

32

रेगेक्स इंजन के दो मुख्य वर्ग हैं।

  1. पर परिमित अवस्था automaton आधारित हैं। ये आमतौर पर सबसे तेज़ होते हैं। वे state machine बनाकर काम करते हैं, और इसे इनपुट स्ट्रिंग से वर्ण खिलाते हैं। इस तरह के इंजनों में कुछ और उन्नत सुविधाओं को लागू करने के लिए असंभव नहीं है, यह मुश्किल है।

    एफएसए आधारित इंजन के उदाहरण:

    • Posix/GNU ERE/BRE — ऐसे ग्रेप, SED और awk के रूप में सबसे यूनिक्स उपयोगिताओं, में प्रयुक्त।
    • Re2 — ऑटोमाटा आधारित विधि को और अधिक शक्ति देने की कोशिश करने के लिए अपेक्षाकृत नई परियोजना।
       
  2. उन वापस ट्रैकिंग पर आधारित है। ये अक्सर मशीन निर्देशों जैसा दिखने वाले बाइट-कोड में पैटर्न संकलित करते हैं। इंजन तब निर्देश को निर्देशित करते हुए कोड को निष्पादित करता है। जब कोई निर्देश विफल रहता है, तो यह इनपुट से मेल खाने के लिए एक और तरीका खोजने के लिए बैक-ट्रैक करता है।

    वापस ट्रैकिंग आधारित इंजन के उदाहरण:

    • Perl — मूल। इस प्रकार के अधिकांश अन्य इंजन पर्ल भाषा में रेगेक्स की कार्यक्षमता को दोहराने का प्रयास करते हैं।
    • PCRE — सबसे सफल कार्यान्वयन। यह पुस्तकालय सबसे व्यापक रूप से उपयोग किया जाने वाला कार्यान्वयन है। इसमें सुविधाओं का एक समृद्ध सेट है, जिनमें से कुछ को "Regular" के रूप में नहीं माना जा सकता है।
    • Python, Ruby, Java, .NET — अन्य कार्यान्वयन मैं आगे वर्णन करने का इरादा नहीं रखता हूं।

अधिक जानकारी के लिए:

यदि आप मुझे कुछ पर विस्तार करना चाहते हैं, तो एक टिप्पणी पोस्ट करें।

+0

ऐसा लगता है कि मेरे पास पोस्ट किए गए लिंक के साथ मेरे लिए कुछ काम कट गया है, लेकिन मेरा मानना ​​है कि यह वही है जो मैं ढूंढ रहा था। इससे भी आगे यदि आप एक वास्तविक पुस्तक के बारे में जानते हैं जिसे खरीदा जा सकता है, तो यह शानदार होगा। – Robb

+0

मैंने इस विषय पर कई किताबें नहीं पढ़ी हैं, लेकिन मुझे पसंद आया कि माइकल सिप्सर द्वारा "गणना की सिद्धांत का परिचय" है। यह केवल नियमित अभिव्यक्तियों के बारे में नहीं है, लेकिन ट्यूरिंग मशीनों और एनपी-पूर्णता आदि के लिए सभी तरह से जाता है। –