পার্সিং ওভারভিউ — টপ-ডাউন বনাম বটম-আপ

Parsing overview — top-down vs bottom-up

৭ মিনিট পড়া মধ্যম · Intermediate Python কোডসহ সম্পূর্ণ বাংলায়

এক নজরে · TL;DR

পার্সিং হলো M4-এর টোকেন-স্ট্রিম নিয়ে সেটি M3-এর গ্রামার থেকে ডেরাইভ করা যায় কিনা যাচাই করা, এবং একটি পার্স ট্রি (L14) তৈরি করা — কম্পাইলার পাইপলাইনের দ্বিতীয় ধাপ (L05)।
টপ-ডাউন পার্সিং রুট থেকে শুরু করে leaves-এর দিকে নামে — L13-এর leftmost derivation-এর সাথে সরাসরি মিলে যায়।
বটম-আপ পার্সিং leaves থেকে শুরু করে রুটের দিকে ওঠে — L13-এর rightmost derivation উল্টো দিকে-র সাথে মিলে যায়।
টপ-ডাউন (বিশেষত recursive descent, L22) হাতে লেখা সহজ কিন্তু গ্রামারে সীমাবদ্ধতা আরোপ করে; বটম-আপ (L24-L26) বড় ক্লাসের গ্রামার হ্যান্ডল করতে পারে কিন্তু সাধারণত টুল দিয়ে জেনারেট করা হয়, হাতে লেখা হয় না।

এই পাঠে যা শিখবেন

পার্সিং ঠিক কী কাজ করে এবং কম্পাইলার পাইপলাইনে এর অবস্থান
টপ-ডাউন পার্সিং কীভাবে leftmost derivation নির্মাণ করে
বটম-আপ পার্সিং কীভাবে rightmost derivation বিপরীত ক্রমে নির্মাণ করে
দুই কৌশলের মধ্যে ব্যবহারিক trade-off — সরলতা বনাম গ্রামার-ক্ষমতা

১ · পার্সিং কী

পার্সিং (Parsing)M4-এর টোকেন-স্ট্রিম নিয়ে তা M3-এর গ্রামার থেকে ডেরাইভ করা সম্ভব কিনা যাচাই করা, এবং সম্ভব হলে একটি পার্স ট্রি (L14) তৈরি করা — কম্পাইলার পাইপলাইনের দ্বিতীয় ধাপ। মানে M4-এর লেক্সার থেকে পাওয়া টোকেন-স্ট্রিম নিয়ে যাচাই করা এটি M3-এর গ্রামার (context-free grammar) থেকে ডেরাইভ করা যায় কিনা — সম্ভব হলে একটি পার্স ট্রি (L14) আউটপুট হিসেবে তৈরি করা। এটি L01/L05-এর কম্পাইলার পাইপলাইনের দ্বিতীয় ধাপ — লেক্সিং-এর ঠিক পরে, সিমান্টিক অ্যানালাইসিসের (M6) আগে।

পার্সিং করার দুটি মৌলিকভাবে ভিন্ন দিক আছে — টপ-ডাউন ও বটম-আপ — উভয়ই সঠিকভাবে একই পার্স ট্রি তৈরি করতে পারে, কিন্তু একদম বিপরীত ক্রমে সেই ট্রির নোডগুলো নির্মাণ/ভিজিট করে।

২ · টপ-ডাউন বনাম বটম-আপ

টপ-ডাউন (Top-down)
পার্স ট্রি রুট (স্টার্ট সিম্বল) থেকে শুরু করে নিচে leaves-এর (টোকেন) দিকে নির্মিত হয় — L13-এর leftmost derivation-এর সাথে সরাসরি সংগতিপূর্ণ। প্রতিটি ধাপে পার্সারকে "কোন প্রোডাকশন রুল প্রয়োগ করব" আন্দাজ/প্রেডিক্ট করতে হয় (L22, L23)।

বটম-আপ (Bottom-up)
leaves (টোকেন) থেকে শুরু করে উপরে রুটের দিকে নির্মিত হয় — L13-এর rightmost derivation বিপরীত ক্রমে-এর সাথে সংগতিপূর্ণ। ছোট ছোট চেনা অংশকে বারবার বড় নন-টার্মিনালে "reduce" করে (L24-L26)।

"2 + 3"-এর একই পার্স ট্রি — টপ-ডাউন রুট (E) থেকে শুরু করে leaves-এ নামে, বটম-আপ leaves (2, 3) থেকে শুরু করে রুটে (E) ওঠে। একদম বিপরীত ক্রম, একই গাছ।

৩ · সাধারণ Trade-off

কোনো একটি কৌশল সবসময় "ভালো" নয় — বাস্তব trade-off আছে —

সততার সাথে trade-off

টপ-ডাউন (বিশেষত recursive descent, L22): হাতে লেখা সহজ, বোঝা ও ডিবাগ করা সহজ — কিন্তু গ্রামারকে নির্দিষ্ট সীমাবদ্ধতা মানতে হয় (যেমন left recursion থাকা যাবে না — L22-এ বিস্তারিত)।

বটম-আপ (L24-L26): অনেক বড় ক্লাসের গ্রামার হ্যান্ডল করতে পারে, টপ-ডাউন যা পারে না তাও পারে — কিন্তু হাতে-কলমে তৈরি করা উল্লেখযোগ্যভাবে জটিল। বাস্তবে বটম-আপ পার্সার প্রায় সবসময় টুল দিয়ে জেনারেট করা হয় (parser generator, L26-এ বিস্তারিত), হাতে লেখা হয় না।

Python

# "2 + 3"-এর পার্স ট্রি, L14-এর নেস্টেড-টাপল স্টাইলে
# ('E', [('T', [('num','2')]), ('+',), ('T', [('num','3')])])
tree = ('E', [
    ('T', [('num', '2')]),
    ('+', []),
    ('T', [('num', '3')]),
])

def read_leftmost_derivation_order(node):
    """টপ-ডাউন: নোড নিজে আগে, তারপর বাম থেকে ডানে সন্তানরা (pre-order)।"""
    label, children = node
    order = [label]
    for child in children:
        order.extend(read_leftmost_derivation_order(child))
    return order

def read_rightmost_reduction_order(node):
    """বটম-আপ: বাম থেকে ডানে সন্তানরা আগে সম্পূর্ণ হয়, তারপর নোড নিজে (post-order)।"""
    label, children = node
    order = []
    for child in children:
        order.extend(read_rightmost_reduction_order(child))
    order.append(label)
    return order

td_order = read_leftmost_derivation_order(tree)
bu_order = read_rightmost_reduction_order(tree)

print("টপ-ডাউন (leftmost derivation) ভিজিট অর্ডার:")
print("  " + " -> ".join(td_order))

print("\nবটম-আপ (rightmost derivation বিপরীত ক্রমে) রিডিউস অর্ডার:")
print("  " + " -> ".join(bu_order))

print("\nএকই গাছ, বিপরীত নির্মাণ-ক্রম:", td_order != bu_order)
print("দুটোতেই একই নোড-সেট আছে:", sorted(td_order) == sorted(bu_order))

লক্ষ্য করুন read_leftmost_derivation_order (pre-order: নোড আগে, সন্তান পরে) এবং read_rightmost_reduction_order (post-order: সন্তান আগে, নোড পরে) — এই দুটো ক্লাসিক ট্রি-ট্রাভার্সাল অর্ডার (DSA কোর্স থেকে পরিচিত) হুবহু টপ-ডাউন ও বটম-আপ পার্সিং-এর নির্মাণ-ক্রমের সাথে মিলে যায়। কোড চালালে দুটো তালিকাই একই ৬টি নোড ধারণ করে (sorted(td_order) == sorted(bu_order) সত্য), কিন্তু ক্রম সম্পূর্ণ ভিন্ন — ঠিক যা প্রত্যাশিত।

মূল কথা · Key takeaway

টপ-ডাউন ও বটম-আপ পার্সিং একই লক্ষ্যে (একটি সঠিক পার্স ট্রি তৈরি করা) পৌঁছায়, কিন্তু সম্পূর্ণ বিপরীত দিক থেকে — একটি রুট থেকে leaves-এর দিকে predict করে, আরেকটি leaves থেকে রুটের দিকে recognize করে। এই দিকনির্দেশনার পার্থক্যই পরবর্তী ছয়টি পাঠের (L22-L27) প্রতিটি নির্দিষ্ট অ্যালগরিদমের ভিত্তি — recursive descent ও LL(1) টপ-ডাউন পরিবারে, shift-reduce, LR, ও LALR বটম-আপ পরিবারে।

ভাবনার প্রশ্ন

প্রতিটি প্রশ্ন নিজে কিছুক্ষণ ভাবুন — তারপর "→ উত্তর" চাপুন।

প্র ০১ "বটম-আপ পার্সিং L13-এর rightmost derivation-এর সাথে সংগতিপূর্ণ, কিন্তু বিপরীত ক্রমে" — এই "বিপরীত ক্রমে" কথাটির অর্থ কী, এবং এটি কেন গুরুত্বপূর্ণ?

একটি rightmost derivation স্টার্ট সিম্বল থেকে শুরু করে ধাপে ধাপে ডানদিকের নন-টার্মিনাল প্রতিস্থাপন করে শেষ পর্যন্ত টোকেন-স্ট্রিং-এ পৌঁছায় — এটি একটি "তৈরি করার" প্রক্রিয়া। বটম-আপ পার্সার আসলে বিপরীত কাজ করে: এটি টোকেন-স্ট্রিং থেকে শুরু করে ধাপে ধাপে reduce করে স্টার্ট সিম্বলে পৌঁছায় — এটি একটি rightmost derivation-এর ধাপগুলোই, কিন্তু শেষ থেকে প্রথম দিকে পড়া। এই সম্পর্কটি গুরুত্বপূর্ণ কারণ এটি প্রমাণ করে বটম-আপ পার্সিং কোনো ভিন্ন তাত্ত্বিক ভিত্তি ব্যবহার করছে না — এটি একই derivation ধারণার, শুধু বিপরীত দিক থেকে গণনা।

প্র ০২ কোড সেলে read_leftmost_derivation_order pre-order আর read_rightmost_reduction_order post-order ব্যবহার করে — কিন্তু দুটোই "বাম থেকে ডানে" সন্তান ভিজিট করে, "ডান থেকে বামে" নয়। rightmost derivation-এর নামে "right" থাকা সত্ত্বেও কেন?

"rightmost derivation" নামটি বোঝায় প্রতিটি ডেরিভেশন-ধাপে কোন নন-টার্মিনালটি পরবর্তীতে expand করা হয় (সবসময় সবচেয়ে-ডানের নন-টার্মিনাল) — এটি টোকেনগুলো কোন ক্রমে স্ট্রিং-এ চূড়ান্তভাবে আবির্ভূত হয় তা বদলায় না। একটি বৈধ প্রোগ্রামের টোকেনগুলো সবসময় বাম থেকে ডানেই পড়া হয় (এটি যেকোনো derivation strategy-তেই ধ্রুবক) — শুধু "কোন নন-টার্মিনাল আগে সমাধান হচ্ছে" তার ক্রমটাই leftmost বনাম rightmost-এ ভিন্ন হয়, যা reduce-অর্ডারে প্রতিফলিত হয়, leaf-পড়ার দিকে নয়।

প্র ০৩ বাস্তবে বেশিরভাগ প্রোগ্রামিং ল্যাঙ্গুয়েজ কম্পাইলার (যেমন GCC, Python-এর নিজস্ব পার্সার) recursive descent (টপ-ডাউন) ব্যবহার করে, যদিও বটম-আপ বেশি শক্তিশালী। কেন?

কারণ ব্যবহারিক বিবেচনায় "সর্বোচ্চ তাত্ত্বিক ক্ষমতা" সবসময় সবচেয়ে গুরুত্বপূর্ণ ফ্যাক্টর নয় (L04-এর ভাষা-ডিজাইন trade-off-এর মতোই একটি বাস্তবায়ন-ডিজাইন trade-off)। বেশিরভাগ বাস্তব প্রোগ্রামিং ল্যাঙ্গুয়েজের গ্রামার ইচ্ছাকৃতভাবে এমনভাবে ডিজাইন করা হয় যাতে টপ-ডাউন পার্সিং-এর সীমাবদ্ধতার মধ্যেই পড়ে (left recursion এড়িয়ে, L22-এর মতো রূপান্তর করে) — বিনিময়ে recursive descent-এর সরলতা, ভালো error message দেওয়ার ক্ষমতা, এবং হাতে-কলমে সহজে maintain করার সুবিধা পাওয়া যায়, যা একটি দীর্ঘমেয়াদী কম্পাইলার প্রজেক্টে বটম-আপের বাড়তি ক্ষমতার চেয়ে বেশি মূল্যবান হয়ে ওঠে।

অনুশীলন

হাতে করুন: কোড সেলের tree-এর জন্য হাতে-কলমে লিখুন টপ-ডাউন ভিজিট অর্ডার কী হবে এবং বটম-আপ রিডিউস অর্ডার কী হবে, তারপর কোড চালিয়ে মিলিয়ে দেখুন।

টপ-ডাউন: E -> T -> num -> + -> T -> num (রুট আগে, তারপর প্রতিটি সন্তান বাম থেকে ডানে, রিকার্সিভভাবে)। বটম-আপ: num -> T -> + -> num -> T -> E (প্রতিটি সাবট্রি সম্পূর্ণ নিচ থেকে ওঠার পর তবেই তার প্যারেন্ট, শেষে রুট E সবার শেষে)। কোড সেল চালিয়ে td_order/bu_order-এর সাথে মিলিয়ে দেখুন।
পরীক্ষা করুন: কোড সেলে tree-তে আরেকটি স্তর যোগ করুন — প্রথম ('T', [('num', '2')])-কে ('T', [('F', [('num', '2')])])-এ পরিবর্তন করে Run চাপুন। নতুন td_order-এ কী পরিবর্তন আসে?

নতুন টপ-ডাউন অর্ডার হবে E -> T -> F -> num -> + -> T -> num — একটি অতিরিক্ত F নোড মাঝে যোগ হয়েছে, কারণ pre-order ট্রাভার্সাল প্রতিটি অতিরিক্ত স্তরকেই রুট-থেকে-leaf ক্রমে ভিজিট করে। এটি সরাসরি দেখায় গ্রামারে একটি নতুন লেয়ার (যেমন L12-এর <factor> নন-টার্মিনাল) যোগ করলে টপ-ডাউন পার্সারের ভিজিট-অর্ডারে ঠিক একটি অতিরিক্ত ধাপ যোগ হয় — গ্রামারের গঠন সরাসরি পার্সিং-এর ধাপগুলোতে প্রতিফলিত হয়।