4.8K 193 70

Đã đăng vào Thứ Hai, 3:34 SA 12 phút đọc

Xây dựng một ngôn ngữ lập trình cần những gì

MayFest2026

1. Các thành phần của một ngôn ngữ

Hình dung việc triển khai 1 ngôn ngữ giống như việc leo núi. Bắt đầu từ chân núi với mã nguồn thô, ban đầu chỉ là một chuỗi các ký tự. Mỗi giai đoạn sẽ phân tích và từ từ làm rõ ý nghĩa mà mã nguồn thể hiện.

Khi lên đến đỉnh. Chúng ta có cái nhìn toàn cảnh và có thể hiểu ý nghĩa mã nguồn.

Sau đó, tiếp tục đi xuống phía bên kia ngọn núi. Sẽ là quá trình chuyển đổi biểu diễn bậc cao xuống các dạng cấp thấp hơn và cuối cùng là mã máy.

Quét (Scanning)

Bước đầu tiên là scanning (quét), còn được gọi là lexing, hoặc lexical analysis.

Một bộ quét (scanner hoặc lexer) nhận đầu vào theo từng dòng và nhóm chúng lại thành các token. Một số token là ký tự đơn, như ( và ,. Một số khác có thể dài vài ký tự, như số (123), chuỗi ký tự ("hi!"), và định danh (min).

Một số ký tự không thực sự có ý nghĩa. Ví dụ như khoảng trắng thường và các chú thích (comments). Bộ quét thường loại bỏ những thứ này, để lại một chuỗi gồm các token có ý nghĩa.

Phân tích cú pháp (Parsing)

Bước tiếp theo là parsing. Có thể liên tưởng đến việc phân tích ngữ pháp tiếng Anh, ngoại trừ việc tiếng Anh có hàng ngàn "từ khóa" và vô số sự mơ hồ. Ngôn ngữ lập trình đơn giản hơn nhiều.

Lỗi cú pháp (syntax errors) cũng sẽ được thông báo nếu có.

Đầu ra của bước này thường là một cấu trúc dữ liệu gọi là abstract syntax tree - AST.

AST

Phân tích tĩnh (Static Analysis)

Tại điểm này, dựa vào AST và các token thì có thể biết cấu trúc của code, ví dụ như biểu thức nào lồng trong biểu thức nào. Tuy nhiên, còn nhiều thông tin cần nắm bắt. Ví dụ như một biểu thức a + b, chúng ta biết đang cộng a và b, nhưng không biết những tên đó đề cập đến cái gì. Chúng là biến cục bộ? Biến toàn cục? Chúng được định nghĩa ở đâu?

Phần phân tích đầu tiên mà các ngôn ngữ thường thực hiện gọi là binding hoặc resolution. Tìm nơi các định danh (tên biến/hàm) được định nghĩa và liên kết chúng lại (thỏa mãn điều kiện trong phạm vi - scope).

let x = 10;          // khai báo x ở scope ngoài

function foo() {
    let x = 20;      // khai báo x khác ở scope trong
    console.log(x);  // binding: x này trỏ đến x = 20, không phải x = 10
}

Tiếp theo, nếu là ngôn ngữ tĩnh thì cần phân tích kiểu dữ liệu. Ví dụ nếu kiểu dữ liệu của a hoặc b không hỗ trợ phép + thì báo lỗi. Với các ngôn ngữ động thì kiểu được kiểm tra sau, trong quá trình chạy.

Mọi thứ cho đến thời điểm này được coi là phần frontend. Theo lẽ thường thì mọi thứ tiếp sau đây là back end, nhưng không phải vậy.

Thời kỳ đầu khi các thuật ngữ "front end" và "back end" được đặt ra, trình biên dịch đơn giản hơn nhiều. Sau này, các nhà nghiên cứu đã đề xuất thêm các giai đoạn mới. Thay vì loại bỏ các thuật ngữ cũ, William Wulf và cộng sự đã gộp các giai đoạn mới đó vào cái tên nghe khá thú vị là "phần giữa" (middle end).

Frontend: Phân tích và nắm bắt ý nghĩa của mã nguồn.
Backend: Chuyển đổi mã nguồn sang dạng mã máy để thực thi. Mỗi kiến trúc phần cứng khác nhau lại có kiểu mã máy khác nhau.

Intermediate Representations

Ví dụ với 3 ngôn ngữ lập trình C, Java, Rust + 3 kiến trúc x86, ARM, SPARC thì cần viết 3*3 = 9 compiler khác nhau (C → x86, Java → x86, Rust → x86 ...).

Với IR là một giao diện trung gian, số lượng compiler cần triển khai giảm xuống còn 3 + 3 = 6.

Một số kiểu IR phổ biến

control flow graph
static single-assignment
continuation-passing style
three-address code

Tối ưu hóa (Optimization)

Khi chúng ta đã hiểu chương trình của người dùng muốn làm gì, chúng ta có thể thay thế nó bằng một chương trình khác có cùng ngữ nghĩa nhưng thực hiện hiệu quả hơn => hành động này gọi là tối ưu hóa.

Ví dụ, mã nguồn gốc: pennyArea = 3.14159 * (0.75 / 2) * (0.75 / 2);

Có thể thực hiện tất cả các phép tính số học đó trong trình biên dịch và thay đổi thành: pennyArea = 0.4417860938;.

Tối ưu hóa một trong những mảng khó nhất của ngành ngôn ngữ lập trình. Nhiều chuyên gia dành cả sự nghiệp ở đây để tối ưu từng phần trăm nhỏ một. Ở cuốn sách này chúng ta sẽ tạm thời bỏ qua phần này.

Một số từ khóa nếu muốn tìm hiểu về mảng tối ưu hóa:

constant propagation
common subexpression elimination
loop invariant code motion
global value numbering
strength reduction
scalar replacement of aggregates
dead code elimination
loop unrolling.

P/s: Nhiều ngôn ngữ thành công có rất ít tối ưu hóa ở giai đoạn biên dịch. Ví dụ, Lua và CPython tập trung vào việc cải thiện hiệu năng ở runtime thay vì trình biên dịch.

Code Generation

Là giai đoạn nhằm chuyển đổi IR sang dạng biểu diễn cấp thấp hơn.

Có 2 đầu ra phổ biến hiện nay:

Mã máy (native code): Cực nhanh và có thể thực thi được ngay. Nhược điểm là độ phức tạp cao và phụ thuộc vào kiến trúc CPU (cần viết nhiều compiler cho mỗi kiến trúc).
Virtual machine code (Bytecode): Chậm hơn nhưng không phụ thuộc vào kiến trúc CPU. Có thể viết 1 lần chạy mọi nơi.

Máy ảo (Virtual Machine)

Với bytecode, máy tính vẫn chưa có thể nạp và thực thi được ngay. Dẫn đến có 2 cách tiếp cận

Mini-compiler: Dịch bytecode sang native code. Chỉ cần viết thêm compiler dịch bytecode sang native code cho từng kiến trúc và tái sử dụng lại toàn bộ các phần ở trên.
Virtual Machine: Bytecode được mô phỏng và chạy trên VM (thường được viết bằng C). Do đã có sẵn trình biên dịch C trên các nền tảng nên ko cần quan tâm đến kiến trúc.

Lưu ý: Phân biệt 2 khái niệm virtual machine

System Virtual Machine — giả lập toàn bộ phần cứng và hệ điều hành
Language/Process Virtual Machine — giả lập chip để chạy bytecode

Runtime

Runtime là tập hợp các dịch vụ mà ngôn ngữ cung cấp trong lúc chương trình đang chạy như garbage collector, type tracking, exception handling, thread management... Với ngôn ngữ biên dịch như Go, runtime được đóng gói thẳng vào binary.

Với ngôn ngữ dùng VM như Java hay Python, runtime sống trong VM. Dù theo cách nào, gần như mọi ngôn ngữ hiện đại đều có runtime — sự khác biệt chỉ là nó được đóng gói và phân phối như thế nào.

2 Shortcuts and Alternate Routes

Không phải mọi ngôn ngữ đều đi theo một lộ trình như nhau. Có một vài lối tắt và con đường thay thế.

Single-pass compilers (trình biên dịch một lượt)

Một số trình biên dịch đơn giản gồm quá trình parsing, analysis và code generation để tạo ra mã máy mà không xây dựng AST hay thông qua IR.

Là triết lý thiết kế của 2 ngôn ngữ Pascal và C trong thời đại bộ nhớ vẫn đang còn rất hạn chế.

Ưu điểm: Tiết kiệm bộ nhớ một tối đa
Nhược điểm: Không có thông tin được "nhớ", trình biên dịch chỉ có thể dựa vào thông tin hiện có để hoạt động. Nền Pascal cần khai báo các biến ở đầu và C không thể gọi các hàm được định nghĩa ở phía dưới.

Tree-walk interpreters

Để chạy chương trình, trình thông dịch sẽ duyệt qua từng nút của AST - Abstract Syntax Tree.

Ưu điểm: Dễ hiểu, dễ triển khai do ko cần tạo ra bytecode hay thông qua IR phức tạp. Phù hợp với bài tập sinh viên hay ngôn ngữ nhỏ.
Nhược điểm: Chậm do quá trình duyệt cây.

Các phiên bản đầu tiên của Ruby sử dụng Tree-walk interpreters. Ở phiên bản 1.9, đã chuyển sang YARV (Yet Another Ruby VM) của Koichi Sasada và cải thiện đáng kể hiệu năng. YARV là một VM.

Transpilers

Thay vì viết phần backend vô cùng phức tạp thì có thể chọn cách "đứng trên vai người khổng lồ" bằng cách chuyển mã nguồn qua một ngôn ngữ đã có sẵn trình biên dịch (như C hay Javascript).

Biên dịch JIT (Just-in-time compilation)

Một trong những giải pháp tiên tiến nhất hiện nay. Cơ chế hoạt động của JIT là đợi đến khi chương trình đang được nạp trên máy của người dùng rồi mới tiến hành biên dịch ra mã máy phù hợp với kiến trúc chip của máy đó.

JIT hiện đại không chỉ "dịch bytecode sang native code" mà còn "học" trong lúc chạy và tìm cách tối ưu. Ví dụ như khi phát hiện ra một đoạn code chạy đi chạy lại rất nhiều lần (gọi là hot spot), JIT sẽ tạm dừng và biên dịch lại đoạn đó với những kỹ thuật tối ưu để đạt tốc độ tối đa.

3 Trình biên dịch và Trình thông dịch

Sự khác biệt giữa trình biên dịch và trình thông dịch là gì?

Biên dịch (Compiling) là một kỹ thuật liên quan đến việc dịch một mã nguồn sang một dạng khác (thường là cấp thấp hơn). Khi tạo ra bytecode hoặc mã máy, đó là biên dịch. Khi dùng kỹ thuật transpile, cũng là biên dịch.
Khi chúng ta nói một ngôn ngữ "dùng trình biên dịch", ngụ ý rằng nó dịch mã nguồn sang dạng khác nhưng không thực thi nó. Người dùng phải lấy kết quả đầu ra và tự chạy.
Ngược lại, khi chúng ta nói một ngôn ngữ sử dụng "trình thông dịch", ngụ ý rằng nó nhận mã nguồn và sau đó thực thi.

Ví dụ như CPython. Khi chạy chương trình Python, code được phân tích và chuyển đổi sang bytecode, rồi được thực thi bên trong VM.

Từ góc độ người dùng, đây rõ ràng là một trình thông dịch. Nhưng bên trong, chắc chắn có quá trình biên dịch diễn ra.

=> CPython là một trình thông dịch, và nó có một trình biên dịch.

Nguồn

https://craftinginterpreters.com/a-map-of-the-territory.html

Compiler programing language