श्रृंखला का पिछला लेख ANTLR और रोजलिन का उपयोग करते हुए स्रोत पार्सिंग के सिद्धांत के लिए समर्पित था। इसमें यह नोट किया गया था कि हमारे पीटी एप्लीकेशन इंस्पेक्टर प्रोजेक्ट में कोड के हस्ताक्षर विश्लेषण की प्रक्रिया को निम्नलिखित चरणों में विभाजित किया गया है:
- एक भाषा पर निर्भर प्रतिनिधित्व (सार सिंटैक्स ट्री, एएसटी) में पार्सिंग;
- एएसटी को भाषा-स्वतंत्र, एकीकृत प्रारूप (यूनिफाइड एएसटी, यूएएसटी) में परिवर्तित करें;
- डीएसएल पर वर्णित टेम्प्लेट में प्रत्यक्ष मानचित्रण।
यह लेख दूसरे चरण के लिए समर्पित है, अर्थात्: विज़िटर और श्रोता रणनीतियों का उपयोग करके एएसटी को संसाधित करना, एएसटी को एक एकीकृत प्रारूप में परिवर्तित करना, एएसटी को सरल बनाना, साथ ही एक पेड़ संरचना मिलान एल्गोरिदम।
सामग्री
एएसटी बायपास
जैसा कि आप जानते हैं, पार्सर स्रोत कोड को पार्स ट्री (एक पेड़ जिसमें सभी तुच्छ टोकन हटा दिए जाते हैं) में बदल देता है, जिसे एएसटी कहा जाता है। ऐसे पेड़ को संसाधित करने के विभिन्न तरीके हैं। सबसे सरल है वंशजों के पुनरावर्ती ट्रावेल का उपयोग करके एक पेड़ को संसाधित करना। हालांकि, यह विधि केवल बहुत ही सरल मामलों के लिए लागू होती है जिसमें कुछ प्रकार के नोड होते हैं और प्रसंस्करण तर्क सरल होता है। अन्य मामलों में, प्रत्येक प्रकार के नोड के प्रसंस्करण तर्क को अलग-अलग तरीकों से स्थानांतरित करना आवश्यक है। यह दो विशिष्ट दृष्टिकोण (डिजाइन पैटर्न) का उपयोग करके पूरा किया जाता है: आगंतुक और श्रोता।
आगंतुक और श्रोता
आगंतुक में, एक नोड के वंशज को संसाधित करने के लिए, आपको उन्हें बायपास करने के लिए मैन्युअल रूप से कॉल करना होगा। इसके अलावा, यदि माता-पिता के तीन वंशज हैं, और केवल दो नोड्स कॉल विधि हैं, तो सबट्री का हिस्सा बिल्कुल भी संसाधित नहीं होगा। श्रोता (वॉकर) में, सभी वंशजों के आने के तरीकों को स्वचालित रूप से कहा जाता है। श्रोता के पास एक नोड विज़िट (एंटरनोड) की शुरुआत में एक विधि होती है और एक नोड यात्रा (एक्ज़ॉटनोड) के बाद बुलाया जाने वाला एक तरीका है। इन विधियों को इवेंट तंत्र का उपयोग करके भी लागू किया जा सकता है। श्रोता के विपरीत विज़िटर विधियाँ वस्तुओं को लौटा सकती हैं और टाइप भी की जा सकती हैं, अर्थात्। CSharpSyntaxVisitor की घोषणा करते समय, प्रत्येक विज़िट विधि एक AstNode ऑब्जेक्ट लौटाएगी, जो हमारे मामले में एकीकृत एएसटी के अन्य सभी नोड्स के लिए एक सामान्य पूर्वज है।
इस प्रकार, विज़िटर डिज़ाइन पैटर्न का उपयोग करते समय, ट्री रूपांतरण कोड अधिक कार्यात्मक और संक्षिप्त होता है, इस तथ्य के कारण कि उसे विज़िट किए गए नोड्स के बारे में जानकारी संग्रहीत करने की आवश्यकता नहीं है। नीचे दिए गए आंकड़े में आप देख सकते हैं कि, उदाहरण के लिए, PHP भाषा को परिवर्तित करते समय, अनावश्यक HTML और CSS नोड्स काट दिए जाते हैं। ट्रैवर्सल ऑर्डर संख्याओं द्वारा इंगित किया गया है। श्रोता आमतौर पर डेटा एकत्र करते समय (उदाहरण के लिए, CSV फ़ाइलों से), एक कोड को दूसरे (JSON -> XML) में परिवर्तित करते समय उपयोग किया जाता है। इसके बारे में और अधिक पढ़ें निश्चित परिभाषा ANTLR 4 संदर्भ में ।
ANTLR और रोजलिन में आगंतुक में अंतर।
विज़िटर और श्रोता का कार्यान्वयन पुस्तकालयों में भिन्न हो सकता है। उदाहरण के लिए, नीचे दी गई तालिका रोसलिन और एएनटीएलआर में आगंतुक और श्रोता वर्गों और विधियों का वर्णन करती है।
| ANTLR | रोसलिन |
|---|
| आगंतुक | AbstractParseTreeVisitor <परिणाम> | CSharpSyntaxVisitor <परिणाम> |
| श्रोता | IParseTreeListener | CSharpSyntaxWalker |
| चूक | DefaultResult | DefaultVisit (SyntaxNode नोड) |
| पर जाएँ | यात्रा (IParseTree पेड़) | यात्रा (सिंटैक्सोड नोड) |
ANTLR और रोज़लिन दोनों के पास डिफ़ॉल्ट रूप से परिणाम लौटाने के तरीके हैं (यदि किसी प्रकार के सिंटैक्स के लिए विज़िटर विधि को ओवरराइड नहीं किया गया है), साथ ही एक सामान्यीकृत यात्रा विधि, जो स्वयं निर्धारित करती है कि किस विशेष विज़िटर विधि को बुलाया जाना चाहिए।
एक ANTLR विज़िटर प्रत्येक सिंटैक्स व्याकरण नियम के लिए अपना विज़िटर बनाता है। विशेष प्रकार के तरीके भी हैं:
VisitChild(IRuleNode node) ; डिफ़ॉल्ट रूप से नोड के बायपास को लागू करने के लिए उपयोग किया जाता है।VisitTerminal(IRuleNode node) ; टर्मिनल नोड्स को बायपास करने के लिए उपयोग किया जाता है, अर्थात्। टोकन।VisitErrorNode(IErrorNode node) ; इसे लेक्सिकल या सिंटैक्टिक त्रुटियों के साथ पार्सिंग कोड के परिणामस्वरूप प्राप्त टोकन को बायपास करने के लिए उपयोग किया जाता है। उदाहरण के लिए, यदि वक्तव्य में अंत में अर्धविराम होता है, तो पार्सर इस तरह के टोकन को सम्मिलित करेगा और संकेत देगा कि यह गलत है। पिछले लेख में पार्सिंग त्रुटियों के बारे में और पढ़ें।AggregateResult(AstNode aggregate, AstNode nextResult) ; बाल ट्रैवर्सल के परिणामों को एकत्र करने के लिए शायद ही कभी इस्तेमाल की गई विधि।ShouldVisitNextChild(IRuleNode node, AstNode currentResult) ; यह निर्धारित करने के लिए शायद ही कभी इस्तेमाल किया गया तरीका है कि currentNode नोड नोड के ट्रैवर्सिंग के परिणाम के आधार पर node के अगले वंश को संसाधित करने के लिए।
रोसलिन विज़िटर के पास प्रत्येक सिंटैक्स के लिए विशेष विधियां हैं और सभी नोड्स के लिए एक सामान्य यात्रा विधि है। हालांकि, ANTLR के विपरीत, "मध्यवर्ती" निर्माणों को बायपास करने के लिए कोई विधियाँ नहीं हैं। उदाहरण के लिए, रोसलिन में VisitStatement लिए कोई तरीका नहीं है, लेकिन केवल विशेष VisitDoStatement , VisitExpressionStatement , VisitForStatement आदि। VisitStatement जेनेरिक Visit को एक VisitStatement रूप में उपयोग कर सकते हैं। एक और अंतर यह है कि तुच्छ (सिंटेक्स ट्रिविया) नोड्स के तरीकों को बायपास करते हैं, अर्थात। नोड्स जिन्हें कोड (रिक्त स्थान, टिप्पणियों) के बारे में जानकारी खोए बिना हटाया जा सकता है, मुख्य नोड्स और टोकन को बायपास करने के तरीकों के साथ कहा जाता है।
ANTLR आगंतुकों का दोष यह है कि उत्पन्न विज़िटर विधियों के नाम सीधे व्याकरण के नियमों को लिखने की शैली पर निर्भर करते हैं, इसलिए वे कोड की सामान्य शैली में फिट नहीं हो सकते हैं। उदाहरण के लिए, sql व्याकरण में यह तथाकथित स्नेक केस का उपयोग करने के लिए प्रथागत है, जिसमें शब्दों को अलग करने के लिए अंडरस्कोर का उपयोग किया जाता है। रोसलिन तरीके C # कोड की शैली में लिखे गए हैं। मतभेदों के बावजूद, रोसलिन और एएनटीएलआर में वृक्ष संरचनाओं के प्रसंस्करण के तरीके नए संस्करणों के साथ अधिक से अधिक एकीकृत हैं, जो अच्छी खबर है (एएनटीएलआर संस्करण 3 और नीचे में, कोई आगंतुक और श्रोता तंत्र नहीं था)।
ANTLR में व्याकरण और आगंतुक।
नियम के लिए ANTLR में
ifStatement : If parenthesis statement elseIfStatement* elseStatement? | If parenthesis ':' innerStatementList elseIfColonStatement* elseColonStatement? EndIf ';' ;
VisitIfStatement(PHPParser.IfStatementContext context) मेथड VisitIfStatement(PHPParser.IfStatementContext context) उत्पन्न होगा, जिसके संदर्भ में निम्नलिखित क्षेत्र होंगे:
parenthesis - एक एकल नोड;elseIfStatement* - नोड्स की एक सरणी। यदि कोई सिंटैक्स नहीं है, तो सरणी की लंबाई शून्य है;elseStatement? - वैकल्पिक नोड। यदि कोई सिंटैक्स नहीं है, तो शून्य;If , EndIf - टर्मिनल नोड्स, एक कैपिटल लेटर से शुरू होते हैं;':' , ';' - टर्मिनल नोड्स संदर्भ में शामिल नहीं हैं (केवल गेटचिल्ड () के माध्यम से सुलभ)।
यह ध्यान देने योग्य है कि व्याकरण में जितने कम नियम हैं, विज़िटर को लिखना उतना ही आसान और तेज़ है। हालाँकि, वाक्यविन्यास को दोहराने के लिए भी अलग नियम बनाने पड़ते हैं।
ANTLR में वैकल्पिक और तत्व लेबल
अक्सर ऐसी परिस्थितियाँ उत्पन्न होती हैं जिनमें एक नियम के कई विकल्प होते हैं और इन विकल्पों को अलग-अलग तरीकों से संसाधित करना अधिक तर्कसंगत होगा। सौभाग्य से, ANTLR 4 में इसके लिए विशेष वैकल्पिक लेबल हैं, जो # प्रतीक से शुरू होते हैं और प्रत्येक वैकल्पिक नियम के बाद जोड़े जाते हैं। पार्सर कोड बनाते समय, प्रत्येक लेबल के लिए एक अलग विज़िटर विधि उत्पन्न की जाती है, जो नियम के कई विकल्प होने की स्थिति में बड़ी मात्रा में कोड से बचता है। यह ध्यान देने योग्य है कि सभी विकल्पों को लेबल किया जाना चाहिए, या कोई भी नहीं। इसके अलावा, एक टर्मिनल को नामित करने के लिए जो कई मूल्यों को स्वीकार करता है, आप नियम तत्व लेबल का उपयोग कर सकते हैं:
expression : op=('+'|'-'|'++'|'--') expression #UnaryOperatorExpression | expression op=('*'|'/'|'%') expression #MultiplyExpression | expression op=('+'|'-') expression #AdditionExpression | expression op='&&' expression #LogicalAndExpression | expression op='?' expression op2=':' expression #TernaryOperatorExpression ;
इस नियम के लिए, ANTLR विज़िटर VisitExpression , VisitUnaryOperatorExpression , VisitMultiplyExpression , आदि उत्पन्न करेगा। प्रत्येक आगंतुक के पास एक अभिव्यक्ति सरणी होगी जिसमें 1 या 2 तत्व शामिल होंगे, साथ ही एक ओपल शाब्दिक होगा। टैग के लिए धन्यवाद, विज़िटर कोड क्लीनर और अधिक संक्षिप्त होंगे:
वैकल्पिक और तत्व लेबल का उपयोग करते समय कोड public override AstNode VisitUnaryOperatorExpression(TestParser.UnaryOperatorExpressionContext context) { var op = new MyUnaryOperator(context.op().GetText()); var expr = (Expression)VisitExpression(context.expression(0)); return new MyUnaryExpression(op, expr); } public override AstNode VisitMultiplyExpression(TestParser.MultiplyExpressionContext context) { var left = (Expression)VisitExpression(context.expression(0)); var op = new MyBinaryOpeartor(context.op().GetText()); var right = (Expression)VisitExpression(context.expression(1)); return new MyBinaryExpression(left, op, right); } public override AstNode VisitTernaryOperatorExpression(TestParser.TernaryOperatorExpressionContext context) { var first = (Expression)VisitExpression(context.expression(0)); var second = (Expression)VisitExpression(context.expression(1)); var third = (Expression)VisitExpression(context.expression(2)); return new MyTernaryExpression(first, second, third); } ...
वैकल्पिक लेबल के बिना, अभिव्यक्ति प्रसंस्करण एक विधि में होगा और कोड इस तरह दिखेगा:
वैकल्पिक और तत्व लेबल का उपयोग किए बिना कोड public override AstNode VisitExpression(TestParser.ExpressionContext context) { Expression expr, expr2, expr3; if (context.ChildCount == 2) // Unary { var op = new MyUnaryOperator(context.GetChild<ITerminalNode>(0).GetText()); expr = (Expression)VisitExpression(context.expression(0)); return new MyUnaryExpression(op, expr); } else if (context.ChildCount == 3) // Binary { expr = (Expression)VisitExpression(context.expression(0)); var binaryOp = new MyBinaryOpeartor(context.GetChild<ITerminalNode>(0).GetText()); expr2 = (Expression)VisitExpression(context.expression(1)); return new MyBinaryExpression(expr, binaryOp, expr2); ... } else // Ternary { var first = (Expression)VisitExpression(context.expression(0)); var second = (Expression)VisitExpression(context.expression(1)); var third = (Expression)VisitExpression(context.expression(2)); return new MyTernaryExpression(first, second, third); } }
यह ध्यान देने योग्य है कि वैकल्पिक लेबल न केवल ANTLR में, बल्कि व्याकरण के वर्णन के लिए अन्य साधनों में भी मौजूद हैं। उदाहरण के लिए, नाइट्रा में, असाइनमेंट साइन के साथ एक लेबल ANTLR के विपरीत, विकल्प के बाईं ओर रखा गया है:
syntax Expression { | IntegerLiteral | BooleanLiteral | NullLiteral = "null"; | Parenthesized = "(" Expression ")"; | Cast1 = "(" !Expression AnyType ")" Expression; | ThisAccess = "this"; | BaseAccessMember = "base" "." QualifiedName; | RegularStringLiteral;
एकीकृत एएसटी नोड प्रकार
एकीकृत एएसटी संरचना का विकास करते समय, हमें NRFactory परियोजना से एएसटी संरचना द्वारा इस तथ्य के मद्देनजर निर्देशित किया गया था कि यह हमारे लिए काफी सरल है, और एक विश्वसनीय पेड़ (निष्ठा, एक चरित्र के लिए स्रोत कोड के विपरीत ) की आवश्यकता नहीं है। कोई भी नोड AstNode का उत्तराधिकारी है और उसका अपना प्रकार NodeType है, जिसका उपयोग टेम्पलेट्स के साथ मिलान के चरण में और JSON से डिस्क्रिअलाइज़ करने पर भी किया जाता है। नोड्स की संरचना कुछ इस तरह दिखती थी:
प्रकार के अतिरिक्त, प्रत्येक नोड में एक संपत्ति होती है जो कोड (TextSpan) में स्थान संग्रहीत करती है, जिसका उपयोग टेम्पलेट के साथ मिलान करते समय इसे स्रोत कोड में प्रदर्शित करने के लिए किया जाता है। एक गैर-टर्मिनल नोड बाल नोड्स की एक सूची संग्रहीत करता है, और एक टर्मिनल नोड एक संख्यात्मक, स्ट्रिंग या अन्य आदिम मूल्य संग्रहीत करता है।
विभिन्न भाषाओं के एएसटी नोड्स की तुलना करने के लिए, एक तालिका संकलित की गई थी, जिसमें लाइनें कुछ नोड्स का सिंटैक्स थीं, और कॉलम उनके कार्यान्वयन में सी #, जावा, पीएचपी थे, जो इस तरह दिखता था:
| नोड | args | C # | जावा | पीएचपी | एमसीए | एमडीए |
|---|
| जब | cond: अभिव्यक्ति; stmt: कथन | जबकि (cond) stmt | जबकि (cond) stmt | जबकि (cond) stmt | जबकि (cond, stmt) | जबकि (cond, stmt) |
| BinaryOp | एल, आर: अभिव्यक्ति; op: शाब्दिक | l ऑप आर | l ऑप आर | l ऑप आर | बाइनरीऑप (l, op, r) | बाइनरीऑप (l, op, r) |
| ... | ... | ... | ... | ... | ... | ... |
| चेक किए गए | जाँच की गई: अभिव्यक्ति | जाँच की (जाँच) | - | - | जाँच | जाँच की गई (जाँच की गई) |
| NullConditional | a: अभिव्यक्ति, b: शाब्दिक | a .b | - | - | a! = अशक्त? ab: अशक्त | a .b |
इस तालिका में:
- अभिव्यक्ति; एक्सप्रेशन का रिटर्न वैल्यू है।
- कथन ; विवरण (निर्देश) का कोई वापसी मूल्य नहीं है।
- शाब्दिक; टर्मिनल नोड।
- अधिकांश कॉमन एस्ट (MCA) सबसे एकीकृत एएसटी है। यह नोड तब बनाया जाता है जब तीनों भाषाओं में यह या समान नोड का प्रकार होता है (उदाहरण के लिए, IfStatement, AssignmentExpression);
- सबसे विस्तार एस्ट (एमडीए) सबसे विस्तृत एएसटी। यह नोड तब बनाया जाता है जब कम से कम एक भाषा में इस प्रकार का नोड होता है (उदाहरण के लिए, फिक्स्डस्टेनेमट
fixed (a) { } सी # के लिए)। ये नोड्स एसक्यूएल जैसी भाषाओं के लिए अधिक प्रासंगिक हैं, इस तथ्य के कारण कि टी-एसक्यूएल और सी # के बीच की अंतिम घोषणात्मक भाषाएं उदाहरण के लिए, PHP और C # के बीच की तुलना में बहुत अधिक भिन्न हैं।
आकृति में दिखाए गए नोड्स (और अगले भाग में वर्णित "पैटर्न नोड्स) के अलावा, अधिकांश कॉमन एस्ट नोड बनाने के लिए अभी भी कृत्रिम नोड्स हैं, जबकि संभव के रूप में कम सिंटैक्स" खो "। ये नोड्स हैं:
- MultichildExpression; अभिव्यक्ति से विरासत में मिला है और अन्य अभिव्यक्ति का एक संग्रह है;
- WrapperExpression; अभिव्यक्ति से विरासत में मिला है और एक नोड के साथ एक मनमाना प्रकार AstNode है;
- WrapperStatement; कथन से विरासत में मिला है और एक नोड के साथ एक मनमाना प्रकार AstNode है।
अनिवार्य प्रोग्रामिंग भाषाओं में, मूल निर्माण अभिव्यक्ति अभिव्यक्ति और कथन कथन हैं। पूर्व में वापसी मूल्य होता है, बाद वाले का उपयोग किसी भी ऑपरेशन को करने के लिए किया जाता है। इसलिए, हमारे मॉड्यूल में, हमने मुख्य रूप से उन पर ध्यान केंद्रित किया। वे सीएफजी और भविष्य में दागी विश्लेषण को लागू करने के लिए आवश्यक स्रोत कोड के अन्य अभ्यावेदन को लागू करने के लिए बुनियादी भवन ब्लॉक हैं। यह जोड़ना योग्य है कि कोड में कमजोरियों के लिए खोज करने के लिए वाक्यविन्यास चीनी, जेनरिक और अन्य भाषा-विशिष्ट चीजों का ज्ञान आवश्यक नहीं है। इसलिए, सिंथैटिक शुगर का मानक निर्माणों में खुलासा किया जा सकता है, और विशिष्ट चीजों के बारे में जानकारी पूरी तरह से हटा दी जा सकती है।
पैटर्न नोड्स कस्टम पैटर्न का प्रतिनिधित्व करने वाले कृत्रिम नोड हैं। उदाहरण के लिए, संख्याओं की श्रेणी, नियमित अभिव्यक्तियों को शाब्दिक पैटर्न के रूप में उपयोग किया जाता है।
कनवर्टर परीक्षण
एक कोड विश्लेषक के लिए, प्राथमिकता पूरे कोड का परीक्षण करना है, न कि इसके व्यक्तिगत भागों की। इस समस्या को हल करने के लिए, सभी प्रकार के नोड्स के लिए आगंतुक विधियों को फिर से परिभाषित करने का निर्णय लिया गया। इस स्थिति में, यदि विज़िटर का उपयोग नहीं किया जाता है, तो यह एक new ShouldNotBeVisitedException(context) अपवाद फेंकता है। यह दृष्टिकोण विकास को सरल बनाता है क्योंकि इंटेलीजेंस खाते में यह ध्यान रखता है कि कौन से तरीके ओवरराइड हैं और कौन से नहीं हैं, इसलिए यह निर्धारित करना आसान है कि विज़िटर ने पहले से किन तरीकों को लागू किया है।
सभी कोड के कवरेज परीक्षण को बेहतर बनाने के बारे में भी हमारे कुछ विचार हैं। एकीकृत एएसटी का प्रत्येक नोड संबंधित स्रोत कोड के निर्देशांक को संग्रहीत करता है। इसके अलावा, सभी टर्मिनल टोकन के साथ जुड़े हुए हैं, अर्थात्। विशिष्ट चरित्र अनुक्रम। चूंकि सभी टोकन को संसाधित किया जाना चाहिए यदि संभव हो तो, कुल कवरेज गुणांक निम्न सूत्र द्वारा व्यक्त किया जा सकता है, जिसमें uterms एकीकृत एएसटी के टर्मिनल हैं, और terms सामान्य रोसलिन या uterms के टर्मिनल हैं:
यह मीट्रिक एकल गुणांक के साथ कोड कवरेज को व्यक्त करता है, जिसे किसी एक को करना चाहिए। बेशक, इस गुणांक के लिए एक अनुमान अनुमानित है, लेकिन इसका उपयोग आगंतुकों के कोड को फिर से भरने और सुधारने में किया जा सकता है। अधिक विश्वसनीय विश्लेषण के लिए, आप कवर किए गए टर्मिनलों के चित्रमय प्रतिनिधित्व का भी उपयोग कर सकते हैं।
सरलीकरण एएसटी
नियमित एएसटी को यूएएसटी में परिवर्तित करने के बाद, उत्तरार्द्ध को सरल बनाने की आवश्यकता है। सबसे सरल और सबसे उपयोगी अनुकूलन स्थिरांक (निरंतर तह) की तह है। उदाहरण के लिए, एक cookie.setMaxAge(2147483647); दोष है जो बहुत लंबे समय तक कुकी के जीवनकाल को स्थापित करने से जुड़ा है: cookie.setMaxAge(2147483647); ब्रैकेट में एक तर्क को एकल संख्या के रूप में लिखा जा सकता है, उदाहरण के लिए 86400 , या किसी प्रकार की अंकगणितीय अभिव्यक्ति, उदाहरण के लिए 60 * 60 * 24 । एसक्यूएल इंजेक्शन और अन्य कमजोरियों की तलाश में एक और उदाहरण स्ट्रिंग कॉन्फैनेटेशन है।
इस कार्य को लागू करने के लिए, एक कस्टम इंटरफ़ेस लागू किया गया था और आगंतुक केवल UAST के लिए है। चूंकि एएसटी के सरलीकरण से बस पेड़ के नोड्स की संख्या कम हो जाती है, आगंतुक टाइप किया गया था, उसी प्रकार को स्वीकार करना और वापस करना। .NET में प्रतिबिंब के लिए समर्थन के लिए धन्यवाद, इस तरह के आगंतुक को कोड की एक छोटी राशि के साथ लागू करने के लिए निकला। चूंकि प्रत्येक नोड में अन्य नोड्स या टर्मिनल आदिम मूल्य होते हैं, इसलिए प्रतिबिंब का उपयोग करके एक निश्चित नोड के सभी सदस्यों को निकालना और उन्हें संसाधित करना संभव है, अन्य आगंतुकों को पुनरावर्ती रूप से आमंत्रित करना।
एएसटी और पैटर्न मिलान एल्गोरिदम
टेम्प्लेट सर्च एल्गोरिथ्म में सभी एएसटी नोड्स की गणना करना और प्रत्येक नोड को एक पेड़ की संरचना के रूप में प्रस्तुत टेम्पलेट के साथ मिलान करना शामिल है। दो नोड्स तुलनीय हैं यदि उनके प्रकार समान हैं और, प्रकार के आधार पर, कुछ शर्तों को पूरा किया जाता है:
- वंशजों की पुनरावर्ती तुलना।
- सरल शाब्दिक प्रकार (पहचानकर्ता, तार, संख्या) की तुलना।
- विस्तारित शाब्दिक प्रकार (नियमित अभिव्यक्ति, पर्वतमाला) की तुलना। टिप्पणियाँ इस समूह में हैं।
- जटिल विस्तारित प्रकारों की तुलना (भाव, कथन क्रम)।
यह एल्गोरिथ्म सरल सिद्धांतों पर आधारित है जो कोड की अपेक्षाकृत कम मात्रा के साथ उच्च प्रदर्शन को प्राप्त करने की अनुमति देता है जो उन्हें लागू करता है। उत्तरार्द्ध को इस तथ्य के कारण प्राप्त किया जाता है कि नोड्स की तुलना करने के लिए ComparTo विधि आधार वर्ग, टर्मिनलों और अन्य नोड्स की एक छोटी संख्या के लिए लागू की जाती है। राज्य मशीनों पर आधारित प्रदर्शन में सुधार के लिए अधिक उन्नत मिलान वाले एल्गोरिदम अभी तक लागू नहीं किए गए हैं। हालांकि, यह एल्गोरिथ्म अधिक उन्नत विश्लेषण के लिए उपयोग करने के लिए समस्याग्रस्त (या असंभव भी है), उदाहरण के लिए, भाषा के शब्दार्थ को ध्यान में रखते हुए, अर्थात्। विभिन्न एएसटी नोड्स के बीच कनेक्शन।
निष्कर्ष
इस लेख में, हमने पेड़ों के प्रसंस्करण के लिए आगंतुक और श्रोता पैटर्न की जांच की, और एक एकीकृत एएसटी की संरचना के बारे में भी बात की। निम्नलिखित लेखों में हम बताएंगे:
- टेम्पलेट भंडारण दृष्टिकोण (हार्डकोड, जसन, डीएसएल) पर;
- पैटर्न का वर्णन करने के लिए DSL का विकास और उपयोग;
- वास्तविक स्रोत और खुले स्रोत परियोजनाओं में उनकी खोज के उदाहरण;
- सीएफजी, डीएफजी और दागी विश्लेषण।