अंकगणित का व्याकरण या ANTLR पर एक कैलकुलेटर लिखें

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



शुरू करने के लिए, आवश्यक उपकरणों पर विचार करें। हमें आवश्यकता होगी:

1. ANTLRWorks - व्याकरण विकास और डिबगिंग वातावरण
2. ANTLR v3 - स्वयं ANTLR (लेखन के समय, नवीनतम संस्करण 3.2 है)
3. सी # रनटाइम डिस्ट्रीब्यूशन (Antlr3.Runtime.dll) - जनरेटर के साथ काम करने के लिए .NET लाइब्रेरी
4. विजुअल स्टूडियो - C # कोड को कंपाइल और डीबग करने का कोई अन्य टूल
5. जावा रनटाइम - चूंकि ANTLR और ANTLRWorks जावा में लिखे गए हैं

ANTLR से संबंधित सब कुछ, यानी पहले तीन बिंदु, आधिकारिक वेबसाइट http://www.antlr.org/download.html से मुफ्त में डाउनलोड किए जा सकते हैं, यानी बिना कुछ लिए।



अब कुछ शब्द, वास्तव में, ANTLR के बारे में (हम विकिपीडिया की ओर मुड़ते हैं)। ANTLR (भाषा मान्यता के लिए एक और उपकरण) एक पार्सर जनरेटर है जो आपको लक्ष्य प्रोग्रामिंग भाषाओं (C ++, Java, C #, पायथन, रूबी) में से एक में पार्सर प्रोग्राम (जैसे एक लेक्सिकल विश्लेषक) बनाने की अनुमति देता है। एलएल (*) के वर्णन के अनुसार - RBNF के करीब की भाषा में व्याकरण। इस परियोजना के लेखक सैन फ्रांसिस्को विश्वविद्यालय से प्रोफेसर टेरेंस पार्र हैं। मुझे कहना होगा कि परियोजना खुला स्रोत है और बीएसडी लाइसेंस के तहत वितरित की जाती है।

1. समस्या का विवरण

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

2. व्याकरण विकास

यह ANTLRWorks लॉन्च करने और हमारे व्याकरण के साथ एक परियोजना बनाने का समय है। लॉन्च होने पर, ANTLRWorks पूछेंगे कि हम किस प्रकार का दस्तावेज़ बनाना चाहते हैं। "ANTLR 3 व्याकरण (* .g)" का चयन करें। दिखाई देने वाली विंडो में, व्याकरण का नाम दर्ज करें (इसे "कैल्क" कहते हैं), डिफ़ॉल्ट रूप से टाइप करें ("संयुक्त व्याकरण")। इसका मतलब है कि एक फ़ाइल में हमारे पास शाब्दिक और पार्सर दोनों व्याकरण के नियम होंगे। आगे की असहमति से बचने के लिए, आइए हम लेक्सिकल एनालाइज़र को लेक्सर और सिंटैक्स को पार्सर कहते हैं। यदि आप ड्रॉप-डाउन सूची में अन्य विकल्पों को देखते हैं, तो आप दर्ज किए गए नोटेशन को समझेंगे। आपको याद दिलाता हूं कि एक लेक्सर पात्रों की एक धारा से टोकन (टोकन) का चयन करता है: पूर्णांक, पहचानकर्ता, तार, आदि, और पार्सर यह जांचता है कि टोकन स्ट्रीम में टोकन सही क्रम में हैं या नहीं। मैं आइडेंटिफायर और इंटेगर को टिक करने की भी सलाह देता हूं ताकि हमारे व्याकरण में पहले से ही पहचानकर्ताओं और पूर्णांकों के लिए नियम हों। परिणाम निम्न होना चाहिए:



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



आइए अब INT नियम के लिए एकमात्र विकल्प देखें। ANTLR में '0' .. '9' + का अर्थ है कि INT अंकों का एक अनुक्रम है जिसमें कम से कम एक अंक होता है। यदि प्रतीक '+' के बजाय उदाहरण के लिए, एक सिवोल '*' था, तो इसका मतलब यह होगा कि अंकों का क्रम खाली हो सकता है। आईडी नियम कुछ अधिक जटिल है और इसका मतलब है कि एक आईडी लोअरकेस और अपरकेस लैटिन अक्षरों, संख्याओं, अंडरस्कोर और अक्षर या अंडरस्कोर से शुरू होने वाले वर्णों का एक क्रम है।



ठीक है, अब हम पार्सर के लिए या वैज्ञानिक स्वयंसिद्ध में अपने स्वयं के पहले नियम पर लिखेंगे, अर्थात् , वह नियम जहां से पार्सर टोकन की धारा की जांच करना शुरू कर देगा। और इसलिए:

 calc	
	 : कथन +
	 ;

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

 कथन
	 : ऑनलाइन नया विस्तार करें
	 |  ID '=' expr NEWLINE
	 |  NEWLINE
	 ;

जो लोग भूल गए हैं कि विकल्प क्या हैं, इस नियम पर यह याद रखना सीख सकते हैं कि यह किस प्रकार का जानवर है। एक विकल्प संभव टोकन आदेश विकल्पों में से एक है। अर्थात, स्टेटमेंट किसी भी एक्सप्रेशन (expr) लाइन फीड (NEWLINE) के साथ समाप्त हो रहा है, या एक असाइनमेंट ऑपरेशन लाइन फीड के साथ समाप्त हो रहा है, या केवल एक लाइन फीड है। हां, वैसे, नए ऑनलाइन नियम को लेसर नियमों में जोड़ना न भूलें, जिसे मैं व्याकरण फ़ाइल के अंत में रखने की सलाह देता हूं:

 NEWLINE: '\ r'?  '\ n'
	 ;

संकेत "?" इसका मतलब है कि वर्ण '\ r' वाक्य में 1 समय में मौजूद होना चाहिए या बिल्कुल मौजूद नहीं होना चाहिए।



अब एक नियम पर विचार करें जिसमें दो विकल्पों को एक में जोड़ा जाता है:

 expr
	 : मल्टी एक्सप्रेशन ('+' मल्टी एक्सप्रेशन | '-' मल्टी एक्सप्रेशन) *
	 ;

ANTLR भाषा में, इसका मतलब है कि expr मनमाना संकेतों के साथ शब्दों का एक मनमाना अनुक्रम है। उदाहरण के लिए, मल्टी एक्सप्रेशन-मल्टीएक्सप्रेशन + मल्टीएक्सप्रेशन-मल्टीएक्सप्रेशन-मल्टीएक्सप्रेशन + मल्टीएक्सप्रेशन।



मैं शेष नियमों पर विचार नहीं करूंगा (इसके अलावा, उनमें से केवल दो शेष हैं), लेकिन बस उन्हें इस प्रकार लाएं:

 multExpression
	 : a1 = परमाणु ('*' a2 = atom | '/' a2 = atom) *
	 ;
	
 परमाणु
	 : आईडी
	 |  INT
	 |  '(' expr ')'
	 ;

यदि आप नियमों को एक व्याकरण फ़ाइल में लिखते हैं जैसा कि आप पढ़ते हैं, तो आप शायद पहले से ही देख चुके हैं कि प्रत्येक नियम के लिए ANTLRWorks एक ग्राफ खींचता है। क्या आपने गौर किया है? बहुत बढ़िया! अब मुझे प्रत्येक नियम पर टिप्पणी करने की आवश्यकता नहीं है:



यहीं पर व्याकरण समाप्त होता है। क्या यह वास्तव में सरल है?

3. पार्सर और लेसर की उत्पत्ति और प्रक्षेपण

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

 विकल्प
 {
	 भाषा = CSharp2;
 }
 @ अपर :: नाम स्थान {उत्पन्न}
 @lexer :: नाम स्थान {उत्पन्न}

ये पंक्तियाँ ANTLR को बताएंगी कि हम C # कोड प्राप्त करना चाहते हैं, और यह भी चाहते हैं कि जनरेट किए गए नेमस्पेस में parser और lexer कक्षाएं हों। सभी, आप कोड उत्पन्न कर सकते हैं। ऐसा करने के लिए, एक .bat फ़ाइल बनाएं जिसमें हम निम्नलिखित सामग्री जोड़ते हैं:

 java -jar antlr-3.2.jar -o उत्पन्न कैलगरी
 ठहराव

कृपया ध्यान दें कि मेरे मामले में .bat फ़ाइल antlr-3.2.jar और Calc.g फ़ाइलों के समान निर्देशिका में है।

"-O" स्विच उस फ़ोल्डर के लिए पथ निर्दिष्ट करता है जिसमें उत्पन्न फाइलें झूठ होंगी। ठहराव केवल सुविधा के लिए किया गया था - ताकि त्रुटियों के मामले में हम इसके बारे में पता लगा सकें।

हम .bat फ़ाइल लॉन्च करते हैं और जनरेट किए गए फ़ोल्डर में देखते हैं। वहां हम तीन फाइलें देखते हैं:

• CalcLexer.cs - lexer कोड
• CalcParser.cs - पार्सर कोड
• Calc.tokens - टोकन की सूची के साथ उपयोगिता फ़ाइल

पार्सर को शुरू करने के लिए, मैंने विजुअल स्टूडियो में कंसोल एप्लिकेशन बनाया और इसमें दो प्राप्त .cs फाइलें जोड़ीं। सुविधा के लिए, नामस्थान को जेनरेटेड कहा जाता है, इसलिए किसी भी उपयोग '' को लिखने के लिए नहीं। यह महत्वपूर्ण है कि प्रोजेक्ट में C # रनटाइम डिस्ट्रीब्यूशन (Antlr3.Runtime.dll फ़ाइल को DOT-NET-runtime-3.1.1.zip संग्रह में ANTLR प्रोजेक्ट साइट से डाउनलोड किया गया) के संदर्भ में जोड़ना न भूलें। निम्नलिखित कोड को मुख्य () फ़ंक्शन में जोड़ें:

 कोशिश
 {
	 // इनपुट कंसोल करने के लिए वर्णों की इनपुट स्ट्रीम सेट करें
	 ANTLReaderStream इनपुट = नया ANTLReaderStream (Console.In);
	 // इस थ्रेड पर लेसर सेट करें
	 CalcLexer lexer = नया CalcLexer (इनपुट);
	 // एक लेक्सर-आधारित टोकन स्ट्रीम बनाएं
	 CommonTokenStream टोकन = नया CommonTokenStream (lexer);
	 // पार्सर बनाएं
	 CalcParser parser = नया CalcParser (टोकन);
	 // और पहला व्याकरण नियम चलाएं !!!
	 parser.calc ();
 }
 पकड़ (अपवाद ई)
 {
	 Console.WriteLine (e.Message);
 }
 Console.ReadKey ();

हो गया !!! संकलित करें और चलाएं।



ध्यान दें कि फ़ाइल के अंत (EOF) वर्ण का सामना होने पर इनपुट समाप्त हो जाता है। इस चरित्र को विंडोज पर रखने के लिए, CTRL + Z दबाएं।

सब कुछ लगभग शानदार है। आपने शायद देखा कि स्क्रीन पर कोई परिणाम प्रदर्शित नहीं होता है। विकार! कष्टप्रद अपूर्णता को ठीक करने के लिए, आपको व्याकरण के साथ फिर से जुड़ने की आवश्यकता है। अभी तक बंद ANTLRWorks नहीं?

4. व्याकरण में कैलकुलेटर की कार्यक्षमता जोड़ना

मज़ा भाग के लिए समय आ गया है। आरंभ करने के लिए, चलिए फ़ाइल के आरंभ में निम्नलिखित स्निपेट जोड़कर ANTLR को थोड़ा और कॉन्फ़िगर करें

व्याकरण:

 @ हेदर {
	 सिस्टम का उपयोग कर;
	 System.Collections का उपयोग कर;
 }

 @ मेमर्स {
	 हैशटेबल मेमोरी = नया हैशटेबल ();
 }

मैं समझा दूंगा। @ मेमर्स ANTLR से कहते हैं कि पार्सर क्लास (वैरिएबल वैल्यूज़ को स्टोर करने के लिए) में एक निजी मेमोरी मेंबर को जोड़ना आवश्यक है और, तदनुसार, हेडर कहता है कि हैशटेबल का उपयोग करने के लिए कौन से नेमस्पेस कनेक्ट होने चाहिए। अब आप हमारे व्याकरण में C # कोड जोड़ सकते हैं। आइए कथन नियम से शुरू करते हैं:

 कथन
	 : expr NEWLINE {Console.WriteLine ($ expr.value);  }
	 |  ID '=' expr NEWLINE {memory.Add ($ ID.text, $ expr.value);  }
	 |  NEWLINE
	 ;

कोड घुंघराले ब्रेसिज़ {} में लिखा है। यदि कथन पहला विकल्प है, तो हम स्क्रीन पर अंकगणितीय अभिव्यक्ति के मूल्य को प्रिंट करते हैं, यदि दूसरा - तो हम चर नाम और इसके मूल्य को स्मृति में संग्रहीत करते हैं ताकि हम इसे बाद में प्राप्त कर सकें। यहां सब कुछ बेहद सरल है, हालांकि, सवाल उठता है कि अभिव्यक्ति का मूल्य $ expr.value कहां से आता है? और इसे यहाँ से लिया गया है:

 expr रिटर्न [int value]	
	 : me1 = मल्टी एक्सप्रेशन {$ value = me1;}
	 ('+' me2 = मल्टी एक्सप्रेशन {$ value + = $ me2.value;};
	 | '-' me2 = मल्टी एक्सप्रेशन {$ value - = $ me2.value;}) *
	 ;

यहां कुछ भी जटिल नहीं है। हम एएनटीएलआर को बताते हैं कि एक्‍सआर नियम एक मान देता है जिसे प्रकार इंट का मान कहा जाता है। कृपया ध्यान दें कि दोनों प्रविष्टियों में "$ expr.value" और "रिटर्न [int value]" मूल्य संयोग से प्रकट नहीं होता है। यदि हम लिखते हैं:

 expr रिटर्न [int tratata]
 ...
	 ;

और फिर $ expr.value की ओर मुड़ें, फिर ANTLR एक त्रुटि फेंक देगा।

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

एक और सूक्ष्मता। उदाहरण के लिए, पहले कथन के नियम पर विचार करें। इस विकल्प के अनुरूप कोड में, हम सीधे expr नियम ($ expr.value) का उल्लेख करते हैं। लेकिन बयान नियम में यह काम नहीं करेगा, क्योंकि इसमें एक साथ दो बहुउद्देशीय नियम शामिल हैं, अर्थात्, उन्हें अलग करने के लिए, आपको उन्हें नाम देने की आवश्यकता है। इस मामले में, ये me1 और me2 हैं। यह सभी सूक्ष्मताएं प्रतीत होती हैं

चर्चा की, अब बिंदु के करीब।

एक्सप्र नियम में, दो विकल्प एक के माध्यम से लिखे गए हैं '|' | यह इस विषय के भाग 2 में स्पष्ट रूप से देखा जाता है। आपको याद दिला दूं कि expr फॉर्म के वाक्य हैं MultExpression-multExpression + multExpression-multExpression-multExpression + multExpression। अब कोड को घुंघराले कोष्ठक में देखते हैं और देखते हैं कि पहले पद का मान लौटाए गए मान को सौंपा गया है, और फिर, ऑपरेशन के आधार पर, बाद के शब्दों के मानों को जोड़ा या घटाया जाता है। नियम समान दिखता है

multExpression:

 मल्टी एक्सप्रेशन रिटर्न [इंट वैल्यू]
	 : a1 = परमाणु {$ value = $ a1.value ;;
	 ('*' a2 = atom {$ value * = $ a2.value;)
	 | '/' a2 = परमाणु {$ value / = $ a2.value;}) *
	 ;

परमाणु पार्सर का अंतिम नियम बना हुआ है। इसके साथ कोई समस्या नहीं होनी चाहिए:

 परमाणु प्रतिफल [int value]
	 : ID {$ value = (int) मेमोरी [$ ID.text] ;;
	 |  INT {$ मूल्य = int.Parse ($ INT.text) ;;
	 |  '(' expr ')' {$ value = $ expr.value ;;
	 ;

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

यह .bat फ़ाइल का उपयोग करके पार्सर और लेक्सर उत्पन्न करने के लिए रहता है। यहां तक ​​कि मुख्य () फ़ंक्शन के कोड को भी बदलना नहीं पड़ता है। हम अपना कैलकुलेटर लॉन्च करते हैं और खेलते हैं।





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





पार्सर ने त्रुटियों का पता लगाया, लेकिन फिर भी परिणाम की सही गणना की। आप "2 ++ 3" जैसे कुछ भी लिख सकते हैं और 5 प्राप्त कर सकते हैं।

5. निष्कर्ष

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

6. पढ़ने की सलाह दी

1. निश्चित ANTLR संदर्भ, टेरेंस Parr, 2007।
   
   आईएसबीएन -10: 0-9787392-5-6, आईएसबीएन -13: 978-09787392-4-9
2. लैंग्वेज इम्प्लीमेंटेशन पैटर्न, टेरेंस पार्र, 2010।
   
   आईएसबीएन -10: 1-934356-45-X, आईएसबीएन -13: 978-1-934356-45-6