Ngôn ngữ lập trình dễ tạo cảm giác như một hộp đen: văn bản đi vào, hành vi xuất hiện, còn compiler hoặc runtime bằng cách nào đó nối hai đầu lại. Cách nhanh nhất để biến sự mơ hồ ấy thành mô hình cụ thể không phải là đọc ngay implementation của một ngôn ngữ production. Hãy tự xây một ngôn ngữ đủ nhỏ để nhìn thấy toàn bộ đường đi của chương trình.

Chúng ta sẽ tạo Pebble, một expression language viết bằng TypeScript. Pebble có số, boolean, phép toán số học, so sánh, biến, hàm ẩn danh, lời gọi hàm và if/else. Chừng đó đã đủ làm lộ ra các ranh giới quan trọng: ký tự trở thành token, token trở thành abstract syntax tree, còn tree được evaluate trong lexical environment. Function sẽ là closure thật, không phải thao tác thay chuỗi.

Đây là một chương trình Pebble hoàn chỉnh:

text
let makeAdder = fn(x) {
  fn(y) { x + y }
};
let add10 = makeAdder(10);
let answer = add10(32);
if (answer == 42) { answer } else { 0 };

Implementation đủ nhỏ để suy luận bằng tay, nhưng kiến trúc của nó vẫn là phiên bản thu gọn của những interpreter lớn hơn.

Từ source text đến runtime value

Interpreter là một chuỗi representation. Mỗi stage loại bỏ chi tiết không còn cần thiết và bổ sung cấu trúc cho stage kế tiếp.

flowchart LR S["Ký tự nguồn"] --> L["Lexer"] L --> T["Dòng token"] T --> P["Pratt parser"] P --> A["Abstract syntax tree"] A --> E["Evaluator"] N["Lexical environment"] --> E E --> V["Runtime value"] subgraph X["AST của add10 32"] C["Call"] --> I["Name add10"] C --> G["Argument 32"] end

Lexer biết answer là một identifier và == là một operator duy nhất. Nó không biết answer đã được khai báo hay chưa. Parser biết phép nhân bind chặt hơn phép cộng, nhưng chưa quan tâm operand có phải number hay không. Evaluator mới resolve tên và áp dụng luật runtime.

Tách trách nhiệm như vậy giúp lỗi chỉ đúng nơi phát sinh:

Stage Input Output Ví dụ lỗi
Lexing Ký tự Token Ký tự @ không hợp lệ
Parsing Token AST Thiếu ) sau argument
Evaluation AST và environment Value Tên total chưa được định nghĩa

Note

Pebble interpret AST trực tiếp. “Interpreted” không có nghĩa là “không parse”, còn “compiled” cũng không đồng nghĩa với native machine code. Cả hai đều cần front end có cấu trúc; khác biệt chính nằm ở việc hệ thống làm gì sau khi đã hiểu chương trình.

Token và lexer có vị trí source

Một token mang category, đoạn text gốc và source span. Giữ vị trí ngay từ đầu là điều bắt buộc nếu muốn diagnostic tốt; cố dựng lại line và column sau khi parser đã bỏ punctuation thường không chính xác.

ts
export type Span = {
  start: number;
  end: number;
  line: number;
  column: number;
};

export type TokenKind =
  | 'number' | 'identifier' | 'let' | 'fn' | 'if' | 'else'
  | 'true' | 'false' | 'leftParen' | 'rightParen'
  | 'leftBrace' | 'rightBrace' | 'comma' | 'semicolon'
  | 'plus' | 'minus' | 'star' | 'slash' | 'bang'
  | 'equal' | 'equalEqual' | 'bangEqual'
  | 'less' | 'lessEqual' | 'greater' | 'greaterEqual' | 'eof';

export type Token = {
  kind: TokenKind;
  lexeme: string;
  span: Span;
  numberValue?: number;
};

const keywords: Record<string, TokenKind> = {
  let: 'let', fn: 'fn', if: 'if', else: 'else',
  true: 'true', false: 'false',
};

Lexer đi một chiều qua source. Whitespace làm thay đổi vị trí nhưng không emit token. Digit mở đầu number; chữ cái hoặc underscore mở đầu identifier; punctuation được xử lý trực tiếp. Operator hai ký tự chỉ cần nhìn trước một ký tự.

ts
export class Lexer {
  #offset = 0;
  #line = 1;
  #column = 1;

  constructor(readonly source: string) {}

  scan(): Token[] {
    const tokens: Token[] = [];
    while (true) {
      while (/\s/.test(this.#peek())) this.#advance();
      if (this.#atEnd()) break;
      tokens.push(this.#nextToken());
    }
    tokens.push(this.#token('eof', this.#offset, this.#line, this.#column));
    return tokens;
  }

  #nextToken(): Token {
    const start = this.#offset;
    const line = this.#line;
    const column = this.#column;
    const char = this.#advance();

    if (/\d/.test(char)) {
      while (/\d/.test(this.#peek())) this.#advance();
      if (this.#peek() === '.' && /\d/.test(this.#peek(1))) {
        this.#advance();
        while (/\d/.test(this.#peek())) this.#advance();
      }
      return this.#token('number', start, line, column, Number(this.source.slice(start, this.#offset)));
    }

    if (/[A-Za-z_]/.test(char)) {
      while (/[A-Za-z0-9_]/.test(this.#peek())) this.#advance();
      const text = this.source.slice(start, this.#offset);
      return this.#token(keywords[text] ?? 'identifier', start, line, column);
    }

    const single: Partial<Record<string, TokenKind>> = {
      '(': 'leftParen', ')': 'rightParen', '{': 'leftBrace', '}': 'rightBrace',
      ',': 'comma', ';': 'semicolon', '+': 'plus', '-': 'minus',
      '*': 'star', '/': 'slash',
    };
    const singleKind = single[char];
    if (singleKind) return this.#token(singleKind, start, line, column);

    const pairs: Record<string, [TokenKind, TokenKind]> = {
      '!': ['bang', 'bangEqual'], '=': ['equal', 'equalEqual'],
      '<': ['less', 'lessEqual'], '>': ['greater', 'greaterEqual'],
    };
    const pair = pairs[char];
    if (pair) {
      const kind = this.#peek() === '=' ? (this.#advance(), pair[1]) : pair[0];
      return this.#token(kind, start, line, column);
    }

    throw new LanguageError('lex', `Unexpected character ${JSON.stringify(char)}`, {
      start, end: this.#offset, line, column,
    });
  }

  #peek(distance = 0): string { return this.source[this.#offset + distance] ?? '\0'; }
  #atEnd(): boolean { return this.#offset >= this.source.length; }
  #advance(): string {
    const char = this.source[this.#offset++] ?? '\0';
    if (char === '\n') { this.#line++; this.#column = 1; }
    else this.#column++;
    return char;
  }
  #token(kind: TokenKind, start: number, line: number, column: number, numberValue?: number): Token {
    return { kind, lexeme: this.source.slice(start, this.#offset), numberValue,
      span: { start, end: this.#offset, line, column } };
  }
}

Sentinel \0 làm cho lookahead ở cuối input an toàn. Lexer production có thể hỗ trợ Unicode identifier, string, comment và numeric separator. Những tính năng ấy nên mở rộng token contract thay vì để xử lý ký tự rò sang parser.

Grammar, AST và độ ưu tiên bằng Pratt parser

Trước khi viết parser, hãy viết ngôn ngữ thành grammar. Pebble dùng semicolon cho statement top-level, còn block kết thúc bằng một expression tạo ra value.

text
program     -> statement* EOF
statement   -> "let" IDENT "=" expression ";" | expression ";"
block       -> "{" ("let" IDENT "=" expression ";")* expression "}"
expression  -> prefix (binary expression | "(" arguments? ")")*
prefix      -> NUMBER | "true" | "false" | IDENT
             | ("-" | "!") expression | "(" expression ")"
             | "fn" "(" parameters? ")" block
             | "if" "(" expression ")" block "else" block
arguments   -> expression ("," expression)*
parameters  -> IDENT ("," IDENT)*

AST lưu ý nghĩa thay vì punctuation. Parenthesis thay đổi grouping nên không cần node riêng sau khi parse.

ts
export type Statement =
  | { kind: 'let'; name: string; value: Expression; span: Span }
  | { kind: 'expression'; expression: Expression; span: Span };

export type Block = { bindings: Extract<Statement, { kind: 'let' }>[]; result: Expression; span: Span };

export type Expression =
  | { kind: 'number'; value: number; span: Span }
  | { kind: 'boolean'; value: boolean; span: Span }
  | { kind: 'name'; name: string; span: Span }
  | { kind: 'prefix'; operator: 'minus' | 'bang'; right: Expression; span: Span }
  | { kind: 'binary'; operator: TokenKind; left: Expression; right: Expression; span: Span }
  | { kind: 'if'; condition: Expression; then: Block; otherwise: Block; span: Span }
  | { kind: 'function'; parameters: string[]; body: Block; span: Span }
  | { kind: 'call'; callee: Expression; arguments: Expression[]; span: Span };

Recursive descent rất hợp với statement, block, function và if. Expression khó hơn vì precedence và associativity tác động lẫn nhau. Pratt parsing giải quyết bằng binding power. Left/right power dưới đây làm binary operator kết hợp trái, còn lời gọi hàm bind chặt nhất.

Dạng Left/right binding power Cách group
==, != 1 / 2 a == (b < c)
<, <=, >, >= 3 / 4 (a + b) < c
+, - 5 / 6 (a + b) - c
*, / 7 / 8 (a * b) / c
Prefix -, ! right 9 -(f(x))
Call (...) left 11 (make(1))(2)
ts
const infixPower: Partial<Record<TokenKind, readonly [number, number]>> = {
  equalEqual: [1, 2], bangEqual: [1, 2],
  less: [3, 4], lessEqual: [3, 4], greater: [3, 4], greaterEqual: [3, 4],
  plus: [5, 6], minus: [5, 6], star: [7, 8], slash: [7, 8],
};

class Parser {
  #current = 0;
  constructor(readonly tokens: Token[]) {}

  parseExpression(minimumPower = 0): Expression {
    let left = this.#parsePrefix();

    while (true) {
      if (this.#check('leftParen')) {
        if (11 < minimumPower) break;
        left = this.#finishCall(left);
        continue;
      }

      const power = infixPower[this.#peek().kind];
      if (!power || power[0] < minimumPower) break;
      const operator = this.#advance();
      const right = this.parseExpression(power[1]);
      left = { kind: 'binary', operator: operator.kind, left, right,
        span: mergeSpans(left.span, right.span) };
    }
    return left;
  }

  #parsePrefix(): Expression {
    const token = this.#advance();
    switch (token.kind) {
      case 'number': return { kind: 'number', value: token.numberValue!, span: token.span };
      case 'true': return { kind: 'boolean', value: true, span: token.span };
      case 'false': return { kind: 'boolean', value: false, span: token.span };
      case 'identifier': return { kind: 'name', name: token.lexeme, span: token.span };
      case 'minus': case 'bang': {
        const right = this.parseExpression(9);
        return { kind: 'prefix', operator: token.kind, right, span: mergeSpans(token.span, right.span) };
      }
      case 'leftParen': {
        const expression = this.parseExpression();
        this.#consume('rightParen', "Expected ')' after expression");
        return expression;
      }
      case 'fn': return this.#parseFunction(token.span);
      case 'if': return this.#parseIf(token.span);
      default: throw this.#error(token, 'Expected an expression');
    }
  }
}

#parseFunction consume danh sách identifier phân tách bằng comma rồi parse block. #parseIf consume condition trong parenthesis, hai block và keyword else bắt buộc. #finishCall parse không hoặc nhiều expression phân tách bằng comma. Đây đều là method recursive descent thông thường; Pratt parser chỉ cần ở nơi precedence quyết định lúc nào recursion dừng.

Warning

Đừng sửa đi sửa lại tree đã tạo để áp precedence. Hãy định nghĩa precedence đúng một lần trong parser. AST phải có grouping chính xác khi rời front end để mọi consumer về sau cùng nhìn thấy một chương trình.

Evaluator, environment và runtime value

Evaluator đi qua AST. Tập value của Pebble cố tình hẹp hơn JavaScript, nhờ đó coercion của host language không vô tình trở thành semantics của guest language.

ts
export type RuntimeValue = number | boolean | Closure;

export type Closure = {
  kind: 'closure';
  parameters: string[];
  body: Block;
  environment: Environment;
};

export class Environment {
  readonly #values = new Map<string, RuntimeValue>();
  constructor(readonly parent?: Environment) {}

  define(name: string, value: RuntimeValue): void {
    if (this.#values.has(name)) throw new Error(`Name '${name}' is already defined`);
    this.#values.set(name, value);
  }

  get(name: string, span: Span): RuntimeValue {
    if (this.#values.has(name)) return this.#values.get(name)!;
    if (this.parent) return this.parent.get(name, span);
    throw new LanguageError('runtime', `Undefined name '${name}'`, span);
  }
}

Name lookup bắt đầu ở environment hiện tại rồi đi theo parent link ra ngoài. Mỗi block tạo child environment nên local binding không thoát khỏi block. Có thể shadow tên bằng cách define lại trong child, trong khi hai binding cùng tên trong một scope vẫn là lỗi.

ts
export function evaluate(expression: Expression, environment: Environment): RuntimeValue {
  switch (expression.kind) {
    case 'number': case 'boolean': return expression.value;
    case 'name': return environment.get(expression.name, expression.span);
    case 'prefix': {
      const right = evaluate(expression.right, environment);
      if (expression.operator === 'minus') return -expectNumber(right, expression.span);
      return !expectBoolean(right, expression.span);
    }
    case 'binary': {
      const left = evaluate(expression.left, environment);
      const right = evaluate(expression.right, environment);
      return evaluateBinary(expression.operator, left, right, expression.span);
    }
    case 'if': {
      const condition = expectBoolean(evaluate(expression.condition, environment), expression.condition.span);
      return evaluateBlock(condition ? expression.then : expression.otherwise, environment);
    }
    case 'function':
      return { kind: 'closure', parameters: expression.parameters,
        body: expression.body, environment };
    case 'call': {
      const callee = evaluate(expression.callee, environment);
      if (!isClosure(callee)) throw new LanguageError('runtime', 'Only functions can be called', expression.callee.span);
      if (callee.parameters.length !== expression.arguments.length) {
        throw new LanguageError('runtime',
          `Expected ${callee.parameters.length} arguments but received ${expression.arguments.length}`,
          expression.span);
      }
      const callEnvironment = new Environment(callee.environment);
      callee.parameters.forEach((name, index) =>
        callEnvironment.define(name, evaluate(expression.arguments[index]!, environment)));
      return evaluateBlock(callee.body, callEnvironment);
    }
  }
}

function evaluateBlock(block: Block, parent: Environment): RuntimeValue {
  const local = new Environment(parent);
  for (const binding of block.bindings) {
    local.define(binding.name, evaluate(binding.value, local));
  }
  return evaluate(block.result, local);
}

evaluateBinary cần yêu cầu number một cách tường minh cho arithmetic và ordering, reject chia cho zero nếu đó là policy của Pebble, đồng thời định nghĩa equality mà không dùng JavaScript coercion. Chẳng hạn, 1 == true phải là lỗi hoặc false, không được phụ thuộc vào bất ngờ của host. Các helper tập trung như expectNumber và expectBoolean giữ luật nhất quán.

Đây là tree-walking evaluator: đi qua AST không có loop gồm nn node tốn O(n)O(n) nếu chưa tính function call, còn lookup trong chuỗi environment đơn giản tốn O(d)O(d) với lexical depth dd. Engine thật thường resolve mỗi tên thành lexical slot trước execution, từ đó thay string lookup lặp lại bằng indexed access.

Lexical scope tạo ra closure như thế nào

Dòng quan trọng nhất khi evaluate function là environment. Function value giữ environment tại nơi function được tạo, không phải nơi nó được gọi về sau. Cặp code và captured environment đó chính là closure.

Khi makeAdder(10) chạy, call environment bind x với 10. Evaluate fn(y) bên trong tạo closure trỏ ngược về environment ấy. Lời gọi ngoài kết thúc, nhưng environment vẫn còn reachable qua closure. Sau đó add10(32) bind y trong child scope mới; lookup tìm thấy y gần nhất và tìm x ở captured parent.

text
global: makeAdder, add10
                  |
                  v
captured call: x = 10
                  ^
                  |
new call: y = 32  -> evaluates x + y

Dynamic scope sẽ tìm tên trong environment của caller. Cách này trông có vẻ đơn giản vì function không cần capture, nhưng hành vi lại phụ thuộc vào call path thay vì cấu trúc lồng nhau trong source. Hầu hết ngôn ngữ general-purpose hiện đại chọn lexical scope vì có thể hiểu free variable của function ngay tại nơi định nghĩa.

Tip

Hãy vẽ environment chain khi debug closure. Nếu free variable resolve sai, kiểm tra function đã capture environment nào, lời gọi tạo environment nào và block evaluation có chèn thêm child scope hay không.

Mutation sẽ làm mô hình phức tạp hơn. Khi biến captured có thể thay đổi, nhiều closure phải trỏ đến cùng storage cell thay vì giữ các bản sao value. Pebble không có assignment nên binding immutable và closure identity vẫn rõ ràng. Recursion cũng cần policy riêng: define tên function trước khi tạo closure hoặc thêm một dạng recursive binding chuyên dụng.

Diagnostic, kiểm thử và đường đến compiler

Mọi stage có thể trả cùng một dạng lỗi. Diagnostic tốt cần cho biết phase, vị trí, source line và kỳ vọng đủ cụ thể để người viết sửa chương trình.

ts
export class LanguageError extends Error {
  constructor(
    readonly stage: 'lex' | 'parse' | 'runtime',
    message: string,
    readonly span: Span,
  ) {
    super(message);
  }
}

export function formatError(error: LanguageError, source: string): string {
  const line = source.split(/\r?\n/)[error.span.line - 1] ?? '';
  const caret = `${' '.repeat(Math.max(0, error.span.column - 1))}^`;
  return `${error.stage} error at ${error.span.line}:${error.span.column}: ${error.message}\n${line}\n${caret}`;
}

Parser nên nói token thực tế nó gặp và construct nó đang chờ. Với REPL tương tác, có thể synchronize sau parse error tại ; hoặc } để một lỗi không che mọi diagnostic phía sau. Runtime error phải mang span của operation trong AST, không phải current token, vì token stream không còn là representation đang chạy.

Test cần đi xuyên qua các stage bên cạnh unit test từng phần:

ts
import { describe, expect, it } from 'vitest';
import { run } from '../src/run.js';

describe('Pebble', () => {
  it('honors precedence', () => {
    expect(run('1 + 2 * 3;')).toBe(7);
  });

  it('captures lexical bindings', () => {
    expect(run(`
      let makeAdder = fn(x) { fn(y) { x + y } };
      let add10 = makeAdder(10);
      add10(32);
    `)).toBe(42);
  });

  it('does not use caller scope', () => {
    expect(() => run(`
      let f = fn() { missing };
      let caller = fn() { let missing = 1; f() };
      caller();
    `))
      .toThrow("Undefined name 'missing'");
  });

  it('reports arity errors', () => {
    expect(() => run('let id = fn(x) { x }; id();'))
      .toThrow('Expected 1 arguments but received 0');
  });
});

Test thứ ba chỉ đặt missing trong local scope của caller. Ngôn ngữ dùng dynamic scope sẽ tìm thấy tên này, còn Pebble đi theo environment mà f đã capture nên báo undefined name. Semantics của ngôn ngữ nằm trong các quyết định tường minh như vậy, không nằm trong hành vi tình cờ rơi ra từ host implementation.

Khi core đã ổn định, mỗi extension trở thành một thay đổi có ranh giới rõ:

Extension Thay đổi front end Thay đổi runtime
String String token và literal AST node Concatenation và string equality
Assignment Grammar và AST node cho assignment Mutable cell và environment update
Array Cú pháp literal và index Array value, bounds policy
Native function Thường không cần Host callable value và capability boundary
Bytecode Compiler từ AST sang instruction Operand stack, call frame, virtual machine

Compiler có thể tái sử dụng lexer, parser, AST, span và nhiều semantic check. Thay vì recursively evaluate tree, nó emit bytecode, WebAssembly hoặc machine instruction. Bytecode VM trả compilation cost một lần rồi dispatch instruction gọn; JIT thu thập evidence lúc chạy và specialize hot path. Front end trả lời “chương trình nào đã được viết?”, còn interpreter hoặc code generator trả lời “chương trình sẽ chạy bằng cách nào?”.

Những điểm cần nhớ

  • Language implementation là pipeline của các representation tường minh: source, token, AST và runtime value.
  • Lexer phân loại ký tự và giữ span; parser enforce grammar cùng precedence; evaluator enforce runtime semantics.
  • Pratt parsing gom precedence của expression vào một bảng nhỏ, trong khi recursive descent xử lý các grammatical form lớn một cách tự nhiên.
  • Runtime value phải do guest language định nghĩa, không được vô tình thừa hưởng coercion của JavaScript.
  • Lexical environment và environment tại thời điểm định nghĩa được capture chính là cơ chế tạo closure.
  • Diagnostic là một phần của language design. Hãy giữ location từ sớm và gắn runtime failure vào AST span.
  • Test tập trung vào precedence, scope, call và error bảo vệ semantics tốt hơn snapshot của tree nội bộ.
  • Interpreter và compiler có thể chia sẻ cùng front end. Viết interpreter nhỏ cho thấy chính xác nơi một VM hoặc compiler tương lai sẽ bắt đầu.