बाएं/दाएं रिकर्सिव, बाएं/दाएं-सबसे व्युत्पन्न, प्राथमिकता, सहयोगीता आदि के बीच अंतर

Question

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

दायां/बायां प्रत्यावर्तन, दायां/बायां-सबसे व्युत्पत्ति, दायां/बायां कमी, पूर्वता, संबद्धता आदि

इन करो सब मतलब एक ही बात?

Answer 1

नहीं, उनके सभी अलग-अलग अर्थ हैं।

दाएं और बाएं-रिकर्सन उत्पादन नियमों के भीतर रिकर्सन का संदर्भ लें। गैर-टर्मिनल के लिए एक उत्पादन रिकर्सिव है यदि यह उस गैर टर्मिनल के साथ अनुक्रम प्राप्त कर सकता है; यह गैर-टर्मिनल व्युत्पन्न अनुक्रम के प्रारंभ (बाएं किनारे) पर दिखाई दे सकता है, और दाएं-पुनरावर्ती है यदि यह अंत (दाएं किनारे) पर दिखाई दे सकता है तो बाएं-रिकर्सिव है। एक उत्पादन बाएं या दाएं-पुनरावर्ती होने के बिना रिकर्सिव हो सकता है, और यह बाएं और दाएं-रिकर्सिव दोनों भी हो सकता है।

उदाहरण के लिए

:

term: term '*' factor   { /* left-recursive */ } 
assignment: lval '=' assignment { /* right-recursive */ } 

उपरोक्त उदाहरण दोनों प्रत्यक्ष प्रत्यावर्तन कर रहे हैं; गैर टर्मिनल सीधे एक अनुक्रम प्राप्त करता है जिसमें गैर-टर्मिनल होता है। रिकर्सन अप्रत्यक्ष भी हो सकता है; यह अभी भी रिकर्सन है।

सभी सामान्य पार्सिंग एल्गोरिदम प्रक्रिया बाएं से दाएं, जो एलएल और एलआर में पहली एल है। टॉप-डाउन (एलएल) पार्सिंग में बाएं सबसे ज्यादा व्युत्पन्न (दूसरा एल) पाता है, जबकि नीचे-ऊपर (एलआर) पार्सिंग को सही व्युत्पन्न (आर) मिलती है।

प्रभावी रूप से, इनपुट पाठ प्राप्त होने तक वर्तमान अनुक्रम में कुछ गैर-टर्मिनल पर आधारित एक गैर-टर्मिनल (प्रारंभ प्रतीक) और "अनुमान" एक व्युत्पन्न के साथ दोनों प्रकार के पार्सर शुरू होते हैं। बाएं सबसे ज्यादा व्युत्पन्न में, यह हमेशा बाएं सबसे गैर-टर्मिनल होता है जिसे विस्तारित किया जाता है। दाएं व्युत्पन्न में, यह हमेशा सही गैर-टर्मिनल होता है।

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

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

एक ऑपरेटर भाषा के लिए एलआर व्याकरण में (लगभग बोलने वाले, भाषाओं के लिए व्याकरण जो अंकगणितीय अभिव्यक्तियों की तरह दिखता है), बाएं- और दाएं-साझेदारी को क्रमशः बाएं और दाएं-पुनरावर्ती व्याकरण नियमों का उपयोग करके मॉडलिंग किया जाता है। "एसोसिएटिविटी" व्याकरण का एक अनौपचारिक विवरण है, जैसा कि "प्राथमिकता" है।

प्राथमिकता को व्याकरण नियमों की एक श्रृंखला का उपयोग करके मॉडलिंग किया जाता है, जिनमें से प्रत्येक अगले नियम को संदर्भित करता है (और जो आमतौर पर कोष्ठक को संभालने के लिए एक पुनरावर्ती उत्पादन के साथ समाप्त होता है - '(' expr ')' - जो न तो बाएं- न ही दाएं-पुनरावर्ती है)।

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

Answer 2

(मैं पार्सर और संकलक सिद्धांत पर एक विशेषज्ञ नहीं हूँ। मैं सीख जा से संबंधित कुछ होता है। और मैं कुछ मैं अब तक पाया है साझा करना चाहते हैं।)

मैं दृढ़ता पर एक नज़र डालने का सुझाव यह awesome article।

यह बताता है और एलएल और एलआर एल्गोरिदम दिखाता है। आप स्पष्ट रूप से देख सकते हैं कि एलएल को टॉप-डाउन क्यों कहा जाता है और एलआर को नीचे-अप कहा जाता है।

कुछ उद्धरण:

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

...

हम कैसे डालूँगा और एलआर पारसर्स संचालित के लिए एक बहुत ही सरल मॉडल पर converging रहे हैं। दोनों इनपुट टोकन की एक धारा पढ़ते हैं और उसी टोकन धारा को आउटपुट करते हैं, प्री-ऑर्डर (एलएल) या पोस्ट-ऑर्डर (एलआर) पार्स पेड़ के ट्रैवर्सल को प्राप्त करने के लिए उचित स्थानों में नियमों को सम्मिलित करते हैं।

...

जब आप डालूँगा तरह पदनाम देखना (1), एलआर (0), आदि कोष्ठक में संख्या अग्रदर्शी की टोकन की संख्या है।

और संक्षिप्त रूप के रूप में: (source)

पहले एलएलआर में और डालूँगा का अर्थ है: कि पदव्याख्यायित्र, इनपुट पढ़ता एक ही दिशा में पाठ का समर्थन किए बिना; वह दिशा आमतौर पर प्रत्येक पंक्ति के भीतर बाएं से दाएं होती है, और पूर्ण इनपुट फ़ाइल की रेखाओं के ऊपर से नीचे तक होती है।

शेष आर और एल का अर्थ है: सबसे-दाएं और बाएं सबसे व्युत्पत्ति, क्रमशः।

ये 2 अलग पार्सिंग रणनीतियों हैं। एक पार्सिंग रणनीति अगले गैर-टर्मिनल को फिर से लिखने के लिए निर्धारित करती है। (source)

• बाएं सबसे अधिक व्युत्पन्न के लिए, यह हमेशा बाएं सबसे अधिक nonterminal है।
• दाएं सबसे अधिक व्युत्पन्न के लिए, यह हमेशा सही nonterminal है।