पार्सिंग अभिव्यक्ति व्याकरण: Difference between revisions

Revision as of 14:12, 6 August 2023

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

सीएफजी के विपरीत, पीईजी अस्पष्ट नहीं हो सकते है और स्ट्रिंग में बिल्कुल वैध ट्री है या कोई भी नहीं है। यह अनुमान लगाया गया है कि ऐसी संदर्भ-मुक्त लैंग्वेज उपस्तिथ होती हैं जिन्हें पीईजी द्वारा पहचाना नहीं जा सकता है, किन्तु यह अभी तक सिद्ध नहीं हुआ है।^[1] इस प्रकार पीईजी कंप्यूटर लैंग्वेज (और लोजबन जैसी कृत्रिम मानव लैंग्वेज) को पार्स करने के लिए उपयुक्त किया हैं, किन्तु प्राकृतिक लैंग्वेज के लिए नहीं, जहां पीईजी एल्गोरिदम का प्रदर्शन अर्ली एल्गोरिथम जैसे सामान्य सीएफजी एल्गोरिदम के सामान्तर होता है।^[2]

परिलैंग्वेज

सिंटेक्स

औपचारिक रूप से, पार्सिंग अभिव्यक्ति व्याकरण में निम्न सम्मिलित होता हैं।

नॉनटर्मिनल प्रतीकों का परिमित समूह एन होता है ।
टर्मिनल प्रतीकों का परिमित समूह Σ जो एन से असंयुक्त समूह होता है।
पार्सिंग नियमों का सीमित समूह पी होता है ।
अभिव्यक्ति ई_एस को आरंभिक अभिव्यक्ति कहा जाता है।

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

परमाणु पार्सिंग अभिव्यक्ति में निम्न सम्मिलित होते हैं।
- कोई भी टर्मिनल प्रतीक,
- कोई नॉनटर्मिनल प्रतीक, या
- रिक्त स्ट्रिंग ε.
किसी भी उपस्तिथ पार्सिंग अभिव्यक्ति ई, ई₁, को देखते हुए और ई₂, निम्नलिखित ऑपरेटरों का उपयोग करके नई पार्सिंग अभिव्यक्ति का निर्माण किया जा सकता है।
- अनुक्रम: ई₁ ई₂
- ऑर्डर किया गया विकल्प: ई₁ / ई₂ यह है
- शून्य-या-अधिक: ई*
- एक-या-अधिक: ई+
- वैकल्पिक: ई?
- और-विधेय: &ई
- गैर-विधेय: !ई
- समूह: (ई)
तालिका 1 के आधार पर ऑपरेटर प्राथमिकताएँ इस प्रकार होती हैं।^[1]

ऑपरेटर	प्राथमिकता
(ई)	5
&ई, !ई	4
ई*, ई+, ई?	3
ई₁ ई₂	2
ई₁ / ई₂	1

शब्दार्थ

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

इसका परिणाम यह होता है कि यदि सीएफजी को सीधे पीईजी में लिप्यंतरित किया जाता है, तब पूर्व में किसी भी अस्पष्टता को संभावित पार्स में से पार्स ट्री को चुनकर हल किया जाता है। इस प्रकार व्याकरण के विकल्पों को निर्दिष्ट करने के क्रम को सावधानीपूर्वक चुनने से, प्रोग्रामर के पास इस बात पर बहुत अधिक नियंत्रण होता है कि कौन सा पार्स ट्री चुना गया है।

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

पार्सिंग अभिव्यक्तियों की परिचालन व्याख्या

पार्सिंग अभिव्यक्ति व्याकरण में प्रत्येक नॉनटर्मिनल अनिवार्य रूप से पुनरावर्ती वंश पार्सर में पार्सिंग फलन (गणित) का प्रतिनिधित्व करता है, और संबंधित पार्सिंग अभिव्यक्ति फलन वाले "कोड" का प्रतिनिधित्व करती है। प्रत्येक पार्सिंग फलन वैचारिक रूप से इनपुट स्ट्रिंग को अपने तर्क के रूप में लेता है, और निम्नलिखित परिणामों में से उत्पन्न करता है।

सफलता, जिसमें फलन वैकल्पिक रूप से आगे बढ़ सकता है या उसे आपूर्ति की गई इनपुट स्ट्रिंग के या अधिक वर्णों का उपभोग कर सकता है, या
विफलता, जिस स्थिति में कोई इनपुट उपभोग नहीं किया जाता है।

यदि इनपुट स्ट्रिंग का पहला अक्षर उस टर्मिनल से मेल खाता है, और उस स्थिति में इनपुट कैरेक्टर का उपभोग करता है, तब एकल 'टर्मिनल' (अर्थात शाब्दिक) से युक्त परमाणु पार्सिंग अभिव्यक्ति सफल होती है, अन्यथा अभिव्यक्ति विफलता परिणाम उत्पन्न करती है। इस प्रकार 'रिक्त' स्ट्रिंग से युक्त परमाणु पार्सिंग अभिव्यक्ति सदैव किसी भी इनपुट का उपभोग किए बिना तुच्छ रूप से सफल होती है।

सामान्यतः परमाणु पार्सिंग अभिव्यक्ति जिसमें 'नॉनटर्मिनल' ए सम्मिलित है, जिससे कि नॉनटर्मिनल-फलन ए के लिए प्रत्यावर्तन कॉल का प्रतिनिधित्व करता है। इस प्रकार नॉनटर्मिनल वास्तव में किसी भी इनपुट का उपभोग किए बिना सफल हो सकता है, और इसे विफलता से भिन्न परिणाम माना जाता है।

'अनुक्रम' ऑपरेटर ई₁ ई₂ सबसे पहले ई₁ को आमंत्रित करता है, और यदि ई₁ सफल होता है, तब इसके पश्चात् में ई₁ द्वारा उपयोग न किए गए शेष इनपुट स्ट्रिंग पर ई₂ को आमंत्रित करता है, और परिणाम देता है। यदि ई₁ या ई₂ में से कोई भी विफल रहता है, तब अनुक्रम अभिव्यक्ति ई₁ ई₂ विफल हो जाती है (कोई इनपुट नहीं लेता) है।

चॉइस ऑपरेटर ई₁ / ई₂ पहले ई₁ को आमंत्रित करता है, और यदि ई₁ सफल होता है, तब तुरंत अपना परिणाम देता है। अन्यथा, यदि ई₁ विफल हो जाता है, तो चॉइस ऑपरेटर मूल इनपुट स्थिति पर वापस चला जाता है जिस पर उसने ई₁ को क्रियान्वित किया था, लेकिन फिर ई₂ को कॉल करता है, और ई₂ का परिणाम लौटाता है।

शून्य-या-अधिक, एक-या-अधिक, और वैकल्पिक ऑपरेटर क्रमशः अपनी उप-अभिव्यक्ति ई की शून्य या अधिक, या अधिक, या शून्य या लगातार पुनरावृत्ति का उपभोग करते हैं। चूंकि, संदर्भ-मुक्त व्याकरण और नियमित अभिव्यक्तियों के विपरीत, यह ऑपरेटर सदैव लालची एल्गोरिदम का व्यवहार करते हैं, इस प्रकार जितना संभव हो उतना इनपुट लेते हैं और कभी भी पीछे नहीं हटते हैं। (नियमित अभिव्यक्ति मिलानकर्ता लालच से मिलान करके प्रारंभ कर सकते हैं, किन्तु यदि वह मिलान करने में विफल रहते हैं तब पीछे हट जाएंगे और छोटे मिलान करने का प्रयास करते है।) उदाहरण के लिए, अभिव्यक्ति ए* सदैव उतने ही ए का उपभोग करता है, जितने इनपुट स्ट्रिंग में लगातार उपलब्ध हैं, और अभिव्यक्ति (ए* ए) सदैव विफल रहेगी जिससे कि पहला भाग (ए*) दूसरे भाग के मिलान के लिए कभी भी a नहीं छोड़ता है।

और-विधेय अभिव्यक्ति &ई उप-अभिव्यक्ति ई का आह्वान करती है, और यदि ई सफल होती है तब सफल होती है और यदि ई विफल होती है तब विफल हो जाती है, किन्तु किसी भी स्थिति में कभी भी किसी इनपुट का उपभोग नहीं करती है।

गैर-विधेयात्मक अभिव्यक्ति !ई सफल होती है यदि ई विफल हो जाती है और विफल हो जाती है यदि ई सफल हो जाती है, फिर से किसी भी स्थिति में कोई इनपुट नहीं लेता है।

उदाहरण

यह पीईजी होता है जो गणितीय सूत्रों को पहचानता है जो गैर-ऋणात्मक पूर्णांकों पर मूलभूतपांच परिचालनों को प्रयुक्त करते हैं।

Expr    ← Sum
Sum     ← Product (('+' / '-') Product)*
Product ← Power (('*' / '/') Power)*
Power   ← Value ('^' Power)?
Value   ← [0-9]+ / '(' Expr ')'

उपरोक्त उदाहरण में, टर्मिनल प्रतीक पाठ के वर्ण होते हैं, जिन्हें एकल उद्धरण चिह्नों में वर्णों द्वारा दर्शाया गया है, जैसे '(' और ')'. सीमा [0-9] से दस वर्णों '0' को '9' के लिए शॉर्टकट होता है। (यह रेंज सिंटैक्स रेगुलर एक्सप्रेशन द्वारा उपयोग किए जाने वाले सिंटैक्स के समान है।) नॉनटर्मिनल प्रतीक वह हैं जो अन्य नियमों मूल्य, पावर, उत्पाद, योग और एक्सप्र तक विस्तारित होते हैं। ध्यान दीजिए कि नियम सम और प्रोडक्ट इन परिचालनों की वांछित बाईं-संबद्धता की ओर नहीं ले जाते हैं (वह सहयोगीता से बिल्कुल भी नहीं निपटते हैं, और इसे पार्सिंग के पश्चात् पोस्ट-प्रोसेसिंग चरण में संभालना पड़ता है), और पावर नियम (दाईं ओर स्वयं को संदर्भित करके) प्रतिपादक की वांछित दाईं-संबद्धता का परिणाम देता है। इस प्रकार यह भी ध्यान दीजिए कि नियम पसंद होता है Sum ← Sum (('+' / '-') Product)? (वाम-साहचर्य प्राप्त करने के इरादे से) अनंत पुनरावृत्ति का कारण बनता है, इसलिए इसे व्याकरण में व्यक्त किए जाने के अतिरिक्त व्यवहार में उपयोग नहीं किया जा सकता है।

निम्नलिखित पुनरावर्ती नियम मानक सी-शैली यदि/तब/अन्य कथनों से इस प्रकार मेल खाता है कि 'आई' ऑपरेटर की अंतर्निहित प्राथमिकता के कारण वैकल्पिक अन्यथा खंड सदैव अंतरतम "यदि" से बंध जाता है। (संदर्भ-मुक्त व्याकरण में, यह निर्माण क्लासिक डेंगलिंग को जन्म देता है।)

S ← 'if' C 'then' S 'else' S / 'if' C 'then' S

निम्नलिखित पुनरावर्ती नियम पास्कल-शैली नेस्टेड टिप्पणी सिंटैक्स से मेल खाता है, (* which can (* nest *) like this *). टिप्पणी चिह्न उन्हें पीईजी ऑपरेटरों से भिन्न करने के लिए एकल उद्धरण चिह्नों में दिखाई देते हैं।

Begin ← '(*'
End   ← '*)'
C     ← Begin N* End
N     ← C / (!Begin !End Z)
Z     ← any single character

पार्सिंग अभिव्यक्ति फू &(बार) टेक्स्ट फू से मेल खाता है और उपभोग करता है किन्तु केवल तभी जब टेक्स्ट बार इसके पश्चात् आता है। इस प्रकार पार्सिंग अभिव्यक्ति फू !(बार) टेक्स्ट फू से मेल खाता है किन्तु केवल तब जब टेक्स्ट बार इसका अनुसरण नहीं करता है। इजहार !(a+ b) a एकल ए से मेल खाता है, किन्तु केवल तभी जब यह ए के पश्चात् बी के इच्छानुसार से लंबे अनुक्रम का भाग नहीं होता है।

पार्सिंग अभिव्यक्ति ('a'/'b')* ए और बी के अनैतिक-लंबाई अनुक्रम से मेल खाता है और उपभोग करता है। इस प्रकार औपचारिक व्याकरण# व्याकरण का वाक्य-विन्यास S ← 'a' ''S''? 'b' सरल संदर्भ-मुक्त मिलान लैंग्वेज का वर्णन करता है $\{a^{n}b^{n}:n\geq 1\}$ .

निम्नलिखित पार्सिंग अभिव्यक्ति व्याकरण क्लासिक गैर-संदर्भ-मुक्त लैंग्वेज का वर्णन करता है $\{a^{n}b^{n}c^{n}:n\geq 1\}$ :

S ← &(A 'c') 'a'+ B !.
A ← 'a' A? 'b'
B ← 'b' B? 'c'

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

किसी भी पार्सिंग अभिव्यक्ति व्याकरण को सीधे पुनरावर्ती वंश पार्सर में परिवर्तित किया जा सकता है।^[3] चूँकि, व्याकरण की औपचारिकता द्वारा प्रदान की जाने वाली असीमित पार्सिंग लुकहेड क्षमता के कारण, परिणामी पार्सर सबसे खराब स्थिति में घातीय समय प्रदर्शन प्रदर्शित कर सकता है।

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

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

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

लाभ

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

जैसा कि ऊपर वर्णित है, अतः किसी भी पीईजी को पैक्रैट पार्सर का उपयोग करके रैखिक समय में पार्स किया जा सकता है।

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

हानि

मेमोरी खपत

पीईजी पार्सिंग सामान्यतः पैक्रैट पार्सिंग के माध्यम से किया जाता है, जो अनावश्यक पार्सिंग चरणों को समाप्त करने के लिए मेमोइज़ेशन का उपयोग करता है।^[5]^[6] इस प्रकार पैकराट पार्सिंग के लिए एलआर पार्सर की भांति पार्स ट्री की गहराई के अतिरिक्त कुल इनपुट आकार के अनुपातिक भंडारण की आवश्यकता होती है। यह अनेक डोमेन में महत्वपूर्ण अंतर है। उदाहरण के लिए, हाथ से लिखे गए स्रोत कोड में प्रोग्राम की लंबाई से स्वतंत्र प्रभावी रूप से स्थिर अभिव्यक्ति नेस्टिंग गहराई होती है - निश्चित गहराई से परे नेस्टेड अभिव्यक्तियाँ पुनः सक्रिय हो जाती हैं।

कुछ व्याकरणों और कुछ इनपुटों के लिए, पार्स ट्री की गहराई इनपुट आकार के समानुपाती हो सकती है,^[7]

इसलिए एलआर पार्सर और पैक्रैट पार्सर दोनों में समान रूप से सबसे खराब स्थिति वाला स्पर्शोन्मुख प्रदर्शन दिखाई देता है। इस प्रकार अधिक त्रुटिहीन विश्लेषण पार्स ट्री की गहराई को इनपुट आकार से भिन्न ध्यान में रखता है। यह उस स्थिति के समान होता है जो ग्राफ एल्गोरिदम में उत्पन्न होती है। सामान्यतः बेलमैन-फोर्ड एल्गोरिदम और फ़्लॉइड-वॉर्शल एल्गोरिदम का चलने का समय समान प्रतीत होता है ( $O(|V|^{3})$ ) यदि केवल शीर्षों की संख्या पर विचार किया जाता है। चूँकि, अधिक त्रुटिहीन विश्लेषण जो भिन्न पैरामीटर के रूप में किनारों की संख्या को ध्यान में रखता है, अतः बेलमैन-फोर्ड एल्गोरिदम को समय निर्दिष्ट करता है $O(|V|*|E|)$ , जो विरल ग्राफ़ के लिए द्विघात $|E|\in O(|V|)$ है।

अप्रत्यक्ष बायाँ प्रत्यावर्तन

खूंटी को सुगठित कहा जाता है।^[1] यदि इसमें कोई लेफ्ट-रिकर्सिव नियम नही होता है, अर्थात् ऐसे नियम जो नॉनटर्मिनल को अभिव्यक्ति में विस्तारित करने की अनुमति देते हैं जिसमें वही नॉनटर्मिनल सबसे बाएं प्रतीक के रूप में होता है। इस प्रकार बाएं से दाएं ऊपर से नीचे पार्सर के लिए, ऐसे नियम अनंत प्रतिगमन का कारण बनते हैं, अतः पार्सिंग स्ट्रिंग में आगे बढ़ने के बिना लगातार उसी नॉनटर्मिनल का विस्तार करती है।

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

Value   ← [0-9.]+ / '(' Expr ')'
Product ← Expr (('*' / '/') Expr)*
Sum     ← Expr (('+' / '-') Expr)*
Expr    ← Product / Sum / Value

इस नये व्याकरण में, इसका मिलान ऍक्स्पआर परीक्षण की आवश्यकता है यदि प्रोडक्ट ए मिलान करते समय मेल खाता है प्रोडक्ट यदि कोई हो तब परीक्षण की आवश्यकता है ऍक्स्पआर मेल खाता है। जिससे कि यह शब्द सबसे बाईं ओर दिखाई देता है, यह नियम गोलाकार सबलैंग्वेज बनाते हैं जिसे हल नहीं किया जा सकता है। (जिन वृत्ताकार सबलैंग्वेज को हल किया जा सकता है, वह उपस्तिथ होता हैं - जैसे कि पहले उदाहरण से मूल सूत्रीकरण में - किन्तु ऐसी सबलैंग्वेज के लिए आवश्यक होता है कि वह पैथोलॉजिकल रिकर्सन को प्रदर्शित नही करता है।) चूँकि, लेफ्ट-रिकर्सिव नियमों को सदैव लेफ्ट-रिकर्सन को खत्म करने के लिए फिर से लिखा जा सकता है।^[2]^[8] उदाहरण के लिए, निम्नलिखित बाएँ-पुनरावर्ती सीएफजी नियम:

string-of-a ← string-of-a 'a' | 'a'

प्लस ऑपरेटर का उपयोग करके पीईजी में पुनः लिखा जा सकता है।

string-of-a ← 'a'+

लेफ्ट रिकर्सन अप्रत्यक्ष लेफ्ट-रिकर्सिव नियमों को फिर से लिखने की प्रक्रिया कुछ पैकराट पार्सर्स में समष्टि है, विशेष रूप से जब सिमेंटिक क्रियाएं सम्मिलित होती हैं।

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

अभिव्यंजक शक्ति

पीईजी पैकराट पार्सर्स कुछ स्पष्ट गैर-नियतात्मक सीएफजी नियमों को नहीं पहचान सकते है, जैसे कि निम्नलिखित:^[2]

S ← 'x' S 'x' | 'x'

न तब एलएल(के) और न ही एलआर(के) पार्सिंग एल्गोरिदम इस उदाहरण को पहचानने में सक्षम हैं। चूँकि, इस व्याकरण का उपयोग सीवाईके एल्गोरिथ्म जैसे सामान्य सीएफजी पार्सर द्वारा किया जा सकता है। चूँकि, विचाराधीन लैंग्वेज को इन सभी प्रकार के पार्सर द्वारा पहचाना जा सकता है, जिससे कि यह वास्तव में नियमित लैंग्वेज है (विषम संख्या में एक्स की स्ट्रिंग की)।

संदर्भ-मुक्त लैंग्वेज का ठोस उदाहरण देना खुली समस्या होती है जिसे पार्सिंग अभिव्यक्ति व्याकरण द्वारा पहचाना नहीं जा सकता है।^[1] विशेष रूप से, यह खुला है कि क्या पार्सिंग अभिव्यक्ति व्याकरण पैलिंड्रोम की लैंग्वेज को पहचान सकता है।^[11]

अस्पष्टता का पता लगाना और मेल खाने वाली लैंग्वेज पर नियम क्रम का प्रभाव

इनपुट व्याकरण अस्पष्ट होने पर एलएल(के) और LR(k) पार्सर जनरेटर पूर्ण करने में विफल हो जाते है। सामान्य स्थितियों में यह विशेषता है कि व्याकरण स्पष्ट होने का इरादा रखता है किन्तु दोषपूर्ण होता है। इस प्रकार पीईजी पार्सर जनरेटर अनपेक्षित अस्पष्टताओं को जल्द से जल्द हल करता है, जो इच्छानुसार हो सकता है और आश्चर्यजनक पार्स का कारण बन सकता है।

पीईजी व्याकरण में प्रस्तुतियों का क्रम न केवल अस्पष्टता के समाधान को प्रभावित करता है, किंतु मिलान की गई लैंग्वेज को भी प्रभावित करता है। उदाहरण के लिए, फोर्ड के पेपर में पहले पीईजी उदाहरण पर विचार करते है।^[1] (उदाहरण पेग्ज्स.ओआरजी/ऑनलाइन नोटेशन में पुनः लिखा गया है, और लेबल किया गया है $G_{1}$ और $G_{2}$ ):

$G_{1}$ : A = "a" "b" / "a"
$G_{2}$ : A = "a" / "a" "b"

फोर्ड नोट करता है कि पश्चात् वाले पीईजी नियम में दूसरा विकल्प कभी सफल नहीं होगा जिससे कि पहली पसंद सदैव ली जाती है यदि इनपुट स्ट्रिंग ... 'ए' से प्रारंभ होती है।^[1] विशेष रूप से, $L(G_{1})$ (अर्थात, लैंग्वेज से मेल खाती है $G_{1}$ ) में इनपुट ab सम्मिलित है, किन्तु $L(G_{2})$ नहीं करता। इस प्रकार, पीईजी व्याकरण में नया विकल्प जोड़ने से मिलान की गई लैंग्वेज से स्ट्रिंग्स को हटाया जा सकता है, उदाहरण के लिए $G_{2}$ एकल-उत्पादन व्याकरण में नियम का जोड़ हैA = "a" "b", जिसमें ऐसी स्ट्रिंग है जो मेल नहीं खाती $G_{2}$ .

इसके अतिरिक्त, मिलान के लिए व्याकरण का निर्माण करना $L(G_{1})\cup L(G_{2})$ पीईजी व्याकरण से $G_{1}$ और $G_{2}$ सदैव कोई साधारण काम नहीं होता. यह सीएफजी के बिल्कुल विपरीत है, जिसमें नए उत्पादन को जोड़ने से स्ट्रिंग्स को हटाया नहीं जा सकता है (चूंकि, यह अस्पष्टता के रूप में समस्याएं प्रस्तुतकर सकता है), और (संभावित रूप से अस्पष्ट) व्याकरण $L(G_{1})\cup L(G_{2})$ का निर्माण किया जा सकता है

S → start(G1) | start(G2)

बॉटम-अप पीईजी पार्सिंग

पिका पार्सर^[12] पीईजी नियमों को नीचे से ऊपर और दाएं से बाएं प्रयुक्त करने के लिए गतिशील प्रोग्रामिंग का उपयोग करता है, जो ऊपर से नीचे, बाएं से दाएं के सामान्य पुनरावर्ती वंश क्रम का उलटा है। उल्टे क्रम में पार्स करने से बाएं पुनरावर्ती समस्या का समाधान हो जाता है, जिससे बाएं-पुनरावर्ती नियमों को गैर-बाएं-पुनरावर्ती रूप में दोबारा लिखे बिना सीधे व्याकरण में उपयोग करने की अनुमति मिलती है, और पार्सर पर इष्टतम त्रुटि पुनर्प्राप्ति क्षमताएं भी मिलती हैं, जिसे प्राप्त करना ऐतिहासिक रूप से कठिनाई सिद्ध करना हुआ है। पुनरावर्ती वंश पार्सर्स के लिए।

व्यावहारिक उपयोग

पायथन (प्रोग्रामिंग लैंग्वेज) संदर्भ कार्यान्वयन सीपीथॉन ने एलएल पार्सर|एलएल(1) पार्सर के विकल्प के रूप में संस्करण 3.9 में पीईजी पार्सर प्रस्तुतकिया और संस्करण 3.10 से केवल पीईजी का उपयोग करता है।^[13]

Jq_(प्रोग्रामिंग_लैंग्वेज) पार्सिंग_एक्सप्रेशन_व्याकरण पीईजी से निकटता से संबंधित औपचारिकता का उपयोग करता है।

यह भी देखें

कंपाइलर विवरण लैंग्वेज (सीडीएल)
औपचारिक व्याकरण
नियमित अभिव्यक्ति
ऊपर से नीचे पार्सिंग लैंग्वेज
पार्सर जनरेटर की तुलना
पार्सर संयोजक

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Ford, Bryan (January 2004). "Parsing Expression Grammars: A Recognition Based Syntactic Foundation" (PDF). Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM. pp. 111–122. doi:10.1145/964001.964011. ISBN 1-58113-729-X.
↑ ^2.0 ^2.1 ^2.2 Ford, Bryan (September 2002). "Packrat parsing: simple, powerful, lazy, linear time, functional pearl" (PDF). ACM SIGPLAN Notices. 37 (9). doi:10.1145/583852.581483.
↑ ^3.0 ^3.1 ^3.2 Ford, Bryan (September 2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Thesis). Massachusetts Institute of Technology. Retrieved 2007-07-27.
↑ Merritt, Doug (November 1993). "Transparent Recursive Descent". Usenet group comp.compilers. Retrieved 2009-09-04.
↑ Ford, Bryan. "The Packrat Parsing and Parsing Expression Grammars Page". BFord.info. Retrieved 23 Nov 2010.
↑ Jelliffe, Rick (10 March 2010). "What is a Packrat Parser? What are Brzozowski Derivatives?". Archived from the original on 28 July 2011.
↑ for example, the LISP expression (x (x (x (x ....))))
↑ Aho, A.V.; Sethi, R.; Ullman, J.D. (1986). Compilers: Principles, Techniques, and Tools. Boston, MA, USA: Addison-Wesley Longman. ISBN 0-201-10088-6.
↑ ^9.0 ^9.1 ^9.2 Warth, Alessandro; Douglass, James R.; Millstein, Todd (January 2008). "Packrat Parsers Can Support Left Recursion" (PDF). Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. PEPM '08. ACM. pp. 103–110. doi:10.1145/1328408.1328424. ISBN 9781595939777. Retrieved 2008-10-02.
↑ Steinmann, Ruedi (March 2009). "Handling Left Recursion in Packrat Parsers" (PDF). n.ethz.ch. Archived from the original (PDF) on 2011-07-06.
↑ Loff, Bruno; Moreira, Nelma; Reis, Rogério (2020-02-14). "अभिव्यक्ति व्याकरणों को पार्स करने की कम्प्यूटेशनल शक्ति". arXiv:1902.08272 [cs.FL].
↑ Hutchison, Luke A. D. (2020). "Pika parsing: parsing in reverse solves the left recursion and error recovery problems". arXiv:2005.06444 [cs.PL].
↑ "PEP 617 – New PEG parser for CPython | peps.python.org". peps.python.org. Retrieved 2023-01-16.

बाहरी संबंध

एक्सप्रेशन पार्सर का उपयोग करके स्ट्रिंग एक्सप्रेशन को लैम्ब्डा एक्सप्रेशन में परिवर्तित करना
पैकराट पार्सिंग और पार्सिंग अभिव्यक्ति व्याकरण पृष्ठ
निर्मित लैंग्वेज लोज्बान में काफी बड़ा पीईजी व्याकरण है जो लोज्बान पाठ के स्पष्ट विश्लेषण की अनुमति देता है।
गुइले योजना में पीईजी का उदाहरणात्मक कार्यान्वयन

[For04-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 ^1.6 Ford, Bryan (January 2004). "Parsing Expression Grammars: A Recognition Based Syntactic Foundation" (PDF). Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM. pp. 111–122. doi:10.1145/964001.964011. ISBN 1-58113-729-X.

[pegs-2] 2.0 ^2.1 ^2.2 Ford, Bryan (September 2002). "Packrat parsing: simple, powerful, lazy, linear time, functional pearl" (PDF). ACM SIGPLAN Notices. 37 (9). doi:10.1145/583852.581483.

[ford02-3] 3.0 ^3.1 ^3.2 Ford, Bryan (September 2002). Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking (Thesis). Massachusetts Institute of Technology. Retrieved 2007-07-27.

[merritt01-4] Merritt, Doug (November 1993). "Transparent Recursive Descent". Usenet group comp.compilers. Retrieved 2009-09-04.

[5] Ford, Bryan. "The Packrat Parsing and Parsing Expression Grammars Page". BFord.info. Retrieved 23 Nov 2010.

[6] Jelliffe, Rick (10 March 2010). "What is a Packrat Parser? What are Brzozowski Derivatives?". Archived from the original on 28 July 2011.

[7] r example, the LISP expression (x (x (x (x ....))))

[AhoSethiUllman_1986-8] Aho, A.V.; Sethi, R.; Ullman, J.D. (1986). Compilers: Principles, Techniques, and Tools. Boston, MA, USA: Addison-Wesley Longman. ISBN 0-201-10088-6.

[warth08-9] 9.0 ^9.1 ^9.2 Warth, Alessandro; Douglass, James R.; Millstein, Todd (January 2008). "Packrat Parsers Can Support Left Recursion" (PDF). Proceedings of the 2008 ACM SIGPLAN symposium on Partial evaluation and semantics-based program manipulation. PEPM '08. ACM. pp. 103–110. doi:10.1145/1328408.1328424. ISBN 9781595939777. Retrieved 2008-10-02.

[ruediste09-10] Steinmann, Ruedi (March 2009). "Handling Left Recursion in Packrat Parsers" (PDF). n.ethz.ch. Archived from the original (PDF) on 2011-07-06.

[11] Loff, Bruno; Moreira, Nelma; Reis, Rogério (2020-02-14). "अभिव्यक्ति व्याकरणों को पार्स करने की कम्प्यूटेशनल शक्ति". arXiv:1902.08272 [cs.FL].

[Hut20-12] Hutchison, Luke A. D. (2020). "Pika parsing: parsing in reverse solves the left recursion and error recovery problems". arXiv:2005.06444 [cs.PL].

[13] "PEP 617 – New PEG parser for CPython | peps.python.org". peps.python.org. Retrieved 2023-01-16.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

@@ Line 74: / Line 74: @@
 * विफलता, जिस स्थिति में कोई इनपुट उपभोग नहीं किया जाता है।
-यदि इनपुट स्ट्रिंग का पहला अक्षर उस टर्मिनल से मेल खाता है, और उस स्थिति में इनपुट कैरेक्टर का उपभोग करता है, तब एकल '''<nowiki/>'टर्मिनल'<nowiki/>''' (अर्थात शाब्दिक) से युक्त परमाणु पार्सिंग अभिव्यक्ति सफल होती है, अन्यथा अभिव्यक्ति विफलता परिणाम उत्पन्न करती है। इस प्रकार '''<nowiki/>'रिक्त'''' स्ट्रिंग से युक्त परमाणु पार्सिंग अभिव्यक्ति सदैव किसी भी इनपुट का उपभोग किए बिना तुच्छ रूप से सफल होती है।
+यदि इनपुट स्ट्रिंग का पहला अक्षर उस टर्मिनल से मेल खाता है, और उस स्थिति में इनपुट कैरेक्टर का उपभोग करता है, तब एकल '''<nowiki/>'टर्मिनल'''' (अर्थात शाब्दिक) से युक्त परमाणु पार्सिंग अभिव्यक्ति सफल होती है, अन्यथा अभिव्यक्ति विफलता परिणाम उत्पन्न करती है। इस प्रकार '''<nowiki/>'रिक्त'''' स्ट्रिंग से युक्त परमाणु पार्सिंग अभिव्यक्ति सदैव किसी भी इनपुट का उपभोग किए बिना तुच्छ रूप से सफल होती है।
 सामान्यतः परमाणु पार्सिंग अभिव्यक्ति जिसमें '''<nowiki/>'नॉनटर्मिनल'''' ए सम्मिलित है, जिससे कि नॉनटर्मिनल-फलन ए के लिए [[ प्रत्यावर्तन |प्रत्यावर्तन]] कॉल का प्रतिनिधित्व करता है। इस प्रकार नॉनटर्मिनल वास्तव में किसी भी इनपुट का उपभोग किए बिना सफल हो सकता है, और इसे विफलता से भिन्न परिणाम माना जाता है।
@@ Line 142: / Line 142: @@
 </ref>
-पैक्रैट पार्सर के प्रदर्शन '''का यह विश्लेषण मानता है कि सभी''' याद किए गए परिणामों को रखने के लिए पर्याप्त मेमोरी उपलब्ध है; व्यवहार में, यदि पर्याप्त मेमोरी नहीं है, तब कुछ पार्सिंग फलन को ही इनपुट स्थिति पर से अधिक बार प्रयुक्त करना पड़ सकता है, और परिणामस्वरूप पार्सर को रैखिक समय से अधिक समय लग सकता है।
+पैक्रैट पार्सर के प्रदर्शन का यह विश्लेषण मानता है कि सभी याद किए गए परिणामों को रखने के लिए पर्याप्त मेमोरी उपलब्ध होती है। इस प्रकार व्यवहार में, यदि पर्याप्त मेमोरी नहीं होती है, तब कुछ पार्सिंग फलन को ही इनपुट स्थिति पर से अधिक बार प्रयुक्त करना पड़ सकता है, और परिणामस्वरूप पार्सर को रैखिक समय से अधिक समय लग सकता है।
-पुनरावर्ती वंश पार्सर की तुलना में उत्तम सबसे खराब प्रदर्शन के साथ, अभिव्यक्ति व्याकरण को पार्स करने से [[एलएल पार्सर]] और [[एलआर पार्सर]] बनाना भी संभव है, किन्तु व्याकरण औपचारिकता की असीमित लुकहेड क्षमता तब खो जाती है। इसलिए, पार्सिंग अभिव्यक्ति व्याकरण का उपयोग करके व्यक्त की जा सकने वाली सभी लैंग्वेजओं को एलएल या एलआर पार्सर्स द्वारा पार्स नहीं किया जा सकता है।
+पुनरावर्ती वंश पार्सर की तुलना में उत्तम सबसे खराब प्रदर्शन के साथ, अभिव्यक्ति व्याकरण को पार्स करने से [[एलएल पार्सर]] और [[एलआर पार्सर]] बनाना भी संभव है, किन्तु व्याकरण औपचारिकता की असीमित लुकहेड क्षमता तब विलुप्त हो जाती है। इसलिए, पार्सिंग अभिव्यक्ति व्याकरण का उपयोग करके व्यक्त की जा सकने वाली सभी लैंग्वेज को एलएल या एलआर पार्सर्स द्वारा पार्स नहीं किया जा सकता है।
 == '''लाभ''' ==
-शुद्ध रेगुलर एक्सप्रेशन (अर्थात बैक-रेफरेंस के बिना) की तुलना में, पीईजी सख्ती से अधिक शक्तिशाली होते हैं, किन्तु उन्हें अधिक अधिक मेमोरी की आवश्यकता होती है। उदाहरण के लिए, [[नियमित अभिव्यक्ति]] स्वाभाविक रूप से कोष्ठक के मिलान जोड़े की मनमानी संख्या नहीं पा सकती है, जिससे कि यह पुनरावर्ती नहीं है, किन्तु पीईजी कर सकता है। चूँकि, पीईजी को इनपुट की लंबाई के अनुपात में मेमोरी की मात्रा की आवश्यकता होगी, जबकि रेगुलर एक्सप्रेशन मैचर को केवल स्थिर मात्रा में मेमोरी की आवश्यकता होगी।
+शुद्ध रेगुलर एक्सप्रेशन (अर्थात् बैक-रेफरेंस के बिना) की तुलना में, पीईजी सख्ती से अधिक शक्तिशाली होते हैं, किन्तु उन्हें अधिक मेमोरी की आवश्यकता होती है। उदाहरण के लिए, [[नियमित अभिव्यक्ति]] स्वाभाविक रूप से कोष्ठक के मिलान जोड़े की अनैतिक संख्या नहीं पा सकती है, जिससे कि यह पुनरावर्ती नहीं होती है, किन्तु पीईजी कर सकता है। चूँकि, पीईजी को इनपुट की लंबाई के अनुपात में मेमोरी की मात्रा की आवश्यकता होती है, जबकि रेगुलर एक्सप्रेशन मैचर को केवल स्थिर मात्रा में मेमोरी की आवश्यकता होती है।
-जैसा कि ऊपर वर्णित है, किसी भी पीईजी को पैक्रैट पार्सर का उपयोग करके रैखिक समय में पार्स किया जा सकता है।
+जैसा कि ऊपर वर्णित है, अतः किसी भी पीईजी को पैक्रैट पार्सर का उपयोग करके रैखिक समय में पार्स किया जा सकता है।
-अनेक सीएफजी में अस्पष्टताएं होती हैं, यदि उनका उद्देश्य स्पष्ट लैंग्वेजओं का वर्णन करना हो। C, C++ और Java में लटकती अन्य समस्या इसका उदाहरण है। इन समस्याओं का समाधान अधिकांशतः व्याकरण के बाहर किसी नियम को प्रयुक्त करके किया जाता है। पीईजी में, प्राथमिकता के कारण यह अस्पष्टताएं कभी उत्पन्न नहीं होती हैं।
+सामान्यतः अनेक सीएफजी में अस्पष्टताएं होती हैं, यदि उनका उद्देश्य स्पष्ट लैंग्वेज का वर्णन करता है। इस प्रकार सी, सी++ और जावा में लटकती अन्य समस्या इसका उदाहरण होता है। इन समस्याओं का समाधान अधिकांशतः व्याकरण के बाहर किसी नियम को प्रयुक्त करके किया जाता है। अतः पीईजी में, प्राथमिकता के कारण यह अस्पष्टताएं कभी उत्पन्न नहीं होती हैं।
 =='''हानि''' ==
 === मेमोरी खपत ===
-पीईजी पार्सिंग सामान्यतः पैक्रैट पार्सिंग के माध्यम से किया जाता है, जो मेमोइज़ेशन का उपयोग करता है<ref>{{cite web
+पीईजी पार्सिंग सामान्यतः पैक्रैट पार्सिंग के माध्यम से किया जाता है, जो अनावश्यक पार्सिंग चरणों को समाप्त करने के लिए मेमोइज़ेशन का उपयोग करता है।<ref>{{cite web
 | title = The Packrat Parsing and Parsing Expression Grammars Page
 | first= Bryan |last=Ford
@@ Line 169: / Line 169: @@
 |archive-date= 28 July 2011
 |date=10 March 2010
-}}</ref> अनावश्यक पार्सिंग चरणों को समाप्त करने के लिए। पैकराट पार्सिंग के लिए एलआर पार्सर की तरह पार्स ट्री की गहराई के अतिरिक्त कुल इनपुट आकार के अनुपातिक भंडारण की आवश्यकता होती है। यह अनेक डोमेन में महत्वपूर्ण अंतर है: उदाहरण के लिए, हाथ से लिखे गए स्रोत कोड में प्रोग्राम की लंबाई से स्वतंत्र प्रभावी रूप से स्थिर अभिव्यक्ति नेस्टिंग गहराई होती है - निश्चित गहराई से परे नेस्टेड अभिव्यक्तियाँ पुनः सक्रिय हो जाती हैं।
+}}</ref> इस प्रकार पैकराट पार्सिंग के लिए एलआर पार्सर की भांति पार्स ट्री की गहराई के अतिरिक्त कुल इनपुट आकार के अनुपातिक भंडारण की आवश्यकता होती है। यह अनेक डोमेन में महत्वपूर्ण अंतर है। उदाहरण के लिए, हाथ से लिखे गए स्रोत कोड में प्रोग्राम की लंबाई से स्वतंत्र प्रभावी रूप से स्थिर अभिव्यक्ति नेस्टिंग गहराई होती है - निश्चित गहराई से परे नेस्टेड अभिव्यक्तियाँ पुनः सक्रिय हो जाती हैं।
 कुछ व्याकरणों और कुछ इनपुटों के लिए, पार्स ट्री की गहराई इनपुट आकार के समानुपाती हो सकती है,<ref>for example, the LISP expression (x (x (x (x ....))))</ref>
-इसलिए एलआर पार्सर और पैक्रैट पार्सर दोनों में समान रूप से सबसे खराब स्थिति वाला स्पर्शोन्मुख प्रदर्शन दिखाई देगा। अधिक त्रुटिहीन विश्लेषण पार्स ट्री की गहराई को इनपुट आकार से भिन्न ध्यान में रखेगा। यह उस स्थिति के समान है जो [[ग्राफ एल्गोरिदम]] में उत्पन्न होती है: बेलमैन-फोर्ड एल्गोरिदम और फ़्लॉइड-वॉर्शल एल्गोरिदम का चलने का समय समान प्रतीत होता है (<math>O(|V|^3)</math>) यदि केवल शीर्षों की संख्या पर विचार किया जाए। चूँकि, अधिक त्रुटिहीन विश्लेषण जो भिन्न पैरामीटर के रूप में किनारों की संख्या को ध्यान में रखता है, बेलमैन-फोर्ड एल्गोरिदम को समय निर्दिष्ट करता है <math>O(|V|*|E|)</math>, जो विरल ग्राफ़ के लिए द्विघात है <math>|E| \in O(|V|)</math>.
+इसलिए एलआर पार्सर और पैक्रैट पार्सर दोनों में समान रूप से सबसे खराब स्थिति वाला स्पर्शोन्मुख प्रदर्शन दिखाई देता है। इस प्रकार अधिक त्रुटिहीन विश्लेषण पार्स ट्री की गहराई को इनपुट आकार से भिन्न ध्यान में रखता है। यह उस स्थिति के समान होता है जो [[ग्राफ एल्गोरिदम]] में उत्पन्न होती है। सामान्यतः बेलमैन-फोर्ड एल्गोरिदम और फ़्लॉइड-वॉर्शल एल्गोरिदम का चलने का समय समान प्रतीत होता है (<math>O(|V|^3)</math>) यदि केवल शीर्षों की संख्या पर विचार किया जाता है। चूँकि, अधिक त्रुटिहीन विश्लेषण जो भिन्न पैरामीटर के रूप में किनारों की संख्या को ध्यान में रखता है, अतः बेलमैन-फोर्ड एल्गोरिदम को समय निर्दिष्ट करता है <math>O(|V|*|E|)</math>, जो विरल ग्राफ़ के लिए द्विघात <math>|E| \in O(|V|)</math> है।
 === अप्रत्यक्ष बायाँ प्रत्यावर्तन ===
-खूंटी को सुगठित कहा जाता है<ref name="For04"/>यदि इसमें कोई [[ बायाँ प्रत्यावर्तन |बायाँ प्रत्यावर्तन]] नहीं है|लेफ्ट-रिकर्सिव नियम, अर्थात, ऐसे नियम जो नॉनटर्मिनल को अभिव्यक्ति में विस्तारित करने की अनुमति देते हैं जिसमें वही नॉनटर्मिनल सबसे बाएं प्रतीक के रूप में होता है। बाएं से दाएं ऊपर से नीचे पार्सर के लिए, ऐसे नियम अनंत प्रतिगमन का कारण बनते हैं: पार्सिंग स्ट्रिंग में आगे बढ़ने के बिना लगातार उसी नॉनटर्मिनल का विस्तार करेगी।
+खूंटी को सुगठित कहा जाता है।<ref name="For04"/> यदि इसमें कोई लेफ्ट-रिकर्सिव नियम नही होता है, अर्थात् ऐसे नियम जो नॉनटर्मिनल को अभिव्यक्ति में विस्तारित करने की अनुमति देते हैं जिसमें वही नॉनटर्मिनल सबसे बाएं प्रतीक के रूप में होता है। इस प्रकार बाएं से दाएं ऊपर से नीचे पार्सर के लिए, ऐसे नियम अनंत प्रतिगमन का कारण बनते हैं, अतः पार्सिंग स्ट्रिंग में आगे बढ़ने के बिना लगातार उसी नॉनटर्मिनल का विस्तार करती है।
-इसलिए, पैक्रैट पार्सिंग की अनुमति देने के लिए, बाएं रिकर्सन को समाप्त किया जाना चाहिए। उदाहरण के लिए, उपरोक्त अंकगणितीय व्याकरण में, कुछ नियमों को इधर-उधर करना आकर्षक होगा जिससे कि उत्पादों और योगों के पूर्वता क्रम को पंक्ति में व्यक्त किया जा सके:
+इसलिए, पैक्रैट पार्सिंग की अनुमति देने के लिए, बाएं रिकर्सन को समाप्त किया जाता है। उदाहरण के लिए, उपरोक्त अंकगणितीय व्याकरण में, कुछ नियमों को इधर-उधर करना आकर्षक होता है, जिससे कि उत्पादों और योगों के पूर्वता क्रम को पंक्ति में व्यक्त किया जा सकते है।
 <syntaxhighlight lang="peg">
@@ Line 187: / Line 187: @@
 Expr    ← Product / Sum / Value
 </syntaxhighlight>
-इस नये व्याकरण में, का मिलान <code>Expr</code> परीक्षण की आवश्यकता है यदि a <code>Product</code> ए मिलान करते समय मेल खाता है <code>Product</code> यदि कोई हो तब परीक्षण की आवश्यकता है <code>Expr</code> मेल खाता है. जिससे कि यह शब्द सबसे बाईं ओर दिखाई देता है, यह नियम [[गोलाकार परिभाषा|गोलाकार परिलैंग्वेज]] बनाते हैं जिसे हल नहीं किया जा सकता है। (जिन वृत्ताकार परिलैंग्वेजओं को हल किया जा सकता है, वह उपस्तिथ हैं - जैसे कि पहले उदाहरण से मूल सूत्रीकरण में - किन्तु ऐसी परिलैंग्वेजओं के लिए आवश्यक है कि वह पैथोलॉजिकल रिकर्सन को प्रदर्शित न करें।) चूँकि, लेफ्ट-रिकर्सिव नियमों को सदैव लेफ्ट-रिकर्सन को खत्म करने के लिए फिर से लिखा जा सकता है।<ref name="pegs" /><ref name="AhoSethiUllman 1986">{{cite book |last1=Aho |first1=A.V. |last2=Sethi |first2=R. |last3=Ullman |first3=J.D. |date=1986 |title=Compilers: Principles, Techniques, and Tools |publisher=[[Addison-Wesley Longman]] |place=Boston, MA, USA |url=https://archive.org/details/compilersprincip0000ahoa/ |url-access=registration |isbn=0-201-10088-6}}</ref> उदाहरण के लिए, निम्नलिखित बाएँ-पुनरावर्ती सीएफजी नियम:
+इस नये व्याकरण में, इसका मिलान <code>ऍक्स्पआर</code> परीक्षण की आवश्यकता है यदि  <code>प्रोडक्ट</code> ए मिलान करते समय मेल खाता है <code>प्रोडक्ट</code> यदि कोई हो तब परीक्षण की आवश्यकता है <code>ऍक्स्पआर</code> मेल खाता है। जिससे कि यह शब्द सबसे बाईं ओर दिखाई देता है, यह नियम [[गोलाकार परिभाषा|गोलाकार सबलैंग्वेज]] बनाते हैं जिसे हल नहीं किया जा सकता है। (जिन वृत्ताकार सबलैंग्वेज को हल किया जा सकता है, वह उपस्तिथ होता हैं - जैसे कि पहले उदाहरण से मूल सूत्रीकरण में - किन्तु ऐसी सबलैंग्वेज के लिए आवश्यक होता है कि वह पैथोलॉजिकल रिकर्सन को प्रदर्शित नही करता है।) चूँकि, लेफ्ट-रिकर्सिव नियमों को सदैव लेफ्ट-रिकर्सन को खत्म करने के लिए फिर से लिखा जा सकता है।<ref name="pegs" /><ref name="AhoSethiUllman 1986">{{cite book |last1=Aho |first1=A.V. |last2=Sethi |first2=R. |last3=Ullman |first3=J.D. |date=1986 |title=Compilers: Principles, Techniques, and Tools |publisher=[[Addison-Wesley Longman]] |place=Boston, MA, USA |url=https://archive.org/details/compilersprincip0000ahoa/ |url-access=registration |isbn=0-201-10088-6}}</ref> उदाहरण के लिए, निम्नलिखित बाएँ-पुनरावर्ती सीएफजी नियम:
 <syntaxhighlight lang="peg">
 string-of-a ← string-of-a 'a' | 'a'
 </syntaxhighlight>
-प्लस ऑपरेटर का उपयोग करके पीईजी में पुनः लिखा जा सकता है:
+प्लस ऑपरेटर का उपयोग करके पीईजी में पुनः लिखा जा सकता है।
 <syntaxhighlight lang="peg">
 string-of-a ← 'a'+
 </syntaxhighlight>
-लेफ्ट रिकर्सन#अप्रत्यक्ष लेफ्ट रिकर्सन|अप्रत्यक्ष लेफ्ट-रिकर्सिव नियमों को फिर से लिखने की प्रक्रिया कुछ पैकराट पार्सर्स में समष्टि है, खासकर जब सिमेंटिक क्रियाएं सम्मिलित होती हैं।
+लेफ्ट रिकर्सन अप्रत्यक्ष लेफ्ट-रिकर्सिव नियमों को फिर से लिखने की प्रक्रिया कुछ पैकराट पार्सर्स में समष्टि है, विशेष रूप से जब सिमेंटिक क्रियाएं सम्मिलित होती हैं।
 कुछ संशोधन के साथ, पारंपरिक पैकेट पार्सिंग सीधे बाएं रिकर्सन का समर्थन कर सकता है,<ref name="ford02"/><ref name="warth08">
@@ Line 220: / Line 220: @@
   |archive-date = 2011-07-06
 }}
-</ref> किन्तु ऐसा करने से रैखिक-समय पार्सिंग संपत्ति का हानि होता है<ref name="warth08"/> जो सामान्यतः पहले स्थान पर पीईजी और पैक्रैट पार्सिंग का उपयोग करने का औचित्य है। केवल [[ओमेटा]] पार्सिंग एल्गोरिदम<ref name="warth08"/> अतिरिक्त परिचर समष्टिता के बिना पूर्ण प्रत्यक्ष और अप्रत्यक्ष बाएं रिकर्सन का समर्थन करता है (किन्तु फिर से, रैखिक समय समष्टिता के हानि पर), जबकि सभी [[जीएलआर पार्सर]] बाएं रिकर्सन का समर्थन करते हैं।
+</ref> किन्तु ऐसा करने से रैखिक-समय पार्सिंग संपत्ति का हानि होता है,<ref name="warth08"/> जो सामान्यतः पहले स्थान पर पीईजी और पैक्रैट पार्सिंग का उपयोग करने का औचित्य होता है। इस प्रकार केवल [[ओमेटा]] पार्सिंग एल्गोरिदम<ref name="warth08"/> अतिरिक्त परिचर समष्टिता के बिना पूर्ण प्रत्यक्ष और अप्रत्यक्ष बाएं रिकर्सन का समर्थन करता है (किन्तु फिर से, रैखिक समय समष्टिता के हानि पर), जबकि सभी [[जीएलआर पार्सर]] बाएं रिकर्सन का समर्थन करते हैं।
 === अभिव्यंजक शक्ति ===
-पीईजी पैकराट पार्सर्स कुछ स्पष्ट गैर-नियतात्मक सीएफजी नियमों को नहीं पहचान सकते, जैसे कि निम्नलिखित:<ref name="pegs"/>
+पीईजी पैकराट पार्सर्स कुछ स्पष्ट गैर-नियतात्मक सीएफजी नियमों को नहीं पहचान सकते है, जैसे कि निम्नलिखित:<ref name="pegs"/>
 <syntaxhighlight lang="peg">
 S ← 'x' S 'x' | 'x'
 </syntaxhighlight>
-न तब [[एलएल(के)]] और न ही एलआर(के) पार्सिंग एल्गोरिदम इस उदाहरण को पहचानने में सक्षम हैं। चूँकि, इस व्याकरण का उपयोग [[CYK एल्गोरिथ्म|सीवाईके एल्गोरिथ्म]] जैसे सामान्य सीएफजी पार्सर द्वारा किया जा सकता है। चूँकि, विचाराधीन लैंग्वेज को इन सभी प्रकार के पार्सर द्वारा पहचाना जा सकता है, जिससे कि यह वास्तव में नियमित लैंग्वेज है (विषम संख्या में x की स्ट्रिंग की)।
+न तब [[एलएल(के)]] और न ही एलआर(के) पार्सिंग एल्गोरिदम इस उदाहरण को पहचानने में सक्षम हैं। चूँकि, इस व्याकरण का उपयोग [[CYK एल्गोरिथ्म|सीवाईके एल्गोरिथ्म]] जैसे सामान्य सीएफजी पार्सर द्वारा किया जा सकता है। चूँकि, विचाराधीन लैंग्वेज को इन सभी प्रकार के पार्सर द्वारा पहचाना जा सकता है, जिससे कि यह वास्तव में नियमित लैंग्वेज है (विषम संख्या में एक्स की स्ट्रिंग की)।
-संदर्भ-मुक्त लैंग्वेज का ठोस उदाहरण देना खुली समस्या है जिसे पार्सिंग अभिव्यक्ति व्याकरण द्वारा पहचाना नहीं जा सकता है।<ref name="For04" /> विशेष रूप से, यह खुला है कि क्या पार्सिंग अभिव्यक्ति व्याकरण पैलिंड्रोम की लैंग्वेज को पहचान सकता है।<ref>{{cite arXiv |last1=Loff |first1=Bruno |last2=Moreira |first2=Nelma |last3=Reis |first3=Rogério |date=2020-02-14 |title=अभिव्यक्ति व्याकरणों को पार्स करने की कम्प्यूटेशनल शक्ति|class=cs.FL |eprint=1902.08272 }}</ref>
+संदर्भ-मुक्त लैंग्वेज का ठोस उदाहरण देना खुली समस्या होती है जिसे पार्सिंग अभिव्यक्ति व्याकरण द्वारा पहचाना नहीं जा सकता है।<ref name="For04" /> विशेष रूप से, यह खुला है कि क्या पार्सिंग अभिव्यक्ति व्याकरण पैलिंड्रोम की लैंग्वेज को पहचान सकता है।<ref>{{cite arXiv |last1=Loff |first1=Bruno |last2=Moreira |first2=Nelma |last3=Reis |first3=Rogério |date=2020-02-14 |title=अभिव्यक्ति व्याकरणों को पार्स करने की कम्प्यूटेशनल शक्ति|class=cs.FL |eprint=1902.08272 }}</ref>
 === अस्पष्टता का पता लगाना और मेल खाने वाली लैंग्वेज पर नियम क्रम का प्रभाव ===
-इनपुट व्याकरण अस्पष्ट होने पर LL(k) और LR(k) पार्सर जनरेटर पूरा करने में विफल हो जाएंगे। सामान्य स्थितियोंमें यह विशेषता है कि व्याकरण स्पष्ट होने का इरादा रखता है किन्तु दोषपूर्ण है। पीईजी पार्सर जनरेटर अनपेक्षित अस्पष्टताओं को जल्द से जल्द हल करेगा, जो इच्छानुसार हो सकता है और आश्चर्यजनक पार्स का कारण बन सकता है।
+इनपुट व्याकरण अस्पष्ट होने पर एलएल(के) और LR(k) पार्सर जनरेटर पूर्ण करने में विफल हो जाते है। सामान्य स्थितियों में यह विशेषता है कि व्याकरण स्पष्ट होने का इरादा रखता है किन्तु दोषपूर्ण होता है। इस प्रकार पीईजी पार्सर जनरेटर अनपेक्षित अस्पष्टताओं को जल्द से जल्द हल करता है, जो इच्छानुसार हो सकता है और आश्चर्यजनक पार्स का कारण बन सकता है।
-पीईजी व्याकरण में प्रस्तुतियों का क्रम न केवल अस्पष्टता के समाधान को प्रभावित करता है, किंतु मिलान की गई लैंग्वेज को भी प्रभावित करता है। उदाहरण के लिए, फोर्ड के पेपर में पहले पीईजी उदाहरण पर विचार करें<ref name="For04" /> (उदाहरण pegjs.org/online नोटेशन में पुनः लिखा गया है, और लेबल किया गया है {{tmath|G_1}} और {{tmath|G_2}}):
+पीईजी व्याकरण में प्रस्तुतियों का क्रम न केवल अस्पष्टता के समाधान को प्रभावित करता है, किंतु मिलान की गई लैंग्वेज को भी प्रभावित करता है। उदाहरण के लिए, फोर्ड के पेपर में पहले पीईजी उदाहरण पर विचार करते है।<ref name="For04" /> (उदाहरण पेग्ज्स.ओआरजी/ऑनलाइन नोटेशन में पुनः लिखा गया है, और लेबल किया गया है {{tmath|G_1}} और {{tmath|G_2}}):
 * {{tmath|G_1}}: {{code|code= A = "a" "b" / "a"}}
 * {{tmath|G_2}}: {{code|code= A = "a" / "a" "b"}}
-फोर्ड नोट करता है कि पश्चात् वाले पीईजी नियम में दूसरा विकल्प कभी सफल नहीं होगा जिससे कि पहली पसंद सदैव ली जाती है यदि इनपुट स्ट्रिंग ... '''<nowiki/>'ए'''' से प्रारंभ होती है।<ref name="For04" />
+फोर्ड नोट कर'''ता है कि पश्चात् वाले पीईजी नियम में''' दूसरा विकल्प कभी सफल नहीं होगा जिससे कि पहली पसंद सदैव ली जाती है यदि इनपुट स्ट्रिंग ... '''<nowiki/>'ए'''' से प्रारंभ होती है।<ref name="For04" />
 विशेष रूप से, {{tmath|L(G_1)}} (अर्थात, लैंग्वेज से मेल खाती है {{tmath|G_1}}) में इनपुट ab सम्मिलित है, किन्तु {{tmath|L(G_2)}} नहीं करता।
 इस प्रकार, पीईजी व्याकरण में नया विकल्प जोड़ने से मिलान की गई लैंग्वेज से स्ट्रिंग्स को हटाया जा सकता है, उदाहरण के लिए {{tmath|G_2}} एकल-उत्पादन व्याकरण में नियम का जोड़ है{{code|code= A = "a" "b"}}, जिसमें ऐसी स्ट्रिंग है जो मेल नहीं खाती {{tmath|G_2}}.

Anonymous

Search

पार्सिंग अभिव्यक्ति व्याकरण: Difference between revisions

Namespaces

More

Page actions

Revision as of 14:12, 6 August 2023

Contents

परिलैंग्वेज

सिंटेक्स

शब्दार्थ

पार्सिंग अभिव्यक्तियों की परिचालन व्याख्या

उदाहरण

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

लाभ

हानि

मेमोरी खपत

अप्रत्यक्ष बायाँ प्रत्यावर्तन

अभिव्यंजक शक्ति

अस्पष्टता का पता लगाना और मेल खाने वाली लैंग्वेज पर नियम क्रम का प्रभाव

बॉटम-अप पीईजी पार्सिंग

व्यावहारिक उपयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

पार्सिंग अभिव्यक्ति व्याकरण: Difference between revisions

Revision as of 14:12, 6 August 2023

परिलैंग्वेज

सिंटेक्स

शब्दार्थ

पार्सिंग अभिव्यक्तियों की परिचालन व्याख्या

उदाहरण

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

लाभ

हानि

मेमोरी खपत

अप्रत्यक्ष बायाँ प्रत्यावर्तन

अभिव्यंजक शक्ति

अस्पष्टता का पता लगाना और मेल खाने वाली लैंग्वेज पर नियम क्रम का प्रभाव

बॉटम-अप पीईजी पार्सिंग

व्यावहारिक उपयोग

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories