Tổng quan quy trình biên dịch

Một hệ thống biên điển hình thường trải qua ba quá trình cốt lõi: Phân tích (Parsing), Chuyển đổi (Transformation) và Tạo mã sinh (Code Generation). Giai đoạn Phân tích lại được chia tách thành hai công đoạn riêng biệt: Phân tích từ vựng (Lexical Analysis) để tách chuỗi ký tự thành các token, và Phân tích cú pháp (Syntactic Analysis) để xác định cấu trúc logic của chương trình. Trong số các kỹ thuật phân tích cú pháp, phương pháp đệ quy giảm xuống (Recursive Descent Parsing) nổi bật nhờ tính trực quan và dễ triển khai.

Lợi thế của kỹ thuật phân tích đệ quy giảm

Đây là phương pháp tiếp cận từ trên xuống, biến từng quy tắc ngữ pháp phức tạp thành một tập hợp các hàm gọi đệ quy. Ưu điểm của mô hình này nằm ở:

• Cấu trúc mạch lạc: Mỗi hàm tương ứng trực tiếp với một quy luật ngôn ngữ cụ thể.
• Dễ dàng theo dõi lỗi: Do phạm vi xử lý hẹp, việc xác định vị trí lỗi cú pháp trở nên nhanh chóng.
• Hiệu quả xử lý: Cho phép kiểm soát luồng thực thi ngay tại thời điểm gặp lỗi.

Dự án the-super-tiny-compiler cung cấp một ví dụ điển hình cho cách áp dụng kỹ thuật này thông qua một lượng mã nguồn tối giản.

Cơ chế hoạt động của bộ phân tích (Parser)

Module Parser trong dự án này tập trung vào việc chuyển đổi danh sách token đầu vào thành Cây Cú Pháp Trừu tượng (AST). Dưới đây là cách thức tổ chức mã nguồn được tinh chỉnh để minh họa rõ hơn về luồng điều khiển.

Hàm khởi tạo bộ phân tích

Chức năng chính bắt đầu bằng việc thiết lập con trỏ truy xuất và định nghĩa hàm đệ quy xử lý từng nút:

function initializeParser(tokenStream) {
  let cursorPosition = 0;

  // Hàm trợ giúp để di chuyển đến token tiếp theo
  const stepForward = () => cursorPosition++;

  // Hàm chủ lực xây dựng các nút của AST
  const buildTree = () => {
    const currentItem = tokenStream[cursorPosition];

    // Xử lý literal số
    if (currentItem.type === 'number') {
      stepForward();
      return {
        type: 'NumberLiteral',
        value: currentItem.value
      };
    }

    // Xử lý literal chuỗi
    if (currentItem.type === 'string') {
      stepForward();
      return {
        type: 'StringLiteral',
        value: currentItem.value
      };
    }

    // Xử lý biểu thức gọi hàm
    if (currentItem.type === 'paren' && currentItem.value === '(') {
      stepForward();
      const nextToken = tokenStream[cursorPosition];
      
      const expressionNode = {
        type: 'CallExpression',
        name: nextToken.value,
        arguments: []
      };
      
      stepForward();
      
      // Vòng lặp phân tích các tham số bên trong ngoặc đơn
      while (
        tokenStream[cursorPosition].value !== ')' ||
        tokenStream[cursorPosition].type !== 'paren'
      ) {
        expressionNode.arguments.push(buildTree());
        
        // Cập nhật token hiện tại
        if (cursorPosition >= tokenStream.length) break;
        const checkToken = tokenStream[cursorPosition];
        if (checkToken.type === 'paren' && checkToken.value === ')') {
           break; 
        }
      }
      
      stepForward(); // Bỏ qua dấu ')'
      return expressionNode;
    }

    throw new TypeError(currentItem.type);
  };

  const rootAst = {
    type: 'Program',
    entries: []
  };

  // Duyệt qua toàn bộ danh sách token để xây dựng thân chương trình
  while (cursorPosition < tokenStream.length) {
    rootAst.entries.push(buildTree());
  }

  return rootAst;
}

Đoạn mã trên sử dụng biến cursorPosition để duy trì trạng thái duyệt, trong khi hàm buildTree chịu trách nhiệm quyết định loại nút cần tạo dựa trên kiểu dữ liệu của token hiện tại. Đối với cấu trúc lồng nhau như lời gọi hàm, hàm sẽ tự gọi lại chính mình để xử lý các đối số.

Ví dụ minh họa luồng dữ liệu

Xét đầu vào Lisp-style dưới dạng token stream: (add 2 (subtract 4 2)). Quá trình xử lý diễn ra như sau:

1. Tìm thấy ký tự mở ngoặc (, khởi tạo nút CallExpression.
2. Token tiếp theo là add, gán vào thuộc tính tên hàm.
3. Bắt đầu phân tích tham số:
   • Tìm thấy số 2 → Tạo nút NumberLiteral.
   • Tìm thấy dấu mở ngoặc ( khác → Đệ quy gọi hàm để phân tích lệnh subtract.
4. Gom nhóm các đối số hoàn tất và trả về nút cha.

Cấu trúc AST cuối cùng thu được sẽ trông như sau:

{
  type: 'Program',
  entries: [
    {
      type: 'CallExpression',
      name: 'add',
      arguments: [
        { type: 'NumberLiteral', value: '2' },
        {
          type: 'CallExpression',
          name: 'subtract',
          arguments: [
            { type: 'NumberLiteral', value: '4' },
            { type: 'NumberLiteral', value: '2' }
          ]
        }
      ]
    }
  ]
}

Đánh giá ưu nhược điểm

Kỹ thuật này mang lại khả năng đọc code cao do sự ánh xạ trực tiếp giữa ngữ pháp và code. Tuy nhiên, nó gặp khó khăn với các quy tắc đệ quy trái (left recursion) và có thể đòi hỏi cơ chế hồi quy (backtracking) trong những trường hợp phức tạp làm giảm hiệu suất. Dự án the-super-tiny-compiler đã khắc phục điều này bằng cách giới hạn ngữ pháp đầu vào chỉ phù hợp với mô hình đệ quy giảm đơn giản.

Cách thức chạy thử nghiệm

Để kiểm tra khả năng hoạt động của bộ phân tích, người dùng thực hiện các thao tác sau trên môi trường Node.js:

# Clone repository local
npm install --global the-super-tiny-compiler
# Hoặc tải source code về thư mục làm việc

# Chạy bộ test tự động
node test.js

Tệp test.js cung cấp bộ kiểm thử đầy đủ, mô phỏng quá trình chuyển đổi từ cú pháp Lisp sang cú pháp tương đương C-style thông qua các giai đoạn biến đổi AST.