लेखन की सुविधाएँ और LR-जनरेटर की संभावित सुविधाएँ

परिचय

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

संदर्भ सेट करने के लिए, मैं आपको सूचित करूंगा कि विश्लेषण के लिए व्याकरण ECMAScript है, जिसे जावास्क्रिप्ट के रूप में भी जाना जाता है। विशिष्ट विनिर्देश ECMA-262 है, जून 2011 का संशोधन 5.1।


जब मुझे पहली बार लेखन की कठिनाइयों का सामना करना पड़ा, तो मैंने तुरंत कंपाइलर कोड लिखने में जल्दबाजी नहीं की। सबसे पहले, मैंने अध्ययन किया कि बड़ी कंपनियों ने इन समस्याओं को कैसे हल किया: मोज़िला और Google (ओपेरा और IE स्रोत सार्वजनिक डोमेन में नहीं हैं)। जैसा कि यह निकला, उन्होंने वास्तव में व्याकरण की औपचारिकता के साथ भाप स्नान नहीं किया और कोड लिखा है, अर्थात, जैसा कि मैंने आपको पहले भाग में करने की चेतावनी दी थी। प्रसंस्करण का एक उदाहरण यदि v8 में है (Chrome का JS इंजन):

IfStatement* Parser::ParseIfStatement(ZoneStringList* labels, bool* ok) { // IfStatement :: // 'if' '(' Expression ')' Statement ('else' Statement)? Expect(Token::IF, CHECK_OK); Expect(Token::LPAREN, CHECK_OK); Expression* condition = ParseExpression(true, CHECK_OK); Expect(Token::RPAREN, CHECK_OK); Statement* then_statement = ParseStatement(labels, CHECK_OK); Statement* else_statement = NULL; if (peek() == Token::ELSE) { Next(); else_statement = ParseStatement(labels, CHECK_OK); } else { else_statement = factory()->NewEmptyStatement(); } return factory()->NewIfStatement(condition, then_statement, else_statement); } 

उन्होंने ऐसा क्यों किया? इसके कई कारण हैं:

1. काम की गति। हालांकि एफएसएम बहुत तेज है, "रैखिक" निष्पादन अभी भी तेज है।
2. लचीलापन। तथ्य यह है कि बाइसन / एएनटीएलआर / बूस्ट :: स्पिरिट / का उपयोग नहीं किया गया था, मेरे स्वयं के विकास ने अप्रत्यक्ष रूप से मुझे इस विचार में डुबो दिया कि यह इस व्याकरण के साथ इतना सरल नहीं था, और मैं केवल वही नहीं था जो सीमाओं में भाग गया था।
3. वे खरोंच से भाषा के डेवलपर नहीं हैं (उदाहरण के लिए, डार्ट के साथ), इसलिए मानक में नए परिवर्तन से पहले एक-दो साल के लिए लिखना और भूलना पर्याप्त है। यह इस प्रकार है कि व्याकरण परिवर्तन हर दिन नहीं किया जाता है।

बेशक, वहाँ कई minuses हैं:

1. केवल पार्सिंग के लिए कोड की 5-10 हजार लाइनें थोड़ी अधिक हैं।
2. कोई विनिर्देश नहीं रह सकता है। चूंकि कोड बहुत ही खंडित है, इसलिए किसी भाषा योजना को केवल स्रोत से स्क्रैच से इकट्ठा करना बहुत मुश्किल है।
3. मुश्किल मैक्रोज़ के बावजूद कोड को संभालने में त्रुटि:
   

    #define CHECK_OK ok); \ if (!*ok) return NULL; \ ((void)0 

   
   

पार्सर / पार्सर जेनरेटर आवश्यकताएँ

अब आप व्याकरण और मेरी उम्मीदों के नुकसान पर आगे बढ़ सकते हैं। मुझे तुरंत कहना होगा कि कुछ बिंदु पूरी तरह से तृतीय-पक्ष सॉफ़्टवेयर द्वारा किए जाते हैं। लेकिन कुल मिलाकर कोई समग्र कार्यक्रम नहीं है, और ऐसे बिंदु हैं जिन पर मुझे कोई समाधान नहीं मिला।

टिप्पणियाँ सहायक हैं!

अपने कार्य में, मुझे पाठ और टिप्पणियों की स्थिति को बचाने की आवश्यकता थी, और उन्हें त्यागने की नहीं। ANTLR और बायसन / फ्लेक्स ऐसा कर सकते हैं। पहला लेक्सर के बहुसंकेतन के कारण, दूसरा - फ्लेक्स की शक्ति के कारण। चूँकि मैंने अभी तक अपना लेसर लिखना शुरू नहीं किया है, मैं फ्लेक्स का उपयोग करता हूँ और उन्होंने इस समस्या को निम्नानुसार हल किया:

  /* [Comment] = [MultiLineComment] | [SingleLineComment] */ /* [MultiLineComment] */ /* start of multiline, grab whole comment, that's why i use yymore() */ "/*" { BEGIN(multilinecomment); yymore(); m_loc.setMore(true); } /* skip all comments chars except "*" */ <multilinecomment>[^*\n\r]* { yymore(); } /* skip all "*", that not followed by "/" */ <multilinecomment>"*"+[^*/\n\r]* { yymore(); } /* end of comment */ <multilinecomment>"*"+"/" { m_comments.push_back(CParser::Comment(yytext, m_loc.tokenLine(), m_loc.tokenCol())); m_loc.setMore(false); BEGIN(INITIAL); } /* [SingleLineComment] increment lineNo */ ("//"([^\r\n])*{LineTerminator})|("//"([^\r\n])*) { m_comments.push_back(CParser::Comment(yytext, m_loc.tokenLine(), m_loc.tokenCol())); m_loc.linc(); } 

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

पार्सर नियंत्रित लेसर मोड

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

 //     regexp'a /asd[^c]/i.match(s); //    -   a = b / c; 

यही है, पार्सर बॉक्स की जांच करने में सक्षम होना चाहिए अगर डिवीजन ऑपरेटर फिलहाल आ सकता है। फ्लेक्स स्तर पर, यह बस हल किया जाता है:

  /* [RegularExpressionLiteral] it has more length then [DivPunctor] (at least 3 == "/X/" versus 2 == "/="), that's why it would be proceeded first, before [DivPunctor] */ "/"{RegularExpressionFirstChar}({RegularExpressionFirstChar}|"*")*"/"({IdentifierStart}|[0-9])* { if (m_mode != Mode::M_REGEXP) REJECT; yylval->assign(yytext, yyleng); return token::T_REGEXP; } /* [DivPunctuator]: "/" or "/=" */ "/" return token::T_DIV; "/=" return token::T_DIVAS; 

चूंकि फ्लेक्स एक लालची लेक्सर है और जब तक संभव हो लेक्सेम को संसाधित करने की कोशिश करता है, तो सबसे पहले यह रेगेक्सप के लिए नियम में आएगा, और वहां, यदि डिवीजन मोड सेट है, तो यह अगले नियम पर जाएगा।

बाहर निकलने पर पार्सर का पेड़

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

  while (!accepted && !error) { ... switch (act.type) { ... case Action::ACTION_SHIFT: ... node.col = m_loc.tokenCol(); node.line = m_loc.tokenLine(); node.type = ParseNode::NODE_TERM; node.termVal = s; node.symb.term = tok; nodes.push(tree.create(node)); break; case Action::ACTION_REDUCE: ... node.type = ParseNode::NODE_NONTERM; node.symb.nonTerm = (Symbols::SymbolsType)act.reduce.nonTerm; CTree<ParseNode>::TreeNode * parent = tree.create(node); unsigned long ruleLen = act.reduce.ruleLength; while (ruleLen) { tree.add(parent, nodes.top(), true); nodes.pop(); ruleLen--; } nodes.push(parent); break; } } if (nodes.top()) tree.SetRoot(nodes.top()); 

कस्टम लुकहेड

व्याकरण में, आप बस ऐसी ही चीज़ देख सकते हैं

 ExpressionStatement = [lookahead ∉ {{, function}] Expression ; 

नहीं, यह एक मानक अपेक्षा-दृढ़ संकल्प प्रतीक नहीं है, जिसके बारे में मैंने पिछले भाग में बात की थी। यह पहली अभिव्यक्ति चरित्र को फ़िल्टर करने की कोशिश करने के विपरीत है। यही है, इस नियम के अनुसार, हमें एक्सप्रेशन से अतिरिक्त बेटी उत्पादों को बाहर फेंकना चाहिए जो टर्मिनल "{" से शुरू होते हैं। इस मामले में, यह ब्लॉक के बीच संघर्ष से बचने के लिए किया जाता है, जो "{}" की तरह लग सकता है और प्राणियों में से एक बस अभिव्यक्ति है: "{}" एक खाली जावास्क्रिप्ट ऑब्जेक्ट ऑब्जेक्ट के कार्य के रूप में। इसी तरह "फ़ंक्शन" के लिए।

निर्णय पार्सर के जादू के बिना किया जा सकता है, लेकिन केवल व्याकरण को घुमाकर:

 ExpressionStatement = ExpressionWithoutBracket ExpressionWithoutBracket = ... | AssignmentExpressionWithoutBracket | ... ... 

और इसलिए जब तक हम टर्मिनल "{" से शुरू होने वाले नियम को प्राप्त नहीं कर लेते, और हम इस नियम को पारम्परिक व्याकरण से बाहर कर देते हैं। समस्या यह है कि लगभग 20 मध्यवर्ती चरण हैं। इसके अलावा, हम इसे 2 से गुणा करते हैं (यह भी "फ़ंक्शन"!) और फिर 2 से क्योंकि यह तकनीक उसी नियम के लिए उपयोग की जाती है लेकिन एक अलग स्थिति में (2 पंक्तियों - अभिव्यक्ति और) ExpressionNoIn)। नहीं, यह मुझे बिल्कुल खुश नहीं करता है।

तकनीकी रूप से, मेरे पार्सर में, यह काफी सरलता से हल किया गया है:

 ExpressionStatement = Expression {filter: [objectLiteral, functionDeclaration]} ... ObjectLiteral = {commonId: objectLiteral} '{' '}' | '{ 'PropertyNameAndValueList '}' | '{' ',' '}' 

बंद करते समय, यदि आवश्यक हो, तो हम माता-पिता से बच्चे को फ़िल्टरिंग लेबल लटकाते हैं। और जब हम फ़िल्टरिंग के अंतर्गत आने वाले किसी नियम को पूरा करते हैं, तो हम इसे बंद करने में शामिल नहीं करते हैं।

कुछ बाल नियम बंद करें

यह पिछले पैराग्राफ की लगभग एक उप-प्रजाति है, लेकिन यहां आपको न केवल पहले चरित्र को देखने की जरूरत है, बल्कि एक मनमाने ढंग से भी। चित्रण पूर्वोक्त अभिव्यक्ति है और एक संबंधित चर यदि आप अधिक विस्तार से देखते हैं, तो समस्या की जड़ें उदाहरण के लिए 2 प्रकार के लिए जाती हैं:
// पहला वाक्य विन्यास
for (var id in obj) अल्रेट (आईडी);
// दूसरा वाक्यविन्यास
के लिए (var आईडी = 1; आईडी <10; आईडी) अलर्ट (आईडी);

सामान्य परिस्थितियों में, जब वेरिएबल को इनिशियलाइज़ किया जाता है, तो हम विंडो में a, a la '' eval '' का उपयोग कर सकते हैं; यह ऑपरेटर किसी दिए गए ऑब्जेक्ट में सदस्य के अस्तित्व की जांच करता है (हुसर्स, चुप रहो!)। हालाँकि, लूप में, इसका उपयोग किसी ऑब्जेक्ट के सभी सदस्यों पर पुनरावृति करने के लिए किया जाता है। और, वास्तव में, भ्रम बहुत आसानी से उत्पन्न हो सकता है, इसलिए इसे दूसरे सिंटैक्स में उपयोग करने से मना किया जाता है। वास्तव में, LALR पार्सर आसानी से अगले चरित्र (';' या ')') की जाँच के साथ दृढ़ संकल्प के लिए यह सब धन्यवाद देता है, लेकिन व्याकरण के रचनाकारों ने स्पष्ट रूप से पार्सर्स के व्यापक वर्ग पर ध्यान केंद्रित किया है और इसलिए "ऑपरेटर" के बिना मामले के लिए 20 नियमों की नकल की है। हालांकि, आपको व्याकरण का पालन करने की आवश्यकता है, इसलिए, आपत्तिजनक बच्चे (महान-महान -...) नियमों को बंद करने के लिए भी एक तंत्र की आवश्यकता है।

मेरे पास विवरण के अंतरों को छोड़कर, यह पिछले पैराग्राफ के समान है:

 ExpressionNoIn = Expression {filter: [RelationalExpression_6]} ... RelationalExpression = ShiftExpression | RelationalExpression '<' ShiftExpression | RelationalExpression '>' ShiftExpression | RelationalExpression '<=' ShiftExpression | RelationalExpression '>=' ShiftExpression | RelationalExpression 'instanceof' ShiftExpression | {id: RelationalExpression_6} RelationalExpression 'in' ShiftExpression 

यह एक वैकल्पिक सुविधा है जो जीवन को आसान बनाती है। और वास्तव में त्रुटियों को दिखाने के उदाहरण कितने हैं। व्याकरण में, वे नियमों में से एक में NoIn जोड़ना भूल गए:

 ConditionalExpressionNoIn = LogicalORExpressionNoIn ? AssignmentExpression : AssignmentExpressionNoIn 

दूसरा असाइनमेंटExpression पोस्टफ़िक्स के साथ स्पष्ट होना चाहिए।

ऑटो डालें '?'

एक और मनोरंजक जावास्क्रिप्ट यह है कि आपको अर्धविराम के साथ बयानों को समाप्त करने की आवश्यकता नहीं है। यहां तक ​​कि उन जगहों पर जहां व्याकरण की आवश्यकता होती है। प्रविष्टि नियम एक साथ वर्णन में सरल और लागू करने में कठिन हैं:

1. यदि पार्सर अगले टोकन पर एक त्रुटि लौटाता है और यह टोकन '{' है या तो इसे पिछले एक से कम से कम एक लाइन फीड द्वारा अलग किया जाता है।
2. EOF से मुलाकात की और यह अप्रत्याशित था।
3. For'a नियमों के लिए लागू नहीं होते हैं। For'a हेडर में कोष्ठक के बीच कमांड।

सम्मिलन काफी सरल है - यदि आप इस कार्रवाई की आवश्यकता का निर्धारण करते हैं, तो नए एफएसएमएमए सर्कल पर जाएं, अंतिम रीड टोकन को अर्धविराम के साथ बदल दें। ठीक है, अगली पाली में, हम नया टोकन नहीं पढ़ते हैं, लेकिन उस त्रुटि का उपयोग करते हैं।

यूनिकोड समर्थन

जेएस इस संबंध में एक बहुत ही सक्षम भाषा है। Utf16 के लिए समर्थन मानक में सख्ती से वर्तनी है। इस बिंदु तक कि पूरे स्रोत को पार्स करने से पहले utf16 में परिवर्तित किया जाना चाहिए। हालांकि, दुर्भाग्य से, फ्लेक्स को यह नहीं पता कि यह कैसे करना है (नहीं, \ xXX उपयुक्त नहीं है। ऑफहैंड, लगभग एक हजार वर्णों को एन्कोडेड करना होगा)। इसलिए, जबकि यह शर्त पूरी नहीं हुई है।

मात्रात्मक समर्थन

एक और बहुत बड़ा विषय जो व्याकरण को आसान बनाता है। सबसे पहले, मुझे निम्नलिखित क्वांटिफायर की आवश्यकता थी: "|" - नियमों के वेरिएंट, जहां बाईं ओर आम है, और दाएं अलग हैं; "?" - नियम में वैकल्पिक चरित्र; "*" - चरित्र को 1 या अधिक बार दोहराया जाता है। हां, वे बीएनएफ व्याकरण के स्तर पर पूरी तरह से हल हैं:

 A = B | C //   A = B A = C A = B? C //   A = BC A = C A = B* //   A = AB A = B 

अंतिम उदाहरण को छोड़कर यहां सब कुछ ठीक है। इस मामले में, हम पेड़ में कदम रखते हैं। यही है, यदि बी को 5 बार दोहराया जाता है, तो हमें 5. के बराबर गहराई के साथ एक नोड ए मिलता है। यह बहुत असुविधाजनक है। इसलिए, फिर से, मैंने एक सुविधाजनक रैखिक प्रतिनिधित्व प्रदान करने वाले पार्सर में संशोधन शुरू करने का फैसला किया - BBBBB 5 पत्तियों बी के साथ एक नोड ए। और क्लोजर फ़ंक्शंस और कन्वेंशन परिभाषाओं में संशोधन। करीब में () हम एक तत्व को लूप करते हैं।

लेकिन क्या होता है अगर हमेशा की तरह:


वह सब है। इस लेख को पढ़ने के लिए धन्यवाद।

लेख के अंश

1. भाग 1. मूल सिद्धांत
2. भाग 2. LR जनरेटर का विवरण
3. भाग 3. एलआर-जनरेटर के लेखन और संभव सुविधाओं की विशेषताएं