Muốn Viết một Trình Biên Dịch? Chỉ Cần Đọc Hai Tài Liệu Này

Việc xây dựng một trình biên dịch (compiler) thường bị coi là một trong những thử thách khó nhằn nhất trong lĩnh vực khoa học máy tính. Tuy nhiên, điều này phần nhiều xuất phát từ cách tài liệu được trình bày hơn là bản chất của vấn đề.

Khi các lập trình viên mới tìm hiểu về viết trình biên dịch, họ thường vấp phải những cuốn sách giáo khảo dày cộp như bộ The Art of Computer Programming của Knuth hay cuốn Dragon Book (Sách Rồng) nổi tiếng. Những tài liệu này tuy xuất sắc nhưng lại quá rộng, bao trùm quá nhiều lý thuyết từ biểu thức chính quy, máy trạng thái đến các loại ngữ pháp phức tạp. Sau khi đọc xong, bạn có thể cảm thấy kiến thức của mình đã mở rộng, nhưng vẫn không gần hơn đến việc viết được một trình biên dịch hoạt động.

Không ngạc nhiên khi sự khó hiểu của các cuốn sách này đã dẫn đến một định kiến phổ biến: viết trình biên dịch là việc cực kỳ khó khăn.

Nguồn tài liệu tốt nhất để phá vỡ định kiến này chính là chuỗi bài viết "Let's Build a Compiler!" của Jack Crenshaw, xuất bản từ năm 1988. Đây là một trong những kiệt tác của văn viết kỹ thuật, nơi một chủ đề vốn được cho là phức tạp bỗng trở nên phù hợp với sinh viên năm nhất. Crenshaw tập trung vào các trình biên dịch theo phong cách Turbo Pascal: biên dịch một lượt (single pass), kết hợp phân tích cú pháp và sinh mã lẫn nhau, và chỉ áp dụng những tối ưu hóa cơ bản nhất cho mã đầu ra.

Các hướng dẫn ban đầu sử dụng ngôn ngữ Pascal làm ngôn ngữ triển khai, nhưng hiện nay đã có phiên bản C, và nếu bạn thích mạo hiểm, Marcel Hendix đã chuyển đổi sang ngôn ngữ Forth. Vì Forth là ngôn ngữ tương tác, việc thực nghiệm và hiểu mã nguồn của nó thậm chí còn dễ hơn so với C hay Pascal.

Tuy nhiên, chuỗi bài của Crenshaw có một điểm thiếu sót lớn: hoàn toàn không có biểu diễn nội bộ của chương trình. Nói cách khác, không có Cây cú pháp trừu tượng (AST - Abstract Syntax Tree). Về mặt lý thuyết, bạn có thể bỏ qua bước này nếu chấp nhận hy sinh tính linh hoạt, nhưng lý do chính nó không xuất hiện trong hướng dẫn là vì việc thao tác trên cây trong Pascal khá phức tạp và không đồng bộ với sự đơn giản của phần mã còn lại.

Nếu bạn làm việc với một ngôn ngữ cấp cao hơn—như Python, Ruby, Erlang, Haskell hay Lisp—lo lắng này sẽ biến mất. Việc tạo và thao tác trên các biểu diễn dữ liệu dạng cây trở nên cực kỳ dễ dàng. Thực tế, đây chính là mục đích thiết kế của Lisp, Erlang và Haskell.

Điều này dẫn chúng ta đến tài liệu thứ hai: "A Nanopass Framework for Compiler Education" (Một khung Nanopass cho giáo dục trình biên dịch) của Sarkar, Waddell và Dybvig. Các chi tiết kỹ thuật của bài báo này không quan trọng bằng khái niệm chung mà nó đề xuất: một trình biên dịch không gì khác hơn là một chuỗi các biến đổi đối với biểu diễn nội bộ của chương trình.

Các tác giả khuyến nghị sử dụng hàng chục, thậm chí hàng trăm lượt biên dịch (compiler passes), trong đó mỗi lượt càng đơn giản càng tốt. Đừng kết hợp các biến đổi lại với nhau; hãy giữ cho chúng tách biệt. Khung Nanopass được đề cập trong tiêu đề là một cách để xác định đầu vào và đầu ra cho mỗi lượt xử lý. Mã nguồn minh họa được viết bằng ngôn ngữ Scheme, một ngôn ngữ kiểu động, nơi dữ liệu được xác thực tại thời điểm chạy.

Sau khi viết được một hoặc hai trình biên dịch, lúc đó hãy cân nhắc bỏ tiền mua cuốn Dragon Book huyền thoại hoặc một số lựa chọn thay thế khác. Có lẽ vậy. Hoặc có thể bạn sẽ không cần chúng nữa.

"Đó không phải là công nghệ vì chính công nghệ. Đó là khả năng hiện thực hóa ý tưởng của bạn."