गुण व्याकरण: Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
'''गुण व्याकरण [[औपचारिक व्याकरण|फॉर्मल व्याकरण]]''' को शब्दार्थ सूचना प्रसंस्करण के साथ पूरक करने की फॉर्मल विधि है। इस प्रकार से सिमेंटिक जानकारी व्याकरण के [[टर्मिनल और नॉनटर्मिनल प्रतीक|टर्मिनल और नॉनटर्मिनल सिम्बल्स]] से जुड़े एट्रिब्यूट (कंप्यूटिंग) में स्टोर्ड करती है। और विशेषताओं के मान व्याकरण के निर्माण से जुड़े विशेषता मूल्यांकन नियमों का परिणाम हैं। अतः विशेषताएँ अमूर्त सिंटैक्स ट्री में कहीं से भी जानकारी को नियंत्रित और फॉर्मल विधि से स्थानांतरित करने की अनुमति देती हैं।{{Sfn|Knuth|1968|p=134}} | |||
प्रत्येक सिमेंटिक फ़ंक्शन केवल उत्पादन नियम में होने वाले | प्रत्येक सिमेंटिक फ़ंक्शन केवल उत्पादन नियम में होने वाले सिम्बल्स की विशेषताओं से संबंधित है: सिमेंटिक फ़ंक्शन पैरामीटर और उसके परिणाम दोनों विशेष नियम से सिम्बल्स की विशेषताएं हैं। जब कोई सिमेंटिक फ़ंक्शन नियम के बाईं ओर सिम्बल्स की किसी विशेषता के मान को परिभाषित करता है, तो विशेषता को संश्लेषित कहा जाता है; अन्यथा इसे इनहेरिटेड कहा जाता है।{{Sfn|Knuth|1968|p=132}} इस प्रकार, संश्लेषित विशेषताएँ सिमेंटिक जानकारी को पार्स ट्री तक पारित करने का कार्य करती हैं, जबकि इनहेरिटेड में मिली विशेषताएँ मूल नोड्स से नीचे और सिंटैक्स ट्री के पार मानों को पारित करने की अनुमति देती हैं। | ||
सरल अनुप्रयोगों में, जैसे कि अंकगणितीय अभिव्यक्तियों का मूल्यांकन, विशेषता व्याकरण का उपयोग सीधे | इस प्रकार से सरल अनुप्रयोगों में, जैसे कि अंकगणितीय अभिव्यक्तियों का मूल्यांकन, विशेषता व्याकरण का उपयोग सीधे विधि से पार्सिंग के अतिरिक्त किए जाने वाले संपूर्ण कार्य का वर्णन करने के लिए किया जा सकता है; और सम्मिश्र प्रणालियों में, उदाहरण के लिए, [[ संकलक |कंपाइलर]] जैसे लैंग्वेज अनुवाद उपकरण का निर्माण करते समय, इसका उपयोग व्याकरण से जुड़े शब्दार्थ जांच को मान्य करने के लिए किया जा सकता है, जो की किसी लैंग्वेज के नियमों का प्रतिनिधित्व करता है इस प्रकार से सिंटैक्स परिभाषा द्वारा स्पष्ट रूप से प्रदान नहीं किए जाते हैं। इसका उपयोग [[पार्सर]] या कंपाइलरों द्वारा सिंटैक्स ट्री को सीधे किसी विशिष्ट मशीन के कोड में या किसी [[मध्यवर्ती भाषा|इंटरमीडिएट]] लैंग्वेज में अनुवाद करने के लिए भी किया जा सकता है। | ||
==इतिहास== | ==इतिहास== | ||
अतः गुण व्याकरण का आविष्कार [[डोनाल्ड नुथ]] और [[पीटर वेगनर]] द्वारा किया गया था।<ref name="genesis">D. E. Knuth: [http://www.cs.miami.edu/home/odelia/teaching/csc419_spring17/syllabus/Knuth_AttributeHistory.pdf The genesis of attribute grammars]. ''Proceedings of the international conference on Attribute grammars and their applications'' (1990), LNCS, [https://doi.org/10.1007%2F3-540-53101-7 vol. 461], 1–12.</ref> जबकि समग्र अवधारणा के लिए डोनाल्ड नुथ को श्रेय दिया जाता है, किन्तु पीटर वेगनर ने नुथ के साथ वार्तालाप के समय इनहेरिटेड में मिली विशेषताओं का आविष्कार किया गया था। कुछ भ्रूणीय विचार पीछे छिपे हैं<ref name="genesis"/> और लेखक एडगर टी. नेड आयरन्स के कार्य के लिए,<ref>{{Cite web|url=http://zzcad.com/ned.htm|title=Main}}</ref> आईएमपी (प्रोग्रामिंग लैंग्वेज) मिलते हैं। | |||
==उदाहरण== | ==उदाहरण== | ||
निम्नलिखित सरल [[संदर्भ-मुक्त व्याकरण]] है जो पूर्णांकों के गुणन और योग से बनी | निम्नलिखित सरल [[संदर्भ-मुक्त व्याकरण|कॉन्टेक्स्ट-मुक्त व्याकरण]] है जो की पूर्णांकों के गुणन और योग से बनी लैंग्वेज का वर्णन कर सकता है। | ||
एक्सप्र → एक्सप्र + टर्म | एक्सप्र → एक्सप्र + टर्म | ||
| Line 18: | Line 18: | ||
गुणनखंड → ''पूर्णांक'' | गुणनखंड → ''पूर्णांक'' | ||
व्याकरण में लिखी गई अभिव्यक्ति के परिणाम की गणना करने के लिए निम्नलिखित विशेषता व्याकरण का उपयोग किया जा सकता है। ध्यान दें कि यह व्याकरण केवल संश्लेषित मानों का उपयोग करता है, और इसलिए यह एस-गुणित व्याकरण है। | इस प्रकार से व्याकरण में लिखी गई अभिव्यक्ति के परिणाम की गणना करने के लिए निम्नलिखित विशेषता व्याकरण का उपयोग किया जा सकता है। अतः ध्यान दें कि यह व्याकरण केवल संश्लेषित मानों का उपयोग करता है, और इसलिए यह एस-गुणित व्याकरण है। | ||
एक्सप्र1 → एक्सप्र2 + टर्म [एक्सप्र1.वैल्यू = एक्सप्र2.वैल्यू + टर्म.वैल्यू] | |||
एक्सप्र → टर्म [ एक्सप्र.वैल्यू = टर्म.वैल्यू ] | |||
टर्म1 → टर्म2 * फ़ैक्टर [ टर्म1.वैल्यू = टर्म2.वैल्यू * फ़ैक्टर.वैल्यू ] | |||
पद → गुणनखंड [अवधि.वैल्यू = गुणनखंड.वैल्यू] | |||
फ़ैक्टर → "(" एक्सप्र ")" [ फ़ैक्टर.वैल्यू = एक्सप्र.वैल्यू ] | |||
गुणनखंड → पूर्णांक [ Factor.value = strToInt(integer.str) ] | |||
==संश्लेषित गुण== | ==संश्लेषित गुण== | ||
एक संश्लेषित विशेषता की गणना | एक संश्लेषित विशेषता की गणना चाइल्ड की विशेषताओं के वैल्यू से की जाती है। चूँकि चाइल्ड के वैल्यू की गणना पहले की जानी चाहिए, यह नीचे से ऊपर की ओर प्रसार का उदाहरण है।{{Sfn|Knuth|1968|p=130}} संश्लेषित विशेषता को फॉर्मल रूप से परिभाषित करने के लिए <math>G= \langle V_n,V_t,P,S \rangle</math>, आइए फॉर्मल व्याकरण होने दें, जहाँ | ||
* <math>V_n</math> गैर टर्मिनल | * <math>V_n</math> गैर टर्मिनल सिम्बल्स का सेट है | ||
* <math>V_t</math> टर्मिनल | * <math>V_t</math> टर्मिनल सिम्बल्स का सेट है | ||
* <math>P</math> | * <math>P</math> फॉर्मल प्रोडक्शंस का सेट है | ||
* <math>S</math> | * <math>S</math> डिस्टिंगुइशेड, या प्रारंभ, सिम्बल्स है | ||
पुनः, नॉनटर्मिनल सिम्बल्स <math>A</math> की श्रृंखला दी गई और विशेषता नाम <math>a</math>, <math>A.a</math> यदि ये तीनों नियम पूर्ण होते हैं तो यह संश्लेषित विशेषता है: | |||
* <math>A \rightarrow \alpha \in P</math> (अर्थात। <math>A \rightarrow \alpha</math> व्याकरण के नियमों में से है) | * <math>A \rightarrow \alpha \in P</math> (अर्थात। <math>A \rightarrow \alpha</math> व्याकरण के नियमों में से है) | ||
*<math>\alpha = \alpha_1 \ldots \alpha_n, \forall i, 1 \leq i \leq n: \alpha_i \in (V_n \cup V_t)</math> (अर्थात नियम के मुख्य भाग में प्रत्येक | *<math>\alpha = \alpha_1 \ldots \alpha_n, \forall i, 1 \leq i \leq n: \alpha_i \in (V_n \cup V_t)</math> (अर्थात नियम के मुख्य भाग में प्रत्येक सिम्बल्स या तो नॉनटर्मिनल या टर्मिनल है) | ||
*<math>A.a = f(\alpha_{j_1}.a_1, \ldots ,\alpha_{j_m}.a_m)</math>, | *<math>A.a = f(\alpha_{j_1}.a_1, \ldots ,\alpha_{j_m}.a_m)</math>, जहाँ <math>\{\alpha_{j_1}, \ldots ,\alpha_{j_m}\} \subseteq \{\alpha_1, \ldots ,\alpha_n\}</math> (अर्थात विशेषता का मान फ़ंक्शन <math>f</math> है नियम के मुख्य भाग में सिम्बल्स से कुछ मानों पर प्रयुक्त होता है) | ||
== | ==इनहेरिटेड में मिले गुण== | ||
पार्स ट्री में नोड पर | इस प्रकार से पार्स ट्री में नोड पर इनहेरिटेड में मिली विशेषता को मूल या सिबलिंग्स में विशेषता मानों का उपयोग करके परिभाषित किया गया है। किसी प्रोग्रामिंग लैंग्वेज निर्माण की उस संदर्भ पर निर्भरता व्यक्त करने के लिए इनहेरिटेड में मिली विशेषताएँ सुविधाजनक होती हैं जिसमें वह प्रकट होती है। उदाहरण के लिए, हम इनहेरिटेड में मिली विशेषता का उपयोग यह ट्रैक करने के लिए कर सकते हैं कि कोई पहचानकर्ता असाइनमेंट के बाईं या दाईं ओर दिखाई देता है या नहीं, यह तय करने के लिए कि पहचानकर्ता के पते या मान की आवश्यकता है या नहीं। संश्लेषित विशेषताओं के विपरीत, इनहेरिटेड में मिली विशेषताएँ मूल और/या सिबलिंग्सों से मान ले सकती हैं। जैसा कि निम्नलिखित उत्पादन में है, | ||
: | : S → ABC | ||
जहां A, S, B और C से मान प्राप्त कर सकता है। B, S, A और C से मान ले सकता है। इसी | जहां A, S, B और C से मान प्राप्त कर सकता है। चूंकि B, S, A और C से मान ले सकता है। इसी प्रकार, C, S, A और B से मान ले सकता है। | ||
==विशेष प्रकार के गुण व्याकरण== | ==विशेष प्रकार के गुण व्याकरण== | ||
* [[एल-विशेषीकृत व्याकरण]]: | * [[एल-विशेषीकृत व्याकरण]]: इनहेरिटेड में मिली विशेषताओं का मूल्यांकन अमूर्त सिंटैक्स ट्री के बाएं से दाएं ट्रैवर्सल में किया जा सकता है | ||
* [[ईसीएलआर-विशेषीकृत व्याकरण]]: एल-एट्रिब्यूटेड व्याकरण जिसकी | * [[ईसीएलआर-विशेषीकृत व्याकरण]]: एल-एट्रिब्यूटेड व्याकरण जिसकी इनहेरिटेड में मिली विशेषताओं का मूल्यांकन [[नीचे से ऊपर का विश्लेषण|बॉटम-अप पार्सिंग]] में भी किया जा सकता है। | ||
* ईसी[[एलआर-विशेषीकृत व्याकरण]]: एलआर-विशेषीकृत व्याकरणों का उपसमूह जहां | * ईसी[[एलआर-विशेषीकृत व्याकरण]]: एलआर-विशेषीकृत व्याकरणों का उपसमूह जहां इनहेरिटेड में मिली विशेषताओं के मूल्यांकन को अनुकूलित करने के लिए समतुल्य वर्गों का उपयोग किया जा सकता है। | ||
* एस-विशेषता व्याकरण: सरल प्रकार का विशेषता व्याकरण, केवल संश्लेषित विशेषताओं का उपयोग करता है, | * एस-विशेषता व्याकरण: सरल प्रकार का विशेषता व्याकरण, केवल संश्लेषित विशेषताओं का उपयोग करता है, किन्तु कोई इनहेरिटेड में मिली विशेषताएँ नहीं है। | ||
==यह भी देखें== | ==यह भी देखें== | ||
* व्याकरण | * व्याकरण एफ्फिक्स | ||
* [[वान विजनगार्डन व्याकरण]] | * [[वान विजनगार्डन व्याकरण]] | ||
* [[सिंटैक्स-निर्देशित अनुवाद]] | * [[सिंटैक्स-निर्देशित अनुवाद|सिंटैक्स-डिरेक्टेड ट्रांसलेशन]] | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 11:07, 4 August 2023
गुण व्याकरण फॉर्मल व्याकरण को शब्दार्थ सूचना प्रसंस्करण के साथ पूरक करने की फॉर्मल विधि है। इस प्रकार से सिमेंटिक जानकारी व्याकरण के टर्मिनल और नॉनटर्मिनल सिम्बल्स से जुड़े एट्रिब्यूट (कंप्यूटिंग) में स्टोर्ड करती है। और विशेषताओं के मान व्याकरण के निर्माण से जुड़े विशेषता मूल्यांकन नियमों का परिणाम हैं। अतः विशेषताएँ अमूर्त सिंटैक्स ट्री में कहीं से भी जानकारी को नियंत्रित और फॉर्मल विधि से स्थानांतरित करने की अनुमति देती हैं।[1]
प्रत्येक सिमेंटिक फ़ंक्शन केवल उत्पादन नियम में होने वाले सिम्बल्स की विशेषताओं से संबंधित है: सिमेंटिक फ़ंक्शन पैरामीटर और उसके परिणाम दोनों विशेष नियम से सिम्बल्स की विशेषताएं हैं। जब कोई सिमेंटिक फ़ंक्शन नियम के बाईं ओर सिम्बल्स की किसी विशेषता के मान को परिभाषित करता है, तो विशेषता को संश्लेषित कहा जाता है; अन्यथा इसे इनहेरिटेड कहा जाता है।[2] इस प्रकार, संश्लेषित विशेषताएँ सिमेंटिक जानकारी को पार्स ट्री तक पारित करने का कार्य करती हैं, जबकि इनहेरिटेड में मिली विशेषताएँ मूल नोड्स से नीचे और सिंटैक्स ट्री के पार मानों को पारित करने की अनुमति देती हैं।
इस प्रकार से सरल अनुप्रयोगों में, जैसे कि अंकगणितीय अभिव्यक्तियों का मूल्यांकन, विशेषता व्याकरण का उपयोग सीधे विधि से पार्सिंग के अतिरिक्त किए जाने वाले संपूर्ण कार्य का वर्णन करने के लिए किया जा सकता है; और सम्मिश्र प्रणालियों में, उदाहरण के लिए, कंपाइलर जैसे लैंग्वेज अनुवाद उपकरण का निर्माण करते समय, इसका उपयोग व्याकरण से जुड़े शब्दार्थ जांच को मान्य करने के लिए किया जा सकता है, जो की किसी लैंग्वेज के नियमों का प्रतिनिधित्व करता है इस प्रकार से सिंटैक्स परिभाषा द्वारा स्पष्ट रूप से प्रदान नहीं किए जाते हैं। इसका उपयोग पार्सर या कंपाइलरों द्वारा सिंटैक्स ट्री को सीधे किसी विशिष्ट मशीन के कोड में या किसी इंटरमीडिएट लैंग्वेज में अनुवाद करने के लिए भी किया जा सकता है।
इतिहास
अतः गुण व्याकरण का आविष्कार डोनाल्ड नुथ और पीटर वेगनर द्वारा किया गया था।[3] जबकि समग्र अवधारणा के लिए डोनाल्ड नुथ को श्रेय दिया जाता है, किन्तु पीटर वेगनर ने नुथ के साथ वार्तालाप के समय इनहेरिटेड में मिली विशेषताओं का आविष्कार किया गया था। कुछ भ्रूणीय विचार पीछे छिपे हैं[3] और लेखक एडगर टी. नेड आयरन्स के कार्य के लिए,[4] आईएमपी (प्रोग्रामिंग लैंग्वेज) मिलते हैं।
उदाहरण
निम्नलिखित सरल कॉन्टेक्स्ट-मुक्त व्याकरण है जो की पूर्णांकों के गुणन और योग से बनी लैंग्वेज का वर्णन कर सकता है।
एक्सप्र → एक्सप्र + टर्म एक्सप्र → अवधि पद → पद * कारक पद → कारक फ़ैक्टर → (एक्सपीआर) गुणनखंड → पूर्णांक
इस प्रकार से व्याकरण में लिखी गई अभिव्यक्ति के परिणाम की गणना करने के लिए निम्नलिखित विशेषता व्याकरण का उपयोग किया जा सकता है। अतः ध्यान दें कि यह व्याकरण केवल संश्लेषित मानों का उपयोग करता है, और इसलिए यह एस-गुणित व्याकरण है।
एक्सप्र1 → एक्सप्र2 + टर्म [एक्सप्र1.वैल्यू = एक्सप्र2.वैल्यू + टर्म.वैल्यू]
एक्सप्र → टर्म [ एक्सप्र.वैल्यू = टर्म.वैल्यू ]
टर्म1 → टर्म2 * फ़ैक्टर [ टर्म1.वैल्यू = टर्म2.वैल्यू * फ़ैक्टर.वैल्यू ]
पद → गुणनखंड [अवधि.वैल्यू = गुणनखंड.वैल्यू]
फ़ैक्टर → "(" एक्सप्र ")" [ फ़ैक्टर.वैल्यू = एक्सप्र.वैल्यू ]
गुणनखंड → पूर्णांक [ Factor.value = strToInt(integer.str) ]
संश्लेषित गुण
एक संश्लेषित विशेषता की गणना चाइल्ड की विशेषताओं के वैल्यू से की जाती है। चूँकि चाइल्ड के वैल्यू की गणना पहले की जानी चाहिए, यह नीचे से ऊपर की ओर प्रसार का उदाहरण है।[5] संश्लेषित विशेषता को फॉर्मल रूप से परिभाषित करने के लिए , आइए फॉर्मल व्याकरण होने दें, जहाँ
- गैर टर्मिनल सिम्बल्स का सेट है
- टर्मिनल सिम्बल्स का सेट है
- फॉर्मल प्रोडक्शंस का सेट है
- डिस्टिंगुइशेड, या प्रारंभ, सिम्बल्स है
पुनः, नॉनटर्मिनल सिम्बल्स की श्रृंखला दी गई और विशेषता नाम , यदि ये तीनों नियम पूर्ण होते हैं तो यह संश्लेषित विशेषता है:
- (अर्थात। व्याकरण के नियमों में से है)
- (अर्थात नियम के मुख्य भाग में प्रत्येक सिम्बल्स या तो नॉनटर्मिनल या टर्मिनल है)
- , जहाँ (अर्थात विशेषता का मान फ़ंक्शन है नियम के मुख्य भाग में सिम्बल्स से कुछ मानों पर प्रयुक्त होता है)
इनहेरिटेड में मिले गुण
इस प्रकार से पार्स ट्री में नोड पर इनहेरिटेड में मिली विशेषता को मूल या सिबलिंग्स में विशेषता मानों का उपयोग करके परिभाषित किया गया है। किसी प्रोग्रामिंग लैंग्वेज निर्माण की उस संदर्भ पर निर्भरता व्यक्त करने के लिए इनहेरिटेड में मिली विशेषताएँ सुविधाजनक होती हैं जिसमें वह प्रकट होती है। उदाहरण के लिए, हम इनहेरिटेड में मिली विशेषता का उपयोग यह ट्रैक करने के लिए कर सकते हैं कि कोई पहचानकर्ता असाइनमेंट के बाईं या दाईं ओर दिखाई देता है या नहीं, यह तय करने के लिए कि पहचानकर्ता के पते या मान की आवश्यकता है या नहीं। संश्लेषित विशेषताओं के विपरीत, इनहेरिटेड में मिली विशेषताएँ मूल और/या सिबलिंग्सों से मान ले सकती हैं। जैसा कि निम्नलिखित उत्पादन में है,
- S → ABC
जहां A, S, B और C से मान प्राप्त कर सकता है। चूंकि B, S, A और C से मान ले सकता है। इसी प्रकार, C, S, A और B से मान ले सकता है।
विशेष प्रकार के गुण व्याकरण
- एल-विशेषीकृत व्याकरण: इनहेरिटेड में मिली विशेषताओं का मूल्यांकन अमूर्त सिंटैक्स ट्री के बाएं से दाएं ट्रैवर्सल में किया जा सकता है
- ईसीएलआर-विशेषीकृत व्याकरण: एल-एट्रिब्यूटेड व्याकरण जिसकी इनहेरिटेड में मिली विशेषताओं का मूल्यांकन बॉटम-अप पार्सिंग में भी किया जा सकता है।
- ईसीएलआर-विशेषीकृत व्याकरण: एलआर-विशेषीकृत व्याकरणों का उपसमूह जहां इनहेरिटेड में मिली विशेषताओं के मूल्यांकन को अनुकूलित करने के लिए समतुल्य वर्गों का उपयोग किया जा सकता है।
- एस-विशेषता व्याकरण: सरल प्रकार का विशेषता व्याकरण, केवल संश्लेषित विशेषताओं का उपयोग करता है, किन्तु कोई इनहेरिटेड में मिली विशेषताएँ नहीं है।
यह भी देखें
- व्याकरण एफ्फिक्स
- वान विजनगार्डन व्याकरण
- सिंटैक्स-डिरेक्टेड ट्रांसलेशन
संदर्भ
- ↑ Knuth 1968, p. 134.
- ↑ Knuth 1968, p. 132.
- ↑ 3.0 3.1 D. E. Knuth: The genesis of attribute grammars. Proceedings of the international conference on Attribute grammars and their applications (1990), LNCS, vol. 461, 1–12.
- ↑ "Main".
- ↑ Knuth 1968, p. 130.
- Original paper introducing attributed grammars: Knuth, Donald E. (1968). "Semantics of context-free languages" (PDF). Mathematical Systems Theory. 2 (2): 127–145. doi:10.1007/BF01692511. S2CID 5182310., backup
बाहरी संबंध
- Why Attribute Grammars Matter, The Monad Reader, Issue 4, July 5, 2005. (This article narrates on how the formalism of attribute grammars brings aspect-oriented programming to functional programming by helping writing catamorphisms compositionally. It refers to the Utrecht University Attribute Grammar system (see also Lrc: A Purely Functional, Higher-Order Attribute Grammar based System) as the implementation used in the examples.)
- Attribute grammar in relation to Haskell and functional programming.
- Jukka Paakki: Attribute grammar paradigms—a high-level methodology in language implementation. ACM Computing Surveys 27:2 (June 1995), 196–255.
- Ox is an attribute grammar compiling system that augments Lex and Yacc specifications with definitions of synthesized and inherited attributes written in a combination of Ox and C/C++ syntax. From these specifications, Ox generates ordinary Lex and Yacc specifications that build and decorate an attributed parse tree. Ox works with the Lex and Yacc versions distributed in the Unix and Solaris operating systems, Flex, RE/flex, Bison, BYacc, BtYacc and MSTA (in the DINO GitHub repository). (See the SourceForge repository.)
- Silver is an extensible attribute grammar specification language and system from University of Minnesota. (See also the GitHub repository.)
