LALR (1) पार्सर्स के लिए एक कंपाइलर लिखना। मूल सिद्धांत

परिचय, या पार्सर की आवश्यकता क्यों है

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

यह हिस्सा कंप्यूटर विज्ञान के सामान्य सिद्धांत, आधार को समर्पित है। यह संभव है कि यह रूस में स्कूलों / विश्वविद्यालयों में भी पढ़ाया जाता है। मांस खुद दूसरे भाग से जाएगा।

तो, किसी को एक पार्सर लिखने की आवश्यकता क्यों होगी, और यह सब क्या है? एक पार्सर एक कोड है जो एक आने वाले चरित्र सेट अर्थ अर्थ देता है। यही है, इन प्रतीकों का एक विश्लेषण होता है, और इस विश्लेषण के आधार पर, कार्यक्रम समझता है कि इन अक्षरों और संख्याओं की व्याख्या कैसे की जाए। एक सरल उदाहरण "1 + 2" है, पार्सिंग प्रक्रिया के बाद या उसके दौरान, "+" चिन्ह सिर्फ एक प्लस प्रतीक नहीं है, बल्कि बाइनरी एडिशन ऑपरेटर का पदनाम है, और "+3" में यह संख्या चिह्न का एकरी संचालक है। यह ज्यादातर लोगों के लिए स्पष्ट है, लेकिन कार के लिए नहीं।

पार्सर्स का उपयोग हर जगह किया जाता है - Word'e में अनुप्रयोगों, शब्द रूपों, सूत्रों आदि के विश्लेषण के लिए; इनपुट डेटा को मान्य करते समय लगभग किसी भी वेबसाइट पर: ईमेल, फोन नंबर, क्रेडिट कार्ड नंबर; कॉन्फ़िगरेशन फ़ाइलें; क्रमबद्ध डेटा (जैसे xml में); कई खेलों में - स्क्रिप्ट क्लिप, एआई स्क्रिप्ट, कंसोल। सामान्य तौर पर, यह कंप्यूटर विज्ञान का एक अभिन्न अंग है।

दो प्रकार के पार्सर्स

ठीक है, इस तकनीक के महत्व को महसूस करने के बाद, कार्यक्रमों के इस वर्ग के लिए लेखन मानकों के सवाल को उठाना आवश्यक है।

अपेक्षाकृत बोलने वाले, पार्सर को दो प्रकारों में विभाजित किया जा सकता है: वे जो औपचारिक भाषा विवरण का उपयोग करते हैं और जिन्हें एक सार डेटा योजना के बिना सीधे कोड में एम्बेड किया जाता है।

पहले दृष्टिकोण का अर्थ है विश्लेषक को दो भागों में विभाजित करना - इनपुट जानकारी और तर्क के प्रारूप / योजना का विवरण, जो अब स्वच्छ डेटा स्ट्रीम के साथ नहीं बल्कि योजना के अनुसार संरचित होता है। एक उदाहरण:

scheme: DIGIT = '0'..'9' ADD = DIGIT '+' DIGIT SIGN = ('+' | '-') DIGIT EXPR = ADD | SIGN code: long result = 0; ParseNode & expr = Parse(input); ParseNode & oper = expr.child() switch (oper.type) { // 0: DIGIT, 1: '+', 2: DIGIT case ADD: result = oper.child(0) + oper.child(2); break; // 0: '+' or '-', 1: DIGIT case SIGN: result = oper.child(0) == '-' ? - oper.child(1) : oper.child(1); break; } 

दूसरा दृष्टिकोण समझाने की तुलना में दिखाना आसान है:

  char c = ''; long result = 0; input >> c; // we have three variants of first symbol switch (c) { case '+': // next symbol is digit input >> c; if (c < '0' || c > '9') return SyntaxError; result = c - '0'; break; case '-': // next symbol is digit input >> c; if (c < '0' || c > '9') return SyntaxError; result = c - '0'; break; default: if (c < '0' || c > '9') return SyntaxError; result = c - '0'; input >> c; if (c != '+') return SyntaxError; input >> c; if (c < '0' || c > '9') return SyntaxError; result += (c - '0'); break; } 

सिद्धांत रूप में, इस उदाहरण से यह निष्कर्ष निकालना पहले से ही संभव है कि कौन सा तरीका बेहतर है, लेकिन मैं अभी भी प्रत्येक प्रकार के पेशेवरों को इकट्ठा करने की कोशिश करता हूं। इस मामले में, एक के लिए एक प्लस दूसरे के एक ऋण के बराबर है।

व्याकरण विवरण लाभ:

1. सबसे पहले, यह आसान भाषा समर्थन है। यही है, संशोधनों, यहां तक ​​कि सबसे अधिक कार्डिनल, बहुत सरल रूप से आरोपित हैं।
2. चूंकि सिंटैक्टिक कंस्ट्रक्शन एक स्थान पर और कॉम्पैक्ट रूप से एकत्र किए जाते हैं, इसलिए समग्र रूप से भाषा की संरचना की समीक्षा करना बहुत सरल है। विकल्प में, आप तर्क के साथ मिश्रित हजारों और दसियों हज़ारों लाइनों के बीच बस दीवार कर सकते हैं। इसके अलावा, भाषा की पारदर्शिता सुनिश्चित की जाती है, संरचनाओं के विकास का स्पष्ट रूप से पता लगाया जाता है। अर्थात्, हमारे उदाहरण में, हम देखते हैं कि कैसे DIGIT ADD में बदल जाता है, और फिर EXPR में, वास्तव में हमें शब्दार्थ तर्क प्रस्तुत करने के लिए बिंदुओं को रेखांकित करने की अनुमति देता है।
3. आसान बग ट्रैकिंग। इसके अलावा, एक बार में दो श्रेणियां - इनपुट डेटा की सिंटैक्स त्रुटियां और कोड खुद को संकलित करने की त्रुटियां। मैन्युअल रूप से लिखते समय, कोड में विसंगतियां, मृत अनुभाग और अन्य तार्किक खुशियाँ हो सकती हैं और उसी समय संकलित की जा सकती हैं। दिए गए सर्किट के साथ, यह संभव नहीं है। विरोधाभासों की पहचान पीढ़ी स्तर पर तुरंत की जाती है।
4. अतिरिक्त अमूर्तता का परिचय स्रोत कोड को सरल करता है और आपको उच्च-स्तरीय संस्थाओं को डिबग और परीक्षण करने की अनुमति देता है, जो परिभाषा के अनुसार वर्णों की एक सरल धारा की तुलना में कम कई और अधिक विशिष्ट हैं।

इस सब के बावजूद, प्रोग्रामिंग के कई फायदे हैं:

1. प्रवेश सीमा बहुत कम है। यही है, लगभग कोई भी प्रोग्रामर "सिट राइट कोड" कह सकता है, और पार्सर को प्रस्तावित शैली में प्रोग्राम किया जाएगा। एक औपचारिक व्याकरण को संकलित करने के लिए, आपको एक छोटे, लेकिन अभी भी महत्वपूर्ण, सिद्धांत की मात्रा - गणितीय तर्क की मूल बातें, व्याकरण के निर्माण को समझने के लिए, एक कोड जनरेशन टूल के मालिक होने की आवश्यकता है।
2. इस तथ्य के बावजूद कि व्याकरण लगभग हर चीज का वर्णन कर सकता है, अपवाद हैं। इसके अलावा, सीमित इंस्ट्रूमेंटेशन उन्हें जोड़ा जाता है। प्रत्यक्ष कोडिंग अत्यधिक लचीला है।
3. अभी भी बहुत छोटा प्लस है - सभी एक ही स्थान पर। यही है, कार्यक्रम के सामान्य संगठन के साथ, आप तर्क के प्रमुख टुकड़ों को उजागर कर सकते हैं और तुरंत उनके सार को समझ सकते हैं। पहले संस्करण में, हमारे पास वास्तव में दो आवश्यक स्क्रीन हैं - एक योजना स्क्रीन + एक कोड स्क्रीन। कभी-कभी आपको बारीकियों को स्पष्ट करने के लिए उनके बीच स्विच करने की आवश्यकता होती है। यह पूरी तरह से सुविधाजनक नहीं है। लेकिन फिर, यह एक बहुत छोटा लाभ है, खासकर जब आप अलग-अलग कोडिंग के दूसरे प्लस को ध्यान में रखते हैं।

पार्सर संरचना

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



यह एक बहुत ही सशर्त योजना है, विश्लेषक में सभी तीन भागों शामिल हो सकते हैं, या पहले या अंतिम दो का एक संयोजन हो सकता है, और यहां तक ​​कि घटकों में अलग किए बिना एक ठोस टुकड़ा हो सकता है। संगठन में लगभग कोई सर्वोत्तम प्रथा नहीं है। लेकिन व्यक्तिगत रूप से, मैं कटलेट से मक्खियों को अलग करना पसंद करता हूं। मैं एक होलिवर नस्ल नहीं करूँगा, लेकिन बस विकल्पों का वर्णन करें।

सबसे पहले, यह समझने योग्य है कि ये घटक क्या हैं। शाब्दिक विश्लेषक किसी दिए गए वर्णमाला (वर्ण, संख्या, प्रयुक्त वर्ण, आदि) के पात्रों की एक इनपुट स्ट्रीम प्राप्त करता है। इसके अलावा, वह इस धारा को और अधिक जटिल आदिम (जैसे एक ऑक्सीमोरोन, हाँ) में तोड़ता है, तथाकथित टोकन या टर्मिनल। उदाहरण के लिए, कुछ लंबाई के अंकों के अनुक्रम के बजाय, पार्सर इस संख्या के मूल्य के बराबर एक विशेषता के साथ एक "संख्या" प्राप्त करता है। मुझे इसकी आवश्यकता क्यों है, मैं नीचे बताऊंगा। इसके बाद, दूसरे पदानुक्रमित क्रम (पहले - टोकन) के प्रतीकों की रचना के लिए टोकन और नियमों के आधार पर एक पार्सर, तथाकथित गैर-टर्मिनल, एक आउटपुट ट्री एकत्र करता है। यह ADT विशिष्ट रूप से मान्यता प्राप्त डेटा की संरचना का प्रतिनिधित्व करता है। और अंत में, अंतिम चरण परिणामस्वरूप पेड़ का एक अर्थ विश्लेषण और व्यावसायिक तर्क का कार्यान्वयन है। बस इस चरण को पहली सूची में प्रस्तुत किया गया है।

अगर हमें वास्तव में सिंटैक्स भाग में एकीकृत किया जा सकता है तो हमें एक लेक्सिकल विश्लेषक की आवश्यकता क्यों है? आखिर वह कौन सा अंतर है जिसे पाने के लिए वर्णमाला - मूल या नया सिंथेटिक। उत्तर काफी स्पष्ट है - सबसे पहले, यह आमतौर पर वर्णमाला का एक संकीर्णता है, अर्थात, शब्दार्थ का सरलीकरण; दूसरी बात, हम इसके गुणों को पूरी तरह से संरक्षित करते हुए पेड़ के एक या कई निचले स्तरों को हटा देते हैं। यह स्पष्ट है कि लेक्सिकल विश्लेषक को वाक्य-विन्यास की भूमिका नहीं माननी चाहिए, और इससे भी अधिक अर्थपूर्ण, इसलिए, इसे "1 + 2" पर 3 नहीं लौटना चाहिए, लेकिन संख्या उत्पन्न करने जैसे सरल कार्य काफी उपयुक्त हैं। आइए उदाहरण को थोड़ा जटिल करते हैं और आउटपुट ट्री को दो मामलों में देखते हैं। उसी समय, मैं दिखाऊंगा कि यह किस तरह का पेड़ है, जो संक्षिप्त विवरण को काफी नहीं समझते हैं।

  DIGIT = '0'..'9' NUMBER = NUMBER? DIGIT ADD = NUMBER '+' NUMBER SIGN = ('+' | '-') NUMBER EXPR = ADD | SIGN 

विश्लेषण के भाव 12 + 34 हैं


इस तरह के एक सरल उदाहरण के साथ भी, यह देखा जा सकता है कि विश्लेषण को कम से कम 2 चरणों में विभाजित करना अधिक सुविधाजनक है। इसके अलावा, शाब्दिक विश्लेषक की विशेषज्ञता अधिक कुशल एल्गोरिदम के उपयोग की अनुमति देती है जो पार्सिंग व्याकरण से भिन्न होती है। पार्सर से ऊपर प्रस्तुत आनुभविक लेसर के अलावा मुख्य अंतर, आउटपुट नियमों की अनुपस्थिति है, या यों कहें, उनका निहित रूप से प्रतिनिधित्व किया जा सकता है, लेकिन केवल वर्णमाला के वर्ण दाईं ओर होंगे, और नियमों का अन्य लेक्सर गैर-टर्मिनलों के साथ कोई संबंध नहीं है। यही है, वे आत्मनिर्भर हैं और केवल पात्रों की अपेक्षित धारा का वर्णन करते हैं।

अब दूसरे संभावित मिश्र धातु पर विचार करें। यह पेड़ के निर्माण के चरण को दरकिनार करते हुए, शब्दार्थ में सीधे शब्दार्थ तर्क का एकीकरण है। यहां रणनीति सरल है - हम उन बिंदुओं को रेखांकित करते हैं जिनके अर्थ अर्थ होते हैं और कोड लिखते हैं। एक उदाहरण:

  DIGIT = '0'..'9' {value = child[0] - '0'} ADD = DIGIT '+' DIGIT {value = child[0].value + child[1].value} SIGN = ('+' | '-') DIGIT {value = child[0].value == '-' ? - child[1].value : child[1].value} EXPR = ADD | SIGN {result = child[0].value} 

यह ध्यान देने योग्य है कि जटिल व्याकरण को इस तरह वर्णित नहीं किया जा सकता है। हां, और इस तरह के मिश्रण से अलग कोड लिखने के कुछ फायदे खत्म हो जाते हैं। लेकिन सरल व्याकरण के लिए, यह कोड लिखने की एक बहुत अच्छी विधि है, और इसके महत्व को कम से कम नहीं किया जाना चाहिए।

एलएल बनाम एलआर, या हाथी बनाम व्हेल

एक अच्छा लेख लिखने वाला एक अलग विषय है, इसलिए मैं केवल एक पार्सर के विकास का वर्णन करना जारी रखूंगा।

एनालाइज़र के दो समूह प्रतिष्ठित हैं - आरोही (एलआर) और अवरोही (एलएल)।

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

LR parser में सशर्त रूप से एक स्टैक होता है जिसमें यह अंतिम आवक वर्णों (दोनों टर्मिनलों और गैर-टर्मिनलों) को संग्रहीत करता है, प्रत्येक चरण पर, अगले टोकन को पढ़ते हुए, पार्सर एक नियम खोजने की कोशिश करता है जिसे स्टैक के शीर्ष से सेट किए गए वर्ण पर लागू किया जा सकता है, यदि यह मिल जाए, तो यह ढह जाता है एक nonterminal में पात्रों का एक क्रम। यही है, यदि स्टैक {DIGIT, +, DIGIT} की तरह दिखता है, तो विश्लेषक इसे {ADD}, और फिर {EXPR} को ध्वस्त कर देगा। इस तरह के पार्सर का छद्म कोड कुछ इस तरह होगा:

 input >> term; while (term != EOF) { stack.push(term); do { reduced = false; for (Rule rule : rules) if (rule.Reduce(stack)) { stack.pop(rule.right.length); stack.push(rule.symbol); reduced = true; break; } } while (reduced); input >> term; } 

एक एलएल पार्सर विपरीत करने की कोशिश करता है - प्रत्येक आने वाले चरित्र के लिए, अनुमान लगाएं कि यह किस नियम पर लागू होता है। सबसे आदिम विकल्प का विकल्प है (उदाहरण के लिए, EXPR को पहले चरित्र द्वारा ADD या SIGN, यानी 2 विकल्पों में) और नए पथ के साथ एक पुनरावर्ती वंश के रूप में तैनात किया जा सकता है जो चयनित पथ से गैर-टर्मिनल उत्पन्न करता है। और इसलिए जब तक कि नियम टर्मिनलों से विघटित नहीं हो जाते। विवरण काफी जटिल है, कोड में इसे समझना बहुत आसान होगा:

 function ExpandRule(symbol, term) { for (Rule rule : rules) { if (rule.sybmol == symbol && firstTerminal(rule) == term) break; } for (s : rule) { if (s.type == NonTerminal) term = ExpandRule(s, term); else { if (term != s) throw SyntaxError; input >> term; } } return term; } input >> term; ExpandRule(EXPR, term); 

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

पुनश्च: लेखों के सही ढंग से लिखने के महत्व को लेख के सही दूसरे खंड को देखकर देखा जा सकता है जो पहले उदाहरण के रूप में उसी स्रोत ब्लॉक में लिपटा हुआ है।

लेख के अंश

1. भाग 1. मूल सिद्धांत
2. भाग 2. LR जनरेटर का विवरण
3. भाग 3. एलआर-जनरेटर के लेखन और संभव सुविधाओं की विशेषताएं