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

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

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

उदाहरण

सामान्य लैंग्वेज

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

A → A | ε

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

इस लैंग्वेज में स्पष्ट ग्रामर भी है, जिसमें एकल प्रोडक्शन नियम (फॉर्मल लैंग्वेज) सम्मिलित हैं:

A → ε

...कारण कि अद्वितीय प्रोडक्शन केवल रिक्त स्ट्रिंग का प्रोडक्शन कर सकता है, जो लैंग्वेज में अद्वितीय स्ट्रिंग है।

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

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

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

A → aA | ε

...किन्तु इसमें एम्बिगुयस ग्रामर भी है:

A → aA | Aa | ε

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

जोड़ना और घटाना

कांटेक्स्ट फ्री ग्रामर

A → A + A | A - A | A

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

	A	→ A + A		A	→ A + A
		→ a + A			→ A + A + A (पहले A को A+A से बदल दिया गया है। दूसरे A के प्रतिस्थापन से समान व्युत्पत्ति प्राप्त होगी)
		→ a + A + A			→ a + A + A
		→ a + a + A			→ a + a + A
		→ a + a + a			→ a + a + a

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

चूँकि, यह जो लैंग्वेज उत्पन्न करता है, वह स्वाभाविक रूप से एम्बिगुयस नहीं है; निम्नलिखित नॉन-एम्बिगुयस ग्रामर है जो समान लैंग्वेज उत्पन्न करता है:

ए → A + A | A - A | ए

डैंगलिंग एल्स

Main article: डैंगलिंग एल्स

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

सामान्यतः, अनेक लैंग्वेज में कोई नियमबद्ध को दो वैध रूपों में लिख सकता है: यदि-तब रूप, और यदि-तब-और रूप - वास्तव में, अन्य खंड को वैकल्पिक बनाता है:

नियमों से युक्त ग्रामर में

Statement → if Condition then Statement |
            if Condition then Statement else Statement |
            ...
Condition → ...

कुछ एम्बिगुयस वाक्यांश संरचनाएँ प्रकट हो सकती हैं।

if a then if b then s else s2

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

if a then begin if b then s end else s2

या जैसे

if a then begin if b then s else s2 end

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

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

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

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

उदाहरण के लिए, सरल ग्रामर

S → A + A
A → 0 | 1

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

S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0

और

S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0

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

एम्बिगुयस ग्रामर को पहचानना

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

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

अनएम्बिगुयस कांटेक्स्ट-फ्री ग्रामर नॉन-डेटर्मिनिस्टिक हो सकते हैं। उदाहरण के लिए, 0 और 1 की वर्णमाला पर सम-लंबाई वाले विलोमपद की लैंग्वेज में स्पष्ट कांटेक्स्ट-फ्री ग्रामर S → 0S0 1S1 ε. इस लैंग्वेज की अनैतिक स्ट्रिंग को पहले उसके सभी प्रतीकों को पढ़े बिना पार्स नहीं किया जा सकता है, जिसका अर्थ है कि पुशडाउन ऑटोमेटन को अर्ध-पार्स की गई स्ट्रिंग की विभिन्न संभावित लंबाई को समायोजित करने के लिए वैकल्पिक राज्य परिवर्तनों का प्रयास करता है। फिर भी, 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\}$ स्वाभाविक रूप से एम्बिगुयस है. यह सेट कांटेक्स्ट-फ्री है, क्योंकि दो कांटेक्स्ट-फ्री लैंग्वेज का मिलन सदैव कांटेक्स्ट-फ्री होता है। किन्तु हॉपक्रॉफ्ट & उल्मन (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.