সরাসরি পর্বে যান
পর্ব ২২ · ৮৫-এর মধ্যে · মডিউল ৪

Lexical analysis — token, lexer আর lexer generator

Lexical Analysis — Tokens, Lexemes, Maximal Munch, Lexers Built from Automata and Lexer Generators

Taught in Bangla, this lesson builds a lexer from theory: tokens, lexemes and patterns, each token type as a regular language, and one DFA from the union of token NFAs. It applies maximal munch and rule priority, writes a scanner that remembers the last accepting position. In-page Python (Pyodide) lexes an order query and probes munch pitfalls, real desktop runs with PLY 3.11 and Lark 1.3.1 produce the same token stream as the hand-written scanner, and the page shows how \w splits Bangla words.

এই পর্বে যা শিখবেন

  • Token, lexeme আর pattern আলাদা করে চেনা, আর একটি lexer-এর formal বিবরণ লেখা
  • Maximal munch আর priority দিয়ে tokenization-এর সংজ্ঞা দেওয়া আর তার অনন্যতা প্রমাণ করা
  • Token-এর regex থেকে NFA-র union আর subset construction-এ lexer-এর DFA বানানো, প্রতিটি DFA state-এ token বসিয়ে
  • Scanner algorithm, whitespace, comment, error আর সবচেয়ে খারাপ ক্ষেত্রের খরচ বিশ্লেষণ করা
  • PLY, Lark আর lex/flex-এর নিয়ম বোঝা, আর Unicode ও বাংলা লেখার ফাঁদ নিজে চালিয়ে দেখা

১ · Compiler-এর প্রথম ধাপ — lexer কী করে

বাজারঘরের admin panel-এ একটি ছোট খোঁজার ভাষা আছে। একজন কর্মী লেখেন FIND order WHERE amount >= 1000 AND district = "Dhaka", আর সার্ভার ঢাকার হাজার টাকা বা তার বেশি দামের সব অর্ডার খুঁজে দেয়। সার্ভারের কাছে কিন্তু এটি শুধু ৫৪টি অক্ষরের একটি সারি: F, I, N, D, ফাঁকা ঘর, o, r, … । অর্থ বের করার আগে এই সারিকে শব্দে ভাগ করতে হবে: কোনটি keyword, কোনটি নাম, কোনটি সংখ্যা, কোনটি তুলনার চিহ্ন। এই প্রথম কাজটির নাম lexical analysis, আর যে program কাজটি করে তার নাম lexer (scanner বা tokenizer-ও বলা হয়)।

মায়ের লেখা বাজারের ফর্দের কথা ভাবুন: “চাল৫কেজি ডাল২কেজি তেল১লিটার”. দোকানি প্রথমে চোখ বুলিয়ে লেখাটিকে টুকরো করেন: “চাল”, “৫”, “কেজি”, “ডাল”, … । তিনি শুধু ঠিক করছেন কোথায় একটি শব্দ শেষ, আর প্রতিটি টুকরো কোন ধরনের: জিনিসের নাম, সংখ্যা না একক। তারপর দ্বিতীয় ধাপে তিনি টুকরোগুলো মিলিয়ে বোঝেন “৫ কেজি চাল”. প্রথম ধাপটি lexer, দ্বিতীয়টি parser. মজার কথা, “৫কেজি”-র মাঝে ফাঁকা না থাকলেও দোকানি ঠিকই ভাঙেন, কারণ অঙ্ক যেখানে শেষ, সংখ্যাও সেখানে শেষ। Lexer-ও ঠিক এভাবে, ধরন বদলের জায়গায়, টুকরো কাটে।

একটি compiler বা interpreter-এর front end সাধারণত এই দুই ধাপে চলে। Lexer অক্ষর পড়ে token-এর ধারা দেয়; ফাঁকা ঘর আর comment সে ফেলে দেয়। Parser token-এর ধারা পড়ে একটি syntax tree বানায়, যা বলে কোন অংশ কোন অংশের সঙ্গে যুক্ত। দুই ধাপের যন্ত্র আলাদা: lexer একটি finite automaton, আর parser-এর পেছনে থাকে একটি context-free grammar আর stack-সহ যন্ত্র, যা মডিউল ৫–৭-এর বিষয়। Python কোর্সের পর্ব ০৫ আর JavaScript কোর্সের পর্ব ০৫-এ এই পাইপলাইনের ব্যবহারিক রূপ দেখেছেন; এখানে দেখা হবে কেন lexer-এর অংশটি ঠিক regular language-এর তত্ত্ব দিয়ে পুরোটা বোঝা যায়।

Front end-এর দুই ধাপ — অক্ষর থেকে token, token থেকে গাছ

Lexer একটি DFA দিয়ে অক্ষর পড়ে আর ফাঁকা ঘর বাদ দেয়; parser grammar মেনে token সাজায়।

Compiler front end: source text, lexer, token stream, parser, syntax tree amount >= 1000 Lexer (scanner) Parser syntax tree → বাকি compiler regex → DFA, maximal munch context-free grammar (মডিউল ৫–৭) ID amount GE >= NUM 1000 অক্ষরের ধারা token-এর ধারা, ফাঁকা বাদ grammar মেনে সাজানো
ছবি ২২.১ — Lexer-এর যন্ত্র finite automaton, parser-এর যন্ত্র grammar আর stack; দুটিকে আলাদা রাখাই front end-কে সরল করে।

কাজ দুই ভাগে কেন? প্রথম কারণ সরলতা। Grammar-এ যদি প্রতিটি অক্ষর আলাদা চিহ্ন হতো, তাহলে “নাম মানে একটি অক্ষর, তারপর যত খুশি অক্ষর বা অঙ্ক” কথাটিও grammar-এর নিয়মে লিখতে হতো, আর প্রতিটি নিয়মে ফাঁকা ঘর কোথায় বসতে পারে তাও। দ্বিতীয় কারণ গতি: DFA-তে অক্ষরপ্রতি কাজ একটি টেবিল-দেখা, আর parser-এর ভারী কাজ চলে অনেক কম সংখ্যক token-এর ওপর। তৃতীয় কারণ তত্ত্বের সীমা: token-এর গঠন regular, কিন্তু সুষম বন্ধনী বা নেস্টেড expression regular নয় (পর্ব ১৭)। তাই যে অংশ finite automaton পারে তা finite automaton-কে, বাকিটা grammar-কে দেওয়া।

২ · Token, lexeme আর pattern — formal বিবরণ

তিনটি শব্দ প্রায়ই গুলিয়ে যায়, তাই শুরুতেই আলাদা করা যাক। Token হলো একটি শ্রেণির নাম, যেমন ID বা NUM; parser শুধু এটিই দেখে। Lexeme হলো input-এর সেই আসল টুকরো, যা ওই শ্রেণিতে পড়েছে, যেমন amount বা 1000. আর pattern হলো শ্রেণির নিয়ম, অর্থাৎ কোন কোন string ওই শ্রেণিতে পড়ে; সাধারণত একটি regex. Lexer সাধারণত parser-কে জোড়া দেয়: (token, attribute), যেখানে attribute হতে পারে lexeme নিজে, সংখ্যার মান বা line আর column নম্বর।

ক্রমTokenPattern (regex)উদাহরণ lexeme
১–৪FIND, WHERE, AND, ORশব্দটি হুবহুFIND
৫ID[A-Za-z_][A-Za-z0-9_]*amount, FINDER
৬NUM[0-9][0-9]*1000
৭STR"[^"\n]*""Dhaka"
৮–১৩GE, LE, NE, GT, LT, EQ>=, <=, !=, >, <, =>=
১৪WS (বাদ যায়)এক বা বেশি ফাঁকা ঘর, tab বা নতুন লাইনফাঁকা ঘর

টেবিলের ক্রমটি গুরুত্বপূর্ণ, কারণ এটিই অংশ ৩-এর priority. Keyword FIND আর একটি identifier (নাম) দুটিই “FIND” লেখাটি মেলায়; তালিকার আগে থাকায় keyword জিতবে। Pattern-গুলো পর্ব ১৩-এর বাস্তব regex-এর ভাষায় লেখা: [0-9] একটি character class, যা গণিতের (0 ∪ 1 ∪ ⋯ ∪ 9)-এর সংক্ষেপ; আর [^"\n] মানে “উদ্ধৃতিচিহ্ন আর নতুন লাইন ছাড়া যেকোনো অক্ষর”, যা alphabet সসীম বলে আবার একটি সসীম union.

সংজ্ঞা ২.১ (Lexical specification)

Σ একটি সসীম alphabet (input-এর অক্ষর)। একটি lexical specification হলো নিয়মের একটি ক্রমযুক্ত তালিকা (T1, R1), (T2, R2), …, (Tk, Rk), যেখানে প্রতিটি Ti একটি token-এর নাম আর Ri Σ-এর ওপর একটি regex, এই শর্তে যে ε ∉ L(Ri). নিয়মের ক্রম তার priority: i ছোট মানে priority বেশি। কিছু token-কে “বাদ যাবে” (skip) চিহ্নিত করা থাকে, যেমন WS আর comment.

শর্ত ε ∉ L(Ri) কেন? কোনো token যদি ফাঁকা string মেলাতে পারে, তাহলে lexer একই জায়গায় অসীম বার ফাঁকা token দিতে পারে, এক পা-ও না এগিয়ে। বাস্তব regex-এ \s* লিখলে ঠিক এই বিপদ; নিরাপদ রূপ \s+. প্রতিটি L(Ri) একটি regular language (Kleene-এর উপপাদ্য, পর্ব ১৪, পর্ব ১৫), আর (R1 ∪ ⋯ ∪ Rk)+-ও regular (পর্ব ১৬)। কিন্তু বন্ধনী মেলানো “বৈধ query”-র সেট সাধারণত regular নয়; সেটি parser-এর কাজ।

৩ · Longest match আর priority — maximal munch-এর দুই নিয়ম

একই input কয়েকভাবে টুকরো করা যায়। >= কি একটি GE, নাকি একটি GT আর তারপর একটি EQ? FINDER কি keyword FIND আর তারপর নাম ER, নাকি পুরোটা একটি নাম? প্রায় সব প্রোগ্রামিং ভাষা এখানে একই উত্তর দেয়, দুটি নিয়মে। প্রথম নিয়ম: বর্তমান অবস্থান থেকে যত লম্বা lexeme কোনো token-এ পড়ে, সবচেয়ে লম্বাটি নিতে হবে। দ্বিতীয় নিয়ম: সেই সবচেয়ে লম্বা lexeme একাধিক token-এ পড়লে তালিকার আগের token জেতে। এই জোড়াটিকে বলে maximal munch (“সবচেয়ে বড় কামড়”) বা longest match.

সংজ্ঞা ৩.১ (Maximal munch tokenization)

Input w ∈ Σ∗-এর অবস্থান p-তে বাকি অংশ v = w[p..]. ধরুন ℓ = max{|u| : u, v-এর একটি prefix, |u| ≥ 1, আর কোনো i-এর জন্য u ∈ L(Ri)}. এমন কোনো u না থাকলে অবস্থান p-তে একটি lexical error. নইলে u হলো v-এর দৈর্ঘ্য ℓ-এর prefix, আর token Tj, যেখানে j = min{i : u ∈ L(Ri)}. Lexer (Tj, u) দেয় (skip-token হলে কিছু দেয় না) আর অবস্থান p + ℓ থেকে আবার একই কাজ শুরু করে, যতক্ষণ না input শেষ হয়।

উপপাদ্য ৩.২ (Maximal munch-এর অনন্যতা)

যেকোনো lexical specification আর input w-এর জন্য সংজ্ঞা ৩.১ ঠিক একটি ফল দেয়: হয় token-এর একটি অনন্য ক্রম (Tj1, u1), …, (Tjm, um), যেখানে u1u2⋯um = w (skip-token-সহ), নয়তো একটি নির্দিষ্ট অবস্থানে প্রথম lexical error.

প্রমাণ (বাকি অংশের দৈর্ঘ্য |v|-এর ওপর strong induction):

  1. ভিত্তি, |v| = 0: input শেষ, ফল ফাঁকা ক্রম, যা অনন্য। — সংজ্ঞা ৩.১-এর থামার শর্ত
  2. ℓ অনন্য: v-এর prefix সসীম সংখ্যক (|v|টি অশূন্য), তাই যোগ্য prefix-এর দৈর্ঘ্যের সেট সসীম; ফাঁকা হলে error, নইলে তার সর্বোচ্চ মান একটি নির্দিষ্ট সংখ্যা। — সসীম সেটের max
  3. j অনন্য: {i : u ∈ L(Ri)} হলো {1, …, k}-এর একটি অশূন্য উপসেট, তাই তার min একটিই। — সসীম সেটের min
  4. এগোনো নিশ্চিত: ℓ ≥ 1, কারণ সংজ্ঞায় |u| ≥ 1 চাওয়া হয়েছে (এখানেই ε ∉ L(Ri) শর্তের দরকার)। তাই বাকি অংশ কঠোরভাবে ছোট হয়। — সংজ্ঞা ২.১
  5. Induction: ছোট বাকি অংশ v' = w[p + ℓ..]-এ hypothesis-এ ফল অনন্য; প্রথম token-এর সঙ্গে জুড়ে পুরো ফলও অনন্য, আর lexeme-গুলো পরপর জুড়লে u · (v'-এর lexeme) = v. ∎ — strong induction

উপপাদ্যটি বলে maximal munch একটি ফাংশন. কিন্তু এটি বলে না যে input-কে token-এ ভাঙার কোনো উপায় থাকলে maximal munch সেটি খুঁজে পাবে। Token {ab, a, bc} আর input abc নিন। “a” + “bc” একটি বৈধ ভাঙন। Maximal munch কিন্তু প্রথমে লম্বাটি নেয়, “ab”, তারপর “c”-তে আটকে error দেয়; scratch-এর একটি script ঠিক এই ফল দিয়েছে। Lexer ফিরে গিয়ে অন্য ভাঙন খোঁজে না।

Lexer-কে এই দুই নিয়ম মানতে হলে একটি DFA লাগে, যার প্রতিটি accepting state-এ একটি token-এর নাম লেখা। নিচের ছবিতে তুলনার চিহ্ন, সংখ্যা আর নামের একটি ছোট সংযুক্ত DFA. GT-এর state থেকে = পড়লে GE-তে যাওয়া যায়; এটিই maximal munch-এর সুযোগ।

GT, GE, EQ, NUM আর ID-এর সংযুক্ত DFA

দুই দাগের বৃত্ত accepting, ভেতরে যে token-এর নাম লেখা সেটিই সেখানে গৃহীত। না-আঁকা সব তীর dead state-এ যায়।

Combined lexer DFA for GT, GE, EQ, NUM and ID q0 GTGE EQNUMID > = = শুরু 0–9 অক্ষর, _ 0–9 অক্ষর, অঙ্ক, _
ছবি ২২.২ — GT-এর state accepting হলেও lexer সেখানে থামে না; পরের অক্ষর = হলে GE-তে এগোয়, অন্য কিছু হলে GT দেয়।

নিচের stepper এই DFA দিয়ে n>=5 পড়ে। প্রতিটি ধাপে দেখুন কোন token এখনো “বেঁচে” (পড়া লেখাটি তার কোনো string-এর prefix) আর শেষ গ্রহণ কোথায়; সংখ্যাগুলো scanner দিয়ে মেলানো।

1col 1 থেকে: n2n> : dead3col 2 থেকে: >4>= : GE5>=5 : dead6col 4 থেকে: 57তুলনা: n> =5
এই ধাপের অবস্থা
এ পর্যন্ত পড়া
বেঁচে থাকা token
শেষ গৃহীত
বের হওয়া token
  1. শুরু। col 1-এ n পড়ে DFA ID-এর state-এ; শুধু ID বেঁচে আছে, আর দৈর্ঘ্য 1-এ একটি ID সম্পূর্ণ। এটি মনে রাখা হলো, কিন্তু lexer এখনো থামে না।
  2. Dead. > পড়ে ID-এর আর কোনো তীর নেই, DFA dead state-এ। এখন শেষ মনে রাখা গ্রহণ, ID(n), বের হয়; পরের token শুরু হবে col 2 থেকে, অর্থাৎ >-টি আবার পড়া হবে।
  3. দুই প্রার্থী। > পড়ে GT-এর state. GT সম্পূর্ণ, আর GE-ও বেঁচে, কারণ “>” হলো “>=”-এর prefix. Maximal munch বলে: গ্রহণটি মনে রেখে আরও পড়তে থাকুন।
  4. লম্বাটি জেতে। = পড়ে GE-এর state; এখন শুধু GE বেঁচে আর দৈর্ঘ্য 2-এ সম্পূর্ণ। শেষ গ্রহণ হালনাগাদ: GE, দৈর্ঘ্য 2.
  5. আবার dead. 5 পড়ে GE থেকে কোনো তীর নেই। শেষ গ্রহণ GE(>=) বের হয়, আর col 4 থেকে নতুন শুরু।
  6. শেষ token. 5 পড়ে NUM-এর state, আর input শেষ। শেষ গ্রহণ NUM(5). পুরো ফল: ID(n) GE(>=) NUM(5).
  7. তুলনা। n> =5-এ >-এর পর ফাঁকা ঘর পড়ে GT-এর পথ dead হয়, তাই GT(>) বের হয়; ফাঁকা ঘর WS হয়ে বাদ যায়, তারপর EQ(=) আর NUM(5). ফাঁকা ঘর lexer-এর কাছে একটি দেয়াল।

৪ · Regex থেকে lexer — NFA-র union, DFA আর state-এর token

ছবি ২২.২-এর DFA হাতে আঁকা। চোদ্দটি token-এ দরকার যন্ত্রিক পদ্ধতি। মডিউল ২–৩-এর তিনটি ফল মিলিয়ে: Thompson construction (পর্ব ১৪), ε-NFA-র union, আর ε-closure-সহ subset construction (পর্ব ১০, পর্ব ১১)। নতুন উপাদান শুধু একটি: DFA-র প্রতিটি state-এ কোন token লেখা হবে।

নির্মাণ ৪.১ (Specification থেকে lexer-এর DFA)

ধাপ ১. প্রতিটি Ri-এর জন্য একটি ε-NFA Ni বানান, state-নাম আলাদা রেখে; Ni-এর accepting state-সেট Fi.
ধাপ ২. একটি নতুন শুরু s0 যোগ করুন, আর প্রতিটি Ni-এর শুরুতে একটি ε-তীর। ফল N, যার language L(R1) ∪ ⋯ ∪ L(Rk).
ধাপ ৩. N-এ subset construction চালান: DFA-র শুরু E({s0}), আর প্রতিটি state S ও অক্ষর c-তে δD(S, c) = E(⋃q ∈ S δ(q, c)), যেখানে E হলো ε-closure.
ধাপ ৪. প্রতিটি DFA state S-এ token বসান: tok(S) = Tj, যেখানে j = min{i : S ∩ Fi ≠ ∅}; এমন i না থাকলে S non-accepting. ∅ হলো dead state.

উপপাদ্য ৪.২ (নির্মাণের সঠিকতা)

যেকোনো অশূন্য string u-র জন্য ধরুন Su = δ̂D(E({s0}), u). তাহলে Su ∩ Fi ≠ ∅ ⇔ u ∈ L(Ri). ফলে tok(Su) = Tj ঠিক তখন, যখন j = min{i : u ∈ L(Ri)}, আর Su = ∅ ⇔ u কোনো token-এর কোনো string-এর prefix নয়।

প্রমাণ:

  1. Subset construction-এর সঠিকতা থেকে Su = N-এ s0 থেকে label u-এর কোনো পথে পৌঁছানো সব state-এর সেট। — পর্ব ১০-এর উপপাদ্য, পর্ব ১১-এর closure-সহ রূপ
  2. s0 থেকে বের হওয়া তীর শুধু Ni-গুলোর শুরুতে ε-তীর, আর আলাদা Ni-এর মধ্যে কোনো তীর নেই। তাই u-এর প্রতিটি পথ একটিমাত্র Ni-এর ভেতরে চলে। — ধাপ ১–২-এর গঠন
  3. তাই Su ∩ Fi ≠ ∅ ⇔ Ni-এ label u-এর একটি গ্রহণকারী পথ আছে ⇔ u ∈ L(Ni) = L(Ri). — পর্ব ১৪-এর উপপাদ্য
  4. ধাপ ৪-এর min এখন ঠিক সংজ্ঞা ৩.১-এর j. আর Su = ∅ মানে কোনো Ni-এ u-এর কোনো পথই নেই, অর্থাৎ কোনো Ri-এর কোনো string u দিয়ে শুরু হয় না; উল্টো দিকও একই যুক্তিতে। ∎ — ধাপ ৪, ধাপ ২

শেষ বাক্যটিই scanner-কে থামার অধিকার দেয়: DFA ∅-এ পৌঁছালে আর কোনো লম্বা lexeme সম্ভব নয়, তাই শেষ মনে রাখা গ্রহণই maximal munch-এর ℓ আর j. নিচের stepper পাঁচটি token-এর (FIND, ID, GE, GT, EQ, এই priority-তে) NFA জুড়ে subset construction-এর কয়েকটি সারি দেখায়। NFA state-এর নাম: FIND-এর f0 → f1 → f2 → f3 → f4, ID-এর i0 → i1 (i1-এ লুপ), GE-এর e0 → e1 → e2, GT-এর g0 → g1, EQ-এর q0 → q1; শেষেরগুলো accepting.

1পাঁচটি আলাদা NFA2নতুন শুরু s03পড়া: F4পড়া: FIN5পড়া: FIND6পড়া: FINDE7পড়া: > আর >=8সারকথা
DFA-র এই state
NFA state-সেট
accepting অংশ
tok(S)
  1. আলাদা যন্ত্র। প্রতিটি token-এর নিজের NFA, তালিকার ক্রমে: FIND, ID, GE, GT, EQ. Keyword-এর NFA শুধু অক্ষরের একটি শিকল, আর ID-এর NFA-তে i1-এ অক্ষর, অঙ্ক বা _ পড়ার লুপ।
  2. Union. নতুন s0 থেকে পাঁচটি শুরুতে ε-তীর। DFA-র শুরু state তার ε-closure, ছয়টি state; কোনোটি accepting নয়, কারণ কোনো token ফাঁকা string মেলায় না।
  3. F পড়া। FIND-এর পথে f1, আর F একটি অক্ষর বলে ID-এর পথে i1. বাকি তিন NFA-র F-তীর নেই, তারা ঝরে পড়ে। সেটে i1 accepting, তাই এই state-এর token ID: “F” একা একটি বৈধ নাম।
  4. FIN পর্যন্ত। সেট {f3, i1}. FIND এখনো সম্পূর্ণ হয়নি, কিন্তু বেঁচে আছে; token এখনো ID.
  5. সংঘাত। D পড়ে {f4, i1}: f4 FIND-এর accepting, i1 ID-এর accepting. ধাপ ৪-এর min নিয়মে FIND (তালিকায় ১ নম্বর) জেতে।
  6. FINDE. f4 থেকে কোনো তীর নেই, তাই সেট {i1}, token ID. তাই FINDER লম্বা বলে পুরোটা ID: maximal munch আর priority একসঙ্গে কাজ করেছে।
  7. তুলনার চিহ্ন। শুরু থেকে > পড়ে {e1, g1}: g1 accepting, তাই GT; = পড়ে {e2}, token GE. এটি ছবি ২২.২-এর GT → GE তীর, এবার যন্ত্রিকভাবে পাওয়া।
  8. সারকথা। প্রতিটি DFA state-এর token = সেটে উপস্থিত accepting state-গুলোর মধ্যে সবচেয়ে উঁচু priority-র token. নির্মাণ শেষে lexer একটি টেবিল: (state, অক্ষর) → state, আর state → token.

এবার পুরো চোদ্দ token-এর lexer ব্রাউজারের Python-এ। কোডটি পুরো DFA আগে বানায় না; প্রতিটি অক্ষরে NFA-র state-সেট হালনাগাদ করে, শুধু দরকারি সারির subset construction. এটি পর্ব ১০-এর lazy DFA-র ধারণা, cache ছাড়া। Pattern-এর লেখার রীতি ছোট: ফাঁকা ঘরে আলাদা করা item, %L মানে অক্ষর বা _, %W অক্ষর, অঙ্ক বা _, %D অঙ্ক, %Q উদ্ধৃতিচিহ্ন বা নতুন লাইন ছাড়া যেকোনো অক্ষর, %S ফাঁকা অক্ষর; শেষে * মানে “শূন্য বা বেশি বার”. একটি NFA state হলো (token-এর নম্বর, pattern-এ অবস্থান)।

CLS = {"%L": lambda c: c.isascii() and (c.isalpha() or c == "_"),
       "%W": lambda c: c.isascii() and (c.isalnum() or c == "_"),
       "%D": lambda c: "0" <= c <= "9", "%Q": lambda c: c not in '"\n', "%S": str.isspace}
SPEC = [("FIND", "F I N D"), ("WHERE", "W H E R E"), ("AND", "A N D"),
        ("OR", "O R"), ("ID", "%L %W*"), ("NUM", "%D %D*"), ("STR", '" %Q* "'),
        ("GE", "> ="), ("LE", "< ="), ("NE", "! ="), ("GT", ">"), ("LT", "<"),
        ("EQ", "="), ("WS", "%S %S*")]            # list order = priority
TOK = [(n, [(x.rstrip("*"), x.endswith("*")) for x in p.split()]) for n, p in SPEC]
END = lambda t, i: i == len(TOK[t][1])           # (token, position) is accepting
def closure(S):                       # ε-move: a starred item may be skipped
    S, todo = set(S), list(S)
    while todo:
        t, i = todo.pop()
        if not END(t, i) and TOK[t][1][i][1] and (t, i + 1) not in S:
            S.add((t, i + 1)); todo.append((t, i + 1))
    return frozenset(S)
def step(S, c):                       # one symbol in the union of all NFAs
    ok = lambda it: CLS[it](c) if it in CLS else it == c
    return closure({(t, i if st else i + 1) for t, i in S if not END(t, i)
                    for it, st in [TOK[t][1][i]] if ok(it)})
winner = lambda S: min((t for t, i in S if END(t, i)), default=None)
START = closure({(t, 0) for t in range(len(TOK))})
def lex(src):
    pos, out = 0, []
    while pos < len(src):
        S, j, last = START, pos, None
        while j < len(src) and S:     # maximal munch: read on while alive
            S = step(S, src[j]); j += 1
            if winner(S) is not None: last = (j, winner(S))
        if last is None: out.append(("ERROR", src[pos])); pos += 1; continue
        if TOK[last[1]][0] != "WS": out.append((TOK[last[1]][0], src[pos:last[0]]))
        pos = last[0]
    return out
for q in ['FIND order WHERE amount >= 1000', 'AND district = "Dhaka"', "FINDER>=7", "a>=b>c @", "x<=-3"]:
    print(f"{q:31}", " ".join(f"{t}({v})" for t, v in lex(q)))

আসল আউটপুট (ব্রাউজারের Python):

FIND order WHERE amount >= 1000 FIND(FIND) ID(order) WHERE(WHERE) ID(amount) GE(>=) NUM(1000)
AND district = "Dhaka"          AND(AND) ID(district) EQ(=) STR("Dhaka")
FINDER>=7                       ID(FINDER) GE(>=) NUM(7)
a>=b>c @                        ID(a) GE(>=) ID(b) GT(>) ID(c) ERROR(@)
x<=-3                           ID(x) LE(<=) ERROR(-) NUM(3)

প্রথম দুই লাইনে বাজারঘরের পুরো query, দুই ভাগে: দশটি token, প্রতিটি keyword ঠিক keyword, আর "Dhaka" উদ্ধৃতিচিহ্নসহ একটি STR. তৃতীয় লাইনে stepper-এর ধাপ ৬: FINDER পুরোটা ID, কারণ লম্বা lexeme আগে বিবেচিত হয়, priority আসে শুধু সমান দৈর্ঘ্যে। চতুর্থ লাইনে >= একটি GE, কিন্তু b>c-এর > একটি GT, কারণ পরের অক্ষর = নয়। শেষে @ কোনো token-এর শুরু নয়, তাই ERROR. শেষ লাইন একটি সূক্ষ্ম কথা দেখায়: এই ভাষায় ঋণাত্মক সংখ্যার token নেই, তাই -3-এর - একটি ERROR আর 3 একটি আলাদা NUM. winner-এর min ঠিক নির্মাণ ৪.১-এর ধাপ ৪.

৫ · Scanner algorithm — শেষ গ্রহণ মনে রাখা, ফাঁকা ঘর আর error

উপরের lex ফাংশনটি কথায়: অবস্থান p থেকে DFA-কে শুরু state-এ বসান; অক্ষর পড়তে থাকুন, আর যতবার একটি accepting state-এ পৌঁছান, (অবস্থান, token) জোড়াটি “শেষ গ্রহণ” হিসেবে লিখে রাখুন; DFA dead state-এ গেলে বা input শেষ হলে থামুন; শেষ গ্রহণটি বের করুন আর তার ঠিক পরের অবস্থান থেকে আবার শুরু করুন। শেষ গ্রহণ না থাকলে error. উপপাদ্য ৪.২ বলে এই পদ্ধতি সংজ্ঞা ৩.১-এর ℓ আর j হুবহু খুঁজে পায়।

ফাঁকা ঘর আর comment. এরা সাধারণ token-এর মতোই নিয়ম পায়, শুধু বের হওয়ার সময় ফেলে দেওয়া হয়। লাইন-comment #[^\n]* পুরোপুরি regular. কিন্তু কিছু ভাষায় (যেমন Haskell, OCaml, Rust) block comment-এর ভেতরে block comment বসানো যায়; তখন খোলা আর বন্ধ চিহ্ন সমান সংখ্যায় মেলাতে হয়, যা anbn-এর মতো একটি non-regular language; pumping lemma (পর্ব ১৭) দিয়ে এটি প্রমাণ করা যায়। বাস্তব lexer তাই DFA-র পাশে একটি counter রাখে।

Error. শেষ গ্রহণ না থাকলে lexer-এর সামনে দুটি পথ: থেমে যাওয়া, অথবা panic mode recovery: একটি অক্ষর (বা পরের নিরাপদ জায়গা, যেমন ফাঁকা ঘর, পর্যন্ত) ফেলে দিয়ে error লিখে রাখা আর আবার শুরু করা, যাতে এক চালনায় অনেক ভুল ধরা যায়। দাম হলো বিভ্রান্তি: শেষ না হওয়া "Dhaka-য় "-টি error, তারপর Dhaka একটি সাধারণ ID. ভালো নকশা হলো ভুলের জন্যও একটি নিয়ম রাখা, যেমন STR-এর ঠিক পরে "[^"\n]* নামে UNTERMINATED_STRING, যাতে বার্তা স্পষ্ট হয়।

উপপাদ্য ৫.১ (Scanner-এর খরচ)

DFA-ভিত্তিক scanner দৈর্ঘ্য n-এর input-এ মোট বড়জোর n(n + 1)/2টি অক্ষর পড়ে, আর এই সীমা কিছু specification-এ ঠিক ঠিক অর্জিত হয়: token A = a আর AB = a∗b, input an. অন্যদিকে, যদি প্রতিটি চালনায় শেষ গ্রহণের পরে (গ্রহণ না থাকলে শুরুর পরে) DFA বড়জোর c ধাপে dead হয় বা input শেষ হয় (একটি ধ্রুবক c), তাহলে মোট পড়া বড়জোর (c + 1)n, অর্থাৎ রৈখিক।

প্রমাণ:

  1. উপরের সীমা: অবস্থান p থেকে শুরু হওয়া একটি চালনা বড়জোর n − p অক্ষর পড়ে, আর প্রতিটি চালনার পর p অন্তত 1 বাড়ে (ℓ ≥ 1, অথবা error-এ একটি অক্ষর বাদ)। তাই মোট ≤ n + (n − 1) + ⋯ + 1 = n(n + 1)/2. — উপপাদ্য ৩.২-এর ধাপ ৪
  2. সীমা অর্জিত: {a, a∗b}-এর DFA-তে a পড়ার পর state সবসময় বেঁচে থাকে, কারণ যত a-ই আসুক, পরে একটি b এলে AB সম্পূর্ণ হতে পারে। an-এ অবস্থান p থেকে scanner তাই বাকি n − p অক্ষর সবই পড়ে, input শেষে থামে, আর শেষ গ্রহণ শুধু দৈর্ঘ্য 1-এর A. পরের চালনা p + 1 থেকে। মোট ঠিক n(n + 1)/2. — DFA-র গঠন
  3. রৈখিক ক্ষেত্র: গ্রহণসহ প্রতিটি চালনায় পড়া = ℓ + (শেষ গ্রহণের পরে পড়া) ≤ ℓ + c, আর error-এর চালনায় পড়া ≤ c, এগোনো ১ অক্ষর। সব চালনার এগোনো যোগ করলে ঠিক n, আর চালনা বড়জোর nটি, তাই মোট ≤ n + cn. ∎ — যোগফল

বাস্তব ভাষার token-এ c ছোট: >-এর পর এক অক্ষর দেখলেই বোঝা যায় GE কি না। Thomas Reps ১৯৯৮ সালের একটি প্রবন্ধে (ACM TOPLAS) দেখান, কোন (DFA state, অবস্থান) জোড়া থেকে আগে ব্যর্থ হতে হয়েছে তা মনে রেখে maximal munch রৈখিক সময়ে করা যায়।

নিচের stepper এবার পুরো বাজারঘর query-টি token ধরে ধরে পড়ে। কলাম নম্বর ১ থেকে গোনা; ৫৪টি অক্ষরে ১০টি token আর ৯টি ফাঁকা ঘর।

1FIND2order3WHERE4amount5>=610007AND district =8"Dhaka"9parser-এর কাছে
এই token
কলাম
সংঘাত বা নিয়ম
token
  1. FIND. col 1–4-এ FIND আর ID দুটিই সম্পূর্ণ; col 5-এর ফাঁকা ঘরে DFA dead. শেষ গ্রহণের state-এ দুটি accepting অংশ ছিল, priority-তে keyword FIND.
  2. order. col 5-এর ফাঁকা ঘর একটি WS, বাদ। col 6–10-এ শুধু ID বেঁচে থাকে; “order” কোনো keyword নয়।
  3. WHERE. আবার keyword আর ID-এর সমান দৈর্ঘ্যের সংঘাত, আবার priority. তাই WHERE নামে কোনো কলাম রাখা যাবে না।
  4. amount. col 18–23, একটি সাধারণ ID; এটি সত্যিই কলামের নাম কি না, তা পরে অর্থ যাচাইয়ের ধাপে।
  5. >=. col 25-এ GT সম্পূর্ণ হয়েও পড়া চলে; col 26-এর = GE সম্পূর্ণ করে; col 27-এর ফাঁকা ঘরে dead. Maximal munch-এ GE.
  6. 1000. col 28–31, NUM; attribute হিসেবে মান 1000-ও দেওয়া যায়।
  7. AND district =. col 33–35-এ AND (priority), col 37–44-এ ID(district), col 46-এ EQ; = এর পর ফাঁকা ঘর, তাই GE-র মতো লম্বা কিছু নেই।
  8. "Dhaka". col 48-এ উদ্ধৃতিচিহ্ন পড়ে শুধু STR বেঁচে থাকে, কিন্তু কোনো accepting state নেই; col 49–53-এও নেই। col 54-এ শেষ উদ্ধৃতিচিহ্নে প্রথম ও একমাত্র গ্রহণ: পুরো ৭ অক্ষরের lexeme.
  9. Parser-এর কাছে। ৯টি WS বাদ দিয়ে ১০টি token: FIND ID WHERE ID GE NUM AND ID EQ STR. Parser এখন grammar মিলিয়ে দেখবে এটি একটি বৈধ query কি না (মডিউল ৫ ও ৭)।

এবার একটি ছোট দৃশ্যায়ন: নিচের JavaScript কোড একই scanner-কে প্রতিটি অক্ষরে থামিয়ে দেখায় কোন token বেঁচে আছে আর শেষ গ্রহণ কোথায়। last: GE@3 মানে input-এর প্রথম ৩টি অক্ষর পর্যন্ত একটি GE সম্পূর্ণ হয়েছিল। JavaScript-এর \w (u flag ছাড়া) শুধু ASCII অক্ষর, অঙ্ক আর _ মেলায়; অংশ ৮-এ Python-এর \w-এর সঙ্গে এর পার্থক্য দেখবেন।

// tokens in priority order; a pattern is a list of [test, starred?] items
const L = c => /[A-Za-z_]/.test(c), W = c => /\w/.test(c), D = c => /[0-9]/.test(c);
const lit = s => [...s].map(ch => [c => c === ch, false]);
const TOK = [["FIND", lit("FIND")], ["ID", [[L, false], [W, true]]],
  ["NUM", [[D, false], [D, true]]], ["GE", lit(">=")], ["GT", lit(">")],
  ["EQ", lit("=")], ["WS", [[c => c === " ", false], [c => c === " ", true]]]];
const end = ([t, i]) => i === TOK[t][1].length;
function close(S) {                     // ε-move: a starred item may be skipped
  const seen = new Map(S.map(p => [p.join(), p])), todo = [...S];
  while (todo.length) {
    const [t, i] = todo.pop(), q = [t, i + 1];
    if (!end([t, i]) && TOK[t][1][i][1] && !seen.has(q.join())) { seen.set(q.join(), q); todo.push(q); }
  }
  return [...seen.values()];
}
const step = (S, c) => close(S.filter(p => !end(p) && TOK[p[0]][1][p[1]][0](c))
  .map(([t, i]) => [t, TOK[t][1][i][1] ? i : i + 1]));
const winner = S => Math.min(...S.filter(end).map(([t]) => t));   // Infinity = none
const alive = S => [...new Set(S.map(([t]) => TOK[t][0]))].join(",") || "(dead)";
function show(src) {
  console.log("input: " + src);
  for (let pos = 0; pos < src.length; ) {
    let S = close(TOK.map((_, t) => [t, 0])), j = pos, last = null;
    while (j < src.length && S.length) {
      S = step(S, src[j++]);
      if (winner(S) < Infinity) last = [j, winner(S)];
      console.log(`  read "${src.slice(pos, j)}"`.padEnd(16) + `alive: ${alive(S)}`.padEnd(22) + `last: ${last ? TOK[last[1]][0] + "@" + last[0] : "-"}`);
    }
    if (!last) { console.log(`  ERROR at ${pos + 1}: ${src[pos]}`); pos++; continue; }
    console.log(`=> ${TOK[last[1]][0]} "${src.slice(pos, last[0])}"`);
    pos = last[0];
  }
}
show("n>=5"); show("FINDx=");

আসল আউটপুট (ব্রাউজারের JavaScript):

input: n>=5
  read "n"      alive: ID             last: ID@1
  read "n>"     alive: (dead)         last: ID@1
=> ID "n"
  read ">"      alive: GE,GT          last: GT@2
  read ">="     alive: GE             last: GE@3
  read ">=5"    alive: (dead)         last: GE@3
=> GE ">="
  read "5"      alive: NUM            last: NUM@4
=> NUM "5"
input: FINDx=
  read "F"      alive: FIND,ID        last: ID@1
  read "FI"     alive: FIND,ID        last: ID@2
  read "FIN"    alive: FIND,ID        last: ID@3
  read "FIND"   alive: FIND,ID        last: FIND@4
  read "FINDx"  alive: ID             last: ID@5
  read "FINDx=" alive: (dead)         last: ID@5
=> ID "FINDx"
  read "="      alive: EQ             last: EQ@6
=> EQ "="

প্রথম অংশটি অংশ ৩-এর stepper, এবার যন্ত্রের নিজের মুখে: “n>”-এ dead, তাই ID “n”; “>”-এ GE আর GT দুটিই বেঁচে, শেষ গ্রহণ GT@2; “>=”-এ শুধু GE, শেষ গ্রহণ GE@3; “>=5”-এ dead, তাই GE বের হয়। দ্বিতীয় অংশে “FIND” পর্যন্ত FIND আর ID দুটিই বেঁচে, আর দৈর্ঘ্য 4-এ শেষ গ্রহণ FIND@4, কারণ priority-তে FIND আগে। কিন্তু x পড়ার পর FIND মরে যায়, ID বেঁচে থাকে, শেষ গ্রহণ ID@5-এ সরে যায়। প্রতিটি token-এর শেষে scanner একটি বাড়তি অক্ষর পড়ে dead হয়, যা পরের token-এ আবার পড়া হয়: উপপাদ্য ৫.১-এর c = 1.

৬ · Maximal munch-এর ফাঁদ — a--b, >> আর এক regex-এর lexer

মানুষ যেভাবে পড়ে, lexer সবসময় সেভাবে পড়ে না। কয়েকটি ক্লাসিক উদাহরণ:

  • a--b (C-ধরনের ভাষায়): মানুষ হয়তো “a বিয়োগ ঋণাত্মক b” পড়েন, কিন্তু lexer সবচেয়ে লম্বা -- নেয়: a, --, b. ফল একটি syntax error. সঠিক রূপ a - -b.
  • x+++++y: C standard-এর lexical অংশে এই উদাহরণটিই দেওয়া আছে। Lexer পায় x ++ ++ + y, যা অবৈধ, যদিও x ++ + ++ y বৈধ হতো। Lexer parser-কে জিজ্ঞেস করে না।
  • vector<vector<int>>: শেষের দুটি > মিলে right-shift token >>. পুরোনো C++-এ তাই > > লিখতে হতো; C++11 থেকে ভাষার নিয়মে এই জায়গায় >>-কে দুটি বন্ধনী হিসেবে ধরা হয়। এটি lexer-কে parser-এর প্রসঙ্গ জানানোর একটি সুপরিচিত উদাহরণ।
  • এক regex-এর lexer: অনেকে সব token-কে একটি বড় regex-এ | দিয়ে জোড়েন। কিন্তু Python-এর re বা JavaScript-এর RegExp একটি backtracking matcher; এরা |-এর বিকল্পগুলো বাঁ থেকে চেষ্টা করে আর প্রথম মেলাটি নেয়, সবচেয়ে লম্বাটি নয় (দুই ধরনের engine-এর তুলনা পর্ব ২১-এ)। তাই > আগে লিখলে >= কখনো আসবে না। Maximal munch তখন নির্ভর করে লেখার ক্রমের ওপর।

নিচের ব্লক প্রথমে একটি ছোট “সব নিয়মের মধ্যে সবচেয়ে লম্বা” lexer দিয়ে C-ধরনের উদাহরণগুলো চালায়, তারপর এক-regex lexer-এর ফাঁদ, আর শেষে উপপাদ্য ৫.১-এর {a, a∗b} specification-এ scanner মোট কতটি অক্ষর পড়ে তা গোনে। DFA-টি হাতে লেখা: state 0 শুরু, 1 মানে একটি a (A গৃহীত), 2 মানে একাধিক a, 3 মানে b পড়া হয়েছে (AB গৃহীত)।

import re

def munch(src, rules):                # maximal munch over (name, regex) rules
    pos, out = 0, []
    while pos < len(src):
        best = None                   # (end, name); ties keep the earlier rule
        for name, rx in rules:
            m = re.compile(rx).match(src, pos)
            if m and m.end() > pos and (best is None or m.end() > best[0]):
                best = (m.end(), name)
        if best is None: out.append("ERR:" + src[pos]); pos += 1; continue
        if best[1] != "WS": out.append(src[pos:best[0]])
        pos = best[0]
    return out

C = [("OP", r"\+\+|--|>>|->|[-+<>=;]"), ("ID", r"[A-Za-z_][A-Za-z0-9_]*"), ("WS", r"\s+")]
for s in ["a--b", "x+++++y", "x++ + ++y", "vector<vector<int>>"]:
    print(f"{s:20}", " ".join(munch(s, C)))

for alt in [r">|>=|=", r">=|>|="]:    # ONE master regex: first alternative wins
    print(f"re.findall({alt!r}, '>=') ->", re.findall(alt, ">="))

D = {(0, "a"): 1, (1, "a"): 2, (2, "a"): 2, (0, "b"): 3, (1, "b"): 3, (2, "b"): 3}
ACC = {1: "A", 3: "AB"}               # tokens A = a and AB = a*b
def reads(src):                       # characters read by the scanner in total
    pos = cnt = 0
    while pos < len(src):
        s, j, last = 0, pos, None
        while j < len(src) and (s, src[j]) in D:
            s = D[(s, src[j])]; j += 1; cnt += 1
            if s in ACC: last = j
        pos = last
    return cnt
for n in [10, 20, 40, 80]:
    print(f"n={n:2}  a^n: {reads('a' * n):4} reads   a^n b: {reads('a' * n + 'b'):2} reads")

আসল আউটপুট (ব্রাউজারের Python):

a--b                 a -- b
x+++++y              x ++ ++ + y
x++ + ++y            x ++ + ++ y
vector<vector<int>>  vector < vector < int >>
re.findall('>|>=|=', '>=') -> ['>', '=']
re.findall('>=|>|=', '>=') -> ['>=']
n=10  a^n:   55 reads   a^n b: 11 reads
n=20  a^n:  210 reads   a^n b: 21 reads
n=40  a^n:  820 reads   a^n b: 41 reads
n=80  a^n: 3240 reads   a^n b: 81 reads

প্রথম চার লাইন ক্লাসিক ফাঁদগুলো: a--b-এ --, x+++++y-এ x ++ ++ + y, আর ফাঁকা ঘর দিলে x ++ + ++ y. চতুর্থ লাইনে শেষে একটি >> token: আধুনিক C++ parser-কে এটিকে দুই ভাগে ভাঙতে হয়। পরের দুই লাইনে এক-regex-এর ফাঁদ: >|>=|= লিখলে >= ভেঙে ['>', '='], আর লম্বা বিকল্প আগে লিখলে ['>=']. শেষ চার লাইন উপপাদ্য ৫.১-এর সংখ্যা: an-এ ঠিক n(n + 1)/2 পড়া (55, 210, 820, 3240), n দ্বিগুণ হলে প্রায় চার গুণ; শেষে একটি b থাকলে মাত্র n + 1, কারণ প্রথম চালনাতেই পুরো input একটি AB.

PLY আর Lark এই এক-regex পদ্ধতিই ব্যবহার করে, তাই তারা নিয়মগুলো এমন ক্রমে জোড়ে যাতে লম্বা বিকল্প আগে আসে (অংশ ৭); lex/flex নিজের DFA বানায়, তাই সেখানে ক্রম শুধু সমান দৈর্ঘ্যে কাজে লাগে।

৭ · সত্যিকারের run — হাতে লেখা scanner, PLY আর Lark

একটি lexer generator token-এর নিয়মের তালিকা থেকে lexer-এর কোড বানায়। নিজের scanner যাচাইয়ের ভালো উপায়: একই specification একটি প্রতিষ্ঠিত generator-কে দিয়ে ফল মেলানো। নিচের কাজটি ডেস্কটপে uv দিয়ে বানানো একটি ছোট প্রকল্পে চালানো হয়েছে: Python 3.12, PLY 3.11 (BSD licence; David Beazley-র লেখা, lex আর yacc-এর Python রূপ) আর Lark 1.3.1 (MIT licence). দুটি package-এর উৎস-কোডে কোনো network বা usage-reporting অংশ নেই (scratch-এ খুঁজে দেখা হয়েছে)। প্রকল্পের mine.py হলো অংশ ৪-এর Python lexer-এর হুবহু কপি।

PLY-তে প্রতিটি token একটি t_ দিয়ে শুরু হওয়া নাম: string হলে সরাসরি regex, function হলে তার docstring-এ regex. PLY-এর উৎস-কোড (lex.py) দেখায়, সে সব নিয়ম একটি বড় regex-এ জোড়ে এই ক্রমে: আগে function-নিয়মগুলো, ফাইলে যে ক্রমে লেখা; তারপর string-নিয়মগুলো, regex-এর দৈর্ঘ্য অনুযায়ী লম্বা থেকে ছোট। এ কারণে t_GE = r">=" নিজে থেকেই t_GT-এর আগে বসে। Keyword-এর জন্য PLY-এর নথির পরামর্শ: আলাদা নিয়ম না লিখে একটি ID-নিয়মে মিলিয়ে তারপর একটি অভিধানে খোঁজা।

import ply.lex as lex

reserved = {"FIND": "FIND", "WHERE": "WHERE", "AND": "AND", "OR": "OR"}
tokens = ["ID", "NUM", "STR", "GE", "LE", "NE", "GT", "LT", "EQ"] + list(reserved.values())

t_GE, t_LE, t_NE = r">=", r"<=", r"!="     # string rules: PLY sorts them
t_GT, t_LT, t_EQ = r">", r"<", r"="        # by decreasing regex length
t_ignore = " \t"

def t_ID(t):
    r"[A-Za-z_][A-Za-z0-9_]*"
    t.type = reserved.get(t.value, "ID")   # keyword lookup, PLY's advice
    return t

def t_NUM(t):
    r"[0-9]+"
    return t

def t_STR(t):
    r'"[^"\n]*"'
    return t

def t_newline(t):
    r"\n+"
    t.lexer.lineno += len(t.value)

def t_error(t):
    print(f"  PLY error: illegal character {t.value[0]!r} at col {t.lexpos + 1}")
    t.lexer.skip(1)

lexer = lex.lex()

def lex_ply(src):
    lexer.input(src)
    return [(tok.type, tok.value) for tok in lexer]

তুলনার script বাজারঘরের query দুই lexer-এ চালায়, তারপর token-এর টুকরো থেকে এলোমেলোভাবে বানানো (seed 22) ২০০০টি query-তে দুটির ফল মেলায়, আর শেষে ইচ্ছাকৃতভাবে ভাঙা একটি query দেয়: মাঝে একটি @, আর শেষ উদ্ধৃতিচিহ্ন নেই।

from importlib.metadata import version
import random
import mine
from ply_lexer import lex_ply

print("ply", version("ply"))
q = 'FIND order WHERE amount >= 1000 AND district = "Dhaka"'
own, errs = mine.lex(q)
for typ, val in own:
    print(f"  {typ:6} {val}")
print("same stream as PLY:", own == lex_ply(q))

random.seed(22)                          # random queries from the token alphabet
parts = ["FIND", "WHERE", "AND", "OR", "FINDER", "x1", "amount", "42", "007",
         '"Dhaka"', ">=", ">", "=", "<", "<=", "!=", " ", "  "]
same = 0
for _ in range(2000):
    s = "".join(random.choice(parts) for _ in range(random.randint(1, 12)))
    same += mine.lex(s)[0] == lex_ply(s)
print("random queries with identical streams:", same, "/ 2000")

bad = 'FIND order WHERE amount >= 1000 @ district = "Dhaka'
print("broken query:", bad)
print("  own errors (col, char):", mine.lex(bad)[1])
print("  own tokens after errors:", mine.lex(bad)[0][-3:])
print("  PLY tokens:", lex_ply(bad)[-3:])

সত্যিকারের run (ডেস্কটপ, PLY 3.11, Python 3.12; mine.py-এর lex token-এর তালিকা আর error-এর তালিকা আলাদা ফেরত দেয়):

~/bazarghar-toc$ uv run python compare.py
ply 3.11
  FIND   FIND
  ID     order
  WHERE  WHERE
  ID     amount
  GE     >=
  NUM    1000
  AND    AND
  ID     district
  EQ     =
  STR    "Dhaka"
same stream as PLY: True
random queries with identical streams: 2000 / 2000
broken query: FIND order WHERE amount >= 1000 @ district = "Dhaka
  own errors (col, char): [(33, '@'), (46, '"')]
  own tokens after errors: [('ID', 'district'), ('EQ', '='), ('ID', 'Dhaka')]
  PLY error: illegal character '@' at col 33
  PLY error: illegal character '"' at col 46
  PLY tokens: [('ID', 'district'), ('EQ', '='), ('ID', 'Dhaka')]

দশটি token অংশ ৫-এর stepper-এর সঙ্গে হুবহু মেলে, আর PLY-এর ধারাও একই। ২০০০টি এলোমেলো query-র প্রতিটিতে দুই lexer একমত. ভাঙা query-তে দুটিই col 33-এ @ আর col 46-এ "-কে অবৈধ বলেছে আর panic mode-এ এক অক্ষর বাদ দিয়ে চলেছে। ফলে দুটিতেই শেষে Dhaka একটি সাধারণ ID: অংশ ৫-এ বলা বিভ্রান্তিকর ফল, এবার সত্যিকারের দুই tool-এ।

Lark একটি parser generator (পর্ব ৪০-এ বিস্তারিত), যার সঙ্গে একটি lexer আসে। lexer="basic" দিলে সে grammar-এর terminal থেকে একটি আলাদা lexer বানায়, ঠিক এই পর্বের ছক। Lark-এর উৎস-কোড (lexer.py) পড়ে দেখা গেছে, terminal-গুলো সাজানো হয় আগে priority, তারপর pattern-এর সর্বোচ্চ সম্ভাব্য দৈর্ঘ্য (লম্বা আগে) ধরে; আর "FIND"-এর মতো keyword, যা ID-এর regex-ও মেলায়, আলাদা বিকল্প হিসেবে থাকে না: ID মেলার পর পুরো lexeme কোনো keyword কি না দেখে ধরন বদলানো হয়, PLY-এর অভিধানের মতোই।

GRAMMAR = r"""
start: "FIND" ID "WHERE" cond (("AND" | "OR") cond)*
cond: ID OP value
value: NUM | STR
OP: ">=" | "<=" | "!=" | ">" | "<" | "="
ID: /[A-Za-z_][A-Za-z0-9_]*/
NUM: /[0-9]+/
STR: /"[^"\n]*"/
%ignore /[ \t\n]+/
"""
p = Lark(GRAMMAR, parser="lalr", lexer="basic")
toks = [(t.type, str(t)) for t in p.lex(q)]          # q = the same query
print(" ", " ".join(t for t, _ in toks))
print("  same lexemes as own:", [v for _, v in toks] == [v for _, v in mine.lex(q)[0]])
try:
    p.parse('FIND order WHERE amount >= 1000 @ x = 1')
except UnexpectedCharacters as e:
    print("  lark error: line", e.line, "col", e.column, repr(e.char))

সত্যিকারের run (ডেস্কটপ, Lark 1.3.1; import আর version-এর লাইন বাদ দিয়ে দেখানো, পুরো ফাইলের বাকি অংশ অংশ ৮-এ):

~/bazarghar-toc$ uv run python lark_check.py
lark 1.3.1
  FIND ID WHERE ID OP NUM AND ID OP STR
  same lexemes as own: True
  lark error: line 1 col 33 '@'
…

Lark-এ সব তুলনার চিহ্ন এক OP terminal, আর keyword-এর নাম তাদের লেখা থেকেই; কিন্তু lexeme-এর ধারা আমাদের lexer-এর সঙ্গে হুবহু এক। Error-এ Lark থামে প্রথম অবৈধ অক্ষরে, line আর column-সহ, panic mode ছাড়া।

lex আর flex. C-ভিত্তিক জগতের ক্লাসিক tool lex আর তার উত্তরসূরি flex. এখানে নিয়ম লেখা হয় একটি .l ফাইলে, আর tool সরাসরি একটি DFA বানিয়ে C কোডে টেবিল হিসেবে লেখে। flex-এর manual-এর নিয়ম এই পর্বের দুই নিয়মই: সবচেয়ে লম্বা মেলা, আর সমান দৈর্ঘ্যে ফাইলে আগে লেখা নিয়ম। এই কম্পিউটারে C compiler বা flex নেই, তাই নিচের ফাইলটি চালানো হয়নি; এটি শুধু গঠন দেখানোর উদাহরণ।

%%
"FIND"                  { return FIND; }
"WHERE"                 { return WHERE; }
">="                    { return GE; }
">"                     { return GT; }
"="                     { return EQ; }
[A-Za-z_][A-Za-z0-9_]*  { return ID; }
[0-9]+                  { return NUM; }
\"[^"\n]*\"             { return STR; }
[ \t\n]+                { /* skip whitespace */ }
.                       { lex_error(yytext); }
%%

শেষ নিয়ম . (যেকোনো একটি অক্ষর) সবচেয়ে নিচে, তাই এটি শুধু তখনই জেতে, যখন অন্য কোনো নিয়ম একটি অক্ষরও মেলায় না: একটি পরিষ্কার error-নিয়ম। আরেকটি পরিচিত tool re2c, যা টেবিলের বদলে DFA-কে সরাসরি C কোডের শাখায় (goto আর switch) লেখে; এমন “direct-coded” lexer প্রায়ই টেবিল-ভিত্তিক lexer-এর চেয়ে দ্রুত বলে উল্লেখ করা হয়। flex-এর licence BSD-ধরনের আর re2c-এর উৎস public domain হিসেবে প্রকাশিত বলে উল্লেখ আছে; ব্যবহারের আগে নিজে তাদের সাইটে মিলিয়ে নিন।

Lex-এর বর্ণনা সাধারণত Bell Labs-এর Mike Lesk আর Eric Schmidt-এর ১৯৭৫ সালের প্রতিবেদন “Lex — A Lexical Analyzer Generator”-এর সঙ্গে যুক্ত; এটি Stephen Johnson-এর yacc parser generator-এর সঙ্গী হিসেবে Unix-এ আসে। flex (“fast lex”) ১৯৮০-এর দশকের শেষ দিকে Vern Paxson-এর কাজ হিসেবে পরিচিত। Regex থেকে finite automaton বানিয়ে স্বয়ংক্রিয়ভাবে lexer তৈরির ধারণা আরও পুরোনো; Johnson, Porter, Ackley আর Ross-এর ১৯৬৮ সালের একটি Communications of the ACM প্রবন্ধ এর প্রথম দিকের উদাহরণ হিসেবে উল্লেখ করা হয়। প্রতিটি সালই উৎসভেদে সামান্য আলাদা লেখা দেখা যায়।

৮ · Unicode, বাংলা লেখা আর বাস্তব lexer-এর প্রসঙ্গ

এ পর্যন্ত alphabet ছিল ASCII. বাস্তবে input হলো Unicode, যেখানে লক্ষাধিক অক্ষর। তত্ত্ব বদলায় না: Σ এখনো সসীম, শুধু বড়। কিন্তু “অক্ষর” আর “অঙ্ক”-এর সংজ্ঞা বদলে যায়, আর সেখানেই ফাঁদ। পর্ব ১৩-এ দেখেছেন, Python-এর \d বাংলা অঙ্ক ০–৯-কেও মেলায়। Lexer-এ এর মানে, বাজারঘরের query-তে কেউ দাম >= ১০০০ লিখলে কী হবে, তা নির্ভর করে NUM-এর pattern কীভাবে লেখা তার ওপর। নিচের ব্লক Python-এর নিজের lexer (standard library-র tokenize module) আর re দিয়ে এটি পরীক্ষা করে।

import io, re, token, tokenize

def py_tokens(src):                   # Python's own lexer (stdlib tokenize)
    skip = {token.NEWLINE, token.NL, token.ENDMARKER}
    try:
        return [f"{token.tok_name[t.exact_type]}:{t.string}"
                for t in tokenize.generate_tokens(io.StringIO(src).readline)
                if t.type not in skip]
    except tokenize.TokenError as e:
        return ["TokenError: " + e.args[0]]

for s in ["x>>=y-->z", "a = 1if b else 2", "s = 'Dhaka", "দাম = 1000", "দাম = ১০০০"]:
    print(f"{s:16}", *py_tokens(s))
try:
    compile("দাম = ১০০০", "<query>", "exec")
except SyntaxError as e:
    print("compile ->", e.msg)

text = "দাম মূল্য ১০০০"
print("re \\w+       :", re.findall(r"\w+", text))
print("split()      :", text.split(), "| 'মূল্য'.isidentifier():", "মূল্য".isidentifier())
print("re \\d+       :", re.findall(r"\d+", text), "| int('১০০০') + 1 =", int("১০০০") + 1)
print("re.ASCII \\d+ :", re.findall(r"\d+", text, re.ASCII))

আসল আউটপুট (ব্রাউজারের Python):

x>>=y-->z        NAME:x RIGHTSHIFTEQUAL:>>= NAME:y MINUS:- RARROW:-> NAME:z
a = 1if b else 2 NAME:a EQUAL:= NUMBER:1 NAME:if NAME:b NAME:else NUMBER:2
s = 'Dhaka       TokenError: unterminated string literal (detected at line 1)
দাম = 1000       NAME:দাম EQUAL:= NUMBER:1000
দাম = ১০০০       NAME:দাম EQUAL:= NAME:১০০০
compile -> invalid character '১' (U+09E7)
re \w+       : ['দ', 'ম', 'ম', 'ল', 'য', '১০০০']
split()      : ['দাম', 'মূল্য', '১০০০'] | 'মূল্য'.isidentifier(): True
re \d+       : ['১০০০'] | int('১০০০') + 1 = 1001
re.ASCII \d+ : []

প্রথম তিন লাইন Python-এর নিজের maximal munch: x>>=y-->z-এ >>= একটি token, আর --> হয়ে যায় - আর -> (Python-এ -- নামে কোনো token নেই, কিন্তু function annotation-এর -> আছে)। 1if ফাঁকা ছাড়াই দুই token, কারণ অঙ্কের পর i কোনো সংখ্যার অংশ নয়। লক্ষ করুন, tokenize keyword-কেও NAME বলে; keyword আলাদা করা হয় পরে। শেষ না হওয়া string একটি স্পষ্ট TokenError দেয়। চতুর্থ লাইনে বাংলা নাম দাম একটি বৈধ NAME, কারণ Python ৩ থেকে Unicode identifier চলে (PEP 3131). কিন্তু পঞ্চম লাইনে ১০০০-ও NAME হিসেবে এসেছে, আর compile সেটিকে “invalid character” বলে বাতিল করেছে: Python-এর lexer প্রথমে অ-ASCII অক্ষর উদারভাবে জড়ো করে, পরে যাচাই করে। সংখ্যা-literal শুধু ASCII অঙ্কে।

পরের চার লাইন re-এর আচরণ, আর এটিই বাংলা লেখার সবচেয়ে বড় ফাঁদ। \w+ “দাম”-কে ভেঙে দ আর ম করেছে, আর “মূল্য”-কে ম, ল, য: আকার (া), ঊ-কার (ূ) আর হসন্ত (্) Unicode-এ combining mark (category Mc বা Mn), আর Python-এর \w সেগুলো মেলায় না। অথচ "মূল্য".isidentifier() True, কারণ identifier-এর Unicode নিয়ম (UAX #31-ভিত্তিক) এই চিহ্নগুলো নামের ভেতরে অনুমতি দেয়। অর্থাৎ \w+ দিয়ে লেখা ID-নিয়ম বাংলা নামকে টুকরো করে ফেলবে। \d+ বাংলা অঙ্ক মেনে নেয়, আর int নীরবে 1000 বানায়, যা ভালো বা খারাপ দুটোই হতে পারে; re.ASCII দিলে কিছুই মেলে না।

একই প্রশ্ন সত্যিকারের run-এও করা হয়েছিল, PLY-প্রকল্পের lark_check.py-এর শেষ অংশে, আমাদের ASCII-নিয়মের lexer দিয়ে:

unicode: দাম >= ১০০০
  own (ASCII classes): ([('GE', '>=')], [(1, 'দ'), (2, 'া'), (3, 'ম'), (8, '১'), (9, '০'), (10, '০'), (11, '০')])
  re \w+ tokens: ['দ', 'ম', '>=', '১০০০']
  int('১০০০') = 1000 | 'দাম'.isidentifier() = True

আমাদের ASCII-নিয়মের lexer প্রতিটি বাংলা অক্ষরকে আলাদা error বলেছে: ভুল, কিন্তু নীরব নয়। শিক্ষা: নামের নিয়ম Unicode-এর identifier-সংজ্ঞা মেনে লিখুন, আর সংখ্যায় বাংলা অঙ্ক চলবে কি না সচেতনভাবে ঠিক করুন (ভাবনার প্রশ্ন ০৫)।

প্রসঙ্গ-নির্ভর lexing. বিশুদ্ধ তত্ত্বে lexer parser-এর কথা জানে না। বাস্তবে কয়েকটি ভাষায় এই দেয়াল ভাঙতে হয়। C-তে typedef-নাম চিনতে lexer symbol table দেখে (lexer hack); JavaScript-এ / ভাগ না regex literal, তা আগের token ঠিক করে; Python-এর INDENT/DEDENT আসে একটি stack থেকে (ভাবনার প্রশ্ন ০৪)। আর কিছু parser lexer ছাড়াই অক্ষরের ওপর সরাসরি কাজ করে, scannerless parsing; ভাবনার প্রশ্ন ০১ দেখুন।

আরও গভীরে: Maximal munch-এর রৈখিক-সময়ের algorithm (Reps, ১৯৯৮) থেকে সীমিত মেমরিতে streaming tokenization পর্যন্ত গবেষণা চলছে। Brzozowski derivative (পর্ব ১৪-এর আলোচনা) দিয়ে সরাসরি lexer-এর DFA বানানোর পদ্ধতি Owens, Reppy আর Turon ২০০৯ সালে বাস্তবে কার্যকর বলে দেখান। আরেকটি দিক “lexer-এর সঠিকতা যন্ত্রে প্রমাণ”: proof assistant-এ যাচাই-করা lexer generator নিয়ে প্রকাশিত কাজ আছে, যাতে regex থেকে DFA আর maximal munch দুটিই প্রমাণিত।

পরীক্ষা ও ইন্টারভিউতে: বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় এই ধরনের প্রশ্ন প্রায়ই আসে:

  • Token, lexeme আর pattern-এর পার্থক্য কী? Token একটি শ্রেণির নাম (ID), lexeme input-এর আসল টুকরো (amount), pattern সেই শ্রেণির নিয়ম (একটি regex).
  • x+++++y কীভাবে tokenize হয়? Maximal munch-এ x ++ ++ + y, যা অবৈধ; lexer বিকল্প ভাঙন খোঁজে না।
  • Keyword আর identifier-এর সংঘাত কীভাবে মেটে? সমান দৈর্ঘ্যে priority (keyword আগে), অথবা ID মিলিয়ে একটি keyword-টেবিলে খোঁজা; লম্বা lexeme (FINDER) সবসময় ID.
  • কয়েকটি regex থেকে lexer-এর DFA কীভাবে বানাবেন? প্রতিটির NFA, নতুন শুরু থেকে ε-তীরে union, subset construction, আর প্রতিটি DFA state-এ সবচেয়ে উঁচু priority-র accepting token.
  • Lexer কেন parser থেকে আলাদা? Token-এর গঠন regular, তাই DFA-তে দ্রুত ও সরল; বন্ধনী মেলানোর মতো non-regular কাজ grammar-এর।

৯ · AI-এর যুগে lexical analysis

AI assistant-এর লেখা lexer প্রথম কয়েকটি উদাহরণে ঠিকই চলে; ভুল লুকিয়ে থাকে সংঘাতের কোণে। বারবার দেখা ভুলগুলো:

AI-এর ভুলকীভাবে ধরবেন
এক বড় regex-এ ছোট বিকল্প আগে (>|>=), ফলে >= দুই token>=, <=, != আলাদা করে চালিয়ে দেখা
ID-নিয়ম keyword-এর আগে, ফলে FIND একটি IDপ্রতিটি keyword আর তার লম্বা রূপ (FINDER) দিয়ে পরীক্ষা
\s* বা [0-9]*-এর মতো ফাঁকা string মেলানো নিয়ম, ফলে অসীম লুপপ্রতিটি pattern-এ ε ∉ L(R) যাচাই, যেমন re.fullmatch(rx, "")
\w আর \d দিয়ে নাম ও সংখ্যা, বাংলা বা অন্য লিপির কথা না ভেবেবাংলা নাম আর বাংলা অঙ্কের input দিয়ে চালানো
“maximal munch সবসময় একটি ভাঙন খুঁজে পায়” বা “lexer nested comment-ও regex-এ পারে” দাবি{ab, a, bc}-এ abc, আর anbn-এর pumping যুক্তি মনে রাখা
Error-নিয়ম না রাখা, ফলে অজানা অক্ষরে crash বা নীরবে বাদ@, শেষ না হওয়া string আর ফাঁকা input দিয়ে পরীক্ষা
flex বা PLY-এর বানানো option, ভুল version বা ভুল সালTool-এর নিজের manual আর উৎস-কোডে মিলিয়ে দেখা

AI-কে ভালোভাবে কাজে লাগানোর উপায়: শুধু কোড না চেয়ে নিয়মের ক্রম, সংঘাতের ব্যাখ্যা আর একটি স্বাধীন যাচাইয়ের পরীক্ষা চাওয়া, তারপর নিজে চালানো।

আমি গণনার তত্ত্ব শিখছি। একটি ছোট query ভাষার জন্য Python-এ (শুধু standard library) একটি lexer লেখো। Token: keyword FIND, WHERE, AND, OR; ID = [A-Za-z_][A-Za-z0-9_]*; NUM = [0-9]+; STR = "..." (ভেতরে " বা নতুন লাইন নেই); GE, LE, NE, GT, LT, EQ; ফাঁকা ঘর বাদ। ১. Maximal munch আর rule priority কীভাবে মানছ, নিয়মের ক্রম দিয়ে ব্যাখ্যা করো। ২. প্রতিটি pattern ফাঁকা string মেলায় না, তা কোডে assert করো। ৩. অজানা অক্ষর আর শেষ না হওয়া string-এর জন্য আলাদা error দাও, column নম্বরসহ। ৪. এই input-গুলোর token-ধারা লিখে দাও: "FINDER>=7", "a>=b>c", "x<=-3", "WHERE=1", আর শেষ উদ্ধৃতিচিহ্ন ছাড়া "Dhaka লেখাটি। ৫. বাংলা নাম (দাম) আর বাংলা অঙ্ক (১০০০) এলে তোমার lexer কী করে, বলো, আর কেন। ৬. শেষে একটি test দাও, যা এলোমেলোভাবে বানানো ১০০০টি input-এ তোমার lexer-কে একটি সরল "সব নিয়মের মধ্যে সবচেয়ে লম্বা মেলা" lexer-এর সঙ্গে মেলায়।

(নিজে যাচাই করুন: সঠিক lexer-এ "FINDER>=7" দেয় ID GE NUM; "WHERE=1" দেয় WHERE EQ NUM, কারণ keyword-এর পরে = ID-এর অংশ নয়; আর "x<=-3"-এ - একটি error, কারণ এই ভাষায় ঋণাত্মক সংখ্যার token নেই।)

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

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

প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন, তারপর “→ উত্তর” চাপুন।

প্র ০১Lexer আর parser আলাদা রাখা কি বাধ্যতামূলক? Scannerless parsing কী, আর কেউ কেন সেটি বেছে নেন?

বাধ্যতামূলক নয়। তত্ত্বের দিক থেকে regular language context-free language-এর একটি উপশ্রেণি (পর্ব ০৬-এর hierarchy), তাই প্রতিটি token-এর নিয়ম grammar-এর নিয়ম হিসেবেও লেখা যায়: ID → অক্ষর ID-বাকি, ID-বাকি → অক্ষর ID-বাকি ∣ অঙ্ক ID-বাকি ∣ ε. তখন grammar-এর terminal হয় একক অক্ষর, আর পুরো কাজ একটি parser করে। একে বলে scannerless parsing. Lex আর yacc-এর জোড়া (১৯৭০-এর দশকের Unix) যে দুই ধাপের ঐতিহ্য তৈরি করে, তার মূল যুক্তি ছিল দক্ষতা আর সরলতা: অক্ষর-স্তরের কাজ DFA-তে, যেখানে প্রতি অক্ষরে একটি টেবিল-দেখা; token-স্তরের কাজ LR বা LL parser-এ, যা অনেক কম সংখ্যক token দেখে।

তবু scannerless পদ্ধতির বাস্তব সুবিধা আছে। প্রথমত, ভাষার মিশ্রণ: একটি ফাইলের ভেতরে অন্য ভাষা (যেমন HTML-এর ভেতরে JavaScript, বা কোনো ভাষার ভেতরে SQL) থাকলে, কোথায় কোন token-নিয়ম খাটবে তা প্রসঙ্গের ওপর নির্ভর করে, আর একটি স্বাধীন lexer তা জানে না। দ্বিতীয়ত, অংশ ৬-এর >>-এর মতো সমস্যা নিজে থেকেই মেটে, কারণ parser নিজেই ঠিক করে দুটি > একসঙ্গে পড়বে কি না। Parsing Expression Grammar (PEG, Bryan Ford-এর ২০০৪ সালের প্রবন্ধ বলে উল্লেখ করা হয়) প্রায়ই scannerless ভাবে ব্যবহৃত হয়।

মূল্যটি হলো ambiguity আর খরচ। Scannerless grammar-এ “FINDER কি FIND + ER” প্রশ্নটি grammar-এর ambiguity হয়ে দাঁড়ায় (পর্ব ২৭), তাই maximal munch-এর মতো নিয়ম আলাদা করে grammar-এ বসাতে হয়, যেমন “একটি নামের পরে আর কোনো অক্ষর আসতে পারবে না”. প্রতিটি অক্ষর parser-এর ধাপ হওয়ায় কাজও বাড়ে। মজার কথা, Python ৩.৯ থেকে PEG-ভিত্তিক parser ব্যবহার করে, কিন্তু তবুও আলাদা tokenizer রাখে, যা অংশ ৮-এ চালানো হয়েছে।

মূল উপলব্ধি: Lexer আলাদা রাখা একটি প্রকৌশলী সিদ্ধান্ত, তত্ত্বের বাধ্যবাধকতা নয়। Regular অংশ DFA-কে দিলে গতি আর সরলতা আসে; প্রসঙ্গ-নির্ভর বা মিশ্র ভাষায় scannerless পদ্ধতি নমনীয়তা দেয়, ambiguity সামলানোর বাড়তি দায় নিয়ে।

প্র ০২Lexer-এর DFA-তে state কত হতে পারে? পর্ব ১০-এর 2n বিস্ফোরণ কি lexer generator-কেও বিপদে ফেলে?

তত্ত্বে ফেলতে পারে। নির্মাণ ৪.১ শেষ পর্যন্ত একটি subset construction, আর পর্ব ১০-এ প্রমাণিত হয়েছে, “শেষ থেকে n-তম চিহ্ন 1”-এর মতো language-এ যেকোনো DFA-তে অন্তত 2nটি state লাগে। কেউ যদি একটি token-এর pattern (a ∪ b)∗a(a ∪ b)20 লেখেন, lexer generator দশ লাখের বেশি state-এর টেবিল বানানোর চেষ্টা করবে। Priority-র কারণে আরও একটি সূক্ষ্মতা আছে: union-এর পর DFA minimization (পর্ব ১৯) করতে গেলে প্রথম partition শুধু accepting বনাম non-accepting নয়, বরং “কোন token” অনুযায়ী ভাগ করতে হয়, কারণ ID-এর state আর FIND-এর state একই language-এ গ্রহণ করলেও আলাদা ফল দেয়।

বাস্তবে প্রোগ্রামিং ভাষার token সরল: keyword-এর শিকল, নাম, সংখ্যা, string, কয়েকটি চিহ্ন। এদের DFA সাধারণত কয়েকশো state-এর মধ্যে থাকে। বড় অংশটা আসলে টেবিলের প্রস্থ: ASCII-তে প্রতিটি state-এ ১২৮ বা ২৫৬টি ঘর, আর Unicode-এ লক্ষাধিক। এ কারণেই flex-এর মতো tool টেবিল সংকোচন করে, যেমন অক্ষরগুলোকে “equivalence class”-এ ভাগ করা: যে অক্ষরগুলো প্রতিটি state-এ একই আচরণ করে (যেমন বাজারঘরের ভাষায় ছোট হাতের a থেকে z, আর F, I, N, D, W, H, E, R, A, O বাদে বাকি বড় হাতের অক্ষর), তারা টেবিলের একটি কলাম ভাগ করে। কিছু সংকোচন পদ্ধতি Aho, Sethi আর Ullman-এর compiler পাঠ্যবইয়ে (যাকে সাধারণত “Dragon Book” বলা হয়) বিস্তারিত আছে।

আরেকটি বিকল্প হলো পুরো DFA না বানানো: এই পর্বের Python lexer-এর মতো চলার পথে subset হিসাব, সঙ্গে cache. এটি lazy DFA, যা বিস্ফোরণ ঘটায় না, কারণ input-এ যে subset আসে শুধু সেগুলোই বানানো হয়, আর প্রতিটি পড়া অক্ষরে বড়জোর একটি নতুন subset তৈরি হয়। অনেক আধুনিক regex engine (পর্ব ২১) এই কৌশলের রূপ ব্যবহার করে।

মূল উপলব্ধি: Lexer generator-এর আকার-সমস্যা subset construction-এর নিম্নসীমা থেকেই আসে, কিন্তু বাস্তব token-সেটে তা বিরল; বড় খরচ সাধারণত alphabet-এর প্রস্থ, যা অক্ষর-শ্রেণি আর টেবিল সংকোচনে কমে।

প্র ০৩Maximal munch কেন প্রায় সব ভাষার নিয়ম হলো? এর বদলে “যে ভাঙনে parser খুশি থাকে” বেছে নিলে কী হতো?

Maximal munch-এর সবচেয়ে বড় গুণ উপপাদ্য ৩.২: এটি একটি ফাংশন। প্রতিটি input-এর ঠিক একটি token-ধারা, যা lexer parser-কে না জিজ্ঞেস করেই বের করতে পারে। মানুষের জন্যও নিয়মটি সহজ: “সবচেয়ে লম্বা যা হতে পারে, তাই।” C standard এই নিয়মটি স্পষ্ট লিখে দেয় আর উদাহরণ হিসেবে ঠিক x+++++y দেখায়, যা x ++ ++ + y হয়ে অবৈধ, যদিও আরেকটি ভাঙন বৈধ হতো। ভাষার নকশাকাররা জেনেশুনেই এই দাম মেনে নেন।

বিকল্পটি কল্পনা করুন: lexer সব সম্ভাব্য ভাঙন parser-কে দেয়, আর parser যেটিতে বৈধ গাছ পায় সেটি নেয়। প্রথম সমস্যা সংখ্যা: দৈর্ঘ্য n-এর একটি string-কে টুকরো করার উপায় 2n − 1টি পর্যন্ত হতে পারে (প্রতিটি ফাঁকে কাটা বা না কাটা), তাই এমন lexer-এর জন্য parser-কে একটি “token-এর graph” বা lattice নিতে হয়। এমন পদ্ধতি সত্যিই আছে, যেমন কিছু GLR-ভিত্তিক parser (পর্ব ৪১) বা প্রাকৃতিক ভাষার বাক্য-বিশ্লেষণে, যেখানে চীনা বা থাই লেখায় শব্দের মাঝে ফাঁকা থাকে না। দ্বিতীয় সমস্যা মানুষের বোঝা: একই লেখা দুই জায়গায় দুইভাবে tokenize হলে, ভুল কোথায় তা বোঝা অনেক কঠিন।

Maximal munch-এর সীমাও তত্ত্বে স্পষ্ট। অংশ ৩-এর {ab, a, bc} উদাহরণে এটি একটি বৈধ ভাঙন হারায়, আর সরল বাস্তবায়নে দ্বিঘাত সময় নিতে পারে (উপপাদ্য ৫.১); Reps-এর memoization-ভিত্তিক পদ্ধতি রৈখিক। বাস্তব ভাষাগুলোর token এমনভাবে বাছা হয় যাতে এক-দুই অক্ষরের সামনে-দেখাই যথেষ্ট, তাই সমস্যাটি সাধারণত দেখা দেয় না।

মূল উপলব্ধি: Maximal munch সম্পূর্ণতা (সব বৈধ ভাঙন খুঁজে পাওয়া) ছেড়ে দিয়ে নির্ধারণযোগ্যতা, সরলতা আর গতি কেনে। এটি একটি সচেতন লেনদেন, আর ভাষার token-নকশা সেই লেনদেনকে নিরাপদ রাখে।

প্র ০৪Python-এর indentation, C-এর typedef বা nested comment দেখায় বাস্তব lexer পুরোপুরি finite automaton নয়। তাহলে “lexer = DFA” কথাটি কতটা সত্য?

কথাটি একটি খুব ভালো প্রথম মডেল, কিন্তু পূর্ণ সত্য নয়। প্রতিটি একক token-এর গঠন প্রায় সবসময় regular, আর DFA সেই অংশটুকু নিখুঁতভাবে করে। কিন্তু lexer-এর চারপাশে কয়েকটি ছোট বাড়তি অবস্থা থাকে। Python-এর ভাষা-নির্দেশিকা নিজেই বলে, indentation-এর মাপগুলো একটি stack-এ রাখা হয়: নতুন লাইনের indentation বাড়লে একটি INDENT token আর stack-এ push, কমলে যতগুলো স্তর বন্ধ হলো ততগুলো DEDENT. Stack অসীম গভীর হতে পারে, তাই এটি আর finite automaton নয়; গঠনটি pushdown automaton-এর মতো (মডিউল ৬)।

C-এর ক্ষেত্রে সমস্যাটি অন্যরকম। A * b; লাইনটি A একটি typedef-নাম হলে একটি pointer ঘোষণা, নইলে একটি গুণ। কোনটি, তা জানতে আগের সব ঘোষণা মনে রাখতে হয়, যা একটি symbol table. অনেক C compiler-এ parser symbol table হালনাগাদ করে আর lexer তা পড়ে ID-কে TYPE_NAME বা IDENTIFIER বলে; এই কৌশলের প্রচলিত নাম “lexer hack”. এখানে lexer-এর আচরণ নির্ভর করছে parser-এর ওপর, অংশ ১-এর পরিষ্কার এক-দিকের পাইপলাইন আর নেই।

Nested comment-এ, যেমন /* বাইরে /* ভেতরে */ আবার বাইরে */, খোলা আর বন্ধের সংখ্যা মেলাতে হয়। এটি {anbn}-এর মতো, আর pumping lemma দিয়ে প্রমাণ করা যায় যে কোনো DFA এটি পারে না: DFA-র p-টি state-এর বেশি গভীরতার comment-এ দুই গভীরতা একই state-এ পড়বে, আর তখন যন্ত্রটি তাদের আলাদা করতে পারবে না। তাই lexer একটি পূর্ণসংখ্যা counter রাখে। তাত্ত্বিকভাবে counter-ও সীমাহীন মেমরি, যদিও খুব সীমিত ধরনের (one-counter automaton).

মূল উপলব্ধি: বাস্তব lexer = একটি DFA, তার চারপাশে একটি ছোট, সতর্কভাবে বেছে নেওয়া বাড়তি মেমরি (stack, counter বা symbol table). কোন অংশ regular আর কোন অংশ নয়, তা চেনাই ভালো lexer-নকশার প্রথম দক্ষতা।

প্র ০৫Unicode identifier চালু করলে কী লাভ আর কী ঝুঁকি? বাংলায় নাম লেখার সুযোগ দিলে lexer-এর নকশায় কী ভাবতে হয়?

লাভ স্পষ্ট: যাঁরা ইংরেজির চেয়ে নিজের ভাষায় স্বচ্ছন্দ, তাঁরা নিজের লিপিতে নাম লিখতে পারেন। Python ৩ (PEP 3131) থেকে non-ASCII identifier চলে, আর Java, JavaScript, C#-এর মতো অনেক ভাষাতেও Unicode-এর নামের নিয়ম আছে। এই নিয়মগুলোর ভিত্তি সাধারণত Unicode-এর একটি নির্দেশিকা, UAX #31: নাম শুরু হবে “ID_Start” শ্রেণির অক্ষরে, আর চলবে “ID_Continue” শ্রেণিতে, যেখানে বাংলা স্বরচিহ্ন আর হসন্তের মতো combining mark-ও আছে। অংশ ৮-এর আউটপুটে দেখেছেন, "মূল্য".isidentifier() True, কিন্তু \w+ সেটিকে টুকরো করে: lexer-এর নিয়ম যদি ভাষার সংজ্ঞা অনুসরণ না করে \w দিয়ে লেখা হয়, তাহলে ভাষা আর lexer দুটি আলাদা language বোঝে।

ঝুঁকির প্রথমটি দেখতে-এক অক্ষর (homoglyph): ল্যাটিন a আর সিরিলিক а দেখতে প্রায় এক, কিন্তু আলাদা code point, তাই দুটি আলাদা নাম। একজন পর্যালোচক কোড পড়ে মনে করবেন একই ভ্যারিয়েবল, অথচ lexer দুটি আলাদা ID দেবে। দ্বিতীয়টি normalization: একই বাংলা শব্দ কখনো দুই ভিন্ন code point-ক্রমে লেখা যায় (যেমন কিছু যুক্ত বা নুক্তা-যুক্ত রূপ)। Python এই কারণে identifier-কে NFKC রূপে normalize করে বলে PEP 3131-এ লেখা আছে, যাতে দুটি রূপ একই নাম হয়। তৃতীয়টি অদৃশ্য অক্ষর: ২০২১ সালে Nicholas Boucher আর Ross Anderson “Trojan Source” নামে দেখান, string বা comment-এর ভেতরে bidirectional control অক্ষর রেখে এমন কোড লেখা যায়, যা চোখে একরকম দেখায় কিন্তু compiler অন্যভাবে পড়ে। এর পর বেশ কিছু compiler আর editor সতর্কবার্তা যোগ করে।

বাজারঘরের মতো একটি ছোট query ভাষার নকশায় তাই কয়েকটি স্পষ্ট সিদ্ধান্ত লাগে: নামে বাংলা চলবে কি না (চললে Unicode-এর ID-নিয়ম মেনে); সংখ্যায় বাংলা অঙ্ক চলবে কি না (চললে int-এর আগে রূপান্তর স্পষ্ট করা); ZWJ বা ZWNJ-এর মতো অদৃশ্য অক্ষর নিষেধ কি না; আর তুলনার আগে normalization কোন রূপে।

মূল উপলব্ধি: Unicode alphabet বড় করে, কিন্তু তত্ত্ব একই থাকে; কঠিন অংশ হলো কোন অক্ষর কোন শ্রেণিতে, তা সচেতনভাবে ঠিক করা আর lexer-এর নিয়মকে ভাষার লেখা সংজ্ঞার সঙ্গে হুবহু মেলানো।

অনুশীলন

আগে কাগজে করুন, তারপর উত্তর মেলান। উত্তরগুলো উপরের Python ব্লকে নিয়ম বা input বদলে বসিয়েও যাচাই করতে পারেন।

  1. নকশা: বাজারঘরের ভাষায় দশমিক দাম আনতে তিনটি token, এই priority-তে: FLOAT = [0-9]+.[0-9]+, NUM = [0-9]+, DOT = “.” (একটি বিন্দু)। (ক) সংযুক্ত DFA আঁকুন, প্রতিটি accepting state-এ token লিখে। (খ) maximal munch-এ "3.14", "3." আর "3..5"-এর token-ধারা লিখুন।

    (ক) State: s (শুরু), A, B, C, E. s –অঙ্ক→ A, A –অঙ্ক→ A, A –.→ B, B –অঙ্ক→ C, C –অঙ্ক→ C, s –.→ E. Accepting: A (NUM), C (FLOAT), E (DOT). B non-accepting: “3.” পর্যন্ত FLOAT এখনো সম্পূর্ণ নয়, আর DOT শুধু শুরু থেকে আসে। বাকি সব তীর dead state-এ।

    (খ) "3.14": s → A → B → C → C, input শেষ, শেষ গ্রহণ C: FLOAT(3.14). "3.": A-তে NUM গৃহীত (দৈর্ঘ্য 1), B-তে কিছু নয়, input শেষ; শেষ গ্রহণে ফিরে NUM(3), তারপর “.” থেকে নতুন চালনায় DOT(.). "3..5": A, তারপর B, তারপর দ্বিতীয় “.” পড়ে dead; ফিরে NUM(3); তারপর DOT(.), DOT(.), NUM(5). Scratch-এ একটি সরল longest-match lexer-এ এই তিনটি ফলই এসেছে।

  2. প্রমাণের ভুল ধরুন: দাবি: “একটি lexical specification-এ input w-কে token-এ ভাঙার কোনো উপায় থাকলে maximal munch-ও w-কে error ছাড়া ভাঙবে।” যুক্তি: “ধরুন w = u1⋯um একটি বৈধ ভাঙন। Maximal munch প্রথম ধাপে অন্তত |u1| দৈর্ঘ্য নেয়, কারণ সে সবচেয়ে লম্বাটি নেয়। তাই প্রতিটি ধাপে সে বৈধ ভাঙনের চেয়ে এগিয়ে থাকে, আর শেষ পর্যন্ত পৌঁছায়। ∎” ভুল কোথায়? একটি পাল্টা-উদাহরণ দিন।

    ভুলটি “এগিয়ে থাকে, তাই শেষে পৌঁছায়” কথায়। প্রথম ধাপে maximal munch সত্যিই অন্তত |u1| নেয়, কিন্তু বেশি নিলে সে বৈধ ভাঙনের কোনো কাটার জায়গায় না-ও থামতে পারে। তখন বাকি অংশটি একটি নতুন string, যার কোনো বৈধ ভাঙন থাকার নিশ্চয়তা নেই; induction-এর hypothesis সেখানে খাটানো যায় না।

    পাল্টা-উদাহরণ: token {ab, a, bc}, input abc. বৈধ ভাঙন a · bc. Maximal munch প্রথমে ab নেয় (দৈর্ঘ্য 2 > 1), বাকি থাকে “c”, যা কোনো token-এর শুরু নয়: lexical error. Scratch-এর longest-match script-এ ঠিক এই ফল [ab, ERR:c] এসেছে। সঠিক দাবিটি দুর্বলতর: maximal munch error না দিলে তার ফল একটি বৈধ ভাঙন (উপপাদ্য ৩.২)।

  3. আউটপুট অনুমান: অংশ ৪-এর query_lexer.py-তে (চোদ্দ token, একই priority) lex("ORDER>=10 OR y<=-3") কী দেবে? প্রতিটি সংঘাতে কোন নিয়ম কাজ করল, বলুন।

    ফল: ID(ORDER) GE(>=) NUM(10) OR(OR) ID(y) LE(<=) ERROR(-) NUM(3). “ORDER”-এর শুরুতে keyword OR দৈর্ঘ্য 2-এ সম্পূর্ণ হয়, কিন্তু ID বেঁচে থেকে দৈর্ঘ্য 5-এ পৌঁছায়: maximal munch-এ লম্বাটি, priority লাগেই না। মাঝের “OR”-এ OR আর ID দুটিই দৈর্ঘ্য 2: priority-তে keyword. >= আর <=-তে লম্বা token. - কোনো token-এর শুরু নয়: ERROR, তারপর 3 একটি NUM. Scratch-এ এই lexer চালিয়ে ঠিক এই ধারা এসেছে।

  4. গণনা ও প্রমাণ: Token A = a আর AB = a∗b-এর scanner দৈর্ঘ্য n = 5-এর input a5 আর a5b-এ মোট কতটি অক্ষর পড়ে? সাধারণ n-এর জন্য সূত্র প্রমাণ করুন, আর একটি উপায় বলুন যাতে an-এ মোট পড়া রৈখিক হয়।
    1. a5: অবস্থান 0 থেকে ৫টি, 1 থেকে ৪টি, …, 4 থেকে ১টি অক্ষর পড়া; মোট 15 = 5 · 6 / 2. — প্রতিটি চালনা input শেষ পর্যন্ত
    2. a5b: প্রথম চালনাতেই ৬টি অক্ষর পড়ে AB সম্পূর্ণ, input শেষ; মোট 6 = n + 1. — একটি token
    3. সাধারণ সূত্র: an-এ অবস্থান p থেকে DFA একটি a পড়ে A-তে গ্রহণ করে, তারপর state 2-এ যত a আসুক বেঁচে থাকে (b এলে AB হতে পারে), তাই বাকি n − p অক্ষর সবই পড়ে। শেষ গ্রহণ দৈর্ঘ্য 1, পরের চালনা p + 1-এ। মোট Σp=0n−1(n − p) = n(n + 1)/2. ∎ — উপপাদ্য ৫.১
    4. রৈখিক করার উপায়: একবার অবস্থান p + 1 থেকে state 2-এ চলে input-এর শেষে b ছাড়া ব্যর্থ হলে, মনে রাখুন “(state 2, অবস্থান j) থেকে কোনো গ্রহণ নেই”; পরের চালনা সেই জোড়ায় পৌঁছালে সঙ্গে সঙ্গে থামে। এটি Reps-এর memoization-এর ধারণা; প্রতিটি (state, অবস্থান) জোড়া বড়জোর একবার “ব্যর্থ” প্রমাণিত হয়, তাই মোট কাজ |Q| · n-এর অনুপাতে। — memoization

    অংশ ৬-এর ব্লকে n = 10, 20, 40, 80-এ 55, 210, 820, 3240 এসেছে, সূত্রের সঙ্গে হুবহু; scratch-এ n = 5-এও 15 আর 6.

নিজেকে যাচাই করুন

ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।

ক্রমকয়েকটি token-এর regex থেকে একটি DFA-ভিত্তিক lexer বানিয়ে চালানোর ধাপগুলো সঠিক ক্রমে সাজান (▲▼ চেপে সরান)

  1. প্রতিটি token-এর regex priority-র ক্রমে লেখা, যাতে কোনোটি ফাঁকা string না মেলায়
  2. প্রতিটি regex থেকে Thompson construction-এ একটি ε-NFA বানানো
  3. নতুন শুরু state থেকে ε-তীরে সব NFA-কে একটিতে জোড়া
  4. Subset construction চালিয়ে প্রতিটি DFA state-এ সবচেয়ে উঁচু priority-র accepting token বসানো
  5. Input-এ DFA চালিয়ে শেষ গ্রহণ মনে রাখা, dead state-এ থেমে token বের করা আর পরের অবস্থান থেকে আবার শুরু

Token GT = “>”, GE = “>=”, EQ = “=” আর maximal munch ধরে input “>==”-এর token-ধারা কী?

  • GT EQ EQ
  • GE EQ
  • GT EQ GE
  • Lexical error

একটি lexer-এ নিয়ম এই ক্রমে: keyword IF = “if”, তারপর ID = [a-z]+. Maximal munch আর rule priority মেনে “if” আর “iffy” কোন token হবে?

  • দুটিই IF
  • দুটিই ID
  • “if” হবে IF, “iffy” হবে ID
  • “if” হবে IF, “iffy” হবে IF আর তারপর ID(fy)

Python-এ re.findall(r">|>=", ">=") কী দেয়, আর কেন?

  • ['>'], কারণ প্রথম বিকল্পটি মিললেই নেওয়া হয়
  • ['>='], কারণ re সবসময় সবচেয়ে লম্বা মেলা নেয়
  • ['>', '=']
  • একটি error, কারণ pattern অবৈধ

নিচের কোন token-শ্রেণি কোনো DFA দিয়েই চেনা সম্ভব নয়, ফলে একটি বিশুদ্ধ finite-automaton lexer-এ করা যায় না?

  • অক্ষর দিয়ে শুরু হওয়া নাম
  • লাইনের শেষ পর্যন্ত চলা comment
  • উদ্ধৃতিচিহ্নের ভেতরে এক লাইনের string
  • যে কোনো গভীরতায় নেস্টেড block comment

C-ধরনের token ++, + আর নাম, আর maximal munch ধরে x+++++y-এর token-ধারা কী?

  • x ++ + ++ y
  • x ++ ++ + y
  • x + + + + + y
  • x +++++ y

Token A = a আর AB = a∗b-এর DFA-ভিত্তিক maximal munch scanner (শেষ গ্রহণে ফিরে আসে, কোনো memoization নেই) input an-এ মোট কতটি অক্ষর পড়ে?

  • ঠিক n
  • ঠিক n + 1
  • ঠিক n(n + 1)/2
  • প্রায় 2n

শব্দকোষ

লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন, অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:

মনে রাখুন

  1. Lexer অক্ষরের ধারাকে (token, lexeme)-এর ধারায় ভাঙে; token-এর pattern regex, তাই প্রতিটি token-শ্রেণি regular, আর কোনো pattern ফাঁকা string মেলাবে না।
  2. Maximal munch: সবচেয়ে লম্বা lexeme, সমান দৈর্ঘ্যে তালিকার আগের নিয়ম। ফল অনন্য, কিন্তু বৈধ ভাঙন থাকলেও error হতে পারে ({ab, a, bc}-এ abc).
  3. Lexer-এর DFA: প্রতিটি regex-এর NFA, নতুন শুরু থেকে ε-তীরে union, subset construction, আর প্রতিটি state-এ সবচেয়ে উঁচু priority-র accepting token.
  4. Scanner শেষ গ্রহণ মনে রেখে dead state পর্যন্ত পড়ে, তারপর ফিরে আসে; সবচেয়ে খারাপ ক্ষেত্রে n(n + 1)/2 পড়া, সীমিত সামনে-দেখায় রৈখিক।
  5. এক-regex lexer (PLY, Lark, re) প্রথম বিকল্প নেয়, তাই লম্বা বিকল্প আগে; আর \w, \d বাংলা লেখায় ভিন্ন আচরণ করে, তাই Unicode-এর নিয়ম সচেতনভাবে বেছে নিতে হয়।

পরের পর্বে: একটি নির্দিষ্ট pattern বা অনেকগুলো keyword একটি বড় লেখায় খোঁজা। Pattern থেকে সরাসরি একটি string matching automaton, KMP-এর failure function আর অনেক pattern একসঙ্গে খোঁজার Aho–Corasick automaton, বাজারঘরের review-এ বাংলা শব্দ খোঁজার উদাহরণসহ।

আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ

এই পর্বটি শেয়ার করুন:
এই পর্বে ভুল পেয়েছেন? জানান