- Dự án tái hiện tutorial “Let’s Build a Compiler” của Jack Crenshaw được công bố trong giai đoạn 1988~1995 bằng Python và WebAssembly
- Bản gốc dùng Pascal và hợp ngữ Motorola 68000, nhưng lần làm lại này chuyển thành mã có thể chạy trong môi trường hiện đại
- Cốt lõi của tutorial là tự triển khai bộ phân tích cú pháp đệ quy xuống (recursive-descent parser) và áp dụng cách tiếp cận sinh mã hợp ngữ thực tế ngay từ giai đoạn đầu
- Cách làm của Crenshaw sử dụng dịch hướng cú pháp (syntax-directed translation), nhưng bộc lộ giới hạn ở giai đoạn xử lý kiểu
- Điểm đáng chú ý của lần tái hiện này là đã phục dựng tutorial kinh điển thành dạng mà các nhà phát triển hiện đại có thể trực tiếp chạy và thử nghiệm
Bối cảnh của tutorial kinh điển
- “Let’s Build a Compiler” của Jack Crenshaw là tài liệu nhập môn xây dựng compiler được công bố trong giai đoạn 1988~1995 và đến nay vẫn thường xuyên được nhắc tới
- Nguyên tác được viết bằng Pascal và xuất ra mã hợp ngữ Motorola 68000
- Sau 35 năm, đến năm 2025, tài liệu này vẫn liên tục được nhắc lại trên Hacker News và các nơi khác
- Tác giả bài viết lần đầu tiếp cận tutorial này vào năm 2003 và bị ấn tượng sâu sắc, sau đó đến năm 2025 đã chuyển lại nó sang Python và WebAssembly
Tái hiện bằng Python và WebAssembly
- Không chỉ dừng ở việc đọc, tác giả còn dịch compiler trong tutorial sang Python và triển khai để xuất ra WebAssembly (WASM)
- Kết quả được công khai trên kho GitHub (eliben/letsbuildacompiler)
- Tệp
TUTORIAL.md giải thích từng phần của bản gốc được ánh xạ sang mã Python như thế nào
- Người dùng có thể vừa đọc tutorial gốc vừa thử nghiệm với mã có thể chạy trực tiếp
Ví dụ ngôn ngữ KISS và đầu ra WASM
- Bài viết đưa ra kết quả biên dịch một chương trình ví dụ của ngôn ngữ KISS do Crenshaw thiết kế bằng phiên bản compiler Python
- Ví dụ bao gồm
procedure, vòng lặp while, cùng truyền tham trị và truyền tham chiếu
- Phần văn bản WASM được tạo ra có chứa logic xử lý tham số tham chiếu (by-reference parameter) và hầu như không có tối ưu hóa nào được áp dụng
- Biến toàn cục
X được trả về ngầm trong hàm main là một cơ chế để thuận tiện cho việc kiểm thử
- Mã WASM sinh ra được dùng trong các bài kiểm thử xác minh kết quả mong đợi thông qua chạy thực tế
Điểm mạnh của tutorial
- Tutorial của Crenshaw xây dựng bộ phân tích cú pháp đệ quy xuống theo từng bước, tập trung vào sinh mã chạy được trực tiếp hơn là lý thuyết phức tạp
- Vào thời điểm đó,
lex và yacc được xem là tiêu chuẩn, nhưng sự đơn giản và rõ ràng của parser tự viết tay đã tạo ảnh hưởng lớn
- Trong 20 năm sau đó, tác giả tiếp tục ưa chuộng parser đệ quy xuống viết thủ công
- Ngoài ra, trong khi phần lớn bài giảng thời đó tập trung vào phân tích cú pháp, Crenshaw lại đề cập đến sinh mã hợp ngữ ngay từ giai đoạn đầu
Giới hạn và khả năng cải thiện
- Tutorial sử dụng cách dịch hướng cú pháp (syntax-directed translation) để sinh mã ngay trong lúc phân tích cú pháp
- Cách tiếp cận này hữu ích cho việc học, nhưng có giới hạn là khó tối ưu hóa vì không thể biết trước thông tin kiểu
- Đặc biệt từ phần 14, khi kiểu dữ liệu được đưa vào, bắt đầu lộ rõ nhu cầu về cách tiếp cận có cấu trúc hơn với biểu diễn trung gian (IR) hoặc AST
- Không có lý do chính thức nào được nêu ra về việc Crenshaw dừng tutorial sau phần 14, nhưng bài viết có nhắc đến khả năng điều này liên quan tới giới hạn trên
- Tác giả đánh giá rằng lấy phần 14 làm bước ngoặt để tạo AST rồi thực hiện kiểm tra kiểu và sinh mã sẽ là hướng tiếp cận phù hợp hơn
Kết luận
- Tutorial gốc vẫn giữ được tính dễ đọc và tính thực tiễn xuất sắc như một tài liệu nhập môn xây dựng compiler
- Phiên bản Python·WASM lần này là một bản hiện đại hóa giúp các nhà phát triển ngày nay học tập mà không cần phụ thuộc vào công nghệ cũ
- Bất kỳ ai cũng có thể thử nghiệm qua kho GitHub, và đây được xem là một cách diễn giải hiện đại cho phép trực tiếp trải nghiệm cấu trúc của compiler
1 bình luận
Ý kiến trên Hacker News
Tôi thích kiểu tutorial không sa đà vào các chi tiết frontend mà tạo ra mã assembly chạy được ngay từ đầu
Cách tiếp cận mở rộng dần bằng cách xây dựng toàn bộ hệ thống từ một phần rất nhỏ của ngôn ngữ, giống như hướng của Ghuloum, đặc biệt hấp dẫn
Một cuốn sách hay tôi mới tìm thấy là ở đây; dù C và x86 không phải đích nhắm tối ưu nhất cho người mới bắt đầu, đây vẫn là tài liệu rất tuyệt để làm compiler đầu tiên
Tham khảo thêm, bài báo của Ghuloum ở đây
Trước kia parsing là phần quan trọng nhất nên chương trình đào tạo được thiết kế như vậy, nhưng ngày nay việc triển khai các tính năng của ngôn ngữ quan trọng hơn
Kể cả khi tự viết compiler, giờ đã là thời đại có thể nói “Claude, hãy tạo cho tôi một recursive descent parser với cú pháp này” và gần như có kết quả ngay trong một lần
Giới học thuật có xu hướng tiếp cận theo layer, còn người làm thực tế thiên về pipe
Cách layer cho ra mã có thể build được nhưng khó chạy, còn cách pipe thì dễ chạy hơn nhưng kém cấu trúc hơn
Cuối cùng, điều cốt lõi là chia việc phát triển thành các đơn vị tối thiểu có thể chạy được
Tôi nghĩ bài này thực sự chỉ ra đúng trọng tâm
Tôi đã quan tâm đến compiler từ trước khi vào đại học, và tài liệu này là phần nhập môn dễ tiếp cận nhất mà tôi từng thấy
Năm 17 tuổi, khi tự viết recursive descent parser, tôi nhận ra rằng ngay cả những vấn đề trông rất phức tạp cũng trở nên đơn giản nếu tách chúng thành những primitive đúng đắn
Tài liệu về thuật toán thì nhiều, nhưng tài liệu nói về cách tiếp cận vấn đề bằng primitive lại rất ít
Trước đây các table-driven parser như yacc từng là chủ đạo, nhưng ngày nay recursive descent thực dụng và linh hoạt hơn
Nhờ sinh mã bằng LLM mà cách tiếp cận này càng trở nên dễ hơn
Với compiler đồ chơi phục vụ học tập, bỏ qua AST, IR và tối ưu hóa để đi thẳng tới sinh mã vẫn đủ mang lại nhiều giá trị
Trước đây khi làm một công cụ kiểm thử trong công ty hỗ trợ tập con của C, tôi để parser trả về cấu trúc dữ liệu có thể thực thi thay vì sinh mã
Ví dụ, lớp ForLoopStatement chứa testExpression, và trong phương thức Execute() sẽ gọi trực tiếp nó
Đây cũng là bài báo quan trọng được nhắc đến trong The Mythical Man-Month của Fred Brooks
Về mặt khái niệm nó rất tự nhiên và gọn gàng
Phần giải thích rằng tutorial của Jack Crenshaw dùng cách syntax-directed translation khá thú vị
Tôi tò mò không biết điều đó chỉ đơn giản có nghĩa là compiler một lượt hay còn là một khái niệm cụ thể hơn
Tôi hiểu rằng trong ngôn ngữ kiểu tĩnh sẽ khó tối ưu hóa dựa trên kiểu, nhưng cũng muốn biết liệu mức độ kiểm tra kiểu có bị hạn chế không
Nhưng nếu không có IR thì các tối ưu hóa nâng cao như LICM, CSE, GVN là không thể
Cá nhân tôi thích kiểu biên dịch 2 lượt theo từng hàm hơn — lượt đầu tạo IR, sau đó sinh mã ngay và bỏ trạng thái đi, nhờ vậy vừa nhanh vừa hiệu quả
Một compiler một lượt vẫn có thể tách các giai đoạn riêng ra và chỉ sinh mã ở bước cuối
Tutorial của Crenshaw không đi tới mức thực dụng hoàn chỉnh, nhưng nếu mở rộng bằng kỹ thuật precedence climbing thì sẽ hữu ích hơn nhiều
Bài viết liên quan được tổng hợp rất tốt ở đây
Tôi đã xem lại các chủ đề về “Let’s Build a Compiler”
Có lịch sử nhiều lần lên HN từ năm 2007 đến 2023
Đặc biệt, cuộc phỏng vấn Jack Crenshaw tuy không có bình luận nhưng là một bài đọc rất thú vị
Xin phép giới thiệu và quảng bá dự án cá nhân: cwerg.org
Dự án dùng Python và recursive descent parsing, đồng thời tách frontend và backend bằng IR
Nó tạo ELF binary cho x86 và ARM, hướng tới sử dụng thực tế
Tuy vậy nó khá phức tạp và không theo phong cách tutorial
Tôi còn nhớ hồi xưa đã học tutorial của Jack Crenshaw qua nhóm tin USENET comp.compilers
Nhân tiện, nhóm đó đến giờ vẫn còn hoạt động
Nếu muốn một cách tiếp cận compiler hiện đại hơn, tôi khuyên đọc bài blog của Cornell này
Mỗi lần dùng nó tôi đều có cảm giác như chỉ đang đặt thêm vài viên đá lên kim tự tháp
Các ngôn ngữ dùng LLVM làm backend đều có điểm chung là tốc độ biên dịch chậm
Zig đã nhận ra điều này và đang phát triển backend riêng, còn Rust vẫn bị trói buộc với việc biên dịch chậm
Theo tôi, LLVM tạo ra ảo giác rằng độ phức tạp sẽ đảm bảo chất lượng, đồng thời là một công nghệ làm suy yếu tính tự chủ của lập trình viên
Nó cũng giống với một số công nghệ phổ biến khác có cùng chữ cái đầu
Tôi cũng đã viết một tutorial tên là tiny-optimizing-compiler vì lý do tương tự
Đây là ví dụ ngắn gọn chỉ tập trung vào các giai đoạn trung gian và backend của compiler
Liên kết GitHub
Khi còn nhỏ tôi đã in tutorial này ra và mang theo để đọc
Cảm giác nhìn thấy một compiler được hoàn thành trong thời gian ngắn thật sự rất tuyệt
Những tài liệu kiểu này, giống như Beej’s Guide, là một trong những tài liệu giá trị nhất trong giáo dục CS, nhưng lại chưa được đánh giá xứng đáng