अस्पष्ट व्याकरण

कंप्यूटर विज्ञान में, अस्पष्ट व्याकरण एक संदर्भ-मुक्त व्याकरण है जिसके लिए एक स्ट्रिंग (कंप्यूटर विज्ञान) मौजूद है जिसमें एक से अधिक बाईं ओर व्युत्पत्ति या पार्स वृक्ष हो सकते हैं। प्रत्येक गैर-रिक्त संदर्भ-मुक्त भाषा उदाहरण के द्वारा एक अस्पष्ट व्याकरण को स्वीकार करती है। एक डुप्लिकेट नियम. वह भाषा जो केवल अस्पष्ट व्याकरणों को स्वीकार करती है, #स्वाभाविक रूप से अस्पष्ट भाषा कहलाती है। नियतिवादी संदर्भ-मुक्त व्याकरण हमेशा असंदिग्ध होते हैं, और असंदिग्ध व्याकरणों का एक महत्वपूर्ण उपवर्ग हैं; हालाँकि, गैर-नियतात्मक स्पष्ट व्याकरण हैं।

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

उदाहरण

तुच्छ भाषा

सबसे सरल उदाहरण उस तुच्छ भाषा के लिए निम्नलिखित अस्पष्ट व्याकरण (प्रारंभ प्रतीक ए के साथ) है जिसमें केवल खाली स्ट्रिंग शामिल है:

ए → ए | ε

...जिसका अर्थ यह है कि नॉनटर्मिनल ए को या तो खुद से, या खाली स्ट्रिंग से प्राप्त किया जा सकता है। इस प्रकार खाली स्ट्रिंग में लंबाई 1, 2, 3 और वास्तव में किसी भी लंबाई की सबसे बाईं व्युत्पत्ति होती है, यह इस पर निर्भर करता है कि नियम ए → ए का कितनी बार उपयोग किया जाता है।

इस भाषा में एक स्पष्ट व्याकरण भी है, जिसमें एकल उत्पादन नियम (औपचारिक भाषाएँ) शामिल हैं:

ए → ε

...मतलब कि अद्वितीय उत्पादन केवल खाली स्ट्रिंग का उत्पादन कर सकता है, जो भाषा में अद्वितीय स्ट्रिंग है।

उसी तरह, किसी गैर-रिक्त भाषा के लिए किसी भी व्याकरण को डुप्लिकेट जोड़कर अस्पष्ट बनाया जा सकता है।

यूनरी स्ट्रिंग

किसी दिए गए वर्ण की यूनरी स्ट्रिंग्स की नियमित भाषा, कहें 'a' (नियमित अभिव्यक्ति a*), स्पष्ट व्याकरण है:

ए → एए | ε

...लेकिन इसमें अस्पष्ट व्याकरण भी है:

ए → एए | आ | ε

ये एक दाएँ-साहचर्य वृक्ष (स्पष्ट व्याकरण के लिए) का निर्माण करने या बाएँ और दाएँ-दोनों-सहयोग की अनुमति देने के अनुरूप हैं। इसका विवरण नीचे दिया गया है।

जोड़ और घटाव

प्रसंग मुक्त व्याकरण

ए → ए + ए | ए - ए | ए

यह अस्पष्ट है क्योंकि स्ट्रिंग a + a + a के लिए दो सबसे बाईं व्युत्पत्तियाँ हैं:

	A	→ A + A		A	→ A + A
		→ a + A			→ A + A + A (First A is replaced by A+A. Replacement of the second A would yield a similar derivation)
		→ a + A + A			→ a + A + A
		→ a + a + A			→ a + a + A
		→ a + a + a			→ a + a + a

एक अन्य उदाहरण के रूप में, व्याकरण अस्पष्ट है क्योंकि स्ट्रिंग ए + ए - ए के लिए दो पार्स ट्री हैं:

हालाँकि, यह जो भाषा उत्पन्न करता है, वह स्वाभाविक रूप से अस्पष्ट नहीं है; निम्नलिखित एक गैर-अस्पष्ट व्याकरण है जो समान भाषा उत्पन्न करता है:

ए → ए + ए | ए - ए | ए

लटकना अन्यथा

Main article: Dangling else

कंप्यूटर प्रोग्रामिंग भाषाओं में अस्पष्टता का एक सामान्य उदाहरण लटकती हुई अन्य समस्या है। कई भाषाओं में, else एक कंडीशनल (कंप्यूटर प्रोग्रामिंग) में #If–then(–else)|If–then(–else) स्टेटमेंट वैकल्पिक है, जिसके परिणामस्वरूप नेस्टेड कंडीशनल को संदर्भ-मुक्त व्याकरण के संदर्भ में पहचाने जाने के कई तरीके होते हैं।

सीधे तौर पर, कई भाषाओं में कोई सशर्त को दो वैध रूपों में लिख सकता है: यदि-तब रूप, और यदि-तब-और रूप - वास्तव में, अन्य खंड को वैकल्पिक बनाता है: नियमों से युक्त व्याकरण में

कथन → यदि शर्त है तो कथन |
 यदि शर्त है तो कथन अन्यथा कथन |
 ...
शर्त → ...

कुछ अस्पष्ट वाक्यांश संरचनाएँ प्रकट हो सकती हैं। इजहार

यदि a तो यदि b तो s अन्य s2

किसी भी रूप में पार्स किया जा सकता है

यदि a है तो आरंभ करें यदि b है तो s समाप्त करें अन्यथा s2

या जैसे

यदि a तो आरंभ यदि b तो s अन्यथा s2 समाप्त

इस पर निर्भर करता है कि क्या else पहले से जुड़ा है if या दूसरा if.

इसे विभिन्न भाषाओं में विभिन्न तरीकों से हल किया जाता है। कभी-कभी व्याकरण को संशोधित किया जाता है ताकि यह स्पष्ट हो, जैसे कि इसकी आवश्यकता होती है endif कथन या कथन करना else अनिवार्य। अन्य मामलों में व्याकरण को अस्पष्ट छोड़ दिया जाता है, लेकिन समग्र वाक्यांश व्याकरण को संदर्भ-संवेदनशील बनाकर अस्पष्टता का समाधान किया जाता है, जैसे कि किसी को संबद्ध करके else निकटतम के साथ if. इस बाद वाले मामले में व्याकरण अस्पष्ट है, लेकिन संदर्भ-मुक्त व्याकरण अस्पष्ट है।

अनेक व्युत्पत्तियों वाला एक स्पष्ट व्याकरण

एक ही स्ट्रिंग की एकाधिक व्युत्पत्तियों का अस्तित्व यह इंगित करने के लिए पर्याप्त नहीं है कि व्याकरण अस्पष्ट है; केवल एकाधिक बाईं ओर की व्युत्पत्तियाँ (या, समकक्ष, एकाधिक पार्स वृक्ष) अस्पष्टता का संकेत देती हैं।

उदाहरण के लिए, सरल व्याकरण

एस → ए + ए
ए → 0 | 1

भाषा के लिए एक स्पष्ट व्याकरण है { 0+0, 0+1, 1+0, 1+1 }। हालाँकि इन चार तारों में से प्रत्येक में केवल एक बाईं ओर की व्युत्पत्ति है, उदाहरण के लिए, इसकी दो अलग-अलग व्युत्पत्तियाँ हैं

एस संदर्भ-मुक्त व्याकरण#नियम अनुप्रयोग|⇒ ए + ए ⇒ 0 + ए ⇒ 0 + 0

और

एस ⇒ ए + ए ⇒ ए + 0 ⇒ 0 + 0

केवल पूर्व व्युत्पत्ति ही सबसे बाईं ओर है।

अस्पष्ट व्याकरणों को पहचानना

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

असंदिग्ध संदर्भ-मुक्त व्याकरण गैर-नियतात्मक हो सकते हैं। उदाहरण के लिए, 0 और 1 की वर्णमाला पर सम-लंबाई वाले विलोमपद की भाषा में स्पष्ट संदर्भ-मुक्त व्याकरण S → 0S0 | 1एस1 | ε. इस भाषा की एक मनमानी स्ट्रिंग को पहले उसके सभी प्रतीकों को पढ़े बिना पार्स नहीं किया जा सकता है, जिसका अर्थ है कि एक पुशडाउन ऑटोमेटन को अर्ध-पार्स की गई स्ट्रिंग की विभिन्न संभावित लंबाई को समायोजित करने के लिए वैकल्पिक राज्य परिवर्तनों का प्रयास करना होगा। फिर भी, व्YACC रण की अस्पष्टता को दूर करने से एक नियतात्मक संदर्भ-मुक्त व्याकरण उत्पन्न हो सकता है और इस प्रकार अधिक कुशल पार्सिंग की अनुमति मिल सकती है। वाईएसीसी जैसे कंपाइलर जनरेटर में कुछ प्रकार की अस्पष्टता को हल करने की विशेषताएं शामिल हैं, जैसे कि प्राथमिकता और सहयोगीता बाधाओं का उपयोग करना।

स्वाभाविक रूप से अस्पष्ट भाषाएँ

जबकि कुछ संदर्भ-मुक्त भाषाएँ (स्ट्रिंग का सेट जो व्याकरण द्वारा उत्पन्न किया जा सकता है) में अस्पष्ट और स्पष्ट व्याकरण दोनों होते हैं, वहीं संदर्भ-मुक्त भाषाएँ मौजूद होती हैं जिनके लिए कोई भी स्पष्ट संदर्भ-मुक्त व्याकरण मौजूद नहीं हो सकता है। ऐसी भाषाओं को स्वाभाविक रूप से अस्पष्ट कहा जाता है।

कोई स्वाभाविक रूप से अस्पष्ट नियमित भाषाएँ नहीं हैं। स्वाभाविक रूप से अस्पष्ट संदर्भ-मुक्त भाषाओं का अस्तित्व 1961 में रोहित जीवणलाल पारीख द्वारा एमआईटी शोध रिपोर्ट में पारिख के प्रमेय के साथ सिद्ध किया गया था। भाषा $\{x|x=a^{n}b^{m}a^{n^{\prime }}b^{m}{\text{ or }}x=a^{n}b^{m}a^{n}b^{m^{\prime }},{\text{ where }}n,n',m,m'\geq 1\}$ स्वाभाविक रूप से अस्पष्ट है. ओग्डेन की लेम्मा यह साबित करने के लिए इस्तेमाल किया जा सकता है कि कुछ संदर्भ-मुक्त भाषाएँ, जैसे $\{a^{n}b^{m}c^{m}|m,n\geq 1\}\cup \{a^{m}b^{m}c^{n}|m,n\geq 1\}$, स्वाभाविक रूप से अस्पष्ट हैं। प्रमाण के लिए ओग्डेन की लेम्मा#अंतर्निहित अस्पष्टता देखें।

का संघ $\{a^{n}b^{m}c^{m}d^{n}\mid n,m>0\}$ साथ $\{a^{n}b^{n}c^{m}d^{m}\mid n,m>0\}$ स्वाभाविक रूप से अस्पष्ट है. यह सेट संदर्भ-मुक्त है, क्योंकि दो संदर्भ-मुक्त भाषाओं का मिलन हमेशा संदर्भ-मुक्त होता है। लेकिन Hopcroft & Ullman (1979) इस बात का प्रमाण दें कि इस संघ भाषा के लिए कोई भी संदर्भ-मुक्त व्याकरण रूप के तारों को स्पष्ट रूप से पार्स नहीं कर सकता है $a^{n}b^{n}c^{n}d^{n},(n>0)$. अधिक उदाहरण, और संदर्भ-मुक्त भाषाओं की अंतर्निहित अस्पष्टता को साबित करने के लिए तकनीकों की एक सामान्य समीक्षा, बैसिनो और निकौड (2011) द्वारा दी गई है।

यह भी देखें

• जीएलआर पार्सर, अस्पष्ट और गैर-नियतात्मक व्याकरणों के लिए एक प्रकार का पार्सर
• चार्ट पार्सर, अस्पष्ट व्याकरण के लिए एक अन्य प्रकार का पार्सर
• वाक्यात्मक अस्पष्टता

संदर्भ

• Gross, Maurice (September 1964). "Inherent ambiguity of minimal linear grammars". Information and Control. 7 (3): 366–368. doi:10.1016/S0019-9958(64)90422-X.
• Michael, Harrison (1978). Introduction to Formal Language Theory. Addison-Wesley. ISBN 0201029553.
• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley. ISBN 9780201029888.
• Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to Automata Theory, Languages and Computation (2nd ed.). Addison Wesley. pp. 217. ISBN 9780201441246.
• Brabrand, Claus; Giegerich, Robert; Møller, Anders (March 2010). "Analyzing Ambiguity of Context-Free Grammars". Science of Computer Programming. Elsevier. 75 (3): 176–191. CiteSeerX 10.1.1.86.3118. doi:10.1016/j.scico.2009.11.002.

बाहरी संबंध

• dk.brics.grammar - a grammar ambiguity analyzer.
• CFGAnalyzer - tool for analyzing context-free grammars with respect to language universality, ambiguity, and similar properties.