Bỏ qua tới nội dung chính

Hướng dẫn học chủ đề

Ngôn ngữ lập trình và trình biên dịch

Programming Languages and Compilers

Nâng caokhoảng 56 giờ6 bước

Ngôn ngữ lập trình và trình biên dịch: cách mã nguồn được phân tích, biên dịch và thực thi.

Bắt đầu học

Bạn sẽ học được gì

  • Giải thích các giai đoạn của một trình biên dịch/thông dịch: scanning, parsing, phân tích ngữ nghĩa, sinh mã
  • Viết bộ quét từ vựng (lexer) và bộ phân tích cú pháp (parser) cho một ngôn ngữ đơn giản
  • Cài đặt một trình thông dịch duyệt cây cú pháp (tree-walk interpreter) có biến, hàm, closure và lớp
  • Thiết kế và cài đặt một máy ảo bytecode kèm bộ thu gom rác (garbage collector) đơn giản
  • Phân biệt các chiến lược gán kiểu tĩnh/động (static/dynamic typing) và ràng buộc tên (scope, binding)
  • Áp dụng một kỹ thuật tối ưu hóa mã cơ bản và giải thích đánh đổi giữa thông dịch và biên dịch

Nên học trước

Giới thiệu

Ngôn ngữ lập trình và trình biên dịch là môn học mà bạn thấy lý thuyết hoạt động thật: một văn phạm hình thức (context-free grammar) không còn là bài tập trừu tượng khi nó chính là thứ quyết định if (a) if (b) c; else d; thuộc về if nào. Cách học sâu nhất không phải đọc mà là viết: tự cài một trình thông dịch từ đầu đến cuối.

Một trình thông dịch là gì, thật ra

Mã nguồn (chuỗi ký tự) → token (scanning) → cây cú pháp (parsing) → duyệt cây và thực thi, hoặc dịch cây thành bytecode rồi chạy trên một máy ảo. Mỗi bước là một phép biến đổi biểu diễn, và mỗi bước đều cài được bằng tay trong vài trăm dòng code — không có phép màu nào ẩn giấu bên trong.

Hai cách thực thi, hai đánh đổi

Tree-walk interpreter (duyệt trực tiếp cây cú pháp) dễ viết, dễ debug nhưng chậm. Bytecode VM (biên dịch sang mã máy ảo rồi chạy vòng lặp dispatch) nhanh hơn nhiều nhưng phức tạp hơn — đúng con đường CPython, Ruby MRI hay JVM đã đi. Viết cả hai loại cho cùng một ngôn ngữ là cách tốt nhất để cảm nhận đánh đổi giữa đơn giản và hiệu năng.

Lý thuyết automata quay lại

Bộ quét từ vựng thực chất là một automaton hữu hạn nhận diện biểu thức chính quy; bộ phân tích cú pháp thực chất là xử lý văn phạm phi ngữ cảnh. Nếu từng học lý thuyết tính toán, đây là lúc thấy nó trả nợ bằng code chạy thật.

Giáo trình & sách tham khảo

Xem tất cả trong tab Sách

Giáo trình chính

Crafting Interpreters

Robert Nystrom · 2021

CC BY-NC-NDTrung bìnhTiếng Anh640 trang

Vì sao chọn: Đúng tinh thần lời khuyên tự viết một trình thông dịch là cách học sâu nhất — sách dẫn dắt cài đặt hai trình thông dịch hoàn chỉnh (tree-walk và bytecode VM) cho cùng một ngôn ngữ, bám sát toàn bộ 6 bước. Miễn phí đọc online.

Nên đọc: Chương 4–15 (Phần II: Tree-Walk Interpreter) và Chương 14–15, 26, 30 (trích Phần III: Bytecode VM)

Compilers: Principles, Techniques, and Tools

Alfred V. Aho, Monica S. Lam và 2 tác giả khác · 2006 · Bản thứ 2

Có phíNâng caoTiếng Anh1.000 trang

Tài liệu tham khảo kinh điển khi cần đào sâu lý thuyết hơn mức Crafting Interpreters, đặc biệt phần tối ưu hóa mã và sinh mã máy ở bước 5-6. Sách kinh điển, bản quyền, nên tìm ở thư viện trường.

Nên đọc: Chương 3–4, 9 (chọn lọc: Lexical Analysis, Syntax Analysis, Machine-Independent Optimizations)

Các bước học

Đăng nhập để đánh dấu các bước đã hoàn thành.

  1. Bước 1: Scanning và văn phạm: từ chuỗi ký tự đến token

    khoảng 7 giờ

    Học cách một automaton hữu hạn quét mã nguồn thành token, và ôn lại văn phạm chính quy/phi ngữ cảnh làm nền cho parsing. Bài tập: viết bộ quét từ vựng (lexer) cho một ngôn ngữ biểu thức số học đơn giản, xử lý số, toán tử và khoảng trắng.

  2. Bước 2: Parsing: từ token đến cây cú pháp

    khoảng 9 giờ

    Học văn phạm phi ngữ cảnh, độ ưu tiên/kết hợp toán tử và cách viết parser đệ quy xuống (recursive descent). Bài tập: mở rộng lexer ở bước 1 thành một parser dựng AST cho biểu thức số học có ngoặc và độ ưu tiên toán tử đúng.

  3. Bước 3: Trình thông dịch duyệt cây: biến, câu lệnh, điều khiển luồng

    khoảng 10 giờ

    Mở rộng parser thành một ngôn ngữ đầy đủ: biến, gán, if/while, khối lệnh. Bài tập: cài đặt một trình thông dịch chạy được chương trình có biến, vòng lặp và rẽ nhánh, kèm bộ kiểm thử ít nhất 10 chương trình mẫu.

    • Đọc: Chương 7 Evaluating Expressions, Chương 8 Statements and State, Chương 9 Control Flow — Crafting Interpreters
  4. Bước 4: Hàm, closure và lớp

    khoảng 10 giờ

    Thêm hàm bậc nhất, closure (đóng gói môi trường) và hướng đối tượng (lớp, kế thừa) vào trình thông dịch. Bài tập: viết một chương trình test có closure thật sự cần thiết (ví dụ hàm tạo bộ đếm) và một lớp có kế thừa, chạy đúng trên trình thông dịch của bạn.

    • Đọc: Chương 10 Functions, Chương 11 Resolving and Binding, Chương 12 Classes, Chương 13 Inheritance — Crafting Interpreters
  5. Bước 5: Máy ảo bytecode và thu gom rác

    khoảng 12 giờ

    Học cách biên dịch sang bytecode và chạy bằng một vòng lặp dispatch, cùng thuật toán thu gom rác cơ bản. Bài tập: cài đặt máy ảo bytecode cho ít nhất phần biểu thức số học và biến toàn cục, đo và so sánh tốc độ với bản tree-walk ở bước 3.

    • Đọc: Chương 14 Chunks of Bytecode, Chương 15 A Virtual Machine, Chương 26 Garbage Collection — Crafting Interpreters
  6. Bước 6: Kiểu dữ liệu và tối ưu hóa cơ bản

    khoảng 8 giờ

    Đọc về đánh đổi static vs dynamic typing, và một vài kỹ thuật tối ưu mã cơ bản (constant folding, inline caching). Bài tập: thêm một tối ưu đơn giản vào máy ảo ở bước 5, ví dụ gộp hằng số tại thời điểm biên dịch, và đo mức cải thiện tốc độ.

Khái niệm chính

Scanning (lexical analysis)
Chia chuỗi mã nguồn thành dãy token (từ khóa, định danh, toán tử...), thường cài bằng một automaton hữu hạn.
Parsing
Dựng cây cú pháp (parse tree/AST) từ dãy token theo một văn phạm phi ngữ cảnh, đồng thời phát hiện lỗi cú pháp.
AST (Abstract Syntax Tree)
Biểu diễn cây của chương trình sau khi bỏ chi tiết cú pháp thừa, dùng làm đầu vào cho các giai đoạn sau.
Tree-walk interpreter
Trình thông dịch thực thi trực tiếp bằng cách duyệt đệ quy AST, đơn giản để viết và debug nhưng chậm.
Bytecode và máy ảo (VM)
Biên dịch AST sang một tập lệnh đơn giản (bytecode) rồi thực thi bằng vòng lặp dispatch, nhanh hơn tree-walk.
Closure
Hàm đóng gói cùng môi trường (biến) nơi nó được định nghĩa, cho phép truy cập biến ngoài ngay cả sau khi hàm đó return.
Static vs dynamic typing
Kiểm tra kiểu ở thời điểm biên dịch (static) hay thời điểm chạy (dynamic); đánh đổi giữa an toàn phát hiện sớm và linh hoạt.
Garbage collection
Tự động thu hồi vùng nhớ không còn được tham chiếu, ví dụ bằng thuật toán mark-and-sweep.

Học xong để làm gì

  • Xây dựng ngôn ngữ cấu hình hoặc DSL (domain-specific language) riêng cho sản phẩm
  • Phát triển công cụ phân tích mã tĩnh (linter), formatter, hoặc plugin IDE cần parser thật
  • Tối ưu hiệu năng ứng dụng nhờ hiểu cách trình biên dịch dịch code thành mã máy
  • Xây dựng template engine hoặc query language nội bộ, ví dụ trong ORM
  • Nghiên cứu và phát triển ngôn ngữ lập trình mới hoặc runtime có JIT compiler

Câu hỏi thường gặp

Cần học Lý thuyết tính toán trước không?

Nên có, vì automata hữu hạn và văn phạm phi ngữ cảnh là nền tảng trực tiếp của scanning/parsing. Không cần học sâu — hiểu trực giác là đủ để bắt đầu.

Nên viết trình thông dịch bằng ngôn ngữ nào?

Ngôn ngữ nào bạn thấy thoải mái để debug từng bước là được — Crafting Interpreters dùng Java rồi C, nhưng chuyển ý tưởng sang Python/Rust/Go đều tự nhiên.

Học xong có tự viết được một ngôn ngữ lập trình thật không?

Bạn sẽ viết được một ngôn ngữ nhỏ hoạt động đầy đủ (biến, hàm, lớp, closure) — nền tảng đủ để mở rộng thành DSL thật hoặc hiểu sâu cách Python/JavaScript hoạt động bên trong.

Mất bao lâu?

Khoảng 56 giờ nếu học 8 giờ/tuần trong 7 tuần, phần lớn thời gian là code trình thông dịch.

Chọn nguồn tự học

Thử tự viết một trình thông dịch ngôn ngữ đơn giản là cách học sâu sắc nhất.