मैं एएनटीएलआर में सी के एक छोटे से सबसेट के लिए एक लेक्सर/पार्सर लिख रहा हूं जो जावा पर्यावरण में चलाया जाएगा। मैं भाषा व्याकरण की दुनिया में हूं और कई एएनटीएलआर ट्यूटोरियल्स में, वे एक एएसटी - सार सिंटेक्स ट्री बनाते हैं, क्या मुझे एक बनाने के लिए मजबूर किया गया है और क्यों?एएनटीएलआर में एक पेड़ पार्सर क्या है और क्या मुझे एक लिखने के लिए मजबूर किया गया है?
मैं jGuru पर सवाल टेरेंस पार, से जो ANTLR बनाया द्वारा लिखित this answer पाया। मैंने here:
साइट से इस स्पष्टीकरण की प्रतिलिपि बनाई है केवल सरल, तथाकथित वाक्यविन्यास निर्देशित अनुवाद पार्सर के भीतर कार्यों के साथ किए जा सकते हैं। इस प्रकार के अनुवाद केवल उन संरचनाओं को थका सकते हैं जो पार्स में उस बिंदु पर पहले से देखी गई जानकारी के कार्य हैं। वृक्ष पार्सर आपको एक मध्यवर्ती रूप से चलने और उस पेड़ में हेरफेर करने की अनुमति देते हैं, धीरे-धीरे इसे कई अनुवाद चरणों में अंतिम रूप में बदल देते हैं जिसे आसानी से नए अनुवाद के रूप में वापस मुद्रित किया जा सकता है।
एक सरल अनुवाद समस्या की कल्पना कीजिए जहां एक html पृष्ठ जिसका शीर्षक है जहां n पहचानकर्ता आप इनपुट धारा में पाया की संख्या है "वहाँ आइटम n कर रहे हैं" बाहर प्रिंट करना चाहते हैं।
<html>
<head>
<title>There are 3 items</title>
</head>
<body>
<ol>
<li>Dog</li>
<li>Cat</li>
<li>Velociraptor</li>
</body>
</html>
Dog
Cat
Velociraptor
तो से
कैसे आप शीर्षक की गणना कर सकते हैं: आईडी इस शीर्षक के बाद मुद्रित किया जाना चाहिए? आप पूरे इनपुट को पढ़ने के बिना नहीं कर सकते हैं। ठीक है, तो अब हम जानते हैं कि हमें एक मध्यवर्ती रूप की आवश्यकता है। सबसे अच्छा आमतौर पर एक एएसटी है जिसे मैंने पाया है क्योंकि यह इनपुट संरचना रिकॉर्ड करता है। इस मामले में, यह सिर्फ एक सूची है लेकिन यह मेरे बिंदु को प्रदर्शित करता है।
ठीक है, अब आप जानते हैं कि एक पेड़ कुछ भी लेकिन सरल अनुवाद के लिए एक अच्छी बात है। एएसटी को देखते हुए, आप इससे आउटपुट कैसे प्राप्त करते हैं? सरल अभिव्यक्ति पेड़ की कल्पना करो। एक तरीका है पेड़ विशिष्ट वर्गों जैसे प्लस नोड, इंटेगर नोड और अन्य में नोड्स बनाना। फिर आप प्रत्येक नोड को खुद को मुद्रित करने के लिए कहते हैं।इनपुट के लिए, 3 + 4 आप पेड़ होगा:
+ | 3 - 4
और कक्षाओं
class PlusNode extends CommonAST {
public String toString() {
AST left = getFirstChild();
AST right = left.getNextSibling();
return left + " + " + right;
}
}
class IntNode extends CommonAST {
public String toString() {
return getText();
}
}
एक अभिव्यक्ति पेड़ को देखते हुए, आप इसे वापस t.toString से संदेश भेजने अनुवाद कर सकते हैं()। तो, इसमें क्या गलत है? महान काम करने लगता है, है ना? यह इस मामले में अच्छी तरह से काम करने के लिए है क्योंकि यह आसान है प्रकट होता है, लेकिन मैं तर्क है कि, यहां तक कि इस सरल उदाहरण के लिए, पेड़ व्याकरण अधिक पठनीय हैं और ठीक है उसका विवरण आप() PlusNode.toString में क्या कोडित औपचारिक रूप दिया जाता है।
expr returns [String r]
{
String left=null, right=null;
}
: #("+" left=expr right=expr) {r=left + " + " + right;}
| i:INT {r=i.getText();}
;
ध्यान दें कि विशिष्ट वर्ग ("विषम एएसटी") दृष्टिकोण वास्तव # के लिए एक पूर्ण रिकर्सिव-डिसेंट पार्सर encodes (+ INT INT) toString में अलग-अलग()। पार्सर जेनरेटर लोगों के रूप में, यह आपको क्रिंग करना चाहिए। ;)
विषम एएसटी दृष्टिकोण की मुख्य कमजोरी यह है कि यह आसानी से संदर्भ जानकारी का उपयोग नहीं कर सकता है। एक पुनरावर्ती-मूल पार्सर में, आपका संदर्भ आसानी से एक्सेस किया जाता है क्योंकि इसे पैरामीटर के रूप में पारित किया जा सकता है। आप यह भी जानते हैं कि व्याकरण को देखकर कौन सा नियम दूसरे नियम (उदाहरण के लिए, यह अभिव्यक्ति एक WHILE स्थिति या IF स्थिति है?) का आह्वान कर सकता है। उपरोक्त प्लस नोड क्लास एक पृथक, अलग दुनिया में मौजूद है जहां इसे पता नहीं है कि इसकी स्ट्रिंग() विधि का आह्वान कौन करेगा। इससे भी बदतर, प्रोग्रामर यह नहीं बता सकता कि किस संदर्भ में इसे पढ़कर इसे बुलाया जाएगा।
सारांश में, बहुत स्पष्ट अनुवाद जहां के लिए अपने इनपुट पार्सर कार्यों के लिए कार्यों को जोड़ने:
इसके अलावा, आपको एक मध्यवर्ती रूप की आवश्यकता होगी - एएसटी आमतौर पर सबसे अच्छा रूप है। एएसटी की संरचना का वर्णन करने के लिए व्याकरण का उपयोग करना आपके इनपुट टेक्स्ट को पार्स करने के लिए व्याकरण का उपयोग करने के समान है। एएनटीएलआर जैसी डोमेन-विशिष्ट उच्च-स्तरीय भाषा में औपचारिक विवरण हाथ कोडित पार्सर्स से बेहतर होते हैं। पेड़ व्याकरण के भीतर की कार्रवाइयां बहुत स्पष्ट संदर्भ हैं और इन्हें आसानी से आरएलयूएस से गुजरने वाली जानकारी तक पहुंच सकते हैं। मल्टीपास अनुवादों के लिए पेड़ में हेरफेर करने वाले अनुवाद पेड़ व्याकरण का उपयोग करके भी अधिक आसान होते हैं।
ANTLR के साथ एक एएसटी बनाना व्याकरण में शामिल किया गया है। आपको ऐसा करने की ज़रूरत नहीं है, लेकिन यह अधिक जटिल आवश्यकताओं के लिए वास्तव में एक अच्छा उपकरण है। पेड़ निर्माण पर यह tutorial है जिसका आप उपयोग कर सकते हैं।
असल में, ANTLR के साथ जब स्रोत पार्स हो रही है, तो आप कुछ ही विकल्प हैं। आप अपने व्याकरण में फिर से लिखने के नियमों का उपयोग कर कोड या एएसटी उत्पन्न कर सकते हैं। एक AST मूल रूप से आपके स्रोत की स्मृति प्रस्तुति में है। वहां से, आप बहुत कुछ कर सकते हैं।
एएनटीएलआर के लिए बहुत कुछ है। यदि आप पहले से नहीं हैं, तो मैं the book प्राप्त करने की अनुशंसा करता हूं।
मुझे लगता है कि एएसटी का निर्माण वैकल्पिक है। Abstract Syntax Tree पार्स किए गए कार्यक्रम के अर्थपूर्ण विश्लेषण जैसे बाद की प्रसंस्करण के लिए उपयोगी है।
केवल आप ही तय कर सकते हैं कि आपको एक बनाने की आवश्यकता है या नहीं। यदि आपका एकमात्र उद्देश्य वाक्य रचनात्मक सत्यापन है तो आपको एक उत्पन्न करने की आवश्यकता नहीं है। javacc (ANTLR के समान) में एक उपयोगिताJJTree कि एएसटी की पीढ़ी की अनुमति देता है कहा जाता है। तो मुझे लगता है कि यह एएनटीएलआर में भी वैकल्पिक है।