अस्पष्ट व्याकरण: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(6 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Type of a context-free grammar}}
{{Short description|Type of a context-free grammar}}
[[कंप्यूटर विज्ञान]] में, अस्पष्ट व्याकरण एक [[संदर्भ-मुक्त व्याकरण]] है जिसके लिए एक [[स्ट्रिंग (कंप्यूटर विज्ञान)]] मौजूद है जिसमें एक से अधिक बाईं ओर व्युत्पत्ति या [[पार्स वृक्ष]] हो सकते हैं।<ref name="Levelt2008">{{cite book|author=Willem J. M. Levelt|title=औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय|url=https://books.google.com/books?id=tFvtwGYNe7kC&q=%22leftmost+derivation%22+%22ambiguous%22|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2}}</ref> प्रत्येक गैर-रिक्त [[संदर्भ-मुक्त भाषा]] उदाहरण के द्वारा एक अस्पष्ट व्याकरण को स्वीकार करती है। एक डुप्लिकेट नियम. वह भाषा जो केवल अस्पष्ट व्याकरणों को स्वीकार करती है, #स्वाभाविक रूप से अस्पष्ट भाषा कहलाती है। [[नियतिवादी संदर्भ-मुक्त व्याकरण]] हमेशा असंदिग्ध होते हैं, और असंदिग्ध व्याकरणों का एक महत्वपूर्ण उपवर्ग हैं; हालाँकि, गैर-नियतात्मक स्पष्ट व्याकरण हैं।
[[कंप्यूटर विज्ञान]] में, '''एम्बिगुयस''' '''ग्रामर''' [[संदर्भ-मुक्त व्याकरण|कांटेक्स्ट-फ्री ग्रामर]] है जिसके लिए [[स्ट्रिंग (कंप्यूटर विज्ञान)]] उपस्थित है जिसमें से अधिक बाईं ओर व्युत्पत्ति या [[पार्स वृक्ष|पार्स ट्री]] हो सकते हैं।<ref name="Levelt2008">{{cite book|author=Willem J. M. Levelt|title=औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय|url=https://books.google.com/books?id=tFvtwGYNe7kC&q=%22leftmost+derivation%22+%22ambiguous%22|year=2008|publisher=John Benjamins Publishing|isbn=978-90-272-3250-2}}</ref> प्रत्येक नॉन-रिक्त [[संदर्भ-मुक्त भाषा|कांटेक्स्ट-फ्री]] लैंग्वेज उदाहरण के द्वारा एम्बिगुयस ग्रामर को स्वीकार करती है। डुप्लिकेट नियम वह लैंग्वेज जो केवल एम्बिगुयस ग्रामर को स्वीकार करती है, स्वाभाविक रूप से एम्बिगुयस लैंग्वेज कहलाती है। [[नियतिवादी संदर्भ-मुक्त व्याकरण|डेटर्मिनिस्टिक कांटेक्स्ट-फ्री ग्रामर]] सदैव अनएम्बिगुयस होते हैं, और अनएम्बिगुयस ग्रामर का महत्वपूर्ण उपवर्ग हैं; चूँकि, नॉन-डेटर्मिनिस्टिक स्पष्ट ग्रामर हैं।
 
कंप्यूटर [[प्रोग्रामिंग भाषा]]ओं के लिए, लटकती अन्य समस्या जैसे मुद्दों के कारण संदर्भ व्याकरण अक्सर अस्पष्ट होता है। यदि मौजूद है, तो इन अस्पष्टताओं को आम तौर पर प्राथमिकता नियमों या अन्य [[संदर्भ-संवेदनशील व्याकरण]]|संदर्भ-संवेदनशील पार्सिंग नियमों को जोड़कर हल किया जाता है, इसलिए समग्र वाक्यांश व्याकरण स्पष्ट है। कुछ पार्सिंग एल्गोरिदम (जैसे कि ([[अर्ली पार्सर]])।<ref>{{cite journal|last1=Scott|first1=Elizabeth|title=प्रारंभिक पहचानकर्ताओं से एसपीपीएफ-शैली पार्सिंग|journal=Electronic Notes in Theoretical Computer Science|date=April 1, 2008|volume=203|issue=2|pages=53–67|doi=10.1016/j.entcs.2008.03.044|doi-access=free}}</ref> या [[सामान्यीकृत एलआर पार्सर]] पार्सर्स) उन स्ट्रिंग्स से पार्स ट्री (या पार्स फ़ॉरेस्ट) के सेट उत्पन्न कर सकते हैं जो [[वाक्यात्मक रूप से अस्पष्ट]] हैं।<ref>Tomita, Masaru. "[http://anthology.aclweb.org/J/J87/J87-1004.pdf An efficient augmented-context-free parsing algorithm]." Computational linguistics 13.1-2 (1987): 31-46.</ref>
 


कंप्यूटर [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज के लिए, अन्य समस्या जैसे उद्देश्यों के कारण कांटेक्स्ट ग्रामर अधिकांशतः एम्बिगुयस होता है। यदि उपस्थित है, तो इन एम्बिगुयसओं को सामान्यतः प्राथमिकता नियमों या अन्य [[संदर्भ-संवेदनशील व्याकरण|कांटेक्स्ट-सेंसिटिव ग्रामर]] या कांटेक्स्ट-सेंसिटिव पार्सिंग नियमों को जोड़कर हल किया जाता है, इसलिए समग्र वाक्यांश ग्रामर स्पष्ट है। कुछ पार्सिंग एल्गोरिदम (जैसे कि ([[अर्ली पार्सर]]) <ref>{{cite journal|last1=Scott|first1=Elizabeth|title=प्रारंभिक पहचानकर्ताओं से एसपीपीएफ-शैली पार्सिंग|journal=Electronic Notes in Theoretical Computer Science|date=April 1, 2008|volume=203|issue=2|pages=53–67|doi=10.1016/j.entcs.2008.03.044|doi-access=free}}</ref> या [[सामान्यीकृत एलआर पार्सर]]) उन स्ट्रिंग्स से पार्स ट्री (या पार्स फ़ॉरेस्ट) के सेट उत्पन्न कर सकते हैं जो [[वाक्यात्मक रूप से अस्पष्ट|सिंटेक्टिकली]] एम्बिगुयस हैं।<ref>Tomita, Masaru. "[http://anthology.aclweb.org/J/J87/J87-1004.pdf An efficient augmented-context-free parsing algorithm]." Computational linguistics 13.1-2 (1987): 31-46.</ref>
==उदाहरण==
==उदाहरण==


===तुच्छ भाषा===
===सामान्य लैंग्वेज===
सबसे सरल उदाहरण उस तुच्छ भाषा के लिए निम्नलिखित अस्पष्ट व्याकरण (प्रारंभ प्रतीक ए के साथ) है जिसमें केवल खाली स्ट्रिंग शामिल है:
सबसे सरल उदाहरण उस सामान्य लैंग्वेज के लिए निम्नलिखित एम्बिगुयस ग्रामर (प्रारंभ प्रतीक A के साथ) है जिसमें केवल रिक्त स्ट्रिंग सम्मिलित है:
:ए → ए | ε
:A → A | ε
...जिसका अर्थ यह है कि नॉनटर्मिनल ए को या तो खुद से, या खाली स्ट्रिंग से प्राप्त किया जा सकता है। इस प्रकार खाली स्ट्रिंग में लंबाई 1, 2, 3 और वास्तव में किसी भी लंबाई की सबसे बाईं व्युत्पत्ति होती है, यह इस पर निर्भर करता है कि नियम ए → ए का कितनी बार उपयोग किया जाता है।
जिसका अर्थ यह है कि नॉनटर्मिनल A को या तो स्वयं से, या रिक्त स्ट्रिंग से प्राप्त किया जा सकता है। इस प्रकार रिक्त स्ट्रिंग में लंबाई 1, 2, 3 और वास्तव में किसी भी लंबाई की सबसे बाईं व्युत्पत्ति होती है, यह इस पर निर्भर करता है कि नियम A → A का कितनी बार उपयोग किया जाता है।


इस भाषा में एक स्पष्ट व्याकरण भी है, जिसमें एकल [[उत्पादन नियम (औपचारिक भाषाएँ)]] शामिल हैं:
इस लैंग्वेज में स्पष्ट ग्रामर भी है, जिसमें एकल [[उत्पादन नियम (औपचारिक भाषाएँ)|प्रोडक्शन नियम (फॉर्मल लैंग्वेज)]] सम्मिलित हैं:
:ए → ε
:A → ε
...मतलब कि अद्वितीय उत्पादन केवल खाली स्ट्रिंग का उत्पादन कर सकता है, जो भाषा में अद्वितीय स्ट्रिंग है।
...कारण कि अद्वितीय प्रोडक्शन केवल रिक्त स्ट्रिंग का प्रोडक्शन कर सकता है, जो लैंग्वेज में अद्वितीय स्ट्रिंग है।


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


===यूनरी स्ट्रिंग===
===यूनरी स्ट्रिंग===
किसी दिए गए वर्ण की यूनरी स्ट्रिंग्स की [[नियमित भाषा]], कहें <code>'a'</code> (नियमित अभिव्यक्ति <code>a*</code>), स्पष्ट व्याकरण है:
किसी दिए गए वर्ण की यूनरी स्ट्रिंग्स की [[नियमित भाषा|रेगुलर लैंग्वेज]], <code>'a'</code> (रेगुलर अभिव्यक्ति <code>a*</code>), स्पष्ट ग्रामर है:
:ए → एए | ε
:A → aA | ε
...लेकिन इसमें अस्पष्ट व्याकरण भी है:
...किन्तु इसमें एम्बिगुयस ग्रामर भी है:
:ए → एए | आ | ε
:A → aA | Aa | ε
ये एक दाएँ-साहचर्य वृक्ष (स्पष्ट व्याकरण के लिए) का निर्माण करने या बाएँ और दाएँ-दोनों-सहयोग की अनुमति देने के अनुरूप हैं। इसका विवरण नीचे दिया गया है।
यह दाएँ-साहचर्य ट्री (स्पष्ट ग्रामर के लिए) का निर्माण करने या बाएँ और दाएँ-दोनों-सहयोग की अनुमति देने के अनुरूप हैं। इसका विवरण नीचे दिया गया है।


===जोड़ और घटाव===
===जोड़ना और घटाना===
प्रसंग मुक्त व्याकरण
कांटेक्स्ट फ्री ग्रामर
:ए → ए + ए | ए - ए | ए
:A → A + A | A - A | A
यह अस्पष्ट है क्योंकि स्ट्रिंग a + a + a के लिए दो सबसे बाईं व्युत्पत्तियाँ हैं:
यह एम्बिगुयस है क्योंकि स्ट्रिंग a + a + a के लिए दो सबसे बाईं व्युत्पत्तियाँ हैं:


{| border="0"
{| border="0"
Line 38: Line 36:
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + A
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + A
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| &nbsp;&nbsp;&nbsp;&nbsp;|&nbsp;&nbsp;&nbsp;&nbsp;
| || → 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 के प्रतिस्थापन से समान व्युत्पत्ति प्राप्त होगी)
|-----
|-----
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + A + A
| &nbsp;&nbsp;&nbsp;&nbsp; ||  || → a + A + A
Line 52: Line 50:
| || → a + a + a
| || → a + a + a
|}
|}
एक अन्य उदाहरण के रूप में, व्याकरण अस्पष्ट है क्योंकि स्ट्रिंग ए + ए - ए के लिए दो पार्स ट्री हैं:
एक अन्य उदाहरण के रूप में, ग्रामर एम्बिगुयस है क्योंकि स्ट्रिंग A + A - A के लिए दो पार्स ट्री हैं:
:[[Image:Leftmostderivations jaredwf.svg|Leftmostderivations jaredwf.svg|400px]]हालाँकि, यह जो भाषा उत्पन्न करता है, वह स्वाभाविक रूप से अस्पष्ट नहीं है; निम्नलिखित एक गैर-अस्पष्ट व्याकरण है जो समान भाषा उत्पन्न करता है:
:[[Image:Leftmostderivations jaredwf.svg|Leftmostderivations jaredwf.svg|400px]]
:ए → ए + ए | ए - ए | ए
:चूँकि, यह जो लैंग्वेज उत्पन्न करता है, वह स्वाभाविक रूप से एम्बिगुयस नहीं है; निम्नलिखित नॉन-एम्बिगुयस ग्रामर है जो समान लैंग्वेज उत्पन्न करता है:
:ए → A + A | A - A | ए


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


सीधे तौर पर, कई भाषाओं में कोई सशर्त को दो वैध रूपों में लिख सकता है: यदि-तब रूप, और यदि-तब-और रूप - वास्तव में, अन्य खंड को वैकल्पिक बनाता है:<ref group=note>The following example uses [[Pascal (programming language)|Pascal]] syntax</ref>
कंप्यूटर प्रोग्रामिंग लैंग्वेज में एम्बिगुयस का सामान्य उदाहरण डैंगलिंग हुई अन्य समस्या है। अनेक लैंग्वेज में, <code>else</code> कंडीशनल (कंप्यूटर प्रोग्रामिंग) में If–then(–else) या If–then(–else) स्टेटमेंट वैकल्पिक है, जिसके परिणामस्वरूप नेस्टेड कंडीशनल को कांटेक्स्ट-फ्री ग्रामर के कांटेक्स्ट में पहचाने जाने के अनेक विधि होते हैं।
नियमों से युक्त व्याकरण में


कथन → यदि शर्त है तो कथन |
सामान्यतः, अनेक लैंग्वेज में कोई नियमबद्ध को दो वैध रूपों में लिख सकता है: यदि-तब रूप, और यदि-तब-और रूप - वास्तव में, अन्य खंड को वैकल्पिक बनाता है:<ref group=note>The following example uses [[Pascal (programming language)|Pascal]] syntax</ref>
  यदि शर्त है तो कथन अन्यथा कथन |
  ...
शर्त → ...


कुछ अस्पष्ट वाक्यांश संरचनाएँ प्रकट हो सकती हैं। इजहार
नियमों से युक्त ग्रामर में<syntaxhighlight lang="abl">
यदि a तो यदि b तो s अन्य s2
Statement → if Condition then Statement |
किसी भी रूप में पार्स किया जा सकता है
            if Condition then Statement else Statement |
यदि a है तो आरंभ करें यदि b है तो s समाप्त करें अन्यथा s2
            ...
या जैसे
Condition → ...
यदि a तो आरंभ यदि b तो s अन्यथा s2 समाप्त
</syntaxhighlight>कुछ एम्बिगुयस वाक्यांश संरचनाएँ प्रकट हो सकती हैं। <syntaxhighlight>
इस पर निर्भर करता है कि क्या <code>else</code> पहले से जुड़ा है <code>if</code> या दूसरा <code>if</code>.
if a then if b then s else s2
</syntaxhighlight>किसी भी रूप में पार्स किया जा सकता है<syntaxhighlight>
if a then begin if b then s end else s2
</syntaxhighlight>या जैसे<syntaxhighlight>
if a then begin if b then s else s2 end
</syntaxhighlight>इस पर निर्भर करता है कि क्या <code>else</code> पहले से जुड़ा है <code>if</code> या दूसरा <code>if</code>.


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


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


उदाहरण के लिए, सरल व्याकरण
उदाहरण के लिए, सरल ग्रामर<syntaxhighlight>
एस → ए + ए
S → A + A
ए → 0 | 1
A → 0 | 1
भाषा के लिए एक स्पष्ट व्याकरण है { 0+0, 0+1, 1+0, 1+1 }। हालाँकि इन चार तारों में से प्रत्येक में केवल एक बाईं ओर की व्युत्पत्ति है, उदाहरण के लिए, इसकी दो अलग-अलग व्युत्पत्तियाँ हैं
एस संदर्भ-मुक्त व्याकरण#नियम अनुप्रयोग|⇒ ए + ए ⇒ 0 + ए ⇒ 0 + 0
और
एस ⇒ ए + ए ⇒ ए + 0 ⇒ 0 + 0
केवल पूर्व व्युत्पत्ति ही सबसे बाईं ओर है।


==अस्पष्ट व्याकरणों को पहचानना==
</syntaxhighlight>लैंग्वेज के लिए स्पष्ट ग्रामर है { 0+0, 0+1, 1+0, 1+1 }। चूँकि इन चार तारों में से प्रत्येक में केवल बाईं ओर की व्युत्पत्ति है, उदाहरण के लिए, इसकी दो भिन्न-भिन्न व्युत्पत्तियाँ हैं<syntaxhighlight>
एक मनमाना व्याकरण अस्पष्ट है या नहीं इसकी [[निर्णय समस्या]] [[अनिर्णीत समस्या]] है क्योंकि यह दिखाया जा सकता है कि यह [[पोस्ट पत्राचार समस्या]] के बराबर है।<ref>{{cite book |last1=Hopcroft |first1=John |authorlink1=John Hopcroft |last2=Motwani |first2=Rajeev |authorlink2=Rajeev Motwani |last3=Ullman |first3=Jeffrey |authorlink3=Jeffrey Ullman |title=[[Introduction to automata theory, languages, and computation]] |edition=2nd |date=2001 |publisher=Addison-Wesley |isbn = 0-201-44124-1 | at = Theorem 9.20, pp. 405–406}}</ref> कम से कम, संदर्भ-मुक्त व्याकरणों की अस्पष्टता का पता लगाने के लिए कुछ अर्ध-निर्णायक | अर्ध-निर्णय प्रक्रिया को लागू करने वाले उपकरण मौजूद हैं।<ref>{{cite conference | last1 = Axelsson | first1 = Roland | last2 = Heljanko | first2 = Keijo | last3 = Lange | first3 = Martin | year = 2008 | title = वृद्धिशील SAT सॉल्वर का उपयोग करके संदर्भ-मुक्त व्याकरण का विश्लेषण| book-title = Proceedings of the 35th [[International Colloquium on Automata, Languages and Programming]] (ICALP'08), Reykjavik, Iceland | series = [[Lecture Notes in Computer Science]] | volume = 5126 | pages = 410–422 | publisher = Springer-Verlag | doi = 10.1007/978-3-540-70583-3_34 | isbn = 978-3-540-70582-6 | url = http://www.tcs.hut.fi/~kepa/publications/AxelssonHeljankoLange-ICALP08.pdf }}</ref>
S ⇒ A + A ⇒ 0 + A ⇒ 0 + 0
संदर्भ-मुक्त व्याकरण को पार्स करने की दक्षता इसे स्वीकार करने वाले ऑटोमेटन द्वारा निर्धारित की जाती है। नियतात्मक संदर्भ-मुक्त व्याकरण [[नियतात्मक पुशडाउन ऑटोमेटा]] द्वारा स्वीकार किए जाते हैं और इन्हें रैखिक समय में पार्स किया जा सकता है, उदाहरण के लिए [[एलआर पार्सर]] द्वारा।<ref>{{Cite journal | last1 = Knuth | first1 = D. E. | authorlink = Donald Knuth | title = भाषाओं के बाएँ से दाएँ अनुवाद पर| doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | doi-access = free }}</ref> वे [[संदर्भ-मुक्त व्याकरण]]ों का एक सख्त उपसमूह हैं, जिन्हें [[पुशडाउन ऑटोमेटा]] द्वारा स्वीकार किया जाता है और बहुपद समय में पार्स किया जा सकता है, उदाहरण के लिए CYK एल्गोरिदम द्वारा।
</syntaxhighlight>और<syntaxhighlight>
S ⇒ A + A ⇒ A + 0 ⇒ 0 + 0
</syntaxhighlight>केवल पूर्व व्युत्पत्ति ही सबसे बाईं ओर है।


असंदिग्ध संदर्भ-मुक्त व्याकरण गैर-नियतात्मक हो सकते हैं। उदाहरण के लिए, 0 और 1 की वर्णमाला पर सम-लंबाई वाले [[विलोमपद]] की भाषा में स्पष्ट संदर्भ-मुक्त व्याकरण S → 0S0 | 1एस1 | ε. इस भाषा की एक मनमानी स्ट्रिंग को पहले उसके सभी प्रतीकों को पढ़े बिना पार्स नहीं किया जा सकता है, जिसका अर्थ है कि एक पुशडाउन ऑटोमेटन को अर्ध-पार्स की गई स्ट्रिंग की विभिन्न संभावित लंबाई को समायोजित करने के लिए वैकल्पिक राज्य परिवर्तनों का प्रयास करना होगा।<ref>{{cite book |last1=Hopcroft |first1=John |authorlink1=John Hopcroft |last2=Motwani |first2=Rajeev |authorlink2=Rajeev Motwani |last3=Ullman |first3=Jeffrey |authorlink3=Jeffrey Ullman |title=[[Introduction to automata theory, languages, and computation]] |edition=2nd |date=2001 |publisher=Addison-Wesley |isbn = 0-201-44124-1 |pages=249–253}}</ref> फिर भी, व्[[ YACC ]]रण की अस्पष्टता को दूर करने से एक नियतात्मक संदर्भ-मुक्त व्याकरण उत्पन्न हो सकता है और इस प्रकार अधिक कुशल पार्सिंग की अनुमति मिल सकती है। वाईएसीसी जैसे कंपाइलर जनरेटर में कुछ प्रकार की अस्पष्टता को हल करने की विशेषताएं शामिल हैं, जैसे कि प्राथमिकता और सहयोगीता बाधाओं का उपयोग करना।
==एम्बिगुयस ग्रामर को पहचानना==
एक अनैतिक ग्रामर एम्बिगुयस है या नहीं इसकी [[निर्णय समस्या]] [[अनिर्णीत समस्या]] है क्योंकि यह दिखाया जा सकता है कि यह [[पोस्ट पत्राचार समस्या|पोस्ट कॉरेस्पोंडेंस समस्या]] के सामान्य है।<ref>{{cite book |last1=Hopcroft |first1=John |authorlink1=John Hopcroft |last2=Motwani |first2=Rajeev |authorlink2=Rajeev Motwani |last3=Ullman |first3=Jeffrey |authorlink3=Jeffrey Ullman |title=[[Introduction to automata theory, languages, and computation]] |edition=2nd |date=2001 |publisher=Addison-Wesley |isbn = 0-201-44124-1 | at = Theorem 9.20, pp. 405–406}}</ref> कम से कम, कांटेक्स्ट-फ्री ग्रामर की एम्बिगुयस का पता लगाने के लिए कुछ अर्ध-निर्णायक या अर्ध-निर्णय प्रक्रिया को प्रयुक्त करने वाले उपकरण उपस्थित हैं।<ref>{{cite conference | last1 = Axelsson | first1 = Roland | last2 = Heljanko | first2 = Keijo | last3 = Lange | first3 = Martin | year = 2008 | title = वृद्धिशील SAT सॉल्वर का उपयोग करके संदर्भ-मुक्त व्याकरण का विश्लेषण| book-title = Proceedings of the 35th [[International Colloquium on Automata, Languages and Programming]] (ICALP'08), Reykjavik, Iceland | series = [[Lecture Notes in Computer Science]] | volume = 5126 | pages = 410–422 | publisher = Springer-Verlag | doi = 10.1007/978-3-540-70583-3_34 | isbn = 978-3-540-70582-6 | url = http://www.tcs.hut.fi/~kepa/publications/AxelssonHeljankoLange-ICALP08.pdf }}</ref>


==स्वाभाविक रूप से अस्पष्ट भाषाएँ==
कांटेक्स्ट-फ्री ग्रामर को पार्स करने की दक्षता इसे स्वीकार करने वाले ऑटोमेटन द्वारा निर्धारित की जाती है। डेटर्मिनिस्टिक कांटेक्स्ट-फ्री ग्रामर [[नियतात्मक पुशडाउन ऑटोमेटा|डेटर्मिनिस्टिक पुशडाउन ऑटोमेटा]] द्वारा स्वीकार किए जाते हैं और इन्हें रैखिक समय में पार्स किया जा सकता है, उदाहरण के लिए [[एलआर पार्सर]] द्वारा <ref>{{Cite journal | last1 = Knuth | first1 = D. E. | authorlink = Donald Knuth | title = भाषाओं के बाएँ से दाएँ अनुवाद पर| doi = 10.1016/S0019-9958(65)90426-2 | journal = Information and Control | volume = 8 | issue = 6 | pages = 607–639 | date = July 1965 | doi-access = free }}</ref> वह [[संदर्भ-मुक्त व्याकरण|कांटेक्स्ट-फ्री]] ग्रामर का सख्त उपसमूह हैं, जिन्हें [[पुशडाउन ऑटोमेटा]] द्वारा स्वीकार किया जाता है और बहुपद समय में पार्स किया जा सकता है, उदाहरण के लिए CYK एल्गोरिदम द्वारा प्रयोग इया जाता है।
जबकि कुछ संदर्भ-मुक्त भाषाएँ (स्ट्रिंग का सेट जो व्याकरण द्वारा उत्पन्न किया जा सकता है) में अस्पष्ट और स्पष्ट व्याकरण दोनों होते हैं, वहीं संदर्भ-मुक्त भाषाएँ मौजूद होती हैं जिनके लिए कोई भी स्पष्ट संदर्भ-मुक्त व्याकरण मौजूद नहीं हो सकता है। ऐसी भाषाओं को स्वाभाविक रूप से अस्पष्ट कहा जाता है।


कोई स्वाभाविक रूप से अस्पष्ट नियमित भाषाएँ नहीं हैं।<ref>{{Cite journal |last1=Book |first1=R. |last2=Even |first2=S. |last3=Greibach |first3=S. |last4=Ott |first4=G. |date=Feb 1971 |title=रेखांकन और अभिव्यक्ति में अस्पष्टता|url=http://dx.doi.org/10.1109/t-c.1971.223204 |journal=IEEE Transactions on Computers |volume=C-20 |issue=2 |pages=149–153 |doi=10.1109/t-c.1971.223204 |s2cid=20676251 |issn=0018-9340}}</ref><ref>{{Cite web |title=formal languages - Can regular expressions be made unambiguous? |url=https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous |access-date=2023-02-23 |website=MathOverflow |language=en}}</ref>
अनएम्बिगुयस कांटेक्स्ट-फ्री ग्रामर नॉन-डेटर्मिनिस्टिक हो सकते हैं। उदाहरण के लिए, 0 और 1 की वर्णमाला पर सम-लंबाई वाले [[विलोमपद]] की लैंग्वेज में स्पष्ट कांटेक्स्ट-फ्री ग्रामर S → 0S0 1S1 ε. इस लैंग्वेज की अनैतिक स्ट्रिंग को पहले उसके सभी प्रतीकों को पढ़े बिना पार्स नहीं किया जा सकता है, जिसका अर्थ है कि पुशडाउन ऑटोमेटन को अर्ध-पार्स की गई स्ट्रिंग की विभिन्न संभावित लंबाई को समायोजित करने के लिए वैकल्पिक राज्य परिवर्तनों का प्रयास करता है।<ref>{{cite book |last1=Hopcroft |first1=John |authorlink1=John Hopcroft |last2=Motwani |first2=Rajeev |authorlink2=Rajeev Motwani |last3=Ullman |first3=Jeffrey |authorlink3=Jeffrey Ullman |title=[[Introduction to automata theory, languages, and computation]] |edition=2nd |date=2001 |publisher=Addison-Wesley |isbn = 0-201-44124-1 |pages=249–253}}</ref> फिर भी, [[ YACC |YACC]] रण की एम्बिगुयस को दूर करने से डेटर्मिनिस्टिक कांटेक्स्ट-फ्री ग्रामर उत्पन्न हो सकता है और इस प्रकार अधिक कुशल पार्सिंग की अनुमति मिल सकती है। वाईएसीसी जैसे कंपाइलर जनरेटर में कुछ प्रकार की एम्बिगुयस को हल करने की विशेषताएं सम्मिलित हैं, जैसे कि प्राथमिकता और सहयोगीता बाधाओं का उपयोग करता है।
स्वाभाविक रूप से अस्पष्ट संदर्भ-मुक्त भाषाओं का अस्तित्व 1961 में [[ रोहित जीवणलाल पारीख |रोहित जीवणलाल पारीख]] द्वारा एमआईटी शोध रिपोर्ट में पारिख के प्रमेय के साथ सिद्ध किया गया था।<ref>{{cite book | last = Parikh | first = Rohit | title = भाषा उत्पन्न करने वाले उपकरण| publisher = Quarterly Progress Report, Research Laboratory of Electronics, MIT | date = January 1961}}</ref> भाषा <math>\{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\}</math> स्वाभाविक रूप से अस्पष्ट है.<ref>{{Cite journal |last=Parikh |first=Rohit J. |date=1966-10-01 |title=प्रसंग-मुक्त भाषाओं पर|url=https://doi.org/10.1145/321356.321364 |journal=Journal of the ACM |volume=13 |issue=4 |pages=570–581 |doi=10.1145/321356.321364 |s2cid=12263468 |issn=0004-5411}} Here: Theorem 3.</ref>
ओग्डेन की लेम्मा<ref>{{Cite journal |last=Ogden |first=William |date=Sep 1968 |title=अंतर्निहित अस्पष्टता साबित करने के लिए एक उपयोगी परिणाम|url=http://dx.doi.org/10.1007/bf01694004 |journal=Mathematical Systems Theory |volume=2 |issue=3 |pages=191–194 |doi=10.1007/bf01694004 |s2cid=13197551 |issn=0025-5661}}</ref> यह साबित करने के लिए इस्तेमाल किया जा सकता है कि कुछ संदर्भ-मुक्त भाषाएँ, जैसे <math>\{a^nb^mc^m | m, n \geq 1\} \cup \{a^mb^mc^n | m, n \geq 1\}</math>, स्वाभाविक रूप से अस्पष्ट हैं। प्रमाण के लिए ओग्डेन की लेम्मा#अंतर्निहित अस्पष्टता देखें।


का संघ <math>\{a^n b^m c^m d^n \mid n, m > 0\}</math> साथ <math>\{a^n b^n c^m d^m \mid n, m > 0\}</math> स्वाभाविक रूप से अस्पष्ट है. यह सेट संदर्भ-मुक्त है, क्योंकि दो संदर्भ-मुक्त भाषाओं का मिलन हमेशा संदर्भ-मुक्त होता है। लेकिन {{harvtxt|Hopcroft|Ullman|1979}} इस बात का प्रमाण दें कि इस संघ भाषा के लिए कोई भी संदर्भ-मुक्त व्याकरण रूप के तारों को स्पष्ट रूप से पार्स नहीं कर सकता है <math>a^n b^n c^n d^n, (n > 0)</math>.<ref>p.99-103, Sect.4.7</ref>
==स्वाभाविक रूप से एम्बिगुयस लैंग्वेज==
अधिक उदाहरण, और संदर्भ-मुक्त भाषाओं की अंतर्निहित अस्पष्टता को साबित करने के लिए तकनीकों की एक सामान्य समीक्षा, बैसिनो और निकौड (2011) द्वारा दी गई है।<ref>{{Cite web |author=Fredérique Bassino and Cyril Nicaud |date=December 16, 2011 |title=Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages |url=https://algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf |url-status=live |archive-url=https://web.archive.org/web/20220925135141/http://algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf |archive-date=2022-09-25}}</ref>
जबकि कुछ कांटेक्स्ट-फ्री लैंग्वेज (स्ट्रिंग का सेट जो ग्रामर द्वारा उत्पन्न किया जा सकता है) में एम्बिगुयस और स्पष्ट ग्रामर दोनों होते हैं, वहीं कांटेक्स्ट-फ्री लैंग्वेज उपस्थित होती हैं जिनके लिए कोई भी स्पष्ट कांटेक्स्ट-फ्री ग्रामर उपस्थित नहीं हो सकता है। ऐसी लैंग्वेज को स्वाभाविक रूप से एम्बिगुयस कहा जाता है।


कोई स्वाभाविक रूप से एम्बिगुयस रेगुलर लैंग्वेज नहीं हैं।<ref>{{Cite journal |last1=Book |first1=R. |last2=Even |first2=S. |last3=Greibach |first3=S. |last4=Ott |first4=G. |date=Feb 1971 |title=रेखांकन और अभिव्यक्ति में अस्पष्टता|url=http://dx.doi.org/10.1109/t-c.1971.223204 |journal=IEEE Transactions on Computers |volume=C-20 |issue=2 |pages=149–153 |doi=10.1109/t-c.1971.223204 |s2cid=20676251 |issn=0018-9340}}</ref><ref>{{Cite web |title=formal languages - Can regular expressions be made unambiguous? |url=https://mathoverflow.net/questions/45149/can-regular-expressions-be-made-unambiguous |access-date=2023-02-23 |website=MathOverflow |language=en}}</ref> स्वाभाविक रूप से एम्बिगुयस कांटेक्स्ट-फ्री लैंग्वेज का अस्तित्व 1961 में [[ रोहित जीवणलाल पारीख |रोहित पारीख]] द्वारा एमआईटी शोध रिपोर्ट में पारिख के प्रमेय के साथ सिद्ध किया गया था।<ref>{{cite book | last = Parikh | first = Rohit | title = भाषा उत्पन्न करने वाले उपकरण| publisher = Quarterly Progress Report, Research Laboratory of Electronics, MIT | date = January 1961}}</ref> लैंग्वेज <math>\{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\}</math> स्वाभाविक रूप से एम्बिगुयस है.<ref>{{Cite journal |last=Parikh |first=Rohit J. |date=1966-10-01 |title=प्रसंग-मुक्त भाषाओं पर|url=https://doi.org/10.1145/321356.321364 |journal=Journal of the ACM |volume=13 |issue=4 |pages=570–581 |doi=10.1145/321356.321364 |s2cid=12263468 |issn=0004-5411}} Here: Theorem 3.</ref>


ओग्डेन की लेम्मा <ref>{{Cite journal |last=Ogden |first=William |date=Sep 1968 |title=अंतर्निहित अस्पष्टता साबित करने के लिए एक उपयोगी परिणाम|url=http://dx.doi.org/10.1007/bf01694004 |journal=Mathematical Systems Theory |volume=2 |issue=3 |pages=191–194 |doi=10.1007/bf01694004 |s2cid=13197551 |issn=0025-5661}}</ref> यह सिद्ध करने के लिए उपयोग किया जा सकता है कि कुछ कांटेक्स्ट-फ्री लैंग्वेज, जैसे कि <math>\{a^nb^mc^m | m, n \geq 1\} \cup \{a^mb^mc^n | m, n \geq 1\}</math>, स्वाभाविक रूप से अस्पष्ट हैं। प्रमाण के लिए यह पृष्ठ देखें.
यूनियन <math>\{a^n b^m c^m d^n \mid n, m > 0\}</math> साथ <math>\{a^n b^n c^m d^m \mid n, m > 0\}</math> स्वाभाविक रूप से एम्बिगुयस है. यह सेट कांटेक्स्ट-फ्री है, क्योंकि दो कांटेक्स्ट-फ्री लैंग्वेज का मिलन सदैव कांटेक्स्ट-फ्री होता है। किन्तु {{harvtxt|हॉपक्रॉफ्ट|उल्मन|1979}} इस बात का प्रमाण दें कि इस यूनियन लैंग्वेज के लिए कोई भी कांटेक्स्ट-फ्री ग्रामर रूप के तारों <math>a^n b^n c^n d^n, (n > 0)</math> को स्पष्ट रूप से पार्स नहीं कर सकता है.<ref>p.99-103, Sect.4.7</ref>
अधिक उदाहरण, और कांटेक्स्ट-फ्री लैंग्वेज की अंतर्निहित एम्बिगुयस को सिद्ध करने के लिए तकनीकों की सामान्य समीक्षा, बैसिनो और निकौड (2011) द्वारा दी गई है।<ref>{{Cite web |author=Fredérique Bassino and Cyril Nicaud |date=December 16, 2011 |title=Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages |url=https://algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf |url-status=live |archive-url=https://web.archive.org/web/20220925135141/http://algo.inria.fr/pfac/PFAC/Program_files/nicaud.pdf |archive-date=2022-09-25}}</ref>
==यह भी देखें==
==यह भी देखें==
*[[जीएलआर पार्सर]], अस्पष्ट और गैर-नियतात्मक व्याकरणों के लिए एक प्रकार का पार्सर
*[[जीएलआर पार्सर]], एम्बिगुयस और नॉन-डेटर्मिनिस्टिक ग्रामर के लिए एक प्रकार का पार्सर
*[[चार्ट पार्सर]], अस्पष्ट व्याकरण के लिए एक अन्य प्रकार का पार्सर
*[[चार्ट पार्सर]], एम्बिगुयस ग्रामर के लिए अन्य प्रकार का पार्सर
* [[वाक्यात्मक अस्पष्टता]]
* [[वाक्यात्मक अस्पष्टता|सिंटेक्टिक एम्बिगुयस]]


==संदर्भ==
==कांटेक्स्ट==
<references/>
<references/>


Line 163: Line 163:
  }}
  }}
* {{cite journal |last1=Brabrand |first1=Claus |last2=Giegerich |first2=Robert |last3=Møller |first3=Anders |date=March 2010 |title=Analyzing Ambiguity of Context-Free Grammars  |journal=Science of Computer Programming |volume=75 |issue=3 |pages=176–191 |publisher=Elsevier |doi=10.1016/j.scico.2009.11.002 |citeseerx=10.1.1.86.3118 }}
* {{cite journal |last1=Brabrand |first1=Claus |last2=Giegerich |first2=Robert |last3=Møller |first3=Anders |date=March 2010 |title=Analyzing Ambiguity of Context-Free Grammars  |journal=Science of Computer Programming |volume=75 |issue=3 |pages=176–191 |publisher=Elsevier |doi=10.1016/j.scico.2009.11.002 |citeseerx=10.1.1.86.3118 }}
==टिप्पणियाँ==
==टिप्पणियाँ==
{{reflist|group=note}}
{{reflist|group=note}}
==बाहरी संबंध==
==बाहरी संबंध==
*[http://www.brics.dk/grammar dk.brics.grammar] - a grammar ambiguity analyzer.
*[http://www.brics.dk/grammar dk.brics.grammar] - a grammar ambiguity analyzer.
*[https://web.archive.org/web/20110719055512/http://www2.tcs.ifi.lmu.de/~mlange/cfganalyzer/index.html CFGAnalyzer] - tool for analyzing context-free grammars with respect to language universality, ambiguity, and similar properties.
*[https://web.archive.org/web/20110719055512/http://www2.tcs.ifi.lmu.de/~mlange/cfganalyzer/index.html CFGAnalyzer] - tool for analyzing context-free grammars with respect to language universality, ambiguity, and similar properties.
[[Category: औपचारिक भाषाएँ]] [[Category: अनिश्चितता]]


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page]]
[[Category:CS1 English-language sources (en)]]
[[Category:Created On 26/07/2023]]
[[Category:Created On 26/07/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:अनिश्चितता]]
[[Category:औपचारिक भाषाएँ]]

Latest revision as of 10:34, 12 August 2023

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

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

उदाहरण

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

सबसे सरल उदाहरण उस सामान्य लैंग्वेज के लिए निम्नलिखित एम्बिगुयस ग्रामर (प्रारंभ प्रतीक 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 के लिए दो पार्स ट्री हैं:

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

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

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

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

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

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

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

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

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

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

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

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

स्वाभाविक रूप से एम्बिगुयस लैंग्वेज

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

कोई स्वाभाविक रूप से एम्बिगुयस रेगुलर लैंग्वेज नहीं हैं।[8][9] स्वाभाविक रूप से एम्बिगुयस कांटेक्स्ट-फ्री लैंग्वेज का अस्तित्व 1961 में रोहित पारीख द्वारा एमआईटी शोध रिपोर्ट में पारिख के प्रमेय के साथ सिद्ध किया गया था।[10] लैंग्वेज स्वाभाविक रूप से एम्बिगुयस है.[11]

ओग्डेन की लेम्मा [12] यह सिद्ध करने के लिए उपयोग किया जा सकता है कि कुछ कांटेक्स्ट-फ्री लैंग्वेज, जैसे कि , स्वाभाविक रूप से अस्पष्ट हैं। प्रमाण के लिए यह पृष्ठ देखें.

यूनियन साथ स्वाभाविक रूप से एम्बिगुयस है. यह सेट कांटेक्स्ट-फ्री है, क्योंकि दो कांटेक्स्ट-फ्री लैंग्वेज का मिलन सदैव कांटेक्स्ट-फ्री होता है। किन्तु हॉपक्रॉफ्ट & उल्मन (1979) इस बात का प्रमाण दें कि इस यूनियन लैंग्वेज के लिए कोई भी कांटेक्स्ट-फ्री ग्रामर रूप के तारों को स्पष्ट रूप से पार्स नहीं कर सकता है.[13]

अधिक उदाहरण, और कांटेक्स्ट-फ्री लैंग्वेज की अंतर्निहित एम्बिगुयस को सिद्ध करने के लिए तकनीकों की सामान्य समीक्षा, बैसिनो और निकौड (2011) द्वारा दी गई है।[14]

यह भी देखें

कांटेक्स्ट

  1. ↑ Willem J. M. Levelt (2008). औपचारिक भाषाओं और ऑटोमेटा के सिद्धांत का एक परिचय. John Benjamins Publishing. ISBN 978-90-272-3250-2.
  2. ↑ Scott, Elizabeth (April 1, 2008). "प्रारंभिक पहचानकर्ताओं से एसपीपीएफ-शैली पार्सिंग". Electronic Notes in Theoretical Computer Science. 203 (2): 53–67. doi:10.1016/j.entcs.2008.03.044.
  3. ↑ Tomita, Masaru. "An efficient augmented-context-free parsing algorithm." Computational linguistics 13.1-2 (1987): 31-46.
  4. ↑ Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. Theorem 9.20, pp. 405–406. ISBN 0-201-44124-1.
  5. ↑ Axelsson, Roland; Heljanko, Keijo; Lange, Martin (2008). "वृद्धिशील SAT सॉल्वर का उपयोग करके संदर्भ-मुक्त व्याकरण का विश्लेषण" (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP'08), Reykjavik, Iceland. Lecture Notes in Computer Science. Vol. 5126. Springer-Verlag. pp. 410–422. doi:10.1007/978-3-540-70583-3_34. ISBN 978-3-540-70582-6.
  6. ↑ Knuth, D. E. (July 1965). "भाषाओं के बाएँ से दाएँ अनुवाद पर". Information and Control. 8 (6): 607–639. doi:10.1016/S0019-9958(65)90426-2.
  7. ↑ Hopcroft, John; Motwani, Rajeev; Ullman, Jeffrey (2001). Introduction to automata theory, languages, and computation (2nd ed.). Addison-Wesley. pp. 249–253. ISBN 0-201-44124-1.
  8. ↑ Book, R.; Even, S.; Greibach, S.; Ott, G. (Feb 1971). "रेखांकन और अभिव्यक्ति में अस्पष्टता". IEEE Transactions on Computers. C-20 (2): 149–153. doi:10.1109/t-c.1971.223204. ISSN 0018-9340. S2CID 20676251.
  9. ↑ "formal languages - Can regular expressions be made unambiguous?". MathOverflow (in English). Retrieved 2023-02-23.
  10. ↑ Parikh, Rohit (January 1961). भाषा उत्पन्न करने वाले उपकरण. Quarterly Progress Report, Research Laboratory of Electronics, MIT.
  11. ↑ Parikh, Rohit J. (1966-10-01). "प्रसंग-मुक्त भाषाओं पर". Journal of the ACM. 13 (4): 570–581. doi:10.1145/321356.321364. ISSN 0004-5411. S2CID 12263468. Here: Theorem 3.
  12. ↑ Ogden, William (Sep 1968). "अंतर्निहित अस्पष्टता साबित करने के लिए एक उपयोगी परिणाम". Mathematical Systems Theory. 2 (3): 191–194. doi:10.1007/bf01694004. ISSN 0025-5661. S2CID 13197551.
  13. ↑ p.99-103, Sect.4.7
  14. ↑ Fredérique Bassino and Cyril Nicaud (December 16, 2011). "Philippe Flajolet & Analytic Combinatorics: Inherent Ambiguity of Context-Free Languages" (PDF). Archived (PDF) from the original on 2022-09-25.

टिप्पणियाँ

  1. ↑ The following example uses Pascal syntax

बाहरी संबंध

  • dk.brics.grammar - a grammar ambiguity analyzer.
  • CFGAnalyzer - tool for analyzing context-free grammars with respect to language universality, ambiguity, and similar properties.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=अस्पष्ट_व्याकरण&oldid=245090’