পাঠ ২০ · ৫৮-এর মধ্যে · মডিউল ৪
Home / Courses / Concepts of Programming Languages & Compiler Design / লেক্সার নির্মাণ

একটি লেক্সার বানানো

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

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

  • একটি লেক্সার ঠিক কোন তিনটি উপাদান একত্রিত করে (প্যাটার্ন, DFA-ভিত্তিক ম্যাচিং, স্ক্যানিং লুপ)
  • maximal munch + keyword-priority টাইব্রেক অ্যালগরিদম বাস্তবায়ন করা
  • "if x12 >= 5"-এর মতো একটি সোর্স স্নিপেট সম্পূর্ণ টোকেনাইজ করা
  • একটি প্রকৃত lexical-error কেস (অচেনা ক্যারেক্টার) সঠিকভাবে সনাক্ত ও রিপোর্ট করা

১ · একটি লেক্সারের তিনটি উপাদান

এই পাঠ M4-এর সব আগের পাঠের সিন্থেসিস। একটি বাস্তব লেক্সার (Lexer)সোর্স কোডের raw ক্যারেক্টার-স্ট্রিমকে টোকেন-স্ট্রিমে রূপান্তরকারী কম্পোনেন্ট — কম্পাইলার পাইপলাইনের প্রথম ধাপ (L01, L05)। তিনটি জিনিস একত্রিত করে —

১. টোকেন প্যাটার্ন
L17-এর regex দিয়ে সংজ্ঞায়িত — প্রতিটি টোকেন টাইপের (NUMBER, IDENTIFIER, KEYWORD, OPERATOR...) নিজস্ব প্যাটার্ন।
২. DFA-ভিত্তিক ম্যাচিং
L18-L19-এ প্রতিটি প্যাটার্নকে (আদর্শভাবে মিনিমাইজড) একটি DFA-তে রূপান্তর করা হয় — রানটাইমে দ্রুত ম্যাচিং।
৩. স্ক্যানিং লুপ
L16-এর maximal munch নীতি প্রয়োগ করে — প্রতি পজিশনে সব প্যাটার্ন একসাথে চালিয়ে সবচেয়ে লম্বা ম্যাচ বেছে নেওয়া।

২ · Longest-match + priority-tiebreak অ্যালগরিদম

প্রতিটি শুরুর পজিশনে, সব টোকেন-প্যাটার্ন একসাথে ট্রাই করা হয় — প্রতিটি প্যাটার্নের জন্য "এখান থেকে সর্বোচ্চ কতদূর ম্যাচ করা যায়" তা মাপা হয়। যে প্যাটার্ন সবচেয়ে লম্বা ম্যাচ দেয়, সেটাই জেতে। কিন্তু যদি একাধিক প্যাটার্ন সমান দৈর্ঘ্যে ম্যাচ করে (যেমন "if" IDENTIFIER প্যাটার্নেও মেলে, KEYWORD প্যাটার্নেও মেলে — দুটোই দৈর্ঘ্য ২), তখন একটি পূর্ব-নির্ধারিত প্রায়োরিটি অর্ডার টাই ভাঙে — এখানে KEYWORD সবসময় IDENTIFIER-এর উপরে।

Error handling — কেন জরুরি

যদি কোনো পজিশনে একটি প্যাটার্নও না মেলে (যেমন একটি অচেনা ক্যারেক্টার @), লেক্সারকে অবশ্যই একটি স্পষ্ট lexical error রিপোর্ট করতে হবে। চুপচাপ সেই ক্যারেক্টার এড়িয়ে যাওয়া (silently skip) বা সেখানে আটকে গিয়ে অসীম লুপে ঢুকে পড়া — দুটোই একটি বাস্তব কম্পাইলারের জন্য গ্রহণযোগ্য নয়।

পজিশন i থেকে স্ক্যান শুরু সব প্যাটার্নে ম্যাচ ট্রাই করুন (NUMBER, IDENTIFIER, KEYWORD, OPERATOR, WHITESPACE) সবচেয়ে দীর্ঘ ম্যাচ বাছুন (maximal munch) টাই হলে → KEYWORD অগ্রাধিকার পায় টোকেন এমিট করুন; i += দৈর্ঘ্য i < len(source) কোনো ম্যাচ নেই Lexical Error! রিপোর্ট করুন
প্রতিটি পজিশনে সব প্যাটার্ন একসাথে ট্রাই করা হয়; দীর্ঘতম ম্যাচ জেতে (টাইয়ে KEYWORD অগ্রাধিকার), আর কোনো প্যাটার্ন না মিললে সরাসরি একটি lexical error রিপোর্ট করা হয় — কখনো নিঃশব্দে এড়িয়ে যাওয়া হয় না।

৩ · সম্পূর্ণ Lexer বাস্তবায়ন

নিচের কোডে match_identifier, match_number, ও match_operator ফাংশনগুলো প্রতিটি নিজ নিজ DFA-র (L18-L19-এর মতো, এখানে সরাসরি সমতুল্য স্ক্যানিং-লুপ হিসেবে সরলীকৃত) আচরণ বাস্তবায়ন করে — প্রতিটি একটি নির্দিষ্ট পজিশন থেকে সর্বোচ্চ কতদূর ম্যাচ করা যায় তা রিটার্ন করে।

Python
KEYWORDS = {"if", "else", "while", "return"}

def match_identifier(s, i):
    if i >= len(s) or not (s[i].isalpha() or s[i] == '_'):
        return 0
    j = i
    while j < len(s) and (s[j].isalnum() or s[j] == '_'):
        j += 1
    return j - i

def match_number(s, i):
    if i >= len(s) or not s[i].isdigit():
        return 0
    j = i
    while j < len(s) and s[j].isdigit():
        j += 1
    return j - i

MULTI_OPS = [">=", "<=", "==", "!="]
SINGLE_OPS = set("+-*/()<>=,;")

def match_operator(s, i):
    for op in MULTI_OPS:
        if s.startswith(op, i):
            return len(op)
    if i < len(s) and s[i] in SINGLE_OPS:
        return 1
    return 0

def match_whitespace(s, i):
    j = i
    while j < len(s) and s[j] in " \t":
        j += 1
    return j - i

class LexError(Exception):
    pass

def tokenize(s):
    tokens = []
    i = 0
    while i < len(s):
        ws_len = match_whitespace(s, i)
        if ws_len > 0:
            i += ws_len
            continue

        candidates = []
        id_len = match_identifier(s, i)
        if id_len > 0:
            candidates.append(("IDENTIFIER", id_len))
        num_len = match_number(s, i)
        if num_len > 0:
            candidates.append(("NUMBER", num_len))
        op_len = match_operator(s, i)
        if op_len > 0:
            candidates.append(("OPERATOR", op_len))

        if not candidates:
            raise LexError(f"lexical error at position {i}: unrecognized character {s[i]!r}")

        # maximal munch: সবচেয়ে দীর্ঘ ম্যাচ বেছে নাও
        max_len = max(length for _, length in candidates)
        best = [kind for kind, length in candidates if length == max_len]
        kind = best[0]
        lexeme = s[i:i + max_len]

        # keyword priority: IDENTIFIER-এর সমান দৈর্ঘ্যে KEYWORD জিতবে
        if kind == "IDENTIFIER" and lexeme in KEYWORDS:
            kind = "KEYWORD"

        tokens.append((kind, lexeme))
        i += max_len
    return tokens

src = "if x12 >= 5"
print(f"tokenize({src!r}):")
for tok in tokenize(src):
    print(f"  {tok}")

bad_src = "if x12 @ 5"
print(f"\ntokenize({bad_src!r}) -- অচেনা ক্যারেক্টার '@' সহ:")
try:
    tokenize(bad_src)
    print("  ত্রুটি রিপোর্ট হয়নি -- এটি একটি বাগ হতো!")
except LexError as e:
    print(f"  সঠিকভাবে LexError রিপোর্ট হলো: {e}")

    
লক্ষ্য করুন প্রথম আউটপুটে "if" টোকেন KEYWORD হিসেবে চিহ্নিত হয়েছে, যদিও match_identifier("if x12 >= 5", 0) স্বাভাবিকভাবেই এটিকে IDENTIFIER হিসেবে ২ দৈর্ঘ্যে ম্যাচ করত — keyword-priority নিয়মটিই এই পার্থক্য তৈরি করেছে। আর দ্বিতীয় রানে "@"-এ পৌঁছে কোনো candidates না পাওয়ায় LexError ছোঁড়া হয়েছে, ঠিক যেমনটা হওয়া উচিত ছিল।
মূল কথা · Key takeaway

একটি লেক্সার আসলে খুব জটিল কিছু নয় — এটি L16-L19-এর ধারণাগুলোর (প্যাটার্ন, DFA, মিনিমাইজেশন) একটি প্রায়োগিক সিন্থেসিস, যেখানে মূল কৌশল দুটি সহজ নিয়মে ফুটে ওঠে: সবসময় সবচেয়ে লম্বা ম্যাচ নাও, এবং টাই ভাঙতে একটি স্থির প্রায়োরিটি ব্যবহার করো। M4 এখানেই শেষ — এখন থেকে বাকি কম্পাইলার পাইপলাইন (M5-এর পার্সিং, শুরু হচ্ছে পরের পাঠ থেকেই) raw টেক্সট নয়, এই টোকেন-স্ট্রিম নিয়েই কাজ করবে।

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

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

প্র ০১ যদি keyword-priority নিয়মটি না থাকত (অর্থাৎ IDENTIFIER ও KEYWORD-এর মধ্যে টাই হলে যেটা candidates তালিকায় আগে আসত সেটাই জিতত), তাহলে tokenize("if x12 >= 5")-এর আউটপুটে কী পার্থক্য হতো?

কোডে candidates তালিকায় IDENTIFIER সবসময় NUMBER ও OPERATOR-এর আগে চেক হয় — তাই "if" প্রথমে IDENTIFIER হিসেবে candidates-এ যোগ হতো, আর keyword-priority নিয়ম ছাড়া best[0] সরাসরি "IDENTIFIER" হয়ে যেত, কখনো "KEYWORD"-এ পরিণত হতো না। ফলাফল ভুল হতো — পরবর্তী পার্সিং ধাপ (M5) "if"-কে একটি সাধারণ ভেরিয়েবল নাম মনে করত, একটি নিয়ন্ত্রণ-প্রবাহ কীওয়ার্ড নয়, যা গ্রামারের ভুল ব্যাখ্যার দিকে নিয়ে যেত।

প্র ০২ match_operator-এ MULTI_OPS (">=", "<=" ইত্যাদি) কেন SINGLE_OPS চেক করার আগে চেক করা হয়েছে?

এটিও এক ধরনের maximal munch, কিন্তু প্যাটার্নদের মধ্যে নয়, একটিমাত্র OPERATOR প্যাটার্নের ভিতরেই। যদি একক-ক্যারেক্টার চেক আগে হতো, তাহলে ইনপুট ">="-এ প্রথমে শুধু ">" (দৈর্ঘ্য ১) ম্যাচ করে থেমে যেত, বাকি "=" আলাদা টোকেন হয়ে যেত — যা ভুল (">=" একটি একক তুলনা অপারেটর, দুটি আলাদা অপারেটর নয়)। মাল্টি-ক্যারেক্টার অপশন আগে ট্রাই করে আমরা নিশ্চিত করি এই ফাংশনটির নিজের ভিতরেই দীর্ঘতম সম্ভাব্য ম্যাচ অগ্রাধিকার পায়।

প্র ০৩ tokenize ফাংশনের while i < len(s) লুপে যদি কখনো i না বাড়ে (যেমন কোনো বাগের কারণে), তাহলে কী ঘটতে পারত — এবং কোডের কোন অংশ এই ঝুঁকি এড়ায়?

যদি i কখনো না বাড়ে, লুপ চিরকাল একই পজিশনে আটকে থেকে একটি অসীম লুপ তৈরি করবে — ব্রাউজার/প্রোগ্রাম হ্যাং হয়ে যাবে। কোডে এই ঝুঁকি এড়ানো হয়েছে if not candidates: raise LexError(...) লাইন দিয়ে — যদি কোনো প্যাটার্নই কিছু ম্যাচ না করে (দৈর্ঘ্য ০-এর বেশি কিছু না পেলে), লুপ চুপচাপ চালিয়ে যাওয়ার বদলে সাথে সাথে একটি এক্সেপশন ছুঁড়ে থেমে যায় — এটাই ঠিক কেন error-handling শুধু "ভালো অভ্যাস" নয়, বরং একটি লেক্সারের সঠিকতার জন্য কাঠামোগতভাবে প্রয়োজনীয়।

অনুশীলন

  1. হাতে করুন: tokenize("return total_sum") হাতে-কলমে ট্রেস করুন — কোন কোন টোকেন তৈরি হবে, এবং কোনটি keyword-priority নিয়মে KEYWORD হবে?

    আউটপুট: [("KEYWORD", "return"), ("IDENTIFIER", "total_sum")]। "return" প্রথমে IDENTIFIER প্যাটার্নে দৈর্ঘ্য ৬-এ ম্যাচ করে (এবং OPERATOR/NUMBER-এ একদম মেলে না), তারপর KEYWORDS সেটে থাকায় KEYWORD-এ রূপান্তরিত হয়। "total_sum" শুধু IDENTIFIER প্যাটার্নে মেলে (আন্ডারস্কোরসহ, দৈর্ঘ্য ৯) এবং KEYWORDS সেটে নেই বলে IDENTIFIER-ই থেকে যায় — L16-এর maximal munch-এর ঠিক সেই উদাহরণের পুনরাবৃত্তি।

  2. পরীক্ষা করুন: কোড সেলে bad_src-এর মান "x = 5 # comment" করে Run চাপুন — কোথায় ও কেন LexError আসবে?

    পজিশন ৬-এ (# ক্যারেক্টারে) LexError আসবে, কারণ # আমাদের কোনো প্যাটার্নেই (IDENTIFIER, NUMBER, OPERATOR, WHITESPACE) নেই — এই সরলীকৃত লেক্সার কমেন্ট সাপোর্ট করে না। বাস্তব লেক্সারে কমেন্ট নিজেই একটি প্যাটার্ন হিসেবে যোগ করতে হতো (যেমন # থেকে লাইনের শেষ পর্যন্ত সবকিছু স্কিপ করা), যা এই পাঠের পরিধির বাইরে ইচ্ছাকৃতভাবে সরলীকৃত রাখা হয়েছে।

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

আগের পাঠ
DFA মিনিমাইজেশন