এই পর্বে যা শিখবেন
- একটি পুরো ভাষার lexer হাতে লেখা: cursor, lookahead, শাখা বেছে নেওয়া আর token তৈরি, reference-এর
lexer.py-এর হুবহু নামে - প্রতিটি token আর error-এর সঠিক
line:colরাখা, বাংলা লেখা থাকলেও - Maximal munch, keyword টেবিল, integer আর string literal-এর নিয়ম, আর প্রতিটির error বার্তা ঠিক কোথায় দেখায়
- দ্বিতীয় একটি lexer আর এলোমেলো input দিয়ে differential test, আর একটি lexer কেন O(n)
- Editor-এর syntax highlighting, বাস্তব compiler-এর lexer, আর AI-এর লেখা lexer যাচাইয়ের উপায়
১ · Lexer কী বানায় — অক্ষরের সারি থেকে token-এর সারি
মুদি দোকানের কর্মচারী আপনার বাজারের ফর্দ হাতে নিলেন: “চাল ২ কেজি, ডাল ১ কেজি”. তিনি প্রথমে অর্থ ভাবেন না। আগে চোখ দিয়ে লেখাটিকে টুকরো করেন: একটি পণ্যের নাম, একটি সংখ্যা, একটি একক, একটি কমা। কোন টুকরো কোথায় শুরু, কোথায় শেষ, সেটি ঠিক হলে তবেই হিসাব। হাতের লেখা না বুঝলে তিনি আঙুল রেখে বলেন, “এই জায়গাটা পড়া যাচ্ছে না।” Compiler-এর প্রথম ধাপ ঠিক এই কর্মচারী।
Lexer source-এর অক্ষরের সারি পড়ে token-এর সারি বানায়। প্রতিটি token-এর আছে একটি শ্রেণি (kind) আর source-এর হুবহু টুকরোটি, যাকে বলে lexeme. ফাঁকা ঘর আর comment বাদ পড়ে, কিন্তু প্রতিটি token-এর ঠিকানা থেকে যায়, যাতে পরের ধাপগুলো error দেখাতে পারে। পর্ব ০১-এ একটি regex দিয়ে বানানো ছোট lexer দেখেছেন, আর পর্ব ০৫-এ পুরো pipeline-এ এর জায়গা। তত্ত্বের দিকটি, অর্থাৎ token-এর pattern কেন regular language আর কীভাবে regex থেকে DFA হয়, গণনার তত্ত্ব কোর্সের পর্ব ২২ (lexical analysis)-এ বিস্তারিত আছে। এই পর্বে সেই তত্ত্ব আর নতুন করে নয়; এখানে আমরা Haat-এর আসল lexer বানাব, যা reference বাস্তবায়নের lexer.py (৮৬ লাইন) আর tokens.py-এর সঙ্গে হুবহু মেলে। মডিউল ৮-এর পুরো পরিকল্পনা (কোন পর্বে কোন ফাইল) আছে পর্ব ৪৫-এ (Compiler-এর front end — Haat ভাষার পরিচয় আর নকশা)।
Reference-এ একটি token দেখতে এমন: Token(kind, text, line, col), একটি frozen dataclass. kind বড় হাতের নাম, যেমন IDENT বা GT_EQ; text source-এর হুবহু লেখা; line আর col দুটিই ১ থেকে গোনা। এই চারটি ঘরই parser (পর্ব ৪৭) পাবে। Haat-এর মোট ৩৭ রকম kind:
| দল | kind | কতটি |
|---|---|---|
| নাম আর literal | IDENT INT STRING | ৩ |
| Keyword (শব্দটিই বড় হাতে) | LET VAR FN IF ELSE WHILE RETURN TRUE FALSE PRINT | ১০ |
| দুই অক্ষরের operator | EQ_EQ ==, BANG_EQ !=, LT_EQ <=, GT_EQ >=, AND_AND &&, OR_OR ||, ARROW -> | ৭ |
| এক অক্ষরের operator আর যতিচিহ্ন | PLUS MINUS STAR SLASH PERCENT LT GT BANG EQ LPAREN RPAREN LBRACE RBRACE COMMA SEMI COLON | ১৬ |
| শেষের চিহ্ন | EOF (লেখা ফাঁকা) | ১ |
পুরো lexer-এর কাজ একটি ছবিতে। একটি cursor বাঁ থেকে ডানে চলে; প্রতিবার বর্তমান অক্ষরটি দেখে ওপর থেকে নিচে শাখাগুলো পরীক্ষা করে, প্রথম যেটি মেলে সেটি খাটে।
ছবি ৪৬.১ — হাতে লেখা lexer-এর কাঠামো
ওপরে source আর cursor; মাঝে ৯টি শাখা, ওপর থেকে নিচের ক্রমে; নিচে token-এর তালিকা, যা parser-এর কাছে যায়
// শাখা ৮-এর /-এর আগে, আর ৭ নম্বর ৮ নম্বরের আগে।২ · Cursor, peek আর advance — line:col গোনা
হাতে লেখা lexer-এর ভেতরে তিনটি মৌলিক কাজ। Peek: cursor না সরিয়ে বর্তমান অক্ষর (src[i]) বা পরের দুটি (src[i:i + 2]) দেখা; একে বলে lookahead. Advance: cursor এক বা একাধিক ঘর সামনে নেওয়া (i += 1). Emit: start থেকে i পর্যন্ত টুকরোটিকে একটি token বানানো। অনেক বইয়ে এগুলো আলাদা method হিসেবে লেখা হয় (peek(), advance(), match()); reference সরাসরি index দিয়ে লেখে, কারণ Python-এ src[i] আর slicing এমনিতেই সংক্ষিপ্ত। দুটি নকশার অর্থ এক।
অবস্থান রাখাটাই আসল সূক্ষ্ম কাজ। Haat-এর source position হলো ১ থেকে গোনা line:col, আর reference README-এর নকশা-সিদ্ধান্ত ১ বলে: কলাম গোনা হয় Unicode code point ধরে, তাই একটি বাংলা অক্ষর এক কলাম; একটি tab-ও এক কলাম; \r ফাঁকা ঘর হিসেবে উপেক্ষা হয়। Python-এর str code point-এর সারি (পর্ব ২১), তাই src[i] একটি পুরো code point, আর i - start সরাসরি কলামের হিসাব দেয়। C বা Rust-এ source সাধারণত UTF-8 byte-এর সারি; সেখানে একই নিয়ম মানতে হলে প্রতিটি অক্ষরের প্রথম byte আলাদা করে গুনতে হয়।
Reference-এর একটি ছোট কৌশল লক্ষ করুন। Token তৈরির পর সে লেখে col += i - start, প্রতিটি অক্ষরে আলাদা করে কলাম বাড়ায় না। এটি ঠিক থাকে একটিমাত্র শর্তে: কোনো token লাইন পার হয় না। Haat-এ শর্তটি সত্য, কারণ string-এর ভেতরে কাঁচা newline নিষেধ (নকশা-সিদ্ধান্ত ৫) আর comment newline-এর আগেই থামে। নতুন লাইনের অক্ষর একমাত্র শাখা ১-এ আসে, যেখানে line বাড়ে আর col আবার ১ হয়। বহু-লাইনের string বা block comment যোগ করলে (অনুশীলন ১) এই হিসাব বদলাতে হবে।
এবার দেখুন lexer আসলে কীভাবে if p >= 1000 { পড়ে। প্রতিটি ধাপ মূল loop-এর একটি ঘোরা। বাঁয়ে শাখাগুলো (ছবি ৪৬.১-এর ক্রমে), যে শাখা খাটছে সেটি উজ্জ্বল; ডানে cursor, অক্ষর, কলাম আর নতুন token.
1if c == "\n": line + 1, col = 12if c in " \t\r": col + 13if "//": লাইনের শেষ পর্যন্ত4if is_ident_start(c): শব্দ5elif is_digit(c): INT6elif c == '"': STRING7elif src[i:i+2] in TWO_CHAR8elif c in ONE_CHAR9else: error10শেষে: EOF
| i | |
| c | |
| col |
- শব্দ।
i= 0, অক্ষরi, যা শাখা ৪-এ পড়ে। Lexer শব্দের শেষ পর্যন্ত পড়ে (if, তারপর space), cursor যায় 2-এ। “if” KEYWORDS টেবিলে আছে, তাই tokenIF, অবস্থান 1:1. কলাম বাড়ে শব্দের দৈর্ঘ্য ২ দিয়ে: 1 → 3. - Space. শাখা ২: কোনো token নয়, শুধু
col3 → 4 আরiএক ঘর সামনে। - এক অক্ষরের নাম।
pটেবিলে নেই, তাইIDENT, অবস্থান 1:4. কলাম 4 → 5. - আবার space. কলাম 5 → 6; cursor এখন
>-এর ওপর। - Maximal munch.
>শাখা ৪, ৫, ৬-এ পড়ে না। শাখা ৭ সামনের দুই অক্ষর দেখে:>=, যা TWO_CHAR-এ আছে। তাই একটি tokenGT_EQ, অবস্থান 1:6; cursor ২ ঘর এগোয় (5 → 7), কলাম 6 → 8. শাখা ৮ পর্যন্ত যাওয়াই হলো না। - Space. কলাম 8 → 9.
- সংখ্যা।
1অঙ্ক, শাখা ৫। Lexer যত অঙ্ক আছে সব পড়ে (1000, cursor 8 → 12), তারপর মান পরীক্ষা করে: 1000 ≤ 9223372036854775807, ঠিক আছে। TokenINT, অবস্থান 1:9, কলাম 9 → 13. - Space. কলাম 13 → 14.
- এক অক্ষরের চিহ্ন।
{-এর পরে আর কিছু নেই, তাইsrc[13:15]শুধু"{", যা TWO_CHAR-এ নেই। শাখা ৮:LBRACE, অবস্থান 1:14; কলাম 14 → 15. - EOF.
i= 14 = লেখার দৈর্ঘ্য, loop শেষ। Lexer শেষে একটি EOF token যোগ করে, অবস্থান তখনকারline:col, অর্থাৎ 1:15. মোট ৬টি token; reference-এরpython -B haat.py tokens-ও হুবহু এই ছয়টি লাইন দেয় (সত্যিকারের run).
৩ · Maximal munch — লম্বা operator আগে
ধাপ ৫-এ যা দেখলেন, তার নাম maximal munch (longest match): বর্তমান অবস্থান থেকে যত লম্বা টুকরো কোনো token হতে পারে, সবচেয়ে লম্বাটি নেওয়া। নিয়মটির তত্ত্ব (কেন DFA-তে “শেষ গ্রহণ-অবস্থা মনে রাখা” লাগে) ToC পর্ব ২২-এর অংশ ৩ আর ৫-এ। হাতে লেখা lexer-এ এর বাস্তবায়ন খুব সরল, কারণ Haat-এর সবচেয়ে লম্বা operator দুই অক্ষরের: আগে দুই অক্ষরের টেবিল (TWO_CHAR), না মিললে এক অক্ষরের (ONE_CHAR). দুই অক্ষরের lookahead-ই যথেষ্ট।
একটি সূক্ষ্মতা: এই পদ্ধতি ঠিক থাকে, কারণ প্রতিটি দুই অক্ষরের operator ভেঙে গেলে তার প্রথম অক্ষর নিজেই একটি বৈধ token, শুধু && আর || ছাড়া। Haat-এ একা & বা | কোনো token নয়; তাই if a & b { দিলে reference বলে 1:6: error: unexpected character '&' (সত্যিকারের run; নকশা-সিদ্ধান্ত ২-এ এটি লেখা আছে)। নিচের stepper-এ a<=-b, যেখানে তিনটি চিহ্ন পাশাপাশি:
1is_ident_start(c)? → শব্দ2is_digit(c)? → INT3c == '"'? → STRING4src[i:i+2] in TWO_CHAR?5c in ONE_CHAR?6নইলে error
| বাকি | |
| দুই অক্ষর |
- নাম।
aশাখা ৪-এ পড়ে; শব্দ এখানেই শেষ, কারণ<নামের অক্ষর নয়।IDENT a, 1:1. - লম্বাটি আগে।
<নাম, অঙ্ক বা কোট নয়। Lexer সামনের দুই অক্ষর দেখে:<=, যা TWO_CHAR-এ আছে। একটি tokenLT_EQ, 1:2; cursor দুই ঘর এগোয়। - তিন অক্ষরের কিছু নেই। এখন
-b.<=-মিলে কোনো token নেই, আর lexer তা খোঁজেও না; প্রতিটি token আলাদা করে শুরু হয়।-bTWO_CHAR-এ নেই, তাই এক অক্ষরেরMINUS, 1:4. (->হলেARROWহতো।) - নাম।
IDENT b, 1:5. - শেষ।
EOF, 1:6. চারটি আসল token:a,<=,-,b, অর্থাৎ parser পরে বুঝবেa <= (-b). Reference-এরtokens-ও হুবহু এই পাঁচটি লাইন দেয়। - ক্রম উল্টালে কী হতো। কেউ যদি ONE_CHAR আগে পরীক্ষা করে,
<একাLTহয়ে যায়, তারপর=হয়EQ. Lexer কোনো error দেয় না! ভুলটি ধরা পড়ে parser-এ: লেখকের lab-এ এমন একটি ভাঙা lexer-এর token reference parser-কে দিলেa<=-b;-এর জন্য বার্তা আসে1:3: error: expected expression, যা আসল কারণ থেকে অনেক দূরের কথা। (অনুশীলন ২-এ এই bug খুঁজবেন।)
Maximal munch সবসময় মানুষের মনের সঙ্গে মেলে না। Haat-এ -- নামে কোনো operator নেই, তাই x = a--b; হয় a, -, -, b, অর্থাৎ a - (-b); reference-এর run-এ দুটি MINUS, কলাম ৬ আর ৭-এ। C-তে -- একটি token, তাই একই লেখা সেখানে অন্য অর্থ বা error. C standard নিজেই একটি উদাহরণ দেয়: x+++++y ভাঙে x ++ ++ + y হিসেবে, যা increment-এর নিয়ম ভাঙে, যদিও x ++ + ++ y বৈধ হতো। Lexer অর্থ বোঝে না; সে শুধু লম্বা টুকরো খোঁজে।
তুলনার জন্য Python-এর নিজের lexer. নিচের output লেখকের যন্ত্রে CPython 3.14.4-এর tokenize module-এর সত্যিকারের run (কলাম ০ থেকে গোনা, Haat-এর মতো ১ থেকে নয়):
$ python pytok.py # tokenize.generate_tokens, শুধু token-গুলো
'a<=-b'
NAME 'a' (1, 0)
LESSEQUAL '<=' (1, 1)
MINUS '-' (1, 3)
NAME 'b' (1, 4)
'x = a--b'
NAME 'x' (1, 0)
EQUAL '=' (1, 2)
NAME 'a' (1, 4)
MINUS '-' (1, 5)
MINUS '-' (1, 6)
NAME 'b' (1, 7)
একই সিদ্ধান্ত: <= একটি token, আর Python-এও -- নেই, তাই দুটি MINUS. ভাষা আলাদা, নিয়ম একই; পার্থক্য শুধু কোন টুকরো টেবিলে আছে।
৪ · Keyword না নাম — আগে পুরো শব্দ, তারপর টেবিল
অক্ষর বা _ দিয়ে শুরু হলে lexer প্রথমে পুরো শব্দটি পড়ে ([A-Za-z_][A-Za-z0-9_]*), তারপর একটিমাত্র dictionary lookup করে: শব্দটি KEYWORDS-এ থাকলে kind হলো শব্দটির বড় হাতের রূপ (while → WHILE), নইলে IDENT. কেন আগে keyword মিলিয়ে দেখা হয় না? কারণ তাহলে iffy হতো IF + fy, আর printer হতো PRINT + er. শব্দের ক্ষেত্রেও এটি maximal munch: আগে সবচেয়ে লম্বা নাম, তারপর সিদ্ধান্ত। একটি keyword আর একটি identifier lexer-এর চোখে একই আকৃতির; পার্থক্য শুধু টেবিলে।
সিদ্ধান্ত ৬: Int Bool Str Unit keyword নয়; lexer এদের IDENT দেয়, আর parser শুধু type-এর জায়গায় এদের type হিসেবে পড়ে। ফলে Haat-এ ১০টি keyword, যা অবশ্যই reserved word: let নামে কোনো variable হয় না। কিন্তু নতুন type নাম যোগ করতে lexer বদলাতে হয় না। সিদ্ধান্ত ৪: নাম আর অঙ্ক শুধু ASCII; বাংলা লেখা চলে কেবল comment আর string-এর ভেতরে। let দাম = 5; দিলে reference বলে 1:5: error: unexpected character 'দ' (সত্যিকারের run).
সিদ্ধান্ত ৪-এর একটি লুকানো ফাঁদ আছে, যা কোড লেখার সময় ধরা পড়ে। Python-এর str.isdigit() বাংলা অঙ্কেও True দেয়, আর int("৫২০") দেয় 520 (লেখকের যন্ত্রে CPython 3.14.4-এর সত্যিকারের run). কেউ যদি c.isdigit() দিয়ে অঙ্ক চেনেন, Haat চুপচাপ বাংলা অঙ্ক মেনে নেবে, অথচ নিয়ম বলে নেবে না। তাই reference নিজের is_digit লেখে: "0" <= c <= "9". একই কারণে নামের জন্য str.isalpha() নয়, স্পষ্ট পরিসর। ভাষার নিয়ম বাস্তবায়নের ভাষার সুবিধার ওপর ছেড়ে দিলে নিয়ম বদলে যায়।
বড় ভাষাগুলো নতুন keyword আনতে ভয় পায়, কারণ পুরোনো কোডে সেই শব্দ নাম হিসেবে থাকতে পারে। সমাধান contextual keyword: Python 3.10-এর match আর case শুধু নির্দিষ্ট জায়গায় keyword, অন্যত্র সাধারণ নাম। এমন শব্দ lexer আলাদা করতে পারে না (সে প্রসঙ্গ জানে না); তাই সেগুলো IDENT হিসেবেই যায়, আর parser ঠিক করে। Haat-এর Int একই কৌশলের ছোট রূপ (ভাবনার প্রশ্ন ৫)।
এবার পুরো টেবিলগুলো চালিয়ে দেখুন। নিচের block reference-এর tokens.py (token-এর ধরন আর টেবিল) আর lexer.py-এর ওপরের অংশ ও scan_string, একই নাম আর একই বার্তায়। Block-টি আপনার ব্রাউজারেই আসল CPython-এ চলে (Pyodide). এটি data-shared: পরের দুটি Python block এর সংজ্ঞাগুলো ব্যবহার করবে, তাই আগে এটি চালান।
# tokens.py আর lexer.py-র টেবিল আর string-অংশ, reference-এর হুবহু নামে
from dataclasses import dataclass
@dataclass(frozen=True)
class Token:
kind: str; text: str; line: int; col: int # col = code point ধরে, ১ থেকে
KEYWORDS = {w: w.upper() for w in
"let var fn if else while return true false print".split()}
TWO_CHAR = {"==": "EQ_EQ", "!=": "BANG_EQ", "<=": "LT_EQ", ">=": "GT_EQ",
"&&": "AND_AND", "||": "OR_OR", "->": "ARROW"}
ONE_CHAR = {"+": "PLUS", "-": "MINUS", "*": "STAR", "/": "SLASH",
"%": "PERCENT", "<": "LT", ">": "GT", "!": "BANG", "=": "EQ",
"(": "LPAREN", ")": "RPAREN", "{": "LBRACE", "}": "RBRACE",
",": "COMMA", ";": "SEMI", ":": "COLON"}
INT_MAX, ESCAPES = 2**63 - 1, {'"': '"', "\\": "\\", "n": "\n"}
def is_ident_start(c): return c == "_" or "a" <= c <= "z" or "A" <= c <= "Z"
def is_digit(c): return "0" <= c <= "9" # শুধু ASCII; ৫ সংখ্যা নয়
class HaatError(Exception): # errors.py: line:col: error: …
def __init__(s, line, col, msg): super().__init__(f"{line}:{col}: error: {msg}")
def scan_string(src, i, line, col): # শেষ কোটের ঠিক পরের index
j = i + 1
while j < len(src) and src[j] not in '"\n':
if src[j] == "\\":
if j + 1 >= len(src) or src[j + 1] not in ESCAPES:
bad = src[j:j + 2].rstrip("\n")
raise HaatError(line, col + (j - i), f"unknown escape sequence '{bad}'")
j += 1 # escape-এর দুই অক্ষর একসাথে পার
j += 1
if j >= len(src) or src[j] != '"': raise HaatError(line, col, "unterminated string literal")
return j + 1
print(3 + len(KEYWORDS) + len(TWO_CHAR) + len(ONE_CHAR) + 1, "kinds;", "Int ->", KEYWORDS.get("Int", "IDENT"))
for s in ['"দাম ৫২০" + x', r'"say \"hi\""', r'"tab\t"', '"open\nx']:
try: print(repr(s), "->", s[:scan_string(s, 0, 1, 1)])
except HaatError as e: print(repr(s), "->", e)আসল আউটপুট (ব্রাউজারের Python):
37 kinds; Int -> IDENT
'"দাম ৫২০" + x' -> "দাম ৫২০"
'"say \\"hi\\""' -> "say \"hi\""
'"tab\\t"' -> 1:5: error: unknown escape sequence '\t'
'"open\nx' -> 1:1: error: unterminated string literal
প্রথম লাইন: ৩ (IDENT, INT, STRING) + ১০ keyword + ৭ দুই অক্ষরের + ১৬ এক অক্ষরের + EOF = ৩৭, README-এর টেবিলের সঙ্গে মেলে; আর Int টেবিলে নেই, তাই IDENT. বাকি চার লাইন scan_string-কে সরাসরি ডাকে (বাঁয়ে Python-এর repr, তাই \ দুবার দেখায়)। বাংলা string-টি শেষ কোট পর্যন্ত কাটা হয়েছে, + x বাদ। দ্বিতীয়টিতে \" string শেষ করেনি, কারণ escape-এর দুই অক্ষর একসাথে পার হয়। তৃতীয়টি \t, যা Haat v1-এ নেই: error কলাম ৫-এ, অর্থাৎ backslash-এর ঘরে। চতুর্থটিতে কোট বন্ধ হওয়ার আগেই newline, তাই error কলাম ১-এ, খোলা কোটের ঘরে। কেন দুটি error দুই রকম জায়গায় দেখায়, পরের অংশে।
৫ · Literal: পূর্ণসংখ্যা আর string
Integer literal
Haat-এর integer literal হলো [0-9]+: চিহ্ন ছাড়া, শুধু দশমিক। -5 দুটি token, MINUS আর INT 5; মাইনাস একটি unary operator. শুরুতে শূন্য চলে: let n = 007;-এ token-এর লেখা 007 থাকে, মান পরে ৭ হয় (reference-এর run). C-তে 007 octal হতো; Haat-এ সেই ধাঁধা নেই। Lexer একটি সীমাও পরীক্ষা করে (নকশা-সিদ্ধান্ত ৩): মান 9223372036854775807-এর বেশি হলে integer literal too large, অবস্থান literal-এর শুরু। Haat-এর Int 64-bit (পর্ব ২০), তাই সবচেয়ে ছোট মান −9223372036854775808 একটি literal হিসেবে লেখা যায় না: ধনাত্মক অংশটিই সীমার বাইরে। লিখতে হয় -9223372036854775807 - 1. C-তে একই কারণে <limits.h>-এর LLONG_MIN সাধারণত (-LLONG_MAX - 1) হিসেবে সংজ্ঞায়িত থাকে। Java অন্য পথ নিয়েছে: সেখানে 9223372036854775808L literal শুধু unary minus-এর ঠিক পরে বৈধ (Java Language Specification §3.10.1), অর্থাৎ lexer-parser একটি বিশেষ ব্যতিক্রম রাখে।
পরীক্ষা করতে গিয়ে পাওয়া একটি আসল bug. সীমা পরীক্ষাটি লেখা int(src[start:i]) > INT_MAX. CPython 3.11 থেকে (আর কিছু পুরোনো version-এর নিরাপত্তা-আপডেটে) int() ৪,৩০০ অঙ্কের বেশি দশমিক লেখা রূপান্তর করতে চায় না; এটি ইচ্ছাকৃত নিরাপত্তা-সীমা। তাই ৫,০০০ অঙ্কের একটি literal দিলে reference-এর বার্তা integer literal too large নয়, একটি Python crash (লেখকের lab-এ সত্যিকারের run, শেষ তিন লাইন):
if int(src[start:i]) > INT_MAX:
~~~^^^^^^^^^^^^^^
ValueError: Exceeds the limit (4300 digits) for integer string conversion: value has 5000 digits; use sys.set_int_max_str_digits() to increase the limit
সমাধান এক লাইনের: আগে দৈর্ঘ্য দেখা। digits = src[start:i].lstrip("0"), তারপর if len(digits) > 19 or int(digits or "0") > INT_MAX. লেখকের lab-এ এই রূপ ৫,০০০ অঙ্কে ঠিক বার্তা দেয়, আর ৫,০০০টি শূন্যের পরে 7 লিখলে মান ৭-এর একটি INT দেয়। Reference read-only, তাই এই পর্বের কোড reference-এর মতোই রাখা হলো (হুবহু মেলানোর জন্য), আর bug-টি reference-এর রক্ষণাবেক্ষণকারীদের জানানো হয়েছে। শিক্ষা: অংশ ৭-এর এলোমেলো পরীক্ষা (৩,০০০ আর ২০,০০০ input) এটি ধরেনি, কারণ টুকরোগুলো ছোট ছিল; চরম মান (খুব লম্বা, খুব বড়, ফাঁকা) আলাদা করে ভাবতে হয়।
String literal
Haat-এর string literal ডাবল কোটে, আর escape sequence মাত্র তিনটি: \", \\, \n (নকশা-সিদ্ধান্ত ৫)। Lexer string-এর মান বানায় না: token-এর text-এ কোট আর escape হুবহু থাকে ("ঘর\n"), আর parser পরে lexer.unescape দিয়ে আসল লেখা বানায়। এতে token-এর লেখা সবসময় source-এর হুবহু টুকরো, যা fmt আর error দেখানোয় কাজে লাগে। String-এর ভেতরে কাঁচা newline নিষেধ, কিন্তু কাঁচা tab চলে: লেখকের run-এ print("a⇥b"); (মাঝে একটি আসল tab) পাঁচটি token দেয়, কোনো error নয়।
দুই রকম string-error দুই জায়গায় দেখায়, আর কারণটি নকশার। unknown escape sequence দেখায় backslash-এর কলামে (col + (j - i)), কারণ ভুলটি ঠিক সেখানে। unterminated string literal দেখায় খোলা কোটের কলামে, কারণ “শেষ কোথায় হওয়ার কথা ছিল” lexer জানে না; জানে শুধু কোথায় শুরু হয়েছিল, আর মানুষকে সেখানেই ঠিক করতে হবে। নিচের stepper-এ একটি অর্ডারের দাম ছাপার লাইন, শেষ কোটটি ভুলে বাদ পড়েছে:
1j = i + 12while j < len(src) and src[j] not in '"\n':3 if src[j] == "\\": escape পরীক্ষা4 j += 15if j >= len(src) or src[j] != '"':6 raise HaatError(line, col, …)7return j + 1
| j | |
| src[j] |
- String শুরু।
print(1:1) আর((1:6) আগেই token হয়েছে। এখনi= 6, অক্ষর", কলাম ৭। শাখা ৬ ডাকেscan_string(src, 6, 1, 7); ভেতরেjশুরু হয় 7 থেকে, অর্থাৎ কোটের পরের অক্ষরদ. - সাধারণ অক্ষর।
দকোট নয়, newline নয়, backslash নয়; তাই শুধুj += 1. বাংলা অক্ষর এখানে বৈধ: string-এর ভেতরে যেকোনো code point চলে। - লাইনের শেষ পর্যন্ত। একইভাবে
া ম : ৯ ৯ ৬ ) ;পার হয়;)আর;-ও এখন string-এর অংশ!jপৌঁছায় 17-এ, যা লেখার দৈর্ঘ্য (৬টি ASCII অক্ষর, কোট, তারপর ১০টি code point). loop শেষ, বন্ধ কোট পাওয়া যায়নি। - Error খোলা কোটে। লাইন ৫-এর শর্ত সত্য, তাই
HaatError(1, 7, "unterminated string literal"): কলাম ৭, খোলা কোট;j-এর কলাম (১৮) নয়। Lexer এখানেই থামে (নকশা-সিদ্ধান্ত ২);)আর;কখনো token হয় না। Reference-এর run-এও ঠিক1:7: error: unterminated string literal. - তুলনা: অজানা escape.
print("a\tb");-এj= 8-এ backslash, পরের অক্ষরtESCAPES-এ নেই (লাইন ৩)। Error-এর কলামcol + (j - i)= 7 + (8 − 6) = ৯, ঠিক backslash-এর ঘর:1:9: error: unknown escape sequence '\t', reference-এর run-এর সঙ্গে হুবহু এক।
৬ · পুরো tokenize() — comment, ফাঁকা ঘর, EOF আর প্রথম error-এ থামা
সব টুকরো এবার একসাথে। নিচের block reference-এর lexer.py-এর tokenize(), একই ক্রমে একই শাখা, আর dump হুবহু haat.py tokens-এর ছাপার রূপ (line:col ৭ ঘরে, kind ৯ ঘরে, তারপর lexeme). আগের block চালানো না থাকলে আগে সেটি চালান। নমুনা দুই লাইনের: বাজারঘরের ছাড়ের শর্ত, একটি বাংলা string, একটি comment, আর পরের লাইনে maximal munch আর একটি অদ্ভুত নাম। শেষে তিনটি ভাঙা লাইন।
# lexer.py-র tokenize(): একটি index i, সঙ্গে line আর col
def tokenize(src):
tokens, i, line, col = [], 0, 1, 1
while i < len(src):
c = src[i]
if c == "\n": # নতুন লাইন: col আবার ১
i, line, col = i + 1, line + 1, 1; continue
if c in " \t\r": # অন্য ফাঁকা ঘর
i, col = i + 1, col + 1; continue
if src.startswith("//", i): # comment: লাইনের শেষ পর্যন্ত
while i < len(src) and src[i] != "\n": i += 1
continue
start = i
if is_ident_start(c): # আগে পুরো শব্দ, তারপর টেবিল
while i < len(src) and (is_ident_start(src[i]) or is_digit(src[i])): i += 1
kind = KEYWORDS.get(src[start:i], "IDENT")
elif is_digit(c):
while i < len(src) and is_digit(src[i]): i += 1
if int(src[start:i]) > INT_MAX: raise HaatError(line, col, "integer literal too large")
kind = "INT"
elif c == '"': i, kind = scan_string(src, i, line, col), "STRING"
elif src[i:i + 2] in TWO_CHAR: kind, i = TWO_CHAR[src[i:i + 2]], i + 2 # লম্বাটি আগে
elif c in ONE_CHAR: kind, i = ONE_CHAR[c], i + 1
else: raise HaatError(line, col, f"unexpected character '{c}'")
tokens.append(Token(kind, src[start:i], line, col))
col += i - start # token কখনো লাইন পার হয় না
return tokens + [Token("EOF", "", line, col)]
def dump(src): # haat.py tokens-এর হুবহু রূপ
for t in tokenize(src): print(f"{t.line}:{t.col}".ljust(7) + f"{t.kind:<9}{t.text}".rstrip())
dump('if p >= 1000 { print("ছাড়"); } // মোট\nlet Int_2=a<=-b;')
for bad in ["let x = 5 @ 2;", "x = 9223372036854775808;", 'print("দাম: ৯৯৬);']:
try: tokenize(bad)
except HaatError as e: print(e)আসল আউটপুট (ব্রাউজারের Python):
1:1 IF if
1:4 IDENT p
1:6 GT_EQ >=
1:9 INT 1000
1:14 LBRACE {
1:16 PRINT print
1:21 LPAREN (
1:22 STRING "ছাড়"
1:28 RPAREN )
1:29 SEMI ;
1:31 RBRACE }
2:1 LET let
2:5 IDENT Int_2
2:10 EQ =
2:11 IDENT a
2:12 LT_EQ <=
2:14 MINUS -
2:15 IDENT b
2:16 SEMI ;
2:17 EOF
1:11: error: unexpected character '@'
1:5: error: integer literal too large
1:7: error: unterminated string literal
লক্ষ করুন: "ছাড়" STRING শুরু কলাম ২২-এ, আর পরের ) কলাম ২৮-এ, অর্থাৎ token-এর লেখা ৬টি code point (দুই কোট আর “ছাড়”-এর ৪টি: ছ া ড ়)। চোখে তিনটি বাংলা অক্ষর, ভেতরে চারটি code point; কলাম গোনা হয় ভেতরের হিসাবে (নকশা-সিদ্ধান্ত ১)। Comment // মোট কোনো token দেয়নি। দ্বিতীয় লাইনে Int_2 একটি সাধারণ নাম; =a-তে ফাঁকা না থাকলেও সমস্যা নেই, কারণ =a কোনো দুই অক্ষরের operator নয়। <=- আগের stepper-এর মতোই। শেষ তিন লাইন তিনটি lexical error: @ কলাম ১১-এ; খুব বড় সংখ্যার error literal-এর শুরুতে (কলাম ৫); শেষ না হওয়া string খোলা কোটে (কলাম ৭)। লেখকের lab-এ একই চারটি input ফাইলে রেখে python -B haat.py tokens চালানো হয়েছে: output byte ধরে হুবহু এক।
এই কোড থেকে চারটি নকশা-প্রশ্নের উত্তর পড়া যায়।
- Comment-এর শাখা শাখা ৮-এর আগে।
//না দেখে আগে/দেখলে comment দুটিSLASHহয়ে যেত। - Comment-এর ভেতরে
colবাড়ে না। দরকারও নেই: comment-এর পরে হয় newline (col আবার ১), নয় লেখার শেষ। শেষের ক্ষেত্রে একটি মজার ফল আছে, যা পরের অংশের পরীক্ষায় ধরা পড়বে। - EOF সবসময় থাকে। Parser-কে “আর token আছে কি না” আলাদা করে ভাবতে হয় না; তালিকার শেষে সবসময় একটি token, যার অবস্থান দিয়ে “শেষে কিছু বাকি” ধরনের error দেখানো যায়। Reference-এ
let x = // c(শেষে newline নেই) দিলে parser বলে1:9: error: expected expression, আর newline থাকলে2:1. - প্রথম error-এ থামা (নকশা-সিদ্ধান্ত ২)।
HaatErrorraise হলেই পুরো lexer থামে। লাইন ২-এ@আর লাইন ৩-এ#থাকলেও reference শুধু একটি বার্তা দেয়:2:11: error: unexpected character '@'. Parser, resolver আর type checker উল্টো, তারা সব error জানায় (পর্ব ৫০-এ এর কৌশল, Parser-এর error recovery আর ভালো diagnostic message).
Haat lexer-এর চারটি বার্তা, আর প্রতিটির কলাম কোথায়, এক জায়গায়:
| বার্তা | কখন | কলাম কোথায় |
|---|---|---|
unexpected character 'X' | কোনো শাখা মেলেনি: @ # & |, বাংলা অক্ষর, একা \ | সেই অক্ষর |
integer literal too large | মান 9223372036854775807-এর বেশি | literal-এর প্রথম অঙ্ক |
unterminated string literal | বন্ধ কোটের আগে newline বা লেখার শেষ | খোলা কোট |
unknown escape sequence '\t' | backslash-এর পরে " \ n ছাড়া অন্য কিছু | backslash |
৭ · Lexer পরীক্ষা — differential test, fuzz আর O(n)
“কোড চলছে” আর “কোড ঠিক” এক কথা নয়। একটি lexer-এর জন্য সবচেয়ে কাজের পরীক্ষা differential testing: একই input দুটি স্বাধীন বাস্তবায়নে দিয়ে ফল মেলানো। লেখকের lab-এ পাতার দুটি block (টেবিল আর tokenize) একসাথে চালিয়ে reference-এর সঙ্গে তিনটি তুলনা হয়েছে, সবই সত্যিকারের run (CPython 3.14.4):
$ python -B harness.py
examples: 13/13 identical, 1377 token lines
fuzz: 20000/20000 identical; errors 15317; tokens in ok runs 18556
$ python -B fuzz2.py # শুধু বৈধ টুকরো থেকে বানানো input
20000 20000 4124 122605
প্রথম লাইন: reference-এর examples/ ফোল্ডারের ১৩টি .haat ফাইলে পাতার dump আর python -B haat.py tokens-এর stdout ও stderr byte ধরে এক, মোট ১,৩৭৭টি token-লাইন। দ্বিতীয়টি একরকম fuzzing: ৫৪ রকম টুকরো (keyword, নাম, বড় সংখ্যা, operator, ভাঙা string, বাংলা অক্ষর, emoji, \r, একা \) এলোমেলো জোড়া দিয়ে ২০,০০০ input (seed 4646); প্রতিটিতে token-তালিকা বা error বার্তা হুবহু এক। এর ১৫,৩১৭টি কোনো error-এ শেষ হয়েছে, তাই error-এর পথগুলোও পরীক্ষিত। তৃতীয়: শুধু বৈধ টুকরো থেকে আরও ২০,০০০ input; সবগুলো এক, ১৫,৮৭৬টি সফল (মোট ১,২২,৬০৫টি token), আর বাকি ৪,১২৪টি error-এর ৩,৯৭৭টি unterminated string, ১৪৬টি খুব বড় সংখ্যা, ১টি একা backslash; জোড়া লাগানোয় বৈধ টুকরোও ভাঙা লেখা বানাতে পারে।
Reference ব্রাউজারে নেই, তাই পাতায় একই ধারণা আরেকভাবে: একটি দ্বিতীয়, সম্পূর্ণ আলাদা lexer, যা একটিমাত্র regular expression দিয়ে লেখা। Lexer generator (lex, flex, PLY) মোটামুটি এভাবেই কাজ করে: প্রতিটি token-এর একটি pattern, আর সবচেয়ে লম্বা মিল। দুটি lexer-কে ৩,০০০টি এলোমেলো input দিয়ে মেলানো হলো (seed 46, তাই প্রতিবার একই input). এটিও data-shared, আগের দুটি block-এর পরে চালান।
# দ্বিতীয়, স্বাধীন lexer: একটি regex (lexer generator-এর ধাঁচে), তারপর দুটির তুলনা
import re, random
PAT = re.compile(r'(?P<WS>[ \t\r]+)|(?P<NL>\n)|(?P<CM>//[^\n]*)|(?P<W>[A-Za-z_]\w*)|(?P<INT>[0-9]+)'
r'|(?P<STRING>"(?:\\["\\n]|[^"\\\n])*")|(?P<OP>==|!=|<=|>=|&&|\|\||->|[-+*/%<>!=(){},;:])', re.ASCII)
def regex_lex(src):
out, pos, line, ls = [], 0, 1, 0 # ls = লাইন কোথায় শুরু
while pos < len(src):
m, col = PAT.match(src, pos), pos - ls + 1
if not m:
if src[pos] != '"': return f"{line}:{col}: error: unexpected character '{src[pos]}'"
k = re.match(r'"(?:\\["\\n]|[^"\\\n])*', src[pos:]).end() + pos # কোথায় আটকাল
if src[k:k + 1] != "\\": return f"{line}:{col}: error: unterminated string literal"
return f"{line}:{k - ls + 1}: error: unknown escape sequence '{src[k:k + 2].rstrip(chr(10))}'"
g, text = m.lastgroup, m.group()
if g == "NL": line, ls = line + 1, m.end()
elif g == "INT" and int(text) > 2**63 - 1: return f"{line}:{col}: error: integer literal too large"
elif g == "W": out.append((KEYWORDS.get(text, "IDENT"), text, line, col))
elif g == "OP": out.append((TWO_CHAR.get(text) or ONE_CHAR[text], text, line, col))
elif g in ("INT", "STRING"): out.append((g, text, line, col))
pos = m.end()
return out + [("EOF", "", line, pos - ls + 1)]
def hand_lex(src):
try: return [(t.kind, t.text, t.line, t.col) for t in tokenize(src)]
except HaatError as e: return str(e)
BITS = ["let", "Int", "fn", "iffy", "x_1", "0", "007", "9223372036854775808", "<", "<=", "=", "==",
"-", ">", "->", "&", "&&", "|", "||", "!", '"ok"', '"ঘর\\n"', '"a\\tb"', '"open', "// c\n",
" ", "\n", "\t", "ক", "@", "(", ")", "{", "}", ";", ":", "+", "/", "%", "\\"]
random.seed(46); same = errs = ntok = 0; diff = []
for _ in range(3000):
src = "".join(random.choice(BITS) + random.choice(["", " "]) for _ in range(random.randint(1, 12)))
a, b = hand_lex(src), regex_lex(src)
same += a == b; errs += type(a) is str; ntok += 0 if type(a) is str else len(a)
if a != b: diff.append((src, a[-1], b[-1]))
print(f"{same}/3000 মিলেছে; error দিয়ে শেষ {errs}টি; সফলগুলোয় মোট {ntok}টি token")
for d in diff: print("অমিল:", *map(repr, d), sep="\n ")আসল আউটপুট (ব্রাউজারের Python):
2999/3000 মিলেছে; error দিয়ে শেষ 2061টি; সফলগুলোয় মোট 4237টি token
অমিল:
'>let "ok" // <'
('EOF', '', 1, 11)
('EOF', '', 1, 15)
৩,০০০-এর মধ্যে ২,৯৯৯টিতে দুটি lexer হুবহু এক: একই token, একই অবস্থান, একই error বার্তা ও কলাম। ২,০৬১টি input কোনো error-এ শেষ হয়েছে, আর সফলগুলোয় মোট ৪,২৩৭টি token মিলেছে। কিন্তু একটি অমিল আছে, আর সেটিই এই পরীক্ষার সবচেয়ে দামি ফল। Input >let "ok" // <: শেষে একটি comment, তারপর কোনো newline নেই। হাতে লেখা lexer (আর reference) EOF দেয় কলাম ১১-এ, যেখানে comment শুরু; regex lexer দেয় ১৫-তে, লেখার একদম শেষে। কারণ হাতে লেখা lexer comment-এর ভেতরে col বাড়ায় না।
কোনটি ঠিক? Haat spec v1 EOF-এর অবস্থান বলে না। Reference-ই এই কোর্সের মাপকাঠি, তাই regex lexer-কে বদলাতে হবে (comment-এর শাখায় pos না সরিয়ে EOF-এর জন্য comment-এর শুরু মনে রাখা)। আসল শিক্ষা অন্যখানে: differential test শুধু bug খোঁজে না, spec-এর ফাঁক খোঁজে। দুজন যত্নশীল মানুষ একই নিয়ম পড়ে দুই রকম কোড লিখেছে; নিয়মটি লিখে না রাখলে পরের lexer আবার আলাদা হবে। এমন সিদ্ধান্ত spec v2-এর জন্য তালিকায় তোলার মতো।
Lexer কেন O(n)
প্রতিটি loop-ঘোরায় i অন্তত ১ বাড়ে, অথবা lexer থামে: newline আর ফাঁকা ঘর ১, comment অন্তত ২, শব্দ আর সংখ্যা অন্তত ১, string অন্তত ২, operator ১ বা ২। আর ভেতরের প্রতিটি ছোট loop-ও i (বা j) বাড়ায়, কখনো পেছনে যায় না। তাই প্রতিটি অক্ষর নির্দিষ্ট কয়েকবারের বেশি দেখা হয় না, আর মোট কাজ লেখার দৈর্ঘ্য n-এর সমানুপাতিক (পূর্ণ প্রমাণ অনুশীলন ৪-এ)। একটিই ব্যতিক্রম: int() দিয়ে খুব লম্বা সংখ্যা রূপান্তর, যা ওপরের bug-এর সমাধানে দৈর্ঘ্য-পরীক্ষা দিয়ে ১৯ অঙ্কে সীমিত হয়। লেখকের একটি যন্ত্রে bazar.haat ১০০, ১,০০০ আর ১০,০০০ বার জোড়া দিয়ে মাপা হয়েছে (একটি যন্ত্রের উদাহরণ, benchmark নয়):
43500 chars 12901 tokens 0.014 s 329 ns/char
435000 chars 129001 tokens 0.148 s 339 ns/char
4350000 chars 1290001 tokens 1.533 s 352 ns/char
লেখা ১০ গুণ হলে সময়ও প্রায় ১০ গুণ; প্রতি অক্ষরে সময় প্রায় একই থাকে। এটিই রৈখিক (linear) আচরণের চিহ্ন।
পরীক্ষা ও ইন্টারভিউতে. বিশ্ববিদ্যালয়, চাকরি বা ইন্টারভিউর পরীক্ষায় lexer নিয়ে সাধারণত এমন প্রশ্ন আসে:
- Token, lexeme আর pattern-এর পার্থক্য? Pattern হলো নিয়ম (
[0-9]+), lexeme হলো source-এর আসল টুকরো (1000), token হলো শ্রেণি আর সঙ্গের তথ্য (INT,"1000", 1:9). if p >= 1000 {-এ কয়টি token? ৫টি, সঙ্গে EOF ধরলে ৬টি;>=একটি token (maximal munch).- Keyword আর identifier lexer কীভাবে আলাদা করে? আগে পুরো শব্দ, তারপর keyword টেবিলে lookup; তাই
iffyএকটি IDENT. - Lexer-এর time complexity? O(n): cursor কখনো পেছনে যায় না, প্রতিটি অক্ষর স্থির-সংখ্যকবার দেখা হয়।
- “একটি calculator-এর tokenizer লিখুন” (ইন্টারভিউ)। এই পর্বের
tokenize()-এর ছোট রূপ, সঙ্গে অবস্থান আর error; ভালো উত্তর ফাঁকা input, খুব বড় সংখ্যা আর অচেনা অক্ষরও সামলায়।
৮ · Token দিয়ে রং — editor আর বাস্তব compiler-এর lexer
আপনার editor যখন while-কে এক রঙে আর "চাল"-কে আরেক রঙে দেখায়, তখন ভেতরে একটি ছোট lexer চলছে; একে বলে syntax highlighting. নিচের JavaScript block Haat-এর জন্য এমন একটি highlighter: প্রতিটি অক্ষরের নিচে তার token-শ্রেণির একটি অক্ষর লেখে। কলাম মেলাতে সে Array.from দিয়ে code point গোনে, কারণ JavaScript-এর string ভেতরে UTF-16, আর .length code point নয়, UTF-16 unit গোনে।
// Haat token highlighter: প্রতিটি অক্ষরের নিচে তার token-এর শ্রেণির এক অক্ষর
// C comment, K keyword, I নাম, N সংখ্যা, S string, O operator, P বন্ধনী/যতি, ! অচেনা
const KW = new Set("let var fn if else while return true false print".split(" "));
const RX = /(\/\/.*)|([A-Za-z_]\w*)|([0-9]+)|("(?:\\["\\n]|[^"\\\n])*")|(==|!=|<=|>=|&&|\|\||->|[-+*\/%<>!=])|([(){},;:])|([ \t\r]+)/y;
function paint(src) {
let row = "", pos = 0, m;
RX.lastIndex = 0;
while (pos < src.length && (m = RX.exec(src))) {
const g = m.slice(1).findIndex(x => x !== undefined); // কোন দল মিলল
const tag = g === 1 && KW.has(m[0]) ? "K" : "CINSOP "[g];
row += tag.repeat(Array.from(m[0]).length); // code point ধরে
pos = RX.lastIndex;
}
return pos < src.length ? row + "!" : row; // প্রথম error-এ থামা
}
for (const line of ["if p >= 1000 { return p - p / 10; }",
'let msg = "say \\"hi\\""; // note',
"ok = a<=-b && !done;",
"let x = 5 @ 2;"]) {
console.log(line);
console.log(paint(line));
}
const t = '"চাল 🛒"';
console.log("UTF-16 unit:", t.length, "| code point:", Array.from(t).length);আসল আউটপুট (ব্রাউজারের JavaScript; Node 24-এও হুবহু একই):
if p >= 1000 { return p - p / 10; }
KK I OO NNNN P KKKKKK I O I O NNP P
let msg = "say \"hi\""; // note
KKK III O SSSSSSSSSSSSP CCCCCCC
ok = a<=-b && !done;
II O IOOOI OO OIIIIP
let x = 5 @ 2;
KKK I O N !
UTF-16 unit: 8 | code point: 7
প্রথম জোড়ায় return K, >= দুটি O (একটি token, দুই কলাম), 10; হলো NNP. দ্বিতীয়টিতে \"-সহ পুরো string একটি S-এর সারি, আর comment সাত ঘরের C. তৃতীয়টিতে a<=-b হলো IOOOI: <= আর - আলাদা token হলেও তিনটিই operator-শ্রেণি। চতুর্থটিতে @-এ এসে ! দিয়ে থেমেছে, Haat lexer-এর মতোই প্রথম error-এ। শেষ লাইন: "চাল 🛒"-এ ৭টি code point কিন্তু ৮টি UTF-16 unit, কারণ 🛒 emoji BMP-র বাইরে, তাই দুটি unit (surrogate pair) নেয়। Reference-এর run-এ let s = "চাল 🛒"; x-এর ; কলাম ১৬-এ, code point গুনে; UTF-16 গুনলে হতো ১৭, UTF-8 byte গুনলে ২৫। Editor আর compiler আলাদা একক গুনলে error-এর দাগ ভুল জায়গায় পড়ে; Haat-এর language server বানালে (পর্ব ৮০, Language tooling — LSP, formatter, linter আর incremental compilation) এই রূপান্তর লাগবে।
বাস্তবের বড় compiler-গুলোর বেশিরভাগ lexer হাতে লেখা। প্রকাশ্য source code অনুযায়ী Clang-এর Lexer, GCC-র C-পরিবারের lexer (libcpp), Go compiler-এর scanner আর rustc-এর rustc_lexer সবই হাতে লেখা। কারণগুলো এই পর্বেই দেখেছেন: সঠিক অবস্থান, নিজের মতো error বার্তা, ভাষার বিশেষ নিয়ম (যেমন Python-এর indentation থেকে INDENT/DEDENT token), আর গতি। অন্যদিকে lex (Mike Lesk আর Eric Schmidt, Bell Labs, ১৯৭৫) আর তার উত্তরসূরি flex-এর মতো generator ছোট ভাষা, DSL আর দ্রুত নমুনা বানাতে এখনো খুব কাজের; ToC কোর্সের পর্ব ৪০-এ PLY আর Lark-এর সত্যিকারের run আছে। Haat হাতে লেখা lexer বেছে নিয়েছে, কারণ ৮৬ লাইনে পুরোটা পড়া যায়, আর প্রতিটি সিদ্ধান্ত চোখে দেখা যায়।
আরও গভীরে. কিছু ভাষার lexer আসল lexing-এর আগেও একটি ধাপ চালায়। Java-তে \u000a ধরনের Unicode escape tokenization-এর আগে আসল অক্ষরে বদলে যায় (Java Language Specification §3.3), তাই comment-এর ভেতরে \u000a লিখলে comment সেখানেই শেষ হয়ে পরের লেখা কোড হয়ে যায়, একটি বিখ্যাত ধাঁধা। Python 3.12 থেকে tokenize module CPython-এর C-তে লেখা tokenizer ব্যবহার করে, যা f-string-কে আর একটি মাত্র STRING token হিসেবে দেখে না (PEP 701). আর editor-গুলো পুরো ফাইল বারবার lex না করে শুধু বদলানো অংশের আশপাশ নতুন করে lex করে (incremental lexing); এজন্যই অনেক highlighter-এর lexer “লাইনের শুরুতে কোন অবস্থা ছিল” মনে রাখে।
৯ · AI-এর যুগে lexer লেখা
“একটি lexer লিখে দাও” AI-এর কাছে সহজ অনুরোধ, আর উত্তরও দ্রুত আসে। কিন্তু lexer-এর ভুল খুব চুপচাপ: প্রোগ্রাম চলে, শুধু একটি token বা একটি কলাম ভুল, আর তার ফল দেখা যায় অনেক পরে, parser-এর অদ্ভুত error-এ (stepper ২-এর ধাপ ৬)। AI-এর লেখা lexer-এ যা প্রায়ই দেখা যায়:
| AI-এর ভুল | কীভাবে ধরবেন |
|---|---|
এক অক্ষরের operator আগে, বা regex-এ < আগে <= পরে | a<=-b, x!=y, f->g দিয়ে token গুনুন |
isdigit()/isalpha() দিয়ে অঙ্ক বা নাম চেনা, ফলে বাংলা অঙ্ক বা অক্ষর ঢুকে পড়া | ৫২০ আর দাম দিয়ে চালান; Haat-এ দুটিই error হওয়ার কথা |
| কলাম byte বা UTF-16 ধরে গোনা, বা tab-কে ৪/৮ ধরা | বাংলা string আর emoji-র পরের token-এর কলাম reference-এর সঙ্গে মেলান |
Keyword আগে মেলানো, তাই iffy → IF + fy | iffy, printer, letter দিয়ে চালান |
নিজের মতো escape যোগ করা (\t, \u) বা error বার্তার ভাষা বদলানো | Spec-এর তালিকা আর reference-এর বার্তা অক্ষর ধরে মেলান |
“Python-এ যেমন, সব ভাষায় তেমন” ধরে নেওয়া (যেমন -- বা octal 007) | প্রতিটি ভাষার নিয়ম তার spec থেকে, আর সেই ভাষার আসল tool চালিয়ে |
AI-কে lexer লিখতে বললে spec, নাম আর পরীক্ষা তিনটিই প্রশ্নে দিয়ে দিন, যাতে উত্তর যাচাই করা যায়:
AI-এর লেখা lexer হাতে পেলে — যাচাইয়ের চেকলিস্ট
ভাবনার প্রশ্ন
প্রতিটি প্রশ্ন নিয়ে নিজে কিছুক্ষণ ভাবুন — তারপর “→ উত্তর” চাপুন।
প্র ০১Lex আর flex থাকতে বড় compiler-গুলো lexer হাতে লেখে কেন?
Lexer generator-এর ধারণা পুরোনো আর সুন্দর। ১৯৭৫ সালে Bell Labs-এ Mike Lesk আর Eric Schmidt lex বানান: আপনি প্রতিটি token-এর regex লেখেন, tool একটি DFA-চালিত C program বানিয়ে দেয়। পরে flex একই কাজ আরও দ্রুত করে, আর আজও Unix জগতে বহুল ব্যবহৃত। তত্ত্বের দিক থেকে এটি নিখুঁত: ToC পর্ব ২২-এ দেখেছেন, regex থেকে NFA, NFA থেকে DFA, আর maximal munch সবই যান্ত্রিকভাবে করা যায়।
তবু প্রকাশ্য source code দেখলে Clang, GCC, Go আর rustc-এর lexer হাতে লেখা। প্রথম কারণ error: generator-এর তৈরি lexer সাধারণত বলে “এখানে মেলেনি”, কিন্তু একটি ভালো compiler বলতে চায় “এই string-টি লাইন ৩-এ শুরু হয়ে শেষ হয়নি”, বা “\t এই ভাষায় নেই, আপনি কি \\t বোঝাতে চেয়েছিলেন?” দ্বিতীয় কারণ প্রসঙ্গ: বাস্তব ভাষার lexing পুরোপুরি regular নয়। Python-এর INDENT/DEDENT-এর জন্য একটি indentation-এর stack লাগে; C-তে একটি নাম typedef কি না, তা জানতে lexer-কে symbol table-এর খবর রাখতে হয় (বিখ্যাত “lexer hack”); অনেক ভাষার string interpolation-এ string-এর ভেতরে আবার expression. হাতে লেখা lexer-এ এগুলো কয়েক লাইনের কাজ, generator-এ প্রায়ই জটিল কৌশল। তৃতীয় কারণ Unicode আর গতি: নিজের লেখা lexer UTF-8 সরাসরি পড়ে, নিজের মতো buffer রাখে, আর profiler দেখে দ্রুত করা যায়।
তাহলে generator কি অচল? মোটেও না। একটি নতুন DSL, একটি config-ফাইলের format, বা দ্রুত নমুনার জন্য PLY, Lark বা flex কয়েক মিনিটে কাজ করা lexer দেয়, আর regex-এর তালিকাটিই হয়ে যায় নথি। দুটির মাঝে একটি সেতুও আছে: এই পর্বের অংশ ৭-এর মতো generator-ধাঁচের একটি lexer-কে হাতে লেখা lexer-এর test oracle হিসেবে রাখা।
মূল উপলব্ধি: Generator দেয় সঠিকতা আর গতিতে শুরু; হাতে লেখা lexer দেয় নিয়ন্ত্রণ: error-এর ভাষা, প্রসঙ্গ আর performance. ভাষা যত বড় আর যত মানুষ ব্যবহার করে, নিয়ন্ত্রণের দাম তত বেশি।
প্র ০২Error-এর “কলাম” কী দিয়ে গোনা উচিত: byte, code point, UTF-16 unit, না চোখে দেখা অক্ষর?
প্রশ্নটি নিরীহ শোনায়, কিন্তু চার রকম উত্তরই বাস্তবে চালু আছে। Byte: UTF-8 ফাইলে সবচেয়ে সস্তা হিসাব; কিন্তু “বাজারঘর” লিখলেই কলাম ১৪ ঘর সরে যায়, কারণ প্রতিটি বাংলা code point UTF-8-এ ৩ byte. UTF-16 unit: JavaScript আর Java-র string এভাবে গোনে, আর Language Server Protocol বহুদিন এটিই ধরে নিত; 3.17 version থেকে client আর server আলোচনা করে UTF-8, UTF-16 বা UTF-32 বেছে নিতে পারে (পর্ব ২১-এ বিস্তারিত)। Code point: Haat-এর পছন্দ (নকশা-সিদ্ধান্ত ১), Python-এর str-এর সঙ্গে স্বাভাবিকভাবে মেলে, আর emoji-ও এক কলাম। চোখে দেখা অক্ষর (grapheme) বা পর্দার প্রস্থ: মানুষের জন্য সবচেয়ে স্বাভাবিক; “ক্ষ” চোখে একটি যুক্তাক্ষর, কিন্তু ভেতরে তিনটি code point (ক, হসন্ত, ষ); আবার একটি চীনা অক্ষর terminal-এ দুই ঘর চওড়া।
Tab আরেকটি জট। Haat tab-কে এক কলাম ধরে, কারণ tab-এর প্রস্থ editor-ভেদে ২, ৪ বা ৮। GCC 11 থেকে -fdiagnostics-column-unit option আছে, যা “display” (পর্দার প্রস্থ, tab বিস্তার করে) আর “byte”-এর মধ্যে বেছে নিতে দেয়; অর্থাৎ বড় compiler-ও এক উত্তরে থামেনি।
সঠিক উত্তর তাই নির্ভর করে কে কলামটি পড়বে তার ওপর। মানুষ পড়লে পর্দার হিসাব ভালো; আরেকটি program (editor, LSP client) পড়লে দুই পক্ষ যে একক মানে সেটি। একটি সমাধান হলো lexer-এর ভেতরে একটি নির্ভরযোগ্য একক রাখা (Haat-এ code point, বা অনেক compiler-এ byte offset) আর দেখানোর সময় রূপান্তর করা। ভুল হয় তখনই, যখন দুই পক্ষ নিঃশব্দে আলাদা একক ধরে নেয়: error-এর দাগ বাংলা লেখার পরে ভুল জায়গায় পড়ে, আর ব্যবহারকারী ভাবেন compiler-ই ভুল।
মূল উপলব্ধি: “কলাম” একটি চুক্তি, প্রাকৃতিক সত্য নয়। ভাষার spec-এ একক লিখে রাখুন, lexer-এ সেটি মানুন, আর যেখানে অন্য tool-এর সঙ্গে কথা হয় সেখানে স্পষ্ট রূপান্তর করুন।
প্র ০৩Maximal munch কখন প্রোগ্রামারের মনের উল্টো কাজ করে, আর ভাষা-নকশাকারীরা কীভাবে সামলান?
Maximal munch সরল, দ্রুত আর প্রায় সবসময় ঠিক। কিন্তু lexer অর্থ বোঝে না, তাই কিছু জায়গায় সে এমন token বানায় যা পরের ধাপে অর্থহীন। C-র standard নিজেই উদাহরণ দেয়: x+++++y ভাঙে x ++ ++ + y হিসেবে, যা বৈধ নয়, অথচ x ++ + ++ y বৈধ হতো। Lexer পেছনে ফিরে অন্যভাবে কাটার চেষ্টা করে না।
বিখ্যাত উদাহরণ C++-এর template: vector<vector<int>>-এর শেষে >> হলো right shift-এর token. C++98/03-এ তাই মাঝে একটি space লিখতে হতো (> >). C++11 নিয়ম বদলায়: template-এর ভেতরে parser প্রয়োজনে >>-কে দুটি > হিসেবে পড়ে। Java-র generics-এও parser একই কাজ করে। অর্থাৎ সমাধানটি lexer-এ নয়, parser-এ: lexer লম্বা token দেয়, আর যে ধাপ প্রসঙ্গ জানে সে দরকারে ভাঙে।
Haat-এ একটি মজার উদাহরণ আছে। C-তে while (x --> 0) একটি পরিচিত কৌতুক (“goes to operator”), যার আসল মানে (x--) > 0. Haat-এ -- নেই, কিন্তু -> আছে! তাই while x-->0 { … } lexer-এ হয় x, -, ->, 0, আর reference-এর check বলে 1:9: error: expected expression (সত্যিকারের run). Function type-এর জন্য বেছে নেওয়া একটি token অন্য জায়গায় ছায়া ফেলেছে।
নকশাকারীরা তিনভাবে সামলান: এমন operator-জোড়া এড়ানো যেখানে একটি অন্যটির শুরু হয়ে অস্পষ্টতা আনে (Haat-এ ++, -- নেই); ভালো error বার্তা (একটি উন্নত Haat বলতে পারত, “-> এখানে অর্থহীন; আপনি কি - > বোঝাতে চেয়েছিলেন?”); আর দরকারে parser-কে token ভাঙার অনুমতি দেওয়া।
মূল উপলব্ধি: Token-এর তালিকা ভাষার নকশার অংশ। প্রতিটি নতুন operator শুধু নিজের জায়গায় নয়, অন্য সব চিহ্নের পাশে বসে কী বানায়, সেটিও ভাবতে হয়।
প্র ০৪Lexer প্রথম error-এ থামবে, নাকি সব error খুঁজে জানাবে?
Haat-এর reference প্রথম lexical error-এ থামে (নকশা-সিদ্ধান্ত ২), অথচ parser, resolver আর type checker সব error জানায়। এই অসমতা ইচ্ছাকৃত। Lexical error প্রায়ই পরের সবকিছু নষ্ট করে। একটি কোট বাদ পড়লে, Haat-এ string লাইন পার হয় না বলে ক্ষতি এক লাইনে থামে, কিন্তু যেসব ভাষায় string কয়েক লাইন চলতে পারে, সেখানে পরের কোডের কোট-গুলো উল্টো জোড়া হয়ে শত শত ভুয়া error দেয়। প্রথম বার্তাটিই একমাত্র বিশ্বাসযোগ্য; বাকিগুলো ছায়া (cascade).
অন্যদিকে একজন মানুষ একবারে কয়েকটি ভুল জানতে চান, বিশেষ করে বড় ফাইলে। বাস্তব compiler-এর lexer তাই সাধারণত থামে না: অচেনা অক্ষর পেলে বার্তা দিয়ে সেটি বাদ দেয়, বা একটি “error token” বানিয়ে parser-কে দেয়, আর শেষ না হওয়া string-কে লাইনের শেষে বন্ধ ধরে নেয়। Editor-এর জন্য এটি জরুরি: আপনি টাইপ করার মাঝপথে ফাইল প্রায় সবসময় ভাঙা, তবু রং, autocomplete আর বাকি অংশের error চাই। এজন্য IDE-কেন্দ্রিক compiler-গুলো এমনভাবে নকশা করা যাতে ভাঙা input থেকেও একটি পূর্ণ token-তালিকা আর syntax tree আসে।
Haat-এর পছন্দের পেছনে শিক্ষাগত কারণও আছে: ৮৬ লাইনের lexer-এ recovery যোগ করলে প্রতিটি শাখায় “ভুল হলে কী” ভাবতে হয়, আর error-এর ক্রম ও সংখ্যা পরীক্ষা করা কঠিন হয়। Recovery-র আসল আলোচনা পর্ব ৫০-এ, parser-এর panic-mode (নকশা-সিদ্ধান্ত ২৫) দিয়ে, যেখানে এর লাভ সবচেয়ে বেশি। চাইলে Haat-এর lexer-কে সহজেই বদলানো যায়: raise-এর বদলে error-টি একটি তালিকায় রেখে অক্ষরটি পার হওয়া, আর শেষে সব error একসাথে ফেরত দেওয়া; তখন golden ফাইলগুলোও বদলাতে হবে।
মূল উপলব্ধি: “কতগুলো error দেখাব” একটি নকশা-সিদ্ধান্ত, যার দুই দিকে সরলতা আর ব্যবহারকারীর সময়। Batch compiler-এ প্রথম error যথেষ্ট হতে পারে; editor-এ ভাঙা input-কে সামলানোই আসল কাজ।
প্র ০৫একটি ভাষায় নতুন keyword যোগ করা কেন বিপজ্জনক, আর Haat-এর Int কেন keyword নয়?
Keyword মানে reserved word: lexer সেটিকে কখনো IDENT দেয় না। তাই নতুন keyword যোগ করলে পুরোনো যে কোডে সেই শব্দ নাম হিসেবে ছিল, তা হঠাৎ syntax error দেয়। Python 3.7-এ async আর await পুরো keyword হয়, আর যেসব library এগুলোকে parameter বা variable-এর নাম হিসেবে ব্যবহার করত, তাদের কোড বদলাতে হয়েছিল। অভিজ্ঞতা থেকে Python পরে অন্য পথ নেয়: 3.10-এ match আর case “soft keyword”, যা শুধু pattern matching-এর জায়গায় keyword, অন্যত্র সাধারণ নাম; 3.12-এ type-ও এভাবে আসে। C#-ও বহু নতুন শব্দ (যেমন var, async) contextual keyword হিসেবে এনেছে।
এর দাম পড়ে lexer আর parser-এর ভাগাভাগিতে। Contextual keyword lexer চিনতে পারে না, কারণ সে প্রসঙ্গ জানে না; শব্দটি IDENT হয়েই parser-এ যায়, আর parser lookahead দেখে ঠিক করে এটি keyword না নাম। Parser জটিল হয়, কিন্তু পুরোনো কোড ভাঙে না।
Haat-এর Int Bool Str Unit এই চিন্তার ছোট রূপ (নকশা-সিদ্ধান্ত ৬)। এগুলো IDENT, আর parser শুধু type-এর জায়গায় এদের type হিসেবে পড়ে; অন্য নাম সেখানে এলে unknown type 'X'. লাভ দুটি। প্রথমত, পরে Float বা বর্ধিত রূপে array-র type যোগ করলে lexer আর keyword টেবিল ছুঁতে হয় না। দ্বিতীয়ত, ভাষার “নিষিদ্ধ শব্দ”-এর তালিকা ছোট থাকে, ১০টি। উল্টো দিকও আছে: lexer-এর output দেখে বোঝা যায় না কোনটি type, তাই syntax highlighter-কে আলাদা নিয়ম জানতে হয়, আর error বার্তা আসে parser থেকে, lexer থেকে নয়।
FORTRAN আর PL/I-এর মতো পুরোনো ভাষায় কোনো reserved word-ই ছিল না: IF নামে variable-ও রাখা যেত, যা lexer-parser দুটিকেই কঠিন করেছিল। আধুনিক ভাষাগুলো মাঝের পথে: অল্প কয়েকটি সত্যিকারের keyword, বাকিগুলো প্রসঙ্গ-নির্ভর।
মূল উপলব্ধি: Keyword টেবিল ভাষার সঙ্গে ব্যবহারকারীদের একটি চুক্তি। যত ছোট, ভাষা তত সহজে বাড়তে পারে; প্রসঙ্গ-নির্ভর শব্দ সেই বৃদ্ধির দাম parser-এর ঘাড়ে দেয়।
অনুশীলন
প্রতিটির উত্তর লেখকের lab-এ চালিয়ে মেলানো। নিজে আগে করে তারপর খুলুন।
-
বাস্তবায়ন — block comment (Haat-এর বর্ধিত রূপ): Haat-এ
/* … */comment যোগ করতে চান, যা কয়েক লাইন চলতে পারে; nesting নেই (C-র মতো)। শেষ না হলে errorunterminated block comment, খোলার/*-এর অবস্থানে।tokenize()-এ কোথায়, কী কোড যোগ করবেন? “Token লাইন পার হয় না” শর্তটি এখন কী হলো, আরlet a = 1; /* দাম⏎ ঠিক */ let b = 2;-এ দ্বিতীয়let-এর অবস্থান কত?Comment-এর শাখার পরে আর
start = i-এর আগে, অর্থাৎ শাখা ৮-এর/-এর আগেই:if src.startswith("/*", i): end = src.find("*/", i + 2) if end == -1: raise HaatError(line, col, "unterminated block comment") for ch in src[i:end + 2]: if ch == "\n": line, col = line + 1, 1 else: col += 1 i = end + 2; continueComment এখন লাইন পার হতে পারে, তাই
col += i - start-এর কৌশল এখানে চলে না; ভেতরের প্রতিটি অক্ষর গুনে line আর col আলাদা করে বদলাতে হয়। Comment token নয়, তাই সমস্যা শুধু অবস্থানের। লেখকের lab-এ চালানো ফল: দ্বিতীয়let2:9-এ (দ্বিতীয় লাইনে “ ঠিক */ ”-এর পরে), শেষেEOF 2:19;let a = 1; /* খোলাদিলে1:12: error: unterminated block comment;a/**/bদুটি IDENT. Nesting না থাকায়a /* /* */ */ b-এর প্রথম*/-এ comment শেষ, বাকি*/হয় STAR আর SLASH (কলাম ১২, ১৩), যা পরে parser-এর error. Rust-এর মতো nested comment চাইলে একটি গভীরতার গণক লাগবে। -
ভুল খুঁজুন: এক বন্ধু
tokenize()-এর দুটি লাইনের ক্রম উল্টে লিখেছেন: আগেelif c in ONE_CHAR, তারপরelif src[i:i + 2] in TWO_CHAR. তাঁর lexer কোনো error দেয় না, আরa && b,a || bঠিকঠাক token দেয়। তাহলে bug কোথায়?if a <= b { print("ঘর"); }-এ কী হয়, আর কোন কোন operator ভাঙে?Maximal munch ভেঙেছে।
<ONE_CHAR-এ আছে, তাই TWO_CHAR পর্যন্ত যাওয়াই হয় না:<=হয়ে যায়LT 1:6আরEQ 1:7. লেখকের lab-এ এই ভাঙা lexer-এর token reference parser-কে দিলে বার্তা আসে1:7: error: expected expression, যা ভুলের আসল জায়গা (lexer) থেকে অনেক দূরে। ভাঙে== != <= >= ->: যেমনx != yহয় BANG, EQ আরf -> gহয় MINUS, GT. কিন্তু&&আর||বেঁচে যায়, কারণ একা&বা|ONE_CHAR-এ নেই, তাই ওই দুটির জন্য ONE_CHAR শাখা খাটে না। এজন্যই কয়েকটি “সহজ” test পাস করে bug লুকিয়ে থাকে; প্রতিটি দুই অক্ষরের operator আলাদা করে পরীক্ষা করা দরকার, বা differential test. -
Trace — output অনুমান করুন: এক লাইনের এই Haat source-এর (শেষে newline নেই)
haat.py tokensoutput লিখুন, প্রতিটিline:col-সহ:let s = "ঘর\n";x>=-7// শেষ(string-এর ভেতরে\nদুটি অক্ষর: backslash আর n).Reference-এর সত্যিকারের run:
1:1 LET let 1:5 IDENT s 1:7 EQ = 1:9 STRING "ঘর\n" 1:15 SEMI ; 1:16 IDENT x 1:17 GT_EQ >= 1:19 MINUS - 1:20 INT 7 1:21 EOFSTRING-এর লেখা ৬টি code point (দুই কোট, ঘ, র, backslash, n), তাই
;9 + 6 = ১৫-তে।>=-হলো GT_EQ আর MINUS (maximal munch),-7দুটি token. সবচেয়ে সূক্ষ্ম অংশ শেষে: comment কলাম ২১-এ শুরু, আর শেষে newline নেই, তাই EOF থাকে1:21-এ, comment-এর শুরুতে (অংশ ৭-এর অমিলটি)। কেউ যদি ২৬ লেখেন (লাইনের শেষ), তাঁর lexer reference থেকে আলাদা। -
প্রমাণ — lexer রৈখিক: দেখান যে reference-এর
tokenize()সফলভাবে শেষ হলে মোট কাজ O(n), যেখানে n লেখার দৈর্ঘ্য (code point-এ); ধরে নিন dictionary lookup আর একটি অক্ষর তুলনা O(1), আর literal-এরint()রূপান্তর সংশোধিত রূপে ১৯ অঙ্কে সীমিত।প্রমাণ।
- বাইরের loop-এর প্রতিটি ঘোরা একটি শাখা নেয়। শাখা ১ ও ২-এ
iঠিক ১ বাড়ে। শাখা ৩-এsrc[i] = "/", যা newline নয়, তাই ভেতরের loop অন্তত একবার চলে আরiঅন্তত ১ বাড়ে। শাখা ৪ ও ৫-এ প্রথম অক্ষরটি শর্ত মানে, তাইiঅন্তত ১ বাড়ে; শাখা ৬-এscan_stringফেরত দেয় অন্ততi + 2; শাখা ৭-এ ২, শাখা ৮-এ ১। শাখা ৯ বা কোনো error হলে lexer থামে। iকখনো কমে না, আর loop চলে শুধুi < nহলে। ধাপ ১ অনুযায়ী প্রতিটি ঘোরায়iঅন্তত ১ বাড়ে, তাই বাইরের loop সর্বোচ্চ n বার ঘোরে।- ভেতরের loop-গুলো (নাম, অঙ্ক, comment, string-এর
j) প্রতিটি পদক্ষেপে cursor ১ বা ২ বাড়ায়, আর প্রতিটি পদক্ষেপে O(1) কাজ। Token-এর শেষে বাইরেরiসেখানেই বসে, যেখানে ভেতরের loop থেমেছিল। তাই সব ভেতরের পদক্ষেপ মিলিয়ে cursor-এর মোট অগ্রগতি ≤ n, অর্থাৎ মোট ভেতরের কাজ O(n). - প্রতিটি token-এ বাড়তি কাজ: slicing
src[start:i](token-এর দৈর্ঘ্যের সমানুপাতিক, আর সব token-এর দৈর্ঘ্যের যোগফল ≤ n), একটি lookup, একটিTokenবানানো, আর INT-এ ≤ ১৯ অঙ্কের রূপান্তর, অর্থাৎ ধ্রুবক। Token-এর সংখ্যা ≤ n. - যোগফল: O(n) + O(n) + O(n) = O(n). ∎
খেয়াল করুন ধাপ ৪-এর শর্তটি: সীমাহীন অঙ্কের
int()CPython-এ রৈখিক নয়, আর reference-এর আসল কোডে ৪,৩০০-এর বেশি অঙ্কে crash হয় (অংশ ৫)। অংশ ৭-এর মাপেও প্রতি অক্ষরে সময় প্রায় স্থির (৩২৯–৩৫২ ns), যা রৈখিক আচরণের সঙ্গে মেলে। - বাইরের loop-এর প্রতিটি ঘোরা একটি শাখা নেয়। শাখা ১ ও ২-এ
নিজেকে যাচাই করুন
ভুল হলে কারণসহ ব্যাখ্যা পাবেন, আবার চেষ্টাও করতে পারবেন।
ক্রমহাতে লেখা lexer একটি token বানাতে যে কাজগুলো করে, সঠিক ক্রমে সাজান (▲▼ চেপে সরান)
- বর্তমান অক্ষর
c = src[i]দেখা - ফাঁকা ঘর, newline বা comment হলে শুধু cursor সরিয়ে আবার শুরু
- শুরুর জায়গা মনে রাখা:
start = i - শাখা বেছে
iএগোনো আর kind ঠিক করা Token(kind, src[start:i], line, col)তালিকায় যোগ- কলাম বাড়ানো:
col += i - start
Haat-এর lexer a<=-b থেকে (EOF বাদে) কোন token-গুলো বানায়?
- IDENT, LT, EQ, MINUS, IDENT
- IDENT, LT_EQ, MINUS, IDENT
- IDENT, একটি তিন অক্ষরের operator, IDENT
- IDENT, LT_EQ, IDENT (-b একটি নাম)
Haat-এ let n: Int = 5; লাইনের Int শব্দটিকে lexer কোন kind দেয়?
- INT
- TYPE
- IDENT
- INT_KW, একটি keyword
এক লাইনের Haat source print("দাম: ৯৯৬); (শেষ কোট নেই)। Lexer-এর বার্তা কী?
- 1:7: error: unterminated string literal
- 1:18: error: unterminated string literal
- 1:16: error: unexpected character ')'
- 1:8: error: unexpected character 'দ'
Haat source let s = "চাল 🛒"; x-এ ;-এর কলাম কত? (Haat কলাম গোনে Unicode code point ধরে; 🛒 একটি code point কিন্তু UTF-16-এ দুটি unit.)
- 15
- 16
- 17
- 25
Haat-এর Int 64-bit, আর integer literal-এর মান 9223372036854775807-এর বেশি হলে lexical error. সবচেয়ে ছোট Int (−9223372036854775808) source-এ কীভাবে লেখা যায়?
- -9223372036854775808
- (-9223372036854775808)
- 0x8000000000000000
- -9223372036854775807 - 1
একটি Haat ফাইলের লাইন ২-এ let b = 2 @ 3; আর লাইন ৩-এ let c = 4 # 5;. Reference lexer কয়টি error বার্তা দেয়?
- একটি, শুধু
@-এর - দুটি,
@আর# - তিনটি, দুটি lexer-এর আর একটি parser-এর
- কোনোটি নয়, এগুলো উপেক্ষা হয়
একটি lexer প্রথমে keyword-গুলো মিলিয়ে দেখে (“লেখা কি if দিয়ে শুরু?”), তারপর নাম পড়ে। Haat source iffy = 1;-এ কী ভুল হবে?
- কিছুই না, iffy একটি IDENT হবে
- f-এ unexpected character error
- IF আর IDENT fy, দুটি token
- FALSE আর IDENT
শব্দকোষ
লেখার মধ্যে ডটেড দাগ দেওয়া শব্দে মাউস রাখুন বা চাপুন — অর্থ দেখাবে। এই পর্বের সব নতুন শব্দ এখানে একসাথে:
মনে রাখুন
- Haat-এর lexer একটি cursor
iআরline,colনিয়ে চলে; প্রতিটি tokenToken(kind, text, line, col), ৩৭ রকম kind, শেষে সবসময় EOF. - কলাম code point ধরে, ১ থেকে; token লাইন পার হয় না, তাই
col += i - startযথেষ্ট। - Maximal munch: দুই অক্ষরের operator আগে, শব্দ পুরোটা পড়ে তারপর keyword টেবিল;
Intএকটি IDENT. - চারটি lexical error, প্রথমটিতেই থামা; unterminated string খোলা কোটে, অজানা escape backslash-এ।
- Lexer O(n); বিশ্বাস আসে differential test আর চরম input থেকে, যা spec-এর ফাঁক আর আসল bug দুটিই খুঁজে দেয়।
আরও পড়ুন · ABCL TECH-এ আপনার পরবর্তী পদক্ষেপ
- পর্ব ৪৭ · Recursive descent parser — Haat-এর statementপরবর্তী পর্বএই পর্বের token থেকে Haat-এর statement আর declaration-এর AST.
- প্রোগ্রামিং ভাষা ও কম্পাইলার · কোর্স হোম৮৬টি পর্বপুরো কোর্সের মানচিত্র আর Haat প্রজেক্টের ধাপ।
- গণনার তত্ত্ব · পর্ব ২২ · Lexical analysisতত্ত্বRegex থেকে NFA আর DFA, maximal munch-এর তত্ত্ব, scanner algorithm.
- পর্ব ২১ · String আর Unicodeপেছনের পর্বCode point, UTF-8, UTF-16 আর বাংলা লেখার কলাম।
- Software Testing & QA · Fuzz testingপাশের ট্র্যাকএলোমেলো input দিয়ে bug খোঁজার পদ্ধতি, বিস্তারিত।