मैंने मार्क बेयर्स को पहले से ही एक +1 दिया है - लेकिन जहां तक मुझे याद है कि पेपर वास्तव में यह नहीं कहता है कि नियमित अभिव्यक्ति मिलान कैसे समझाता है कि एक एल्गोरिदम खराब क्यों है और दूसरा बेहतर है। शायद लिंक में कुछ?
मैं अच्छे दृष्टिकोण पर ध्यान केंद्रित करूंगा - सीमित ऑटोमाटा बनाना। यदि आप स्वयं को निर्धारित करने के लिए निर्धारिती ऑटोमाटा तक सीमित करते हैं, तो यह वास्तव में बहुत मुश्किल नहीं है।
Modern Compiler Design में लिया गया दृष्टिकोण क्या है (बहुत तेज़ी से) वर्णन करता हूं।
कल्पना कीजिए कि आप निम्नलिखित नियमित अभिव्यक्ति है ...
a (b c)* d
पत्र शाब्दिक वर्णों का मिलान करने के लिए प्रतिनिधित्व करते हैं। * सामान्य शून्य-या-अधिक पुनरावृत्ति मिलान है। मूल विचार डॉट नियमों के आधार पर राज्यों को प्राप्त करना है। राज्य शून्य हम, राज्य है जहां अभी तक कुछ नहीं मिलान किया गया है, क्योंकि ले लेंगे तो डॉट मोर्चे पर चला जाता है ...
0 : .a (b c)* d
ही संभव मैच 'एक' है, इसलिए अगले राज्य हम निकाले जाते है। ..
1 : a.(b c)* d
अब हम दो संभावनाएं है - 'बी' से मेल खाते हैं (हो, तो की 'बी सी' कम से कम एक दोहराने) या मेल खाते हैं 'प' अन्यथा। नोट - हम मूल रूप से यहां एक डिग्राफ खोज कर रहे हैं (या तो गहराई पहले या चौड़ाई पहले या जो भी हो) लेकिन हम इसे खोजते समय डिग्राफ की खोज कर रहे हैं। एक चौड़ाई वाली पहली रणनीति मानते हुए, हमें बाद में विचार करने के लिए हमारे मामलों में से एक को कतारबद्ध करने की आवश्यकता होगी, लेकिन मैं यहां से उस मुद्दे को अनदेखा कर दूंगा। वैसे भी, हमने दो नए राज्यों की खोज की है ...
2 : a (b.c)* d
3 : a (b c)* d.
राज्य 3 एक अंत राज्य है (एक से अधिक हो सकता है)। राज्य 2 के लिए, हम केवल 'सी' से मेल खाते हैं, लेकिन हमें बाद में डॉट स्थिति से सावधान रहना होगा। हमें "ए। (बी सी) * डी" मिलता है - जो राज्य 1 जैसा ही है, इसलिए हमें एक नई स्थिति की आवश्यकता नहीं है।
आईआईआरसी, आधुनिक कंपाइलर डिज़ाइन में दृष्टिकोण डॉट के हैंडलिंग को सरल बनाने के लिए, ऑपरेटर को दबाते समय एक नियम का अनुवाद करना है। राज्य 1 में तब्दील किया जाएगा ...
1 : a.b c (b c)* d
a.d
है, अपने अगले विकल्प या तो पहले पुनरावृत्ति मैच के लिए या पुनरावृत्ति को छोड़ने के लिए है। इसके अगले राज्य राज्यों 2 और 3 के बराबर हैं। इस दृष्टिकोण का एक लाभ यह है कि आप अपने सभी पिछले मैचों ('।' से पहले सब कुछ छोड़ सकते हैं) क्योंकि आप केवल भविष्य के मैचों की परवाह करते हैं। यह आम तौर पर एक छोटा राज्य मॉडल देता है (लेकिन जरूरी नहीं कि कम से कम एक)।
संपादित करें यदि आप पहले से मिलान किए गए विवरण को छोड़ देते हैं, तो आपका राज्य विवरण स्ट्रिंग्स के सेट का प्रतिनिधित्व है जो इस बिंदु से हो सकता है।
अमूर्त बीजगणित के संदर्भ में, यह एक प्रकार का सेट बंद है। एक बीजगणित मूल रूप से एक (या अधिक) ऑपरेटरों के साथ एक सेट है। हमारा सेट राज्य के विवरणों का है, और हमारे ऑपरेटर हमारे संक्रमण (चरित्र मिलान) हैं। एक बंद सेट वह है जहां सेट में किसी भी सदस्य को कोई भी ऑपरेटर लागू करना हमेशा सेट में मौजूद एक अन्य सदस्य का उत्पादन करता है। एक सेट को बंद करना सबसे बड़ा सेट है जो बंद है। तो मूल रूप से, स्पष्ट प्रारंभ स्थिति से शुरू होने पर, हम उन राज्यों के न्यूनतम सेट का निर्माण कर रहे हैं जो संक्रमण ऑपरेटर के हमारे सेट के सापेक्ष बंद हैं - पहुंचने योग्य राज्यों का न्यूनतम सेट।
यहां न्यूनतम बंद प्रक्रिया को संदर्भित करता है - वहां एक छोटा समकक्ष ऑटोमाटा हो सकता है जिसे सामान्य रूप से न्यूनतम कहा जाता है।
इस मूल विचार को ध्यान में रखते हुए, यह कहना मुश्किल नहीं है कि "अगर मेरे पास स्ट्रिंग के दो सेट का प्रतिनिधित्व करने वाली दो राज्य मशीनें हैं, तो मैं संघ का प्रतिनिधित्व करने वाले तीसरे को कैसे प्राप्त करूं" (या चौराहे, या सेट अंतर ...)। बिंदीदार नियमों के बजाय, आपके राज्य के प्रतिनिधित्व प्रत्येक इनपुट automaton और शायद अतिरिक्त विवरण से वर्तमान स्थिति (या मौजूदा राज्यों का सेट) होगा।
यदि आपके नियमित व्याकरण जटिल हो रहे हैं, तो आप कम कर सकते हैं। यहां मूल विचार अपेक्षाकृत सरल है। आप अपने सभी राज्यों को एक समकक्ष वर्ग या "ब्लॉक" में समूहित करते हैं। फिर आप बार-बार परीक्षण करते हैं कि किसी विशेष संक्रमण प्रकार के संबंध में आपको ब्लॉक को विभाजित करने की आवश्यकता है (राज्य वास्तव में समकक्ष नहीं हैं)। यदि किसी विशेष ब्लॉक में सभी राज्य एक ही चरित्र के एक मैच को स्वीकार कर सकते हैं और ऐसा करने में, उसी अगली-ब्लॉक तक पहुंचें, तो वे बराबर हैं।
होपक्रॉफ्ट्स एल्गोरिदम इस मूल विचार को संभालने का एक प्रभावी तरीका है।
न्यूनतमकरण के बारे में एक विशेष रूप से दिलचस्प बात यह है कि प्रत्येक निर्धारिती परिमित automaton का एक न्यूनतम रूप है। इसके अलावा, होपक्रॉफ्ट्स एल्गोरिदम उस न्यूनतम रूप के समान प्रतिनिधित्व का उत्पादन करेगा, इससे कोई फर्क नहीं पड़ता कि यह किस बड़े मामले से शुरू हुआ था। यही है, यह एक "कैननिकल" प्रतिनिधित्व है जिसका उपयोग हैश प्राप्त करने के लिए किया जा सकता है या मनमानी-लेकिन-लगातार क्रम के लिए किया जा सकता है। इसका अर्थ यह है कि आप कंटेनरों में कुंजियों के रूप में न्यूनतम automata का उपयोग कर सकते हैं।
उपरोक्त शायद थोड़ा सा मैला डब्लूआरटी परिभाषा है, इसलिए सुनिश्चित करें कि आप स्वयं का उपयोग करने से पहले किसी भी शब्द को स्वयं देखते हैं, लेकिन कुछ भाग्य के साथ यह बुनियादी विचारों के लिए एक त्वरित त्वरित परिचय देता है।
बीटीडब्ल्यू - शेष Dick Grunes site के आसपास एक नज़र डालें - उसके पास पार्सिंग तकनीकों पर एक मुफ्त पीडीएफ पुस्तक है। मॉडर्न कंपाइलर डिज़ाइन का पहला संस्करण बहुत अच्छा आईएमओ है, लेकिन जैसा कि आप देखेंगे, दूसरा संस्करण आसन्न है।
+1 दिलचस्प विचार। यदि आप इसे प्राप्त करते हैं तो आप रेगेक्स में विशेषज्ञ होंगे;) –
[रोचक] (http://www.codeproject.com/KB/recipes/OwnRegExpressionsParser.aspx#Seven) एक सरलीकृत आरई पार्सर बनाने के तरीके पर आलेख नहीं (नहीं हालांकि पाइथन संबंधित) – systempuntoout
http://perl.plover.com/Regex/article.html ऑटोटाटा का उपयोग कर रेगेक्स इंजन का एक स्पष्टीकरण है। आप यहां एक सरल परियोजना पर भी विचार करना चाहेंगे जो कुछ समय पहले उठाया गया था, जो एक रेगेक्स-टू-इंग्लिश अनुवादक लिखना है। उदाहरण के लिए, '(foo | bar) (baz) +' को 'या तो "foo" या बार "फिर एक या अधिक" baz "में अनुवाद करना चाहिए। पाइपर्सिंग (http://pyparsing.wikispaces.com/Documentation) मदद कर सकता है इसके साथ। – katrielalex