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

Compiler-এর front end — Haat ভাষার পরিচয় আর নকশা

The Compiler Front End — Introducing and Specifying the Haat Language

Taught in Bangla, this lesson defines the compiler front end's contract: characters in, a checked AST or a list of line:col errors out, through lexer, parser, name resolution and type checker. It reads Haat's specification in six parts, including lexical grammar, EBNF syntax and a precedence table, weighs hand-written parsers against generators, runs a miniature front end on bazar.haat in in-page Python (Pyodide) matching the reference, and explains golden files, differential testing and round trips.

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

  • Front end-এর ইনপুট, আউটপুট আর ভুল জানানোর চুক্তি স্পষ্ট করে বলতে পারা, আর একটি Haat লাইনকে অক্ষর থেকে AST পর্যন্ত হাতে চালাতে পারা
  • একটি ভাষার spec কোন কোন ভাগে লেখা হয়, আর Haat-এর lexical grammar, EBNF আর precedence টেবিল পড়তে পারা
  • হাতে লেখা parser আর parser generator-এর আপস, বাস্তব compiler-এর উদাহরণসহ
  • মডিউল ৮ আর ৯-এ reference-এর কোন ফাইল কোন পর্বে বানাবেন, তার মানচিত্র
  • Front end পরীক্ষার কৌশল: golden file, differential testing, round trip, আর round trip থেকে একটি ছোট প্রমাণ

১ · Front end-এর কাজ — অক্ষর থেকে গাছ, সঙ্গে ভুলের তালিকা

জেলা শহরের একটি বড় ডাকঘরের বাছাই-কক্ষের কথা ভাবুন। বস্তা থেকে হাজার হাজার খাম বের হয়। একজন কর্মী প্রথমে খামের হাতের লেখা পড়ে শব্দ চেনেন: “বাড়ি ১২”, “রোড ৪”, “ধানমন্ডি”, “ঢাকা”। দ্বিতীয়জন দেখেন ঠিকানার গঠন ঠিক আছে কি না: আগে নাম, তারপর বাড়ি, তারপর এলাকা, শেষে জেলা। তৃতীয়জন মিলিয়ে দেখেন এলাকাটি সত্যিই ওই জেলায় আছে কি না। কোনো খামে গোলমাল পেলে সেটি আলাদা ঝুড়িতে যায়, সঙ্গে একটি চিরকুট: “তৃতীয় লাইনে জেলার নাম নেই”। সব ঠিক থাকলে তবেই খাম পৌঁছায় পাঠানোর কাউন্টারে।

শব্দ চেনা হলো lexer, গঠন বোঝা হলো parser, এলাকা আর জেলা মেলানো হলো semantic analysis. এই তিনজন মিলে compiler-এর front end. পাঠানোর কাউন্টার হলো back end বা interpreter: সে ধরে নেয়, যে খাম তার হাতে এসেছে, তার ঠিকানা ইতিমধ্যে যাচাই-করা। আর চিরকুটটি হলো compiler-এর diagnostic: কোথায় (line:col) আর কী ভুল।

পর্ব ০৫-এ (Compiler-এর ধাপগুলো) compiler-এর পুরো পথ ওপর থেকে দেখেছিলেন: front end ভাষা বোঝে, middle end IR নিয়ে optimize করে, back end যন্ত্র বোঝে। আর পর্ব ০১-এ একটি ছোট lexer আর Pratt parser এক ঝলক দেখেছিলেন। এই মডিউল থেকে আমরা সত্যিই বানানো শুরু করছি: Haat-এর পূর্ণ front end, ফাইল ধরে ধরে। আজকের পর্ব সেই কাজের নকশা-ঘর: কী বানাব, কোন নিয়মে, কোন ক্রমে, আর কীভাবে জানব যে ঠিক বানিয়েছি।

সংজ্ঞা ৪৫.১ — front end-এর চুক্তি

ধরুন Σ হলো Unicode অক্ষরের সেট, আর Σ* মানে Σ-এর অক্ষর দিয়ে বানানো যেকোনো দৈর্ঘ্যের লেখা। একটি front end হলো একটি function
F : Σ* → AST ∪ Err+,
যেখানে Err+ মানে এক বা একাধিক error-এর একটি তালিকা, আর প্রতিটি error একটি ত্রয়ী (line, col, message).

আমরা চাই তিনটি শর্ত: (১) নির্ধারিত: একই লেখায় সবসময় একই ফল। (২) অবস্থানসহ: প্রতিটি error-এর line আর col লেখার ভেতরের একটি আসল জায়গা দেখায়। (৩) সঠিক: F(s) একটি AST দেয় ঠিক তখনই, যখন s একটি বৈধ Haat program, অর্থাৎ ব্যাকরণ আর সব static নিয়ম মানে।

শর্ত (৩)-এর “বৈধ” কথাটির মানে কে ঠিক করে? সেটিই ভাষার specification, যা অংশ ২-এর বিষয়। আর এই কোর্সে front end-এর ভাগ দুটি মডিউলে: মডিউল ৮ বানায় syntax-এর অংশ (lexer, parser, AST, error recovery), মডিউল ৯ বানায় অর্থের অংশ (symbol table, name resolution, type checker).

এবার bazar.haat-এর লাইন ৪, if p >= 1000 { return p - p / 10; }, front end-এর ভেতর দিয়ে চালাই। প্রতিটি প্যানেলের লেখা Haat reference বাস্তবায়নের সত্যিকারের আউটপুট (CPython 3.14.4-এ, python -B haat.py tokens|ast|check); AST-এর অবস্থানগুলো reference-এর parse ফাংশনের ফল থেকে নেওয়া।

  1. অক্ষরsrccolumn গোনা
  2. Lexertokensশব্দ
  3. Parserstatementগঠন
  4. ASTIfগাছ
  5. Semanticcheckনাম, type
লাইন ৪প্রতিটি অক্ষরের column
    if p >= 1000 { return p - p / 10; }
1   5  8 10 13   18 20     27  31  35 39
       ↑ p     ↑ {           ↑ p
haat.py tokensলাইন ৪-এর ১৩টি token
4:5    IF       if
4:8    IDENT    p
4:10   GT_EQ    >=
4:13   INT      1000
4:18   LBRACE   {
4:20   RETURN   return
4:27   IDENT    p
4:29   MINUS    -
4:31   IDENT    p
4:33   SLASH    /
4:35   INT      10
4:37   SEMI     ;
4:39   RBRACE   }
parser.pystatement() দেখে IF
IF → if_stmt()
  cond  = expression()     p >= 1000
          থামে LBRACE-এ: এটি infix নয়
  then  = block(...)       { ... }
  else_ = None             ELSE নেই
Prattreturn-এর expression
p   -   p   /   10
    50      60          ← binding power

/ (60) বেশি শক্ত, তাই আগে বাঁধে:
(- p (/ p 10))
haat.py astঅবস্থানসহ
(if (>= p 1000)          If 4:5, >= 4:10
  (block                  Block 4:18
    (return               Return 4:20
      (- p (/ p 10)))))   - 4:29, / 4:33
haat.py checkপুরো bazar.haat
ok

resolver: p → 3:9-এর let p (price-এর local)
checker:  p : Int, 1000 : Int, শর্ত : Bool
          return-এর মান Int, price ফেরত দেয় Int
  1. অক্ষর। লাইনটি শুরু হয় চারটি ফাঁকা ঘর দিয়ে, তাই if-এর i আছে column 5-এ। Haat-এ column গোনা হয় অক্ষর (code point) ধরে, byte ধরে নয় (reference-এর spec decision 1). এই গোনাই পরে প্রতিটি error-এর ঠিকানা হবে।
  2. Lexer. ফাঁকা ঘর বাদ, শব্দগুলো token-এ ভাগ: ১৩টি। >= একটি token (GT_EQ), দুটি নয়, কারণ lexer সবসময় সবচেয়ে লম্বা মিল নেয় (maximal munch). if আর return keyword, কিন্তু p একটি IDENT.
  3. Parser, statement-এর স্তরে। প্রথম token IF, তাই parser if_stmt ডাকে: এটি recursive descent, ব্যাকরণের প্রতিটি নিয়মের জন্য একটি function. শর্তের expression থামে {-এ, কারণ { কোনো infix operator নয়। else নেই, তাই else-অংশ None.
  4. Parser, expression-এর স্তরে। p - p / 10-এ কোনটি আগে বাঁধবে? Pratt parsing-এ প্রতিটি operator-এর একটি binding power: --এর ৫০, /-এর ৬০. বেশি শক্তির / নিজের operand আগে নিয়ে নেয়, তাই গাছ (- p (/ p 10)).
  5. AST. বন্ধনী, ; আর ফাঁকা ঘর আর নেই; আছে শুধু অর্থ: একটি If, যার শর্ত একটি তুলনা আর then-অংশে একটি return. প্রতিটি node-এর সঙ্গে একটি অবস্থান: If 4:5-এ (keyword), Binary node তার operator-এ (4:10, 4:29, 4:33). এটিই abstract syntax tree.
  6. Semantic analysis. Syntax-এর কাজ শেষ, কিন্তু front end-এর নয়। p কোন ঘোষণা? লাইন ৩-এর let p (পর্ব ৫১-এ বানাবেন)। শর্তটি কি Bool? হ্যাঁ, কারণ দুই পাশে Int (পর্ব ৫২)। পুরো ফাইলে কোনো ভুল নেই, তাই check বলে ok. (ধূসর লাইনগুলো ব্যাখ্যা, CLI-র আউটপুট নয়।)

২ · Haat-এর spec — ভাষাকে কাগজে লেখা

একটি বাস্তবায়ন (implementation) লিখতে বসার আগে প্রশ্ন: “ঠিক” মানে কী? a < b < c কি বৈধ? Int কি keyword? -7 / 2 কত? এর উত্তর থাকে ভাষার specification-এ, সংক্ষেপে spec. রান্নার রেসিপি যেমন বলে কী কী উপকরণ, কোন ক্রমে আর কতক্ষণ, তেমনি spec বলে কোন লেখা program, আর program-টির অর্থ কী। Spec ছাড়া দুজন আলাদা বাস্তবায়ন লিখলে দুটি আলাদা ভাষা পাবেন, যদিও নাম একই।

Haat-এর spec দুই স্তরে। প্রথমটি কোর্সের নির্দিষ্ট “spec v1”, যা সব পর্ব মেনে চলে। দ্বিতীয়টি কেন্দ্রীয়ভাবে বানানো, ৩২টি পরীক্ষায় উত্তীর্ণ reference implementation-এর README-এর “Spec decisions” তালিকা: যেখানে v1 নীরব বা দ্ব্যর্থ, সেখানে ২৮টি সিদ্ধান্ত (C আর Rust-এর সবচেয়ে কাছের ব্যাখ্যা বেছে)। এই কোর্সে “decision 10” মানে সেই তালিকার ১০ নম্বর। একটি পূর্ণ spec-এ সাধারণত ছয়টি ভাগ থাকে।

২.১ Lexical grammar — কোন অক্ষর-গুচ্ছ কোন token

Lexical grammar বলে অক্ষরগুলো কীভাবে token-এ ভাগ হবে। Haat-এর token-এর মোট ৩৭টি শ্রেণি (kind):

শ্রেণিনিয়মখেয়াল রাখুন
INT[0-9]+চিহ্ন নেই; সর্বোচ্চ 9223372036854775807 (decision 3)
STRING"…", escape শুধু \" \\ \nকাঁচা newline চলে না (decision 5)
IDENT[A-Za-z_][A-Za-z0-9_]*শুধু ASCII (decision 4); Int একটি IDENT (decision 6)
১০টি keywordlet var fn if else while return true false printkind হলো শব্দটি বড় হাতে: WHILE
৭টি দুই-অক্ষরের== != <= >= && || ->এক-অক্ষরের আগে চেষ্টা (longest match)
১৬টি এক-অক্ষরের+ - * / % < > ! = ( ) { } , ; :একা & বা | অচেনা অক্ষর (decision 2)
EOF(খালি)ফাইলের শেষ চিহ্ন

Comment (// থেকে লাইনের শেষ) আর ফাঁকা ঘর কোনো token নয়; তাই বাংলা লেখা comment আর string-এর ভেতরে থাকতে পারে, নামের ভেতরে নয়। Token-এর তত্ত্ব, অর্থাৎ regular expression থেকে DFA আর maximal munch-এর প্রমাণ, গণনার তত্ত্ব কোর্সের পর্ব ২২-এ (Lexical analysis) আছে; এখানে আমরা শুধু ব্যবহার করব।

২.২ Syntax — EBNF-এ পুরো ব্যাকরণ

Token-এর পরের স্তর: কোন token-এর সারি একটি program. নিচে Haat-এর পুরো ব্যাকরণ EBNF-এ, reference-এর parser.py থেকে লেখা। { x } মানে x শূন্য বা বেশিবার, [ x ] মানে x থাকতেও পারে, না-ও পারে। বড় হাতের নাম (INT, IDENT) token, উদ্ধৃতির ভেতরে আক্ষরিক token.

program    = { statement } EOF ;
statement  = letDecl | fnDecl | ifStmt | whileStmt
           | returnStmt | printStmt | block | simpleStmt ;
letDecl    = ( "let" | "var" ) IDENT [ ":" type ] "=" expr ";" ;
fnDecl     = "fn" IDENT params [ "->" type ] block ;
params     = "(" [ param { "," param } ] ")" ;
param      = IDENT ":" type ;
ifStmt     = "if" expr block [ "else" ( ifStmt | block ) ] ;
whileStmt  = "while" expr block ;
returnStmt = "return" [ expr ] ";" ;
printStmt  = "print" "(" expr ")" ";" ;
block      = "{" { statement } "}" ;
simpleStmt = expr [ "=" expr ] ";" ;    (* "=" এর বাঁয়ে শুধু নাম *)
type       = IDENT
           | "(" [ type { "," type } ] ")" "->" type ;
expr       = andExpr { "||" andExpr } ;
andExpr    = eqExpr { "&&" eqExpr } ;
eqExpr     = relExpr [ ( "==" | "!=" ) relExpr ] ;
relExpr    = addExpr [ ( "<" | "<=" | ">" | ">=" ) addExpr ] ;
addExpr    = mulExpr { ( "+" | "-" ) mulExpr } ;
mulExpr    = unary { ( "*" | "/" | "%" ) unary } ;
unary      = ( "-" | "!" ) unary | postfix ;
postfix    = primary { "(" [ expr { "," expr } ] ")" } ;
primary    = INT | STRING | "true" | "false" | IDENT
           | "(" expr ")" | "fn" params [ "->" type ] block ;

তিনটি জায়গা ব্যাকরণের বাইরে থেকে আসা নিয়ম। (১) Statement fn দিয়ে শুরু হলে পরের token IDENT হলে fnDecl, নইলে একটি anonymous function-এর expression; parser একটি token আগে দেখে (lookahead) ঠিক করে। (২) simpleStmt-এ =-এর বাঁয়ে শুধু একটি নাম চলে, নইলে invalid assignment target (decision 9); ব্যাকরণ এটি সরাসরি বলে না, parser আলাদা করে দেখে। (৩) type-এর জায়গার IDENT শুধু Int Bool Str Unit হতে পারে, নইলে unknown type 'X' (decision 6). খেয়াল করুন eqExpr আর relExpr-এ { } নয়, [ ]: অর্থাৎ একটি স্তরে বড়জোর একটি তুলনা। এটিই decision 10-এর non-associative নিয়ম, ব্যাকরণে লেখা।

Reference-এর parser এই layered ব্যাকরণ ধরে লেখা নয়; সে statement-এ recursive descent আর expression-এ Pratt ব্যবহার করে। তাহলে দুটি কি সত্যিই একই ভাষা বোঝায়? ল্যাবে এই EBNF থেকে সরাসরি একটি ছোট recursive-descent recognizer লিখে reference-এর সঙ্গে মিলিয়েছি: seed 4545 দিয়ে বানানো ৩০০০টি এলোমেলো expression (দুই-তৃতীয়াংশ গঠনমূলক, এক-তৃতীয়াংশ token-এর এলোমেলো স্তূপ), যার ১৬৫৯টি reference গ্রহণ করে। ৩০০০টির সবকটিতে দুটি একই সিদ্ধান্ত দিয়েছে, আর গ্রহণ করা প্রতিটিতে একই গাছ। এটি প্রমাণ নয়, কিন্তু একটি শক্ত প্রমাণ-চিহ্ন। Grammar-এর তত্ত্ব আর precedence-স্তরে ভাগ করার কৌশল গণনার তত্ত্ব কোর্সের পর্ব ৪২-এ (grammar নকশা); দ্ব্যর্থতা পর্ব ২৭-এ।

২.৩ Precedence আর associativity — একটি টেবিল

স্তর (নিচু → উঁচু)Operatorlbp / rbpAssociativity
১||10 / 11বাঁ
২&&20 / 21বাঁ
৩== !=30 / 31non-associative
৪< <= > >=40 / 41non-associative
৫+ -50 / 51বাঁ
৬* / %60 / 61বাঁ
৭prefix - !— / 70(prefix)
৮call f(a, b)80 / —বাঁ: f(1)(2)

EBNF-এর আটটি expression-নিয়ম আর এই টেবিল একই তথ্য দুইভাবে বলে। Operator precedence বলে কোন operator আগে বাঁধবে, associativity বলে একই স্তরের দুটি পাশাপাশি থাকলে কোন দিক থেকে। Pratt parser টেবিলটি সরাসরি ব্যবহার করে (পর্ব ৪৮), আর পর্ব ২৬-এ (Expression আর evaluation order) এর মূল algorithm দেখেছিলেন।

২.৪ থেকে ২.৬ — static নিয়ম, চলার সময়ের অর্থ, error

ব্যাকরণ মানলেই program বৈধ নয়। Static নিয়ম (চালানোর আগে, compile time-এ যাচাই) Haat-এ এগুলো: প্রতিটি নাম ব্যবহারের আগে ঘোষিত, একই scope-এ দুবার নয় (decision 15), ঘোষণার আগে ব্যবহার নিষেধ, এমনকি নিজের initializer-এ (decision 16), শুধু top-level function hoisted (decision 17), শুধু var-এ assignment (decision 19), operand-এর type (decision 11), print একটি statement আর Unit ছাপে না (decision 8), প্রতিটি পথে return (decision 21). চলার সময়ের অর্থ (run time-এ): বাঁ থেকে ডানে মূল্যায়ন (decision 12), Int ৬৪ বিটে wrap করে (decision 13), / শূন্যের দিকে কাটে আর % dividend-এর চিহ্ন নেয়, যেমন C-তে। আর error-এর format: line:col: error: message, missing ; আগের token-এর ঠিক পরে (decision 24), lexer প্রথম ভুলেই থামে কিন্তু parser সব ভুল জানায় (decision 2), panic-mode-এ নিরাপদ জায়গায় লাফ (decision 25).

নিচের stepper-এ ছয়টি ভাগের প্রতিটির জন্য একটি করে প্রশ্ন, আর spec-এর কোন অংশ উত্তর দেয়। প্রতিটি উত্তর reference দিয়ে চালিয়ে পাওয়া।

1Lexical grammar2Syntax (EBNF)3Precedence table4Static rules5Dynamic semantics6Errors, positions
প্রশ্ন আর spec-এর উত্তর
Program
নিয়ম
  1. Lexical grammar. Int কি keyword? না: keyword-এর তালিকায় নেই, তাই এটি সাধারণ IDENT, আর একটি variable-এর নামও হতে পারে। শুধু type-এর জায়গায় এটি type বোঝায়। Program চলে আর 5 ছাপে। (মানুষের পড়ার জন্য ভালো নাম নয়, কিন্তু বৈধ।)
  2. Syntax. primary = "(" expr ")": খোলা বন্ধনী বন্ধ হতেই হবে। 2-এর পরে parser ) চায় কিন্তু পায় ; (column 15), আর error সেখানেই। এই ভুল ব্যাকরণের, তাই parser ধরে।
  3. Precedence টেবিল. < non-associative, তাই দ্বিতীয় <-এ (column 13) error. C-তে a < b < c বৈধ আর মানে (a < b) < c, যা প্রায়ই প্রোগ্রামারের উদ্দেশ্য নয়; Haat ইচ্ছা করে এটি নিষেধ করেছে।
  4. Static নিয়ম. ব্যাকরণে নিখুঁত, কিন্তু block-এর a ঘোষিত হচ্ছে, আর initializer-এ সেই a ব্যবহার। Decision 16 (JavaScript-এর let-এর মতো) এটিকে error বলে। এটি ধরে resolver, অর্থাৎ মডিউল ৯-এর কাজ।
  5. চলার সময়ের অর্থ. −7 / 2-এর গাণিতিক মান −3.5; Haat শূন্যের দিকে কেটে −3 দেয়, আর −7 % 2 = −1 (ভাগশেষ dividend-এর চিহ্ন নেয়)। Python 3-এ একই হিসাব দেয় −4 আর 1: একই লেখা, ভিন্ন ভাষা, ভিন্ন অর্থ। -7 কোনো literal নয়, unary - আর 7.
  6. Error আর অবস্থান. ; নেই লাইন ১-এ, কিন্তু parser সেটি টের পায় লাইন ২-এর print দেখে। তবু error দেখায় 1:15, অর্থাৎ 10-এর ঠিক পরে, কারণ decision 24 বলে missing ; আগের token-এর শেষে জানাতে হবে, gcc আর rustc-এর মতো।

Spec লেখা মানে সিদ্ধান্ত নেওয়া। উপরের ছয়টির প্রতিটির অন্য উত্তরও যুক্তিসংগত হতো: Rust একই scope-এ নাম আবার ঘোষণা করতে দেয়, Python a < b < c-কে a < b and b < c হিসেবে পড়ে। ভুল হলো সিদ্ধান্ত না নেওয়া: তখন প্রতিটি বাস্তবায়ন নিজের মতো বেছে নেয়। Reference-এর README-তে “Suggested clarifications for spec v2” নামে একটি তালিকা আছে, যেখানে এমন দশটি বিষয় (decision 3, 8, 10, 11, 14–19 আর 21) চিহ্নিত, যা spec-এর লেখাতেই থাকা উচিত।

৩ · Front end-এর মানচিত্র — reference-এর ফাইল আর এই মডিউলের পরিকল্পনা

Spec হাতে; এবার বাস্তবায়নের নকশা। Haat reference-এর front end ছয়টি ফাইলে: tokens.py (২৮ লাইন), lexer.py (৮৬), errors.py (২১), ast_nodes.py (১৮৭), parser.py (২৭৮) আর ast_print.py (১৫১); তারপর semantic অংশে resolver.py (১৭৭) আর typechecker.py (১৬৪)। নিচের ছবি ডেটা আর ভুলের পথ দেখায়।

ছবি ৪৫.১ — Haat-এর front end: ডেটার পথ আর ভুলের পথ

বাঁয়ে ফাইল (ধাপ), মাঝে তীরের পাশে ডেটা, ডানে লাল লেখায় কোন ধাপ কয়টি ভুল জানায়।

Haat front end: data path and error path মডিউল ৮ মডিউল ৯ অক্ষরের সারি (.haat) lexer.py পর্ব ৪৬ parser.py পর্ব ৪৭, ৪৮, ৫০ resolver.py পর্ব ৫১ typechecker.py পর্ব ৫২, ৫৪ Token-এর তালিকা AST (ast_nodes.py) AST + Bindings যাচাই-করা AST interpreter (৫৬) বা bytecode compiler (৫৮) প্রথম ভুলেই থামে সব ভুল, recovery-সহ সব ভুল সব ভুল (sorted)
ছবি ৪৫.১ — একটি ধাপ কোনো ভুল পেলে পরের ধাপ আর চলে না (decision 2). যেমন let x = ;, print(1 +); আর let y = 2 (; ছাড়া) তিন লাইনের ফাইলে reference এক run-এ তিনটি parser error দেয়: 1:9, 2:10 আর 3:10.

কেন lexer প্রথম ভুলেই থামে, কিন্তু parser সব ভুল জানায়? Lexical ভুল সাধারণত বিরল আর স্থানীয় (একটি @), আর পরের অক্ষরগুলো কীভাবে ভাগ হবে তা প্রায়ই ভুলের ওপর নির্ভর করে: শেষ না হওয়া একটি string পুরো বাকি ফাইল গিলে ফেলে। Parser-এর ভুল বেশি, আর একটি নিরাপদ জায়গা (; বা }) খুঁজে আবার শুরু করা সহজ: একে বলে panic mode recovery (পর্ব ৫০)। Resolver আর checker একটি সম্পূর্ণ গাছ পায়, তাই তারা প্রতিটি ভুলের পরেও এগোতে পারে।

এখান থেকে পরের দুই মডিউলের কাজের ভাগ। প্রতিটি পর্ব reference-এর একটি অংশ নিজে হাতে বানায়, একই নাম আর একই আউটপুট রেখে:

পর্বযা বানাবেনReference-এর ফাইলমিলিয়ে দেখার কমান্ড
৪৬ · হাতে লেখা lexerToken, position, string, errortokens.py, lexer.pyhaat.py tokens
৪৭ · Recursive descent parserstatement, block, typeparser.py (প্রথম ভাগ)haat.py ast
৪৮ · Pratt parsingসব expressionparser.py (expression)haat.py ast
৪৯ · AST নকশাnode, visitor, pretty printerast_nodes.py, ast_print.pyhaat.py fmt
৫০ · Error recoverypanic mode, diagnosticerrors.py, parser.pyhaat.py check
৫১ · Symbol tablescope, binding, slotresolver.pyhaat.py check
৫২ · Type checkertype নিয়ম কোডেtypechecker.pyhaat.py check
৫৩–৫৫attribute grammar, অন্য check, desugaringtypechecker.py (missing return)haat.py check

৪ · হাতে লেখা parser, না parser generator?

একটি ব্যাকরণ হাতে থাকলে দুটি পথ। এক, একটি parser generator (yacc, Bison, ANTLR, Lark) ব্যাকরণ পড়ে parser বানিয়ে দেবে। দুই, নিজে হাতে parser লিখবেন: প্রতিটি নিয়মের জন্য একটি function. Compiler-এর বই সাধারণত প্রথমটি বেশি শেখায়, কিন্তু বাস্তবের বড় compiler-গুলো বেশিরভাগ দ্বিতীয় পথে চলে।

হাতে লেখা (recursive descent + Pratt)

Error message আর recovery-র ওপর পুরো নিয়ন্ত্রণ; কোন token প্রত্যাশিত ছিল, তা কোডের প্রতিটি জায়গায় জানা। Context-নির্ভর জায়গা (যেমন C-র typedef নাম) সহজে সামলানো যায়। Debugger-এ পড়া যায়, বাড়তি tool লাগে না। দাম: ব্যাকরণ-এর conflict কেউ আপনাআপনি ধরিয়ে দেয় না।

Clang, GCC, Go, rustc, V8, Haat

Parser generator

ব্যাকরণই spec, আর tool দ্ব্যর্থতা বা conflict জানায়। নতুন ভাষার প্রথম খসড়া খুব দ্রুত। দাম: ভালো error message বানানো কঠিন, build-এ বাড়তি ধাপ, আর generated কোড পড়া কষ্টের।

CPython (নিজের PEG generator), অনেক DSL আর SQL বাস্তবায়ন

ইতিহাস এই প্রবণতা দেখায়। GCC-র C++ parser একসময় yacc-ভিত্তিক ছিল; GCC 3.4 (২০০৪)-এ সেটি হাতে লেখা recursive descent parser-এ বদলায়, আর পরে C parser-ও (GCC 4.1-এর সময়, প্রায় ২০০৬)। Clang শুরু থেকেই হাতে লেখা। Go-র compiler-এর parser yacc থেকে তৈরি হতো; Go 1.6 (২০১৬)-এর release notes বলে, parser এখন yacc-এর বদলে হাতে লেখা। rustc আর V8-এর JavaScript parser-ও হাতে লেখা recursive descent. উল্টো দিকে, CPython 3.9 (PEP 617) পুরোনো LL(1) parser ছেড়ে একটি PEG parser নিয়েছে, যা Python-এর নিজের ব্যাকরণ ফাইল থেকে নিজের generator (pegen) দিয়ে তৈরি হয়। অর্থাৎ “generator খারাপ” নয়: CPython-এর দল generator-টিও নিজে লিখেছে, যাতে error আর কাঠামোর ওপর নিয়ন্ত্রণ থাকে।

Haat-এর ব্যাকরণ ছোট আর LL-ধরনের: প্রতিটি statement-এর প্রথম token বলে দেয় কোন নিয়ম। তাই হাতে লেখা recursive descent এখানে স্বাভাবিক। Generator দিয়ে একই কাজ (Lark, ANTLR, PLY-এর সত্যিকারের run) দেখতে চাইলে গণনার তত্ত্ব কোর্সের পর্ব ৪০ (parser generator) দেখুন; LL(1) টেবিলের তত্ত্ব পর্ব ৩৮-এ।

আরও গভীরে: “হাতে লেখা parser”-ও প্রায়ই খাঁটি recursive descent নয়। V8 প্রথমে একটি দ্রুত “pre-parser” দিয়ে function-এর ভেতরটা শুধু ভাসা-ভাসা পড়ে, আর পুরো parse করে তখনই, যখন function-টি সত্যিই ডাকা হয় (lazy parsing), কারণ ওয়েব পাতার বেশিরভাগ JavaScript কখনো চলেই না। Ruby দীর্ঘদিন একটি Bison ব্যাকরণ (parse.y) ব্যবহার করত; Ruby 3.4 (২০২৪)-এ হাতে লেখা Prism parser default হয়েছে বলে release notes জানায়। আবার Roslyn (C#) আর rust-analyzer-এর মতো tool সম্পূর্ণ lossless গাছ রাখে, যাতে প্রতিটি ফাঁকা ঘর আর comment-ও থাকে, কারণ editor-এর জন্য লেখাটি হুবহু ফিরিয়ে দিতে হয় (পর্ব ৮০-এ আসবে)।

৫ · ব্রাউজারে একটি ছোট Haat front end

এবার নিজে চালিয়ে দেখুন। নিচের চারটি block মিলে একটি front end, যা bazar.haat পুরোটা পড়তে পারে। প্রতিটি block আগেরটির নাম ব্যবহার করে (আগেরটি না চালালে নিজে থেকেই আগে চলবে)। নামগুলো reference-এর মতোই: Token(kind, text, line, col), UPPER_CASE token kind, আর AST-এর class ও field-এর নাম ast_nodes.py-এর হুবহু। এটি ইচ্ছা করে ছোট: string literal, anonymous function আর function type নেই, আর প্রথম ভুলেই থামে; পর্ব ৪৬–৫০ এগুলো পূর্ণ করবে। প্রথম block: token আর node-এর data type, আর lexer (reference-এর tokens.py আর lexer.py-এর ছোট রূপ)।

from dataclasses import make_dataclass
class HaatError(Exception): pass
Token = make_dataclass("Token", ["kind", "text", "line", "col"], frozen=True)
for spec in ("Num value|Bool value|Var name|Unary op operand|Binary op left right|Call callee args|"
             "Param name type|Let name mutable type init|Assign name value|If cond then else_|While cond "
             "body|Return value|Print value|ExprStmt expr|Block stmts|FnDecl name params ret body").split("|"):
    name, *fields = spec.split(); globals()[name] = make_dataclass(name, fields + ["line", "col"])
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 = dict(zip("+-*/%<>!=(){},;:", "PLUS MINUS STAR SLASH PERCENT LT GT BANG "
                    "EQ LPAREN RPAREN LBRACE RBRACE COMMA SEMI COLON".split()))
word = lambda c: c == "_" or c.isascii() and c.isalnum()     # ASCII letters, digits, _
def tokenize(src):
    toks, i, line, col = [], 0, 1, 1
    while i < len(src):
        c, start = src[i], i
        if c == "\n": 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: skip to end of line
            while i < len(src) and src[i] != "\n": i += 1
            continue
        if word(c) and not c.isdigit():                      # identifier or keyword
            while i < len(src) and word(src[i]): i += 1
            kind = KEYWORDS.get(src[start:i], "IDENT")
        elif c.isascii() and c.isdigit():                    # integer literal
            while i < len(src) and src[i].isascii() and src[i].isdigit(): i += 1
            if int(src[start:i]) > 2**63 - 1: raise HaatError(f"{line}:{col}: error: integer literal too large")
            kind = "INT"
        elif src[i:i + 2] in TWO_CHAR: kind, i = TWO_CHAR[src[i:i + 2]], i + 2   # longest match first
        elif c in ONE_CHAR: kind, i = ONE_CHAR[c], i + 1
        else: raise HaatError(f"{line}:{col}: error: unexpected character '{c}'")
        toks.append(Token(kind, src[start:i], line, col)); col += i - start
    return toks + [Token("EOF", "", line, col)]
print(*tokenize("if p >= 1000 { return p - p / 10; }")[:6], sep="\n")

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

Token(kind='IF', text='if', line=1, col=1)
Token(kind='IDENT', text='p', line=1, col=4)
Token(kind='GT_EQ', text='>=', line=1, col=6)
Token(kind='INT', text='1000', line=1, col=9)
Token(kind='LBRACE', text='{', line=1, col=14)
Token(kind='RETURN', text='return', line=1, col=16)

এখানে লাইনটি সামনের চার ফাঁকা ঘর ছাড়া দেওয়া, তাই if column 1-এ (bazar-এর ভেতরে ছিল 4:5). >= একটি token, কারণ TWO_CHAR টেবিল এক-অক্ষরেরটির আগে দেখা হয়। Lexer-এর মূল যুক্তি একটি loop: প্রতিবার একটি অক্ষর দেখে ঠিক করে কোন শাখায় যাবে, আর col এগোয় token-এর দৈর্ঘ্য যত। AST-এর ১৬টি class এখানে make_dataclass দিয়ে এক loop-এ তৈরি; reference সেগুলো আলাদা আলাদা @dataclass হিসেবে লেখে, কিন্তু নাম আর field একই, তাই repr-ও একই দেখায়।

দ্বিতীয় block: parser-এর কাঠামো আর expression. BP হলো অংশ ২.৩-এর টেবিল; expression একটি Pratt loop, যা call-কে postfix হিসেবে আর তুলনাকে non-associative হিসেবে সামলায়। এটি reference-এর parser.py-এর expression, prefix আর call-এর ছোট রূপ।

BP = {"OR_OR": 10, "AND_AND": 20, "EQ_EQ": 30, "BANG_EQ": 30, "LT": 40, "LT_EQ": 40, "GT": 40,
      "GT_EQ": 40, "PLUS": 50, "MINUS": 50, "STAR": 60, "SLASH": 60, "PERCENT": 60}
class Parser:
    def __init__(p, toks): p.toks, p.pos = toks, 0
    def peek(p, kind=None): return p.toks[p.pos] if kind is None else p.toks[p.pos].kind == kind
    def advance(p): t = p.toks[p.pos]; p.pos += t.kind != "EOF"; return t
    def expect(p, kind, msg):                       # a missing ';' is reported just after prev
        if p.peek(kind): return p.advance()
        t, c = (p.toks[p.pos - 1], len(p.toks[p.pos - 1].text)) if kind == "SEMI" else (p.peek(), 0)
        raise HaatError(f"{t.line}:{t.col + c}: error: {msg}")
    def items(p, item, msg):                        # [item {"," item}] ")"
        out = [] if p.peek("RPAREN") else [item()]
        while p.peek("COMMA"): p.advance(); out.append(item())
        p.expect("RPAREN", msg); return out
    def expression(p, min_bp=0):                    # Pratt parsing with the BP table
        left, last = p.prefix(), None
        while p.peek("LPAREN") or BP.get(p.peek().kind, -1) >= min_bp:
            t = p.advance()
            if t.kind == "LPAREN":                  # call f(a, b): postfix, bp 80, always binds
                args, s = p.items(p.expression, "expected ')' after arguments"), left
                while isinstance(s, Binary): s = s.left
                left = Call(left, args, s.line, s.col)
            elif BP[t.kind] in (30, 40) and last == BP[t.kind]:
                raise HaatError(f"{t.line}:{t.col}: error: comparison operators cannot be chained")
            else: last = BP[t.kind]; left = Binary(t.text, left, p.expression(last + 1), t.line, t.col)
        return left
    def prefix(p):
        t = p.advance(); k = t.kind
        if k == "INT": return Num(int(t.text), t.line, t.col)
        if k == "IDENT": return Var(t.text, t.line, t.col)
        if k in ("TRUE", "FALSE"): return Bool(k == "TRUE", t.line, t.col)
        if k in ("MINUS", "BANG"): return Unary(t.text, p.expression(70), t.line, t.col)
        if k == "LPAREN": e = p.expression(); p.expect("RPAREN", "expected ')' after expression"); return e
        raise HaatError(f"{t.line}:{t.col}: error: expected expression")
print(Parser(tokenize("qty * unit - p / 10")).expression())

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

Binary(op='-', left=Binary(op='*', left=Var(name='qty', line=1, col=1), right=Var(name='unit', line=1, col=7), line=1, col=5), right=Binary(op='/', left=Var(name='p', line=1, col=14), right=Num(value=10, line=1, col=18), line=1, col=16), line=1, col=12)

লম্বা, কিন্তু পড়ুন বাইরে থেকে ভেতরে: বাইরের node - (column 12), তার বাঁয়ে qty * unit, ডানে p / 10. অর্থাৎ (- (* qty unit) (/ p 10)). * আর / (৬০) --এর (৫০) চেয়ে শক্ত বলে আগে বেঁধেছে। ল্যাবে reference-এর parse দিয়ে একই লেখা পড়ে তার repr নিয়েছি: অক্ষরে অক্ষরে একই। খেয়াল করুন expect: ; না পেলে error-এর column আগের token-এর শেষে (decision 24), অন্য ক্ষেত্রে বর্তমান token-এ।

তৃতীয় block: statement, recursive descent-এ। প্রতিটি if k == … শাখা অংশ ২.২-এর একটি EBNF নিয়ম। নতুন class আগের Parser-কে বাড়ায় (inheritance), তাই আগের সব method থেকে যায়। এটি reference-এর parser.py-এর statement, let_decl, fn_decl, if_stmt আর expr_or_assign-এর ছোট রূপ।

class Parser(Parser):                               # add statements (recursive descent)
    def statement(p):
        t = p.peek(); k = t.kind
        if k in ("LET", "VAR", "FN", "IF", "WHILE", "RETURN", "PRINT"): p.advance()
        if k in ("LET", "VAR"):
            n = p.expect("IDENT", f"expected variable name after '{t.text}'")
            ann = p.advance() and p.expect("IDENT", "expected a type").text if p.peek("COLON") else None
            p.expect("EQ", f"expected '=' after variable name in '{t.text}'"); init = p.expression()
            p.expect("SEMI", "expected ';' after variable declaration")
            return Let(n.text, k == "VAR", ann, init, n.line, n.col)
        if k == "FN":
            n = p.advance(); p.expect("LPAREN", "expected '(' after function name")
            ps = p.items(p.param, "expected ')' after parameters")
            ret = p.advance() and p.expect("IDENT", "expected a type").text if p.peek("ARROW") else "Unit"
            return FnDecl(n.text, ps, ret, p.block("expected '{' before function body"), n.line, n.col)
        if k in ("IF", "WHILE"):
            cond, body = p.expression(), p.block(f"expected '{{' after {t.text} condition")
            if k == "WHILE": return While(cond, body, t.line, t.col)
            alt = p.peek("ELSE") and p.advance() and (
                p.statement() if p.peek("IF") else p.block("expected '{' or 'if' after 'else'"))
            return If(cond, body, alt or None, t.line, t.col)
        if k == "PRINT":
            p.expect("LPAREN", "expected '(' after 'print'"); v = p.expression()
            p.expect("RPAREN", "expected ')' after print argument")
            p.expect("SEMI", "expected ';' after print statement"); return Print(v, t.line, t.col)
        if k == "RETURN":
            v = None if p.peek("SEMI") else p.expression()
            p.expect("SEMI", "expected ';' after return"); return Return(v, t.line, t.col)
        if k == "LBRACE": return p.block("expected '{'")
        e = p.expression()
        if not p.peek("EQ"): p.expect("SEMI", "expected ';' after expression"); return ExprStmt(e, t.line, t.col)
        if not isinstance(e, Var): raise HaatError(f"{p.peek().line}:{p.peek().col}: error: invalid assignment target")
        p.advance(); v = p.expression(); p.expect("SEMI", "expected ';' after assignment"); return Assign(e.name, v, e.line, e.col)
print(Parser(tokenize("let p = qty * unit;")).statement())

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

Let(name='p', mutable=False, type=None, init=Binary(op='*', left=Var(name='qty', line=1, col=9), right=Var(name='unit', line=1, col=15), line=1, col=13), line=1, col=5)

let p = qty * unit; একটি Let node: mutable=False কারণ let (var হলে True), type=None কারণ কোনো type লেখা নেই, আর অবস্থান 1:5, নামটির জায়গা, keyword-এর নয়। reference-এর repr-এর সঙ্গে হুবহু। block আর param এখনো লেখা হয়নি; তাই fn বা if এখানে চালালে AttributeError হবে। Python এই method-গুলো খোঁজে ডাকার মুহূর্তে, তাই পরের block-এ যোগ করলেই চলবে।

চতুর্থ block: পুরো bazar.haat, শেষ দুটি method, আর একটি walk, যা গাছের প্রতিটি node একবার করে দেখে গুনে দেয়।

from collections import Counter; from dataclasses import fields, is_dataclass
SRC = """// বাজারঘর: অর্ডারের মোট দাম
fn price(qty: Int, unit: Int) -> Int {
    let p = qty * unit;
    if p >= 1000 { return p - p / 10; }
    return p;
}
fn delivery(total: Int) -> Int {
    if total >= 1000 { return 0; } else { return 60; }
}
let first = price(2, 520) + delivery(price(2, 520));
print(first);
var total = 0;
var rounds = 0;
while total < 5000 { total = total + 1250; rounds = rounds + 1; }
print(total);
print(rounds - 1);
"""
class Parser(Parser):
    def param(p):
        n = p.expect("IDENT", "expected parameter name")
        p.expect("COLON", f"expected ':' and a type after parameter '{n.text}'")
        return Param(n.text, p.expect("IDENT", "expected a type").text, n.line, n.col)
    def block(p, msg):
        lb, out = p.expect("LBRACE", msg), []
        while not p.peek("RBRACE") and not p.peek("EOF"): out.append(p.statement())
        p.expect("RBRACE", "expected '}' at end of block"); return Block(out, lb.line, lb.col)
def walk(n):                                        # every AST node, depth-first (pre-order)
    if isinstance(n, list): return [x for m in n for x in walk(m)]
    return [n] + [x for f in fields(n) for x in walk(getattr(n, f.name))] if is_dataclass(n) else []
toks = tokenize(SRC); p = Parser(toks); stmts = []
while not p.peek("EOF"): stmts.append(p.statement())
kinds = Counter(type(n).__name__ for n in walk(stmts))
print(len(toks), "tokens,", len(stmts), "top-level statements,", sum(kinds.values()), "nodes")
print(dict(kinds.most_common()))

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

130 tokens, 9 top-level statements, 71 nodes
{'Var': 16, 'Num': 15, 'Binary': 10, 'Block': 6, 'Let': 4, 'Return': 4, 'Param': 3, 'Call': 3, 'Print': 3, 'FnDecl': 2, 'If': 2, 'Assign': 2, 'While': 1}

১৩০টি token, EOF-সহ: haat.py tokens examples/bazar.haat-ও ঠিক ১৩০ লাইন ছাপে। ৯টি top-level statement: দুটি fn, একটি let, দুটি var, একটি while আর তিনটি print. ৭১টি node: এখানে Program বাদ, আর type annotation (Int) গোনা হয়নি, কারণ এই ছোট front end-এ type শুধু একটি লেখা ("Int"), reference-এর মতো TypeName node নয়। ৪৭৭ byte-এর একটি ফাইল (৪৩৫টি অক্ষর; বাংলা comment-এর প্রতিটি অক্ষর UTF-8-এ ৩ byte) থেকে ১৩০টি token, তা থেকে ৭১টি node: প্রতিটি ধাপ তথ্য ঘন করে।

এই চারটি block আর reference কি সত্যিই একই কাজ করে? ল্যাবে একটি differential test চালিয়েছি (CPython 3.14.4): দুটিকে একই ইনপুট দিয়ে token-এর তালিকা (kind, text, line, col) আর পুরো AST (প্রতিটি node-এর line আর col-সহ) মিলিয়েছি। ফল:

~/haat/fe $ python -B difftest.py
bazar.haat           same=True  mine_err=None
counter.haat         same=False  mine_err=2:31: error: expected a type
err_names.haat       same=True  mine_err=None
err_syntax.haat      same=True  mine_err=2:15: error: expected ';' after variable declaration
mutual.haat          same=True  mine_err=None
recursion.haat       same=True  mine_err=None
strings.haat         same=False  mine_err=2:12: error: unexpected character '"'
… (১৩টির মধ্যে ৮টিতে অমিল: string, fn type বা lambda আছে)
random programs: 600, same=600, valid(ref parses)=363
mutants: 400, same first error/AST=398, ref reports an error in 369

reference-এর ১৩টি উদাহরণের পাঁচটিতে হুবহু মিল; বাকি আটটিতে string, function type বা anonymous function আছে, যা এই ছোট front end জানে না, আর সে নিজেই সেটি error দিয়ে জানায়। তারপর একটি seed দেওয়া generator দিয়ে বানানো ৬০০টি এলোমেলো program (যার ৩৬৩টি বৈধ, বাকিগুলোতে জোড়া তুলনা বা ভুল assignment-এর মতো syntax ভুল): ৬০০টিতেই একই token, একই গাছ বা একই প্রথম error. শেষে ৪০০টি program থেকে একটি করে token মুছে বানানো ভাঙা program (mutant): ৩৯৮টিতে মিল। বাকি দুটিতে fn-এর পরে নাম মুছে গিয়েছিল; reference তখন fn(-কে একটি anonymous function হিসেবে পড়ে, আর এই ছোট parser তা জানে না। এই পরীক্ষাকে বলে differential testing, আর এলোমেলো ব্যাকরণ-মানা ইনপুট বানানোকে grammar-based fuzzing.

৬ · Front end কীভাবে পরীক্ষা করবেন — golden file, differential আর round trip

Front end-এর ভুল সবচেয়ে বিপজ্জনক, কারণ পরের সব ধাপ তার ওপর বিশ্বাস করে। একটি ভুল associativity হলে 10 - 4 - 3-এর মান 3-এর বদলে 9 হবে, আর কোনো error ছাড়াই। তাই reference আর এই কোর্সের প্রতিটি পর্ব তিন ধরনের পরীক্ষা ব্যবহার করে।

Golden file

প্রতিটি উদাহরণের পাশে একটি .out ফাইল, যেখানে প্রত্যাশিত পুরো আউটপুট, error-সহ। একে বলে golden file. পরীক্ষা মানে চালিয়ে হুবহু মেলানো, এক অক্ষর আলাদা হলেও ব্যর্থ। সত্যিকারের run:

~/haat/_haat_ref $ python -B -m unittest discover -s tests
................................
----------------------------------------------------------------------
Ran 32 tests in 0.681s

OK
~/haat/fe $ python -B golden.py
bazar.haat           3 lines  run=ok  vm=ok
err_syntax.haat      4 lines  run=ok  vm=ok
strings.haat         7 lines  run=ok  vm=ok
… (১৩টি উদাহরণ)
13/13 examples match their golden file in both back ends

err_syntax.haat-এর golden file-এ চারটি error, তাই এটি error message আর panic-mode recovery-ও পাহারা দেয়। Golden file-এর বিপদ একটি: কেউ ভুল আউটপুট দেখে না বুঝে “নতুন golden” হিসেবে সেভ করলে পরীক্ষা তখন ভুলকেই রক্ষা করে। তাই golden file বদলানোর আগে diff পড়ে দেখুন। (এই ধরনের পরীক্ষা নিয়ে বিস্তারিত Software Testing & QA কোর্সের পর্ব ৬১-এ।)

Differential testing

অংশ ৫-এ দেখেছেন: দুটি স্বাধীন বাস্তবায়ন, একই ইনপুট, ফল মেলানো। Reference নিজেও এটি করে: tree-walking interpreter আর bytecode VM প্রতিটি উদাহরণে একই আউটপুট দেয় কি না, আর ৪০০টি এলোমেলো expression দুই back end-এ আর একটি স্বাধীন Python হিসাবের সঙ্গে মেলে কি না। এর জোর হলো “সঠিক উত্তর” আগে থেকে জানতে হয় না; অমিলই সংকেত। দুর্বলতা: দুটি বাস্তবায়ন একই ভুল করলে (যেমন দুজনেই spec ভুল পড়লেন) ধরা পড়ে না।

Round trip

Parser-এর একটি বিপরীত আছে: pretty-printer, যা গাছ থেকে আবার source লেখে। Reference-এর haat.py fmt এটি করে, সবচেয়ে কম বন্ধনী দিয়ে। একটি সুন্দর পরীক্ষা: parse করুন, ছাপুন, আবার parse করুন; গাছ একই থাকতে হবে। একে বলে round-trip test. এটি একসঙ্গে parser আর printer দুটিকে পরীক্ষা করে, আর কোনো golden file লাগে না, তাই হাজার হাজার এলোমেলো গাছে চালানো যায় (property-based testing; পর্ব ৪৯-এ বানাবেন)।

1src = read("rt.haat")2t1  = parse(src)3out = fmt(t1)4t2  = parse(out)5assert t2 == t16assert fmt(t2) == out
অবস্থা
লেখা
AST
  1. Source. একজন অতিরিক্ত সাবধানী প্রোগ্রামার বন্ধনী দিয়েছেন, যা আসলে লাগে না। EOF-সহ ১৬টি token.
  2. Parse. গাছে বন্ধনী নেই, আছে শুধু গঠন: বাইরে -, দুই পাশে * আর /.
  3. fmt. Printer প্রতিটি operand-এর স্তর দেখে বন্ধনী বসায় শুধু যেখানে দরকার। * আর /-এর স্তর --এর চেয়ে উঁচু, তাই কোনো বন্ধনী লাগে না: ১২টি token.
  4. আবার parse. নতুন লেখা থেকে পাওয়া গাছ t2 আগের t1-এর সমান (অবস্থান বাদে তুলনা)। অর্থাৎ printer অর্থ বদলায়নি।
  5. Idempotence. t2 আবার ছাপলে একই লেখা: fmt(fmt(x)) = fmt(x). Formatter-এর জন্য এটি জরুরি, নইলে প্রতিবার সেভে ফাইল বদলাত। reference-এ bazar.haat-এও দুটি সত্য: ast-এর আউটপুট মেলে, fmt দুবার চালালে একই।
  6. যেখানে বন্ধনী লাগে। a - (b - c): ডান operand একই স্তরের, আর - বাঁ-সংযোজী, তাই বন্ধনী বাদ দিলে অর্থ বদলাবে। Printer সেটি রাখে; round trip পাস।
  7. Bug ধরা পড়ল। ল্যাবে printer-এর একটি নকলে ডান operand-এর বন্ধনীর নিয়ম মুছে দিয়েছি। সে লেখে a - b - c, যা parse হয়ে (- (- a b) c): অন্য গাছ। কোনো golden file ছাড়াই পরীক্ষা ভুলটি ধরেছে। (সব ফল reference-এর parser আর printer দিয়ে চালানো।)

Round trip থেকে একটি ছোট কিন্তু কাজের উপপাদ্য পাওয়া যায়।

উপপাদ্য ৪৫.২ — round trip থাকলে printer injective

ধরুন প্রতিটি AST t-এর জন্য parse(fmt(t)) = t. তাহলে fmt injective: t1 ≠ t2 হলে fmt(t1) ≠ fmt(t2). (Injective মানে আলাদা ইনপুট সবসময় আলাদা আউটপুট দেয়।)

প্রমাণ. (১) ধরি fmt(t1) = fmt(t2). (২) দুই পাশে parse প্রয়োগ: parse(fmt(t1)) = parse(fmt(t2)), কারণ parse একটি function (একই লেখায় একই ফল, সংজ্ঞা ৪৫.১-এর শর্ত ১)। (৩) অনুমান থেকে বাঁ পাশ t1, ডান পাশ t2, তাই t1 = t2. (৪) contrapositive নিলে দাবিটি। ∎

ফল. যে printer কখনো বন্ধনী লেখে না, সে round trip পাস করতে পারে না: (- a (- b c)) আর (- (- a b) c) দুটিই a - b - c হয়, অর্থাৎ fmt injective নয়। Stepper-এর ৭ নম্বর ধাপ ঠিক এই পাল্টা উদাহরণ।

উল্টোটা সত্য নয়: fmt injective হলেই round trip হয় না (printer হয়তো এমন লেখা দেয়, যা parser অন্য গাছ হিসেবে পড়ে)। আর round trip “t → লেখা → t” দিক পরীক্ষা করে, “লেখা → t → লেখা” নয়: bazar.haat-এর comment আর ফাঁকা ঘর fmt-এর পরে হারিয়ে যায় (১৬ লাইনের ৪৭৭ byte থেকে ২৪ লাইনের ৪৫০ byte; block ভেঙে লাইন বেড়েছে, comment গেছে), কারণ AST-এ সেগুলো রাখাই হয় না। Comment রেখে formatter বানাতে হলে অন্য ধরনের গাছ লাগে (পর্ব ৪৯ আর ৮০)।

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

  • Compiler-এর front end কী কী করে, আউটপুট কী? Lexical analysis (token), syntax analysis (parse tree বা AST), semantic analysis (symbol table, type যাচাই); আউটপুট যাচাই-করা AST বা IR, অথবা অবস্থানসহ error.
  • a<=b-তে কয়টি token? তিনটি: IDENT, <=, IDENT; maximal munch-এর কারণে < আর = আলাদা নয়।
  • Lexer আর parser আলাদা কেন? সরলতা (regular অংশ DFA-তে, গঠন CFG-তে), গতি, আর ফাঁকা ঘর ও comment একবারেই বাদ দেওয়া।
  • Hand-written parser কেন বেশি জনপ্রিয়? ভালো error message আর recovery, context-নির্ভর জায়গা সামলানো, বাড়তি tool ছাড়া build; উদাহরণ Clang, GCC, Go.
  • একটি parser কীভাবে পরীক্ষা করবেন? Golden file, round trip (parse(print(t)) = t), আর আরেকটি বাস্তবায়নের সঙ্গে differential testing, এলোমেলো ইনপুট দিয়ে।

৭ · AI-এর যুগে front end বানানো

“একটি ছোট ভাষার lexer আর parser লিখে দাও” — AI assistant এই কাজ কয়েক সেকেন্ডে করে, আর কোড দেখতে প্রায় সবসময় ঠিক। সমস্যা লুকিয়ে থাকে খুঁটিনাটিতে, ঠিক সেই জায়গাগুলোতে, যেগুলো spec ঠিক করে দেয়। এই বিষয়ে বারবার দেখা ভুল:

AI-এর ভুলকীভাবে ধরবেন
Precedence বা associativity ভুল: a - b - c-কে ডান থেকে বাঁধা, বা -a * b-তে unary-কে দুর্বল রাখাAST ছাপিয়ে reference-এর haat.py ast-এর সঙ্গে মেলানো; এলোমেলো expression-এ differential test
এক ভাষার নিয়ম আরেক ভাষায় চাপানো: Python-এর মতো a < b < c মেনে নেওয়া, বা Int-কে keyword বানানোSpec-এর decision 10 আর 6 পড়ে, ঠিক সেই উদাহরণ চালিয়ে দেখা
Error-এর অবস্থান ভুল: missing ; পরের লাইনে দেখানো, column byte ধরে গোনাDecision 1 আর 24; বাংলা comment-ওয়ালা ফাইলে column মেলানো; golden file
Maximal munch ভুলে যাওয়া: <=-কে দুটি token, বা ->-কে MINUS আর GThaat.py tokens-এর সঙ্গে token-তালিকা মেলানো
“Parser generator ছাড়া চলবে না” বা উল্টো, কোনো compiler সম্পর্কে ভুল ইতিহাস বলাসেই compiler-এর release notes বা source দেখা; সাল আর version লিখে রাখা
নিজে বানানো আউটপুট দেখানো: “এই কোড চালালে এই AST আসবে”নিজে চালানো; AI-কে আউটপুট বানাতে নিষেধ করা

AI-কে কোড লেখার যন্ত্র না বানিয়ে পরীক্ষার সঙ্গী বানান। এমন prompt দিন, যার উত্তর আপনি নিজে চালিয়ে যাচাই করতে পারেন:

আমি Haat নামের একটি ছোট শিক্ষণ-ভাষার front end বানাচ্ছি (Python 3, শুধু standard library). Spec-এর মূল কথা: - precedence (নিচু থেকে উঁচু): || , && , == != , < <= > >= , + - , * / % , prefix - ! , call f(a) - সব binary operator বাঁ-সংযোজী, কিন্তু দুই স্তরের তুলনাই non-associative: a < b < c হলে "comparison operators cannot be chained" error, দ্বিতীয় operator-এর জায়গায় - missing ';' আগের token-এর ঠিক পরের column-এ জানাতে হবে ১. আমার Pratt parser পরীক্ষার জন্য ১৫টি expression দাও, যেগুলো precedence, associativity আর non-associativity-র কিনারা ছোঁয়; প্রতিটির প্রত্যাশিত S-expression লেখো। ২. যেগুলোর উত্তর নিয়ে তুমি নিশ্চিত নও, সেগুলো "অনিশ্চিত" চিহ্ন দাও; আমি reference বাস্তবায়ন দিয়ে মেলাব। ৩. অন্য কোনো ভাষার (C, Python) নিয়ম ধরে নেবে না; spec-এ না থাকলে বলবে "spec-এ নেই"। ৪. কোনো program-এর আউটপুট নিজে বানিয়ে লিখবে না।

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

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

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

প্র ০১Compiler-এর বই parser generator শেখায়, অথচ বড় compiler-গুলো বেশিরভাগ হাতে লেখা parser ব্যবহার করে। কেন এই ফারাক?

১৯৭০-এর দশকে yacc (Stephen Johnson, Bell Labs) একটি বিপ্লব ছিল: ব্যাকরণ লিখুন, LALR(1) parser পান। তখন মেমরি কম, ব্যাকরণ জটিল, আর হাতে লেখা parser-এ ভুল বেশি। প্রচলিত বইগুলোর অনেকটা সেই যুগে লেখা, আর LR তত্ত্ব সুন্দর ও শেখানোর যোগ্য; তাই শিক্ষায় generator-এর জায়গা বড় থেকে গেছে। কিন্তু production compiler-এর অগ্রাধিকার বদলেছে। আজ একটি compiler-এর ব্যবহারকারী দিনে শতবার error message দেখেন, আর editor প্রতিটি কী-চাপে front end চালায়। তাই প্রশ্ন “ব্যাকরণ কত সহজে লিখব” থেকে সরে গেছে “ভুলের সময় ব্যবহারকারীকে কত ভালো সাহায্য করব”-তে।

হাতে লেখা parser-এ প্রতিটি জায়গায় জানা থাকে কী প্রত্যাশিত, তাই “expected ';' after variable declaration”-এর মতো নির্দিষ্ট মেসেজ দেওয়া সহজ। LR parser-এর অবস্থা একটি সংখ্যা, আর সেখান থেকে মানুষের ভাষার মেসেজ বানানো কঠিন। C আর C++-এর ব্যাকরণ context-নির্ভর: T * x; গুণ না pointer-ঘোষণা, তা নির্ভর করে T একটি type কি না। হাতে লেখা parser symbol table-এ সরাসরি জিজ্ঞেস করতে পারে। GCC 3.4 (২০০৪)-এ C++-এর yacc parser বাদ দিয়ে হাতে লেখা recursive descent নেওয়া হয়, মূলত এই কারণগুলোতে। Go 1.6 (২০১৬)-এ yacc থেকে তৈরি parser বদলে হাতে লেখা parser আসে; release notes এটিকে compiler-এর ভেতরের সবচেয়ে বড় পরিবর্তন বলে।

তবু generator মরেনি। CPython 3.9 (PEP 617) নিজের PEG generator দিয়ে parser বানায়, কারণ Python-এর ব্যাকরণ বড় আর একটি ব্যাকরণ ফাইলই সবচেয়ে ভালো spec. অনেক DSL, configuration ভাষা আর query ভাষাও generator দিয়ে বানানো হয়, কারণ সেখানে দ্রুত শুরু করা আর ব্যাকরণের conflict ধরা বেশি জরুরি। একটি মধ্যপথও আছে: ব্যাকরণ আলাদা ফাইলে রেখে তা থেকে হাতে লেখা parser-এর পরীক্ষা বানানো, যেমন এই পর্বে EBNF থেকে recognizer লিখে reference-এর সঙ্গে ৩০০০টি expression মেলানো হয়েছে।

মূল উপলব্ধি: বাছাইটি প্রকৌশলের আপস, তত্ত্বের নয়। ছোট, LL-ধরনের, ভালো diagnostic-চাওয়া ভাষায় হাতে লেখা parser প্রায়ই জেতে; বড় বা দ্রুত বদলানো ব্যাকরণে generator-এর মূল্য বেশি। দুই ক্ষেত্রেই ব্যাকরণটি লিখিত থাকা চাই।

প্র ০২“Reference implementation-ই spec” — এই নীতির সুবিধা আর বিপদ কী? Haat কোন পথে হাঁটছে?

অনেক ভাষা লিখিত spec ছাড়াই বড় হয়েছে: একটি বাস্তবায়ন যা করে, সেটিই নিয়ম। সুবিধা পরিষ্কার: প্রশ্নের উত্তর পেতে চালিয়ে দেখলেই হয়, আর spec আর কোডের মধ্যে কখনো অমিল হয় না। Python-এর ক্ষেত্রে CPython দীর্ঘদিন এই ভূমিকায়; Python-এর Language Reference আছে, কিন্তু খুঁটিনাটিতে অনেকেই CPython-এর আচরণকে মানদণ্ড ধরে।

বিপদ তিনটি। এক, bug আর নিয়মের পার্থক্য থাকে না: বাস্তবায়নের একটি দুর্ঘটনা স্থায়ী নিয়ম হয়ে যায়, কারণ কেউ না কেউ তার ওপর নির্ভর করে ফেলে। দুই, দ্বিতীয় বাস্তবায়ন লেখা কঠিন: PyPy বা অন্য কোনো Python বাস্তবায়নের লেখকদের প্রায়ই CPython-এর কোড পড়ে আচরণ অনুমান করতে হয়। তিন, যুক্তি করা কঠিন: “এই program কি বৈধ?” প্রশ্নের উত্তর তখন একটি বিশেষ version-এর ওপর নির্ভর করে।

উল্টো প্রান্তে Standard ML: ১৯৯০ সালে Milner, Tofte আর Harper-এর The Definition of Standard ML ভাষাটির পুরো static আর dynamic semantics গাণিতিক নিয়মে লেখে, ১৯৯৭ সালে সংশোধিত। C-র আছে ISO standard, JavaScript-এর ECMA-262, আর JavaScript-এর জন্য test262 নামে একটি বিশাল conformance test suite, যা দিয়ে প্রতিটি engine নিজেকে মাপে। মধ্যপথটি তাই জনপ্রিয়: লিখিত spec, তার সঙ্গে চালানো যায় এমন পরীক্ষার সংগ্রহ।

Haat এই মধ্যপথে। Spec v1 লেখা আছে; reference বাস্তবায়ন ফাঁকগুলো পূরণ করে ২৮টি সিদ্ধান্তে, প্রতিটি নম্বরসহ লিখিত; আর README নিজেই বলে কোন দশটি বিষয় spec v2-তে লেখা উচিত। প্রতিটি উদাহরণের golden file আছে, আর README-র উদ্ধৃত tokens, ast, fmt আর dis আউটপুট বর্তমান কোডের সঙ্গে অক্ষরে অক্ষরে মেলে কি না, তারও একটি পরীক্ষা আছে। এতে কোর্সের ৮৬টি পর্ব একটি ভাষাই শেখায়, আর প্রতিটি পর্বের কোড reference-এর সঙ্গে মেলানো যায়।

মূল উপলব্ধি: spec আর reference পরস্পরের পাহারাদার। লিখিত নিয়ম ছাড়া bug নিয়ম হয়ে যায়; চালানো যায় এমন বাস্তবায়ন আর পরীক্ষা ছাড়া লিখিত নিয়ম যাচাইহীন থেকে যায়।

প্র ০৩প্রতিটি token আর node-এ line:col রাখতে মেমরি আর কোড দুটোই বেশি লাগে। তবু কেন এটি অপরিহার্য, আর “column” আসলে কী গুনবে?

অবস্থান ছাড়া একটি compiler বলতে পারে “কোথাও একটি type mismatch আছে”, কিন্তু কোথায় তা নয়। পাঁচ হাজার লাইনের ফাইলে এটি প্রায় অকেজো। অবস্থানের তথ্য একবার হারালে পরে ফেরানো যায় না, কারণ AST-এ ফাঁকা ঘর আর বন্ধনী নেই। তাই নিয়মটি সরল: lexer প্রতিটি token-এ অবস্থান লেখে, parser প্রতিটি node-এ তা বসায়, আর পরের প্রতিটি ধাপ, এমনকি bytecode-ও (Code.positions), সেটি বহন করে। Runtime error-এর ঠিকানা (division by zero /-এর জায়গায়, decision 24) সেখান থেকেই আসে। Debugger-এর “এই লাইনে থামা”-ও একই তথ্যে চলে।

কিন্তু “column” কী গুনবে? তিনটি উত্তর প্রচলিত। Byte: UTF-8-এ “চাল” শব্দটি ৯ byte (তিনটি code point, প্রতিটি ৩ byte). Code point: তিনটি। UTF-16 code unit: এখানেও তিনটি, কিন্তু emoji-র মতো BMP-র বাইরের অক্ষরে দুটি। আর মানুষের চোখে “চা” আর “ল” দুটি অক্ষর-গুচ্ছ (grapheme cluster). Haat decision 1 code point বেছে নিয়েছে, তাই let s = "চাল"; x-এ x column 16-এ (reference-এর পরীক্ষায় আছে)। Language Server Protocol বহুদিন শুধু UTF-16 code unit ব্যবহার করত; version 3.17 থেকে client আর server আলোচনা করে encoding বেছে নিতে পারে। ফলে একই ফাইলে editor আর compiler আলাদা column বললে লাল দাগ ভুল জায়গায় পড়ে। পর্ব ২১-এ (String আর Unicode) এই পার্থক্যগুলো বিস্তারিত দেখেছেন।

খরচও কম নয়। বড় compiler প্রতিটি node-এ পুরো (line, col) না রেখে ফাইলের শুরু থেকে একটি byte offset রাখে, আর দরকার হলে লাইনের শুরুগুলোর একটি টেবিল থেকে line আর column হিসাব করে; Clang-এর SourceLocation এই ধরনের একটি সংকুচিত সংখ্যা। Haat শেখানোর ভাষা, তাই স্পষ্ট line আর col রাখে, যাতে প্রতিটি dataclass পড়েই বোঝা যায়।

মূল উপলব্ধি: source position front end-এর সবচেয়ে মূল্যবান “বাড়তি” তথ্য। কী গুনছেন (byte, code point, UTF-16 unit) তা spec-এ লিখুন, আর বাংলা লেখাসহ ফাইলে পরীক্ষা করুন।

প্র ০৪Golden file, differential testing আর round trip — প্রতিটি কোন ভুল ধরে, কোনটি ফসকে যায়? শুধু একটি বাছতে হলে কোনটি?

Golden file সবচেয়ে সরাসরি: নির্দিষ্ট ইনপুটে নির্দিষ্ট আউটপুট। এটি regression ধরে, অর্থাৎ আগে যা ঠিক ছিল, তা হঠাৎ বদলে গেলে। Error message-এর শব্দ আর line:col-এর মতো খুঁটিনাটি পাহারা দিতেও এটি সেরা। দুর্বলতা দুটি: শুধু সেই ইনপুটগুলোই পরীক্ষা হয়, যেগুলো কেউ লিখেছেন; আর প্রথমবার golden file বানানোর সময় আউটপুট ভুল হলে পরীক্ষা চিরকাল ভুলকে রক্ষা করে। তাই প্রতিটি golden file কাউকে না কাউকে হাতে যাচাই করতে হয়।

Differential testing-এর জোর হলো সংখ্যা: প্রত্যাশিত আউটপুট কাউকে লিখতে হয় না, তাই লক্ষ ইনপুট চালানো যায়। ২০১১ সালে Xuejun Yang, John Regehr ও সহকর্মীদের Csmith এলোমেলো C program বানিয়ে GCC আর LLVM-এ কয়েকশো আগে-অজানা bug পেয়েছিল, এই পদ্ধতিতে। এই পর্বের ছোট front end-ও এভাবে ১০০০টি program-এ reference-এর সঙ্গে মেলানো হয়েছে। দুর্বলতা: দুই বাস্তবায়ন একই ভুল করলে চুপ, আর অমিল পেলে কোনটি ভুল তা আলাদা করে বের করতে হয়।

Round trip একটি অন্তর্নিহিত বৈশিষ্ট্য (property) পরীক্ষা করে: parser আর printer পরস্পরের বিপরীত। দ্বিতীয় বাস্তবায়ন বা golden file লাগে না। কিন্তু দুটি একসঙ্গে একইভাবে ভুল হলে চুপ থাকে: ধরুন parser a - b - c-কে ভুলভাবে ডান থেকে বাঁধে, আর printer-ও ঠিক সেই ভুল ধারণা থেকে বন্ধনী বসায়; তাহলে round trip পাস করবে, অথচ ভাষাটি ভুল। এই ভুল ধরবে একটি golden file বা reference-এর সঙ্গে differential test.

তাই উত্তর: একটি নয়, তিনটির মিশ্রণ। ছোট কিন্তু হাতে-যাচাই-করা golden file-এর একটি সেট নিয়ম ঠিক করে; differential test সেই নিয়ম লক্ষ ইনপুটে ছড়িয়ে দেয়; round trip এমন বৈশিষ্ট্য পাহারা দেয়, যা দুটি বাস্তবায়নের তুলনায় ধরা পড়ে না। Software testing-এর ভাষায় এগুলো আলাদা test oracle, অর্থাৎ ফল ঠিক না ভুল তা বিচারের উপায়।

মূল উপলব্ধি: প্রতিটি পরীক্ষা-পদ্ধতি নিজের অন্ধ জায়গা নিয়ে আসে। ভালো পরীক্ষা-ব্যবস্থা এমনভাবে সাজানো, যাতে এক পদ্ধতির অন্ধ জায়গা অন্যটি দেখে।

প্র ০৫Lexer, parser আর semantic analysis-এর সীমারেখা কি সবসময় পরিষ্কার? C-র “lexer hack” আর Haat-এর decision 6 এখানে কী শেখায়?

তত্ত্বে ভাগটি পরিষ্কার: lexer regular, parser context-free, আর বাকি সব (নাম, type) semantic. বাস্তবে কিছু ভাষা এই দেয়াল ভাঙে। C-র উদাহরণটি বিখ্যাত: T * x; যদি T একটি typedef নাম হয়, তাহলে এটি একটি pointer-ঘোষণা; T একটি variable হলে গুণ, যার ফল ফেলে দেওয়া হয়। Parser-কে আগেই জানতে হয় T কী। প্রচলিত সমাধানকে বলে lexer hack: parser যখন একটি typedef দেখে, symbol table-এ লিখে রাখে, আর lexer পরে সেই নামটিকে IDENT-এর বদলে একটি আলাদা TYPE_NAME token হিসেবে ফেরত দেয়। ফলে lexer আর semantic analysis-এর মধ্যে একটি গোপন সুতো তৈরি হয়, আর ধাপগুলো আর স্বাধীন থাকে না।

আরও উদাহরণ আছে। JavaScript-এ / ভাগ না regular expression-এর শুরু, তা নির্ভর করে আগের token-এর ওপর, তাই lexer-কে parser-এর অবস্থা জানতে হয়। Python-এ ইন্ডেন্টেশন tokenizer-এর ভেতরে একটি stack দিয়ে INDENT আর DEDENT token-এ বদলায়, যা কোনো regular expression একা করতে পারে না। C++-এ >> কখন shift আর কখন দুটি template-বন্ধনী, তা C++11 আলাদা নিয়ম দিয়ে ঠিক করেছে।

Haat এই সমস্যাগুলো নকশা দিয়েই এড়িয়েছে। Decision 6: Int Bool Str Unit keyword নয়, সাধারণ IDENT; শুধু type-এর জায়গায় parser তাদের type হিসেবে পড়ে। Type-এর জায়গা ব্যাকরণ থেকেই চেনা যায় (: বা ->-এর পরে), তাই lexer-কে কোনো symbol table দেখতে হয় না। Statement-এর শুরুর fn declaration না expression, তা এক token lookahead-এই বোঝা যায়। ফলে lexer, parser আর resolver আলাদা ফাইলে, আলাদা পর্বে, আলাদাভাবে পরীক্ষা করা যায়; এই কোর্সের কাঠামো ঠিক এর ওপর দাঁড়িয়ে।

দাম হলো কিছু অদ্ভুত কিন্তু বৈধ program, যেমন let Int = 5; print(Int);, যা 5 ছাপে। এটি একটি সচেতন আপস: পড়ার জন্য খারাপ নাম, কিন্তু ভাষার কাঠামো সরল। একটি linter চাইলে এমন নামে সতর্ক করতে পারে, ভাষার নিয়ম না বদলেই।

মূল উপলব্ধি: ধাপগুলোর পরিষ্কার ভাগ আপনাআপনি আসে না; ভাষার নকশা সেটি সম্ভব বা অসম্ভব করে। নতুন ভাষা নকশার সময় জিজ্ঞেস করুন: কোনো token বা গঠন বুঝতে কি নামের অর্থ জানতে হয়? হলে ব্যাকরণ বদলানোর কথা ভাবুন।

অনুশীলন

প্রথমটিতে কোড লিখতে হবে; বাকিগুলো ভুল খোঁজা ও প্রমাণ, trace আর ভাষা-নকশা।

  1. Front end বাড়ান (বাস্তবায়ন): অংশ ৫-এর ছোট front end anonymous function বোঝে না। এটি যোগ করুন: fn(a: Int, b: Int) -> Int { return a + b; } একটি expression, reference-এর মতো একটি Lambda(params, ret, body, line, col) node বানাবে, যার অবস্থান fn-এ। Statement-এর শুরুতে fn-এর পরে নাম না থাকলে সেটিও expression. চারটি block চালানোর পরে আপনার কোড চালিয়ে reference-এর সঙ্গে মেলান।

    দুটি method-কে বাড়াতে হয়: prefix (expression-এর শুরুতে fn) আর statement (fn-এর পরে IDENT না থাকলে expression statement):

    Lambda = make_dataclass("Lambda", ["params", "ret", "body", "line", "col"])
    class Parser(Parser):
        def prefix(p):
            if not p.peek("FN"): return super().prefix()
            t = p.advance(); p.expect("LPAREN", "expected '(' after 'fn'")
            ps = p.items(p.param, "expected ')' after parameters")
            ret = p.advance() and p.expect("IDENT", "expected a type").text if p.peek("ARROW") else "Unit"
            return Lambda(ps, ret, p.block("expected '{' before function body"), t.line, t.col)
        def statement(p):
            if p.peek("FN") and p.toks[p.pos + 1].kind != "IDENT":   # fn( ... ) is an expression
                t, e = p.peek(), p.expression()
                p.expect("SEMI", "expected ';' after expression"); return ExprStmt(e, t.line, t.col)
            return super().statement()

    ল্যাবে তিনটি program-এ (যেমন let add = fn(a: Int, b: Int) -> Int { return a + b; }; আর fn(x: Int) { print(x); }(7);) reference-এর সঙ্গে token আর অবস্থানসহ পুরো AST মিলিয়েছি: তিনটিতেই হুবহু। দ্বিতীয়টিতে খেয়াল করুন, lambda-র পরেই (7): call-এর binding power 80, তাই সেটি lambda-কেই ডাকে। Reference-এর ast দেখায় (expr (call (lambda ((x Int)) Unit (block (print x))) 7)), আর run ছাপে 7. -> T না থাকলে ret "Unit" (decision 23).

  2. ভুল খুঁজুন আর প্রমাণ করুন: (ক) একজন Haat-এর ব্যাকরণে লিখলেন relExpr = addExpr { ( "<" | "<=" | ">" | ">=" ) addExpr } ;. Spec-এর কোন সিদ্ধান্ত এটি ভাঙে, আর এই ব্যাকরণ মেনে লেখা parser print(a < b < c);-এ কী করবে, reference কী বলে? (খ) প্রমাণ করুন: যে printer কোনো বন্ধনীই লেখে না, সে round-trip শর্ত parse(fmt(t)) = t মানতে পারে না।

    (ক) { } মানে শূন্য বা বেশিবার, তাই এই নিয়ম a < b < c গ্রহণ করে আর বাঁ থেকে বেঁধে (< (< a b) c) বানায়, C-র মতো। এটি decision 10 ভাঙে: দুই তুলনা-স্তরই non-associative. সঠিক রূপ [ … ], অর্থাৎ বড়জোর একটি। Reference বলে 1:13: error: comparison operators cannot be chained, দ্বিতীয় <-এর জায়গায়। ভুল ব্যাকরণের parser কোনো syntax error দেবে না; পরে type checker a < b-এর Bool-কে <-এর বাঁ operand হিসেবে পেয়ে একটি type error দেবে (decision 11: < শুধু Int-এ), অর্থাৎ ভুল ধাপে, ভুল মেসেজে।

    (খ) প্রমাণ. (১) দুটি গাছ নিন: t1 = (- a (- b c)) আর t2 = (- (- a b) c). এরা আলাদা। (২) বন্ধনী-ছাড়া printer দুটির জন্যই লেখে a - b - c, অর্থাৎ fmt(t1) = fmt(t2). (৩) উপপাদ্য ৪৫.২ বলে round trip থাকলে fmt injective, অর্থাৎ fmt(t1) = fmt(t2) হলে t1 = t2. (৪) এখানে তা মিথ্যা, তাই round trip থাকতে পারে না। সরাসরি দেখলেও: parse(a - b - c) একটিই গাছ, (- (- a b) c), তাই parse(fmt(t1)) = t2 ≠ t1. ∎ (reference-এর printer-এর একটি নকলে এই ভুল বসিয়ে ঠিক এই ফল পাওয়া গেছে; অংশ ৬-এর stepper.)

  3. আউটপুট অনুমান করুন (trace): নিচের program-এর জন্য বলুন: (ক) EOF-সহ কয়টি token, আর লাইন ৩-এর == আর --এর অবস্থান; (খ) haat.py ast-এর S-expression; (গ) fmt-এর আউটপুট; (ঘ) চালালে কী ছাপবে; (ঙ) লাইন ৩-এর শেষের ; মুছে দিলে কোন error, কোন অবস্থানে।
    var stock = 12;
    while stock > 0 { stock = stock - 5; }
    print(stock == -3);

    (ক) লাইন ১-এ ৫টি, লাইন ২-এ ১২টি, লাইন ৩-এ ৮টি, আর EOF: মোট ২৬টি (reference-এর tokens ২৬ লাইন ছাপে)। == আছে 3:13-এ, - 3:16-এ, আর 3 3:17-এ: -3 দুটি token, কারণ INT-এ চিহ্ন থাকে না।

    (খ) সত্যিকারের আউটপুট:

    (program
      (var stock 12)
      (while (> stock 0)
        (block
          (set stock (- stock 5))))
      (print (== stock (- 3))))

    Assignment-এর node Assign, S-expression-এ set. (- 3) একটি Unary; (- stock 5) একটি Binary.

    (গ) fmt block-কে কয়েক লাইনে ভাঙে, ৪ ঘর ইন্ডেন্টেশন দেয়:

    var stock = 12;
    while stock > 0 {
        stock = stock - 5;
    }
    print(stock == -3);

    (ঘ) stock: 12 → 7 → 2 → −3, তারপর শর্ত মিথ্যা। ছাপে true. (ঙ) 3:19: error: expected ';' after print statement: শেষ token ) আছে 3:18-এ, আর missing ; তার ঠিক পরে জানানো হয় (decision 24).

  4. একটি feature নকশা করুন (spec লেখা): বাজারঘরের দল চায় Haat-এ x += e; থাকুক। (ক) আজকের reference var x = 1; আর তার পরের লাইনে x += 1; পেলে কী বলে, আর কেন? (খ) Spec-এর ছয়টি ভাগের প্রতিটিতে কী যোগ বা বদলাতে হবে লিখুন। (গ) এই পরিবর্তন কি আগের কোনো বৈধ program-এর অর্থ বদলাতে পারে? যুক্তি দিন।

    (ক) সত্যিকারের run: 2:4: error: expected expression. += কোনো token নয়, তাই lexer দেয় PLUS (2:3) আর EQ (2:4). Parser x + পড়ে ডান operand খোঁজে, পায় =, যা কোনো expression শুরু করে না।

    (খ) Lexical: TWO_CHAR-এ "+=": "PLUS_EQ" (চাইলে -=, *=…); maximal munch-এর কারণে x+=1 আর x += 1 একই, কিন্তু x + = 1 আগের মতোই ভুল। Syntax: simpleStmt = expr [ ( "=" | "+=" ) expr ] ";". Precedence: বদলায় না, কারণ এটি statement, operator নয় (decision 9-এর মতো)। Static: বাঁ দিকে শুধু নাম, আর শুধু var (decision 19-এর মেসেজ); type: Int += Int বা Str += Str, decision 11-এর +-এর নিয়ম মেনে। Dynamic: অর্থ x = x + e;, বাঁ থেকে ডানে: আগে x পড়া, তারপর e (decision 12). বাঁ দিক একটি সাধারণ নাম, তাই C-র a[f()] += 1-এর মতো “দুবার মূল্যায়ন” প্রশ্ন ওঠে না। Error: নতুন মেসেজ, যেমন expected ';' after assignment আবার ব্যবহার, আর অবস্থানের নিয়ম আগের মতো। বাস্তবায়নে নতুন AST node রাখবেন, না parser-এই Assign(x, Binary("+", Var x, e)) বানাবেন (desugaring, পর্ব ৫৫)? দ্বিতীয়টি সহজ, কিন্তু তখন fmt x += 1 ফিরিয়ে দিতে পারে না: round trip-এর “লেখা” দিক হারায়।

    (গ) না। আজ যেখানে +-এর ঠিক পরে = আসে, সেই প্রতিটি program অবৈধ, কারণ = কোনো expression শুরু করে না, আর +-এর পরে একটি expression লাগে। তাই নতুন token শুধু আগে-অবৈধ লেখাকে বৈধ করে; কোনো বৈধ program-এর token-ভাগ বা গাছ বদলায় না। এই যুক্তিই একটি নতুন feature “backward compatible” কি না যাচাইয়ের মূল কৌশল।

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

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

ক্রমএকটি Haat ফাইল front end-এর ভেতর দিয়ে যে ক্রমে যায়, সেভাবে সাজান (▲▼ চেপে সরান)

  1. অক্ষরের সারি পড়া, column গোনা
  2. Lexer — token-এর তালিকা, শেষে EOF
  3. Parser — recursive descent আর Pratt দিয়ে AST
  4. Resolver — প্রতিটি নাম তার ঘোষণার সঙ্গে জোড়া
  5. Type checker — type নিয়ম যাচাই
  6. যাচাই-করা AST interpreter বা bytecode compiler-এর হাতে

Haat-এর lexer লেখা a<=-b কোন token-এর সারিতে ভাগ করবে (EOF বাদে)?

  • IDENT, LT, EQ, MINUS, IDENT
  • IDENT, LT_EQ, MINUS, IDENT
  • IDENT, LT_EQ, IDENT
  • IDENT, LT, ARROW, IDENT

Haat program let Int = 5; print(Int); reference বাস্তবায়নে চালালে কী হয়?

  • Lexer error: Int একটি keyword
  • Parser error: নামের জায়গায় একটি type
  • Program চলে আর 5 ছাপে
  • Resolver error: Int আগে থেকেই ঘোষিত

Haat program let total = 10 (প্রথম লাইন, ; নেই) আর তার পরের লাইনে print(total);. Reference কোন অবস্থানে error দেয়?

  • 1:15, অর্থাৎ 10-এর ঠিক পরে
  • 2:1, অর্থাৎ print-এর জায়গায়
  • 1:13, অর্থাৎ 10-এর শুরুতে
  • কোনো error নেই, runtime-এ total ছাপে

একটি pretty-printer কখনো বন্ধনী লেখে না। Round-trip পরীক্ষা parse(fmt(t)) = t কোন গাছে এই printer-কে ব্যর্থ দেখাবে?

  • (- (* a b) c)
  • (- (- a b) c)
  • a
  • (- a (- b c))

Golden-file পরীক্ষার সবচেয়ে বড় দুর্বলতা কোনটি?

  • Error message-এর লেখা পরীক্ষা করা যায় না
  • ভুল আউটপুট একবার golden হয়ে গেলে পরীক্ষা সেই ভুলকেই রক্ষা করে
  • দ্বিতীয় একটি বাস্তবায়ন ছাড়া চালানো যায় না
  • প্রতিবার ফল এলোমেলো হয়

Clang, GCC আর Go-র মতো অনেক production compiler হাতে লেখা parser ব্যবহার করে। নিচের কোনটি এর সাধারণ কারণ নয়?

  • ভালো, নির্দিষ্ট error message দেওয়া সহজ
  • Context-নির্ভর জায়গা (যেমন C-র typedef নাম) সামলানো সহজ
  • হাতে লেখা parser যেকোনো generator-এর চেয়ে বেশি ভাষা চিনতে পারে
  • Error recovery-র ওপর পূর্ণ নিয়ন্ত্রণ

Haat-এ print(a < b < c); লিখলে কোন ধাপ, কী বলে?

  • Parser: 1:13: error: comparison operators cannot be chained
  • Lexer: unexpected character '<'
  • কোনো error নেই, মানে a < b আর b < c দুটিই
  • Type checker: type mismatch

শব্দকোষ

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

মনে রাখুন

  1. Front end-এর চুক্তি: অক্ষর → token → AST → নাম ও type যাচাই; ফল হয় যাচাই-করা AST, নয়তো line:col-সহ error-এর তালিকা।
  2. একটি ভাষার spec-এ ছয় ভাগ: lexical grammar, EBNF, precedence, static নিয়ম, চলার সময়ের অর্থ, error-এর format; Haat-এর ফাঁক পূরণ করে reference-এর ২৮টি decision.
  3. Non-associative তুলনা ব্যাকরণে লেখা হয় [ … ] দিয়ে, { … } দিয়ে নয়; precedence টেবিল আর layered EBNF একই তথ্যের দুই রূপ।
  4. অনেক production compiler হাতে লেখা recursive descent ব্যবহার করে (Clang, GCC, Go 1.6 থেকে, rustc, V8), মূলত diagnostic আর recovery-র জন্য; CPython-এর PEG generator একটি শিক্ষণীয় ব্যতিক্রম।
  5. Front end পরীক্ষা করুন তিনভাবে: golden file, differential testing আর round trip; round trip থাকলে printer injective (উপপাদ্য ৪৫.২)।

পরের পর্বে: হাতে লেখা lexer, পুরোটা: character cursor, peek আর advance, বাংলা লেখায় column গোনা, string-এর escape, খুব বড় integer, আর প্রতিটি error message reference-এর সঙ্গে অক্ষরে অক্ষরে মিলিয়ে।

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

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