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

Revision as of 17:08, 3 August 2023

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

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

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

परिभाषा

सिंटेक्स

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

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

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

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

Operator	Priority
(e)	5
&e, !e	4
e*, e+, e?	3
e₁ e₂	2
e₁ / e₂	1

शब्दार्थ

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

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

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

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

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

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

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

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

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

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

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

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

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

उदाहरण

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

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

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

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

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

पार्सिंग अभिव्यक्ति foo &(bar) टेक्स्ट foo से मेल खाता है और उपभोग करता है लेकिन केवल तभी जब टेक्स्ट बार इसके बाद आता है। पार्सिंग अभिव्यक्ति foo !(bar) टेक्स्ट foo से मेल खाता है लेकिन केवल तभी जब टेक्स्ट बार इसका अनुसरण नहीं करता है। इजहार !(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]

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

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

लाभ

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

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

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

नुकसान

मेमोरी खपत

पीईजी पार्सिंग आमतौर पर पैक्रैट पार्सिंग के माध्यम से किया जाता है, जो मेमोइज़ेशन का उपयोग करता है^[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

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

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

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

string-of-a ← 'a'+

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

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

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

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

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

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

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

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

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

पीईजी व्याकरण में प्रस्तुतियों का क्रम न केवल अस्पष्टता के समाधान को प्रभावित करता है, बल्कि मिलान की गई भाषा को भी प्रभावित करता है। उदाहरण के लिए, फोर्ड के पेपर में पहले पीईजी उदाहरण पर विचार करें^[1](उदाहरण pegjs.org/online नोटेशन में पुनः लिखा गया है, और लेबल किया गया है $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})$ नहीं करता। इस प्रकार, PEG व्याकरण में नया विकल्प जोड़ने से मिलान की गई भाषा से स्ट्रिंग्स को हटाया जा सकता है, उदाहरण के लिए $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_(प्रोग्रामिंग_भाषा)#Parsing_Expression_Grammars PEG से निकटता से संबंधित औपचारिकता का उपयोग करता है।

यह भी देखें

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

संदर्भ

↑ ^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.

बाहरी संबंध

Converting a string expression into a lambda expression using an expression parser
The Packrat Parsing and Parsing Expression Grammars Page
The constructed language Lojban has a fairly large PEG grammar allowing unambiguous parsing of Lojban text.
An illustrative implementation of a PEG in Guile scheme

[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 1: / Line 1: @@
 {{short description|Type of grammar for describing formal languages}}
-[[कंप्यूटर विज्ञान]] में, पार्सिंग एक्सप्रेशन व्याकरण (पीईजी) एक प्रकार का [[औपचारिक व्याकरण]]#विश्लेषणात्मक व्याकरण औपचारिक व्याकरण है, यानी यह भाषा में [[स्ट्रिंग (कंप्यूटर विज्ञान)]] को पहचानने के लिए नियमों के एक सेट के संदर्भ में एक [[औपचारिक भाषा]] का वर्णन करता है। औपचारिकतावाद की शुरुआत 2004 में ब्रायन फोर्ड द्वारा की गई थी<ref name="For04">
+[[कंप्यूटर विज्ञान]] में, पार्सिंग एक्सप्रेशन व्याकरण (पीईजी) प्रकार का [[औपचारिक व्याकरण]] औपचारिक व्याकरण है, यानी यह भाषा में [[स्ट्रिंग (कंप्यूटर विज्ञान)]] को पहचानने के लिए नियमों के सेट के संदर्भ में [[औपचारिक भाषा]] का वर्णन करता है। औपचारिकतावाद की शुरुआत 2004 में ब्रायन फोर्ड द्वारा की गई थी<ref name="For04">
 {{cite conference
 | first = Bryan
@@ Line 13: / Line 13: @@
 |pages=111–122
 }}</ref> और 1970 के दशक की शुरुआत में शुरू की गई [[ऊपर से नीचे पार्सिंग भाषा]] के परिवार से निकटता से संबंधित है।
-वाक्यात्मक रूप से, पीईजी भी [[संदर्भ-मुक्त व्याकरण]] (सीएफजी) के समान दिखते हैं, लेकिन उनकी एक अलग व्याख्या होती है: चॉइस ऑपरेटर पीईजी में पहले मैच का चयन करता है, जबकि सीएफजी में यह अस्पष्ट है। यह व्यवहार में स्ट्रिंग पहचान कैसे की जाती है, इसके करीब है, उदाहरण के लिए। एक [[पुनरावर्ती वंश पार्सर]] द्वारा।
-सीएफजी के विपरीत, पीईजी [[अस्पष्ट व्याकरण]] नहीं हो सकते; एक स्ट्रिंग में बिल्कुल एक वैध [[पार्स वृक्ष]] है या कोई भी नहीं है। यह अनुमान लगाया गया है कि ऐसी संदर्भ-मुक्त भाषाएँ मौजूद हैं जिन्हें PEG द्वारा पहचाना नहीं जा सकता है, लेकिन यह अभी तक सिद्ध नहीं हुआ है।<ref name="For04" />पीईजी कंप्यूटर भाषाओं (और [[लोज में]] जैसी कृत्रिम मानव भाषाओं) को पार्स करने के लिए उपयुक्त हैं, लेकिन [[प्राकृतिक भाषा]]ओं के लिए नहीं, जहां पीईजी एल्गोरिदम का प्रदर्शन सामान्य सीएफजी एल्गोरिदम जैसे [[अर्ली एल्गोरिथम]] के बराबर है।<ref name="pegs">
+वाक्यात्मक रूप से, पीईजी भी [[संदर्भ-मुक्त व्याकरण]] (सीएफजी) के समान दिखते हैं, लेकिन उनकी अलग व्याख्या होती है: चॉइस ऑपरेटर पीईजी में पहले मैच का चयन करता है, जबकि सीएफजी में यह अस्पष्ट है। यह व्यवहार में स्ट्रिंग पहचान कैसे की जाती है, इसके करीब है, उदाहरण के लिए। [[पुनरावर्ती वंश पार्सर]] द्वारा।
+सीएफजी के विपरीत, पीईजी [[अस्पष्ट व्याकरण]] नहीं हो सकते; स्ट्रिंग में बिल्कुल वैध [[पार्स वृक्ष]] है या कोई भी नहीं है। यह अनुमान लगाया गया है कि ऐसी संदर्भ-मुक्त भाषाएँ मौजूद हैं जिन्हें PEG द्वारा पहचाना नहीं जा सकता है, लेकिन यह अभी तक सिद्ध नहीं हुआ है।<ref name="For04" />पीईजी कंप्यूटर भाषाओं (और [[लोज में]] जैसी कृत्रिम मानव भाषाओं) को पार्स करने के लिए उपयुक्त हैं, लेकिन [[प्राकृतिक भाषा]]ओं के लिए नहीं, जहां पीईजी एल्गोरिदम का प्रदर्शन सामान्य सीएफजी एल्गोरिदम जैसे [[अर्ली एल्गोरिथम]] के बराबर है।<ref name="pegs">
 {{cite journal
 | first= Bryan |last=Ford
@@ Line 26: / Line 27: @@
 }}
 </ref>
 == परिभाषा ==
-{{No footnotes|section|date=December 2022}}
 === सिंटेक्स ===
-औपचारिक रूप से, एक पार्सिंग अभिव्यक्ति व्याकरण में निम्न शामिल हैं:
+औपचारिक रूप से, पार्सिंग अभिव्यक्ति व्याकरण में निम्न शामिल हैं:
-* नॉन[[टर्मिनल प्रतीक]]ों का एक परिमित सेट एन।
+* नॉन[[टर्मिनल प्रतीक]] का परिमित सेट एन।
-* टर्मिनल प्रतीकों का एक परिमित सेट Σ जो एन से [[असंयुक्त सेट]] है।
+* टर्मिनल प्रतीकों का परिमित सेट Σ जो एन से [[असंयुक्त सेट]] है।
-* पार्सिंग नियमों का एक सीमित सेट पी।
+* पार्सिंग नियमों का सीमित सेट पी।
 * एक अभिव्यक्ति ई<sub>S</sub>प्रारंभिक अभिव्यक्ति कहा जाता है।
-पी में प्रत्येक पार्सिंग नियम का रूप ए ← ई है, जहां ए एक गैर-टर्मिनल प्रतीक है और ई एक पार्सिंग अभिव्यक्ति है। एक पार्सिंग अभिव्यक्ति एक [[नियमित अभिव्यक्ति]] के समान एक पदानुक्रमित [[अभिव्यक्ति (गणित)]] है, जिसका निर्माण निम्नलिखित तरीके से किया गया है:
+पी में प्रत्येक पार्सिंग नियम का रूप ए ← ई है, जहां ए गैर-टर्मिनल प्रतीक है और ई पार्सिंग अभिव्यक्ति है। पार्सिंग अभिव्यक्ति [[नियमित अभिव्यक्ति]] के समान पदानुक्रमित [[अभिव्यक्ति (गणित)]] है, जिसका निर्माण निम्नलिखित तरीके से किया गया है:
 # परमाणु पार्सिंग अभिव्यक्ति में निम्न शामिल हैं:
 #* कोई भी टर्मिनल प्रतीक,
 #* कोई नॉनटर्मिनल प्रतीक, या
 #* खाली स्ट्रिंग ε.
-# किसी भी मौजूदा पार्सिंग अभिव्यक्ति ई, ई को देखते हुए<sub>1</sub>, और ई<sub>2</sub>, निम्नलिखित ऑपरेटरों का उपयोग करके एक नई पार्सिंग अभिव्यक्ति का निर्माण किया जा सकता है:
+# किसी भी मौजूदा पार्सिंग अभिव्यक्ति ई, ई को देखते हुए<sub>1</sub>, और ई<sub>2</sub>, निम्नलिखित ऑपरेटरों का उपयोग करके नई पार्सिंग अभिव्यक्ति का निर्माण किया जा सकता है:
 #* अनुक्रम: ई<sub>1</sub> e<sub>2</sub>
 #* ऑर्डर किया गया विकल्प: ई<sub>1</sub> / यह है<sub>2</sub>
@@ Line 66: / Line 63: @@
 | ''e''<sub>1</sub> / ''e''<sub>2</sub> || 1
 |}
 === शब्दार्थ ===
 [[संदर्भ-मुक्त व्याकरण]] और पार्सिंग अभिव्यक्ति व्याकरण के बीच मूलभूत अंतर यह है कि पीईजी के पसंदीदा ऑपरेटर का आदेश दिया जाता है। यदि पहला विकल्प सफल हो जाता है, तो दूसरे विकल्प को नजरअंदाज कर दिया जाता है। इस प्रकार संदर्भ-मुक्त व्याकरणों की तरह अव्यवस्थित विकल्प के विपरीत, क्रमबद्ध विकल्प क्रमविनिमेयता नहीं है। ऑर्डर किया गया विकल्प कुछ लॉजिक प्रोग्रामिंग भाषाओं में उपलब्ध [[ कट ([[तर्क प्रोग्रामिंग]]) ]] ऑपरेटरों के अनुरूप है।
-इसका परिणाम यह है कि यदि एक सीएफजी को सीधे पीईजी में लिप्यंतरित किया जाता है, तो पूर्व में किसी भी अस्पष्टता को संभावित पार्स में से एक पार्स पेड़ को चुनकर हल किया जाता है। व्याकरण के विकल्पों को निर्दिष्ट करने के क्रम को सावधानीपूर्वक चुनने से, एक प्रोग्रामर के पास इस बात पर बहुत अधिक नियंत्रण होता है कि कौन सा पार्स ट्री चुना गया है।
+इसका परिणाम यह है कि यदि सीएफजी को सीधे पीईजी में लिप्यंतरित किया जाता है, तो पूर्व में किसी भी अस्पष्टता को संभावित पार्स में से पार्स पेड़ को चुनकर हल किया जाता है। व्याकरण के विकल्पों को निर्दिष्ट करने के क्रम को सावधानीपूर्वक चुनने से, प्रोग्रामर के पास इस बात पर बहुत अधिक नियंत्रण होता है कि कौन सा पार्स ट्री चुना गया है।
-[[बूलियन व्याकरण]]|बूलियन संदर्भ-मुक्त व्याकरणों की तरह, पार्सिंग अभिव्यक्ति व्याकरण भी और- और नहीं- वाक्यविन्यास विधेय जोड़ते हैं। क्योंकि वे वास्तव में इसका उपभोग किए बिना इनपुट स्ट्रिंग में आगे देखने के लिए एक मनमाने ढंग से जटिल उप-अभिव्यक्ति का उपयोग कर सकते हैं, वे एक शक्तिशाली वाक्यविन्यास पार्सिंग#लुकहेड और असंबद्धता सुविधा प्रदान करते हैं, विशेष रूप से जब विकल्पों को पुन: व्यवस्थित करने से वांछित सटीक पार्स ट्री निर्दिष्ट नहीं किया जा सकता है।
+[[बूलियन व्याकरण]]|बूलियन संदर्भ-मुक्त व्याकरणों की तरह, पार्सिंग अभिव्यक्ति व्याकरण भी और- और नहीं- वाक्यविन्यास विधेय जोड़ते हैं। क्योंकि वे वास्तव में इसका उपभोग किए बिना इनपुट स्ट्रिंग में आगे देखने के लिए मनमाने ढंग से जटिल उप-अभिव्यक्ति का उपयोग कर सकते हैं, वे शक्तिशाली वाक्यविन्यास पार्सिंग#लुकहेड और असंबद्धता सुविधा प्रदान करते हैं, विशेष रूप से जब विकल्पों को पुन: व्यवस्थित करने से वांछित सटीक पार्स ट्री निर्दिष्ट नहीं किया जा सकता है।
 === पार्सिंग अभिव्यक्तियों की परिचालन व्याख्या ===
-पार्सिंग अभिव्यक्ति व्याकरण में प्रत्येक नॉनटर्मिनल अनिवार्य रूप से एक पुनरावर्ती वंश पार्सर में एक पार्सिंग [[फ़ंक्शन (गणित)]] का प्रतिनिधित्व करता है, और संबंधित पार्सिंग अभिव्यक्ति फ़ंक्शन वाले कोड का प्रतिनिधित्व करती है। प्रत्येक पार्सिंग फ़ंक्शन वैचारिक रूप से एक इनपुट स्ट्रिंग को अपने तर्क के रूप में लेता है, और निम्नलिखित परिणामों में से एक उत्पन्न करता है:
+पार्सिंग अभिव्यक्ति व्याकरण में प्रत्येक नॉनटर्मिनल अनिवार्य रूप से पुनरावर्ती वंश पार्सर में पार्सिंग [[फ़ंक्शन (गणित)]] का प्रतिनिधित्व करता है, और संबंधित पार्सिंग अभिव्यक्ति फ़ंक्शन वाले कोड का प्रतिनिधित्व करती है। प्रत्येक पार्सिंग फ़ंक्शन वैचारिक रूप से इनपुट स्ट्रिंग को अपने तर्क के रूप में लेता है, और निम्नलिखित परिणामों में से उत्पन्न करता है:
-* सफलता, जिसमें फ़ंक्शन वैकल्पिक रूप से आगे बढ़ सकता है या उसे आपूर्ति की गई इनपुट स्ट्रिंग के एक या अधिक वर्णों का उपभोग कर सकता है, या
+* सफलता, जिसमें फ़ंक्शन वैकल्पिक रूप से आगे बढ़ सकता है या उसे आपूर्ति की गई इनपुट स्ट्रिंग के या अधिक वर्णों का उपभोग कर सकता है, या
 * विफलता, जिस स्थिति में कोई इनपुट उपभोग नहीं किया जाता है।
-यदि इनपुट स्ट्रिंग का पहला अक्षर उस टर्मिनल से मेल खाता है, और उस स्थिति में इनपुट कैरेक्टर का उपभोग करता है, तो एकल 'टर्मिनल' (यानी शाब्दिक) से युक्त एक परमाणु पार्सिंग अभिव्यक्ति सफल होती है; अन्यथा अभिव्यक्ति विफलता परिणाम उत्पन्न करती है। 'रिक्त' स्ट्रिंग से युक्त एक परमाणु पार्सिंग अभिव्यक्ति हमेशा किसी भी इनपुट का उपभोग किए बिना तुच्छ रूप से सफल होती है।
+यदि इनपुट स्ट्रिंग का पहला अक्षर उस टर्मिनल से मेल खाता है, और उस स्थिति में इनपुट कैरेक्टर का उपभोग करता है, तो एकल 'टर्मिनल' (यानी शाब्दिक) से युक्त परमाणु पार्सिंग अभिव्यक्ति सफल होती है; अन्यथा अभिव्यक्ति विफलता परिणाम उत्पन्न करती है। 'रिक्त' स्ट्रिंग से युक्त परमाणु पार्सिंग अभिव्यक्ति हमेशा किसी भी इनपुट का उपभोग किए बिना तुच्छ रूप से सफल होती है।
-एक परमाणु पार्सिंग अभिव्यक्ति जिसमें 'नॉनटर्मिनल' ए शामिल है, नॉनटर्मिनल-फ़ंक्शन ए के लिए एक [[ प्रत्यावर्तन ]] कॉल का प्रतिनिधित्व करता है। एक नॉनटर्मिनल वास्तव में किसी भी इनपुट का उपभोग किए बिना सफल हो सकता है, और इसे विफलता से अलग परिणाम माना जाता है।
+एक परमाणु पार्सिंग अभिव्यक्ति जिसमें 'नॉनटर्मिनल' ए शामिल है, नॉनटर्मिनल-फ़ंक्शन ए के लिए [[ प्रत्यावर्तन |प्रत्यावर्तन]] कॉल का प्रतिनिधित्व करता है। नॉनटर्मिनल वास्तव में किसी भी इनपुट का उपभोग किए बिना सफल हो सकता है, और इसे विफलता से अलग परिणाम माना जाता है।
 'अनुक्रम' ऑपरेटर ई<sub>1</sub> e<sub>2</sub> सबसे पहले ई का आह्वान करता है<sub>1</sub>, और यदि ई<sub>1</sub> सफल होता है, बाद में ई को आमंत्रित करता है<sub>2</sub> ई द्वारा उपभोग न किए गए छोड़े गए इनपुट स्ट्रिंग के शेष भाग पर<sub>1</sub>, और परिणाम लौटाता है। यदि या तो ई<sub>1</sub> या ई<sub>2</sub> विफल रहता है, तो अनुक्रम अभिव्यक्ति ई<sub>1</sub> e<sub>2</sub> विफल रहता है (कोई इनपुट नहीं लेता)।
@@ Line 89: / Line 84: @@
 चॉइस ऑपरेटर ''ई''<sub>1</sub> / यह है<sub>2</sub> सबसे पहले ई का आह्वान करता है<sub>1</sub>, और यदि ई<sub>1</sub> सफल होता है, तुरंत अपना परिणाम लौटाता है। अन्यथा, यदि ई<sub>1</sub> विफल हो जाता है, तो चॉइस ऑपरेटर मूल इनपुट स्थिति पर वापस लौट जाता है जिस पर उसने ई को लागू किया था<sub>1</sub>, लेकिन फिर ई को कॉल करता है<sub>2</sub> इसके बजाय, ई लौट रहा है<sub>2</sub>का परिणाम.
-शून्य-या-अधिक, एक-या-अधिक, और वैकल्पिक ऑपरेटर क्रमशः अपनी उप-अभिव्यक्ति ''ई'' की शून्य या अधिक, एक या अधिक, या शून्य या एक लगातार पुनरावृत्ति का उपभोग करते हैं। हालांकि, संदर्भ-मुक्त व्याकरण और नियमित अभिव्यक्तियों के विपरीत, ये ऑपरेटर ''हमेशा'' [[लालची एल्गोरिदम]] का व्यवहार करते हैं, जितना संभव हो उतना इनपुट लेते हैं और कभी भी पीछे नहीं हटते हैं। (नियमित अभिव्यक्ति मिलानकर्ता लालच से मिलान करके शुरू कर सकते हैं, लेकिन यदि वे मिलान करने में विफल रहते हैं तो पीछे हट जाएंगे और छोटे मिलान करने का प्रयास करेंगे।) उदाहरण के लिए, अभिव्यक्ति a* हमेशा उतने ही a का उपभोग करेगा जितने इनपुट स्ट्रिंग में लगातार उपलब्ध हैं, और अभिव्यक्ति (a* a) हमेशा विफल रहेगी क्योंकि पहला भाग (a*) दूसरे भाग के मिलान के लिए कभी भी a नहीं छोड़ेगा।
+शून्य-या-अधिक, एक-या-अधिक, और वैकल्पिक ऑपरेटर क्रमशः अपनी उप-अभिव्यक्ति ''ई'' की शून्य या अधिक, या अधिक, या शून्य या लगातार पुनरावृत्ति का उपभोग करते हैं। हालांकि, संदर्भ-मुक्त व्याकरण और नियमित अभिव्यक्तियों के विपरीत, ये ऑपरेटर ''हमेशा'' [[लालची एल्गोरिदम]] का व्यवहार करते हैं, जितना संभव हो उतना इनपुट लेते हैं और कभी भी पीछे नहीं हटते हैं। (नियमित अभिव्यक्ति मिलानकर्ता लालच से मिलान करके शुरू कर सकते हैं, लेकिन यदि वे मिलान करने में विफल रहते हैं तो पीछे हट जाएंगे और छोटे मिलान करने का प्रयास करेंगे।) उदाहरण के लिए, अभिव्यक्ति a* हमेशा उतने ही a का उपभोग करेगा जितने इनपुट स्ट्रिंग में लगातार उपलब्ध हैं, और अभिव्यक्ति (a* a) हमेशा विफल रहेगी क्योंकि पहला भाग (a*) दूसरे भाग के मिलान के लिए कभी भी a नहीं छोड़ेगा।
 और-विधेय अभिव्यक्ति &''e'' उप-अभिव्यक्ति ''e'' का आह्वान करती है, और यदि ''e'' सफल होती है तो सफल होती है और यदि ''e'' विफल होती है तो विफल हो जाती है, लेकिन किसी भी स्थिति में ''कभी भी किसी इनपुट का उपभोग नहीं करती''।
@@ Line 96: / Line 91: @@
 === उदाहरण ===
-यह एक पीईजी है जो गणितीय सूत्रों को पहचानता है जो गैर-नकारात्मक पूर्णांकों पर बुनियादी पांच परिचालनों को लागू करते हैं।
+यह पीईजी है जो गणितीय सूत्रों को पहचानता है जो गैर-नकारात्मक पूर्णांकों पर बुनियादी पांच परिचालनों को लागू करते हैं।
 <syntaxhighlight lang="peg">
 Expr    ← Sum
@@ Line 104: / Line 99: @@
 Value   ← [0-9]+ / '(' Expr ')'
 </syntaxhighlight>
-उपरोक्त उदाहरण में, टर्मिनल प्रतीक पाठ के वर्ण हैं, जिन्हें एकल उद्धरण चिह्नों में वर्णों द्वारा दर्शाया गया है, जैसे <code>'('</code> और <code>')'</code>. सीमा <code>[0-9]</code> से दस वर्णों के लिए एक शॉर्टकट है <code>'0'</code> को <code>'9'</code>. (यह रेंज सिंटैक्स रेगुलर एक्सप्रेशन द्वारा उपयोग किए जाने वाले सिंटैक्स के समान है।) नॉनटर्मिनल प्रतीक वे हैं जो अन्य नियमों तक विस्तारित होते हैं: मूल्य, पावर, उत्पाद, योग और एक्सप्र। ध्यान दें कि नियम Sum और Product इन परिचालनों की वांछित बाईं-संबद्धता की ओर नहीं ले जाते हैं (वे सहयोगीता से बिल्कुल भी नहीं निपटते हैं, और इसे पार्सिंग के बाद पोस्ट-प्रोसेसिंग चरण में संभालना पड़ता है), और पावर नियम (दाईं ओर खुद को संदर्भित करके) प्रतिपादक की वांछित दाईं-संबद्धता का परिणाम देता है। यह भी ध्यान दें कि एक नियम पसंद है {{code|Sum ← Sum (('+' / '-') Product)?|peg}} (वाम-साहचर्य प्राप्त करने के इरादे से) अनंत पुनरावृत्ति का कारण बनेगा, इसलिए इसे व्याकरण में व्यक्त किए जाने के बावजूद व्यवहार में उपयोग नहीं किया जा सकता है।
+उपरोक्त उदाहरण में, टर्मिनल प्रतीक पाठ के वर्ण हैं, जिन्हें एकल उद्धरण चिह्नों में वर्णों द्वारा दर्शाया गया है, जैसे <code>'('</code> और <code>')'</code>. सीमा <code>[0-9]</code> से दस वर्णों के लिए शॉर्टकट है <code>'0'</code> को <code>'9'</code>. (यह रेंज सिंटैक्स रेगुलर एक्सप्रेशन द्वारा उपयोग किए जाने वाले सिंटैक्स के समान है।) नॉनटर्मिनल प्रतीक वे हैं जो अन्य नियमों तक विस्तारित होते हैं: मूल्य, पावर, उत्पाद, योग और एक्सप्र। ध्यान दें कि नियम Sum और Product इन परिचालनों की वांछित बाईं-संबद्धता की ओर नहीं ले जाते हैं (वे सहयोगीता से बिल्कुल भी नहीं निपटते हैं, और इसे पार्सिंग के बाद पोस्ट-प्रोसेसिंग चरण में संभालना पड़ता है), और पावर नियम (दाईं ओर खुद को संदर्भित करके) प्रतिपादक की वांछित दाईं-संबद्धता का परिणाम देता है। यह भी ध्यान दें कि नियम पसंद है {{code|Sum ← Sum (('+' / '-') Product)?|peg}} (वाम-साहचर्य प्राप्त करने के इरादे से) अनंत पुनरावृत्ति का कारण बनेगा, इसलिए इसे व्याकरण में व्यक्त किए जाने के बावजूद व्यवहार में उपयोग नहीं किया जा सकता है।
 निम्नलिखित पुनरावर्ती नियम मानक सी-शैली if/then/else कथनों से इस प्रकार मेल खाता है कि '/' ऑपरेटर की अंतर्निहित प्राथमिकता के कारण वैकल्पिक अन्यथा खंड हमेशा अंतरतम if से बंध जाता है। (संदर्भ-मुक्त व्याकरण में, यह निर्माण क्लासिक डेंगलिंग को जन्म देता है।)
@@ Line 118: / Line 113: @@
 Z     ← any single character
 </syntaxhighlight>
-पार्सिंग अभिव्यक्ति {{code|2=peg|foo &(bar)}} टेक्स्ट foo से मेल खाता है और उपभोग करता है लेकिन केवल तभी जब टेक्स्ट बार इसके बाद आता है। पार्सिंग अभिव्यक्ति {{code|2=peg|foo !(bar)}} टेक्स्ट foo से मेल खाता है लेकिन केवल तभी जब टेक्स्ट बार इसका अनुसरण नहीं करता है। इजहार {{code|2=peg|!(a+ b) a}} एक एकल ए से मेल खाता है, लेकिन केवल तभी जब यह ए के बाद बी के मनमाने ढंग से लंबे अनुक्रम का हिस्सा नहीं है।
+पार्सिंग अभिव्यक्ति {{code|2=peg|foo &(bar)}} टेक्स्ट foo से मेल खाता है और उपभोग करता है लेकिन केवल तभी जब टेक्स्ट बार इसके बाद आता है। पार्सिंग अभिव्यक्ति {{code|2=peg|foo !(bar)}} टेक्स्ट foo से मेल खाता है लेकिन केवल तभी जब टेक्स्ट बार इसका अनुसरण नहीं करता है। इजहार {{code|2=peg|!(a+ b) a}} एकल ए से मेल खाता है, लेकिन केवल तभी जब यह ए के बाद बी के मनमाने ढंग से लंबे अनुक्रम का हिस्सा नहीं है।
 पार्सिंग अभिव्यक्ति {{code|2=peg|('a'/'b')*}} ए और बी के मनमाने-लंबाई अनुक्रम से मेल खाता है और उपभोग करता है। औपचारिक व्याकरण# व्याकरण का वाक्य-विन्यास {{code|2=peg|S ← 'a' ''S''? 'b'}} सरल [[संदर्भ-मुक्त भाषा]]|संदर्भ-मुक्त मिलान भाषा का वर्णन करता है <math> \{ a^n b^n : n \ge 1 \} </math>.
@@ Line 127: / Line 122: @@
 B ← 'b' B? 'c'
 </syntaxhighlight>
 == अभिव्यक्ति व्याकरण को पार्स करने के लिए पार्सर लागू करना ==
 और पार्सिंग अभिव्यक्ति व्याकरण को सीधे पुनरावर्ती वंश पार्सर में परिवर्तित किया जा सकता है।<ref name="ford02">{{cite thesis|url=http://pdos.csail.mit.edu/~baford/packrat/thesis|title=Packrat Parsing: a Practical Linear-Time Algorithm with Backtracking|last=Ford|first=Bryan|date=September 2002|publisher=Massachusetts Institute of Technology|access-date=2007-07-27}}
@@ Line 138: / Line 131: @@
 </ref> हालाँकि, व्याकरण की औपचारिकता द्वारा प्रदान की जाने वाली असीमित पार्सिंग#लुकहेड क्षमता के कारण, परिणामी पार्सर सबसे खराब स्थिति में [[घातीय समय]] प्रदर्शन प्रदर्शित कर सकता है।
-किसी भी पार्सिंग अभिव्यक्ति व्याकरण के लिए उसके पुनरावर्ती वंश पार्सर को [[पैकराट पार्सर]] में परिवर्तित करके बेहतर प्रदर्शन प्राप्त करना संभव है, जो काफी अधिक भंडारण स्थान आवश्यकताओं की कीमत पर हमेशा [[रैखिक समय]] में चलता है। एक पैकेट पार्सर<ref name="ford02" />निर्माण में पुनरावर्ती वंश पार्सर के समान [[ पदच्छेद ]] का एक रूप है, सिवाय इसके कि पार्सिंग प्रक्रिया के दौरान यह पारस्परिक पुनरावर्ती पार्सिंग कार्यों के सभी आह्वानों के मध्यवर्ती परिणामों को याद रखता है, यह सुनिश्चित करता है कि प्रत्येक पार्सिंग फ़ंक्शन किसी दिए गए इनपुट पर अधिकतम एक बार ही लागू किया जाता है पद। इस [[संस्मरण]] के कारण, एक पैकेट पार्सर में रैखिक समय में कई संदर्भ-मुक्त व्याकरण और किसी भी पार्सिंग अभिव्यक्ति व्याकरण (कुछ जो संदर्भ-मुक्त भाषाओं का प्रतिनिधित्व नहीं करते हैं) को पार्स करने की क्षमता होती है। मेमोइज़्ड रिकर्सिव डिसेंट पार्सर्स के उदाहरण कम से कम 1993 से ही ज्ञात हैं।<ref name="merritt01">
+किसी भी पार्सिंग अभिव्यक्ति व्याकरण के लिए उसके पुनरावर्ती वंश पार्सर को [[पैकराट पार्सर]] में परिवर्तित करके बेहतर प्रदर्शन प्राप्त करना संभव है, जो काफी अधिक भंडारण स्थान आवश्यकताओं की कीमत पर हमेशा [[रैखिक समय]] में चलता है। पैकेट पार्सर<ref name="ford02" />निर्माण में पुनरावर्ती वंश पार्सर के समान [[ पदच्छेद |पदच्छेद]] का रूप है, सिवाय इसके कि पार्सिंग प्रक्रिया के दौरान यह पारस्परिक पुनरावर्ती पार्सिंग कार्यों के सभी आह्वानों के मध्यवर्ती परिणामों को याद रखता है, यह सुनिश्चित करता है कि प्रत्येक पार्सिंग फ़ंक्शन किसी दिए गए इनपुट पर अधिकतम बार ही लागू किया जाता है पद। इस [[संस्मरण]] के कारण, पैकेट पार्सर में रैखिक समय में कई संदर्भ-मुक्त व्याकरण और किसी भी पार्सिंग अभिव्यक्ति व्याकरण (कुछ जो संदर्भ-मुक्त भाषाओं का प्रतिनिधित्व नहीं करते हैं) को पार्स करने की क्षमता होती है। मेमोइज़्ड रिकर्सिव डिसेंट पार्सर्स के उदाहरण कम से कम 1993 से ही ज्ञात हैं।<ref name="merritt01">
 {{cite web
 |url=http://compilers.iecc.com/comparch/article/93-11-012
@@ Line 149: / Line 142: @@
 }}
 </ref>
-पैक्रैट पार्सर के प्रदर्शन का यह विश्लेषण मानता है कि सभी याद किए गए परिणामों को रखने के लिए पर्याप्त मेमोरी उपलब्ध है; व्यवहार में, यदि पर्याप्त मेमोरी नहीं है, तो कुछ पार्सिंग फ़ंक्शन को एक ही इनपुट स्थिति पर एक से अधिक बार लागू करना पड़ सकता है, और परिणामस्वरूप पार्सर को रैखिक समय से अधिक समय लग सकता है।
+पैक्रैट पार्सर के प्रदर्शन का यह विश्लेषण मानता है कि सभी याद किए गए परिणामों को रखने के लिए पर्याप्त मेमोरी उपलब्ध है; व्यवहार में, यदि पर्याप्त मेमोरी नहीं है, तो कुछ पार्सिंग फ़ंक्शन को ही इनपुट स्थिति पर से अधिक बार लागू करना पड़ सकता है, और परिणामस्वरूप पार्सर को रैखिक समय से अधिक समय लग सकता है।
 पुनरावर्ती वंश पार्सर की तुलना में बेहतर सबसे खराब प्रदर्शन के साथ, अभिव्यक्ति व्याकरण को पार्स करने से [[एलएल पार्सर]] और [[एलआर पार्सर]] बनाना भी संभव है, लेकिन व्याकरण औपचारिकता की असीमित लुकहेड क्षमता तब खो जाती है। इसलिए, पार्सिंग अभिव्यक्ति व्याकरण का उपयोग करके व्यक्त की जा सकने वाली सभी भाषाओं को एलएल या एलआर पार्सर्स द्वारा पार्स नहीं किया जा सकता है।
 == लाभ ==
-शुद्ध रेगुलर एक्सप्रेशन (यानी बैक-रेफरेंस के बिना) की तुलना में, पीईजी सख्ती से अधिक शक्तिशाली होते हैं, लेकिन उन्हें काफी अधिक मेमोरी की आवश्यकता होती है। उदाहरण के लिए, एक [[नियमित अभिव्यक्ति]] स्वाभाविक रूप से कोष्ठक के मिलान जोड़े की एक मनमानी संख्या नहीं पा सकती है, क्योंकि यह पुनरावर्ती नहीं है, लेकिन एक पीईजी कर सकता है। हालाँकि, एक पीईजी को इनपुट की लंबाई के अनुपात में मेमोरी की मात्रा की आवश्यकता होगी, जबकि एक रेगुलर एक्सप्रेशन मैचर को केवल स्थिर मात्रा में मेमोरी की आवश्यकता होगी।
+शुद्ध रेगुलर एक्सप्रेशन (यानी बैक-रेफरेंस के बिना) की तुलना में, पीईजी सख्ती से अधिक शक्तिशाली होते हैं, लेकिन उन्हें काफी अधिक मेमोरी की आवश्यकता होती है। उदाहरण के लिए, [[नियमित अभिव्यक्ति]] स्वाभाविक रूप से कोष्ठक के मिलान जोड़े की मनमानी संख्या नहीं पा सकती है, क्योंकि यह पुनरावर्ती नहीं है, लेकिन पीईजी कर सकता है। हालाँकि, पीईजी को इनपुट की लंबाई के अनुपात में मेमोरी की मात्रा की आवश्यकता होगी, जबकि रेगुलर एक्सप्रेशन मैचर को केवल स्थिर मात्रा में मेमोरी की आवश्यकता होगी।
 जैसा कि ऊपर वर्णित है, किसी भी पीईजी को पैक्रैट पार्सर का उपयोग करके रैखिक समय में पार्स किया जा सकता है।
-कई सीएफजी में अस्पष्टताएं होती हैं, भले ही उनका उद्देश्य स्पष्ट भाषाओं का वर्णन करना हो। C, C++ और Java में लटकती अन्य समस्या इसका एक उदाहरण है। इन समस्याओं का समाधान अक्सर व्याकरण के बाहर किसी नियम को लागू करके किया जाता है। पीईजी में, प्राथमिकता के कारण ये अस्पष्टताएं कभी उत्पन्न नहीं होती हैं।
+कई सीएफजी में अस्पष्टताएं होती हैं, भले ही उनका उद्देश्य स्पष्ट भाषाओं का वर्णन करना हो। C, C++ और Java में लटकती अन्य समस्या इसका उदाहरण है। इन समस्याओं का समाधान अक्सर व्याकरण के बाहर किसी नियम को लागू करके किया जाता है। पीईजी में, प्राथमिकता के कारण ये अस्पष्टताएं कभी उत्पन्न नहीं होती हैं।
 ==नुकसान ==
@@ Line 176: / Line 170: @@
 |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 193: / 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> उदाहरण के लिए, निम्नलिखित बाएँ-पुनरावर्ती CFG नियम:
+इस नये व्याकरण में, का मिलान <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> उदाहरण के लिए, निम्नलिखित बाएँ-पुनरावर्ती CFG नियम:
 <syntaxhighlight lang="peg">
 string-of-a ← string-of-a 'a' | 'a'
@@ Line 234: / Line 228: @@
 S ← 'x' S 'x' | 'x'
 </syntaxhighlight>
-न तो [[एलएल(के)]] और न ही एलआर(के) पार्सिंग एल्गोरिदम इस उदाहरण को पहचानने में सक्षम हैं। हालाँकि, इस व्याकरण का उपयोग [[CYK एल्गोरिथ्म]] जैसे सामान्य CFG पार्सर द्वारा किया जा सकता है। हालाँकि, विचाराधीन भाषा को इन सभी प्रकार के पार्सर द्वारा पहचाना जा सकता है, क्योंकि यह वास्तव में एक नियमित भाषा है (विषम संख्या में x की स्ट्रिंग की)।
+न तो [[एलएल(के)]] और न ही एलआर(के) पार्सिंग एल्गोरिदम इस उदाहरण को पहचानने में सक्षम हैं। हालाँकि, इस व्याकरण का उपयोग [[CYK एल्गोरिथ्म]] जैसे सामान्य CFG पार्सर द्वारा किया जा सकता है। हालाँकि, विचाराधीन भाषा को इन सभी प्रकार के पार्सर द्वारा पहचाना जा सकता है, क्योंकि यह वास्तव में नियमित भाषा है (विषम संख्या में x की स्ट्रिंग की)।
-संदर्भ-मुक्त भाषा का एक ठोस उदाहरण देना एक खुली समस्या है जिसे पार्सिंग अभिव्यक्ति व्याकरण द्वारा पहचाना नहीं जा सकता है।<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) पार्सर जनरेटर पूरा करने में विफल हो जाएंगे। सामान्य मामले में यह एक विशेषता है कि व्याकरण स्पष्ट होने का इरादा रखता है लेकिन दोषपूर्ण है। एक पीईजी पार्सर जनरेटर अनपेक्षित अस्पष्टताओं को जल्द से जल्द हल करेगा, जो मनमाना हो सकता है और आश्चर्यजनक पार्स का कारण बन सकता है।
+इनपुट व्याकरण अस्पष्ट होने पर LL(k) और LR(k) पार्सर जनरेटर पूरा करने में विफल हो जाएंगे। सामान्य मामले में यह विशेषता है कि व्याकरण स्पष्ट होने का इरादा रखता है लेकिन दोषपूर्ण है। पीईजी पार्सर जनरेटर अनपेक्षित अस्पष्टताओं को जल्द से जल्द हल करेगा, जो मनमाना हो सकता है और आश्चर्यजनक पार्स का कारण बन सकता है।
 पीईजी व्याकरण में प्रस्तुतियों का क्रम न केवल अस्पष्टता के समाधान को प्रभावित करता है, बल्कि मिलान की गई भाषा को भी प्रभावित करता है। उदाहरण के लिए, फोर्ड के पेपर में पहले पीईजी उदाहरण पर विचार करें<ref name="For04" />(उदाहरण pegjs.org/online नोटेशन में पुनः लिखा गया है, और लेबल किया गया है {{tmath|G_1}} और {{tmath|G_2}}):
-* {{tmath|G_1}}:  {{code|code= A = "a" "b" / "a"}}
+* {{tmath|G_1}}: {{code|code= A = "a" "b" / "a"}}
-* {{tmath|G_2}}:  {{code|code= A = "a" / "a" "b"}}
+* {{tmath|G_2}}: {{code|code= A = "a" / "a" "b"}}
 फोर्ड नोट करता है कि बाद वाले पीईजी नियम में दूसरा विकल्प कभी सफल नहीं होगा क्योंकि पहली पसंद हमेशा ली जाती है यदि इनपुट स्ट्रिंग ... 'ए' से शुरू होती है।<ref name="For04" />
 विशेष रूप से, {{tmath|L(G_1)}} (अर्थात, भाषा से मेल खाती है {{tmath|G_1}}) में इनपुट ab शामिल है, लेकिन {{tmath|L(G_2)}} नहीं करता।
-इस प्रकार, PEG व्याकरण में एक नया विकल्प जोड़ने से मिलान की गई भाषा से स्ट्रिंग्स को हटाया जा सकता है, उदाहरण के लिए {{tmath|G_2}} एकल-उत्पादन व्याकरण में एक नियम का जोड़ है{{code|code= A = "a" "b"}}, जिसमें एक ऐसी स्ट्रिंग है जो मेल नहीं खाती {{tmath|G_2}}.
+इस प्रकार, PEG व्याकरण में नया विकल्प जोड़ने से मिलान की गई भाषा से स्ट्रिंग्स को हटाया जा सकता है, उदाहरण के लिए {{tmath|G_2}} एकल-उत्पादन व्याकरण में नियम का जोड़ है{{code|code= A = "a" "b"}}, जिसमें ऐसी स्ट्रिंग है जो मेल नहीं खाती {{tmath|G_2}}.
 इसके अलावा, मिलान के लिए व्याकरण का निर्माण करना {{tmath|L(G_1) \cup L(G_2)}}पीईजी व्याकरण से {{tmath|G_1}} और {{tmath|G_2}} हमेशा कोई मामूली काम नहीं होता.
-यह सीएफजी के बिल्कुल विपरीत है, जिसमें एक नए उत्पादन को जोड़ने से स्ट्रिंग्स को हटाया नहीं जा सकता है (हालांकि, यह अस्पष्टता के रूप में समस्याएं पेश कर सकता है),
+यह सीएफजी के बिल्कुल विपरीत है, जिसमें नए उत्पादन को जोड़ने से स्ट्रिंग्स को हटाया नहीं जा सकता है (हालांकि, यह अस्पष्टता के रूप में समस्याएं पेश कर सकता है),
-और एक (संभावित रूप से अस्पष्ट) व्याकरण {{tmath|L(G_1) \cup L(G_2)}} का निर्माण किया जा सकता है
+और (संभावित रूप से अस्पष्ट) व्याकरण {{tmath|L(G_1) \cup L(G_2)}} का निर्माण किया जा सकता है
 <syntaxhighlight lang="apl">
 S → start(G1) | start(G2)
 </syntaxhighlight>
 == बॉटम-अप पीईजी पार्सिंग ==
@@ Line 269: / Line 259: @@
 == व्यावहारिक उपयोग ==
-[[पायथन (प्रोग्रामिंग भाषा)]] संदर्भ कार्यान्वयन [[सीपीथॉन]] ने एलएल पार्सर|एलएल(1) पार्सर के विकल्प के रूप में संस्करण 3.9 में एक पीईजी पार्सर पेश किया और संस्करण 3.10 से केवल पीईजी का उपयोग करता है।<ref>{{Cite web |title=PEP 617 – New PEG parser for CPython {{!}} peps.python.org |url=https://peps.python.org/pep-0617/ |access-date=2023-01-16 |website=peps.python.org}}</ref>
+[[पायथन (प्रोग्रामिंग भाषा)]] संदर्भ कार्यान्वयन [[सीपीथॉन]] ने एलएल पार्सर|एलएल(1) पार्सर के विकल्प के रूप में संस्करण 3.9 में पीईजी पार्सर पेश किया और संस्करण 3.10 से केवल पीईजी का उपयोग करता है।<ref>{{Cite web |title=PEP 617 – New PEG parser for CPython {{!}} peps.python.org |url=https://peps.python.org/pep-0617/ |access-date=2023-01-16 |website=peps.python.org}}</ref>
 Jq_(प्रोग्रामिंग_भाषा)#Parsing_Expression_Grammars PEG से निकटता से संबंधित औपचारिकता का उपयोग करता है।
@@ Line 282: / Line 273: @@
 == संदर्भ ==
 {{reflist}}
 == बाहरी संबंध ==
 * [https://web.archive.org/web/20131103083443/http://mathosproject.com/updates/convert-a-string-expression-into-a-lambda-expression/ Converting a string expression into a lambda expression using an expression parser]
@@ Line 289: / Line 278: @@
 * The [[constructed language]] [[Lojban]] has a [http://www.digitalkingdom.org/~rlpowell/hobbies/lojban/grammar/ fairly large PEG grammar] allowing unambiguous parsing of Lojban text.
 * [https://www.gnu.org/software/guile/manual/html_node/PEG-Parsing.html An illustrative implementation of a PEG in Guile scheme]
-{{Parsers}}
 {{DEFAULTSORT:Parsing Expression Grammar}}[[Category: औपचारिक भाषाएँ]]

Anonymous

Search

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

Namespaces

More

Page actions

Revision as of 17:08, 3 August 2023

Contents

परिभाषा

सिंटेक्स

शब्दार्थ

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

उदाहरण

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

लाभ

नुकसान

मेमोरी खपत

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

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

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

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Revision as of 17:08, 3 August 2023

परिभाषा

सिंटेक्स

शब्दार्थ

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

उदाहरण

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

लाभ

नुकसान

मेमोरी खपत

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

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

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

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

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

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories