এই পর্বে যা শিখবেন
- যেকোনো CFG-তে leftmost আর rightmost derivation লেখা, আর একটি ভুল ধাপ চিনে ফেলা
- Parse tree-র formal definition, আংশিক গাছ আর yield-এর সঙ্গে sentential form-এর সম্পর্ক
- গাছ ⇔ leftmost ⇔ rightmost derivation সংযোগের প্রমাণের রূপরেখা, induction দিয়ে
- একটি গাছ থেকে কতগুলো derivation আসে তা গোনা, আর কেন “দুটি leftmost derivation” মানে দুটি গাছ
- Parse tree আর abstract syntax tree-র পার্থক্য, বাজারঘরের order-query-র আসল গাছসহ
১ · একটি string, অনেক derivation — কেন একটি মানক ক্রম দরকার
পর্ব ২৫-এ আপনি context-free grammar G = (V, Σ, R, S) আর তার derivation দেখেছেন: u ⇒ v মানে u-র কোনো একটি variable A-কে একটি নিয়ম A → α দিয়ে বদলানো। লক্ষ করুন, সংজ্ঞায় বলা নেই কোন variable বদলাতে হবে। একটি sentential form-এ তিনটি variable থাকলে আপনি যেকোনোটি আগে বদলাতে পারেন। “Context-free” কথাটির মানেই এটি: একটি variable-এর বদল তার পাশের অংশের ওপর নির্ভর করে না, তাই বদলের ক্রমও ফলাফলে কোনো প্রভাব ফেলে না।
বাজারঘরের গুদামে একটি বড় order প্যাক হচ্ছে। Order-টি ভাগ হয় তিনটি ব্যাগে: “চাল-ডাল”, “সবজি”, “মশলা”. প্রতিটি ব্যাগ আবার ভাগ হয় নির্দিষ্ট জিনিসে। দুজন কর্মী একই order প্যাক করলেন: একজন বাঁ থেকে ডানে, আগে চাল-ডালের ব্যাগ শেষ করে তারপর সবজি; আরেকজন আগে মশলার ব্যাগ, তারপর বাকি। কাজের ক্রম আলাদা, কিন্তু কোন ব্যাগে কী গেছে, সেই কাঠামো হুবহু এক। Derivation হলো কাজের ক্রম; parse tree হলো সেই কাঠামো, “কোন জিনিস কোন ব্যাগের ভেতরে”.
ছোট একটি উদাহরণ: S → AB, A → a, B → b. String “ab”-এর দুটি derivation আছে:
দুটিতেই একই তিনটি নিয়ম একবার করে খাটানো হয়েছে, শুধু দ্বিতীয় আর তৃতীয় ধাপের ক্রম উল্টো। বড় string-এ এই স্বাধীনতা দ্রুত বাড়ে। পর্ব ২৫-এর স্তরভাগ করা গাণিতিক expression-এর grammar ধরুন:
এখানে E (expression) যোগের স্তর, T (term) গুণের স্তর, আর F (factor) একটি id বা বন্ধনীর ভেতরের পুরো expression. String id+id∗id-এর কাঠামো একটিই, কিন্তু অংশ ৫-এ brute force দিয়ে গুনে দেখবেন, এর মোট ১০৫টি আলাদা derivation আছে। এতগুলো সমান-অর্থের ক্রম নিয়ে কাজ করা অসুবিধাজনক। প্রশ্ন ওঠে: “এই string-এর derivation কয়টি?” এর উত্তর ১০৫, কিন্তু আসলে আমরা জানতে চাই “এর কাঠামো কয়টি?” এর জন্য দুটি হাতিয়ার লাগে: একটি মানক ক্রম (leftmost বা rightmost), আর ক্রম-নিরপেক্ষ একটি ছবি (parse tree). এই পর্বের মূল উপপাদ্য দেখাবে, দুটি আসলে একই জিনিস।
২ · Leftmost আর rightmost derivation
G = (V, Σ, R, S) একটি CFG. u ⇒lm v (“u থেকে এক leftmost ধাপে v”) মানে u = xAy আর v = xαy, যেখানে A → α ∈ R, x ∈ Σ∗ (A-এর বাঁয়ে শুধু terminal) আর y ∈ (V ∪ Σ)∗. একইভাবে u ⇒rm v মানে u = xAy, v = xαy, যেখানে y ∈ Σ∗ (A-এর ডানে শুধু terminal). ⇒lm∗ আর ⇒rm∗ হলো এদের reflexive-transitive closure, অর্থাৎ শূন্য বা বেশি এমন ধাপ।
সংজ্ঞার মূল শর্ত x ∈ Σ∗: বদলানো variable-এর বাঁয়ে কোনো variable থাকতে পারবে না, তাই সেটি সবচেয়ে বাঁয়ের variable. প্রতিটি sentential form-এ সবচেয়ে বাঁয়ের variable একটিই, তাই leftmost derivation-এ প্রতি ধাপে একমাত্র স্বাধীনতা হলো “কোন নিয়ম”, “কোন জায়গা” নয়। ফলে একটি leftmost derivation পুরোপুরি বোঝা যায় শুধু নিয়মের ক্রম দিয়ে, যেমন “নিয়ম ১, ২, ৪, ৬, ৩, ৪, ৬, ৬”. অংশ ৭-এর JavaScript ব্লক ঠিক এভাবে নিয়মের নম্বরের তালিকা থেকে গাছ বানায়।
একটি সূক্ষ্ম কথা: leftmost derivation-এর প্রতিটি sentential form “terminal-এর একটি স্থির উপসর্গ, তারপর একটি variable, তারপর যা-খুশি” আকারের। স্থির উপসর্গটি আর কখনো বদলায় না। Top-down parser ঠিক এই ধর্ম কাজে লাগায়: input-এর বাঁ অংশ মিলে গেলে সেটি নিশ্চিত, এরপর শুধু ডানের দিকে এগোনো (পর্ব ৩৮-এ LL parsing). নিচের stepper id+id∗id-এর leftmost derivation দেখায়; প্রতিটি ধাপে কোন নিয়ম খাটল, তা বাঁয়ের তালিকায় আলো হয়ে ওঠে।
1E → E+T2E → T3T → T∗F4T → F5F → (E)6F → id
| sentential form | |
| বদলানো variable | |
| স্থির বাঁ অংশ |
- শুরু। E-তে একটিই variable. নিয়ম ১ (E → E+T): E ⇒lm E+T. Expression-এর সবচেয়ে বাইরের operation হলো যোগ, তাই এই grammar-এ শুরুতেই এই নিয়ম আসে।
- বাঁয়ের E. E+T-তে variable দুটি, E আর T; সবচেয়ে বাঁয়ের E. নিয়ম ২ (E → T): T+T. যোগের বাঁ অংশে আর কোনো যোগ নেই, তাই E সরাসরি T হলো।
- বাঁয়ের T. T+T-তে সবচেয়ে বাঁয়ের T. নিয়ম ৪ (T → F): F+T. বাঁ অংশে গুণও নেই।
- প্রথম terminal. নিয়ম ৬ (F → id): id+T. এখন বাঁয়ের “id+” স্থির, পরের কোনো ধাপ এটি আর ছোঁবে না।
- ডানের অংশ। একমাত্র variable এখন T. নিয়ম ৩ (T → T∗F): id+T∗F. গুণটি যোগের ডান অংশের ভেতরে ঢুকল; অর্থ দাঁড়াবে id + (id ∗ id).
- আবার সবচেয়ে বাঁয়ের। id+T∗F-তে variable T আর F; বাঁয়ের T. নিয়ম ৪: id+F∗F. ডানের F অপেক্ষা করছে, যদিও তাকেও এখনই বদলানো যেত; leftmost নিয়ম সেই স্বাধীনতা কেড়ে নেয়।
- দ্বিতীয় id. বাঁয়ের F → id: id+id∗F. স্থির অংশ এখন “id+id∗”.
- শেষ। শেষ F → id: id+id∗id. মোট ৮ ধাপ, নিয়মের ক্রম ১, ২, ৪, ৬, ৩, ৪, ৬, ৬. পর্ব ২৫-এর leftmost derivation-এর সঙ্গে হুবহু মেলে।
Rightmost derivation একই কাজ ডান দিক থেকে করে: E ⇒rm E+T ⇒rm E+T∗F ⇒rm E+T∗id ⇒ ⋯. এটি অংশ ৪-এ পূর্ণ দেখবেন। কেন দুটি ক্রমই দরকার? Top-down parser (LL) ওপর থেকে গাছ বানাতে গিয়ে স্বাভাবিকভাবেই leftmost derivation তৈরি করে। Bottom-up parser (LR) পাতা থেকে শুরু করে ওপরে ওঠে, আর তার প্রতিটি “reduce” ধাপ একটি rightmost derivation-কে উল্টো ক্রমে খুঁজে পায় (পর্ব ৩৯)। তত্ত্বের দিক থেকে দুটি ক্রমই সমান শক্তিশালী, উপপাদ্য ৪.১ তা প্রমাণ করবে।
সাধারণ ভুল: “leftmost মানে বাঁ থেকে প্রথম চিহ্ন বদলানো” ভাবা। Terminal কখনো বদলায় না; leftmost মানে সবচেয়ে বাঁয়ের variable. আরেকটি ভুল: অর্ধেক ধাপ leftmost আর অর্ধেক rightmost লিখে পুরোটাকে “leftmost derivation” বলা। একটি মাত্র ধাপ নিয়ম ভাঙলেই সেটি আর leftmost derivation নয়; অংশ ৮-এর Python ব্লক এমন ভুল ধাপ ধরে।
৩ · Parse tree আর yield
Derivation একটি ক্রম; parse tree সেই ক্রম ভুলে গিয়ে শুধু “কে কার থেকে এসেছে” রাখে। গাছের ধারণা আপনি ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৬৫-এ (rooted tree) আর পর্ব ৬৬-এ (expression tree) দেখেছেন; এখানে শুধু grammar-এর নিয়মের সঙ্গে গাছের মিলটি নিখুঁত করে লেখা হলো।
G = (V, Σ, R, S) একটি CFG আর A ∈ V. A-root-এর একটি parse tree হলো একটি ordered rooted tree (প্রতিটি node-এর সন্তানদের বাঁ-ডান ক্রম নির্দিষ্ট), যেখানে
১. root-এর লেবেল A;
২. প্রতিটি node-এর লেবেল V ∪ Σ ∪ {ε}-এর একটি চিহ্ন, আর প্রতিটি ভেতরের node-এর লেবেল একটি variable;
৩. কোনো ভেতরের node-এর লেবেল B আর তার সন্তানদের লেবেল বাঁ থেকে ডানে X1, …, Xk হলে B → X1⋯Xk একটি নিয়ম;
৪. কোনো পাতার লেবেল ε হলে সেটি তার বাবার একমাত্র সন্তান, আর বাবার নিয়মটি B → ε.
সব পাতা terminal বা ε হলে গাছটি সম্পূর্ণ; কোনো পাতা variable হলে গাছটি আংশিক। পাতাগুলোর লেবেল বাঁ থেকে ডানে জুড়ে পাওয়া string-কে বলে গাছের yield; ε-পাতা কিছুই যোগ করে না।
শর্ত ৩-ই আসল কথা: প্রতিটি ভেতরের node একটি নিয়ম-প্রয়োগ, আর তার সন্তানরা নিয়মের ডান দিক, একই ক্রমে। শর্ত ৪ একটি বিশেষ ক্ষেত্র সামলায়: B → ε নিয়মের ডান দিকে কোনো চিহ্ন নেই, তবু গাছে একটি ε-পাতা আঁকা হয়, যাতে বোঝা যায় B “খালি হয়ে গেছে”, পাতা হয়ে থেমে নেই। আংশিক গাছের yield-এ variable থাকতে পারে, তাই সেটি একটি sentential form. Derivation-এর মাঝপথের প্রতিটি sentential form আসলে মাঝপথের আংশিক গাছের yield; নিচের stepper-এ এটি নিজের চোখে দেখবেন।
নিচের ছবিতে id+id∗id-এর সম্পূর্ণ parse tree. প্রতিটি variable-node-এর দুই পাশে দুটি ছোট সংখ্যা: বাঁয়েরটি (নীল) বলছে leftmost derivation-এর কত নম্বর ধাপে এই node-এর নিয়ম খাটে, ডানেরটি (কমলা) rightmost derivation-এ কত নম্বর ধাপে। গাছ একটিই, দুটি ক্রম তার ভেতরের node-গুলো দুই রকম সারিতে ঘুরে দেখে।
id+id∗id-এর parse tree, দুই ক্রমের ধাপ-নম্বরসহ
নীল বৃত্ত variable, সবুজ terminal. বাঁয়ের নীল সংখ্যা leftmost ধাপ, ডানের কমলা সংখ্যা rightmost ধাপ। পাতা বাঁ থেকে ডানে: id + id ∗ id.
দুটি পর্যবেক্ষণ। প্রথমত, গাছে variable-node ৮টি, আর দুটি derivation-এরই ৮ ধাপ: প্রতিটি ধাপ ঠিক একটি variable-node-এর নিয়ম খাটায়। দ্বিতীয়ত, গাছে কোন নিয়ম কোথায় খাটল তা আছে, কিন্তু কখন খাটল তা নেই। এই “কখন” তথ্যটুকু বাদ দেওয়াই গাছের শক্তি। এবার উল্টো দিক থেকে দেখুন: leftmost derivation চলতে চলতে গাছটি কীভাবে ওপর থেকে নিচে গজায়।
| yield | |
| variable-পাতা |
- Root-এর নিয়ম। E → E+T: root-এর নিচে তিনটি সন্তান E, +, T. গাছের yield “E + T”, ঠিক derivation-এর প্রথম sentential form.
- সবচেয়ে বাঁয়ের variable-পাতা। বাঁয়ের E-পাতার নিচে একটি সন্তান T (নিয়ম E → T). Leftmost derivation মানে গাছে সবসময় সবচেয়ে বাঁয়ের variable-পাতাটি বাড়ানো।
- আরও নিচে। T-এর নিচে F (T → F). একটি সন্তানের শিকল E → T → F: যোগ নেই, গুণ নেই, শুধু একটি factor.
- প্রথম পাতা terminal. F-এর নিচে id. গাছের সবচেয়ে বাঁয়ের শাখা সম্পূর্ণ; yield “id + T”-এর “id +” আর বদলাবে না।
- ডানের শাখা। এবার বাঁ থেকে প্রথম variable-পাতা হলো root-এর ডান সন্তান T. তার নিচে T, ∗, F (T → T∗F). গুণ যোগের ডান শাখায় বসল।
- গুণের বাঁ অংশ। সবচেয়ে বাঁয়ের variable-পাতা এখন নতুন T; তার নিচে F. Yield “id + F ∗ F”.
- দ্বিতীয় id. সেই F-এর নিচে id. বাকি একটিই variable-পাতা, সবচেয়ে ডানের F.
- গাছ সম্পূর্ণ। শেষ F-এর নিচে id. সব পাতা terminal, yield id + id ∗ id. প্রতিটি ধাপে গাছের yield ছিল ঠিক সেই ধাপের sentential form, আর প্রতিটি ধাপ একটি নতুন variable-node “খুলেছে”, মোট ৮টি।
৪ · সংযোগের উপপাদ্য — গাছ ⇔ leftmost ⇔ rightmost
এতক্ষণ যা চোখে দেখলেন, এবার সেটি উপপাদ্য হিসেবে। এটি পুরো মডিউলের ভিত্তি: ambiguity-র সংজ্ঞা (পর্ব ২৭), CNF-এর গাছের উচ্চতার যুক্তি (পর্ব ২৯), CFL pumping lemma (পর্ব ৩৬) আর parsing algorithm (মডিউল ৭), সবই এর ওপর দাঁড়িয়ে।
G = (V, Σ, R, S) একটি CFG, A ∈ V আর w ∈ Σ∗. নিচের চারটি কথা সমতুল্য:
(ক) A ⇒∗ w;
(খ) A ⇒lm∗ w;
(গ) A ⇒rm∗ w;
(ঘ) root A আর yield w-এর একটি parse tree আছে।
তার ওপর, A-root আর yield w-এর parse tree-গুলোর set থেকে A থেকে w-এর leftmost derivation-গুলোর set-এ একটি bijection আছে (প্রতিটি গাছের ঠিক একটি leftmost derivation, আর প্রতিটি leftmost derivation ঠিক একটি গাছ থেকে আসে); rightmost derivation-এর ক্ষেত্রেও একই।
প্রমাণে একটি ছোট lemma বারবার লাগে, যা “context-free” শব্দটির গাণিতিক রূপ।
X1X2⋯Xk ⇒n w (ঠিক n ধাপে) হলে w = w1w2⋯wk লেখা যায়, যেখানে প্রতিটি i-তে Xi ⇒ni wi আর n1 + ⋯ + nk = n. (Xi terminal হলে ni = 0 আর wi = Xi.)
প্রমাণের রূপরেখা (lemma): n-এর ওপর induction. প্রতিটি ধাপ একটি variable বদলায়, আর সেই variable কোনো একটি Xi-এর “বংশধর” অংশের ভেতরে থাকে; বদলটি অন্য Xj-এর অংশ ছোঁয় না, কারণ নিয়ম পাশের চিহ্ন দেখে না। তাই প্রতিটি ধাপকে ঠিক একটি i-এর ঘরে ফেলা যায়, আর i-এর ঘরের ধাপগুলো ক্রম বজায় রেখে Xi ⇒∗ wi-এর একটি derivation. ∎
প্রমাণের রূপরেখা (উপপাদ্য ৪.১):
- (খ) ⇒ (ক) আর (গ) ⇒ (ক): প্রতিটি leftmost বা rightmost ধাপ একটি সাধারণ ধাপও। — সংজ্ঞা ২.১
- (ক) ⇒ (ঘ): derivation-এর দৈর্ঘ্য n-এর ওপর strong induction. প্রথম ধাপ A ⇒ X1⋯Xk, কোনো নিয়ম A → X1⋯Xk দিয়ে। বাকি n − 1 ধাপে lemma ৪.২ খাটিয়ে w = w1⋯wk, যেখানে প্রতিটি variable Xi ⇒∗ wi n − 1-এর কম বা সমান ধাপে। Induction-এ প্রতিটি variable Xi-এর জন্য root Xi আর yield wi-এর একটি গাছ আছে। A-root-এর নিচে এই গাছগুলো (আর terminal Xi-এর জন্য একটি পাতা; k = 0 হলে একটি ε-পাতা) বসালে root A, yield w1⋯wk = w. — lemma ৪.২ + induction hypothesis
- (ঘ) ⇒ (খ): গাছের উচ্চতার ওপর induction (structural induction). Root-এর নিয়ম A → X1⋯Xk, আর i-তম সন্তানের উপগাছের yield wi. Induction-এ প্রতিটি variable Xi ⇒lm∗ wi. এবার A ⇒lm X1⋯Xk, তারপর X1-এর leftmost derivation পুরোটা চালান, তারপর X2-এর, এভাবে। Xi-এর পালা আসার সময় তার বাঁয়ে শুধু w1⋯wi−1, অর্থাৎ terminal, তাই প্রতিটি ধাপ সত্যিই leftmost. — সংজ্ঞা ২.১-এর x ∈ Σ∗ শর্ত
- (ঘ) ⇒ (গ): একই যুক্তি আয়নায়: আগে Xk-এর rightmost derivation, তারপর Xk−1-এর, এভাবে বাঁয়ে। — প্রতিসাম্য
- Bijection: ধাপ ৩-এর গঠন প্রতিটি গাছ থেকে একটি নির্দিষ্ট leftmost derivation দেয়। উল্টো দিকে, একটি leftmost derivation থেকে গাছটি ধাপে ধাপে পুনর্গঠন করা যায়: প্রতিটি ধাপ সবচেয়ে বাঁয়ের variable-পাতায় তার নিয়মের সন্তান বসায় (অংশ ৩-এর stepper). Leftmost ধাপে জায়গা বাছার স্বাধীনতা নেই, তাই দুটি আলাদা leftmost derivation প্রথম যে ধাপে আলাদা হয়, সেখানে একই node-এ আলাদা নিয়ম খাটায়, ফলে গাছ আলাদা। দুটি মানচিত্র একে অপরের উল্টো। ∎ — ধাপ ৩ আর পুনর্গঠন
একটি তাৎক্ষণিক ফল: grammar-টিকে ambiguous বলা হয়, যদি কোনো string-এর দুটি আলাদা parse tree থাকে। Bijection-এর কারণে এটি “কোনো string-এর দুটি আলাদা leftmost derivation আছে” বা “দুটি আলাদা rightmost derivation আছে” বলার সমান। কিন্তু “দুটি আলাদা derivation আছে” বলার সমান নয়: S → AB-এর “ab”-এরই দুটি derivation ছিল, অথচ গাছ একটি। পূর্ণ আলোচনা পর্ব ২৭-এ।
এবার একই গাছের rightmost derivation, stepper-এ। ছবি ২৬.১-এর কমলা সংখ্যাগুলো ধাপের ক্রম মিলিয়ে দেখতে পারেন।
1E → E+T2E → T3T → T∗F4T → F5F → (E)6F → id
| sentential form | |
| বদলানো variable | |
| স্থির ডান অংশ |
- প্রথম ধাপ একই। E ⇒rm E+T. Root-এর নিয়ম যেকোনো ক্রমেই প্রথমে খাটে, কারণ বাকি সব node তার বংশধর।
- এবার ডানের দিক। E+T-তে সবচেয়ে ডানের variable T. নিয়ম ৩: E+T∗F. Leftmost-এ এই নিয়ম এসেছিল ৫ নম্বর ধাপে, এখানে ২ নম্বরে।
- সবচেয়ে ডানের F. E+T∗F-তে ডানের variable F. নিয়ম ৬: E+T∗id. String-এর শেষ “∗id” এখন স্থির; rightmost derivation-এ ডান অংশ আগে পাকা হয়।
- T নামল F-এ। E+T∗id-এ সবচেয়ে ডানের variable T. নিয়ম ৪: E+F∗id.
- ডান শাখা সম্পূর্ণ। F → id: E+id∗id. Root-এর ডান সন্তানের পুরো উপগাছ শেষ, অথচ বাঁ সন্তান E এখনো ছোঁয়াই হয়নি।
- বাঁ শাখা। একমাত্র variable E. নিয়ম ২: T+id∗id.
- আরও নিচে। T → F: F+id∗id.
- শেষ। F → id: id+id∗id. আট ধাপ, নিয়মের ক্রম ১, ৩, ৬, ৪, ৬, ২, ৪, ৬: leftmost-এর একই আটটি নিয়ম, অন্য ক্রমে। দুই derivation-এর মাঝপথের রূপের মধ্যে মিল শুধু প্রথম রূপ E+T-এ।
গাছ থেকে derivation বের করার কাজটি যান্ত্রিক, তাই কোডে লেখা যায়। নিচের ব্লকে parse tree একটি Python tuple: (লেবেল, [সন্তানরা]), আর পাতা একটি সাধারণ string. derive function একটি তালিকা রাখে, যাতে কিছু terminal আর কিছু “এখনো না-খোলা” node; প্রতি ধাপে সবচেয়ে বাঁয়ের (বা ডানের) node-টিকে তার সন্তানদের দিয়ে বদলায়। এটি উপপাদ্যের প্রমাণের ধাপ ৩ আর ৪ হুবহু।
# A parse tree is (label, [children]); a leaf is a plain string.
def N(label, *kids): return (label, list(kids))
T = N("E", N("E", N("T", N("F", "id"))), "+",
N("T", N("T", N("F", "id")), "*", N("F", "id")))
def yield_(t):
if isinstance(t, str): return t
return "".join(yield_(c) for c in t[1])
def derive(tree, rightmost=False):
"""Expand the leftmost (or rightmost) unexpanded node, step by step."""
form, steps = [tree], []
while True:
idx = [i for i, x in enumerate(form) if not isinstance(x, str)]
if not idx: return steps
i = idx[-1] if rightmost else idx[0]
form = form[:i] + form[i][1] + form[i + 1:]
steps.append("".join(x if isinstance(x, str) else x[0] for x in form))
def show(name, steps):
print(f"{name} ({len(steps)} steps):")
print(" E => " + "\n => ".join(steps))
lm, rm = derive(T), derive(T, rightmost=True)
show("leftmost", lm)
show("rightmost", rm)
print("yield:", yield_(T), "| same end:", lm[-1] == rm[-1] == yield_(T))
print("shared middle forms:", set(lm[:-1]) & set(rm[:-1]))আসল আউটপুট (ব্রাউজারের Python):
leftmost (8 steps):
E => E+T
=> T+T
=> F+T
=> id+T
=> id+T*F
=> id+F*F
=> id+id*F
=> id+id*id
rightmost (8 steps):
E => E+T
=> E+T*F
=> E+T*id
=> E+F*id
=> E+id*id
=> T+id*id
=> F+id*id
=> id+id*id
yield: id+id*id | same end: True
shared middle forms: {'E+T'}
দুটি তালিকা stepper দুটির সঙ্গে হুবহু মেলে: আটটি করে ধাপ, শেষ string একই আর গাছের yield-এর সমান। শেষ লাইন বলছে, শেষ string বাদে দুই derivation-এর মধ্যে অভিন্ন sentential form শুধু E+T. অর্থাৎ একই গাছের দুটি মানক derivation মাঝপথে প্রায় সম্পূর্ণ আলাদা পথে হাঁটে, অথচ উপপাদ্য ৪.১ বলছে দুটি একই কাঠামো পড়ার দুই রকম উপায়। T-এর জায়গায় (id+id)∗id-এর গাছ বসিয়ে দেখুন (অনুশীলন ৪)। কোডে গুণের চিহ্ন *, লেখায় ∗; দুটি একই চিহ্ন।
৫ · কতগুলো derivation, কতগুলো গাছ
উপপাদ্য ৪.১ বলছে প্রতিটি গাছের leftmost derivation একটিই। কিন্তু মোট derivation কয়টি? একটি derivation মানে গাছের variable-node-গুলোকে কোনো এক ক্রমে “খোলা”, এই শর্তে যে বাবা সবসময় সন্তানের আগে খোলে (সন্তান তো বাবা খোলার পরেই জন্মায়)। এমন প্রতিটি ক্রম গাছের node-গুলোর partial order-এর একটি linear extension, আর আলাদা ক্রম মানে আলাদা derivation. Rooted tree-র ক্ষেত্রে এদের সংখ্যার একটি পরিচিত সূত্র আছে (tree-র hook length সূত্র নামে পরিচিত): m-টি variable-node থাকলে
derivation-এর সংখ্যা = m! ⁄ ∏v s(v)
যেখানে গুণফলটি প্রতিটি variable-node v-এর ওপর, আর s(v) হলো v-root-এর উপগাছে variable-node-এর সংখ্যা (v-সহ)। কেন: সব m! ক্রমের মধ্যে, প্রতিটি v-এর উপগাছের s(v)-টি node-এর মধ্যে v-কে প্রথম হতে হবে, যার সম্ভাবনা 1/s(v), আর এই শর্তগুলো পরস্পর স্বাধীন। ছবি ২৬.১-এর গাছে s-এর মান: root 8, বাঁয়ের E 3, তার নিচের T 2, F 1, ডানের T 4, তার নিচের T 2, আর দুটি F 1 করে। গুণফল 8 · 3 · 2 · 1 · 4 · 2 · 1 · 1 = 384, আর 8! / 384 = 40320 / 384 = 105.
সূত্রটি একটি দাবি; নিচের ব্লকটি grammar থেকে সরাসরি brute force-এ গুনে দাবিটি পরীক্ষা করে। ways(form) গোনে sentential form থেকে লক্ষ্য string-এ পৌঁছানোর কতগুলো আলাদা derivation আছে: প্রতিটি variable-এর প্রতিটি জায়গা আর প্রতিটি নিয়ম চেষ্টা করে। এই দুই grammar-এ ε-নিয়ম নেই, তাই sentential form কখনো ছোট হয় না; লক্ষ্যের চেয়ে লম্বা form বাদ দেওয়া নিরাপদ। leftmost_only হলে শুধু সবচেয়ে বাঁয়ের variable. দুটি grammar: পর্ব ২৫-এর স্তরভাগ করা grammar (layered) আর এক-স্তরের E → E+E ∣ E∗E ∣ (E) ∣ id (flat).
from functools import lru_cache
# Grammars as {variable: [right-hand sides as tuples]}; no ε-rules here,
# so a sentential form never gets shorter than it is: a safe length bound.
LAYERED = {"E": [("E", "+", "T"), ("T",)], "T": [("T", "*", "F"), ("F",)],
"F": [("(", "E", ")"), ("id",)]}
FLAT = {"E": [("E", "+", "E"), ("E", "*", "E"), ("(", "E", ")"), ("id",)]}
def count(G, w, leftmost_only):
@lru_cache(maxsize=None)
def ways(form): # derivations form =>* w
if len(form) > len(w): return 0
spots = [i for i, X in enumerate(form) if X in G]
if not spots: return int(form == w)
if leftmost_only: # terminal prefix must already match
k = spots[0]
if form[:k] != w[:k]: return 0
spots = spots[:1]
return sum(ways(form[:i] + rhs + form[i + 1:])
for i in spots for rhs in G[form[i]])
return ways(("E",))
for w in ["id+id*id", "id+id+id", "(id+id)*id"]:
toks = tuple(w.replace("id", " id ").replace("+", " + ").replace(
"*", " * ").replace("(", " ( ").replace(")", " ) ").split())
for name, G in [("layered", LAYERED), ("flat", FLAT)]:
print(f"{w:11} {name:8} all: {count(G, toks, False):5}"
f" leftmost: {count(G, toks, True)}")আসল আউটপুট (ব্রাউজারের Python):
id+id*id layered all: 105 leftmost: 1
id+id*id flat all: 16 leftmost: 2
id+id+id layered all: 280 leftmost: 1
id+id+id flat all: 16 leftmost: 2
(id+id)*id layered all: 90 leftmost: 1
(id+id)*id flat all: 10 leftmost: 1
প্রথম লাইনে brute force-এর ১০৫ সূত্রের ১০৫-এর সঙ্গে মিলেছে, আর leftmost derivation একটিই: স্তরভাগ করা grammar-এ এই string-এর গাছ একটি। Flat grammar-এ id+id∗id-এর leftmost derivation দুটি, তাই উপপাদ্য ৪.১ অনুযায়ী গাছও দুটি: একটিতে যোগ ওপরে (id + (id ∗ id)), অন্যটিতে গুণ ওপরে ((id + id) ∗ id). প্রতিটি গাছে ৫টি variable-node, সূত্রে 5! / (5 · 1 · 3 · 1 · 1) = 8, দুই গাছে 16, ঠিক যা ছাপা হয়েছে। id+id+id-এও flat grammar-এর দুটি গাছ (যোগের বাঁ বা ডান দিকে জোড়া)। বন্ধনী থাকলে flat grammar-এও গাছ একটি, শেষ লাইন দেখুন। খেয়াল করুন, মোট derivation-এর সংখ্যা দিয়ে ambiguity বোঝা যায় না: layered-এর ২৮০টি derivation একটি গাছের, flat-এর ১৬টি দুটি গাছের। গোনার ঠিক একক হলো leftmost derivation বা গাছ।
গাছ গোনার প্রশ্নটি নিজেই গুরুত্বপূর্ণ। Flat grammar-এ id-এর মাঝে n-টি “+” থাকলে গাছের সংখ্যা n-তম Catalan সংখ্যা (1, 1, 2, 5, 14, …), যা খুব দ্রুত বাড়ে; সংখ্যাগুলো ডিসক্রিট ম্যাথমেটিক্স কোর্সের পর্ব ৫০-এ পাবেন, আর brute force দিয়ে যাচাই পর্ব ২৭-এ। বাস্তবের parser কেন এত গাছ একসঙ্গে রাখতে পারে, তা ভাবনার প্রশ্ন ৪-এ।
৬ · Parse tree বনাম abstract syntax tree — lark দিয়ে সত্যিকারের run
এতক্ষণের গাছ হাতে বানানো। এবার একটি আসল parser. lark হলো একটি Python parser library (MIT licence), যা grammar-এর একটি লেখা file থেকে parser বানায়। এর Earley parser যেকোনো CFG মেনে নেয়, left-recursive নিয়মসহ (E → E+T-এর মতো, যেখানে নিয়মের ডান দিক নিজের variable দিয়েই শুরু)। lark-এর grammar-রীতি EBNF-এর মতো: নিয়মের নাম ছোট হাতের, “:” মানে →, terminal উদ্ধৃতিতে বা বড় হাতের নামে (ID). কোনো network বা usage-reporting কোড library-তে নেই, তা scratch-এ খুঁজে দেখা হয়েছে। ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে script-টির প্রথম অংশ:
from lark import Lark, __version__
import sys
print("lark", __version__, "| Python", sys.version.split()[0])
# 1) Full parse tree: every rule shown, every token kept
expr = r"""
e: e "+" t | t
t: t "*" f | f
f: "(" e ")" | ID
ID: "id"
%ignore " "
"""
full = Lark(expr, start="e", parser="earley", keep_all_tokens=True)
print("== parse tree: id+id*id")
print(full.parse("id+id*id").pretty())
# 2) AST-style: '?' inlines single-child rules, '->' names the operation
ast_g = r"""
?e: e "+" t -> add | t
?t: t "*" f -> mul | f
?f: "(" e ")" | ID
ID: "id"
%ignore " "
"""
ast = Lark(ast_g, start="e", parser="earley")
print("== AST: id+id*id")
print(ast.parse("id+id*id").pretty())
print("== AST: (id+id)*id")
print(ast.parse("(id+id)*id").pretty())সত্যিকারের run (ডেস্কটপ, lark 1.3.1, Python 3.12.13; শেষের order-query অংশ অংশ ৭-এ):
~/bazarghar-toc$ uv run python trees.py
lark 1.3.1 | Python 3.12.13
== parse tree: id+id*id
e
e
t
f id
+
t
t
f id
*
f id
== AST: id+id*id
add
id
mul
id
id
== AST: (id+id)*id
mul
add
id
id
id
…
.pretty() গাছটিকে indentation দিয়ে ছাপে: প্রতিটি লাইন একটি node, এক ধাপ ডানে সরা মানে সন্তান। একটিমাত্র terminal-সন্তান থাকলে lark সেটি বাবার পাশেই লেখে (f id মানে F-এর একমাত্র সন্তান id). প্রথম গাছটি ছবি ২৬.১-এর গাছ হুবহু: root e-এর তিন সন্তান e, +, t; বাঁয়ের e → t → f → id শিকল; ডানের t-এর নিচে t, ∗, f. keep_all_tokens=True না দিলে lark “+” আর “∗”-এর মতো উদ্ধৃতির terminal বাদ দিত। দ্বিতীয় আর তৃতীয় গাছ AST-ধাঁচের: নিয়মের সামনে ? থাকলে এক-সন্তানের node মুছে সন্তানকে সরাসরি ওপরে তোলে, আর -> add node-এর নাম বদলে operation-এর নাম দেয়। (id+id)∗id-এর AST-এ বন্ধনী নেই, তবু গাছের আকারই বলছে যোগ আগে: mul-এর বাঁ সন্তান add.
এখানেই দুই রকম গাছের পার্থক্য। Parse tree (একে concrete syntax tree-ও বলে) grammar-এর প্রতিটি নিয়ম-প্রয়োগ রাখে: E → T → F-এর শিকল, বন্ধনী, প্রতিটি token. এটি grammar-এর প্রতি বিশ্বস্ত, তাই উপপাদ্য ৪.১ এর জন্যই খাটে। Abstract syntax tree (AST) শুধু অর্থ বহনকারী অংশ রাখে: কোন operation, কোন operand. Grammar বদলালেও (ধরুন স্তরের নাম বদলালেন, বা নতুন একটি স্তর যোগ করলেন) একই অর্থের expression-এর AST একই থাকে। Compiler-এর পরের ধাপগুলো (type checking, code তৈরি) AST-এর ওপর কাজ করে।
| বিষয় | Parse tree | AST |
|---|---|---|
| ভেতরের node | grammar-এর variable (E, T, F) | operation (add, mul) |
| এক-সন্তানের শিকল | থাকে (E → T → F) | মুছে যায় |
| বন্ধনী আর keyword | পাতা হিসেবে থাকে | সাধারণত বাদ; অর্থ গাছের আকারে |
| yield | ঠিক মূল token-ক্রম | মূল string ফেরত দেয় না |
| কোথায় কাজে লাগে | তত্ত্ব, ambiguity, formatter | হিসাব, type checking, compiler |
৭ · বাজারঘরের order-query-র parse tree
পর্ব ২২-এর lexer বাজারঘরের query লাইনকে token-এ ভাঙে, আর পর্ব ২৫-এ তার grammar লেখা হয়েছে: Q → FIND order WHERE C, C → C OR T ∣ T, T → T AND F ∣ F, F → ( C ) ∣ amount R NUM ∣ district = STR ∣ status = STR, R → = ∣ >= ∣ <. একই grammar lark-এর রীতিতে, AST-ধাঁচে, একই script-এর শেষ অংশে:
# 3) Bazarghar order query (tokens as in lesson 25)
q = r"""
query: "FIND" "order" "WHERE" cond
?cond: cond "OR" term -> or_ | term
?term: term "AND" fact -> and_ | fact
?fact: "(" cond ")"
| "amount" REL NUM -> amount
| "district" "=" STR -> district
| "status" "=" STR -> status
REL: ">=" | "=" | "<"
NUM: /[0-9]+/
STR: /"[^"]*"/
%ignore " "
"""
qp = Lark(q, start="query", parser="earley")
s = 'FIND order WHERE amount >= 1000 AND district = "Dhaka"'
print("==", s)
print(qp.parse(s).pretty())
try:
qp.parse('FIND order WHERE amount >= 1000 AND')
except Exception as ex:
print("== error:", type(ex).__name__)সত্যিকারের run (একই প্রকল্প, একই run-এর শেষ অংশ):
== FIND order WHERE amount >= 1000 AND district = "Dhaka"
query
and_
amount
>=
1000
district "Dhaka"
== error: UnexpectedEOF
গাছটি পড়ুন: root query-র একমাত্র অর্থপূর্ণ সন্তান and_, যার দুই সন্তান দুটি শর্ত। FIND, order, WHERE, AND আর “=” নেই, কারণ উদ্ধৃতির terminal lark নিজে থেকেই বাদ দেয়; থাকে শুধু নাম-দেওয়া terminal (REL, NUM, STR)-এর মান। এখানে lark lexer আর parser একসঙ্গে চালিয়েছে, তাই NUM-এর আসল মান 1000 আর STR-এর মান "Dhaka" পাতায় দেখা যাচ্ছে। দ্বিতীয় query AND-এর পরেই শেষ: grammar অনুযায়ী এখানে একটি শর্ত আসার কথা ছিল, তাই parser UnexpectedEOF (input অসময়ে শেষ) জানিয়েছে। “FIND order WHERE amount >= 1000 AND” string-টি language-এর কোনো string-এর prefix, কিন্তু নিজে language-এ নেই।
এবার উল্টো দিক থেকে: leftmost derivation দিলে গাছটি কেমন? নিচের JavaScript ব্লক পর্ব ২৫-এর token-grammar নেয়, আর প্রতিটি ধাপে কোন নিয়ম খাটবে তার নম্বরের একটি তালিকা (প্রতিটি variable-এর নিয়ম ০ থেকে গোনা)। অংশ ২-এ দেখেছেন, leftmost derivation-এ জায়গা বাছার দরকার নেই, তাই নিয়মের নম্বরই যথেষ্ট। Program প্রতিটি ধাপে সবচেয়ে বাঁয়ের না-খোলা variable-পাতায় সন্তান বসায় (অংশ ৩-এর stepper-এর কাজ), প্রতিটি sentential form ছাপে, শেষে গাছটি লেখা-আকারে আঁকে।
// Leftmost derivation -> parse tree. You give the rule number used at
// each step; the program grows the tree and draws it as text.
const G = {
Q: [["FIND", "order", "WHERE", "C"]],
C: [["C", "OR", "T"], ["T"]],
T: [["T", "AND", "F"], ["F"]],
F: [["(", "C", ")"], ["amount", "R", "NUM"],
["district", "=", "STR"], ["status", "=", "STR"]],
R: [["="], [">="], ["<"]],
};
function build(start, choices) {
const root = { sym: start, kids: null };
let frontier = [root]; // leaves, left to right
for (const c of choices) {
const i = frontier.findIndex(n => n.sym in G && !n.kids);
const node = frontier[i];
node.kids = G[node.sym][c].map(s => ({ sym: s, kids: null }));
frontier = [...frontier.slice(0, i), ...node.kids, ...frontier.slice(i + 1)];
console.log("=>", frontier.map(n => n.sym).join(" "));
}
return root;
}
function draw(n, pre = "", last = true, top = true) {
console.log(top ? n.sym : pre + (last ? "└─ " : "├─ ") + n.sym);
const p = top ? "" : pre + (last ? " " : "│ ");
(n.kids || []).forEach((k, j) => draw(k, p, j === n.kids.length - 1, false));
}
// FIND order WHERE amount >= NUM AND district = STR
const tree = build("Q", [0, 1, 0, 1, 1, 1, 2]);
draw(tree);আসল আউটপুট (ব্রাউজারের JavaScript):
=> FIND order WHERE C
=> FIND order WHERE T
=> FIND order WHERE T AND F
=> FIND order WHERE F AND F
=> FIND order WHERE amount R NUM AND F
=> FIND order WHERE amount >= NUM AND F
=> FIND order WHERE amount >= NUM AND district = STR
Q
├─ FIND
├─ order
├─ WHERE
└─ C
└─ T
├─ T
│ └─ F
│ ├─ amount
│ ├─ R
│ │ └─ >=
│ └─ NUM
├─ AND
└─ F
├─ district
├─ =
└─ STR
সাতটি নিয়ম-নম্বর, সাতটি ধাপ, আর গাছে সাতটি variable-node (Q, C, দুটি T, দুটি F, R). এটি পূর্ণ parse tree: সব keyword, C → T-এর শিকল, সবই আছে। lark-এর AST-এর সঙ্গে মেলান: সেখানে Q, C আর বাইরের T-এর শিকল মুছে গিয়ে শুধু and_ রয়ে গিয়েছিল, আর এখানে AND-এর node হলো T → T AND F. তালিকার তৃতীয় সংখ্যা 0-কে 1 করলে কী হয়? তখন T → F, গাছে AND-এর শাখাই জন্মায় না, query দাঁড়ায় শুধু “amount >= NUM”, আর শেষ নম্বরের জন্য কোনো variable বাকি থাকে না বলে program একটি error দেয়। একটি নম্বর বদলালে পুরো গাছ বদলায়; উপপাদ্য ৪.১-এর bijection ঠিক এটিই বলে। নিজে একটি OR-সহ query-র নম্বর-তালিকা বানিয়ে দেখুন। নিয়ম বাকি থাকতে তালিকা শেষ হলে গাছ আংশিক থাকে, আর শেষ লাইনটি তখন একটি sentential form.
লক্ষ করুন, AND-এর node C → T-এর নিচে, অর্থাৎ OR-এর স্তরের নিচে। “a OR b AND c” লিখলে গাছে AND নিচে বসবে, তাই অর্থ a OR (b AND c). Database-এ query চালানোর সময় বাজারঘরের সিস্টেম এই গাছ নিচ থেকে ওপরে হিসাব করবে: আগে প্রতিটি শর্ত, তারপর AND, তারপর OR. গাছের আকারই অর্থ ঠিক করে, তাই grammar-এর নকশায় স্তর বসানো এত জরুরি (পর্ব ২৭)।
আরও গভীরে: একটি CFG-এর সব parse tree-র set নিজেই একটি “গাছের language”, আর এটি একটি regular tree language: এমন একটি tree automaton আছে, যা নিচ থেকে ওপরে সসীম state নিয়ে গাছ পড়ে চেনে। উল্টো দিকে, যেকোনো regular tree language-এর গাছগুলোর yield নিলে ঠিক একটি context-free language পাওয়া যায়। এই ধারার ফলাফল ১৯৬০-এর দশকের শেষে James Thatcher, Jesse Wright, John Doner প্রমুখের কাজ থেকে এসেছে বলে পরিচিত; XML-এর schema-ভাষার তত্ত্ব আর program transformation-এ tree automaton আজও ব্যবহৃত। বিস্তারিত জানতে Comon প্রমুখের মুক্ত বই “Tree Automata Techniques and Applications” দেখুন।
পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:
- id+id∗id-এর leftmost ও rightmost derivation আর parse tree দিন (E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id). অংশ ২ আর ৪-এর দুটি stepper; গাছ ছবি ২৬.১.
- Parse tree-র yield কী? পাতাগুলোর লেবেল বাঁ থেকে ডানে জুড়ে পাওয়া string, ε-পাতা বাদ দিয়ে।
- একটি string-এর দুটি derivation থাকলেই কি grammar ambiguous? না; দুটি আলাদা leftmost derivation (বা দুটি গাছ) লাগে।
- Derivation-এর ধাপের সংখ্যা আর গাছের কী সমান? গাছের variable-node-এর সংখ্যা।
- Parse tree আর AST-এর পার্থক্য কী? Parse tree সব নিয়ম আর token রাখে; AST শুধু operation আর operand.
৮ · AI-এর যুগে derivation আর parse tree
“id+id∗id-এর rightmost derivation দাও” জাতীয় প্রশ্নে AI assistant প্রায় সবসময় একটি পরিচ্ছন্ন তালিকা দেয়। সমস্যা হলো, তালিকার মাঝের একটি ধাপ প্রায়ই নিয়ম ভাঙে: কখনো সবচেয়ে ডানের বদলে অন্য একটি variable বদলায়, কখনো এক লাইনে দুটি ধাপ একসঙ্গে লেখে। চোখে ধরা কঠিন, কারণ শেষ string ঠিকই আসে। নিচের ব্লক প্রতিটি ধাপ পরীক্ষা করে: আগের রূপ থেকে পরের রূপ কি ঠিক একটি নিয়মে আসে, আর বদলানো variable কি সত্যিই সবচেয়ে ডানের (বা বাঁয়ের)? প্রথম তালিকাটি একটি নমুনা ভুল উত্তর, যেমনটি AI প্রায়ই দেয়।
# Check a claimed derivation, step by step. Symbols are separated by spaces.
G = {"E": ["E + T", "T"], "T": ["T * F", "F"], "F": ["( E )", "id"]}
RULES = [(A, tuple(r.split())) for A, rs in G.items() for r in rs]
def step_kinds(u, v):
"""All ways u => v in one step; returns positions of the replaced variable."""
u, v, hits = u.split(), v.split(), []
for i, X in enumerate(u):
for A, rhs in RULES:
if X == A and u[:i] + list(rhs) + u[i + 1:] == v:
hits.append(i)
return u, hits
def check(forms, mode):
print(f"claimed {mode} derivation of '{forms[-1]}':")
for k in range(1, len(forms)):
u, hits = step_kinds(forms[k - 1], forms[k])
vars_ = [i for i, X in enumerate(u) if X in G]
want = vars_[0] if mode == "leftmost" else vars_[-1]
if not hits:
print(f" step {k}: NOT a single rule step"); return
if want not in hits:
print(f" step {k}: valid step, but not {mode}"); return
print(f" all {len(forms) - 1} steps OK")
ai_claim = ["E", "E + T", "E + T * F", "T + T * F", "T + T * id",
"F + T * id", "F + F * id", "id + F * id", "id + id * id"]
check(ai_claim, "rightmost")
fixed = ["E", "E + T", "E + T * F", "E + T * id", "E + F * id",
"E + id * id", "T + id * id", "F + id * id", "id + id * id"]
check(fixed, "rightmost")
check(["E", "E + T", "T + T", "T + F", "id + id"], "leftmost")আসল আউটপুট (ব্রাউজারের Python):
claimed rightmost derivation of 'id + id * id':
step 3: valid step, but not rightmost
claimed rightmost derivation of 'id + id * id':
all 8 steps OK
claimed leftmost derivation of 'id + id':
step 3: valid step, but not leftmost
নমুনা উত্তরের তৃতীয় ধাপে E+T∗F থেকে T+T∗F: বাঁয়ের E বদলেছে, অথচ ডানে তখনো T আর F বাকি। ধাপটি grammar-এর একটি বৈধ ধাপ, শেষ string-ও ঠিক, তাই উত্তরটি একটি সঠিক derivation; শুধু “rightmost” দাবিটি মিথ্যা। দ্বিতীয় তালিকা অংশ ৪-এর stepper-এর derivation, আটটি ধাপই ঠিক। তৃতীয় তালিকায় T+T থেকে T+F: ডানের T বদলেছে, তাই leftmost নয়। Checker প্রথম ভুল ধাপে থামে; ওই তালিকার পরের ধাপ T+F থেকে id+id এক ধাপে দুটি variable বদলায়, সেটিও ভুল। তালিকাগুলো বদলে নিজের হাতে লেখা derivation পরীক্ষা করুন।
| AI-এর সাধারণ ভুল | কীভাবে ধরবেন |
|---|---|
| “Rightmost” derivation-এর মাঝে একটি leftmost বা এলোমেলো ধাপ | ওপরের checker চালান, বা প্রতিটি ধাপে “বদলানো variable-এর ডানে শুধু terminal?” প্রশ্নটি করুন |
| এক লাইনে দুটি নিয়ম একসঙ্গে খাটানো | দুই লাইনের পার্থক্য ঠিক একটি variable-এর বদল কি না দেখুন; ধাপের সংখ্যা গাছের variable-node-এর সমান কি না গুনুন |
| Parse tree-তে সন্তানের ক্রম উল্টো, বা ε-পাতা বাদ | প্রতিটি node-এর সন্তানদের বাঁ থেকে ডানে পড়ে নিয়মের ডান দিকের সঙ্গে মেলান; yield মূল string কি না দেখুন |
| “দুটি derivation আছে, তাই grammar ambiguous” | দুটি leftmost derivation বা দুটি গাছ চাই; count_derivations.py-র মতো leftmost সংখ্যা গুনুন |
| AST-কে parse tree বলা, বা উল্টো | গাছে grammar-এর variable আর বন্ধনী আছে কি না দেখুন; উপপাদ্য ৪.১ শুধু parse tree-র জন্য |
| বানানো ইতিহাস বা রেফারেন্স (যেমন LR parsing-এর সাল) | Sipser বা Hopcroft–Motwani–Ullman-এ নিজে খুঁজে দেখুন; মূল প্রবন্ধের নাম আর সাল মিলিয়ে নিন |
AI-কে ভালোভাবে কাজে লাগানোর উপায়: derivation-এর সঙ্গে প্রতিটি ধাপের ব্যাখ্যা আর একটি যাচাইয়ের কোড চাওয়া, যা আপনি নিজে চালাবেন।
(নিজে যাচাই করুন: সঠিক উত্তরে দুটি derivation-ই ১১ ধাপের, কারণ গাছে ১১টি variable-node; অনুশীলন ৪-এ পূর্ণ তালিকা আছে।)
AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।
প্র ০১Parser-এর জগতে “LL” আর “LR” নাম দুটির সঙ্গে leftmost আর rightmost derivation-এর সম্পর্ক কী? কেন bottom-up parser rightmost derivation উল্টো ক্রমে পায়?
দুটি নামের প্রথম L মানে input বাঁ থেকে ডানে (Left to right) পড়া। দ্বিতীয় অক্ষরটি বলে parser কোন derivation তৈরি করে: LL-এ Leftmost, LR-এ Rightmost. Top-down parser start symbol থেকে শুরু করে, আর প্রতিবার সবচেয়ে বাঁয়ের না-খোলা variable-এর জন্য একটি নিয়ম বাছে, input-এর পরের token দেখে। এটি ঠিক অংশ ৩-এর stepper: গাছ ওপর থেকে নিচে, বাঁ থেকে ডানে গজায়, আর input-এর যে অংশ মিলে গেছে, সেটি sentential form-এর স্থির বাঁ অংশ।
Bottom-up parser উল্টো কাজ করে। সে token পড়ে একটি stack-এ রাখে (shift), আর stack-এর ওপরের অংশ কোনো নিয়মের ডান দিকের সঙ্গে মিললে সেটিকে বাঁ দিকের variable-এ গুটিয়ে ফেলে (reduce). id+id∗id-এ প্রথম reduce হয় প্রথম id → F, তারপর F → T, তারপর T → E. এবার অংশ ৪-এর rightmost derivation-টি নিচ থেকে ওপরে পড়ুন: id+id∗id ⇐ F+id∗id ⇐ T+id∗id ⇐ E+id∗id ⇐ ⋯. হুবহু একই ক্রম! কারণটি সহজ: parser বাঁ থেকে পড়ে, তাই সে প্রথমে বাঁ দিকের অংশ গুটায়; আর rightmost derivation-এর শেষ ধাপগুলোই বাঁ দিকের অংশ পাকা করে। তাই bottom-up parser একটি rightmost derivation-কে শেষ থেকে শুরুর দিকে পুনর্গঠন করে।
ইতিহাস: Donald Knuth ১৯৬৫ সালের “On the translation of languages from left to right” প্রবন্ধে LR(k) grammar আর তার parsing-এর তত্ত্ব দেন; LL(k)-এর formal তত্ত্ব ১৯৬০-এর দশকের শেষে Philip Lewis ও Richard Stearns এবং পরে Daniel Rosenkrantz ও Stearns-এর কাজে গড়ে ওঠে বলে পরিচিত। দুটিরই সুবিধা হলো linear সময়, কিন্তু শুধু কিছু বিশেষ শ্রেণির grammar-এর জন্য। পর্ব ৩৮ আর ৩৯-এ এদের নির্মাণ দেখবেন।
মূল উপলব্ধি: leftmost আর rightmost derivation শুধু পরীক্ষার খাতার রীতি নয়; এরা দুই প্রধান parsing কৌশলের গাণিতিক ছায়া। উপপাদ্য ৪.১-এর কারণে দুই কৌশলই একই গাছ খোঁজে, শুধু ভিন্ন পথে।
প্র ০২বাস্তবের compiler আর code-editor কি parse tree রাখে, নাকি শুধু AST? দুটির মধ্যে বাছাই কীসের ওপর নির্ভর করে?
উত্তর নির্ভর করে tool-টির কাজের ওপর। একটি compiler-এর মূল লক্ষ্য অর্থ বোঝা আর code তৈরি করা, তাই সে সাধারণত parse tree-কে খুব দ্রুত AST-এ ছেঁটে ফেলে, বা কোনো পূর্ণ parse tree না বানিয়ে সরাসরি AST তৈরি করে। CPython এর একটি ভালো উদাহরণ: Python-এর ast module প্রোগ্রামের AST দেখায়, যেখানে বন্ধনী নেই, শুধু BinOp, Call-এর মতো node. CPython ৩.৯ সংস্করণে PEP 617 অনুযায়ী একটি নতুন PEG-ভিত্তিক parser আসে, যা সরাসরি AST বানায়; পুরোনো concrete syntax tree দেখানোর parser module ৩.১০-এ বাদ দেওয়া হয়।
কিন্তু code formatter, refactoring tool আর IDE-র কাজ আলাদা। একটি formatter আপনার code সুন্দর করে সাজায়, কিন্তু আপনার comment, ফাঁকা লাইন আর বন্ধনী হারাতে পারে না। AST থেকে মূল লেখা ফেরত পাওয়া যায় না, কারণ yield-এর তথ্য সেখানে নেই (অংশ ৬-এর সারণি)। তাই এই tool-গুলো এমন গাছ রাখে যা প্রতিটি token, এমনকি whitespace আর comment-ও ধরে রাখে; এদের প্রায়ই “lossless” বা “full-fidelity” syntax tree বলা হয়। Tree-sitter নামের open-source parsing library (প্রথম প্রকাশ ২০১৮ সালের দিকে) অনেক editor-এ syntax highlighting আর code navigation-এর জন্য এমন concrete tree বানায়, আর একটি অক্ষর বদলালে পুরো file নয়, শুধু বদলানো অংশ আবার parse করে।
তত্ত্বের দিক থেকে দেখুন: parse tree-র yield মূল token-ক্রম, তাই parse tree থেকে মূল লেখা হুবহু ফেরত আসে; AST একটি “ভুলে যাওয়ার” মানচিত্র, অনেক parse tree এক AST-এ মেলে (id, (id), ((id)) তিনটিরই AST একটি id). কোন তথ্য ভুলবেন, সেটিই নকশার সিদ্ধান্ত।
মূল উপলব্ধি: Parse tree আর AST প্রতিদ্বন্দ্বী নয়, একই তথ্যের দুই স্তর। অর্থের কাজে AST, লেখার কাজে concrete tree; আর grammar-এর তত্ত্ব (ambiguity, উপপাদ্য ৪.১) সবসময় parse tree নিয়ে।
প্র ০৩একটি expression-এর “মান” string-এ থাকে, নাকি গাছে? Grammar-এর নিয়মের সঙ্গে হিসাবের সূত্র জোড়ার ধারণা কীভাবে এল?
“2+3∗4” string-টির নিজের কোনো মান নেই; মান আসে কীভাবে পড়বেন তা থেকে। Parse tree-তে যোগ ওপরে আর গুণ নিচে থাকলে মান 2 + 12 = 14; গুণ ওপরে থাকলে (2 + 3) ∗ 4 = 20. তাই মান হিসাব হয় গাছ ধরে: প্রতিটি node-এর মান তার সন্তানদের মান থেকে, নিচ থেকে ওপরে। এটি expression tree-র postorder হিসাব, আর বাজারঘরের order-query-ও এভাবেই চলে: প্রতিটি শর্তের true/false, তারপর AND, তারপর OR.
Grammar-এর প্রতিটি নিয়মের সঙ্গে একটি ছোট হিসাবের সূত্র জোড়ার ধারণা বেশ পুরোনো। Edgar Irons ১৯৬১ সালে ALGOL 60-এর জন্য একটি “syntax-directed” compiler-এর বর্ণনা প্রকাশ করেন বলে পরিচিত, যেখানে প্রতিটি syntax নিয়মের সঙ্গে অনুবাদের কাজ বাঁধা ছিল। Donald Knuth ১৯৬৮ সালের “Semantics of context-free languages” প্রবন্ধে এর formal রূপ দেন, যার নাম attribute grammar. সেখানে গাছের প্রতিটি node-এর কিছু “attribute” থাকে; কিছু নিচ থেকে ওপরে যায় (যেমন expression-এর মান, synthesized), কিছু ওপর থেকে নিচে (যেমন “এই block-এ কোন variable declare করা আছে”, inherited). Knuth দেখান, কোন অবস্থায় attribute-এর নির্ভরতায় চক্র হয়, আর সেটি পরীক্ষা করা যায়।
এর একটি গভীর শিক্ষা আছে। Grammar ambiguous হলে একই string-এর দুটি গাছ, তাই দুটি সম্ভাব্য মান; অর্থ আর অনন্য থাকে না। এ কারণেই programming language-এর grammar এমনভাবে লেখা হয় (বা parser-কে এমন নির্দেশ দেওয়া হয়) যাতে প্রতিটি program-এর গাছ একটিই থাকে। পর্ব ২৭-এ 2+3∗4-এর দুটি মান কোডে হিসাব করে দেখবেন।
মূল উপলব্ধি: মান থাকে গাছে, string-এ নয়। এ কারণেই parse tree-র অনন্যতা শুধু একটি তাত্ত্বিক সৌন্দর্য নয়; এটি “এই program-এর অর্থ কী” প্রশ্নের উত্তর এক থাকার শর্ত।
প্র ০৪একটি string-এর parse tree খুব বেশি হলে, যেমন হাজার হাজার, একটি parser কীভাবে সেগুলো সামলায়?
অংশ ৫-এ দেখেছেন, flat grammar E → E+E ∣ E∗E ∣ (E) ∣ id-এ n-টি operator থাকলে গাছের সংখ্যা n-তম Catalan সংখ্যা, যা মোটামুটি 4n-এর হারে বাড়ে। ২০টি operator-এর একটি expression-এ গাছ ছয় শতকোটিরও বেশি (C20 = 6,564,120,420). সবগুলো আলাদা করে তৈরি করা অসম্ভব। তবু কিছু parser ambiguous grammar-এ “সব গাছ” ফেরত দেয়; কীভাবে?
উত্তর হলো ভাগাভাগি। দুটি আলাদা গাছের অনেক অংশ অভিন্ন: id+id∗id-এর দুটি গাছেই প্রতিটি id-এর পাতা, আর “id ∗ id” বা “id + id”-এর ছোট উপগাছ বারবার আসে। Parse forest প্রতিটি “এই variable থেকে input-এর এই অংশ” জোড়ের জন্য একটিই node রাখে, আর সেই node-এর নিচে বিকল্প ভাঙনগুলো (packed node) পাশাপাশি রাখে। ফলে অসংখ্য গাছ একটি polynomial আকারের graph-এ এঁটে যায়। Jay Earley তাঁর ১৯৬৮ সালের PhD thesis-এ আর ১৯৭০ সালের প্রবন্ধে এমন একটি algorithm দেন, যা যেকোনো CFG-এর membership সবচেয়ে খারাপ ক্ষেত্রে n-এর ঘন অনুপাতের সময়ে বের করে; আর Masaru Tomita ১৯৮০-এর দশকের মাঝামাঝি GLR parsing আর shared packed forest-এর ধারণা জনপ্রিয় করেন, প্রথমে মানুষের ভাষার জন্য।
lark-এর Earley parser এর একটি ব্যবহারিক রূপ: ambiguity থাকলে সাধারণত নিজের নিয়মে একটি গাছ বেছে দেয়, আর ambiguity='explicit' দিলে বিকল্পগুলো _ambig নামের node-এ দেখায়। পর্ব ২৭-এ এটি সত্যিকারের run-এ দেখবেন, আর পর্ব ৪১-এ Earley আর GLR-এর ভেতরের কাজ।
মূল উপলব্ধি: গাছের সংখ্যা exponential হলেও তাদের “ভিন্ন টুকরো” polynomial. উপপাদ্য ৪.১-এর মতো, এখানেও কৌশলটি হলো অপ্রয়োজনীয় তথ্য (কোন ক্রমে, কোন গাছে) বাদ দিয়ে কাঠামোর অভিন্ন অংশ একবার রাখা।
প্র ০৫Parser কত তাড়াতাড়ি বুঝতে পারে যে input-এ ভুল আছে? “UnexpectedEOF”-এর মতো বার্তার পেছনের তত্ত্ব কী?
অংশ ৭-এর run-এ “FIND order WHERE amount >= 1000 AND” দেওয়ায় lark জানিয়েছিল input অসময়ে শেষ। লক্ষ করুন, এর প্রতিটি prefix language-এর কোনো string-এর prefix: AND-এর পরে একটি শর্ত বসালেই বৈধ query. তাই parser শেষ পর্যন্ত কোনো ভুল দেখেনি; ভুল ধরা পড়ল শুধু input ফুরোনোর পর। অন্যদিকে “FIND order WHERE AND” লিখলে চতুর্থ token-এই ভুল, কারণ “FIND order WHERE AND” দিয়ে শুরু হওয়া কোনো বৈধ query নেই।
যে parser বাঁ থেকে পড়তে পড়তে ঠিক সেই প্রথম token-এ থামে, যার পরে input আর কোনো বৈধ string-এর prefix নয়, তার আছে “valid prefix property” (বা correct prefix property). গাছের ভাষায়: এতক্ষণ পড়া অংশ দিয়ে একটি আংশিক parse tree বানানো যায়, যার yield-এর শুরু ঠিক এই prefix, আর পরের token সেই আংশিক গাছের সঙ্গে আর খাপ খায় না। LL(1) আর LR(1) parser-এর এই ধর্ম আছে বলে পরিচিত, Earley parser-এরও। এটি ব্যবহারকারীর কাছে খুব মূল্যবান: ভুলের বার্তা ঠিক ভুলের জায়গা দেখায়, পরে কোথাও নয়।
তবে “প্রথম অসম্ভব token”-ই সবসময় মানুষের ভুলের জায়গা নয়। একটি বন্ধনী খুলে বন্ধ করতে ভুলে গেলে parser হয়তো file-এর একেবারে শেষে অভিযোগ করে, যদিও ভুলটি অনেক আগের লাইনে। ভালো error message আর error recovery (ভুলের পরেও parse চালিয়ে আরও ভুল খোঁজা) তাই আলাদা প্রকৌশল-সমস্যা, পর্ব ৪২-এ এর কৌশল দেখবেন। বাজারঘরের query box-এ এর ব্যবহারিক রূপ: ব্যবহারকারী লিখতে লিখতেই “AND-এর পরে একটি শর্ত দিন” দেখানো, কারণ আংশিক গাছ জানে এরপর কী আসতে পারে।
মূল উপলব্ধি: আংশিক parse tree শুধু derivation-এর মাঝপথ নয়; এটি “এ পর্যন্ত যা পড়েছি তার অর্থ” আর “এরপর কী আসতে পারে” দুটিরই হিসাব। দ্রুত ভুল ধরা মানে আংশিক গাছ যত তাড়াতাড়ি অসম্ভব হয়, তত তাড়াতাড়ি থামা।
অনুশীলন
আগে কাগজে করুন, তারপর উত্তর মেলান। tree_to_derivations.py আর check_derivation.py ব্লকে নিজের গাছ বা derivation বসিয়ে উত্তর যাচাই করতে পারেন।
-
Grammar নকশা আর গাছ: E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id grammar-এ একটি ঘাতের operator “^” যোগ করুন, যা গুণের চেয়েও আগে হিসাব হয় আর ডান দিক থেকে জোড়ে (a^b^c মানে a^(b^c)). তারপর id∗id^id^id-এর parse tree আঁকুন আর তার leftmost derivation লিখুন।
নকশা: গুণের স্তরের নিচে একটি নতুন স্তর: E → E+T ∣ T, T → T∗F ∣ F, F → P^F ∣ P, P → (E) ∣ id. F → P^F নিয়মে recursion ডান দিকে, তাই a^b^c-এর গাছে ডানের ঘাতটি নিচে বসে: a^(b^c). যোগ আর গুণে recursion বাঁ দিকে (E → E+T), তাই সেগুলো বাঁ দিক থেকে জোড়ে।
গাছ (indentation-এ): E → T; T → T ∗ F; বাঁয়ের T → F → P → id; ডানের F → P ^ F, যেখানে P → id আর F → P ^ F, যার P → id আর F → P → id. অর্থাৎ id ∗ (id ^ (id ^ id)).
Leftmost derivation (১১ ধাপ): E ⇒ T ⇒ T∗F ⇒ F∗F ⇒ P∗F ⇒ id∗F ⇒ id∗P^F ⇒ id∗id^F ⇒ id∗id^P^F ⇒ id∗id^id^F ⇒ id∗id^id^P ⇒ id∗id^id^id.
Scratch-এ brute force-এ এই string-এর leftmost derivation একটিই পাওয়া গেছে, আর lark (1.3.1) দিয়ে একই grammar-এর AST-ধাঁচের গাছ এসেছে
mul(id, pow(id, pow(id, id))), ওপরের উত্তরের সঙ্গে হুবহু মিল। -
প্রমাণ: ধরুন একটি CFG-তে কোনো ε-নিয়ম নেই আর কোনো unit নিয়ম (A → B, যেখানে B একটি variable) নেই। প্রমাণ করুন, দৈর্ঘ্য n ≥ 1-এর যেকোনো string-এর প্রতিটি derivation-এ বড়জোর 2n − 1টি ধাপ।
- উপপাদ্য ৪.১-এর প্রমাণের ধাপ ২ অনুযায়ী derivation-টি থেকে একটি parse tree পাওয়া যায়, যার প্রতিটি variable-node ঠিক একটি ধাপ; তাই ধাপের সংখ্যা = গাছের variable-node-এর সংখ্যা। — উপপাদ্য ৪.১-এর গঠন
- ε-নিয়ম নেই, তাই কোনো ε-পাতা নেই; প্রতিটি পাতা একটি terminal, আর yield-এর দৈর্ঘ্য n, তাই পাতা ঠিক n-টি। — yield-এর সংজ্ঞা
- প্রতিটি variable-node-এর হয় একটি সন্তান, নয়তো দুই বা তার বেশি। একটি সন্তান হলে নিয়মটি A → X; unit নিয়ম নেই বলে X একটি terminal, অর্থাৎ node-টি একটি পাতার ঠিক ওপরে। এমন node বড়জোর n-টি, কারণ প্রতিটির নিচে আলাদা একটি পাতা। — unit নিয়ম নেই
- দুই বা বেশি সন্তানের node-গুলো: যে rooted tree-তে প্রতিটি ভেতরের node-এর অন্তত দুটি সন্তান, তাতে ভেতরের node পাতার চেয়ে অন্তত একটি কম। এক-সন্তানের node-গুলো “গুটিয়ে” ফেললে (প্রতিটির বদলে তার সন্তান) এমন একটি গাছ পাওয়া যায়, যার পাতা n-টি; তাই বহু-সন্তানের node বড়জোর n − 1টি। — পাতার ওপর induction-এ প্রমাণিত গাছের ধর্ম
- মোট variable-node ≤ n + (n − 1) = 2n − 1, তাই ধাপ ≤ 2n − 1. ∎ — ধাপ ১, ৩ আর ৪ যোগ করে
সীমাটি পৌঁছানো যায়: Chomsky normal form-এ (পর্ব ২৯) প্রতিটি derivation ঠিক 2n − 1 ধাপের। এর বিপরীতে, অংশ ৫-এর স্তরভাগ করা grammar-এ T → F-এর মতো unit নিয়ম আছে; id+id∗id-এ n = 5 token, 2n − 1 = 9, আর ধাপ ৮, সীমার নিচেই। কিন্তু unit নিয়ম থাকলে সাধারণভাবে এমন কোনো সীমা নেই (যেমন A → B, B → A-এর চক্র)।
-
গণনা আর trace: BAL grammar S → (S)S ∣ ε. (ক) ()()-এর parse tree আঁকুন আর তার rightmost derivation লিখুন। (খ) এই string-এর মোট কয়টি derivation আছে, আর কয়টি leftmost? অংশ ৫-এর সূত্র দিয়ে হিসাব করুন।
(ক) Root S → ( S1 ) S2; S1 → ε (ভেতরের প্রথম জোড়া ফাঁকা); S2 → ( S3 ) S4; S3 → ε, S4 → ε. Variable-node ৫টি, তিনটি ε-পাতা। Rightmost derivation: S ⇒ (S)S ⇒ (S)(S)S ⇒ (S)(S) ⇒ (S)() ⇒ ()(). পাঁচ ধাপ: আগে ডানের S2 খোলে, তারপর তার ডানের S4 মোছে, তারপর S3, শেষে বাঁয়ের S1.
(খ) s-এর মান: root 5, S1 1, S2 3, S3 1, S4 1. মোট = 5! / (5 · 1 · 3 · 1 · 1) = 120 / 15 = 8. Leftmost derivation ১টি, কারণ BAL-এর এই string-এর গাছ একটিই। Scratch-এ brute force-এ ঠিক ৮টি derivation আর ১টি leftmost পাওয়া গেছে। লক্ষ করুন, ε-নিয়মের node-ও একটি ধাপ, তাই গোনায় আসে।
-
Output অনুমান: tree_to_derivations.py ব্লকে T-এর জায়গায় (id+id)∗id-এর parse tree বসালে (একই E, T, F grammar) leftmost তালিকায় কয়টি ধাপ আসবে, আর তালিকাটি কী? Rightmost তালিকার দ্বিতীয় আর তৃতীয় লাইন কী হবে?
গাছ: E → T; T → T ∗ F; বাঁয়ের T → F → ( E ); ভেতরের E → E + T, যার E → T → F → id আর T → F → id; ডানের F → id. Variable-node ১১টি, তাই ১১ ধাপ।
Leftmost: E ⇒ T ⇒ T∗F ⇒ F∗F ⇒ (E)∗F ⇒ (E+T)∗F ⇒ (T+T)∗F ⇒ (F+T)∗F ⇒ (id+T)∗F ⇒ (id+F)∗F ⇒ (id+id)∗F ⇒ (id+id)∗id.
Rightmost-এর প্রথম দুই ধাপ একই (E ⇒ T ⇒ T∗F), কারণ তখন variable একটিই; তাই দ্বিতীয় লাইন
=> T*F, আর তৃতীয় লাইনে ডানের F আগে খোলে:=> T*id. বাকি: F∗id, (E)∗id, (E+T)∗id, (E+F)∗id, (E+id)∗id, (T+id)∗id, (F+id)∗id, (id+id)∗id. Scratch-এ ব্লকটি চালিয়ে ঠিক এই দুটি তালিকা এসেছে, দুটিই ১১ ধাপের। অংশ ৫-এর brute force-এর শেষ লাইন অনুযায়ী এই গাছের মোট derivation ৯০টি।
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমএকটি parse tree থেকে তার leftmost derivation লেখার ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- Root-এর লেবেল (start symbol) দিয়ে প্রথম sentential form লেখা
- বর্তমান sentential form-এ সবচেয়ে বাঁয়ের variable খুঁজে বের করা
- গাছে সেই variable-এর node-টি খুঁজে তার সন্তানদের বাঁ থেকে ডানে পড়া
- Variable-টির জায়গায় সন্তানদের লেবেল বসিয়ে পরের sentential form লেখা (ε হলে কিছুই না)
- কোনো variable বাকি না থাকা পর্যন্ত আগের তিনটি ধাপ বারবার করা
- শেষ string গাছের yield-এর সমান আর ধাপ-সংখ্যা variable-node-এর সমান কি না মেলানো
E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id grammar-এ sentential form E+T∗F থেকে পরের rightmost ধাপ কোনটি হতে পারে?
- T+T∗F
- E+T∗id
- E+F∗F
- E+id∗id
একটি parse tree-তে ৮টি variable-node (ভেতরের node) আছে। এই গাছের সঙ্গে মেলে এমন যেকোনো derivation-এ কয়টি ধাপ থাকবে?
- yield-এর দৈর্ঘ্যের সমান
- leftmost-এ ৮টি, অন্য ক্রমে বেশি বা কম হতে পারে
- ঠিক ৮টি, যে ক্রমেই হোক
- গাছের মোট node-এর সমান
S → aSb ∣ ε grammar-এর একটি parse tree-র পাতাগুলো বাঁ থেকে ডানে a, a, ε, b, b. গাছটির yield কী?
- aabb
- aaεbb
- aaSbb
- abab
G: S → AB, A → a, B → b. String ab-এর বিষয়ে কোন কথাটি সঠিক?
- ab-এর derivation ঠিক একটি
- দুটি derivation আছে, তাই G ambiguous
- ab-এর leftmost derivation দুটি
- derivation দুটি, কিন্তু parse tree একটি
একটি CFG-এর কোনো string w-এর ঠিক একটি parse tree আছে। তাহলে w-এর rightmost derivation কয়টি?
- শূন্য, কারণ rightmost derivation সবসময় থাকে না
- গাছের variable-node-এর সংখ্যার সমান
- ঠিক একটি
- ঠিক দুটি, কারণ leftmost-এর একটি আয়না-রূপ থাকে
E → E+T ∣ T, T → T∗F ∣ F, F → (E) ∣ id grammar-এ (id) string-এর parse tree আর একটি সাধারণ AST-এর তুলনায় কোনটি সঠিক?
- দুটিতেই বন্ধনী দুটি পাতা হিসেবে থাকে
- Parse tree-তে E, T, F-এর শিকল আর দুটি বন্ধনী থাকে; AST-এ শুধু id
- AST-এ শিকল থাকে, parse tree-তে থাকে না
- AST থেকে মূল string হুবহু ফেরত আনা যায়, parse tree থেকে যায় না
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Leftmost ধাপে বদলানো variable-এর বাঁয়ে শুধু terminal (x ∈ Σ∗), rightmost ধাপে ডানে শুধু terminal.
- Parse tree: root-এ start symbol, প্রতিটি ভেতরের node একটি নিয়ম, সন্তানরা নিয়মের ডান দিক একই ক্রমে; ε-নিয়মে একটি ε-পাতা। পাতা বাঁ থেকে ডানে = yield.
- A ⇒∗ w ⇔ A ⇒lm∗ w ⇔ A ⇒rm∗ w ⇔ root A, yield w-এর গাছ আছে; গাছ আর leftmost (বা rightmost) derivation-এর মধ্যে bijection.
- যেকোনো derivation-এর ধাপ = গাছের variable-node; মোট derivation = m! ⁄ ∏ s(v), কিন্তু ambiguity গোনা হয় গাছ বা leftmost derivation দিয়ে।
- Parse tree সব নিয়ম আর token রাখে (yield = মূল string); AST শুধু operation আর operand রাখে, আর অর্থ হিসাব হয় গাছ ধরে।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ২৫ · Context-free grammar — formal definition আর উদাহরণফিরে দেখুনG = (V, Σ, R, S), derivation-এর সংজ্ঞা আর এই পর্বের সব grammar.
- পর্ব ০৬ · Chomsky hierarchy-র মানচিত্র — চার শ্রেণির language আর machineপটভূমিContext-free স্তর কেন গাছ-আকারের derivation দেয়, আর ওপরের স্তরে কেন দেয় না।
- পর্ব ০৪ · Theory of Computation-এর প্রমাণপটভূমিউপপাদ্য ৪.১-এর প্রমাণে লাগা structural induction.
- গণনার তত্ত্ব · কোর্স হোম৮৫টি পর্ব১৪টি মডিউলের পুরো মানচিত্র; পরের পর্ব ২৭ ambiguity.
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৬৬ — Tree traversal আর expression treeপাশের ট্র্যাকPreorder আর postorder, আর expression tree থেকে মান হিসাব।
- ডিসক্রিট ম্যাথমেটিক্স · পর্ব ৭৩ — Grammar আর formal languageপাশের ট্র্যাকBNF আর derivation-এর প্রথম পরিচয়, গণিতের দিক থেকে।