पार्सिंग अभिव्यक्ति व्याकरण

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

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

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

परिभाषा

सिंटेक्स

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

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

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

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

Operator	Priority
(e)	5
&e, !e	4
e*, e+, e?	3
e1 e2	2
e1 / e2	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'

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

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

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

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

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

लाभ

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

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

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

हानि

मेमोरी खपत

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

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

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

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

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

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

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

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

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

string-of-a ← 'a'+

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

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

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

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

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

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

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

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

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

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

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

फोर्ड नोट करता है कि बाद वाले पीईजी नियम में दूसरा विकल्प कभी सफल नहीं होगा क्योंकि पहली पसंद हमेशा ली जाती है यदि इनपुट स्ट्रिंग ... 'ए' से प्रारंभ होती है। विशेष रूप से, $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)

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

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

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

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

Jq_(प्रोग्रामिंग_भाषा)#Parsing_Expression_Grammars PEG से निकटता से संबंधित औपचारिकता का उपयोग करता है।

यह भी देखें

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

बाहरी संबंध

• 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