HTTP अनुरोध को पार्स करने के लिए एक राज्य मशीन बनाना

इनपुट अनुक्रम को पार्स करने के लिए एक बहुत तेज़ तरीके को लागू करने के लिए एक नियतात्मक परिमित राज्य मशीन का उपयोग किया जा सकता है। यह इनपुट अनुक्रम में केवल एक पास लेता है, और प्रत्येक चरण में न्यूनतम क्रियाएं करता है। दुर्भाग्य से, इस मॉडल की सीमाएं हैं - मौजूदा Nondeterministic परिमित राज्य मशीन (नियमित अभिव्यक्ति, व्याकरण) के लिए DFA का निर्माण करना हमेशा संभव नहीं होता है। या यहां तक ​​कि अगर यह निर्माण करना संभव है, तो एक ऑटोमेटन में बहुत सारे राज्य हो सकते हैं।

फिर भी, मैंने DCA के आधार पर HTTP अनुरोध के लिए एक पार्सर बनाने का प्रयास करने का निर्णय लिया। मुख्य कार्य केवल HTTP अनुरोध की शुद्धता की जांच करना नहीं है, बल्कि इनपुट लाइन में उन तत्वों का चयन करना है जो HTTP अनुरोध फ़ील्ड के कुछ मूल्यों के अनुरूप हैं। बीएनएफ नियमों (आरएसीसी 2616 में बिखरे हुए) से एक ऑटोमेटन उत्पन्न किया जाना चाहिए। सब कुछ C # में लागू किया गया है, आउटपुट मशीन C # में भी है। हालांकि यह स्पष्ट है कि जब मशीन किसी भी भाषा में इसे तैयार करने के लिए तैयार है, किसी भी रूप में कोई समस्या नहीं है।

DFA उत्पन्न करने के लिए निम्नलिखित श्रृंखलाओं को कार्यान्वित किया जाता है:
1. बीएनएफ नियमों का विश्लेषण
2. उनके आधार पर एनसीए का निर्माण
3. NKA को DKA में बदलें
4. डीकेए का न्यूनतमकरण
5. स्रोत पाठ और रूपांतरण तालिका के साथ फाइलें बनाना

मैंने बीएनएफ व्याकरण को पार्स करने के लिए आयरनरी का उपयोग किया, आरएफसी 5234 में एबीएनएफ व्याकरण का अच्छी तरह से वर्णन किया गया है। वाक्यविन्यास वृक्ष के अनुसार, कार्यक्रम थॉमसन के नियमों के अनुसार एनकेए का निर्माण करता है। एनएफए को डीएफए में बदलने और इसे कम से कम करने के लिए मानक एल्गोरिदम का उपयोग किया गया था; मैं उनका वर्णन नहीं करूंगा।

चूंकि HTTP संदेश एक अपेक्षाकृत सरल वस्तु है, इसलिए parser का आउटपुट एक वर्ग है (यह पर्याप्त है), HTTP सर्वर के अनुरूप फ़ील्ड के साथ। पारित होने के दौरान संदेश को पार्स करने के लिए मशीन के लिए, कक्षा चर को संशोधित करने वाली सरल क्रियाएं पीढ़ी के दौरान डीसीए में आवश्यक राज्यों में जोड़ी जाती हैं। उदाहरण के लिए, आपको होस्ट हेडर का मान प्राप्त करने की आवश्यकता है, कक्षा में हेडर की शुरुआत और अंत दो चर हैं। मशीन के होस्ट फ़ील्ड के मान से जाने पर ट्रिगर होने वाले राज्यों में, इन चरों को बदलने के लिए क्रियाएं जोड़ी जाती हैं। डीकेए में, यह निर्धारित करना असंभव है कि व्यवहार में किस राज्य के लिए जिम्मेदार है। इसलिए, NKA बनाते समय राज्यों को चिह्नित किया जाता है, और फिर ये लेबल ऑटोमेटन के सभी परिवर्तनों के साथ सहेजे जाते हैं। राज्यों के अंकन और कार्यों के उद्देश्य को सरल बनाने के लिए, एक सरल भाषा बनाई गई थी जिसमें चर के नाम निर्धारित किए गए हैं और वे कौन से मूल्य प्राप्त करेंगे। इस डेटा के आधार पर, एक वर्ग उत्पन्न होता है जिसमें पार्सर कार्य का परिणाम डालता है।

एक समान दृष्टिकोण का उपयोग नियमित अभिव्यक्तियों में किया जाता है (हालांकि सभी कार्यान्वयन डीसीए में रूपांतरण नहीं करते हैं)। लेकिन मशीन तक सीधी पहुंच होने पर, कई दिलचस्प अनुकूलन करना संभव है। उदाहरण के लिए, सामग्री-लेनिंग फ़ील्ड में संदेश निकाय की लंबाई होती है; इस फ़ील्ड के लिए, संख्या में रूपांतरण सीधे मशीन में होता है; आउटपुट पर, हमारे पास इंट कंटेंटलेन्थ क्लास का एक क्षेत्र होता है। एक और दिलचस्प अनुकूलन, उदाहरण के लिए, HTTP अनुरोध के लिए तरीकों का एक सेट (GET, HOST ...) परिभाषित किया गया है। पार्सर के आउटपुट पर, आप तुरंत विधि के अनुरूप स्थिरांक प्राप्त कर सकते हैं। और यह सब एक पास में।

यह भी बहुत महत्वपूर्ण है कि पार्सर इनपुट के रूप में बाइट्स की एक सरणी को स्वीकार करता है, यह विशेष रूप से सी # जैसी आधुनिक भाषाओं के लिए सच है, जहां एक स्ट्रिंग बाइट्स की एक सी + + के रूप में नहीं है, और आप यहां सरल संकेतक के साथ नहीं कर सकते।

सामान्य तौर पर, सिस्टम इस प्रकार है। एक BNF व्याकरण है, और उस वर्ग का विवरण है जिसे हम आउटपुट पर प्राप्त करना चाहते हैं। यह सब जनरेटर के इनपुट को खिलाया जाता है, और हम सी # में डीएफए प्राप्त करते हैं। एक तैयार मशीन के साथ, आप निम्नानुसार काम कर सकते हैं:

dfa.SetDefaultValue();
dfa.Parse(message0, 0, message0.Length);
dfa.SetArray(message0);

Console.WriteLine("Method: {0}", dfa.Method);
Console.WriteLine("Request-URI: |{0}|", dfa.RequestUri.ToString());
Console.WriteLine("Host: |{0}|", dfa.Host.ToString());
Console.WriteLine("Content-Type: |{0}|", dfa.ContentType.Value.ToString());
Console.WriteLine("Content-Length: {0}", dfa.ContentLength);
Console.WriteLine("Referer: |{0}|", dfa.Referer.ToString());


व्यवहार में, एक HTTP अनुरोध के लिए डीकेए में 1K-2K के बाद 150K राज्यों को कम करने के लिए होता है। यह स्पष्ट है, सबसे पहले, कि वास्तविक उपयोग के लिए 1K-2K काफी स्वीकार्य है। दूसरे, यह 150K बताता है, इसकी गणना के लिए कुछ मेमोरी और समय की आवश्यकता होती है (कम से कम मेरे कार्यान्वयन में) - मिनट x-tsat।

पार्सर की गति बहुत अधिक है, इस दृष्टिकोण के लिए एक औपचारिक मोटा अनुमान ~ * O (n) है, और संभवतः इसे मौलिक रूप से सुधारना मुश्किल है। वास्तव में, मेरी मशीन पर C # में पार्सर 3.3 सेकंड में 1M लंबाई में 220 बाइट्स के संदेश को पार्स करने में कामयाब रहा।

परियोजना के लिए स्रोत कोड उपलब्ध है: code.google.com/p/siprevo

मैंने जनरेटर के आउटपुट पर कोड को सटीक बनाने की कोशिश की, लेकिन मसौदा प्रारूप में जनरेटर स्वयं थोड़ा (कम से कम कहने के लिए) था। यह अच्छा है (बस डिबगिंग के दौरान नहीं) कि इस तरह की प्रणाली शायद ही थोड़ा गड़बड़ कर सकती है, यह या तो काम करती है या काम नहीं करती है, इस मामले में यह काम करता है।

अद्यतन: मशीन का "संकलक" एक अलग उपयोगिता के रूप में यहां रहता है ।