ANTLR और रोसलिन का उपयोग करके स्रोत पार्सिंग का सिद्धांत और अभ्यास

हमारी परियोजना पीटी एप्लीकेशन इंस्पेक्टर विभिन्न प्रोग्रामिंग भाषाओं में स्रोत कोड के विश्लेषण के लिए कई दृष्टिकोण लागू करता है:

• हस्ताक्षर खोज
• कोड के एक स्थिर अमूर्त व्याख्या के परिणामस्वरूप प्राप्त गणितीय मॉडल के गुणों का अध्ययन;
• तैनात आवेदन का गतिशील विश्लेषण और उस पर स्थैतिक विश्लेषण के परिणामों का सत्यापन।

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

निम्नलिखित आवश्यकताओं को विकसित मॉड्यूल के लिए तैयार किया गया था, दूसरों के बीच में:

• कई प्रोग्रामिंग भाषाओं और नए लोगों के आसान जोड़ के लिए समर्थन;
• वाक्य रचना और अर्थ संबंधी त्रुटियों वाले पार्सिंग कोड के लिए समर्थन;
• एक सार्वभौमिक भाषा (डीएसएल, डोमेन विशिष्ट भाषा) में टेम्पलेट्स का वर्णन करने की क्षमता।

हमारे मामले में, सभी टेम्पलेट स्रोत कोड में किसी भी कमजोरियों या खामियों का वर्णन करते हैं।

कोड विश्लेषण की पूरी प्रक्रिया को निम्नलिखित चरणों में विभाजित किया जा सकता है:

1. एक भाषा पर निर्भर प्रतिनिधित्व (सार सिंटैक्स ट्री, एएसटी) में पार्सिंग;
2. एएसटी को भाषा-स्वतंत्र, एकीकृत प्रारूप में परिवर्तित करें
3. डीएसएल पर वर्णित टेम्प्लेट में प्रत्यक्ष मानचित्रण।

यह लेख पहले चरण के लिए समर्पित है, अर्थात्: पार्सिंग, विभिन्न पार्सर की कार्यक्षमता और सुविधाओं की तुलना करते हुए, जावा, पीएचपीएल, पीएसक्यूएल, टीएसक्यूएल, और यहां तक ​​कि सी # व्याकरण के उदाहरणों के रूप में व्यवहार में सिद्धांत लागू करते हैं। शेष चरणों की चर्चा बाद के प्रकाशनों में की जाएगी।

सामग्री

• पार्सिंग सिद्धांत
  
  • शब्दावली
  • औपचारिक भाषाओं के प्रकार
  • ANTLR
  • रोसलिन
• पार्सिंग मुद्दे
  
  • पहचानकर्ता के रूप में कीवर्ड
  • अस्पष्टता
  • रिक्त स्थान, टिप्पणियों को संभालना
  • पार्सिंग एरर हैंडलिंग
    
    • ANTLR में त्रुटियां
    • रोजलिन में त्रुटियां
• सिद्धांत से अभ्यास तक
  
  • जावा और जावा 8 व्याकरण
  • पीएचपी व्याकरण
    
    • केस-असंवेदनशील कीवर्ड
    • PHP, HTML, CSS, जावास्क्रिप्ट के लिए लेक्सिकल मोड
    • जटिल संदर्भ-संवेदनशील निर्माण
  • टी-एसक्यूएल व्याकरण
  • व्याकरण PL / SQL
  • C # व्याकरण
    
    • प्रीप्रोसेसर निर्देश
    • स्ट्रिंग इंटरपोलेशन
• परीक्षण
  
  • ANTLR पार्सर्स की शुद्धता
  • पार्सर स्पीड ANTLR और रोजलिन
  • ANTLR और रोसलिन में त्रुटि हैंडलिंग तंत्र
  • मेमोरी की खपत
• निष्कर्ष
• सूत्रों का कहना है

पार्सिंग सिद्धांत

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

शब्दावली

पार्सिंग सिद्धांत से परिचित लोग इस अनुभाग को छोड़ सकते हैं।

पार्सिंग स्रोत कोड को एक संरचित दृश्य में परिवर्तित करने की प्रक्रिया है। एक ठेठ पार्सर एक लेसर और एक पार्सर का एक संयोजन है। लेक्सर स्रोत कोड में वर्णों को सार्थक अनुक्रमों में समूहित करता है जिन्हें टोकन कहा जाता है। उसके बाद, टोकन का प्रकार निर्धारित किया जाता है (पहचानकर्ता, संख्या, स्ट्रिंग, आदि)। एक टोकन एक टोकन और उसके प्रकार के अर्थ का एक संयोजन है। नीचे दिए गए आंकड़े में उदाहरण में, टोकन सपा , = , 100 हैं । पार्सर टोकन स्ट्रीम से एक कनेक्टेड ट्री स्ट्रक्चर बनाता है, जिसे पार्स ट्री कहा जाता है। इस मामले में, असाइनमेंट पेड़ के नोड्स में से एक है। एब्सट्रैक्ट सिंटैक्स ट्री या एएसटी एक उच्च स्तर पर एक पार्सिंग ट्री है, जिसमें से कोष्ठक, अल्पविराम जैसे महत्वहीन टोकन हटा दिए जाते हैं। हालांकि, ऐसे पार्सर हैं जिनमें लेक्सिंग और पार्सिंग स्टेप्स संयुक्त हैं।

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

चूंकि यह शुरू में .NET प्रौद्योगिकियों पर परियोजना को विकसित करने का निर्णय लिया गया था, इसलिए रोज़न को सी # कोड का विश्लेषण करने के लिए, और अन्य भाषाओं के लिए ANTLR का उपयोग करने का निर्णय लिया गया था, क्योंकि बाद में .NET रनटाइम का समर्थन करता है, और अन्य विकल्पों में कम विशेषताएं हैं।

औपचारिक भाषाओं के प्रकार

चॉम्स्की पदानुक्रम के अनुसार, औपचारिक भाषाएं 4 प्रकार की होती हैं:

• नियमित उदाहरण: एक ^एन
• संदर्भ-मुक्त (CS, उदाहरण: a ⁿ b ⁿ )
• संदर्भ-संवेदनशील (शॉर्ट सर्किट, उदाहरण: एक ^एन बी ^एन सी ^एन )
• ट्यूरिंग-पूर्ण।

नियमित अभिव्यक्तियाँ आपको तुलना के लिए केवल सबसे सरल निर्माण का वर्णन करने की अनुमति देती हैं, जो, हालांकि, रोजमर्रा के अभ्यास में अधिकांश कार्यों को कवर करती हैं। नियमित अभिव्यक्तियों का एक और लाभ यह है कि उनका समर्थन अधिकांश आधुनिक प्रोग्रामिंग भाषाओं में शामिल है। ट्यूरिंग-पूर्ण भाषाओं का लिखित और पार्सिंग दोनों में अपनी जटिलता के कारण कोई व्यावहारिक उपयोग नहीं है (गूढ़ लोगों को आप थू याद कर सकते हैं)।

वर्तमान में, आधुनिक प्रोग्रामिंग भाषाओं के लगभग पूरे सिंटैक्स को सीएस ग्रामर का उपयोग करके वर्णित किया जा सकता है। यदि हम केएस-भाषाओं के पार्सरों और नियमित अभिव्यक्ति "उंगलियों पर" की तुलना करते हैं, तो उत्तरार्द्ध की कोई स्मृति नहीं है। और अगर हम KZ और CS भाषाओं के पार्सर्स की तुलना करते हैं, तो बाद वाले को पहले गए नियमों को याद नहीं रहता।

इसके अलावा, एक मामले में भाषा एक सीओपी हो सकती है, और दूसरे में - एक केजेड। यदि हम शब्दार्थ पर विचार करते हैं, अर्थात्। भाषा की परिभाषाओं के साथ संगति, विशेष रूप से, प्रकारों की संगति, फिर भाषा को KZ माना जा सकता है। उदाहरण के लिए, T a = new T ()। यहां दाईं ओर कंस्ट्रक्टर का प्रकार बाईं ओर इंगित किए गए अनुसार होना चाहिए। आमतौर पर पार्सिंग चरण के बाद शब्दार्थ की जांच करना उचित है। हालाँकि, ऐसे वाक्यात्मक निर्माण हैं जो CS व्याकरणों का उपयोग करके पार्स नहीं किए जा सकते हैं, उदाहरण के लिए PHP में Heredoc : $ x = <<< EOL नमस्ते दुनिया ईओएल ; इसमें, ईओएल टोकन ब्रेकिंग लाइन की शुरुआत और अंत का एक मार्कर है, इसलिए, विज़िट किए गए टोकन के मूल्य को याद रखना आवश्यक है। यह लेख ऐसी KS और KZ भाषाओं के विश्लेषण पर केंद्रित है।

ANTLR

यह पार्सर जनरेटर एलएल (*) है , यह 20 से अधिक वर्षों से अस्तित्व में है, और 2013 में इसका 4 वां संस्करण जारी किया गया था। अब इसे GitHub पर विकसित किया जा रहा है। फिलहाल, यह आपको जावा, C #, पायथन 2, पायथन 3, जावास्क्रिप्ट भाषाओं में पार्सर्स जेनरेट करने की अनुमति देता है। C ++ के दृष्टिकोण पर, स्विफ्ट। मुझे कहना होगा, अब इस टूल में व्याकरण को विकसित करना और डीबग करना काफी सरल है। इस तथ्य के बावजूद कि LL व्याकरण बाएं पुनरावर्ती नियमों की अनुमति नहीं देता है, ANTLR में, संस्करण 4 से शुरू, इस तरह के नियमों को लिखना संभव है (छिपे या अप्रत्यक्ष बाईं पुनरावृत्ति के साथ नियमों को छोड़कर)। जब पार्सर उत्पन्न होता है, तो ऐसे नियम नियमित गैर-वाम-पुनरावर्ती वाले में परिवर्तित हो जाते हैं। यह उदाहरण के लिए, अंकगणितीय अभिव्यक्तियों की रिकॉर्डिंग को छोटा करता है:

expr : expr '*' expr | expr '+' expr | <assoc=right> expr '^' expr | id ; 

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

रोसलिन

रोजलिन सिर्फ एक पार्सर नहीं है, बल्कि सी # कोड को पार्स करने, विश्लेषण करने और संकलन करने का एक पूरा उपकरण है। इसका विकास GitHub पर भी चल रहा है, हालांकि यह ANTLR से काफी छोटा है। यह लेख केवल शब्दार्थ की परवाह किए बिना इसकी पार्सिंग क्षमताओं पर चर्चा करता है। Roslyn एक निष्ठा, अपरिवर्तनीय और थ्रेड सेफ ट्री में कोड को पार्स करता है। विश्वसनीयता इस तथ्य में निहित है कि इस तरह के पेड़ को वर्ण-से-वर्ण कोड में बदला जा सकता है, जिसमें रिक्त स्थान, टिप्पणियां और प्रीप्रोसेसर निर्देश शामिल हैं, भले ही इसमें सिंटैक्स त्रुटियां हों। अपरिवर्तनशीलता से कई धागों के साथ एक पेड़ को संसाधित करना आसान हो जाता है, क्योंकि प्रत्येक धागा उस पेड़ की "स्मार्ट" प्रतिलिपि बनाता है जिसमें केवल परिवर्तन संग्रहीत होते हैं। इस पेड़ में निम्नलिखित वस्तुएँ हो सकती हैं:

• सिंटेक्स नोड एक गैर-टर्मिनल ट्री नोड है जिसमें कई अन्य नोड्स होते हैं और एक विशिष्ट डिज़ाइन प्रदर्शित करते हैं। इसमें एक वैकल्पिक नोड भी हो सकता है (उदाहरण के लिए, अगर के लिए ElseClauseSyntax);
• सिंटैक्स टोकन - एक टर्मिनल नोड जो एक कीवर्ड, पहचानकर्ता, शाब्दिक या विराम चिह्न प्रदर्शित करता है;
• सिंटेक्स ट्रिविया एक टर्मिनल नोड है जो एक स्थान, टिप्पणी या प्रीप्रोसेसर निर्देश प्रदर्शित करता है (यह कोड के बारे में जानकारी खोए बिना दर्द रहित रूप से हटाया जा सकता है)। सामान्य ज्ञान का कोई जनक नहीं हो सकता। कोड में एक पेड़ को वापस बदलने पर ये नोड्स अपरिहार्य हैं (उदाहरण के लिए, रिफैक्टरिंग के लिए)।

पार्सिंग मुद्दे

व्याकरण और पार्सर विकसित करते समय, कुछ समस्याएं होती हैं जिन पर विचार करने की आवश्यकता होती है।

पहचानकर्ता के रूप में कीवर्ड

अक्सर ऐसा होता है कि जब पार्सिंग कीवर्ड पहचानकर्ता भी हो सकते हैं। उदाहरण के लिए, C # में, async Method() विधि के हस्ताक्षर से पहले रखा गया async कीवर्ड का अर्थ है कि विधि अतुल्यकालिक है। लेकिन यदि दिए गए शब्द का उपयोग चर var async = 42; के पहचानकर्ता के रूप में किया जाएगा var async = 42; , तो कोड भी मान्य होगा। ANTLR इस समस्या को दो तरह से हल करता है:

1. वाक्यविन्यास नियम के लिए शब्दार्थ का उपयोग करते हुए: async: {_input.LT(1).GetText() == "async"}? ID ; async: {_input.LT(1).GetText() == "async"}? ID ; ; हालाँकि, एसिंक्स टोकन स्वयं मौजूद नहीं होगा। यह दृष्टिकोण बुरा है क्योंकि व्याकरण रनटाइम पर निर्भर हो जाता है और बदसूरत दिखता है;
2. आईडी नियम में टोकन को शामिल करके:
   

    ASYNC: 'async'; ... id : ID ... | ASYNC; 

अस्पष्टता

एक प्राकृतिक भाषा में अस्पष्ट रूप से व्याख्या किए गए वाक्यांश हैं (जैसे कि "इन प्रकार के स्टील हमारी कार्यशाला में हैं")। औपचारिक भाषाओं में, ऐसे निर्माण भी हो सकते हैं। उदाहरण के लिए, निम्नलिखित स्निपेट:

 stat: expr ';' // expression statement | ID '(' ')' ';' // function call statement; ; expr: ID '(' ')' | INT ; 

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

 expr: { isfunc(ID) }? ID '(' expr ')' // func call with 1 arg | { istype(ID) }? ID '(' expr ')' // ctor-style type cast of expr | INT | void ; 

इसके अलावा, कभी-कभी अस्पष्टता को व्याकरण को थोड़ा नया करने के साथ ठीक किया जा सकता है। उदाहरण के लिए, C # में एक बिटवाइज़ राइट शिफ्ट ऑपरेटर RIGHT_SHIFT: '>>' ; दो कोण कोष्ठक का उपयोग जेनेरिक कक्षाओं का वर्णन करने के लिए भी किया जा सकता है: List<List<int>> । यदि आप टोकन >> को परिभाषित करते हैं, तो दो सूचियों के निर्माण को कभी भी पार्स नहीं किया जा सकता है, क्योंकि पार्सर यह मान लेगा कि ऑपरेटर >> दो समापन कोष्ठक के बजाय लिखा गया है। इस समस्या को हल करने के लिए, यह केवल RIGHT_SHIFT टोकन को अस्वीकार करने के लिए पर्याप्त है। उसी समय, LEFT_SHIFT: '<<' टोकन LEFT_SHIFT: '<<' छोड़ा जा सकता है, क्योंकि वर्णों के इस तरह के अनुक्रम जब पार्सिंग कोण कोष्ठक को एक वैध कोड में नहीं पाया जा सकता है।

हमारे मॉड्यूल में, हमने अभी तक विस्तार से परीक्षण नहीं किया है कि क्या विकसित व्याकरण में अस्पष्टता है।

रिक्त स्थान, टिप्पणियों को संभालना।

पार्सिंग के साथ एक और समस्या टिप्पणी प्रसंस्करण है। यहां असुविधा यह है कि यदि आप व्याकरण में टिप्पणियों को शामिल करते हैं, तो यह अतिव्यापी हो जाएगा, क्योंकि वास्तव में प्रत्येक नोड में टिप्पणियां होंगी। हालाँकि, टिप्पणियों को फेंका नहीं जा सकता, क्योंकि उनमें महत्वपूर्ण जानकारी हो सकती है। ANTLR टिप्पणियों को संसाधित करने के लिए तथाकथित चैनलों का उपयोग करता है, जो अन्य टोकन से कई टिप्पणियों को अलग करता है: Comment: ~[\r\n?]+ -> channel(PhpComments);

रोजलिन में, टिप्पणियों को पेड़ के नोड्स में शामिल किया गया है, लेकिन एक विशेष प्रकार का सिंटैक्स ट्रिविया है। ANTLR और रोजलिन दोनों एक विशेष नियमित टोकन के साथ जुड़े तुच्छ टोकन की एक सूची प्रदान करते हैं। ANTLR में, स्ट्रीम में इंडेक्स i के साथ टोकन के लिए, एक विधि है जो बाएं या दाएं से एक विशिष्ट चैनल से सभी टोकन लौटाती है: getHiddenTokensToLeft(int tokenIndex, int channel) , getHiddenTokensToRight(int tokenIndex, int channel) । रोजलिन में, टर्मिनल सिंटेक्स टोकन में ऐसे टोकन तुरंत शामिल किए जाते हैं।

सभी टिप्पणियां प्राप्त करने के लिए, ANTLR में आप एक निश्चित चैनल के सभी टोकन ले सकते हैं: lexer.GetAllTokens().Where(t => t.Channel == PhpComments) , और Roslyn में आप निम्नलिखित SyntaxKind के साथ रूट नोड के लिए सभी DescendantTrivia ले सकते हैं: SingleLineCommentTrivia , MultiLineCommentTrivia , SingleLineDocumentationCommentTrivia , MultiLineDocumentationCommentTrivia , DocumentationCommentExteriorTrivia , XmlComment ।

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

 case MOD_UNLOAD: if (via_feature_rng & VIA_HAS_RNG) random_nehemiah_deinit(); random_source_deregister(&random_nehemiah); 

पार्सिंग एरर हैंडलिंग।

प्रत्येक पार्सर की एक महत्वपूर्ण क्षमता त्रुटि से निपटने के लिए है - निम्नलिखित कारणों से:

• पार्सिंग प्रक्रिया को केवल एक त्रुटि के कारण बाधित नहीं किया जाना चाहिए, लेकिन सही ढंग से बहाल किया जाना चाहिए और कोड को आगे पार्स करना चाहिए (उदाहरण के लिए, एक चूक अर्धविराम के बाद);
• कई अप्रासंगिक लोगों के बजाय एक प्रासंगिक त्रुटि और उसके स्थान की खोज करें।

ANTLR में त्रुटियां

ANTLR में निम्नलिखित प्रकार की पार्सिंग त्रुटियाँ मौजूद हैं:

• टोकन मान्यता त्रुटि (Lexer no viable alt); एकमात्र मौजूदा शाब्दिक त्रुटि, एक मौजूदा टोकन से टोकन बनाने के लिए एक नियम की अनुपस्थिति का संकेत देती है:
  
  कक्षा # {int i; } - यहाँ ऐसा टोकन # है ।

  
  

• लापता टोकन (गुम टोकन); इस मामले में, ANTLR टोकन स्ट्रीम में लापता टोकन सम्मिलित करता है, यह दर्शाता है कि यह गायब है, और मौजूद होने पर पार्स करना जारी रखता है।
  
  वर्ग T {int f (x) {a = 3 4 5; } } - यहाँ इस तरह के एक टोकन है } अंत में;

  
  

• अतिरिक्त टोकन (एक्सट्रोनस टोकन); ANTLR का संकेत है कि टोकन गलत है और आगे जारी रहता है, जैसे कि यह अनुपस्थित था: उदाहरण में, ऐसा टोकन पहले है ;
  
  क्लास टी ; {इंट आई; }

  
  

• असंगत इनपुट श्रृंखला (बेमेल इनपुट); इस स्थिति में, "पैनिक मोड" चालू होता है, इनपुट टोकन श्रृंखला को अनदेखा किया जाता है, और पार्सर सिंक्रनाइज़ेशन सेट से टोकन की अपेक्षा करता है। निम्नलिखित उदाहरण में, टोकन 4 और 5 को अनदेखा किया गया है, और सिंक्रनाइज़ेशन टोकन है ;
  
  वर्ग T {int f (x) {a = 3 4 5 ; }}

  
  
• लापता विकल्प (कोई व्यवहार्य वैकल्पिक इनपुट नहीं); यह त्रुटि अन्य सभी संभावित पार्सिंग त्रुटियों का वर्णन करती है।
  
  कक्षा टी { इंट; }

इसके अलावा, त्रुटियों को नियम के विकल्पों को जोड़कर मैन्युअल रूप से नियंत्रित किया जा सकता है, उदाहरण के लिए इस तरह:

 function_call : ID '(' expr ')' | ID '(' expr ')' ')' {notifyErrorListeners("Too many parentheses");} | ID '(' expr {notifyErrorListeners("Missing closing ')'");} ; 

इसके अलावा, ANTLR 4 अपनी त्रुटि हैंडलिंग तंत्र का उपयोग कर सकता है। यह आवश्यक है, उदाहरण के लिए, पार्सर के प्रदर्शन को बढ़ाने के लिए: पहले, तेज एसएलएल एल्गोरिथ्म का उपयोग करके कोड को पार्स किया जाता है, जो, हालांकि, अस्पष्टता के साथ कोड को गलत तरीके से पार्स कर सकता है। यदि, इस एल्गोरिथ्म का उपयोग करते हुए, यह पता चलता है कि कम से कम एक त्रुटि है (यह कोड या अस्पष्टता में एक त्रुटि हो सकती है), पूर्ण, लेकिन कम तेज ऑल-एल्गोरिदम का उपयोग करके कोड को पार्स किया जाता है। बेशक, वास्तविक त्रुटियों के साथ कोड (उदाहरण के लिए, छोड़ दिया गया) हमेशा एलएल का उपयोग करके पार्स किया जाएगा, लेकिन आमतौर पर त्रुटियों के बिना फ़ाइलों की तुलना में ऐसी फाइलें कम होती हैं।

 // try with simpler/faster SLL(*) parser.getInterpreter().setPredictionMode(PredictionMode.SLL); // we don't want error messages or recovery during first try parser.removeErrorListeners(); parser.setErrorHandler(new BailErrorStrategy()); try { parser.startRule(); // if we get here, there was no syntax error and SLL(*) was enough; // there is no need to try full LL(*) } catch (ParseCancellationException ex) { // thrown by BailErrorStrategy tokens.reset(); // rewind input stream parser.reset(); // back to standard listeners/handlers parser.addErrorListener(ConsoleErrorListener.INSTANCE); parser.setErrorHandler(new DefaultErrorStrategy()); // full now with full LL(*) parser.getInterpreter().setPredictionMode(PredictionMode.LL); parser.startRule(); } 

रोजलिन में त्रुटियां

रोजलिन में निम्नलिखित पार्सिंग त्रुटियां हैं:

• छूटी हुई वाक्य रचना रोजलिन संपत्ति के मूल्य के साथ संबंधित नोड को पूरा करता है IsMissing = true (एक विशिष्ट उदाहरण अर्धविराम के बिना स्टेटमेंट है);
• अधूरा सदस्य ; एक अलग IncompleteMember नोड बनाया गया है।
• एक संख्यात्मक, स्ट्रिंग, या वर्ण शाब्दिक का गलत मान (उदाहरण के लिए, एक मान बहुत बड़ा, एक खाली चार): NumericLiteralToken , StringLiteralToken या CharacterLiteralToken बराबर एक अलग नोड के साथ;
• सुपरफ़्लुअस सिंटैक्स (उदाहरण के लिए, एक बेतरतीब ढंग से टाइप किया गया पात्र): Kind = SkippedTokensTrivia के साथ एक अलग नोड बनाया जाता है।

निम्न कोड स्निपेट इन सभी त्रुटियों को प्रदर्शित करता है।
(रोसलिन विजुअल स्टूडियो सिंटेक्स विज़ुअलाइज़र के प्लगइन के साथ जांच करने के लिए भी सुविधाजनक है):

 namespace App { class Program { ; // Skipped Trivia static void Main(string[] args) { a // Missing ';' ulong ul = 1lu; // Incorrect Numeric string s = """; // Incorrect String char c = ''; // Incorrect Char } } class bControl flow { c // Incomplete Member } } 

सिंटैक्स त्रुटियों के इन सुविचारित प्रकारों के लिए धन्यवाद, रोजलिन चरित्र द्वारा कोड में किसी भी संख्या में त्रुटियों के साथ एक पेड़ को परिवर्तित कर सकता है।

सिद्धांत से अभ्यास तक

PHP के लिए, टी-एसक्यूएल पार्सर, php , tsql , plsql व्याकरण , जो उपरोक्त सिद्धांत के दृश्य अनुप्रयोग हैं, को खुले स्रोत में विकसित और निर्धारित किया गया था। जावा पार्सिंग के लिए, रेडी-मेड जावा और जावा 8 व्याकरण का उपयोग किया गया और तुलना की गई। इसके अलावा, रोजलिन और एएनटीएलआर पर आधारित पार्सर की तुलना करने के लिए, हमने भाषा के संस्करण 5 और 6 का समर्थन करने के लिए सी # व्याकरण को संशोधित किया। इन व्याकरणों के विकास और उपयोग में दिलचस्प बिंदु नीचे वर्णित हैं। हालाँकि एसक्यूएल-आधारित भाषाएं आवधिक की तुलना में अधिक घोषणात्मक हैं, लेकिन टी-एसक्यूएल, पीएल / एसक्यूएल की उनकी बोलियों में अनिवार्य निर्माण ( नियंत्रण प्रवाह ) के लिए समर्थन है, जिसके लिए हमारे अधिकांश भाग के लिए विश्लेषक का विकास किया जाता है।

जावा और जावा 8 व्याकरण

ज्यादातर मामलों में, गहरी पुनरावृत्ति वाले मामलों को छोड़कर, जावा 7 की तुलना में जावा 7 व्याकरण पार्स कोड पर आधारित एक पार्सर, उदाहरण के लिए, ManyStringConcatenation.java फ़ाइल में, जब पार्सिंग अधिक समय और स्मृति का क्रम लेता है। मैं यह नोट करना चाहता हूं कि यह सिर्फ एक सिंथेटिक उदाहरण नहीं है - हम वास्तव में एक समान "स्पेगेटी कोड" के साथ फाइलों में आए थे। जैसा कि यह निकला, पूरी समस्या अभिव्यक्ति में बाएं पुनरावर्ती नियमों के कारण ठीक है। जावा 8 व्याकरण में केवल आदिम पुनरावृत्ति के साथ नियम हैं। आदिम पुनरावृत्ति के साथ नियम सामान्य से भिन्न होते हैं जिसमें वे किसी भी विकल्प के बाएं या दाएं हिस्से में खुद को संदर्भित करते हैं, लेकिन दोनों में एक साथ नहीं। एक नियमित पुनरावर्ती अभिव्यक्ति का एक उदाहरण:

 expression : expression ('*'|'/') expression | expression ('+'|'-') expression | ID ; 

और उपरोक्त नियमों को आदिम बाएँ-पुनरावर्ती में परिवर्तित करने के बाद प्राप्त किया जाता है:

 expression : multExpression | expression ('+'|'-') multExpression ; multExpression : ID | multExpression ('*'|'/') ID ; 

या यहां तक ​​कि गैर-पुनरावर्ती (हालांकि, इस मामले में, पार्सिंग के बाद के भाव प्रक्रिया के लिए बहुत सुविधाजनक नहीं होंगे, क्योंकि वे द्विआधारी होना बंद हो जाएंगे):

 expression : multExpression (('+'|'-') multExpression)* ; 

यदि ऑपरेशन में सही समरूपता है (उदाहरण के लिए, घातांक), तो आदिम सही-पुनरावर्ती नियम का उपयोग किया जाता है:

 expression : <assoc=right> expression '^' expression | ID ; 

 powExpression : ID '^' powExpression | ID ; 

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

पीएचपी व्याकरण

.NET प्लेटफॉर्म पर PHP को पार्स करने के लिए एक फालैंगर प्रोजेक्ट है। हालांकि, हम इस तथ्य से सहज नहीं थे कि यह परियोजना व्यावहारिक रूप से विकसित नहीं हो रही है, और एएसटी नोड्स (केवल वॉकर) को पार करने के लिए एक विज़िटर इंटरफ़ेस प्रदान नहीं करता है। इस प्रकार, हमारे द्वारा ANTLR के तहत PHP व्याकरण विकसित करने का निर्णय लिया गया।

केस-असंवेदनशील कीवर्ड।

जैसा कि आप जानते हैं, PHP में सभी टोकन, चर नामों के अपवाद के साथ (जो '$' से शुरू होते हैं), केस असंवेदनशील होते हैं। ANTLR के मामले में, केस असंवेदनशीलता को दो तरीकों से लागू किया जा सकता है:

1. सभी लैटिन अक्षरों के लिए खंडित शाब्दिक नियमों की घोषणा और निम्नलिखित तरीके से उनका उपयोग करना:

   
   

    Abstract: ABSTRACT; Array: ARRAY; As: AS; BinaryCast: BINARY; BoolType: BOOLEAN | BOOL; BooleanConstant: TRUE | FALSE; ... fragment A: [aA]; fragment B: [bB]; ... fragment Z: [zZ]; 

   
   

   ANTLR में एक स्निपेट टोकन का हिस्सा है जिसे अन्य टोकन में इस्तेमाल किया जा सकता है।
   हालाँकि, यह अपने आप में एक टोकन नहीं है। यह अनिवार्य रूप से टोकन का वर्णन करने के लिए सिंथेटिक चीनी है। अंशों का उपयोग किए बिना, उदाहरण के लिए, पहला टोकन निम्नानुसार लिखा जा सकता है: Abstract: [Aa] [Bb] [Ss] [Tt] [Rr] [Aa] [Cc] [Tt] । इस दृष्टिकोण का लाभ यह है कि उत्पन्न लेसर रनटाइम से स्वतंत्र है, क्योंकि ऊपरी और निचले मामले के चरित्र व्याकरण में तुरंत घोषित किए जाते हैं। Minuses में से, यह ध्यान दिया जा सकता है कि इस दृष्टिकोण के साथ लेक्सर का प्रदर्शन दूसरी विधि की तुलना में कम है।

   
   
2. वर्णों की संपूर्ण इनपुट स्ट्रीम को निम्न (या ऊपरी) रजिस्टर में लाना और लेक्सर शुरू करना, जिसमें इस रजिस्टर में सभी टोकन वर्णित हैं। हालांकि, इस तरह के रूपांतरण को प्रत्येक रनटाइम (जावा, सी #, जावास्क्रिप्ट, पायथन) के लिए अलग से करना होगा, जैसा कि एक कस्टम फ़ाइल या स्ट्रिंग स्ट्रीम और ओवरराइड एलए को लागू करने में वर्णित है। इसके अलावा, इस दृष्टिकोण के साथ, यह सुनिश्चित करना मुश्किल है कि कुछ टोकन मामले संवेदनशील हैं और अन्य नहीं हैं।

विकसित PHP व्याकरण में, पहले दृष्टिकोण का उपयोग किया गया था, क्योंकि शाब्दिक विश्लेषण आमतौर पर सिंटैक्टिक की तुलना में कम समय में किया जाता है। और इस तथ्य के बावजूद कि व्याकरण वैसे भी रनटाइम पर निर्भर होता है, यह दृष्टिकोण संभावित रूप से व्याकरण को अन्य रनटाइम में पोर्ट करने के कार्य को सरल करता है। इसके अलावा, हमने केस-असंवेदनशील टोकनों के विवरण को सुविधाजनक बनाने के लिए, पल्स रिक्वेस्ट RFC केस इन्सेन्सिटी प्रूफ ऑफ़ कॉन्सेप्ट बनाया। लेकिन, दुर्भाग्य से, उन्हें ANTLR समुदाय से ज्यादा मंजूरी नहीं मिली।

PHP, HTML, CSS, जावास्क्रिप्ट के लिए लेक्सिकल मोड।

जैसा कि आप जानते हैं, PHP कोड के आवेषण HTML कोड के अंदर लगभग कहीं भी स्थित हो सकते हैं। सीएसएस और जावास्क्रिप्ट कोड आवेषण भी इस HTML में स्थित हो सकते हैं (इन आवेषणों को "द्वीप" भी कहा जाता है)। उदाहरण के लिए, निम्न कोड ( वैकल्पिक सिंटैक्स का उपयोग करना) मान्य है:

 <?php switch($a): case 1: // without semicolon?> <br> <?php break ?> <?php case 2: ?> <br> <?php break;?> <?php case 3: ?> <br> <?php break;?> <?php endswitch; ?> 

या

 <script type="text/javascript"> document.addEvent('domready', function() { var timers = { timer: <?=$timer?> }; var timer = TimeTic.periodical(1000, timers); functionOne(<?php echo implode(', ', $arrayWithVars); ?>); }); </script> 

सौभाग्य से, ANTLR में तथाकथित मोड का एक तंत्र है, जो आपको एक निश्चित स्थिति के तहत टोकन के विभिन्न सेटों के बीच स्विच करने की अनुमति देता है। उदाहरण के लिए, क्रमशः SCRIPT और स्टाइल मोड जावास्क्रिप्ट और सीएसएस के लिए टोकन की एक धारा उत्पन्न करने के लिए डिज़ाइन किए गए हैं (हालांकि, इस व्याकरण में, उन्हें वास्तव में अनदेखा किया जाता है)। डिफ़ॉल्ट मोड में, DEFAULT_MODE HTML टोकन उत्पन्न होते हैं। यह ध्यान देने योग्य है कि आप ANTLR में वैकल्पिक सिंटैक्स समर्थन को लागू कर सकते हैं, जो कि लेस्टर में लक्ष्य कोड की एक भी प्रविष्टि के बिना नहीं है। अर्थात्, nonEmptyStatement में इनलाइनहेटलएम नियम शामिल है, जो बदले में DEFAULT_MODE मोड में प्राप्त टोकन को शामिल करता है:

 nonEmptyStatement : identifier ':' | blockStatement | ifStatement | ... | inlineHtml ; ... inlineHtml : HtmlComment* ((HtmlDtd | htmlElement) HtmlComment*)+ ; 

जटिल संदर्भ-संवेदनशील निर्माण।

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

 <?php foo(<<< HEREDOC Heredoc line 1. Heredoc line 2. HEREDOC ) ; ?> 

टी-एसक्यूएल व्याकरण

"SQL" की सामान्य जड़ के बावजूद, T-SQL व्याकरण (MSSQL) और PL / SQL एक दूसरे से काफी अलग हैं।

हमें खुशी होगी कि हम इस कठिन भाषा के लिए अपने स्वयं के पार्सर का विकास नहीं करेंगे। हालांकि, मौजूदा पार्सर पूर्णता, प्रासंगिकता (एक परित्यक्त गोल्ड-पार्सर के लिए व्याकरण ), और C # ( सामान्य SQL पार्सर ) में खुला स्रोत के मानदंडों को पूरा नहीं करते हैं। TSQL MSDN. : , , ( SQL- MSDN). , . , . , - .

PL/SQL

PL/SQL , ANTLR3 . , java-runtime. java , AST ( , ). ,

 decimal_key : {input.LT(1).getText().equalsIgnoreCase("decimal")}? REGULAR_ID 

:
decimal_key: DECIMAL , .

C#-

, , 5 6 , . . -, runtime.

C# ( , , . . false ):

 #if DEBUG && false Sample not compilied wrong code var 42 = a + ; #else // Compilied code var x = a + b; #endif 

, -, COMMENTS_CHANNEL DIRECTIVE . codeTokens , . . , ANTLR . — CSharpPreprocessorParser.g4 . true false #if , #elif , else , true , , . Conditional Symbols ( "DEBUG").

true , codeTokens , — . ( var 42 = a + ; ) . : CSharpAntlrParser.cs .

स्ट्रिंग इंटरपोलेशन

, , , (interpolation-expression), . , (, #0.##). , (regular), (verbatium), . MSDN .

, :

 s = $"{p.Name} is \"{p.Age} year{(p.Age == 1 ? "" : "s")} old"; s = $"{(p.Age == 2 ? $"{new Person { } }" : "")}"; s = $@"\{p.Name} ""\"; s = $"Color [ R={func(b: 3):#0.##}, G={G:#0.##}, B={B:#0.##}, A={A:#0.##} ]"; 

, . CSharpLexer.g4 .

परीक्षण

ANTLR

Roslyn, , . ANTLR :

• , . , TSQL antlr grammars-v4 . C# AllInOne.cs , Roslyn.
• .
• . PHP WebGoat , phpbb , Zend Framework . C# Roslyn-1.1.1 , Corefx-1.0.0-rc2 , ImageProcessor-2.3.0 , Newtonsoft.Json-8.0.2 .

ANTLR Roslyn

Release . ANTLR 4 4.5.0-alpha003 Roslyn (Microsoft.CodeAnalysis) 1.1.1.

WebGoat.PHP

— 885. — 137 248, — 4 461 768.
— 00:00:31 ( 55%, 45%).

PL/SQL Samples

— 175. — 1 909, — 55 741.
< 1 . ( 5%, 95%).

CoreFX-1.0.0-rc2

— 7329. — 2 286 274, — 91 132 116.
:

• Roslyn: 00:00:04 .,
• ANTLR: 00:00:24 . ( 12%; 88%).

Roslyn-1.1.1

— 6527. — 1 967 672, — 74 319 082.
:

• Roslyn: 00:00:03 .,
• ANTLR: 00:00:16 . ( 12%; 88%).

CoreFX Roslyn , C# ANTLR 5 Roslyn, . , « » , Roslyn, C#- Java, Python JavaScript ( ), .

, , . PHP, , . , , T-SQL PL/SQL ( ) ( 20). , C# SHARP: NEW_LINE Whitespace* '#'; SHARP: '#'; , 7 , 10 ! , , #, ( , ).

ANTLR Roslyn

C#-, ANTLR:

 namespace App { class Program { static void Main(string[] args) { a = 3 4 5; } } class B { c } 

ANTLR

• token recognition error at: '' at 3:5
• mismatched input '4' expecting {'as', 'is', '[', '(', '.', ';', '+', '-', '*', '/', '%', '&', '|', '^', '<', '>', '?', '??', '++', '--', '&&', '||', '->', '==', '!=', '<=', '>=', '<<'} at 8:19
• extraneous input '5' expecting {'as', 'is', '[', '(', '.', ';', '+', '-', '*', '/', '%', '&', '|', '^', '<', '>', '?', '??', '++', '--', '&&', '||', '->', '==', '!=', '<=', '>=', '<<'} at 8:21
• no viable alternative at input 'c}' at 15:5
• missing '}' at 'EOF' at 15:6

Roslyn

• test(3,5): error CS1056: Unexpected character ''
• test(8,19): error CS1002:; expected
• test(8,21): error CS1002:; expected
• test(15,5): error CS1519: Invalid token '}' in class, struct, or interface member declaration
• test(15,6): error CS1513: } expected

, Roslyn , ANTLR. . . , Roslyn , . , ( , ), ANTLR . ANTLR , ( , ). , #if , . ( - ).

मेमोरी की खपत

, ANTLR 4 , , . ( 70000 PHP ) , . lexer.Interpreter.ClearDFA() parser.Interpreter.ClearDFA() .

, . , GetAllTokens() ClearDFA() ( ) "Object reference not set to an instance of an object". , ANTLR C#, ( ) ( ) ReadWriterLockSlim .

Roslyn . 5 C# aspnet-mvc-6.0.0-rc1 , roslyn-1.1.1 , corefx , Newtonsoft.Json-8.0.2 ImageProcessor-2.3.0 200 .

निष्कर्ष

ANTLR Roslyn. निम्नलिखित लेखों में हम बताएंगे:

• AST Visitor Walker (Listener);
• , ANTLR 4;
• .NET;
• AST;
• DSL .

VladimirKochetkov « ‎ SAST» 40 60 .

सूत्रों का कहना है

• Modeling and Discovering Vulnerabilities with Code Property Graphs; Fabian Yamaguchi; 2014.
• Compilers: Principles, Techniques, and Tools; Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman; 2006।
• The Definitive ANTLR Reference; Terence Parr; 2014.
• Adaptive LL(*) Parsing: The Power of Dynamic Analysis, Terence Parr; Sam Harwell; 2014.
• Roslyn code & docs, https://github.com/dotnet/roslyn
• ANTLR grammars, https://github.com/antlr/grammars-v4
• ANTLR code, https://github.com/antlr/antlr4