एक पार्सर बनाना (भाग I)

Question

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

if(x > 5) 
    return true; 

Tokenizer:

T_IF   "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_NUMBER  "5" 
T_RPAREN  ")" 
T_IDENTIFIER "return" 
T_TRUE  "true" 
T_TERMINATOR ";" 

मैं नहीं जानता कि अगर मेरे तर्क सही है इसके लिए थोड़ी देर के लिए। मेरी पार्सर पर यह और भी बेहतर है (या नहीं?) और इसे करने के लिए अनुवाद करते हैं (हाँ, बहुआयामी सरणी):

1. मेरे रास्ते बेहतर या बदतर है कि है:

   T_IF    "if" 
       T_EXPRESSION  ... 
       T_IDENTIFIER  "x" 
       T_GT    ">" 
       T_NUMBER   "5" 
       T_CLOSURE  ... 
       T_IDENTIFIER  "return" 
       T_TRUE   "true" 
   

   मैं कुछ शक है मूल तरीका? ध्यान दें कि मेरा कोड हर समय व्याख्या किए जाने के बजाय, पढ़ा और संकलित किया जाएगा (PHP की तरह किसी अन्य भाषा में अनुवादित)।

2. टोकननाइज़र के बाद, मुझे वास्तव में क्या करना चाहिए? मैं वास्तव में इस पास पर खो गया हूँ!
3. सीखने के लिए कुछ अच्छे ट्यूटोरियल हैं कि मैं इसे कैसे कर सकता हूं?

ठीक है, कि है। अलविदा!

Answer 1

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

तो आपने अपने पात्रों को टोकन में बदल दिया है। अब आप टोकन की अपनी समतल सूची को सार्थक नेस्टेड अभिव्यक्तियों में परिवर्तित करना चाहते हैं, और पारंपरिक रूप से इसे पार्सिंग कहा जाता है। जावास्क्रिप्ट जैसी भाषा के लिए, आपको recursive descent parsing में देखना चाहिए। विभिन्न प्राथमिकता स्तरों के इंफिक्स ऑपरेटरों के साथ अभिव्यक्तियों को पार्स करने के लिए, Pratt parsing बहुत उपयोगी है, और आप विशेष मामलों के लिए सामान्य रिकर्सिव वंश पार्सिंग पर वापस आ सकते हैं।

बस आपको अपने मामले के आधार पर एक और ठोस उदाहरण देने के लिए, मुझे लगता है कि आप दो कार्य लिख सकते हैं: accept(token) और expect(token), जो आपके द्वारा बनाई गई स्ट्रीम में अगले टोकन का परीक्षण करता है। आप अपनी भाषा के व्याकरण में प्रत्येक प्रकार के कथन या अभिव्यक्ति के लिए एक फ़ंक्शन करेंगे। यहाँ एक statement() समारोह के लिए Pythonish स्यूडोकोड है, उदाहरण के लिए:

def statement(): 

    if accept("if"): 
    x = expression() 
    y = statement() 
    return IfStatement(x, y) 

    elif accept("return"): 
    x = expression() 
    return ReturnStatement(x) 

    elif accept("{") 
    xs = [] 
    while True: 
     xs.append(statement()) 
     if not accept(";"): 
     break 
    expect("}") 
    return Block(xs) 

    else: 
    error("Invalid statement!") 

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

Answer 2

क्या मेरा तरीका बेहतर है या खराब है मूल तरीका? ध्यान दें कि मेरा कोड हर समय व्याख्या किए जाने के बजाय, पढ़ा और संकलित किया जाएगा (PHP की तरह किसी अन्य भाषा में अनुवादित)।

मूल तरीका क्या है? भाषाओं को लागू करने के कई अलग-अलग तरीके हैं। मुझे लगता है कि आपका वास्तव में ठीक है, मैंने एक बार अपनी भाषा बनाने की कोशिश की जो सी #, hack programming language में अनुवाद किया गया। कई भाषा संकलक एक मध्यवर्ती भाषा में अनुवाद करते हैं, यह काफी आम है।

I टोकनेज़र के बाद, मुझे वास्तव में क्या करना चाहिए? मैं वास्तव में इस पास पर खो गया हूँ!

टोकनिंग के बाद, आपको पार्स की आवश्यकता है। कुछ अच्छे लेक्सर/पार्सर फ्रेमवर्क का उपयोग करें, जैसे Boost.Spirit, या कोको, या जो भी हो। उनमें से सैकड़ों हैं। या आप अपना खुद का लेजर लागू कर सकते हैं, लेकिन इसमें समय और संसाधन लगते हैं। कोड पार्स करने के कई तरीके हैं, मैं आम तौर पर recursive descent parsing पर भरोसा करता हूं।

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

सीखने के लिए कुछ अच्छे ट्यूटोरियल हैं कि मैं इसे कैसे कर सकता हूं?

जैसा कि मैंने पहले सुझाव दिया था, इसे करने के लिए उपकरण का उपयोग करें। बहुत अच्छे अच्छे दस्तावेज वाले पार्सर फ्रेमवर्क हैं।अधिक जानकारी के लिए, आप कुछ लोगों से पूछने का प्रयास कर सकते हैं जो इस सामान के बारे में जानते हैं। 0D35Mपर @DeadMG, "वाइड" नामक प्रोग्रामिंग भाषा का निर्माण कर रहा है। आप उससे परामर्श करने की कोशिश कर सकते हैं।

Answer 3

अधिकांश उपकरणकिटें दो अलग भागों

में पूरी प्रक्रिया को विभाजित

• lexer (उर्फ। Tokenizer)
• पार्सर (उर्फ। व्याकरण)

tokenizer इनपुट डेटा विभाजित कर देगा टोकन में पार्सर केवल टोकन "स्ट्रीम" पर काम करेगा और संरचना का निर्माण करेगा।

आपका प्रश्न टोकनज़र पर केंद्रित होना प्रतीत होता है। लेकिन आपका दूसरा समाधान व्याकरण पार्सर और टोकननाइज़र को एक चरण में मिलाता है। सैद्धांतिक रूप से यह भी संभव है लेकिन शुरुआत के लिए यह है इसे अन्य टूल/ढांचे के समान ही करना आसान है: चरणों को अलग रखें।

अपने पहले समाधान करने के लिए

: मैं इस तरह अपने उदाहरण tokenize होगा:

T_KEYWORD_IF "if" 
T_LPAREN  "(" 
T_IDENTIFIER "x" 
T_GT   ">" 
T_LITARAL  "5" 
T_RPAREN  ")" 
T_KEYWORD_RET "return" 
T_KEYWORD_TRUE "true" 
T_TERMINATOR ";" 

सबसे अधिक भाषाओं कीवर्ड में विधि के नाम, चर नाम और इतने पर के रूप में इस्तेमाल नहीं किया जा सकता। यह पहले से टोकनिज़र स्तर पर दिखाई देता है (T_KEYWORD_IF, T_KEYWORD_RET, T_KEYWORD_TRUE)।

अगले स्तर इस धारा ले जाएगा और - एक औपचारिक व्याकरण लगाने से - कुछ आंकड़ा संरचना का निर्माण होगा (अक्सर कहा जाता AST - सार सिंटेक्स ट्री) जो इस प्रकार दिखाई देंगे:

IfStatement: 
    Expression: 
     BinaryOperator: 
      Operator:  T_GT 
      LeftOperand: 
       IdentifierExpression: 
        "x" 
      RightOperand: 
       LiteralExpression 
        5 
    IfBlock 
     ReturnStatement 
      ReturnExpression 
       LiteralExpression 
        "true" 
    ElseBlock (empty) 

हाथ से पार्सर को लागू करने आमतौर पर कुछ ढांचे द्वारा किया जाता है।हाथ से कुछ ऐसा कार्यान्वित करना और आमतौर पर एक सेमेस्टर के बेहतर हिस्से में एक विश्वविद्यालय में कुशलता से किया जाता है। तो आपको वास्तव में कुछ प्रकार के ढांचे का उपयोग करना चाहिए।

व्याकरण पार्सर ढांचे के लिए इनपुट आमतौर पर किसी प्रकार के BNF में औपचारिक व्याकरण होता है। आपका "अगर" भाग माई इस तरह दिखता है:

IfStatement: T_KEYWORD_IF T_LPAREN Expression T_RPAREN Statement ; 

Expression: LiteralExpression | BinaryExpression | IdentifierExpression | ... ; 

BinaryExpression: LeftOperand BinaryOperator RightOperand; 

.... 

यह केवल विचार प्राप्त करने के लिए है। जावास्क्रिप्ट जैसे रीयलवर्ल्ड-भाषा को सही ढंग से पार्स करना एक आसान काम नहीं है। लेकिन मज़ेदार।