🤾🏿 🏵️ 🔪 एलएल पार्सिंग के बारे में: स्ट्रिंग कटिंग की अवधारणा के माध्यम से पार्सिंग के लिए दृष्टिकोण 🤲🏻 💻 📜

प्रतिष्ठित समुदाय को बधाई!

पुनरावृत्ति सीखने की मां है, और किसी भी प्रोग्रामर के लिए पार्सिंग समझना एक बहुत ही उपयोगी कौशल है, इसलिए मैं इस विषय को फिर से उठाना चाहता हूं और बहुत अधिक औपचारिकता किए बिना पुनरावर्ती वंश (एलएल) विश्लेषण के बारे में बात करना चाहता हूं (आप हमेशा उन्हें बाद में कर सकते हैं) लौट आओ)।

जैसा कि महान डी। स्ट्रोगोव लिखते हैं, "समझने के लिए सरल करना है।" इसलिए, पुनरावर्ती वंश विधि (उर्फ एलएल-पार्सिंग) का उपयोग करके पार्सिंग की अवधारणा को समझने के लिए, हम यथासंभव कार्य को सरल करते हैं और मैन्युअल रूप से JSON के समान एक प्रारूप का पार्सर लिखते हैं, लेकिन सरल (यदि आप चाहें, तो आप इसे पूर्ण-पूर्ण JSON पार्सर में विस्तार कर सकते हैं) व्यायाम करना चाहते हैं)। आइए इसे लिखें, स्ट्रिंग को काटने के विचार के रूप में।

क्लासिक पुस्तकों और संकलक डिजाइन पाठ्यक्रमों में, वे आमतौर पर पार्सिंग और व्याख्या के विषय की व्याख्या करना शुरू करते हैं, कई चरणों पर प्रकाश डालते हैं:

लेक्सिकल विश्लेषण: स्रोत टेक्स्ट को सब्सट्रिंग (टोकन, या टोकन) की एक सरणी में विभाजित करना
पार्सिंग: टोकन की एक सरणी से एक पार्सिंग पेड़ का निर्माण
व्याख्या (या संकलन): परिणामी पेड़ को वांछित (प्रत्यक्ष या रिवर्स) क्रम में ट्रेस करना और इस ट्रैवर्सल के कुछ चरणों में कुछ व्याख्या या कोड जनरेशन क्रियाएं करना

वास्तव में ऐसा नहीं है

क्योंकि पार्सिंग की प्रक्रिया में हमें पहले से ही चरणों का एक अनुक्रम मिलता है, जो कि पेड़ के नोड्स की यात्राओं का एक क्रम है, स्पष्ट रूप में पेड़ खुद मौजूद नहीं हो सकता है, लेकिन हम अभी तक गहराई में नहीं जाएंगे। जो लोग गहराई में जाना चाहते हैं, उनके लिए अंत में लिंक हैं।

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

चलो एक सरल कार्य के साथ शुरू करते हैं: सीमांकक के साथ एक पंक्ति है, और मैं इसके मूल्यों पर एक पुनरावृति लिखना चाहता हूं। कुछ इस तरह:

String names = "ivanov;petrov;sidorov"; for (String name in names) { echo("Hello, " + name); }

यह कैसे किया जा सकता है? मानक तरीका है कि सीमांकित स्ट्रिंग को सरणी या सूची में String.split (जावा में), या name.split (",") (जावास्क्रिप्ट में) का उपयोग करके परिवर्तित किया जाए, और पहले से ही सरणी के माध्यम से पुनरावृत्त करें। लेकिन कल्पना करें कि हम किसी सरणी में रूपांतरण का उपयोग नहीं कर सकते हैं या नहीं कर सकते हैं (उदाहरण के लिए, अच्छी तरह से, अगर हम AVAJ ++ प्रोग्रामिंग भाषा में प्रोग्राम करते हैं, जिसमें "सरणी" डेटा संरचना नहीं है)। आप अभी भी स्ट्रिंग को स्कैन कर सकते हैं और सीमांकक को ट्रैक कर सकते हैं, लेकिन मैं इस विधि का उपयोग नहीं करूंगा, क्योंकि यह पुनरावृत्ति लूप कोड को बोझिल बनाता है और, सबसे महत्वपूर्ण बात, यह उस अवधारणा के खिलाफ जाता है जिसे मैं दिखाना चाहता हूं। इसलिए, हम कार्यात्मक प्रोग्रामिंग में सूचियों से संबंधित उसी तरह एक सीमांकित स्ट्रिंग से संबंधित होंगे। और वहां वे हमेशा फ़ंक्शन हेड (सूची का पहला तत्व प्राप्त करते हैं) और पूंछ (बाकी सूची प्राप्त करें) को परिभाषित करते हैं। लिस्प की पहली बोलियों से शुरू, जहां इन कार्यों को बिल्कुल भयावह और गैर-सहज रूप से कहा जाता था: कार और सीडीआर (कार = पता रजिस्टर की सामग्री, सीडीआर = वेतन वृद्धि रजिस्टर की सामग्री। पुराने की किंवदंतियां गहरी हैं, हां, एहेह।)।

हमारी लाइन एक सीमांकित रेखा है। बैंगनी में डिवाइडर को हाइलाइट करें:

और सूची की वस्तुओं को पीले रंग में हाइलाइट करें:

हम मानते हैं कि हमारी रेखा परिवर्तनशील है (इसे बदला जा सकता है) और एक फ़ंक्शन लिखें:

उनके हस्ताक्षर, उदाहरण के लिए, हो सकते हैं:

 public boolean cutNextToken(StringBuilder svList, String separator, StringBuilder token)

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

परिणामस्वरूप, हमें इस तरह लिखने का अवसर मिला:

 StringBuilder names = new StringBuilder("ivanov;petrov;sidorov"); StringBuilder name = new StringBuilder(); while(cutNextToken(names, ";", name)) { System.out.println(name); }

उम्मीद के मुताबिक आउटपुट:

इवानोव
पेत्रोव
Sidorov

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

अब आइए कुछ अधिक दिलचस्प बनाएं: कुंजी-मूल्य जोड़े की एक सूची। यह भी एक बहुत ही सामान्य कार्य है।

 StringBuilder pairs = new StringBuilder("name=ivan;surname=ivanov;middlename=ivanovich"); StringBuilder pair = new StringBuilder(); while (cutNextToken(pairs, ";", pair)) { StringBuilder paramName = new StringBuilder(); StringBuilder paramValue = new StringBuilder(); cutNextToken(pair, "=", paramName); cutNextToken(pair, "=", paramValue); System.out.println("param with name \"" + paramName + "\" has value of \"" + paramValue + "\""); }

निष्कर्ष:

 param with name "name" has value of "ivan" param with name "surname" has value of "ivanov" param with name "middlename" has value of "ivanovich"

उम्मीद भी की गई। और रेखाओं को काटे बिना String.split के साथ एक ही चीज हासिल की जा सकती है।
लेकिन हम कहते हैं कि अब हम अपने प्रारूप को जटिल बनाना चाहते थे और फ्लैट कुंजी-मूल्य से जेन्सन की याद दिलाने वाले एक नेस्टेबल प्रारूप में चले जाते थे। अब हम कुछ इस तरह पढ़ना चाहते हैं:

 {'name':'ivan','surname':'ivanov','birthdate':{'year':'1984','month':'october','day':'06'}}

क्या विभाजक विभाजित करते हैं? यदि यह अल्पविराम है, तो एक टोकन में हमारे पास लाइन होगी

 'birthdate':{'year':'1984'

जाहिर है कि हमें क्या चाहिए। इसलिए, हमें उस पंक्ति की संरचना पर ध्यान देना चाहिए जिसे हम पार्स करना चाहते हैं।

यह एक घुंघराले ब्रेस के साथ शुरू होता है और एक घुंघराले ब्रेस के साथ समाप्त होता है (इसे जोड़ा जाता है, जो महत्वपूर्ण है)। इन कोष्ठकों के अंदर 'कुंजी': 'वैल्यू' जोड़े की एक सूची है, प्रत्येक जोड़ी को अगले जोड़े से अल्पविराम द्वारा अलग किया जाता है। कुंजी और मूल्य एक बृहदान्त्र द्वारा अलग किए जाते हैं। एक कुंजी एपोस्ट्रोफिस में संलग्न अक्षरों की एक स्ट्रिंग है। मूल्य एपोस्ट्रोफ्स में संलग्न वर्णों की एक स्ट्रिंग हो सकता है, या यह एक ही संरचना हो सकता है, शुरुआत और जोड़ी वाले घुंघराले ब्रेसिज़ के साथ समाप्त हो सकता है। हम इस तरह की संरचना को "ऑब्जेक्ट" शब्द कहते हैं, जैसा कि JSON में इसे कॉल करने के लिए प्रथागत है।

हमने अनौपचारिक रूप से हमारे JSON जैसे प्रारूप के व्याकरण का वर्णन किया है। आमतौर पर, व्याकरणों को औपचारिक रूप में, रिवर्स और बीएनएफ संकेतन या इसके रूपांतरों को लिखने के लिए उपयोग किया जाता है। लेकिन अब मैं इसके बिना कर सकता हूं, और हम सिर्फ यह देखेंगे कि आप इस लाइन को कैसे "काट" सकते हैं ताकि इसे इस व्याकरण के नियमों के अनुसार पार्स किया जा सके।

वास्तव में, हमारा "ऑब्जेक्ट" एक शुरुआती घुंघराले ब्रेस के साथ शुरू होता है और एक जोड़ी के साथ समाप्त होता है जो इसे बंद कर देता है। इस तरह के प्रारूप को पार्स करने वाले एक फ़ंक्शन क्या कर सकता है? सबसे अधिक संभावना है, निम्नलिखित:

सत्यापित करें कि पारित स्ट्रिंग एक उद्घाटन ब्रेस के साथ शुरू होता है
सत्यापित करें कि पारित स्ट्रिंग समापन ब्रेसिज़ की एक जोड़ी के साथ समाप्त होती है
यदि दोनों स्थितियां सत्य हैं, तो उद्घाटन और समापन कोष्ठक काट दें, और जो बचा है, उस फ़ंक्शन को पास करें जो जोड़े की कुंजी को सूचीबद्ध करता है: 'मान'

कृपया ध्यान दें: "फ़ंक्शन इस प्रारूप को पार्स करने वाले" और "जोड़े की कुंजी की सूची को पार्स करने वाले फ़ंक्शन: 'वैल्यू'" दिखाई दिए। हमारे पास दो विशेषताएं हैं! ये बहुत ही कार्य हैं कि पुनरावर्ती वंश एल्गोरिथ्म के शास्त्रीय विवरण में "गैर-प्रतीक प्रतीकों के पार्सिंग फ़ंक्शन" कहा जाता है, और जो कहते हैं कि "प्रत्येक गैर-प्रतीक चिह्न के लिए, अपना स्वयं का पार्सिंग फ़ंक्शन बनाया जाता है"। जो, वास्तव में, इसे पार्स करता है। हम उन्हें नाम दे सकते हैं, कह सकते हैं, parseJsonObject और parseJsonPairList।

इसके अलावा अब हमें ध्यान देने की जरूरत है कि हमें "विभाजक" की अवधारणा के अलावा "जोड़ी ब्रैकेट" की अवधारणा मिल गई है। यदि अगले विभाजक (एक कुंजी और मूल्य के बीच एक कॉलन, "कुंजी: मान" जोड़े के बीच एक अल्पविराम) के लिए एक रेखा को काटने के लिए cutNextToken फ़ंक्शन हमारे लिए पर्याप्त था, अब हम न केवल एक स्ट्रिंग का उपयोग कर सकते हैं, बल्कि एक वस्तु भी, हमें चाहिए समारोह "कोष्ठक की अगली जोड़ी के लिए कट"। कुछ इस तरह:

यह फ़ंक्शन खुलने वाले ब्रैकेट से पंक्ति से एक टुकड़ा काटता है जो इसे बंद करता है, कोष्ठक को दिया जाता है, यदि कोई हो। बेशक, आप कोष्ठक तक सीमित नहीं हो सकते हैं, लेकिन विभिन्न ब्लॉक संरचनाओं को काटने के लिए एक समान फ़ंक्शन का उपयोग करें जो कि नेस्टेड हो सकते हैं: ऑपरेटर ब्लॉक शुरू होते हैं..तो, if..endif, for..endfor और इसी तरह के अन्य।

चलो रेखांकन ड्रा करें स्ट्रिंग का क्या होगा। फ़िरोज़ा रंग - इसका मतलब है कि हम फ़िरोज़ा में उजागर प्रतीक के आगे की रेखा को यह निर्धारित करने के लिए स्कैन करते हैं कि हमें आगे क्या करना चाहिए। वायलेट "क्या काट दिया जाता है, यह तब होता है जब हम लाइन से वायलेट में हाइलाइट किए गए टुकड़ों को काटते हैं, और जो आगे रहता है उसे पार्स करना जारी रखता है।

तुलना के लिए, प्रोग्राम का आउटपुट (प्रोग्राम टेक्स्ट परिशिष्ट में दिया गया है) जो इस लाइन को पार्स करता है:

JSON जैसी संरचना को पार्स करने का प्रदर्शन

 ok, about to parse JSON object {'name':'ivan','surname':'ivanov','birthdate':{'year':'1984','month':'october','day':'06'}} ok, about to parse pair list 'name':'ivan','surname':'ivanov','birthdate':{'year':'1984','month':'october','day':'06'} found KEY: 'name' found VALUE of type STRING:'ivan' ok, about to parse pair list 'surname':'ivanov','birthdate':{'year':'1984','month':'october','day':'06'} found KEY: 'surname' found VALUE of type STRING:'ivanov' ok, about to parse pair list 'birthdate':{'year':'1984','month':'october','day':'06'} found KEY: 'birthdate' found VALUE of type OBJECT:{'year':'1984','month':'october','day':'06'} ok, about to parse JSON object {'year':'1984','month':'october','day':'06'} ok, about to parse pair list 'year':'1984','month':'october','day':'06' found KEY: 'year' found VALUE of type STRING:'1984' ok, about to parse pair list 'month':'october','day':'06' found KEY: 'month' found VALUE of type STRING:'october' ok, about to parse pair list 'day':'06' found KEY: 'day' found VALUE of type STRING:'06'

किसी भी समय, हम जानते हैं कि हम अपनी इनपुट लाइन में क्या खोजने की उम्मीद करते हैं। यदि हमने parJJsonObject फ़ंक्शन में प्रवेश किया है, तो हम उम्मीद करते हैं कि ऑब्जेक्ट हमारे पास वहां गया था, और हम शुरुआत और अंत में उद्घाटन और समापन कोष्ठक की उपस्थिति से इसकी जांच कर सकते हैं। यदि हम parseJsonPairList फ़ंक्शन में प्रवेश करते हैं, तो हम "कुंजी: मान" जोड़े की एक सूची की उम्मीद करते हैं, और उसके बाद हम "बिट" कुंजी (":" विभाजक से पहले), हम उम्मीद करते हैं कि अगली चीज़ हम "बंद" है मूल्य। हम मूल्य के पहले वर्ण को देख सकते हैं, और इसके प्रकार के बारे में एक निष्कर्ष निकाल सकते हैं (यदि एपोस्ट्रोफ है, तो मान "स्ट्रिंग" प्रकार का है, यदि उद्घाटन घुंघराले ब्रैकेट मूल्य "ऑब्जेक्ट" प्रकार का है)।

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

यहाँ। आने वाली गर्मियों में सभी को बधाई और आपको शुभकामनाएं, प्यार और कार्यात्मक प्यार :)

आगे पढ़ने के लिए:

वैचारिक: स्टीव Yeegge द्वारा लंबे समय तक पढ़ने लायक लेखों की एक जोड़ी:

समृद्ध प्रोग्रामर भोजन

वहाँ से उद्धरण के एक जोड़े:

आप या तो कंपाइलर सीखते हैं और अपने खुद के डीएसएल लिखना शुरू करते हैं, या अपने आप को एक बेहतर भाषा बनाते हैं

संकलन पाइपलाइन का पहला बड़ा चरण पार्सिंग है

पिनोच्चियो समस्या

वहां से बोली:

टाइप कास्ट, संकीर्णता और चौड़ीकरण, मानक कक्षा की सुरक्षा को बायपास करने के लिए फ्रेंड फ़ंक्शंस, स्ट्रिंग में मिनिलंगुज को भरकर और हाथ से उन्हें पार्स करने के लिए , जावा और सी ++ में टाइप सिस्टम को बायपास करने के दर्जनों तरीके हैं, और प्रोग्रामर हर समय उनका उपयोग करते हैं। , क्योंकि (थोड़ा वे जानते हैं) वे वास्तव में सॉफ्टवेयर बनाने की कोशिश कर रहे हैं, हार्डवेयर नहीं।

तकनीकी: एलएल और एलआर दृष्टिकोण के बीच अंतर के बारे में दो लेख:
एलएल और एलआर पार्सिंग डेमिस्टिफायड
संदर्भ में एलएल और एलआर: पारसिंग टूल्स हार्ड क्यों हैं

और विषय में और भी गहरा: C ++ में एक लिस्प इंटरप्रिटर कैसे लिखें
C ++ की 90 लाइनों में लिस्प दुभाषिया

आवेदन। उदाहरण कोड (जावा) जो लेख में वर्णित विश्लेषक को लागू करता है:

 package demoll; public class DemoLL { public boolean cutNextToken(StringBuilder svList, String separator, StringBuilder token) { String s = svList.toString(); if (s.trim().isEmpty()){ return false; } int sepIndex = s.indexOf(separator); if (sepIndex == -1) { //   ,    token.setLength(0); token.append(s); svList.setLength(0); } else { String t = s.substring(0, sepIndex); String restOfString = s.substring(sepIndex + separator.length(), s.length()); svList.setLength(0); svList.append(restOfString); token.setLength(0); token.append(t); } return true; } // "{hello world}:again" -> "{hello world}", ":again" //"{'year':'1980','month':'october','day':'06'},'key1':'value1','key2':'value2'" -> "{'year':'1980','month':'october','day':'06'}", ",'key1':'value1','key2':'value2'" public void cutTillMatchingParen(StringBuilder sbSrc, String openParen, String closeParen, StringBuilder matchPart){ String src = sbSrc.toString(); matchPart.setLength(0); int openParenCount = 0; String state = "not_copying"; for (int i = 0; i < src.length(); i++){ String cs = String.valueOf(src.charAt(i)); // cs - current symbol if (state.equals("not_copying")){ if (cs.equals(openParen)) { state = "copying"; } } if (state.equals("copying")){ matchPart.append(cs); if (cs.equals(openParen)){ openParenCount = openParenCount + 1; } if (cs.equals(closeParen)) { openParenCount = openParenCount - 1; } if (openParenCount == 0) { break; } } } sbSrc.setLength(0); sbSrc.append(src.substring(matchPart.length(), src.length())); } public void parseJsonObject(String s) { System.out.println("ok, about to parse JSON object " + s); if (s.charAt(0) == '{' && s.charAt(s.length() - 1) == '}') { String pairList = s.substring(1, s.length() - 1).trim(); parseJsonPairList(pairList); } else { System.out.println("Syntax error: not a JSON object. Must start with { and end with }"); } } public void parseJsonPairList(String pairList) { pairList = pairList.trim(); if (pairList.isEmpty()) { //System.out.println("pairList is empty"); return; } System.out.println("ok, about to parse pair list " + pairList); if (pairList.charAt(0) != '\'') { System.out.println("syntax error: key must be of type STRING, input: + pairList"); return; } StringBuilder key = new StringBuilder(); StringBuilder sbPairList = new StringBuilder(pairList); this.cutNextToken(sbPairList, ":", key); // sbPairList  ,   "name":"ivan"...,   "ivan"... System.out.println("found KEY: " + key); // checking type of value - may be String or Object StringBuilder value = new StringBuilder(); if (sbPairList.charAt(0) == '{') { cutTillMatchingParen(sbPairList, "{", "}", value); System.out.println("found VALUE of type OBJECT:" + value); parseJsonObject(value.toString()); StringBuilder emptyString = new StringBuilder(); cutNextToken(sbPairList, ",", emptyString); } else if (sbPairList.charAt(0) == '\'') { this.cutNextToken(sbPairList, ",", value); System.out.println("found VALUE of type STRING:" + value); } else { System.out.println("syntax error: VALUE must be either STRING or OBJECT"); return; } parseJsonPairList(sbPairList.toString()); } public static void main(String[] args){ DemoLL d = new DemoLL(); System.out.println("   \"=\""); StringBuilder pairs = new StringBuilder("name=ivan;surname=ivanov;middlename=ivanovich"); StringBuilder pair = new StringBuilder(); while (d.cutNextToken(pairs, ";", pair)) { StringBuilder paramName = new StringBuilder(); StringBuilder paramValue = new StringBuilder(); d.cutNextToken(pair, "=", paramName); d.cutNextToken(pair, "=", paramValue); System.out.println("param with name \"" + paramName + "\" has value of \"" + paramValue + "\""); } System.out.println("  JSON- "); String s = "{'name':'ivan','surname':'ivanov','birthdate':{'year':'1984','month':'october','day':'06'}}"; d.parseJsonObject(s); } }

एलएल पार्सिंग के बारे में: स्ट्रिंग कटिंग की अवधारणा के माध्यम से पार्सिंग के लिए दृष्टिकोण

More articles: