ऑपरेटर-प्राथमिकता पार्सर
कंप्यूटर विज्ञान में, एक "ऑपरेटर प्राथमिकता पार्सर" एक बॉटम-अप पार्सर है जो ऑपरेटर प्राथमिकता व्याकरण की व्याख्या करता है। उदाहरण के लिए, अधिकांश कैलकुलेटर संचालन के क्रम पर निर्भर मानव-पठनीयइन्फिक्स संकेतन से रिवर्स पोलिश नोटेशन (आरपीएन) जैसे मूल्यांकन के लिए अनुकूलित प्रारूप में परिवर्तित करने के लिए ऑपरेटर प्राथमिकता पार्सर का उपयोग करते हैं।
एडस्गर डाईक्स्ट्रा के शंटिंग यार्ड एल्गोरिथ्म का उपयोग सामान्यतः ऑपरेटर प्राथमिकता पार्सर को लागू करने के लिए किया जाता है।
अन्य पार्सर से संबंध
ऑपरेटर-प्राधिकरण पार्सर एक सरल शिफ्ट-कम पार्सर है जो LR(1) व्याकरणों का एक उपसंख्या को पार्स करने में सक्षम होता है। अधिक सटीक रूप से कहें तो, ऑपरेटर-प्राधिकरण पार्सर सभी LR(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] विचार यह है कि जब तक हमें समान प्राथमिकता वाले ऑपरेटर मिलते हैं, तब तक हम अंकगणितीय परिचालनों को संबद्ध करना छोड़ सकते हैं,परंतु उच्च प्राथमिकता वाले ऑपरेटरों का मूल्यांकन करने के लिए हमें एक अस्थायी परिणाम को सेव करना होगा। यहां प्रस्तुत एल्गोरिथ्म को स्पष्ट स्टैक की आवश्यकता नहीं है, इसके अतिरिक्त, यह स्टैक को लागू करने के लिए पुनरावर्ती कॉल का उपयोग करता है।
एल्गोरिथ्म दिज्क्स्ट्रा शंटिंग यार्ड एल्गोरिथ्म की तरह शुद्ध "ऑपरेटर प्राथमिकता पार्सर" नहीं है। यह मानता है कि प्राथमिक नॉनटर्मिनल को एक अलग सबरूटीन में पार्स किया जाता है, जैसे कि पुनरावर्ती डिसेंट पार्सर में किया जाता है।
स्यूडोकोड
एल्गोरिथम के लिए छद्मकोड इस प्रकार है। पार्सर फ़ंक्शन पार्सर प्राथमिकता पर प्रारंभ होता है। प्राथमिकता स्तर 0 से अधिक या उसके बराबर हैं।
parse _expression() return parse_expression_1(parse_primary(), 0)
parse _expression_1(lhs, min_precedence lookahead := peek next token
while lookahead is a binary operator whose precedence is >= min_precedence
op := lookahead
advance to next token
rhs := parse _primary ()
lookahead := peek next token
while lookahead is a binary operator whose precedence is greater
than op's, or a right-associative operator
whose precedence is equal to op's
rhs := parse _expression_1 (rhs, precedence of op + (1 if lookahead precedence is greater, else 0))
lookahead := peek next token
lhs := the result of applying op with operands lhs and rhs
return lhs
ध्यान दें कि इस तरह के उत्पादन नियम के स्थिति में जहां ऑपरेटर केवल एक बार ही उपस्थित हो सकता है:
equality-expression ::= additive-expression ( '==' | '!=' ) additive-expression
एल्गोरिथ्म को केवल उन बाइनरी ऑपरेटरों को स्वीकार करने के लिए संशोधित किया जाना चाहिए जिनकी प्रिसीडेंस> min_प्रिसीडेंस. है।
एल्गोरिथ्म का उदाहरण निष्पादन
एक उदाहरण का अभिव्यक्ति पर निष्पादन 2 + 3 * 4 + 5 == 19 पर निम्नलिखित रूप में हो सकता है। हम समानता अभिव्यक्तियों को प्राथमिकता 0, योजनात्मक अभिव्यक्तियों को 1, और गुणनात्मक अभिव्यक्तियों को 2 देते हैं।
"पार्स _"एक्सप्रेशन"_1 (lhs = 2, min_"एक्सप्रेशन" = 0)"।
- लुकहेड टोकन + है, प्राथमिकता 1 के साथ। बाहरी ह्वाइल लूप दर्ज किया गया है।
- op + (प्राथमिकता 1) है और इनपुट उन्नत है
- rhs 3 है
- यदि लुकआहेड टोकन "*" है और इसकी प्राथमिकता 2 है, तो आप आंतरिक वाइल लूप में प्रवेश करेंगे।
पार्स_अभिव्यक्ति_1 (lhs = 3, न्यूनतम_प्रासंगिकता = 2)
- लुकहेड टोकन * है, प्राथमिकता 2 के साथ। बाहरी लूप दर्ज किया गया है।
- op * ( प्राथमिकता 2) है और इनपुट उन्नत है
- rhs 4 है
- अगला टोकन + है, प्राथमिकता 1 के साथ। आंतरिक जबकि लूप दर्ज नहीं किया गया है।
- lhs को 3*4 = 12 सौंपा गया है
- अगला टोकन + है, प्राथमिकता 1 के साथ। बाहरी ह्वाइल लूप बचा हुआ है।
- 12 लौटा दिया गया है
- लुकहेड टोकन + है, प्राथमिकता 1 के साथ। आंतरिक जबकि लूप दर्ज नहीं किया गया है।
- lhs 2+12 = 14 दिया गया है
- लुकहेड टोकन + है, प्राथमिकता 1 के साथ। बाहरी जबकि लूप नहीं छोड़ा गया है।
- op+ (प्राथमिकता 1) है और इनपुट उन्नत है
- lhs 5 है
- अगला टोकन == है, प्राथमिकता 0 के साथ। आंतरिक जबकि लूप दर्ज नहीं किया गया है।
- lhs 14+5 = 19 निर्धारित किया गया है
- अगला टोकन == है, प्राथमिकता 0 के साथ। बाहरी जबकि लूप नहीं छोड़ा गया है।
- ऑप ==== (प्राथमिकता 0) है और इनपुट उन्नत है
- lhs 19 है
- अगला टोकन एंड-ऑफ़-लाइन है, जो ऑपरेटर नहीं है। आंतरिक जबकि लूप दर्ज नहीं किया गया है।
- lhs को 19 == 19 के मूल्यांकन का परिणाम सौंपा गया है, उदाहरण के लिए 1।
- अगला टोकन एंड-ऑफ़-लाइन है, जो ऑपरेटर नहीं है। बाहरी लूप बचा है।
प्रैट पार्सिंग
प्रैट पार्सिंग के रूप में जाना जाने वाला एक अन्य पूर्वता पार्सर का वर्णन पहली बार वॉन प्रैट ने 1973 के पेपर टॉप डाउन ऑपरेटर पूर्वता में किया था,[3] पुनरावर्ती डिसेंट पार्सर पर आधारित है। यद्यपि यह प्राथमिकता डिसेंट से पहले का है, इसे प्राथमिकता डिसेंट के सामान्यीकरण के रूप में देखा जा सकता है।[4] प्रैट ने पार्सर को मूल रूप से कॉल प्रोग्रामिंग भाषा को लागू करने के लिए पार्सर डिज़ाइन किया था और उसका अध्ययन उनके प्रशिक्षण के अंतर्गत एक मास्टर्स थीसिस में और भी गहराई से किया गया था।[5]
ट्यूटोरियल और कार्यान्वयन:
- डगलस क्रॉकफ़ोर्ड ने जेएसलिंट में जावास्क्रिप्ट पार्सर को प्रैट पार्सिंग पर आधारित बनाया था।[6]
- प्राथमिकता क्लाइंबिंग और प्रैट पार्सिंग के पायथन कार्यान्वयन के बीच तुलना: एंडी चू द्वारा "प्रैट पार्सिंग और प्राथमिकता क्लाइंबिंग एक ही एल्गोरिदम हैं" (2016)
- रस्ट का उपयोग करने वाला ट्यूटोरियल: एलेक्सी कल्दोव द्वारा "सरल परंतु शक्तिशाली प्रैट पार्सिंग" (2020)
- पायथन का उपयोग करने वाला ट्यूटोरियल: फ्रेड्रिक लुंड द्वारा "पायथन में सरल टॉप-डाउन पार्सिंग" (2008) वेबैक मशीन पर 2015-02-28 को संग्रहीत किया गया:
- जावा का उपयोग करते हुए ट्यूटोरियल: "प्रैट पार्सर्स: एक्सप्रेशन पार्सिंग मेड ईज़ी" (2011) क्राफ्टिंग इंटरप्रिटर्स के लेखक बॉब निस्ट्रॉम द्वारा किया गया ।
- "ग्रेट" एक सी# में प्राथमिक वायन प्रैट के ऊपर से नीचे ऑपरेटर प्राधिकरण पार्सर है, जो नेट मानक के लिए तैयार किया गया है। यह सी# में विकसित किया गया है और जावा परिवर्तन के संदर्भ में बॉब नायस्ट्रोम द्वारा प्रस्तुत किया गया "प्रैट पार्सर्स: एक्सप्रेशन पार्सिंग मेड ईज़ी" नामक जावा अनुप्रयोग से प्रेरित है।।
वैकल्पिक विधि
ऑपरेटर प्राथमिकता नियमों को लागू करने के लिए अन्य विधि भी हैं। एक विधि यह है कि हम मूल व्यक्ति का एक ट्री बनाते हैं और फिर उस पर ट्री रिव्राइट नियम का उपयोग करते हैं। इस विधि को ट्री बेस्ड पार्सिंग कहते हैं।
वाक्य ट्री को पारंपरिक विधि से वृक्ष संरचना के डेटा संरचनाओं का उपयोग करके विकसित करने की ज़रूरत नहीं होती है। इसके अतिरिक्त, टोकन्स को फ्लैट संरचनाओं, जैसे कि टेबल्स में संग्रहीत किया जा सकता है, जिससे प्राथमिकता सूची बनाई जा सकती है जो यह दर्शाती है कि कौन से तत्व किस अनुक्रम में प्रोसेस करने के लिए हैं।
पूर्ण कोष्ठक
एक अन्य विधि यह है कि पहले अभिव्यक्ति को पूरी तरह से कोष्ठक में रखा जाए, प्रत्येक ऑपरेटर के चारों ओर कई कोष्ठक डाले जाएं, जिससे वे एक रैखिक, बाएं से दाएं पार्सर के साथ पार्स करने पर भी सही प्राथमिकता की ओर ले जाएं। इस एल्गोरिथ्म का उपयोग प्रारंभिक फोरट्रान फोरट्रान कंपाइलर में किया गया था:[7]
फोर्ट्रान कंपाइलर ने प्रत्येक ऑपरेटर को एक सिक्वेंस ऑफ़ पैरेंथिज़ के साथ विस्तृत किया था। एक सरलीकृत रूप में एल्गोरिदम में, यह किया गया था
- replace
+and–with))+((and))-((, respectively; - replace
*and/with)*(and)/(, respectively; - add
((प्रत्येक "एक्सप्रेशन" की शुरुआत में और मूल अभिव्यक्ति में प्रत्येक बाएँ कोष्ठक के बाद; और - add
))"एक्सप्रेशन" के अंत में और मूल अभिव्यक्ति में प्रत्येक दाएँ कोष्ठक से पहले.।
यद्यपि स्पष्ट नहीं है, एल्गोरिथ्म सही था, और, डोनाल्ड नुथ के शब्दों में, "परिणामस्वरूप सूत्र उचित रूप से कोष्ठक में रखा गया है, विश्वास करें या न करें।"[8]
यहां एक सरल C एप्लिकेशन का उदाहरण दिया गया है जो बेसिक मैथ ऑपरेटर (+, -, *, /, ^, ( and )) के पैरेंथेसिसेशन को हैंडल करता है।
#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))))
कंसोल पर आउटपुट के रूप में इस रणनीति की एक सीमा यह है कि यूनरी ऑपरेटरों को इंफिक्स ऑपरेटरों की तुलना में अधिक प्राथमिकता मिलनी चाहिए। उपरोक्त कोड में नकारात्मक ऑपरेटर की घातांक की तुलना में अधिक प्राथमिकता है। इस इनपुट के साथ प्रोग्राम चला रहे हैं यह आउटपुट उत्पन्न करता है
((((-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
