Stoffle भाषा के लिए Ruby इंटरप्रेटर बनाना

GitHub पर पूर्ण स्रोत

Stoffle प्रोग्रामिंग भाषा का एक पूर्ण कार्यान्वयन GitHub पर उपलब्ध है। यदि आपको बग मिलते हैं या आपके कोई प्रश्न हैं तो बेझिझक एक इश्यू खोलें।

इस ब्लॉग पोस्ट में, हम Stoffle के लिए इंटरप्रेटर को लागू करना शुरू करने जा रहे हैं, एक खिलौना प्रोग्रामिंग भाषा जिसे पूरी तरह से Ruby में बनाया गया है। आप इस प्रोजेक्ट के बारे में इस श्रृंखला के पहले भाग में अधिक पढ़ सकते हैं।

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

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

लेक्सर और पार्सर का त्वरित सारांश

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

स्टेट 0: स्रोत

my_var = 1 

स्टेट 1: लेक्सर कच्चे स्रोत कोड को टोकन्स में बदलता है

[:identifier, :'=', :number] 

स्टेट 2: पार्सर टोकन्स को एब्सट्रैक्ट सिंटैक्स ट्री में बदलता है

यह सब वॉकिंग के बारे में है

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

जैसा कि हमने इस श्रृंखला के पिछले भागों में किया था, हम सभी महत्वपूर्ण कोड लाइन्स से गुजरकर कार्यान्वयन का पता लगाने जा रहे हैं जो एक उदाहरण प्रोग्राम को संभालने में शामिल हैं। Stoffle कोड का वह टुकड़ा जिसे हमें इंटरप्रेट करना है, वह निम्नलिखित है:

num = -2
if num > 0
  println("The number is greater than zero.")
else
  println("The number is less than or equal to zero.")
end 

यह उसी प्रोग्राम के लिए उत्पादित AST है:

हमारे वॉक में पहला कदम

जैसा कि आप शायद इस श्रृंखला के अंतिम पोस्ट से याद करते हैं, एक Stoffle AST की जड़ हमेशा एक AST::Program नोड होती है। इस रूट में आमतौर पर कई बच्चे होते हैं। उनमें से कुछ उथले होंगे (एक साधारण वेरिएबल असाइनमेंट के लिए उत्पादित AST के बारे में सोचें)। अन्य बच्चे काफी गहरे सबट्रीज की जड़ हो सकते हैं (एक लूप के बारे में सोचें जिसके बॉडी के अंदर कई लाइनें हैं)। यह वह Ruby कोड है जिसकी हमें अपने इंटरप्रेटर को पास किए गए AST के माध्यम से चलना शुरू करने के लिए आवश्यकता है:

module Stoffle
  class Interpreter
    attr_reader :program, :output, :env
    def initialize
      @output = []
      @env = {}
    end
    def interpret(ast)
      @program = ast
      interpret_nodes(program.expressions)
    end
    private
    def interpret_nodes(nodes)
      last_value = nil
      nodes.each do |node|
        last_value = interpret_node(node)
      end
      last_value
    end
    def interpret_node(node)
      interpreter_method = "interpret_#{node.type}"
      send(interpreter_method, node)
    end
    #...
  end
end 

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

#interpret_nodes मेथड रूट नोड (AST::Program) के सभी बच्चों के माध्यम से लूप करता है। फिर, यह प्रत्येक व्यक्तिगत नोड के लिए #interpret_node कॉल करता है।

#interpret_node सरल है लेकिन फिर भी दिलचस्प। यहां, हम वर्तमान में हाथ में नोड प्रकार को संभालने के लिए उपयुक्त मेथड को कॉल करने के लिए थोड़ा Ruby मेटाप्रोग्रामिंग उपयोग करते हैं। उदाहरण के लिए, एक AST::VarBinding नोड के लिए, #interpret_var_binding मेथड वह है जो कॉल किया जाता है।

अनिवार्य रूप से, हमें वेरिएबल्स के बारे में बात करनी है

उदाहरण प्रोग्राम के AST में हमें इंटरप्रेट करने वाला पहला नोड एक AST::VarBinding है। इसका @left एक AST::Identifier है, और इसका @right एक AST::UnaryOperator है। आइए वेरिएबल बाइंडिंग को इंटरप्रेट करने के लिए जिम्मेदार मेथड पर एक नज़र डालें:

def interpret_var_binding(var_binding)
  env[var_binding.var_name_as_str] = interpret_node(var_binding.right)
end 

जैसा कि आप देख सकते हैं, यह बहुत सीधा है। हम @env हैश में एक की-वैल्यू जोड़ी जोड़ते हैं (या ओवरराइट करते हैं)।

कुंजी वेरिएबल का नाम है (#var_name_as_str सिर्फ एक हेल्पर मेथड है जो var_binding.left.name के समतुल्य है)। इस समय, सभी वेरिएबल्स ग्लोबल हैं। हम अगले पोस्ट में स्कोपिंग को संभालेंगे।

मान असाइनमेंट के दाएं पक्ष पर एक्सप्रेशन को इंटरप्रेट करने का परिणाम है। ऐसा करने के लिए, हम फिर से #interpret_node का उपयोग करते हैं। चूंकि दाएं पक्ष पर हमारे पास एक AST::UnaryOperator है, अगला मेथड जो कॉल किया जाता है वह #interpret_unary_operator है:

def interpret_unary_operator(unary_op)
  case unary_op.operator
  when :'-'
    -(interpret_node(unary_op.operand))
  else # :'!'
    !(interpret_node(unary_op.operand))
  end
end 

Stoffle के समर्थित यूनरी ऑपरेटर्स (- और !) की सेमेंटिक्स Ruby के समान हैं। परिणामस्वरूप, कार्यान्वयन सरल नहीं हो सकता: हम ऑपरेंड को इंटरप्रेट करने के परिणाम पर Ruby के - ऑपरेटर को लागू करते हैं। हमारा पुराना परिचित संदिग्ध, #interpret_node, यहां फिर से प्रकट होता है। जैसा कि आप हमारे प्रोग्राम के AST से याद कर सकते हैं, - के लिए ऑपरेंड एक AST::Number है (संख्या 2)। इसका मतलब है कि हमारा अगला पड़ाव #interpret_number पर है:

def interpret_number(number)
  number.value
end 

#interpret_number का कार्यान्वयन एकदम आसान है। नंबर लिटरल्स के प्रतिनिधित्व के रूप में Ruby फ्लोट को अपनाने का हमारा निर्णय (यह लेक्सर में होता है!) यहां फल देता है। AST::Number नोड का @value पहले से ही संख्याओं के हमारे वांछित आंतरिक प्रतिनिधित्व को धारण करता है, इसलिए हम बस इसे पुनः प्राप्त करते हैं।

इसके साथ, हम AST::Program के पहले डायरेक्ट चाइल्ड को इंटरप्रेट करना समाप्त करते हैं। अब, हमारे प्रोग्राम को इंटरप्रेट करना समाप्त करने के लिए, हमें इसके अन्य, अधिक बालों वाले चाइल्ड को संभालना होगा: AST::Conditional प्रकार का एक नोड।

शर्तें लागू होती हैं

#interpret_nodes में वापस, हमारा सबसे अच्छा दोस्त #interpret_node AST::Program के अगले डायरेक्ट चाइल्ड को इंटरप्रेट करने के लिए फिर से कॉल किया जाता है।

def interpret_nodes(nodes)
  last_value = nil
  nodes.each do |node|
    last_value = interpret_node(node)
  end
  last_value
end 

AST::Conditional को इंटरप्रेट करने के लिए जिम्मेदार मेथड #interpret_conditional है। इसे देखने से पहले, हालांकि, आइए AST::Conditional के कार्यान्वयन की समीक्षा करके अपनी याददाश्त ताज़ा करें:

class Stoffle::AST::Conditional < Stoffle::AST::Expression
  attr_accessor :condition, :when_true, :when_false
  def initialize(cond_expr = nil, true_block = nil, false_block = nil)
    @condition = cond_expr
    @when_true = true_block
    @when_false = false_block
  end
  def ==(other)
    children == other&.children
  end
  def children
    [condition, when_true, when_false]
  end
end 

ठीक है, तो @condition एक एक्सप्रेशन रखता है जो या तो ट्रूथी या फाल्सी होगा; @when_true एक ब्लॉक रखता है जिसमें एक या अधिक एक्सप्रेशन्स होते हैं जिन्हें निष्पादित किया जाता है यदि @condition ट्रूथी है, और @when_false (ELSE क्लॉज) उस ब्लॉक को रखता है जिसे चलाया जाता है यदि @condition फाल्सी होता है।

अब, आइए #interpret_conditional पर एक नज़र डालें:

def interpret_conditional(conditional)
  evaluated_cond = interpret_node(conditional.condition)
  # हम नीचे की लाइन को छोटे तरीके से लागू कर सकते थे, लेकिन Stoffle में ट्रूथीनेस के बारे में स्पष्ट होना बेहतर है।
  if evaluated_cond == nil || evaluated_cond == false
    return nil if conditional.when_false.nil?
    interpret_nodes(conditional.when_false.expressions)
  else
    interpret_nodes(conditional.when_true.expressions)
  end
end 

Stoffle में ट्रूथीनेस Ruby के समान है। दूसरे शब्दों में, Stoffle में, केवल nil और false फाल्सी हैं। किसी अन्य इनपुट को कंडीशन में ट्रूथी माना जाता है।

हम पहले conditional.condition द्वारा रखे गए एक्सप्रेशन को इंटरप्रेट करके कंडीशन का मूल्यांकन करते हैं। आइए हमारे प्रोग्राम के AST को फिर से देखें ताकि यह पता लगाया जा सके कि हम किस नोड से निपट रहे हैं:

बात यह है कि हमारे पास एक AST::BinaryOperator है (num > 0 में उपयोग किया गया >)। ठीक है, यह वही रास्ता फिर से: पहले #interpret_node, जो इस बार #interpret_binary_operator को कॉल करता है:

def interpret_binary_operator(binary_op)
  case binary_op.operator
  when :and
    interpret_node(binary_op.left) && interpret_node(binary_op.right)
  when :or
    interpret_node(binary_op.left) || interpret_node(binary_op.right)
  else
    interpret_node(binary_op.left).send(binary_op.operator, interpret_node(binary_op.right))
  end
end 

हमारे लॉजिकल ऑपरेटर्स (and और or) को बाइनरी ऑपरेटर्स माना जा सकता है, इसलिए हम उन्हें यहां भी संभालते हैं। चूंकि उनकी सेमेंटिक्स Ruby के && और || के समतुल्य हैं, कार्यान्वयन स्पष्ट है, जैसा कि आप ऊपर देख सकते हैं।

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

-2 > 0 # है समतुल्य -2.send(:'>', 0) # यह
# और निम्न लाइन एक सामान्य समाधान होगा,
# हमारे इंटरप्रेटर में जो हमारे पास है उसके बहुत समान
operand_1.send(binary_operator, operand_2) 

बाइनरी ऑपरेटर्स का एक वर्बोज कार्यान्वयन

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

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

# ... #interpret_binary_operator के अंदर ...
case binary_op.operator
when :'+'
  interpret_node(binary_op.left) + interpret_node(binary_op.right)
# ... अन्य ऑपरेटर्स
end 

#interpret_conditional पर वापस जाने से पहले, आइए एक त्वरित चक्कर लगाएं ताकि यह सुनिश्चित हो सके कि कुछ भी छूटा नहीं है। यदि आप याद करते हैं कि हम जिस प्रोग्राम को इंटरप्रेट कर रहे हैं, num वेरिएबल का उपयोग उस तुलना में किया जाता है (बाइनरी ऑपरेटर > का उपयोग करके) जिसे हमने अभी एक साथ एक्सप्लोर किया। हम उस तुलना के बाएं ऑपरेंड (यानी, num वेरिएबल में संग्रहीत मान) को कैसे पुनः प्राप्त करते हैं? इसके लिए जिम्मेदार मेथड #interpret_identifier है, और इसका कार्यान्वयन आसान है:

def interpret_identifier(identifier)
  if env.has_key?(identifier.name)
    env[identifier.name]
  else
    # अपरिभाषित वेरिएबल।
    raise Stoffle::Error::Runtime::UndefinedVariable.new(identifier.name)
  end
end 

अब, #interpret_conditional पर वापस। हमारे छोटे प्रोग्राम के मामले में, कंडीशन का मूल्यांकन Ruby false मान में हुआ। हम इस मान का उपयोग यह निर्धारित करने के लिए करते हैं कि हमें कंडीशनल स्ट्रक्चर के IF या ELSE ब्रांच को निष्पादित करना है। हम ELSE ब्रांच को इंटरप्रेट करने के लिए आगे बढ़ते हैं, जिसका संबंधित कोड ब्लॉक conditional.when_false में संग्रहीत है। यहां, हमारे पास एक AST::Block है, जो हमारे AST के रूट नोड (AST::Program) के बहुत समान है। ब्लॉक, इसी तरह, संभावित रूप से कई एक्सप्रेशन्स रखता है जिन्हें इंटरप्रेट करने की आवश्यकता होती है। इस उद्देश्य के लिए, हम #interpret_nodes का भी उपयोग करते हैं।

def interpret_conditional(conditional)
  evaluated_cond = interpret_node(conditional.condition)
  # हम नीचे की लाइन को छोटे तरीके से लागू कर सकते थे, लेकिन Stoffle में ट्रूथीनेस के बारे में स्पष्ट होना बेहतर है।
  if evaluated_cond == nil || evaluated_cond == false
    return nil if conditional.when_false.nil?
    interpret_nodes(conditional.when_false.expressions)
  else
    interpret_nodes(conditional.when_true.expressions)
  end
end 

अब हमें जिस अगले AST नोड को संभालना है वह एक AST::FunctionCall है। फंक्शन कॉल को इंटरप्रेट करने के लिए जिम्मेदार मेथड #interpret_function_call है:

def interpret_function_call(fn_call)
  return if println(fn_call)
end 

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

def println(fn_call)
  return false if fn_call.function_name_as_str != 'println'
  result = interpret_node(fn_call.args.first).to_s
  output << result
  puts result
  true
end 

हमारे AST::FunctionCall का पहला और एकमात्र आर्गुमेंट एक AST::String है, जिसे #interpret_string द्वारा संभाला जाता है:

def interpret_string(string)
  string.value
end 

#interpret_string में, हमारे पास #interpret_number का सटीक समान मामला है। एक AST::String पहले से ही एक उपयोग-के-लिए-तैयार Ruby स्ट्रिंग मान रखता है, इसलिए हमें बस इसे पुनः प्राप्त करना होगा।

अब, #println पर वापस:

def println(fn_call)
  return false if fn_call.function_name_as_str != 'println'
  result = interpret_node(fn_call.args.first).to_s
  output << result
  puts result
  true
end 

फंक्शन आर्गुमेंट (Ruby स्ट्रिंग में परिवर्तित) को result में संग्रहीत करने के बाद, हमारे पास पूरा करने के लिए दो और चरण हैं। पहला, हम जो कंसोल पर प्रिंट करने वाले हैं उसे @output में संग्रहीत करते हैं। जैसा कि पहले समझाया गया है, यहां विचार यह है कि क्या प्रिंट किया गया था (और किस क्रम में) आसानी से इंस्पेक्ट करने में सक्षम होना। डिबगिंग या इंटरप्रेटर टेस्ट करते समय यह हमारे जीवन को आसान बनाता है। अंत में, कंसोल पर कुछ प्रिंट करने को लागू करने के लिए, हम Ruby के puts का उपयोग करते हैं।

निष्पादन मायने रखता है

अब जब हमने Stoffle के बेयर-बोन्स को लागू करने के लिए आवश्यक सब कुछ एक्सप्लोर कर लिया है, तो आइए हमारे इंटरप्रेटर को क्रिया में देखने के लिए एक बहुत ही बेसिक एक्जीक्यूटेबल बनाएं।

#!/usr/bin/env ruby
require_relative '../lib/stoffle'
path = ARGV[0]
source = File.read(path)
lexer = Stoffle::Lexer.new(source)
parser = Stoffle::Parser.new(lexer.start_tokenization)
interpreter = Stoffle::Interpreter.new
interpreter.interpret(parser.parse)
exit(0) 

टिप: Stoffle के इंटरप्रेटर को कहीं से भी उपयोग करने के लिए, एक्जीक्यूटेबल को अपने PATH में जोड़ना याद रखें।

आखिरकार हमारे प्रोग्राम को चलाने का समय आ गया है। यदि सब कुछ ठीक काम करता है, तो हमें स्ट्रिंग "The number is less than or equal to zero" कंसोल पर प्रिंट होती देखनी चाहिए। जब हम इंटरप्रेटर चलाते हैं तो वास्तव में यही होता है:

टिप: यदि आपके पास इंटरप्रेटर इंस्टॉल है, तो हमारे सैंपल प्रोग्राम में num वेरिएबल को बदलने का प्रयास करें ताकि यह शून्य से बड़ी संख्या रखे। अपेक्षित रूप से, अब IF ब्रांच निष्पादित होगी, और स्ट्रिंग "The number is greater than zero" प्रिंट होगी।

समापन

इस पोस्ट में, हमने Stoffle के इंटरप्रेटर की शुरुआत देखी। हमने इंटरप्रेटर का इतना हिस्सा लागू किया कि यह भाषा की कुछ बुनियादी बातों को संभाल सके: वेरिएबल्स, कंडीशनल्स, यूनरी और बाइनरी ऑपरेटर्स, डेटा प्रकार, और कंसोल पर प्रिंटिंग। इंटरप्रेटर पर अगले और अंतिम भाग में, हम अपने छोटे खिलौना भाषा को डिज़ाइन के अनुसार काम करने के लिए आवश्यक शेष बिट्स से निपटेंगे: वेरिएबल स्कोपिंग, फंक्शन परिभाषा, फंक्शन कॉलिंग, और लूप्स। मुझे आशा है कि आपको लेख पढ़ने में मज़ा आया (मैंने निश्चित रूप से इसे लिखने में मज़ा लिया!), और हम जल्द ही इस श्रृंखला के अगले पोस्ट में मिलेंगे!