ऑपरेटर-प्राथमिकता पार्सर
कंप्यूटर विज्ञान में, एक ऑपरेटर प्राथमिकता पार्सर एक नीचे से ऊपर की ओर पार्सिंग|बॉटम-अप पार्सर है जो ऑपरेटर-प्राथमिकता व्याकरण की व्याख्या करता है। उदाहरण के लिए, अधिकांश कैलकुलेटर संचालन के क्रम पर निर्भर मानव-पठनीय इन्फिक्स संकेतन से रिवर्स पोलिश नोटेशन (आरपीएन) जैसे मूल्यांकन के लिए अनुकूलित प्रारूप में परिवर्तित करने के लिए ऑपरेटर प्राथमिकता पार्सर का उपयोग करते हैं।
एडवर्ड डिज्क्स्ट्रा के शंटिंग यार्ड एल्गोरिदम का उपयोग आमतौर पर ऑपरेटर प्राथमिकता पार्सर्स को लागू करने के लिए किया जाता है।
अन्य पार्सर्स से संबंध
ऑपरेटर-प्राथमिकता पार्सर एक सरल शिफ्ट-कम पार्सर है जो एलआर पार्सर|एलआर(1) व्याकरण के सबसेट को पार्स करने में सक्षम है। अधिक सटीक रूप से, ऑपरेटर-प्राथमिकता पार्सर सभी एलआर (1) व्याकरणों को पार्स कर सकता है जहां दो लगातार नॉनटर्मिनल और खाली स्ट्रिंग किसी भी नियम के दाईं ओर कभी दिखाई नहीं देते हैं।
ऑपरेटर-प्राथमिकता पार्सर व्यवहार में अक्सर उपयोग नहीं किए जाते हैं; हालाँकि उनमें कुछ गुण हैं जो उन्हें बड़े डिज़ाइन में उपयोगी बनाते हैं। सबसे पहले, वे हाथ से लिखने में काफी सरल हैं, जो आमतौर पर अधिक परिष्कृत राइट शिफ्ट-रिड्यूस पार्सर्स के मामले में नहीं है। दूसरा, उन्हें रन टाइम (प्रोग्राम जीवनचक्र चरण) पर एक ऑपरेटर तालिका से परामर्श करने के लिए लिखा जा सकता है, जो उन्हें उन भाषाओं के लिए उपयुक्त बनाता है जो पार्सिंग करते समय अपने ऑपरेटरों को जोड़ या बदल सकते हैं। (एक उदाहरण हास्केल (प्रोग्रामिंग भाषा) है, जो उपयोगकर्ता-परिभाषित इन्फिक्स ऑपरेटरों को कस्टम एसोसिएटिविटी और प्राथमिकता के साथ अनुमति देता है; परिणामस्वरूप, सभी संदर्भित मॉड्यूल के पार्सिंग के बाद प्रोग्राम पर एक ऑपरेटर-प्राथमिकता पार्सर चलाया जाना चाहिए।)
राकू (प्रोग्रामिंग भाषा) गति और गतिशीलता का संतुलन प्राप्त करने के लिए दो पुनरावर्ती वंश पार्सर के बीच एक ऑपरेटर-प्राथमिकता पार्सर को सैंडविच करता है। जीएनयू कंपाइलर संग्रह के सी और सी++ पार्सर, जो हाथ से कोडित पुनरावर्ती वंश पार्सर हैं, दोनों को एक ऑपरेटर-प्राथमिकता पार्सर द्वारा गति दी जाती है जो अंकगणितीय अभिव्यक्तियों की तुरंत जांच कर सकती है। अभिव्यक्ति पार्सिंग के लिए पुनरावर्ती वंश दृष्टिकोण को उल्लेखनीय रूप से तेज़ करने के लिए ऑपरेटर प्राथमिकता पार्सर्स को संकलक-संकलक -जनरेटेड पार्सर्स के भीतर भी एम्बेड किया गया है।[1]
प्राथमिकता चढ़ने की विधि
पूर्ववर्ती चढ़ाई विधि अभिव्यक्तियों को पार्स करने के लिए एक कॉम्पैक्ट, कुशल और लचीली एल्गोरिदम है जिसे पहली बार मार्टिन रिचर्ड्स और कॉलिन व्हिटबी-स्ट्रेवेन्स द्वारा वर्णित किया गया था।[2] ईबीएनएफ प्रारूप में एक इन्फ़िक्स-नोटेशन अभिव्यक्ति व्याकरण आमतौर पर इस तरह दिखेगा:
expression ::= equality-expression
equality-expression ::= additive-expression ( ( '==' | '!=' ) additive-expression ) *
additive-expression ::= multiplicative-expression ( ( '+' | '-' ) multiplicative-expression ) *
multiplicative-expression ::= primary ( ( '*' | '/' ) primary ) *
primary ::= '(' expression ')' | NUMBER | VARIABLE | '-' primary
प्राथमिकता के कई स्तरों के साथ, इस व्याकरण को पूर्वानुमानित पुनरावर्ती-वंशीय पार्सर के साथ लागू करना अक्षम हो सकता है। उदाहरण के लिए, किसी संख्या को पार्स करने के लिए पांच फ़ंक्शन कॉल की आवश्यकता हो सकती है: प्राथमिक तक पहुंचने तक व्याकरण में प्रत्येक गैर-टर्मिनल के लिए एक।
एक ऑपरेटर-प्राथमिकता पार्सर इसे अधिक कुशलता से कर सकता है।[1] विचार यह है कि जब तक हमें समान प्राथमिकता वाले ऑपरेटर मिलते हैं, तब तक हम अंकगणितीय परिचालनों को संबद्ध करना छोड़ सकते हैं, लेकिन उच्च प्राथमिकता वाले ऑपरेटरों का मूल्यांकन करने के लिए हमें एक अस्थायी परिणाम सहेजना होगा। यहां प्रस्तुत एल्गोरिदम को स्पष्ट स्टैक की आवश्यकता नहीं है; इसके बजाय, यह स्टैक को लागू करने के लिए पुनरावर्ती कॉल का उपयोग करता है।
एल्गोरिथम दिज्क्स्ट्रा शंटिंग यार्ड एल्गोरिथम की तरह शुद्ध ऑपरेटर-प्राथमिकता पार्सर नहीं है। यह मानता है कि प्राथमिक नॉनटर्मिनल को एक अलग सबरूटीन में पार्स किया जाता है, जैसे कि पुनरावर्ती वंश पार्सर में।
स्यूडोकोड
एल्गोरिथम के लिए छद्मकोड इस प्रकार है। पार्सर फ़ंक्शन parse_expression पर प्रारंभ होता है। प्राथमिकता स्तर 0 से अधिक या उसके बराबर हैं।
parse_expression()
'वापसी' parse_expression_1(parse_primary(), 0)
parse_expression_1(lhs, min_precedence)
आगे देखें := अगले टोकन पर नज़र डालें
'जबकि' लुकहेड एक बाइनरी ऑपरेटर है जिसकी प्राथमिकता >=min_precedence है
ऑप := आगे देखो
अगले टोकन पर आगे बढ़ें
rhs := पार्स_प्राइमरी ()
आगे देखें := अगले टोकन पर नज़र डालें
'जबकि' लुकहेड एक बाइनरी ऑपरेटर है जिसकी प्राथमिकता अधिक है
op's, या एक राइट-एसोसिएटिव ऑपरेटर की तुलना में
जिसकी पूर्वता ऑप के बराबर है
rhs := parse_expression_1 (rhs, op + की पूर्वता (यदि लुकहेड प्राथमिकता अधिक है तो 1, अन्यथा 0))
आगे देखें := अगले टोकन पर नज़र डालें
एलएचएस := ऑपरेंड एलएचएस और आरएचएस के साथ ऑप लागू करने का परिणाम
'वापसी' एलएचएस
ध्यान दें कि इस तरह के उत्पादन नियम के मामले में (जहां ऑपरेटर केवल एक बार ही उपस्थित हो सकता है):
equality-expression ::= additive-expression ( '==' | '!=' ) additive-expression
एल्गोरिदम को केवल उन बाइनरी ऑपरेटरों को स्वीकार करने के लिए संशोधित किया जाना चाहिए जिनकी प्राथमिकता > min_precedence है।
एल्गोरिथ्म का उदाहरण निष्पादन
अभिव्यक्ति 2 + 3 * 4 + 5 == 19 पर एक उदाहरण निष्पादन इस प्रकार है। हम समानता वाले भावों को 0, योगात्मक भावों को 1, गुणात्मक भावों को 2 प्राथमिकता देते हैं।
parse_expression_1 (lhs = 2, min_precedence = 0)
- लुकहेड टोकन + है, प्राथमिकता 1 के साथ। बाहरी while लूप दर्ज किया गया है।
- ऑप + (प्राथमिकता 1) है और इनपुट उन्नत है
- आरएचएस 3 है
- लुकहेड टोकन * है, प्राथमिकता 2 के साथ। आंतरिक while लूप दर्ज किया गया है।
parse_expression_1 (lhs = 3, min_precedence = 2)
- लुकहेड टोकन * है, प्राथमिकता 2 के साथ। बाहरी while लूप दर्ज किया गया है।
- ऑप * (प्राथमिकता 2) है और इनपुट उन्नत है
- आरएचएस 4 है
- अगला टोकन + है, प्राथमिकता 1 के साथ। आंतरिक जबकि लूप दर्ज नहीं किया गया है।
- एलएचएस को 3*4 = 12 असाइन किया गया है
- अगला टोकन + है, प्राथमिकता 1 के साथ। बाहरी while लूप बचा है।
- 12 लौटा दिया गया है।
- लुकहेड टोकन + है, प्राथमिकता 1 के साथ। आंतरिक जबकि लूप दर्ज नहीं किया गया है।
- एलएचएस को 2+12 = 14 सौंपा गया है
- लुकहेड टोकन + है, प्राथमिकता 1 के साथ। बाहरी जबकि लूप नहीं छोड़ा गया है।
- ऑप + (प्राथमिकता 1) है और इनपुट उन्नत है
- आरएचएस 5 है
- अगला टोकन == है, प्राथमिकता 0 के साथ। आंतरिक जबकि लूप दर्ज नहीं किया गया है।
- एलएचएस को 14+5 = 19 सौंपा गया है
- अगला टोकन == है, प्राथमिकता 0 के साथ। बाहरी जबकि लूप नहीं छोड़ा गया है।
- ऑप == (प्राथमिकता 0) है और इनपुट उन्नत है
- आरएचएस 19 है
- अगला टोकन एंड-ऑफ़-लाइन है, जो ऑपरेटर नहीं है। आंतरिक जबकि लूप दर्ज नहीं किया गया है।
- एलएचएस को 19 == 19 के मूल्यांकन का परिणाम सौंपा गया है, उदाहरण के लिए 1 (जैसा कि सी मानक में है)।
- अगला टोकन एंड-ऑफ़-लाइन है, जो ऑपरेटर नहीं है। बाहरी while लूप बचा है।
1 लौटा दिया गया है.
प्रैट पार्सिंग
प्रैट पार्सिंग के रूप में जाना जाने वाला एक अन्य पूर्वता पार्सर का वर्णन पहली बार वॉन प्रैट ने 1973 के पेपर टॉप डाउन ऑपरेटर पूर्वता में किया था,[3] पुनरावर्ती वंश पार्सर पर आधारित। हालाँकि यह प्राथमिकता चढ़ाई से पहले का है, इसे प्राथमिकता चढ़ाई के सामान्यीकरण के रूप में देखा जा सकता है।[4] प्रैट ने पार्सर को मूल रूप से COLL प्रोग्रामिंग भाषा को लागू करने के लिए डिज़ाइन किया था, और उनकी देखरेख में मास्टर्स थीसिस में इसका अधिक गहराई से इलाज किया गया था।[5] ट्यूटोरियल और कार्यान्वयन:
- डगलस क्रॉकफ़ोर्ड ने जेएसलिंट में जावास्क्रिप्ट पार्सर को प्रैट पार्सिंग पर आधारित किया।[6]
- प्रीसीडेंस क्लाइंबिंग और प्रैट पार्सिंग के पायथन कार्यान्वयन के बीच तुलना: प्रैट पार्सिंग और प्रीसीडेंस क्लाइंबिंग आर द सेम एल्गोरिथम (2016) एंडी चू द्वारा
- रस्ट (प्रोग्रामिंग भाषा) का उपयोग करने वाला ट्यूटोरियल: सरल लेकिन शक्तिशाली प्रैट पार्सिंग (2020) एलेक्सी क्लाडोव द्वारा
- पायथन (प्रोग्रामिंग भाषा) का उपयोग करने वाला ट्यूटोरियल: फ्रेड्रिक लुंड द्वारा पायथन में सरल टॉप-डाउन पार्सिंग (2008) Archived 2015-02-28 at the Wayback Machine
- जावा (प्रोग्रामिंग भाषा) का उपयोग करने वाला ट्यूटोरियल: made-easy/ प्रैट पार्सर्स: एक्सप्रेशन पार्सिंग मेड ईज़ी (2011) क्राफ्टिंग इंटरप्रिटर्स के लेखक बॉब निस्ट्रॉम द्वारा
- सी शार्प (प्रोग्रामिंग भाषा) में कार्यान्वयन | सी #: Gratt: .NET मानक के लिए एक जेनेरिक वॉन प्रैट का टॉप-डाउन ऑपरेटर प्राथमिकता पार्सर (बॉब निस्ट्रॉम द्वारा प्रस्तुत जावा कार्यान्वयन से प्रेरित एक सामान्य प्रोग्रामिंग संस्करण made -ईज़ी/ प्रैट पार्सर्स: एक्सप्रेशन पार्सिंग मेड ईज़ी )
वैकल्पिक तरीके
ऑपरेटर प्राथमिकता नियम लागू करने के अन्य तरीके भी हैं। एक है मूल अभिव्यक्ति का एक वृक्ष बनाना और फिर उस पर वृक्ष पुनर्लेखन नियम लागू करना।
ऐसे पेड़ों को पारंपरिक रूप से पेड़ों के लिए उपयोग की जाने वाली डेटा संरचनाओं का उपयोग करके लागू करने की आवश्यकता नहीं है। इसके बजाय, टोकन को फ्लैट संरचनाओं में संग्रहीत किया जा सकता है, जैसे कि टेबल, साथ ही एक प्राथमिकता सूची बनाकर जो बताती है कि किस क्रम में किन तत्वों को संसाधित करना है।
पूर्ण कोष्ठक
एक अन्य तरीका यह है कि पहले अभिव्यक्ति को पूरी तरह से कोष्ठक में रखा जाए, प्रत्येक ऑपरेटर के चारों ओर कई कोष्ठक डाले जाएं, ताकि वे एक रैखिक, बाएं से दाएं पार्सर के साथ पार्स करने पर भी सही प्राथमिकता की ओर ले जाएं। इस एल्गोरिदम का उपयोग प्रारंभिक फोरट्रान#फोरट्रान कंपाइलर में किया गया था:[7] <ब्लॉककोट> फोरट्रान I कंपाइलर प्रत्येक ऑपरेटर को कोष्ठकों के अनुक्रम के साथ विस्तारित करेगा। एल्गोरिथम के सरलीकृत रूप में, यह होगा
- बदलना
+और–साथ))+((और))-((, क्रमश; - बदलना
*और/साथ)*(और)/(, क्रमश; - जोड़ना
((प्रत्येक अभिव्यक्ति की शुरुआत में और मूल अभिव्यक्ति में प्रत्येक बाएँ कोष्ठक के बाद; और - जोड़ना
))अभिव्यक्ति के अंत में और मूल अभिव्यक्ति में प्रत्येक दाएँ कोष्ठक से पहले।
हालांकि स्पष्ट नहीं है, एल्गोरिथ्म सही था, और, डोनाल्ड नुथ के शब्दों में, "परिणामस्वरूप सूत्र उचित रूप से कोष्ठक में रखा गया है, विश्वास करें या न करें।"[8] </ब्लॉककोट>
 | This section is missing information about why parenthesization works. (May 2023) |
एक साधारण सी एप्लिकेशन का उदाहरण कोड जो बुनियादी गणित ऑपरेटरों के कोष्ठक को संभालता है (+, -, *, /, ^, ( और )):
#include <stdio.h>
#include <string.h>
// The command-line argument boundary is our lexer.
int main(int argc, char *argv[]) {
int i;
printf("((((");
for (i=1; i!=argc; i++) {
// strlen(argv[i]) == 2
if (argv[i] && !argv[i][1]) {
switch (*argv[i]) {
case '(': printf("(((("); continue;
case ')': printf("))))"); continue;
case '^': printf(")^("); continue;
case '*': printf("))*(("); continue;
case '/': printf("))/(("); continue;
case '+':
// unary check: either first or had an operator expecting secondary argument
if (i == 1 || strchr("(^*/+-", *argv[i-1]))
printf("+");
else
printf(")))+(((");
continue;
case '-':
if (i == 1 || strchr("(^*/+-", *argv[i-1]))
printf("-");
else
printf(")))-(((");
continue;
}
}
printf("%s", argv[i]);
}
printf("))))\n");
return 0;
}
उदाहरण के लिए, जब मापदंडों के साथ कमांड लाइन से संकलित और आह्वान किया जाता है
a * b + c ^ d / e
वह उत्पादन करता है
((((a))*((b)))+(((c)^(d))/((e))))
कंसोल पर आउटपुट के रूप में।
इस रणनीति की एक सीमा यह है कि यूनरी ऑपरेटरों को इंफिक्स ऑपरेटरों की तुलना में अधिक प्राथमिकता मिलनी चाहिए। उपरोक्त कोड में नकारात्मक ऑपरेटर की घातांक की तुलना में अधिक प्राथमिकता है। इस इनपुट के साथ प्रोग्राम चला रहे हैं <पूर्व>- ए ^ 2</पूर्व> यह आउटपुट उत्पन्न करता है
((((-a)^(2))))
जो संभवतः वह उद्देश्य नहीं है।
संदर्भ
- ↑ 1.0 1.1 Harwell, Sam (2008-08-29). "ऑपरेटर प्राथमिकता पार्सर". ANTLR3 Wiki. Retrieved 2017-10-25.
- ↑ Richards, Martin; Whitby-Strevens, Colin (1979). BCPL — the language and its compiler. Cambridge University Press. ISBN 9780521219655.
- ↑ Pratt, Vaughan. "Top down operator precedence." Proceedings of the 1st Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (1973).
- ↑ Norvell, Theodore. "पुनरावर्ती वंश द्वारा पार्सिंग अभिव्यक्तियाँ". www.engr.mun.ca.
The purpose of this post is to [... start] with precedence climbing and refactoring it to use the command pattern until we arrive at a Pratt parser. [This is the author who coined the term "precedence climbing".]
- ↑ Van De Vanter, Michael L. "A Formalization and Correctness Proof of the CGOL Language System." (Master's Thesis). MIT Laboratory for Computer Science Technical Report MIT-LCS-TR-147 (Cambridge, Massachusetts). 1975.
- ↑ Crockford, D (2007-02-21). "टॉप डाउन ऑपरेटर प्राथमिकता".
- ↑ Padua, David (2000). "फोरट्रान I कंपाइलर" (PDF). Computing in Science & Engineering. 2 (1): 70–75. Bibcode:2000CSE.....2a..70P. doi:10.1109/5992.814661.
- ↑ Knuth, Donald E. (1962). "लेखन संकलनकर्ताओं का इतिहास". Computers and Automation. Edmund C. Berkeley. 11 (12): 8–14.
बाहरी संबंध
- Clarke, Keith (1992-05-26). "Re: compact recursive-descent parsing of expressions". Retrieved 2012-01-24.
- Example C++ code by Keith Clarke for parsing infix expressions using the precedence climbing method
- Samelson, Klaus; Friedrich L. Bauer (February 1960). "Sequential formula translation". Communications of the ACM. 3 (2): 76–83. doi:10.1145/366959.366968.
- Parser for expression with infix notation using precedence lists
