गुण व्याकरण

From Vigyanwiki

एट्रिब्यूटेड ग्रामर फॉर्मल ग्रामर को शब्दार्थ सूचना प्रसंस्करण के साथ पूरक करने की फॉर्मल विधि है। इस प्रकार से सिमेंटिक जानकारी ग्रामर के टर्मिनल और नॉनटर्मिनल सिम्बल्स से जुड़े एट्रिब्यूट (कंप्यूटिंग) में स्टोर्ड करती है। और विशेषताओं के मान ग्रामर के निर्माण से जुड़े विशेषता मूल्यांकन नियमों का परिणाम हैं। अतः विशेषताएँ एब्स्ट्रेक्ट सिंटैक्स ट्री में कहीं से भी जानकारी को नियंत्रित और फॉर्मल विधि से स्थानांतरित करने की अनुमति देती हैं।[1]

प्रत्येक सिमेंटिक फ़ंक्शन केवल उत्पादन नियम में होने वाले सिम्बल्स की विशेषताओं से संबंधित है: सिमेंटिक फ़ंक्शन पैरामीटर और उसके परिणाम दोनों विशेष नियम से सिम्बल्स की विशेषताएं हैं। जब कोई सिमेंटिक फ़ंक्शन नियम के बाईं ओर सिम्बल्स की किसी विशेषता के मान को परिभाषित करता है, तो विशेषता को संश्लेषित कहा जाता है; अन्यथा इसे इनहेरिटेड कहा जाता है।[2] इस प्रकार, संश्लेषित विशेषताएँ सिमेंटिक जानकारी को पार्स ट्री तक पारित करने का कार्य करती हैं, जबकि इनहेरिटेड में मिली विशेषताएँ मूल नोड्स से नीचे और सिंटैक्स ट्री के पार मानों को पारित करने की अनुमति देती हैं।

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

इतिहास

अतः एट्रिब्यूटेड ग्रामर का आविष्कार डोनाल्ड नुथ और पीटर वेगनर द्वारा किया गया था।[3] जबकि समग्र अवधारणा के लिए डोनाल्ड नुथ को श्रेय दिया जाता है, किन्तु पीटर वेगनर ने नुथ के साथ वार्तालाप के समय इनहेरिटेड में मिली विशेषताओं का आविष्कार किया गया था। कुछ भ्रूणीय विचार पीछे छिपे हैं[3] और लेखक एडगर टी. नेड आयरन्स के कार्य के लिए,[4] आईएमपी (प्रोग्रामिंग लैंग्वेज) मिलते हैं।

उदाहरण

निम्नलिखित सरल कॉन्टेक्स्ट-मुक्त ग्रामर है जो की पूर्णांकों के एट्रिब्यूटेडन और योग से बनी लैंग्वेज का वर्णन कर सकता है।

 Expr  Expr + Term                                                                                                            
 Expr  Term                                                                                                         
 Term  Term * Factor                                                                                                                                                              
 Term  Factor
 Factor  "(" Expr ")"
 Factor  integer

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

Expr1 → Expr2 + Term [ Expr1.value = Expr2.value + Term.value ]
 Expr → Term [ Expr.value = Term.value ]
 Term1 → Term2 * Factor [ Term1.value = Term2.value * Factor.value ]
 Term → Factor [ Term.value = Factor.value ]
 Factor → "(" Expr ")" [ Factor.value =  Expr.value ]
 Factor → integer [ Factor.value = strToInt(integer.str) ]

संश्लेषित एट्रिब्यूटेड

एक संश्लेषित विशेषता की गणना चाइल्ड की विशेषताओं के वैल्यू से की जाती है। चूँकि चाइल्ड के वैल्यू की गणना पहले की जानी चाहिए, यह नीचे से ऊपर की ओर प्रसार का उदाहरण है।[5] संश्लेषित विशेषता को फॉर्मल रूप से परिभाषित करने के लिए , आइए फॉर्मल ग्रामर होने दें, जहाँ

  • गैर टर्मिनल सिम्बल्स का सेट है
  • टर्मिनल सिम्बल्स का सेट है
  • फॉर्मल प्रोडक्शंस का सेट है
  • डिस्टिंगुइशेड, या प्रारंभ, सिम्बल्स है

पुनः, नॉनटर्मिनल सिम्बल्स की श्रृंखला दी गई और विशेषता नाम , यदि ये तीनों नियम पूर्ण होते हैं तो यह संश्लेषित विशेषता है:

  • (अर्थात। ग्रामर के नियमों में से है)
  • (अर्थात नियम के मुख्य भाग में प्रत्येक सिम्बल्स या तो नॉनटर्मिनल या टर्मिनल है)
  • , जहाँ (अर्थात विशेषता का मान फ़ंक्शन है नियम के मुख्य भाग में सिम्बल्स से कुछ मानों पर प्रयुक्त होता है)

इनहेरिटेड एट्रिब्यूटेड

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

S → ABC

जहां A, S, B और C से मान प्राप्त कर सकता है। चूंकि B, S, A और C से मान ले सकता है। इसी प्रकार, C, S, A और B से मान ले सकता है।

विशेष प्रकार के एट्रिब्यूटेड ग्रामर

  • एल-एट्रिब्यूटेड ग्रामर: इनहेरिटेड में मिली विशेषताओं का मूल्यांकन एब्स्ट्रेक्ट सिंटैक्स ट्री के बाएं से दाएं ट्रैवर्सल में किया जा सकता है
  • ईसीएलआर-एट्रिब्यूटेड ग्रामर: एल-एट्रिब्यूटेड ग्रामर जिसकी इनहेरिटेड में मिली विशेषताओं का मूल्यांकन बॉटम-अप पार्सिंग में भी किया जा सकता है।
  • ईसीएलआर-एट्रिब्यूटेड ग्रामर: एलआर-एट्रिब्यूटेड ग्रामरों का उपसमूह जहां इनहेरिटेड में मिली विशेषताओं के मूल्यांकन को अनुकूलित करने के लिए समतुल्य वर्गों का उपयोग किया जा सकता है।
  • एस-विशेषता ग्रामर: सरल प्रकार का विशेषता ग्रामर, केवल संश्लेषित विशेषताओं का उपयोग करता है, किन्तु कोई इनहेरिटेड में मिली विशेषताएँ नहीं है।

यह भी देखें

कॉन्टेक्स्ट

  1. Knuth 1968, p. 134.
  2. Knuth 1968, p. 132.
  3. 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.
  4. "Main".
  5. Knuth 1968, p. 130.


बाहरी संबंध