फ्लेक्स और बाइसन के साथ परसिम पायथन कोड

प्रविष्टि

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

पार्सर पर काम करने की प्रक्रिया काफी मनोरंजक थी और मैं आपके साथ अपने अनुभव को साझा करना चाहूंगा, साथ ही आपको कुछ ऐसे नुकसानों के बारे में बताऊंगा जो हमें विकास के चरण में मिले थे।

शब्दावली

यदि आप पहले से ही व्याकरण के साथ काम कर चुके हैं और जानते हैं कि कंपाइलर कैसे काम करता है, तो अगले पैराग्राफ में आपका स्वागत है, बाकी आपका स्वागत है।

पार्सर विकास प्रक्रिया को दो मुख्य घटकों में विभाजित किया गया है:

• इनपुट स्ट्रीम का विश्लेषण और टोकन में विभाजन (लेक्सिकल विश्लेषण)
• वाक्यविन्यास नियमों के एक सेट के साथ पार्सिंग टोकन (पार्सिंग)

आइए थोड़ा उदाहरण देखें। एक अभिव्यक्ति (या इनपुट डेटा स्ट्रीम) होने दें:

3 + 4 * 15 

इनपुट स्ट्रीम परिवर्तित करने के लिए नियम बनाएँ:

 [1-9]* -> NUMBER + -> PLUS * -> MULT 

इस प्रकार, शाब्दिक विश्लेषण के बाद हम प्राप्त करते हैं:

 NUMBER(3) PLUS(+) NUMBER(4) MULT(*) NUMBER(15) EQUAL(=) 

निम्नलिखित एक व्याकरण का एक उदाहरण है, जिसके साथ बाद में, नियमों का उपयोग करते हुए, आप अभिव्यक्ति को पार्स कर सकते हैं:

 exp: NUMBER | exp sign exp sign: PLUS | MULT * / \ + 15 / \ 3 4 

इस उदाहरण में, NUMBER, MULT, PLUS - परिभाषा, टर्मिनलों, या टोकनों द्वारा, शाब्दिक विश्लेषण के चरण में परिभाषित किया गया है। expr, sign टर्मिनल नहीं हैं, क्योंकि वे समग्र इकाइयाँ हैं।

यह परिचय थकाऊ नहीं है, इसलिए, सिद्धांत के लिए पुस्तक फ्लेक्स एंड बाइसन ओ'रेली का उल्लेख करना चाहिए।

व्याकरण

अजगर के लिए पूर्ण व्याकरण (संस्करण 2.5.2) यहां पाया जा सकता है:
http://docs.python.org/release/2.5.2/ref/grammar.txt

मेरा काम केवल कक्षाओं, कार्यों और फ़ंक्शन कॉल की परिभाषा की पहचान करना था।

शुरू करने के लिए, हम विस्तारित बैकस-नौर फॉर्म (आरबीएनएफ) ( विकी ) का उपयोग करके व्याकरण के आवश्यक हिस्से का वर्णन करेंगे।

 class_def = CLASS classname [inheritance] COLON suite classname = ID inheritance = LBRACE class_args_list RBRACE class_args_list = [class_arg] class_arg = dotted_name {COMMA dotted_name} dotted_name = ID {DOT ID} 

यहां [X] की 0 या 1 घटना है, {Y} 0 है या {Y} अधिक घटनाएं हैं Y

वर्ग का नाम और उसकी निर्भरता निर्धारित करने के लिए पर्याप्त है। अब सुविधाओं के लिए।

 func_def = DEF funcname LBRACE [func_args_list] RBRACE COLON suite funcname = ID func_args_list = [func_arg] func_arg = (dotted_name | star_arg) {OTHER | COMMA | dotted_name | star_arg | MESSAGE} star_arg = [STAR] STAR ID 

वैसे, यह माना जाता है कि उपयोगकर्ता कोड सही होगा (दुभाषिया के दृष्टिकोण से), अन्यथा व्याकरण के नियमों को अधिक सख्ती से परिभाषित किया जाना चाहिए।

खैर, अब के लिए, चलो व्याकरण के साथ समाप्त करें और लेक्सर (लेक्सिकल एनालाइज़र) पर जाएं, क्योंकि व्याकरण का विश्लेषण करने से पहले, मूल पायथन कोड को टोकन में तोड़ दिया जाना चाहिए।

लेक्सिकल विश्लेषक

लेक्सर फ्लेक्स द्वारा उत्पन्न होता है। सबसे सरल उदाहरण:

 %{ #include <stdio.h> %} %% start printf("START\n"); stop printf("STOP\n"); . ; /*    */ %% 

इस उदाहरण को कैसे संकलित करें:

 % flex lexer.l && gcc lex.yy.c -o lexer -lfl 

व्याकरण के लिए व्याकरण का वर्णन करना सीखें:
http://rus-linux.net/lib.php?name=/MyLDP/algol/lex-yacc-howto.html

ठीक है, अब टोकन के बारे में फैसला करते हैं। व्याकरण में, हमने पहले ही निम्नलिखित का उपयोग किया है:
CLASS, COLON, COMMA, DEF, DOT, ID, LBRACE, MESSAGE, RBRACE, OTHER, STAR
हमें भी DEFINED - आरक्षित पायथन शब्दों की आवश्यकता है।

हम एक लेक्सर बनाते हैं।
कोड: https://gist.github.com/2158334

संक्षिप्त पार्सिंग: टिप्पणियों, रिक्त लाइनों और रिक्त स्थान की अनदेखी की जाती है। बाकी सब कुछ (तथाकथित टोकन स्ट्रीम) बाइसन इनपुट को दिया गया है।

वर्ण सेट जो पैटर्न पाता है (उदाहरण के लिए, पैटर्न [ \t]+ ) को yytext में रखा गया है। डिफ़ॉल्ट रूप से, yytext एक yytext पॉइंटर है, लेकिन यदि आप संकलन में -l स्विच जोड़ते हैं, तो yytext को चार सरणी के रूप में माना जाएगा। बाइसन को टोकन वापस करने से पहले, हम टेम्पलेट द्वारा परिभाषित मूल्य को yylval में yylval (अधिक विवरण के लिए, नीचे देखें)।

यह बाइसन के लिए व्याकरण का वर्णन करने के लिए आगे बढ़ने का समय है।

बिजोन

बायसन के लिए व्याकरण का वर्णन करना सीखें: http://rus-linux.net/lib.php?name=/MyLDP/algol/lex-yacc-howto.html

मैं आपको इस लेख के बारे में फिर से बता रहा हूं, क्योंकि जो लोग बाइसन के लिए व्याकरण नहीं बना सकते हैं, वे इस लिंक पर सामग्री का उपयोग करके आसानी से सीख सकते हैं। खैर, कौन जानता है कि कैसे - महान, चलो आगे बढ़ते हैं।

इसलिए, व्याकरण लेख के अनुच्छेद को देखते हुए, हम बाइसन के लिए एक व्याकरण रचना करने का प्रयास करेंगे:

कोड: https://gist.github.com/2158315

बाइसन नियम में, प्रत्येक टोकन का एक अर्थ है। वर्तमान नियम द्वारा एकत्रित समूह का मूल्य $ में संग्रहीत किया जाता है, शेष टोकन का मूल्य $1, $2, …

 test_rule: token1, token2, token3; $$ $1 $2 $3 

$n में संग्रहित मूल्य कुछ भी नहीं है, लेकिन जब yylval टोकन लौटाता है, तो yylval का मूल्य।

.tab.h -d साथ रनिंग बाइसन फ़ाइल .tab.h जेनरेट करता है, इसमें .tab.h में उपयोग किए जाने वाले टोकन के प्रकार की मैक्रो परिभाषाएँ होती हैं। प्रत्येक टोकन संख्या > 257 से मेल खाता है। इस फ़ाइल को #include "pyparser.tab.h" में शामिल किया जाना चाहिए, जो हमने किया था: #include "pyparser.tab.h" ।

विश्लेषक कैसे काम करता है? yyparse फ़ंक्शन को main से yyparse है, जो विश्लेषण शुरू करता है - टोकन पढ़ता है, कुछ क्रियाएं करता है, और बाहर निकलता है अगर यह इनपुट पाठ ( return 0 ) या सिंटैक्स त्रुटि ( return 1 ) के अंत का सामना करता है।

बाइसन के काम के बारे में अधिक जानकारी: http://www.linux.org.ru/books/GNU/bison/bison_7.html

हम यह संकलित करने और परखने की कोशिश कर रहे हैं कि हमारे पास क्या है:

 % bison -d pyparser.y --verbose && flex lexer.l && g++ -c lex.yy.c pyparser.tab.c && g++ -o parser lex.yy.o pyparser.tab.o -ll -ly 

परीक्षण उदाहरण:

 class Foo: pass class Test(Foo): class Test2: def __init__(self): pass def foo(): pass 

परिणाम:

  >> CLASS: Foo() >> CLASS: Test(Foo) >> CLASS: Test2() >> FUNC: __init__(self) >> FUNC: foo() 

सिद्धांत रूप में, यह सच है, हालांकि काफी नहीं है। मैं फ़ंक्शन की परिभाषा में "पूरा नाम" देखना चाहता हूं, जो है:

 >> CLASS: Foo() >> CLASS: Test(Foo) >> CLASS: Test2() >> FUNC: Test.Test2.__init__(self) >> FUNC: Test.Test2.foo() 

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

विचार और कार्यान्वयन आगे है।

पायथन सुविधाएँ

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

yylloc चार तत्वों की एक संरचना है: first_line, first_column, last_line last_column । first_line हम वर्तमान लाइन की संख्या (डिबगिंग के लिए उपयोगी है, और यह मेरे काम का हिस्सा है) को last_column करेगा, last_column हम इंडेंट रखेंगे।

हम कोड में परिवर्तन करते हैं। लेसर में, yylloc चर के प्रकार और लाइन संख्या के लिए डिफ़ॉल्ट मान को परिभाषित करें:

 extern YYLTYPE yylloc; #define YY_USER_INIT yylloc.first_line=1; // =0 

जब हम एक नई पंक्ति को पूरा करते हैं:

 yylloc.first_line++; yylloc.last_column = 0; isNewLine = true; 

यदि कोई रेखा रिक्त स्थान से शुरू होती है:

 if (isNewLine == true && 0 == yyleng % SPACES_PER_INDENT) yylloc.last_column = yyleng / SPACES_PER_INDENT; isNewLine = false; 

yyleng - टेम्पलेट द्वारा पाया गया टोकन की लंबाई। डिफ़ॉल्ट रूप से, SPACES_PER_INDENT को 4 (मानक द्वारा) सेट करें।

यदि पंक्ति टैब वर्ण से शुरू होती है:

 if (isNewLine == true) yylloc.last_column = yyleng; isNewLine = false; 

अब हम लाइन काउंट को सही करेंगे। अजगर में ट्रिपल उद्धरण हैं, आमतौर पर प्रलेखन पर लंबी टिप्पणी के लिए उपयोग किया जाता है। उपेक्षा के लिए, हम एक फ़ंक्शन लिखते हैं:

 static string skipMessage(string _ch){ string ch; string str = _ch; _ch = _ch[0]; bool skip = false; int count = 1; for(;;ch = yyinput()) { str += ch; if (ch == _ch){ if (count == 3) return str; else count++; } else count = 1; if ("\n" == ch || "\r" == ch) yylloc.first_line++; } } 

यहां, वास्तव में, कोई व्यक्ति नियमित अभिव्यक्ति के साथ मिल सकता है, लेकिन फिर लाइन संख्या को सही ढंग से निर्धारित करना संभव नहीं होगा - हम regexp द्वारा खाए गए लाइनों की संख्या का पता लगाने में सक्षम नहीं होंगे (या हम कर सकते हैं? यदि हां, तो विधि लिखें)।

इसके अलावा टिप्पणी लाइन को अनदेखा करना न भूलें:

 static void skipComments(){ for(char ch = yyinput();;ch = yyinput()) { if ('\0' == ch || '\n' == ch || '\r' == ch) { yylloc.first_line++; break; } } } 

हम स्टैक एल्गोरिदम को पास करते हैं।

नेस्टिंग फ़ंक्शन का निर्धारण करें

हम ऊपर वर्णित एल्गोरिदम के अनुसार कार्य करते हैं।

सुविधा के लिए, हम प्रकारों को परिभाषित करते हैं:

 typedef pair <string, int> meta_data; // <_, > typedef stack <meta_data> meta_stack; static meta_stack class_st; 

हमने स्टैक पर <__, > की एक जोड़ी लगाई

 class_def: CLASS classname inheritance COLON suite { int indent = @1.last_column; //    meta_data new_class($2, indent); clean_stack( class_st, indent ); class_st.push( new_class ); } ; 

वर्तमान इंडेंट से पहले स्टैक को खाली करने का कार्य:

 static void clean_stack( meta_stack& stack, int indent ) { while(!stack.empty()) { if( indent > stack.top().second ) break; stack.pop(); } } 

खैर, हम फ़ंक्शन का पूरा नाम निर्धारित करते हैं:

 func_def: DEF funcname LBRACE func_args_list RBRACE COLON suite { string fnc_name = $2; int indent = @1.last_column; clean_stack( class_st, indent ); meta_stack tmp_class_st(class_st); while (!tmp_class_st.empty()) { fnc_name = tmp_class_st.top().first + "." + fnc_name; tmp_class_st.pop(); } } 

निष्कर्ष

मैंने लेख में एक फ़ंक्शन कॉल की परिभाषा का वर्णन करना शुरू नहीं किया, क्योंकि यह वास्तव में एक फ़ंक्शन घोषणा को खोजने के समान है, हालांकि इसकी अपनी कठिनाइयां हैं। अगर रुचि है - यहाँ github पर मेरी रिपॉजिटरी है: https://github.com/sagod/pyparser । टिप्पणियाँ, टिप्पणियाँ और पूल अनुरोधों का स्वागत है।

साहित्य

• जॉन लेविन द्वारा फ्लेक्स एंड बाइसन: shop.oreilly.com/product/9780596155988.do
• बाइसन: www.linux.org.ru/books/GNU/bison/bison_7.html
• फ्लेक्स: www.delorie.com/gnu/docs/flex/flex_1.html
• Rus -linux पर अच्छा लेख: rus-linux.net/lib.php?name=/MyLDP/algol/lex-yacc-howto.html