গিটহাবে ফুল সোর্স
Stoffle প্রোগ্রামিং ল্যাঙ্গুয়েজের সম্পূর্ণ ইমপ্লিমেন্টেশন GitHub-এ উপলব্ধ। এই রেফারেন্স ইমপ্লিমেন্টেশনে কোড পড়া সহজ করার জন্য প্রচুর কমেন্ট রয়েছে। বাগ পেলে বা প্রশ্ন থাকলে ইস্যু খুলতে মিরুন।
এই ব্লগ পোস্টে, আমরা Stoffle-এর পার্সার ইমপ্লিমেন্ট করব, একটি টয় প্রোগ্রামিং ল্যাঙ্গুয়েজ যা সম্পূর্ণরূপে রুবিতে তৈরি। এই প্রজেক্ট সম্পর্কে আরও জানতে এই সিরিজের প্রথম পার্ট পড়ুন।
স্ক্র্যাচ থেকে পার্সার বানাতে আমাকে কিছু অনাকাঙ্ক্ষিত অন্তর্দৃষ্টি এবং জ্ঞান দিয়েছে। আমি মনে করি এই অভিজ্ঞতা ব্যক্তি থেকে فردে ভিন্ন হতে পারে, কিন্তু আমি নিশ্চিতভাবে অনুমান করতে পারি এই আর্টিকেল পড়ার পর, আপনি কমপক্ষে নিচের একটি বিষয়ে আপনার জ্ঞান অর্জন বা গভীর করবেন:
- আপনি সোর্স কোডকে ভিন্ন দৃষ্টি থেকে দেখতে শুরু করবেন এবং এর অসন্দেহ্য ট্রি-লাইক স্ট্রাকচার আরও সহজে লক্ষ্য করবেন;
- আপনি সিনট্যাকটিক শुगर-র সম্পর্কে গভীর বোঝাপড়া পাবেন এবং এটা সব জায়গায় দেখতে শুরু করবেন — Stoffle-এ, রুবিতে, অথবা অন্যান্য প্রোগ্রামিং ল্যাঙ্গুয়েজেও।
আমি মনে করি একটি পার্সার পারেটো প্রিন্সিপালের একটা পরফেক্ট উদাহরণ। কিছু এক্সট্রা-নাইস ফিচার, যেমন অসাধারণ এরর মেসেজ, তৈরির জন্য যা লাগে সেটা বেসিক চলে আনোর চেয়ে নিশ্চিতভাবেই বেশি এবং ডিসপ্রপোরশনেট। আমরা এসেনশিয়ালগুলোর ওপর ফোকাস করব এবং উন্নতিগুলো আপনার হাতে ছেড়ে দিচ্ছি, প্রিয় পাঠক। আমরা এই সিরিজের পরবর্তী আর্টিকেলে কিছু আরো ইন্ড্রেস্টিং এক্স্ট্রা হ্যান্ডল করব বা নাও করব।
সিনট্যাকটিক শুগার
সিনট্যাকটিক শুগার হলো এমন কনস্ট্রাক্টগুলকে বোঝাতে ব্যবহৃত এক্সপ্রেশন যা একটি ল্যাঙ্গুয়েজকে ব্যবহার করা সহজ করে, কিন্তু যেগুলো রিমুভ করলে প্রোগ্রামিং ল্যাঙ্গুয়েজটি ফাংশনালিটি হারাবে না। একটি চমৎকার উদাহরণ রুবির
elsifকনস্ট্রাক্ট। Stoffle-এ আমাদের এতকিছু স্ট্রাকচার নেই, তাই একই কিছু এক্সপ্রেস করার জন্য আমাদের বেশি ভার্বোজ হতে হয়:if some_condition # ... else # oops, no elsif available if another_condition # ... end end
পার্সার কী?
আমরা শুরু করি সোর্স কোড দিয়ে, ক্যারেক্টরের একটি কাঁচা সিকোয়েন্স। তারপর, যেন এই সিরিজের পূর্ববর্তী আর্টিকেলে দেখানো হয়েছে, লেক্সার এই ক্যারেক্টরগুলোকে সেনসিবল ডেটা স্ট্রাকচারে গ্রুপ করে যা টোকেন বলে। কিন্তু আমাদের কাছে এখনও ডেটা আছে যা সম্পূর্ণ ফ্ল্যাট, এমন কিছু যা এখনও সোর্স কোডের নেস্টেড প্রকৃতি উপযুক্তভাবে রিপ্রেজেন্ট করে না। এইভাবে, পার্সারের কাজ হয় এই ক্যারেক্টর সিকোয়েন্স থেকে একটি ট্রি তৈরি করা। যখন এটি তার কাজ শেষ করে, আমরা এমন ডেটা পাবো যা এখনো সক্ষম আমাদের প্রোগ্রামের প্রতিটি অংশ কীভাবে একে অপরের সাথে নেস্ট এবং রিলেট করে সেটা এক্সপ্রেস করতে।
পার্সার দ্বারা তৈরি ট্রি সাধারণত অাবস্ট্রাক্ট সিনট্যাক্স ট্রি (AST) বলে। নামটি ইঙ্গিত দিচ্ছে আমরা একটি ট্রি ডেটা স্ট্রাকচারের সাথে ডাল করছি, যার রুট প্রোগ্রামটিকে রিপ্রেজেন্ট করে এবং এই প্রোগ্রাম নোডের চাইল্ডরা প্রোগ্রামটি গঠন করে এমন অনেক এক্সপ্রেশন। AST-র অবস্ট্রাক্ট শব্দটি আমাদের সক্ষমতাকে বোঝায় যে আমরা অবস্ট্রাক্ট করতে পারি সেই অংশগুলোকে যেগুলো পূর্বের স্টেপে এক্সপ্লিসিটলি উপস্থিত ছিল। এক্সপ্রেশন টার্মিনেটর (Stoffle-এ নিউ লাইন) একটি ভালো উদাহরণ; AST বানানোর সময় সেগুলো বিবেচনা করা হয়, কিন্তু টার্মিনেটর রিপ্রেজেন্ট করার জন্য আমাদের কোনো নির্দিষ্ট নোড টাইপ দরকার নেই। কিন্তু মনে রাখবেন, আমাদের টার্মিনেটর রিপ্রেজেন্ট করার জন্য একটি এক্সপ্লিসিট টোকেন ছিল।
একটি উদাহরণ AST-র ভিজ্যুয়ালাইজেশন থাকলে কি উপকারী হতো? আপনার ইচ্ছা হুকুম! নিচে একটি সিম্পল Stoffle প্রোগ্রাম, যা আমরা এই পোস্টে স্টেপ-বাই-স্টেপ পার্স করব, এবং এর সংশ্লিষ্ট অ্যাবস্ট্রাক্ট সিনট্যাক্স ট্রি:
fn double: num num * 2 end 
সোর্স থেকে AST, একটি ফার্স্ট উদাহরণ
এই সেকশনে, আমরা স্টেপ-বাই-স্টেপ এক্সপ্লোর করব কীভাবে আমাদের পার্সার একটি খুব সিম্পল Stoffle প্রোগ্রাম হ্যান্ডেল করে, যা একটি সিংগল লাইন से बना যেখানে একটি ভেরিয়েবল বাইন্ডিং এক্সপ্রেস করা হয়েছে (অর্থাৎ, আমরা একটি ভেরিয়েবলে ভ্যালু অ্যাসাইন করছি)। এখানে সোর্স, লেক্সারের আউটপুটের একটি সিম্প্লিফাইড রিপ্রেজেন্টেশন (এই টোকেনগুলো হলো আমাদের পার্সারের ইনপুট) এবং শেষে, পার্সারের আউটপুটের একটি ভিজ্যুয়াল রিপ্রেজেন্টেশন (এন অ্যাবস্ট্রাক্ট সিনট্যাক্স ট্রি) যা প্রোগ্রামটি রিপ্রেজেন্ট করবে:
সোর্স
my_var = 1 টোকেনস (লেক্সারের আউটপুট, পার্সারের ইনপুট)
[:identifier, :'=', :number] পার্সারের আউটপুটের ভিজ্যুয়াল রিপ্রেজেন্টেশন (এন অ্যাবস্ট্রাক্ট সিনট্যাক্স ট্রি)
আপনি কল্পনা করতে পারেন, আমাদের পার্সার কর কোড আমাদের লেক্সারের কর কোডের খুব সাদৃশ্য। লেক্সারের কেসে, আমাদের প্রসেস করার জন্য ক্যারেক্টারগুলো ছিল। এখনও, আমাদের এখনও একটি কালেকশন ওভার ইটারেট করতে হচ্ছে, কিন্তু পার্সারের কেসে, আমরা আমাদের লেক্সার বন্ধু द्वारा প্রডিউস করা টোকেনের লিস্ট ওভার যাব। আমাদের একটি সিংগল পয়েন্টার (@next_p) রয়েছে আমাদের টোকেন কালেকশনে পজিশন ট্র্যাক রাখতে। এই পয়েন্টার নেক্সট টোকেনকে মার্ক করে যা প্রসেস হবে। যদিও আমাদের শুধু এই একটা পয়েন্টার রয়েছে, আমাদের 필요 অনুযায়ী অনেক অন্যান্য "ভার্চুয়াল" পয়েন্টার রয়েছে যেগুলো আমরা ফরওয়ার্ড যাওয়ার সাথে সাথে দেখব। এমন একটি "ভার্চুয়াল" পয়েন্টার হলো current (বেসিক্যালি, @next_p - 1 পজিশনের টোকেন)।
#parse হলো কল করার মেথড যাতে টোকেনগুলো AST-এ রূপান্তরিত হয়, যা @ast ইনস্ট্যান্স ভেরিয়েবলে উপলব্ধ থাকবে। #parse-র ইমপ্লিমেন্টেশন স্ট্রেইটফরওয়ার্ড। আমরা #consume কল করে এবং @next_p মুভ করে কালেকশন থ্রু এডভান্স করতে থাকি যতক্ষণ না প্রসেস করার জন্য আর কোনো টোকেন থাকে না (অর্থাৎ, যতক্ষণ next_p < tokens.length)। #parse_expr_recursively একটি AST নোড রিটার্ন করতে পারে বা কিছুই নাও। মনে রাখবেন, আমাদের টার্মিনেটরগুলোকে AST-এ রিপ্রেজেন্ট করার দরকার নেই, উদাহরণস্বরূপ। যদি বর্তমান ইটারেশনে একটি নোড তৈরি হয়, তবে আমরা এটাকে @ast-এ যোগ করি আগামি চালু রাখার আগে। মনে রাখা গুরুত্বপূর্ণ যে #parse_expr_recursively ও @next_p মুভ করছে, কারণ যখন আমরা একটি টোকেন পাই যা একটি নির্দিষ্ট কনস্ট্রাক্টের শুরু বোঝায়, আমাদের একাধিকবার এডভান্স করতে হয় যতক্ষণ না আমরা সেটা ফুলি রিপ্রেজেন্ট করার নোড তৈরি করতে পারি। কল্পনা করুন একটি if রিপ্রেজেন্ট করার নোড বানাতে কত টোকেন কনসাম করতে হবে।
module Stoffle class Parser attr_accessor :tokens, :ast, :errors # ... def initialize(tokens) @tokens = tokens @ast = AST::Program.new @next_p = 0 @errors = [] end def parse while pending_tokens? consume node = parse_expr_recursively ast << node if node != nil end end # ... end end উপরোক্ত স্নিপেটে, প্রথমবার আমাদের পার্সার ইমপ্লিমেন্টেশনের অংশবিশেষ অনেক প্রকার AST নোড টাইপের সাথে পরিচিত হয়েছি। নিচে, আমাদের AST::Program নোড টাইপের ফুল সোর্স কোড রয়েছে। আপনি অনুমান করতে পারছেন, এটি আমাদের ট্রির রুট, পুরো প্রোগ্রামকে রিপ্রেজেন্ট করে। এর সবচেয়ে ইন্ড্রেস্টিং অংশগুলো এক্সপ্লোর করি:
- একটি Stoffle প্রোগ্রাম koost হয়
@expressions-এর মাধ্যমে; এগুলোAST::Programনোডের#children; - আপনি আবার দেখবেন, প্রতিটি নোড টাইপ
#==মেথড ইমপ্লিমেন্ট করে। ফলস্বরূপ, দুটি সিম্পল নোড, এবং পুরো প্রোগ্রামগুলো একসাথে কমপেয়ার করা খুব সহজ! দুটি প্রোগ্রাম (বা দুটি কমপ্লেক্স নোড) কমপেয়ার করার সময়, তাদের ইকুয়ালিটি নির্ধারিত হবে সকল চাইল্ডের ইকুয়ালিটি, সকল চাইল্ডের সকল চাইল্ডের ইকুয়ালিটি, এবং এভাবে চলে যাবে।#==দ্বারা ব্যবহৃত এই সিম্পল কিন্তু পাওয়ারফুল স্ট্র্যাটেজি আমাদের ইমপ্লিমেন্টেশন টেস্ট করার জন্য এক্সট্রিমলি ইউজফুল।
class Stoffle::AST::Program attr_accessor :expressions def initialize @expressions = [] end def <<(expr) expressions << expr end def ==(other) expressions == other&.expressions end def children expressions end end এক্সপ্রেশন vs. স্টেটমেন্ট
কিছু ল্যাঙ্গুয়েজে, অনেক কনস্ট্রাক্ট কোনো ভ্যালু প্রডিউস করে না; একটি কন্ডিশনাল একটি ক্লাসিক উদাহরণ। এগুলোকে স্টেটমেন্ট বলা হয়। অন্যান্য কনস্ট্রাক্ট, যাঁরা ভ্যালুএ ইভ্যালুয়েট হয় (যেমন, একটি ফাংশন কল)। এগুলোকে এক্সপ্রেশন বলা হয়। অন্য কিছু ল্যাঙ্গুয়েজে, সবকিছুই এক্সপ্রেশন এবং ভ্যালু প্রডিউস করে। রুবি এই পদ্ধতির উদাহরণ। উদাহরণস্বরূপ, IRB-তে নিচের স্নিপেট টাইপ করে দেখুন মেথড ডেফিনিশন কী ভ্যালুতে ইভ্যালুয়েট হয়:
irb(main):001:0> def two; 2; endআপনি যদি IRB ফায়ার আপ করার মনের না হন, তবে আমি খবর দিচ্ছি; রুবিতে, একটি মেথড ডেফিনিশন এক্সপ্রেশন একটি সিম্বলে ইভ্যালুয়েট হয় (মেথড নাম)। যেহেতু Stoffle রুবি থেকে বহুল প্রেরণা নিয়েছে, আমাদের ছোট টয় ল্যাঙ্গুয়েজেও সবকিছু এক্সপ্রেশন। মনে রাখবেন যে এই ডেফিনিশনগুলো প্র্যাকটিক্যাল উদ্দেশ্যে যথেষ্ট, কিন্তু কোনো কনসেনসাস নেই, এবং আপনি স্টেটমেন্ট এবং এক্সপ্রেশন টার্মগুলো অন্যথা ডিফাইন করা দেখতে পারেন অন্যথাই জায়গায়।
গভীরে যাই: #parse_expr_recursively-এর ইমপ্লিমেন্টেশন শুরু
যেনো আমরা উপরের স্নিপেটে দেখেছি, #parse_expr_recursively হলো একটি নতুন AST নোড বানাতে সম্ভাব্যভাবে কল করা মেথড। #parse_expr_recursively পার্সিং প্রসেসে অন্য অনেক ছোট মেথড ব্যবহার করে, কিন্তু আমরা শান্তভাবে বলতে পারি যে এটি আমাদের পার্সারয় আসল ইঞ্জিন। যদিও এটি খুব দীর্ঘ নয়, এই মেথড কিছুটা ডাইজেস্ট করার কঠিন। তাই, আমরা এটাকে দুটি পার্টে ভাগ করব। এই সেকশনে, এর ইনিয়াল সেগমেন্ট দিয়ে শুরু করি, যা ইতিমধ্যে Stoffle প্রোগ্রামিং ল্যাঙ্গুয়েজের কিছু সিম্পলার অংশ পার্স করার জন্য পর্যাপ্ত শক্তিশালী। রিফ্রেশার হিসেবে, মনে রাখবেন যে আমরা একটি সিম্পল প্রোগ্রাম পার্স করার জন্য যেসব স্টেপ নিচ্ছিলাম যেটি একটি সিংগল ভেরিয়েবল বাইন্ডিং এক্সপ্রেস করে:
সোর্স
my_var = 1 টোকেনস (লেক্সারের আউটপুট, পার্সারের ইনপুট)
[:identifier, :'=', :number] আমরা যে টোকেনগুলো হ্যান্ডেল করতে হবে সেগুলো দেখে এবং অন্যান্য, সাদৃশ্য সিম্পল এক্সপ্রেশনের জন্য লেক্সার আউটপুট কী হতো সেটা কল্পনা করে, লাগে টোকেন টাইপগুলোকে স্পেসিফিক পার্সিং মেথডের সাথে অ্যাসোসিয়েট করার একটি ভালো আইডিয়া:
def parse_expr_recursively parsing_function = determine_parsing_function if parsing_function.nil? unrecognized_token_error return end send(parsing_function) end #parse_expr_recursively-র এই ইনিয়াল ইমপ্লিমেন্টেশনে, সেটাই আমরা করছি। যেহেতু বেশ অনেক ভিন্ন টোকেন টাইপ হ্যান্ডেল করতে হবে, সিদ্ধান্ত গ্রহণের প্রসেসকে একটি আলাদা মেথড -#determine_parsing_function-এ এক্সট্র্যাক্ট করা ভালো, যা আমরা একক্ষণে দেখব।
যখন আমরা শেষ করব, কোনো টোকেন অজানা থাকা উচিত নয়, কিন্তু সেফগার্ড হিসেবে, আমরা চেক করব কারেন্ট টোকেনের সাথে কোনো পার্সিং ফাংশন অ্যাসোসিয়েটেড আছে কিনা। যদি না থাকে, তবে আমরা একটি এরর অ্যাড করব আমাদের @errors ইনস্ট্যান্স ভেরিয়েবলে, যেটি পার্সিং এর সময় ঘটা সকল সমস্যাকে ধারণ করে। আমরা এখানে ডিটেইলে কভার করব না, কিন্তু আপনি যদি কিউরিয়াস হন, তবে GitHub-এ পার্সার এর ফুল ইমপ্লিমেন্টেশন চেক করতে পারেন।
#determine_parsing_function একটি সিম্বল রিটার্ন করে যা কল করা পার্সিং মেথডের নাম রিপ্রেজেন্ট করে। আমরা রুবির send ব্যবহার করে ডাইনামিক্যালি উপযুক্ত মেথড কল করব।
পার্সিং মেথড নির্ধারণ এবং ভেরিয়েবল বাইন্ডিং পার্স করা
এখন, #determine_parsing_function-এ এক নজর দেই এই ইনিয়াল মেকানিজম বুঝতে যা Stoffle-এর ভিন্ন কনস্ট্রাক্ট পার্স করার জন্য স্পেসিফিক মেথড কল করে। #determine_parsing_function সবকিছুর জন্য ব্যবহার হবে (যেমন কিওয়ার্ড এবং ইউনারি অপারেটর) বাইনারি অপারেটর বাদে। বাইনারি অপারেটরের কেসে যেটি টেকনিক ব্যবহার হয়েছে সেটা আমরা পরে এক্সপ্লোর করব। এখন, #determine_parsing_function দেখি:
def determine_parsing_function if [:return, :identifier, :number, :string, :true, :false, :nil, :fn, :if, :while].include?(current.type) "parse_#{current.type}".to_sym elsif current.type == :'(' :parse_grouped_expr elsif [:"\n", :eof].include?(current.type) :parse_terminator elsif UNARY_OPERATORS.include?(current.type) :parse_unary_operator end end উপরে বলা মত, #current একটি ভার্চুয়াল পয়েন্টার কারেন্ট টোকেনের দিকে যা এই মুহূর্তে প্রসেস হচ্ছে। #determine_parsing_function-র ইমপ্লিমেন্টেশন খুব স্ট্রেইটফরওয়ার্ড; আমরা কারেন্ট টোকেনে (নির্দিষ্টভাবে, এর টাইপ) তাকাই এবং কল করার উপযুক্ত মেথডকে রিপ্রেজেন্ট করার একটি সিম্বল রিটার্ন করি।
মনে রাখবেন যে আমরা একটি ভেরিয়েবল বাইন্ডিং (my_var = 1) পার্স করার প্রসেস থেকে যাচ্ছি, তাই আমরা যে টোকেন টাইপ হ্যান্ডেল করছি সেগুলো হলো [:identifier, :'=', :number]। কারেন্ট টোকেন টাইপ :identifier, তাই #determine_parsing_function রিটার্ন করবে :parse_identifier, जैसा আপনি অনুমান করছেন। চলুন আমাদের পরবর্তী স্টেপ, #parse_identifier মেথডে এক নজর দেই:
def parse_identifier lookahead.type == :'=' ? parse_var_binding : AST::Identifier.new(current.lexeme) end এখানে, মূলত সব অন্যান্য পার্স মেথড যা করে তার একটি খুব সিম্পল ম্যানিফেস্টেশন। #parse_identifier - এবং অন্যান্য পার্স মেথডগুলিতে - আমরা টোকেনগুলো চেক করি নির্ধারণ করার জন্য যে আমরা যে স্ট্রাকচার এক্সপেক্ট করছি সেটা আসলে উপস্থিত কিনা। আমরা জানি আমাদের কাছে একটি আইডেন্টিফায়ার আছে, কিন্তু আমাদের নেক্সট টোকেনে তাকিয়ে দেখতে হবে لتحديد করতেই হবে যে আমরা একটি ভেরিয়েবল বাইন্ডিং নিয়ে কাজ করছি কিনা, যা হবে যদি নেক্সট টোকেন টাইপ :'=' হয়, অথবা আমাদের শুধু একটি আইডেন্টিফায়ার আছে নিজে থেকে বা একটি আরও কমপ্লেক্স এক্সপ্রেশনে অংশগ্রহণ করছে। কল্পনা করুন, একটি অ্যরিথমেটিক এক্সপ্রেশন যেখানে আমরা ভেরিয়েবলে স্টোর করা ভ্যালু ম্যানিপুলেট করছি।
যেহেতু আমাদের কাছে নেক্সটে :'=' আছে, #parse_var_binding কল হবে:
def parse_var_binding identifier = AST::Identifier.new(current.lexeme) consume(2) AST::VarBinding.new(identifier, parse_expr_recursively) end এখানে, আমরা একটি নতুন AST নোড তৈরি করি কারেন্ট প্রসেস করা আইডেন্টিফায়ার রিপ্রেজেন্ট করার জন্য। AST::Identifier-র কনস্ট্রাক্টর আইডেন্টিফায়ার টোকেনের লেক্সিম এক্সপেক্ট করে (অর্থাৎ, ক্যারেক্টর সিকোয়েন্স, স্ট্রিং "my_var" আমাদের কেসে), তাই আমরা সেটা সরবরাহ করি। তারপর, আমরা প্রসেস হচ্ছে টোকেন স্ট্রিমে দুই পজিশন এডভান্স করি, যা টোকেন টাইপ :number-কে পরবর্তী ანালাইসিস করার টোকেন বানায়। মনে রাখবেন আমরা [:identifier, :'=', :number] নিয়ে কাজ করছি।
শেষে, আমরা একটি ভেরিয়েবল বাইন্ডিং রিপ্রেজেন্ট করার AST নোড বানাই এবং রিটার্ন করি। AST::VarBinding-র কনস্ট্রাক্টর দুটি প্যারামিটার এক্সপেক্ট করে: একটি আইডেন্টিফায়ার AST নোড (বাইন্ডিং এক্সপ্রেশনের লেফট-হ্যান্ড সাইড) এবং যেকোনো বৈধ এক্সপ্রেশন (রাইট-হ্যান্ড সাইড)। এখানে একটি অত্যন্ত গুরুত্বপূর্ণ বিষয় লক্ষ্য করা দরকার; ভেরিয়েবল বাইন্ডিং এক্সপ্রেশনের রাইট-হ্যান্ড সাইড প্রডিউস করার জন্য, আমরা #parse_expr_recursively আবার কল করছি। এটা প্রথমে একটু অদ্ভুত লাগতে পারে, কিন্তু মনে রাখবেন যে একটি ভেরিয়েবল খুব কমপ্লেক্স এক্সপ্রেশনের সাথে বাউন্ড হতে পারে, শুধু একটি মাত্র নম্বারের সাথে নয়, যেন আমাদের উদাহরণে। আপনি যদি আমাদের পার্সিং স্ট্র্যাটেজি এক শব্দে ডিফাইন করতে চান, তবে সেটা হবে রিকার্সিভ। এখন, আমি অনুমান করি আপনি বুঝতে শুরু করছেন কেন #parse_expr_recursively-র এত নাম।
এই সেকশন ফিনিশ করার আগে, আমরা দ্রুত AST::Identifier এবং AST::VarBinding এক্সপ্লোর করি। প্রথম, AST::Identifier:
class Stoffle::AST::Identifier < Stoffle::AST::Expression attr_accessor :name def initialize(name) @name = name end def ==(other) name == other&.name end def children [] end end এখানে কিছু ফ্যান্সি নেই। মেনশন করার লাইক হলো নোডটি ভেরিয়েবলের নাম স্টোর করে এবং এর কোনো চাইল্ড নেই।
এখন, AST::VarBinding:
class Stoffle::AST::VarBinding < Stoffle::AST::Expression attr_accessor :left, :right def initialize(left, right) @left = left @right = right end def ==(other) children == other&.children end def children [left, right] end end লেফট-হ্যান্ড সাইড হলো একটি AST::Identifier নোড। রাইট-হ্যান্ড সাইড প্রায় সকল সম্ভাব্য নোড টাইপ — একটি সিম্পল নম্বর থেকে, যেন আমাদের উদাহরণে, কিছু কমপ্লেক্স কিছুর মাধ্যমে — যা আইডেন্টিফায়ারের সাথে বাউন্ড এক্সপ্রেশনকে রিপ্রেজেন্ট করে। একটি ভেরিয়েবল বাইন্ডিং-এর #children হলো সেস AST নোডগুলো যেগুলো এটি @left এবং @right-এ ধারণ করে।
সোর্স থেকে AST, একটি সেকেন্ড উদাহরণ
#parse_expr_recursively-র বর্তমান अवতরণ ইতিমধ্যে কিছু সিম্পল এক্সপ্রেশন পার্স করতে পারে, যেন আমরা পূর্ববর্তী সেকশনে দেখেছি। এই সেকশনে, আমরা এর ইমপ্লিমেন্টেশন ফিনিশ করব যাতে এটি আরও কমপ্লেক্স এন্টিটিও পার্স করতে পারে, যেমন বাইনারি এবং লজিক্যাল অপারেটর। এখানে, আমরা স্টেপ-বাই-স্টেপ এক্সপ্লোর করব কীভাবে আমাদের পার্সার একটি প্রোগ্রাম হ্যান্ডেল করে যা একটি ফাংশন ডিফাইন করে। এখানে সোর্স, লেক্সার দ্বারা প্রডিউস করা টোকেনের একটি সিম্প্লিফাইড রিপ্রেজেন্টেশন এবং, যেন প্রথম সেকশনে ছিল, পার্সারের আউটপুটের একটি ভিজ্যুয়াল রিপ্রেজেন্টেশন (এন অ্যাবস্ট্রাক্ট সিনট্যাক্স ট্রি) যা প্রোগ্রামটি রিপ্রেজেন্ট করবে:
সোর্স
fn double: num num * 2 end টোকেনস (লেক্সারের আউটপুট, পার্সারের ইনপুট)
[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof] পার্সারের আউটপুটের ভিজ্যুয়াল রিপ্রেজেন্টেশন (এন অ্যাবস্ট্রাক্ট সিনট্যাক্স ট্রি)
আগাম ধাপে যাওয়ার আগে, আসুন একটু পেছনে হটে অপারেটর প্রেসিডেন্স রুলস সম্পর্কে কথা বলি। এগুলো গাণিতিক কনভেনশনের ওপর ভিত্তি করে; গণিতে, এগুলো শুধু কনভেনশন, এবং আপনার আপনি অভ্যাস করে থাকা অপারেটর প্রেসিডেন্সের পেছনে কিছু ফান্ডামেন্টাল কারণ নেই। এই রুলস আমাদের একটি এক্সপ্রেশনের সঠিক إيفালুয়েশন অর্ডার নির্ধারণ করতে দেয় এবং, আমাদের কেসে, এটি প্রথমে পার্স করার জন্য। প্রতিটি অপারেটর প্রেসিডেন্স ডিফাইন করতে, আমরা শুধু একটি ম্যাপ (অর্থাৎ, একটি Hash) রাখি টোকেন টাইপ এবং ইন্টিজারের। উচ্চ সংখ্যা মানে অপারেটরটি প্রথমে হ্যান্ডেল করা উচিত:
# আমরা এই প্রেসিডেন্স রুলস Stoffle::Parser-এর টপে ডিফাইন করি। module Stoffle class Parser # ... UNARY_OPERATORS = [:'!', :'-'].freeze BINARY_OPERATORS = [:'+', :'-', :'*', :'/', :'==', :'!=', :'>', :'<', :'>=', :'<='].freeze LOGICAL_OPERATORS = [:or, :and].freeze LOWEST_PRECEDENCE = 0 PREFIX_PRECEDENCE = 7 OPERATOR_PRECEDENCE = { or: 1, and: 2, '==': 3, '!=': 3, '>': 4, '<': 4, '>=': 4, '<=': 4, '+': 5, '-': 5, '*': 6, '/': 6, '(': 8 }.freeze # ... end end #parse_expr_recursively`-এ ব্যবহৃত টেকনিক কম্পিউটার সায়েন্টিস্ট ভৌন প্র্যাট তার ১৯৭৩ সালের পেপার, "Top Down Operator Precedence"-এ উপস্থাপিত বিখ্যাত পার্সার অ্যালগরিদমের ওপর ভিত্তি করে। আপনি দেখবেন, অ্যালগরিদমটি খুব সিম্পল, কিন্তু একটু কঠিন পুরোপুরি বুঝতে। কেউ কেউ বলতে পারে এটি একটু ম্যাজিকাল লাগে। এই পোস্টে আমরা যা করব সেটা হলো একটি ইন্তুইটিভ আন্ডারস্ট্যান্ডিং পেতে এই টেকনিকের ওপারেশন সম্পর্কে, আমাদের উপরে উল্লিখিত Stoffle স্নিপেট পার্স করার সময় কী হয় সেটা স্টেপ-বাই-স্টেপ যাব। তাহলে, আর দেরি না করে, এখানে #parse_expr_recursively-র সম্পূর্ণ ভার্সন:
def parse_expr_recursively(precedence = LOWEST_PRECEDENCE) parsing_function = determine_parsing_function if parsing_function.nil? unrecognized_token_error return end expr = send(parsing_function) return if expr.nil? # When expr is nil, it means we have reached a \n or a eof. # Note that, here, we are checking the NEXT token. while nxt_not_terminator? && precedence < nxt_precedence infix_parsing_function = determine_infix_function(nxt) return expr if infix_parsing_function.nil? consume expr = send(infix_parsing_function, expr) end expr end #parse_expr_recursively এখন একটি প্যারামিটার গ্রহণ করে, precedence। এটি একটি দিয়ে गये কলে বিবেচ্য প্রেসিডেন্স "লেভেল" রিপ্রেজেন্ট করে। এডিশনালি, মেথডের প্রথম অংশ প্রায় সেম। তারপর - যদি আমরা এই প্রথম অংশে একটি এক্সপ্রেশন বিল্ড করতে পারি - আসে মেথডের নবীন অংশ। যতক্ষণ না নেক্সট টোকেন একটি টার্মিনেটর (অর্থাৎ, লাইন ব্রেক বা ফাইল এন্ড) এবং প্রেসিডেন্স ( precedence প্যারাম) নেক্সট টোকেনের প্রেসিডেন্স থেকে কম, আমরা পটেনশিয়ালি টোকেন স্ট্রিম কনসাম করতে থাকি।
while-র ভেতর ঝাঁকার আগে, এর সেকেন্ড কন্ডিশন (precedence < nxt_precedence) এর মানে চিন্তা করি একটু। যদি নেক্সট টোকেনের প্রেসিডেন্স বেশি হয়, তবে আমরা যা এক্সপ্রেশন বিল্ড করেছি ( expr লোকাল ভেরিয়েবল) সেটা প্রয়ববলি একটি নোডের চাইল্ড যেটি এখনো বিল্ড হয়নি (মনে রাখবেন আমরা একটি AST বানাচ্ছি, একটি অ্যাবস্ট্রাক্ট সিনট্যাক্স ট্রি)। আমাদের Stoffle স্নিপেট পার্স করার মাধ্যমে যাওয়ার আগে, একটু চিন্তা করি একটি সিম্পল অ্যরিথমেটিক এক্সপ্রেশন পার্স করার কথা: 2 + 2। এই এক্সপ্রেশন পার্স করার সময়, আমাদের মেথডের প্রথম অংশ একটি AST::Number নোড বিল্ড করবে প্রথম 2 রিপ্রেজেন্ট করার জন্য এবং এটাকে expr-এ স্টোর করবে। তারপর, আমরা while-এ এন্টার করব কারণ নেক্সট টোকেনের প্রেসিডেন্স (:'+') ডিফল্ট প্রেসিডেন্স থেকে বেশি হবে। আমরা তখন যোগ হ্যান্ডেল করার পার্সিং মেথড কল করব, এটাকে AST::Number নোড পাস করে এবং একটি বাইনারি অপারেটর রিপ্রেজেন্ট করার নোড (AST::BinaryOperator) ফেরত পাব। শেষে, আমরা expr-এ স্টোর করা ভ্যালু, 2 + 2-র প্রথম 2 রিপ্রেজেন্ট করার নোড, ওভাররাইট করব এই নতুন নোড দিয়ে যা প্লাস অপারেটর রিপ্রেজেন্ট করছে। লক্ষ্য করুন যে এন্ডে, এই অ্যালগরिदম আমাদের নোডগুলো রিয়ারেঞ্জ করতে দিয়েছে; আমরা AST::Number নোড বানানো শুরু করলাম এবং শেষে এটা আমাদের ট্রিতে একটি ডিপার নোড হয়ে গেল, AST::BinaryOperator নোডের চাইল্ডদের একটি হিসেবে।
ফাংশন ডেফিনিশন পার্স করা স্টেপ-বাই-স্টেপ
এখন যেনো আমরা #parse_expr_recursively-র একটি ওভারঅ্যাল এক্সপ্লানেশন দেখেছি, আসুন আমাদের সিম্পল ফাংশন ডেফিনিশনে ফিরে যাই:
fn double: num num * 2 end এমনকি পার্সার এক্সিকিউশনের একটি সিম্প্লিফাইড ডেসক্রিপশন দেখার আইডিয়া ক্লান্তিকর লাগতে পারে (আর নিশ্চিতভাবেই, হয়তো এটি ক্লান্তিকর!), কিন্তু আমার মতে এটি খুব ভ্যালুয়েবল উভয় #parse_expr_recursively এবং স্পেসিফিক বিটস (ফাংশন ডেফিনিশন এবং প্রোডাক্ট অপারেটর) পার্স করার বোঝাপড়ার জন্য। প্রথম কিছুই, এখানে টোকেন টাইপগুলো যেগুলো আমরা হ্যান্ডেল করব (নিচে আউটপুট হলো @tokens.map(&:type), পার্সারের ভেতরে লেক্সার স্নিপেটটি টোকেনাইজ করার পর ফিনিশ করলে):
[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof] নিচের টেবিলে সবচেয়ে গুরুত্বপূর্ণ মেথডগুলোর কল হওয়ার অর্ডার দেখানো হয়েছে যেনো আমরা উপরের টোকেনগুলো পার্স করি। মনে রাখবেন যে এটি একটি সিম্প্লিফিকেশন, এবং আপনি আপনি যদি পার্সার এক্সিকিউশনের সকল এক্সएक্ট স্টেপ বুঝতে চান, আমি রিকমেন্ড করি একটি রুবি ডিবাগার, যেমন Byebug, ব্যবহার করা এবং প্রোগ্রাম এক্সিকিউট হওয়ার সাথে সাথে লাইন-বাই-লাইন এডভান্স করা।
আমাদের পার্সার মাইক্রোস্কোপের নিচে
এই সटিক স্নিপেট ব্যবহার করে একটি টেস্ট উপলব্ধ Stoffle-এর সোর্সে। আপনি এটাকে spec/lib/stoffle/parser_spec.rb-তে পাবেন; এটি वो টেস্ট যেটি
complex_program_ok_2.sfeনামক স্নিপেট ব্যবহার করে।পার্সার এক্সিকিউশন স্টেপ-বাই-স্টেপ এক্সপ্লোর করতে, আপনি সোর্স এডিট করে
byebugকল যোগ করতে পারেনParser#parse-র শুরুতে, শুধু উপরে উল্লিখিত টেস্ট RSpec-এ রান করুন, এবং তারপর Byebug-এরstepকমান্ড ব্যবহার করে প্রোগ্রাম এক লাইন একবারে এডভান্স করুন।Byebug কীভাবে কাজ করে এবং সকল উপলব্ধ কমান্ড সম্পর্কে আরও জানতে GitHub-এ প্রজেক্টের README ফাইল ভিজিট করুন।
| কল করা মেথড | কারেন্ট টোকেন | নেক্সট টোকেন | নোটেবল ভেরিয়েবল / কল রেজাল্ট | Obs |
|---|---|---|---|---|
| parse | nil | :fn | ||
| parse_expr_recursively | :fn | :identifier | precedence = 0, parsing_function = :parse_fn | |
| parse_function_definition | :fn | :identifier | parse_fn is an alias of parse_function_definition | |
| parse_function_params | :identifier | :":" | ||
| parse_block | :"\n" | :identifier | ||
| parse_expr_recursively | :identifier | :* | precedence = 0, parsing_function = :parse_identifier, nxt_precedence() returns 6, infix_parsing_function = :parse_binary_operator | |
| parse_identifier | :identifier | :* | ||
| parse_binary_operator | :* | :number | op_precedence = 6 | |
| parse_expr_recursively | :number | :"\n" | precedence = 6, parsing_function = :parse_number, nxt_precedence() returns 0 | |
| parse_number | :number | :"\n" |
এখন যেনো আমাদের পার্সারের এক্সিকিউশন ফ্লো এবং স্টেটের একটি জেনারেল ধারণা পেয়েছি, চলুন আমরা যেসব পার্সিং মেথড এখনো দেখিনি সেগুলো 좀 বিস্তারিতে অধ্যয়ন করি।
#parse_function_definition মেথড
#parse_function_definition মেথডটি কল হয়েছিল যখন কারেন্ট টোকেন ছিল :fn এবং নেক্সট ছিল :identifier:
def parse_function_definition return unless consume_if_nxt_is(build_token(:identifier)) fn = AST::FunctionDefinition.new(AST::Identifier.new(current.lexeme)) if nxt.type != :"\n" && nxt.type != :':' unexpected_token_error return end fn.params = parse_function_params if nxt.type == :':' return unless consume_if_nxt_is(build_token(:"\n", "\n")) fn.body = parse_block fn end #consume_if_nxt_is - আপনি অনুমান করতে পারছেন - আমাদের পয়েন্টার এডভান্স করاয় যদি নেক্সট টোকেন একটি দিয়ে गये টাইপের হয়। অন্যথায়, এটা @errors-এ একটি এরর অ্যাড করে। #consume_if_nxt_is খুব ইউজফুল - এবং অনেক পার্সার মেথডে ব্যবহার হয় - যখন আমরা টোকেনের স্ট্রাকচার চেক করতে চাই সিনট্যাক্স বৈধ কিনা তা নির্ধারণ করার জন্য। সেটা করার পর, কারেন্ট টোকেন টাইপ হয় :identifier (আমরা 'double' হ্যান্ডেল করছি, ফাংশনের নাম), এবং আমরা একটি AST::Identifier বানাই এবং ফাংশন ডেফিনিশন রিপ্রেজেন্ট করার নোড তৈরির কনস্ট্রাক্টরে পাস করি (AST::FunctionDefinition)। আমরা এখানে ডিটেইলে দেখব না, কিন্তু বেসিক্যালি, একটি AST::FunctionDefinition নোড এক্সপেক্ট করে ফাংশন নাম, পটেনশিয়ালি একটি প্যারামিটার অ্যারে এবং ফাংশন বড।
#parse_function_definition-র পরবর্তী স্টেপ হলো ভেরিফাই করা নেক্সট টোকেন আইডেন্টিফায়ারের পর এক্সপ্রেশন টার্মিনেটর (অর্থাৎ, প্যারামিটারের बिना একটি ফাংশন) নাকি কোলন (অর্থাৎ, এক বা একাধিক প্যারামিটারসহ ফাংশন)। যদি প্যারামিটার থাকে, যেন double ফাংশন ডিফাইন করছি, আমরা #parse_function_params কল করি সেগুলো পার্স করার জন্য। একক্ষণে এই মেথড চেক করব, কিন্তু আগে চলুন #parse_function_definition-র এক্সপ্লোরেশন ফিনিশ করি।
শেষ স্টেপ হলো আবার একটি সিনট্যাক্স চেক করা যেন ফাংশন নাম + প্যারামিটার এর পর একটি টার্মিনেটর আছে এবং, তারপর, ফাংশন বড পার্স করতে #parse_block কল করুন। শেষে, আমরা fn রিটার্ন করি, যেটি আমাদের ফুলি-বিল্ট AST::FunctionDefinition ইনস্ট্যান্স ধারণ করে, ফাংশন নাম, প্যারামিটার, এবং বডসহ।
ফাংশন প্যারামিটারস পার্স করার নাট বোল্টস
পূর্ববর্তী সেকশনে, আমরা দেখেছি #parse_function_params #parse_function_definition-এর ভেতরে কল হয়েছে। আমরা আমাদের টেবিলে ফিরে যাই যা আমাদের পার্সার এক্সিকিউশন ফ্লো এবং স্টেট সাড়ান쇼 করছিল, আমরা দেখতে পাই যে যখন #parse_function_params চলতে শুরু করে, কারেন্ট টোকেন টাইপ হয় :identifier, এবং নেক্সটটি :":" (অর্থাৎ, আমরা ফাংশন নাম পার্স করা ফিনিশ করলাম)। এই সব মাথায় রেখে, চলুন কিছু আরো কোড দেখি:
def parse_function_params consume return unless consume_if_nxt_is(build_token(:identifier)) identifiers = [] identifiers << AST::Identifier.new(current.lexeme) while nxt.type == :',' consume return unless consume_if_nxt_is(build_token(:identifier)) identifiers << AST::Identifier.new(current.lexeme) end identifiers end এই মেথডের প্রতিটি অংশ এক্সপ্লেইন করার আগে, চলুন রিক্যাপ করি আমাদের প্রসেস করার টোকেনগুলো এবং আমরা এই জবের কোথায় আছি:
[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof] # here ▲ #parse_function_params-র প্রথম অংশ স্ট্রেইটফরওয়ার্ড। আমাদের যদি বৈধ সিনট্যাক্স থাকে (কমপক্ষে :-এর পর একটি আইডেন্টিফায়ার), তবে আমরা আমাদের পয়েন্টার দুই পজিশন মুভ করি:
[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof] # ▲ এখন, আমরা প্রথম প্যারামিটার যা পার্স হবে (একটি টোকেন টাইপ :identifier) তে বসে আছি। প্রত্যাশা অনুযায়ী, আমরা একটি AST::Identifier তৈরি করি এবং এটাকে পশ করি একটি অ্যারেতে, যেটি পটেনশিয়ালি একাধিক অন্যান্য প্যারামিটার ধারণ করতে পারে যা এখনো পার্স হয়নি। #parse_function_params-র পরবর্তী বিটে, আমরা প্যারামিটার পার্স করা চালু রাখি যতক্ষণ না প্যারামিটার সেপারেটর থাকে (অর্থাৎ, টোকেন টাইপ :',')। আমরা মেথডটি শেষ করি লোকাল ভেরিয়েবল identifiers রিটার্ন করে, একটি অ্যারে যা পটেনশিয়ালি একাধিক AST::Identifier নোড ধারণ করে, প্রতিটি একটি প্যারামিটার রিপ্রেজেন্ট করে। কিন্তু আমাদের কেসে, এই অ্যারেতে শুধু একটি এলিমেন্ট রয়েছে।
ফাংশন বডর কী?
এখন চলুন গভীরে যাই ফাংশন ডেফিনিশন পার্স করার শেষ অংশে: এর বড ডিল করা। যখন #parse_block কল হয়, আমরা সেটি টার্মিনেটরে বসে আছি যেটি ফাংশন প্যারামিটারের লিস্টের এন্ড মার্ক করলো:
[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof] # ▲ এবং, এখানে #parse_block-র ইমপ্লিমেন্টেশন:
def parse_block consume block = AST::Block.new while current.type != :end && current.type != :eof && nxt.type != :else expr = parse_expr_recursively block << expr unless expr.nil? consume end unexpected_token_error(build_token(:eof)) if current.type == :eof block end AST::Block হলো একটি কোড ব্লক রিপ্রেজেন্ট করার AST নোড। অন্য কথায়, AST::Block শুধু এক্সপ্রেশনর একটি লিস্ট ধারণ করে, খুব সাদৃশ্য ফ্যাশনে আমাদের প্রোগ্রামের রুট নোড, একটি AST::Program নোড (যেন আমরা এই পোস্টের শুরুতে দেখেছি)। ব্লক পার্স করার জন্য (অর্থাৎ, ফাংশন বড), আমরা অনপ্রসেসড টোকেন থ্রু এডভান্স করি যতক্ষণ না একটি টোকেন পাই যা ব্লকের এন্ড মার্ক করে।
ব্লক গঠন করে এক্সপ্রেশনগুলো পার্স করার জন্য, আমরা আমাদের ইতিমধ্যে পরিচিত #parse_expr_recursively ব্যবহার করি। আমরা এই মেথড কল এ টাকিয়ে দিবো শুধু একক্ষণে; এই পয়েন্টে আমরা আমাদের double ফাংশনের ভেতরে হচ্ছে প্রোডাক্ট অপারেশন পার্স করা শুরু করব। এটি সariously ফলো করলে আমাদের #parse_expr_recursively-এ প্রেসিডেন্স ভ্যালুসের ব্যবহার এবং কীভাবে একটি ইনফিক্স অপারেটর (আমাদের কেসে *) ডিল হয় সেটা বুঝতে সাহায্য করবে। কিন্তু তার আগে, চলুন #parse_block-র এক্সপ্লোরেশন ফিনিশ করি।
AST::Block নোড রিটার্ন করার আগে, আমরা চেক করি কারেন্ট টোকেন টাইপ :eof কিনা। যদি হয়, তবে আমাদের একটি সিনট্যাক্স এরর আছে যেহেতু Stoffle একটি ব্লককে end কিওয়ার্ড দিয়ে এন্ড করার চায়। #parse_block-র এক্সপ্লেনেশন র্যাপ আপ করার আগে, আমি একটা কিছু মেনশন করতে চাই যা আপনি নিশ্চিতভাবেই লক্ষ্য করেছেন; আমাদের লুপের কন্ডিশনগুলোতে একটি যাচাই করে নেক্সট টোকেন টাইপ :else কিনা। এটি হয় কারণ #parse_block অন্যান্য পার্সিং মেথডের সাথে শেয়ার করা হয়, যেসব কন্ডিশনাল এবং লুপ পার্স করার জন্য দায়িত্বवान। খুব নাইস, ঠিক?
ইনফিক্স অপারেটর পার্স করা
নামটি একটু ফ্যান্সি লাগতে পারে, কিন্তু ইনফিক্স অপারেটরগুলো সেসব যেগুলো আমরা অ্যরিথমেটিকে খুব অভ্যস্ত আছি, প্লাস কিছু অন্যান্য যেগুলো আমরা সফটওয়্যার ডেভেলপার হিসেবে বেশি পরিচিত হতে পারি:
module Stoffle class Parser # ... BINARY_OPERATORS = [:'+', :'-', :'*', :'/', :'==', :'!=', :'>', :'<', :'>=', :'<='].freeze LOGICAL_OPERATORS = [:or, :and].freeze # ... end end যখন ইনফিক্স নোটেশন ব্যবহার করা হয়, যেন Stoffle-এ হয়, এগুলো ইনফিক্সড ব্যবহার করা এক্সপেক্টেড, অর্থাৎ এগুলো তাদের দুই অপারেন্ডের মাঝপথে আয়ত্ত থাকা উচিত (যেন * আমাদের double ফাংশনে num * 2-এ আয়ত্ত)। কিছু মেনশন করার লাইক হলো যদিও ইনফিক্স নোটেশন খুব জনপ্রিয়, অপারেটরকে তাদের অপারেন্ডের সাথে পজিশন করার অন্যান্য পদ্ধতিও রয়েছে। আপনি যদি কিউরিয়াস হন, "পোলিশ নোটেশন" এবং "রিভার্স পোলিশ নোটেশন" মেথড সম্পর্কে কিছু রিসার্চ করুন।
আমাদের double ফাংশন ফিনিশ করার জন্য, আমাদের * অপারেটর ডিল করতে হবে:
fn double: num num * 2 end পূর্ববর্তী সেকশনে, আমরা মেনশন করেছি যে double-র বড গঠন করে এক্সপ্রেশন পার্স করা শুরু হয় যখন #parse_expr_recursively #parse_block-এর ভেতরে কল হয়। সেটা হলে, এখানে আমাদের পজিশন @tokens-এ:
[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof] # ▲ এবং, আমাদের মেমরি রিফ্রেশ করার জন্য, এখানে আবার #parse_expr_recursively-র কোড:
def parse_expr_recursively(precedence = LOWEST_PRECEDENCE) parsing_function = determine_parsing_function if parsing_function.nil? unrecognized_token_error return end expr = send(parsing_function) return if expr.nil? # When expr is nil, it means we have reached a \n or a eof. # Note that here, we are checking the NEXT token. while nxt_not_terminator? && precedence < nxt_precedence infix_parsing_function = determine_infix_function(nxt) return expr if infix_parsing_function.nil? consume expr = send(infix_parsing_function, expr) end expr end মেথডের প্রথম অংশে, আমরা সেম #parse_identifier মেথড ব্যবহার করব যা আমরা num ভেরিয়েবল পার্স করতে ব্যবহার করেছিলাম। তারপর, প্রথমবারের মতো, while লুপের কন্ডিশনগুলো ইভ্যালুয়েট হবে ট্রু; নেক্সট টোকেন একটি টার্মিনেটর নয়, এবং নেক্সট টোকেনের প্রেসিডেন্স এই কারেন্ট এক্সিকিউশন parse_expr_recursively-র প্রেসিডেন্স থেকে বেশি (precedence হলো ডিফল্ট, 0, যখন nxt_precedence ৬ রিটার্ন করছে যেহেতু নেক্সট টোকেন টাইপ :'*')। এটি ইঙ্গিত দিচ্ছে যে আমরা যা নোড ইতিমধ্যে বিল্ড করেছি (একটি AST::Identifier রিপ্রেজেন্টিং num) সেটা প্রয়ববলি আমাদের AST-এ ডিপার থাকবে (অর্থাৎ, এটি একটি নোডের চাইল্ড হবে যেটি এখনো বিল্ড হয়নি)। আমরা লুপে এন্টার করি এবং #determine_infix_function কল করি, নেক্সট টোকেন ( * ) পাস করে:
def determine_infix_function(token = current) if (BINARY_OPERATORS + LOGICAL_OPERATORS).include?(token.type) :parse_binary_operator elsif token.type == :'(' :parse_function_call end end যেহেতু * একটি বাইনারি অপারেটর, #determine_infix_function রান করলে রেজাল্ট হবে :parse_binary_operator। #parse_expr_recursively-এ ফিরে, আমরা আমাদের টোকেন পয়েন্টার এক পজিশন এডভান্স করি এবং তারপর #parse_binary_operator কল করি, expr-র ভ্যালু ( num রিপ্রেজেন্টিং AST::Identifier ) পাস করে:
[:fn, :identifier, :":", :identifier, :"\n", :identifier, :*, :number, :"\n", :end, :"\n", :eof] #▲ def parse_binary_operator(left) op = AST::BinaryOperator.new(current.type, left) op_precedence = current_precedence consume op.right = parse_expr_recursively(op_precedence) op end class Stoffle::AST::BinaryOperator < Stoffle::AST::Expression attr_accessor :operator, :left, :right def initialize(operator, left = nil, right = nil) @operator = operator @left = left @right = right end def ==(other) operator == other&.operator && children == other&.children end def children [left, right] end end #parse_binary_operator-এ, আমরা একটি AST::BinaryOperator তৈরি করি (এর ইমপ্লিমেন্টেশন উপরে দেখানো হয়েছে আপনি কিউরিয়াস হলে) * রিপ্রেজেন্ট করার জন্য, এর লেফট অপারেন্ড সেট করি আইডেন্টিফায়ার (num) যা আমরা #parse_expr_recursively-এ পেয়েছিলাম। তারপর, আমরা *-এর প্রেসিডেন্স ভ্যালু লোকাল ভেরিয়েবল op_precedence-এ সেভ করি এবং আমাদের টোকেন পয়েন্টার এডভান্স করি। * রিপ্রেজেন্ট করার নোড ফুলি বিল্ড করার জন্য, আমরা #parse_expr_recursively আবার কল করি! আমাদের এই পথে এগিয়ে যেতে হবে কারণ আমাদের অপারেটরের রাইট-হ্যান্ড সাইড সবসময় একটি সিংগল নম্বর বা আইডেন্টিফায়ার নয়; এটি একটি কমপ্লেক্স এক্সপ্রেশন হতে পারে, যেমন num * (2 + 2)।
#parse_binary_operator-এ যেটি অত্যন্ত গুরুত্বপূর্ণ ঘটে সেটা হলো পদ্ধতি যেনে আমরা #parse_expr_recursively আবার কল করি। আমরা এটাকে কল করি 6 প্রেসিডেন্স ভ্যালু পাস করে (*-এর প্রেসিডেন্স, যেটি op_precedence-এ স্টোর করা)। এখানে আমরা আমাদের পার্সিং অ্যালগরিদমের একটি গুরুত্বপূর্ণ দিক বুঝতে পারি, যেটি পূর্বে মেনশন করা হয়েছিল। একটি আপেক্ষিক উচ্চ প্রেসিডেন্স ভ্যালু পাস করে, মনে হয় * নেক্সট টোকেনকে তার অপারেন্ড হিসেবে টানছে। কল্পনা করুন আমরা num * 2 + 1 এক্সপ্রেশন পার্স করছি; এই কেসে, *-এর প্রেসিডেন্স ভ্যালু যা এই নেক্সট কলের সময় #parse_expr_recursively-এ পাস করা হয়েছে, সেটা গ্যারান্টি দেবে যে 2 *-এর রাইট-হ্যান্ড সাইড হয়ে যাবে, +-এর অপারেন্ড হবena, যেস প্রেসিডেন্স ভ্যালু কম 5।
#parse_expr_recursively একটি AST::Number নোড রিটার্ন করলে, আমরা এটাকে *-এর রাইট-হ্যান্ড সাইড হিসেবে সেট করি এবং, শেষে, আমাদের কমপ্লিট AST::BinaryOperator নোড রিটার্ন করি। এই পয়েন্টে, আমরা বেসিক্যালি আমাদের Stoffle প্রোগ্রাম পার্স করা ফিনিশ করেছি। আমাদের এখনও কিছু টার্মিনেটর টোকেন পার্স করতে বাকি, কিন্তু এটি স্ট্রেইটফরওয়ার্ড এবং খুব ইন্ড্রেস্টিং নয়। শেষে, আমাদের @ast-এ একটি AST::Program ইনস্ট্যান্স থাকবে এক্সপ্রেশনসহ যেগুলো ভিজ্যুয়ালি রিপ্রেজেন্ট করা যাবে ট্রি হিসেবে যেটি আমরা এই পোস্টের শুরুতে এবং পোস্টের দ্বিতীয় সেকশনের ইন্ট্রোডাকশনে দেখেছিলাম:
র্যাপ আপ
এই পোস্টে, আমরা Stoffle-এর পার্সারের প্রধান দিকগুলো কভার করেছি। আপনি যদি এখানে এক্সপ্লোর করা বিটগুলো বুঝতে পারেন, তবে আপনাকে অন্যান্য পার্সার মেথড বুঝতে কোনো সমস্যা হবেনা যেগুলো আমরা কভার করতে পারিনি, যেমন কন্ডিশনাল এবং লুপ পার্স করা। আমি আপনাকে উৎসাহিত করি পার্সার এর সোর্স কোড নিজে এক্সপ্লোর করতে এবং ইমপ্লিমেন্টেশন টুইক করতে আপনি যদি আরও অ্যাডভেঞ্চারাস ফিল করেন! ইমপ্লিমেন্টেশনের সাথে একটি কম্প্রيهেনসিভ টেস্ট স্যুট রয়েছে, তাই পার্সারের সাথে এক্সপেরিমেন্ট করার ভয় করবেন না।
এই সিরিজের পরবর্তী পোস্টগুলিতে, আমরা শেষ বিট ইমপ্লিমেন্ট করে আমাদের ছোট মন্সটারকে জীবন দেব: ট্রি-ওয়াক ইন্টারপ্রেটার। আমি ওপেক্ষা করছি আপনার সাথে সেখানে থাকার জন্য যখন আমরা আমাদের প্রথম Stoffle প্রোগ্রাম রান করব!
