ट्यूटोरियल "एलएलवीएम के साथ एक प्रोग्रामिंग भाषा बनाना" के अध्याय 2 में आपका स्वागत है। इस अध्याय में, हम देखेंगे कि अध्याय 1 में बनाए गए लेक्सिकल एनालाइज़र का उपयोग किस तरह से किया जाए ताकि हम अपनी कलीसिया की भाषा के लिए एक पूर्ण पार्सर का निर्माण कर सकें । हमारे पास पार्सर तैयार होने के बाद, हम एब्सट्रैक्ट सिंटैक्स ट्री (एएसटी) (एब्सट्रैक्ट सिंटैक्स ट्री) का निर्माण करेंगे।

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

सार सिंटेक्स ट्री (एएसटी)

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

/// ExprAST -      . class ExprAST { public: virtual ~ExprAST() {} }; /// NumberExprAST -       (, "1.0"). class NumberExprAST : public ExprAST { double Val; public: NumberExprAST(double val) : Val(val) {} };

उपरोक्त कोड एक्सप्रैस्ट बेस क्लास और उसके उपवर्ग की परिभाषा को दर्शाता है, जिसका उपयोग हम संख्यात्मक शाब्दिक के लिए करते हैं।

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

 /// VariableExprAST -      (, "a"). class VariableExprAST : public ExprAST { std::string Name; public: VariableExprAST(const std::string &name) : Name(name) {} }; /// BinaryExprAST -      . class BinaryExprAST : public ExprAST { char Op; ExprAST *LHS, *RHS; public: BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) : Op(op), LHS(lhs), RHS(rhs) {} }; /// CallExprAST -      . class CallExprAST : public ExprAST { std::string Callee; std::vector<ExprAST*> Args; public: CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) : Callee(callee), Args(args) {} };

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

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

 /// PrototypeAST -    ""  , ///        (,  , ///    ). class PrototypeAST { std::string Name; std::vector<std::string> Args; public: PrototypeAST(const std::string &name, const std::vector<std::string> &args) : Name(name), Args(args) {} }; /// FunctionAST -     class FunctionAST { PrototypeAST *Proto; ExprAST *Body; public: FunctionAST(PrototypeAST *proto, ExprAST *body) : Proto(proto), Body(body) {} };

बहुरूपदर्शक में, कार्यों को उनके तर्कों की संख्या से ही टाइप किया जाता है। चूँकि सभी मान दोहरे सटीक वास्तविक संख्याएँ हैं, इसलिए यह प्रत्येक तर्क के प्रकार को कहीं भी संग्रहीत करने का कोई मतलब नहीं है। एक वास्तविक प्रोग्रामिंग भाषा में, ExprAST वर्ग में संभवतः एक अन्य प्रकार का फ़ील्ड होगा।

अब हम अंत में बहुरूपदर्शक में अभिव्यक्तियों और कार्यों के बारे में बात कर सकते हैं।

पार्सर आधार

अब जब हमारे पास एएसटी तत्व हैं, तो हमें इसे बनाने के लिए एक कोड पार्सर को परिभाषित करना होगा। यहाँ विचार यह है कि हम एक एक्स में "x + y" (जो कि लेक्सिकल पार्सिंग के दौरान तीन टोकन के रूप में लौटाए जाते हैं) जैसे कुछ को पार्स करना चाहते हैं, जो कुछ इस तरह से उत्पन्न हो सकता है:

  ExprAST *X = new VariableExprAST("x"); ExprAST *Y = new VariableExprAST("y"); ExprAST *Result = new BinaryExprAST('+', X, Y);

ऐसा करने से पहले, हम कई सहायक प्रक्रियाओं को परिभाषित करेंगे:

 /// CurTok/getNextToken -    . CurTok -   /// ,  . getNextToken     ///     CurTok. static int CurTok; static int getNextToken() { return CurTok = gettok(); }

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

 /// Error* -       . ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; }

ये सहायक प्रक्रियाएं हैं जो हमारे पार्सर त्रुटियों को संभालने के लिए उपयोग करेंगे। हमारे पार्सर में त्रुटियों का सुधार उपयोगकर्ता के लिए सबसे अच्छा और विशेष रूप से सुविधाजनक नहीं है, लेकिन इस ट्यूटोरियल के ढांचे के भीतर पर्याप्त होगा।

इन सहायक कार्यों के साथ, हम अपने व्याकरण के पहले भाग को लागू कर सकते हैं: संख्यात्मक शाब्दिक।

पार्सिंग एक्सप्रेशंस

चलो संख्यात्मक शाब्दिक के साथ शुरू करते हैं, उनके साथ सबसे आसान तरीका है। प्रत्येक व्याकरण नियम के लिए, हम एक फ़ंक्शन को परिभाषित करते हैं जो इस नियम का विश्लेषण करता है। संख्यात्मक शाब्दिकों के लिए, हमारे पास:

 /// numberexpr ::= number static ExprAST *ParseNumberExpr() { ExprAST *Result = new NumberExprAST(NumVal); getNextToken(); //   return Result; }

फ़ंक्शन बहुत सरल है: जब बुलाया जाता है, तो यह उम्मीद करता है कि वर्तमान टोकन tok_number है। यह एक NumberExprAST नोड बनाता है, यह वर्तमान संख्या के मूल्य को पारित करता है, लेक्सिकल विश्लेषक को अगले टोकन पर ले जाता है और बनाए गए नोड को वापस करता है।

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

 /// parenexpr ::= '(' expression ')' static ExprAST *ParseParenExpr() { getNextToken(); //  (. ExprAST *V = ParseExpression(); if (!V) return 0; if (CurTok != ')') return Error("expected ')'"); getNextToken(); //  ). return V; }

यह फ़ंक्शन पार्सर के बारे में कई दिलचस्प बातों को दर्शाता है:

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

निम्नलिखित व्याकरण नियम चर संदर्भ और फ़ंक्शन कॉल को संभाल रहे हैं:

 /// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' static ExprAST *ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); //  . if (CurTok != '(') //   . return new VariableExprAST(IdName); //  . getNextToken(); //  ( std::vector<ExprAST*> Args; if (CurTok != ')') { while (1) { ExprAST *Arg = ParseExpression(); if (!Arg) return 0; Args.push_back(Arg); if (CurTok == ')') break; if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); getNextToken(); } } //  ')'. getNextToken(); return new CallExprAST(IdName, Args); }

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

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

 /// primary /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr static ExprAST *ParsePrimary() { switch (CurTok) { default: return Error("unknown token when expecting an expression"); case tok_identifier: return ParseIdentifierExpr(); case tok_number: return ParseNumberExpr(); case '(': return ParseParenExpr(); } }

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

अब जब मूल भावों को संसाधित किया जा सकता है, तो हम बाइनरी अभिव्यक्तियों के साथ काम कर सकते हैं। वे बहुत अधिक जटिल हैं।

बाइनरी एक्सप्रेशंस पार्सिंग

बाइनरी एक्सप्रेशंस पार्स करने के लिए बहुत कठिन होते हैं क्योंकि वे अक्सर अस्पष्ट होते हैं। उदाहरण के लिए, स्ट्रिंग "x + y * z" के लिए, पार्सर या तो "x (y + y) * z" या "x + (y * z)" के रूप में पार्स कर सकता है। गणित की मूल बातें जानने के बाद, हम दूसरे विकल्प की उम्मीद करते हैं, क्योंकि "*" (गुणा) में "+" (जोड़) से अधिक प्राथमिकता है।

कई संभावित समाधान हैं, लेकिन सबसे सुंदर और कुशल तरीका ऑपरेटरों की प्रधानता को पार्स करना है । यह पार्सिंग तकनीक ऑपरेशन को प्राथमिकता देने के लिए पुनरावृत्ति का उपयोग करती है। पहले हमें एक प्राथमिकता तालिका चाहिए:

 /// BinopPrecedence -      static std::map<char, int> BinopPrecedence; /// GetTokPrecedence -     . static int GetTokPrecedence() { if (!isascii(CurTok)) return -1; // ,     . int TokPrec = BinopPrecedence[CurTok]; if (TokPrec <= 0) return -1; return TokPrec; } int main() { //     // 1 -  . BinopPrecedence['<'] = 10; BinopPrecedence['+'] = 20; BinopPrecedence['-'] = 20; BinopPrecedence['*'] = 40; //  . ... }

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

अब हम बाइनरी अभिव्यक्तियों को पार्स करना शुरू कर सकते हैं। ऑपरेटरों की प्रधानता को पार्स करने का मुख्य विचार संभावित रूप से अस्पष्ट बाइनरी ऑपरेटरों के साथ अभिव्यक्ति को भागों में विभाजित करना है। उदाहरण के लिए, अभिव्यक्ति "a + b + (c + d) * e * f + g"। ऑपरेटर पूर्वता पार्सर इसे बाइनरी ऑपरेटरों द्वारा अलग किए गए प्राथमिक अभिव्यक्तियों की एक धारा के रूप में मानता है। इस प्रकार, प्राथमिक पार्सिंग के दौरान, प्रमुख प्राथमिक अभिव्यक्ति "a" पहले पार्स की जाती है, और यह जोड़े को देखेगी [+, b] [+, (c + d)] [*, ] [*, f] और [+, g ]। कोष्ठक पर ध्यान दें: पार्सर को नेस्टेड अभिव्यक्तियों के बारे में चिंता करने की आवश्यकता नहीं है जैसे (सी + डी)।

शुरू करने के लिए, एक अभिव्यक्ति एक प्राथमिक अभिव्यक्ति है, संभावित रूप से [बिनॉप, प्राइमरेक्सप्र] जोड़े के अनुक्रम के बाद:

 /// expression /// ::= primary binoprhs /// static ExprAST *ParseExpression() { ExprAST *LHS = ParsePrimary(); if (!LHS) return 0; return ParseBinOpRHS(0, LHS); }

ParseBinOpRHS एक फ़ंक्शन है जो जोड़े के अनुक्रम का विश्लेषण करता है। यह विश्लेषण के लिए एक अभिव्यक्ति के लिए पूर्ववर्तीता और एक संकेतक लेता है। ध्यान दें कि "x" एक बिल्कुल वैध अभिव्यक्ति है: इस प्रकार, "बिनोप्रिहस" खाली हो सकता है, इस स्थिति में फ़ंक्शन उस अभिव्यक्ति को वापस करता है जो इसे पारित किया गया था। ऊपर हमारे उदाहरण में, कोड ParseBinOpRHS के लिए "ए" और वर्तमान टोकन "+" की अभिव्यक्ति उत्तीर्ण करता है ।

ParseBinOpRHS को दिया जाने वाला प्राथमिकता मूल्य इसके स्वीकार किए जाने के लिए आवश्यक ऑपरेटरों की न्यूनतम प्राथमिकता को दर्शाता है। उदाहरण के लिए, यदि धारा [+, x] और ParseBinOpRHS में वर्तमान जोड़ी को प्राथमिकता 40 स्थानांतरित की जाती है, तो यह टोकन स्वीकार नहीं करेगी (चूंकि प्राथमिकता "+" केवल 20 है)। इसलिए, ParseBinOpRHS के साथ शुरू होता है:

 /// binoprhs /// ::= ('+' primary)* static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { //    ,    while (1) { int TokPrec = GetTokPrecedence(); //           , //  ,    if (TokPrec < ExprPrec) return LHS;

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

  // ,  ,    . int BinOp = CurTok; getNextToken(); //    //       ExprAST *RHS = ParsePrimary(); if (!RHS) return 0;

इस प्रकार, यह कोड बाइनरी ऑपरेटर को प्राप्त करता है (और याद करता है), और उसके बाद प्राथमिक अभिव्यक्ति को पार्स करता है। यह जोड़े बनाता है, जिनमें से हमारे उदाहरण में पहला [+, बी] होगा।

अब जब हमने आरएचएस अनुक्रम से अभिव्यक्ति के बाईं ओर और एक जोड़ी का विश्लेषण किया है, तो हमें यह तय करना होगा कि अभिव्यक्ति को कैसे बांधें। विशेष रूप से, हम दोनों "(ए + बी) बिनोप अनपर्सड" और "ए + (बी बिनॉप अनस्पार्स्ड)" हो सकते हैं (जहां बिनॉप द्विआधारी ऑपरेटर है, अनपर्सड अनसैब्ड पार्ट है)। निर्णय लेने के लिए, हम अपनी प्राथमिकता निर्धारित करने के लिए एक और “बिनॉप” (बाइनरी ऑपरेटर) की प्रतीक्षा करते हैं और इसे बिनऑप की प्राथमिकता के साथ तुलना करते हैं (जो इस मामले में "+" है):

  //  BinOp   RHS  ,    RHS, //      RHS  LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) {

यदि "आरएचएस" के अधिकार के लिए बाइनरी ऑपरेटर की प्राथमिकता हमारे वर्तमान ऑपरेटर की प्राथमिकता से कम या बराबर है, तो हम जानते हैं कि हमारे पास मामला है ("ए + बी) बिनॉप ..."। हमारे उदाहरण में, वर्तमान "+" ऑपरेटर और अगले "+" ऑपरेटर की समान प्राथमिकता है। इसलिए, हम “a + b” के लिए AST नोड बनाएंगे, और फिर पार्सिंग जारी रखेंगे:

  ...     ... } //  LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); } }

हमारे उदाहरण में, "a + b +" को "(a + b)" के रूप में लौटाया जाएगा और लूप के अगले पुनरावृत्ति को "+" के साथ चालू टोकन के रूप में निष्पादित किया जाएगा। यह भाग स्वीकार किया जाएगा और आगे, जैसा कि आप याद करते हैं, "(c + d)" को प्राथमिक अभिव्यक्ति के रूप में पार्स किया जाना चाहिए, अर्थात, वर्तमान जोड़ी [+, (c + d)] होगी। तब बाइनरी ऑपरेटर के रूप में "*" के साथ एक अभिव्यक्ति प्राप्त होगी। इस मामले में, प्राथमिकता "*" प्राथमिकता "+" से अधिक है, ताकि ऊपर दिए गए सशर्त निर्माण को निष्पादित किया जाएगा।

बाईं ओर के लिए यहां सबसे महत्वपूर्ण सवाल यह होगा कि "इस स्थिति में पूर्ण रूप से दाईं ओर को कैसे अलग किया जाए"? विशेष रूप से, एएसटी के लिए हमारे उदाहरण के लिए सही ढंग से निर्मित होने के लिए, इसे आरएचएस अभिव्यक्ति चर के रूप में पूर्ण अभिव्यक्ति "(सी + डी) * ई * एफ" मिलना चाहिए। इसके लिए कोड आश्चर्यजनक रूप से सरल है (संदर्भ के लिए दो उपरोक्त ब्लॉकों का कोड डुप्लिकेट है):

  //  BinOp   RHS  ,    RHS, //      RHS  LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) {

  RHS = ParseBinOpRHS(TokPrec+1, RHS); if (RHS == 0) return 0;

  } //  LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); } }

फिलहाल, हम जानते हैं कि हमारी प्राथमिक अभिव्यक्ति के दाईं ओर बाइनरी ऑपरेटर की वर्तमान में बाइनरी ऑपरेटर की तुलना में अधिक प्राथमिकता है। इस प्रकार, हम जानते हैं कि "+" की तुलना में उच्च प्राथमिकता वाले ऑपरेटरों के जोड़े के किसी भी अनुक्रम को अलग किया जाना चाहिए और "RHS" के रूप में लौटाया जाना चाहिए। ऐसा करने के लिए, हम ParseBinOpRHS फ़ंक्शन को पैरामीटर "TokPrec + 1" के साथ न्यूनतम प्राथमिकता के रूप में जारी रखने के लिए आवश्यक कॉल करते हैं। हमारे लंबे समय तक पीड़ित उदाहरण में, यह आरटीएच के रूप में "(सी + डी) * ई * एफ" के लिए वापस लौटने के लिए एएसटी नोड का कारण होगा, जो तब '+' के साथ अभिव्यक्ति के लिए सही पक्ष बन जाता है।

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

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

बाकी को पार्स करना

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

 /// prototype /// ::= id '(' id* ')' static PrototypeAST *ParsePrototype() { if (CurTok != tok_identifier) return ErrorP("Expected function name in prototype"); std::string FnName = IdentifierStr; getNextToken(); if (CurTok != '(') return ErrorP("Expected '(' in prototype"); //    . std::vector<std::string> ArgNames; while (getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); if (CurTok != ')') return ErrorP("Expected ')' in prototype"); //  . getNextToken(); //  ')'. return new PrototypeAST(FnName, ArgNames); }

किसी फ़ंक्शन को घोषित करने की सादगी को देखते हुए, फ़ंक्शन के मुख्य भाग में एक प्रोटोटाइप + अभिव्यक्ति शामिल होगी:

 /// definition ::= 'def' prototype expression static FunctionAST *ParseDefinition() { getNextToken(); //  def. PrototypeAST *Proto = ParsePrototype(); if (Proto == 0) return 0; if (ExprAST *E = ParseExpression()) return new FunctionAST(Proto, E); return 0; }

इसके अलावा, आपको "पाप" और "कॉस" जैसे कार्यों को घोषित करने के लिए "बाहरी" समर्थन की आवश्यकता है, और उपयोगकर्ता द्वारा परिभाषित कार्यों की समयपूर्व घोषणा का समर्थन करने के लिए भी। 'बाहरी' में केवल एक शरीर के बिना एक प्रोटोटाइप शामिल होगा:

 /// external ::= 'extern' prototype static PrototypeAST *ParseExtern() { getNextToken(); //  extern. return ParsePrototype(); }

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

 /// toplevelexpr ::= expression static FunctionAST *ParseTopLevelExpr() { if (ExprAST *E = ParseExpression()) { //   . PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); return new FunctionAST(Proto, E); } return 0; }

अब जब हमारे पास सभी भाग हैं, तो हम एक छोटा नियंत्रण कार्यक्रम बनाते हैं जो हमें लिखे गए सभी कोड को आज़माने की अनुमति देता है!

प्रबंधन कार्यक्रम

नियंत्रण कार्यक्रम केवल चक्रीय रूप से पार्सिंग कहता है। यहां कुछ भी दिलचस्प नहीं है, नीचे पूर्ण कोड में "शीर्ष स्तर पार्सिंग" अनुभाग देखें।

 /// top ::= definition | external | expression | ';' static void MainLoop() { while (1) { fprintf(stderr, "ready> "); switch (CurTok) { case tok_eof: return; case ';': getNextToken(); break; //  ';'  . case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; } } }

इस कोड में सबसे दिलचस्प हिस्सा यह है कि हम शीर्ष-स्तरीय अर्धविरामों की उपेक्षा करते हैं। तुम पूछते हो क्यों?मुख्य कारण यह है कि यदि आप कमांड लाइन पर "4 + 5" दर्ज करते हैं, तो पार्सर को पता नहीं है कि यह अंत है, क्या आप पाठ दर्ज करना जारी रखेंगे। उदाहरण के लिए, अगली पंक्ति में, आप "डिफ़ फ़ू ..." दर्ज कर सकते हैं, इस मामले में 4 +5 शीर्ष-स्तरीय अभिव्यक्ति का अंत है, या आप अभिव्यक्ति जारी रखने के लिए "* 6" दर्ज कर सकते हैं। ऊपरी स्तर के अर्धविरामों की उपस्थिति आपको "4 + 5" प्रिंट करने की अनुमति देती है और पार्सर को पता चल जाएगा कि आपका क्या मतलब है।

निष्कर्ष

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

$ ./a.out ready> def foo(xy) x+foo(y, 4.0); Parsed a function definition. ready> def foo(xy) x+yy; Parsed a function definition. Parsed a top-level expr ready> def foo(xy) x+y ); Parsed a function definition. Error: unknown token when expecting an expression ready> extern sin(a); ready> Parsed an extern ready> ^D $

सुधार करने के कई तरीके हैं। आप नए एएसटी नोड्स को परिभाषित कर सकते हैं, कई तरीकों से भाषा का विस्तार कर सकते हैं, आदि। अगले भाग में, हम देखेंगे कि एएसटी से एलएलवीएम इंटरमीडिएट रिप्रेजेंटेशन (आईआर) कैसे उत्पन्न किया जाए।

पूर्ण कोड सूची

यहाँ इस और पिछले अध्याय के लिए कोड की एक पूरी सूची है। ध्यान दें कि कोड पूरी तरह से स्वायत्त है: आपको LLVM या किसी बाहरी लाइब्रेरी की आवश्यकता नहीं है। (छोड़कर, निश्चित रूप से, मानक सी और सी ++ पुस्तकालय)। आप इस कोड को इस तरह संकलित कर सकते हैं:

# g++ -g -O3 toy.cpp # ./a.out

ठीक है, कोड ही:

 #include <cstdio> #include <cstdlib> #include <string> #include <map> #include <vector> //===----------------------------------------------------------------------===// // Lexer ( ) //===----------------------------------------------------------------------===// //     [0-255],   , //       enum Token { tok_eof = -1, //  ( ) tok_def = -2, tok_extern = -3, //  ( : , ) tok_identifier = -4, tok_number = -5 }; static std::string IdentifierStr; // ,  tok_identifier static double NumVal; // ,  tok_number /// gettok -       . static int gettok() { static int LastChar = ' '; //  . while (isspace(LastChar)) LastChar = getchar(); if (isalpha(LastChar)) { // : [a-zA-Z][a-zA-Z0-9]* IdentifierStr = LastChar; while (isalnum((LastChar = getchar()))) IdentifierStr += LastChar; if (IdentifierStr == "def") return tok_def; if (IdentifierStr == "extern") return tok_extern; return tok_identifier; } if (isdigit(LastChar) || LastChar == '.') { // : [0-9.]+ std::string NumStr; do { NumStr += LastChar; LastChar = getchar(); } while (isdigit(LastChar) || LastChar == '.'); NumVal = strtod(NumStr.c_str(), 0); return tok_number; } if (LastChar == '#') { //     do LastChar = getchar(); while (LastChar != EOF && LastChar != '\n' && LastChar != '\r'); if (LastChar != EOF) return gettok(); } //   . if (LastChar == EOF) return tok_eof; //         ASCII int ThisChar = LastChar; LastChar = getchar(); return ThisChar; } //===----------------------------------------------------------------------===// // Abstract Syntax Tree (     ) //===----------------------------------------------------------------------===// /// ExprAST -      . class ExprAST { public: virtual ~ExprAST() {} }; /// NumberExprAST -       (, "1.0"). class NumberExprAST : public ExprAST { double Val; public: NumberExprAST(double val) : Val(val) {} }; /// VariableExprAST -      (, "a"). class VariableExprAST : public ExprAST { std::string Name; public: VariableExprAST(const std::string &name) : Name(name) {} }; /// BinaryExprAST -      . class BinaryExprAST : public ExprAST { char Op; ExprAST *LHS, *RHS; public: BinaryExprAST(char op, ExprAST *lhs, ExprAST *rhs) : Op(op), LHS(lhs), RHS(rhs) {} }; /// CallExprAST -      . class CallExprAST : public ExprAST { std::string Callee; std::vector<ExprAST*> Args; public: CallExprAST(const std::string &callee, std::vector<ExprAST*> &args) : Callee(callee), Args(args) {} }; /// PrototypeAST -    ""  , ///        (,  , ///    ). class PrototypeAST { std::string Name; std::vector<std::string> Args; public: PrototypeAST(const std::string &name, const std::vector<std::string> &args) : Name(name), Args(args) {} }; /// FunctionAST -     class FunctionAST { PrototypeAST *Proto; ExprAST *Body; public: FunctionAST(PrototypeAST *proto, ExprAST *body) : Proto(proto), Body(body) {} }; //===----------------------------------------------------------------------===// // Parser (   ) //===----------------------------------------------------------------------===// /// CurTok/getNextToken -    . CurTok -   /// ,  . getNextToken     ///     CurTok. static int CurTok; static int getNextToken() { return CurTok = gettok(); } /// BinopPrecedence -      static std::map<char, int> BinopPrecedence; /// GetTokPrecedence -     . static int GetTokPrecedence() { if (!isascii(CurTok)) return -1; // ,     . int TokPrec = BinopPrecedence[CurTok]; if (TokPrec <= 0) return -1; return TokPrec; } /// Error* -       . ExprAST *Error(const char *Str) { fprintf(stderr, "Error: %s\n", Str);return 0;} PrototypeAST *ErrorP(const char *Str) { Error(Str); return 0; } FunctionAST *ErrorF(const char *Str) { Error(Str); return 0; } static ExprAST *ParseExpression(); /// identifierexpr /// ::= identifier /// ::= identifier '(' expression* ')' static ExprAST *ParseIdentifierExpr() { std::string IdName = IdentifierStr; getNextToken(); //  . if (CurTok != '(') //  . return new VariableExprAST(IdName); //  . getNextToken(); //  ( std::vector<ExprAST*> Args; if (CurTok != ')') { while (1) { ExprAST *Arg = ParseExpression(); if (!Arg) return 0; Args.push_back(Arg); if (CurTok == ')') break; if (CurTok != ',') return Error("Expected ')' or ',' in argument list"); getNextToken(); } } //  ')'. getNextToken(); return new CallExprAST(IdName, Args); } /// numberexpr ::= number static ExprAST *ParseNumberExpr() { ExprAST *Result = new NumberExprAST(NumVal); getNextToken(); //   return Result; } /// parenexpr ::= '(' expression ')' static ExprAST *ParseParenExpr() { getNextToken(); //  (. ExprAST *V = ParseExpression(); if (!V) return 0; if (CurTok != ')') return Error("expected ')'"); getNextToken(); //  ). return V; } /// primary /// ::= identifierexpr /// ::= numberexpr /// ::= parenexpr static ExprAST *ParsePrimary() { switch (CurTok) { default: return Error("unknown token when expecting an expression"); case tok_identifier: return ParseIdentifierExpr(); case tok_number: return ParseNumberExpr(); case '(': return ParseParenExpr(); } } /// binoprhs /// ::= ('+' primary)* static ExprAST *ParseBinOpRHS(int ExprPrec, ExprAST *LHS) { //    ,    while (1) { int TokPrec = GetTokPrecedence(); //           , //  ,    if (TokPrec < ExprPrec) return LHS; // ,  ,    . int BinOp = CurTok; getNextToken(); // eat binop //       ExprAST *RHS = ParsePrimary(); if (!RHS) return 0; //  BinOp   RHS  ,    RHS, //      RHS  LHS. int NextPrec = GetTokPrecedence(); if (TokPrec < NextPrec) { RHS = ParseBinOpRHS(TokPrec+1, RHS); if (RHS == 0) return 0; } //  LHS/RHS. LHS = new BinaryExprAST(BinOp, LHS, RHS); } } /// expression /// ::= primary binoprhs /// static ExprAST *ParseExpression() { ExprAST *LHS = ParsePrimary(); if (!LHS) return 0; return ParseBinOpRHS(0, LHS); } /// prototype /// ::= id '(' id* ')' static PrototypeAST *ParsePrototype() { if (CurTok != tok_identifier) return ErrorP("Expected function name in prototype"); std::string FnName = IdentifierStr; getNextToken(); if (CurTok != '(') return ErrorP("Expected '(' in prototype"); //    . std::vector<std::string> ArgNames; while (getNextToken() == tok_identifier) ArgNames.push_back(IdentifierStr); if (CurTok != ')') return ErrorP("Expected ')' in prototype"); //  . getNextToken(); //  ')'. return new PrototypeAST(FnName, ArgNames); } /// definition ::= 'def' prototype expression static FunctionAST *ParseDefinition() { getNextToken(); //  def. PrototypeAST *Proto = ParsePrototype(); if (Proto == 0) return 0; if (ExprAST *E = ParseExpression()) return new FunctionAST(Proto, E); return 0; } /// toplevelexpr ::= expression static FunctionAST *ParseTopLevelExpr() { if (ExprAST *E = ParseExpression()) { //   . PrototypeAST *Proto = new PrototypeAST("", std::vector<std::string>()); return new FunctionAST(Proto, E); } return 0; } /// external ::= 'extern' prototype static PrototypeAST *ParseExtern() { getNextToken(); //  extern. return ParsePrototype(); } //===----------------------------------------------------------------------===// // Top-Level parsing (  ) //===----------------------------------------------------------------------===// static void HandleDefinition() { if (ParseDefinition()) { fprintf(stderr, "Parsed a function definition.\n"); } else { //      . getNextToken(); } } static void HandleExtern() { if (ParseExtern()) { fprintf(stderr, "Parsed an extern\n"); } else { //      . getNextToken(); } } static void HandleTopLevelExpression() { //      . if (ParseTopLevelExpr()) { fprintf(stderr, "Parsed a top-level expr\n"); } else { //      . getNextToken(); } } /// top ::= definition | external | expression | ';' static void MainLoop() { while (1) { fprintf(stderr, "ready> "); switch (CurTok) { case tok_eof: return; case ';': getNextToken(); break; //     . case tok_def: HandleDefinition(); break; case tok_extern: HandleExtern(); break; default: HandleTopLevelExpression(); break; } } } //===----------------------------------------------------------------------===// // Main driver code (  ) //===----------------------------------------------------------------------===// int main() { //    . // 1 -  . BinopPrecedence['<'] = 10; BinopPrecedence['+'] = 20; BinopPrecedence['-'] = 20; BinopPrecedence['*'] = 40; // highest. fprintf(stderr, "ready> "); getNextToken(); //    " ". MainLoop(); return 0; }

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

LLVM का उपयोग करके एक प्रोग्रामिंग भाषा बनाना। भाग 2: पार्सर और एएसटी को लागू करना