Yantra: Trình tạo bộ phân tích cú pháp LALR(1) mới cho C++

Giấy phép MIT

Trong thế giới phát triển trình biên dịch và các công cụ xử lý ngôn ngữ, việc tạo ra một bộ phân tích cú pháp (parser) hiệu quả luôn là bài toán tốn nhiều công sức. Mới đây, một dự án mang tên Yantra đã được giới thiệu trên Hacker News, hứa hẹn mang đến cách tiếp cận mới cho các lập trình viên C++ làm việc với ngữ pháp hình thức.

Yantra là một trình tạo trình biên dịch (compiler compiler) và bộ sinh parser LALR(1) được viết hoàn toàn bằng C++, với điểm nhấn là khả năng sinh ra lexer, parser và bộ duyệt AST chỉ từ một công cụ duy nhất.

Điểm khác biệt cốt lõi: Xây dựng AST trước, duyệt sau

Điểm làm nên sự khác biệt của Yantra so với các công cụ truyền thống như Yacc, Bison hay Lemon nằm ở thứ tự thực thi các hành động ngữ nghĩa (semantic actions).

Hầu hết các bộ sinh parser LALR(1) đều chạy hành động ngữ nghĩa trong lúc phân tích, ngay khi mỗi quy tắc được rút gọn theo hướng bottom-up. Điều này đồng nghĩa với việc khi hành động của một quy tắc được gọi, bạn chưa biết nút cha của nó trông như thế nào. Hệ quả là lập trình viên thường phải tự xây dựng các lớp AST thủ công và thực hiện thêm một lượt duyệt riêng biệt khi cần nhìn về các nút anh em hoặc trì hoãn quyết định cho đến khi có đủ ngữ cảnh.

"Yantra luôn xây dựng toàn bộ AST trước, sau đó duyệt nó theo hướng top-down trong một lượt riêng, gọi các hành động ngữ nghĩa khi đi qua. Nhờ đó, hành động của một quy tắc cha có thể chạy trước khi các nút con được thăm."

Điều này cho phép một ngữ pháp duy nhất có thể định nghĩa nhiều bộ duyệt khác nhau — ví dụ một bộ sinh mã C++, một bộ khác sinh mã Java — từ cùng một lần phân tích. Cả AST lẫn các lớp bộ duyệt đều được Yantra sinh tự động.

Ví dụ minh họa trực quan

Với đoạn ngữ pháp đơn giản xử lý phép cộng:

expr := expr(a) PLUS expr(b)
%{
    std::cout << "Đang cộng" << std::endl;
%}

expr := NUMBER(N)
%{
    std::cout << "Số: " << N.text << std::endl;
%}

Khi chạy trên chuỗi đầu vào "1 + 2 + 3", kết quả in ra sẽ là:

Đang cộng
Số: 1
Đang cộng
Số: 2
Số: 3

Điểm đáng chú ý là dòng "Đang cộng" ở nút gốc của cây in ra đầu tiên, trước cả hai nút con. Đây là điều chỉ có thể xảy ra khi toàn bộ cây đã tồn tại trước khi bất kỳ hành động nào được thực thi. Với một parser viết tay theo kiểu đệ quy hoặc bottom-up, lập trình viên sẽ phải xây dựng thêm các lớp AST và một lượt duyệt riêng để đạt được thứ tự này.

Các tính năng nổi bật khác

Phiên bản hiện tại

Bên cạnh cơ chế duyệt AST độc đáo, Yantra còn sở hữu nhiều tính năng đáng chú ý:

• Lexer tích hợp với hỗ trợ chế độ (mode) cho các cấu trúc như chú thích lồng nhiều dòng
• Hỗ trợ UNICODE/UTF8 sẵn có cho đầu vào
• Lexer hướng push — đọc từng ký tự và đẩy token cho parser ngay khi hoàn thành, hữu ích khi xử lý dữ liệu đến theo luồng (ví dụ từ socket)
• Chế độ amalgamated cho phép sinh toàn bộ parser thành một tệp .cpp duy nhất kèm hàm main() đầy đủ
• Chế độ thông thường sinh ra các tệp .hpp và .cpp riêng biệt, sẵn sàng tích hợp vào dự án hiện có
• Chuẩn C++23, không phụ thuộc ngoài thư viện chuẩn

Trạng thái CI

So sánh với các công cụ khác

So với họ LALR(1) cổ điển (Bison/Yacc/Lemon): Đây là nhóm mà Yantra nhắm tới trực tiếp, với Lemon của SQLite là nguồn cảm hứng chính. Sự khác biệt mấu chốt nằm ở thời điểm chạy hành động ngữ nghĩa và khả năng định nghĩa nhiều bộ duyệt từ một ngữ pháp.

So với ANTLR: ANTLR cũng duyệt trên cây cú pháp hoàn chỉnh, nhưng điều này có được nhờ thuật toán LL(*) vốn đã xây dựng cây theo hướng top-down ngay khi phân tích. Yantra đạt được kết quả tương tự từ LALR(1) — một thuật toán bottom-up — mà vẫn giữ được hiệu quả về thời gian và bộ nhớ. Ngoài ra, công cụ sinh mã của ANTLR viết bằng Java, buộc dự án C++ phải cài thêm JVM chỉ để chạy công cụ sinh mã; Yantra là tệp thực thi C++ gốc, không có ràng buộc này.

So với tree-sitter: Đây là bài toán hoàn toàn khác. Tree-sitter được thiết kế cho việc phân tích tăng dần, chịu lỗi, nhúng trong trình soạn thảo và IDE. Yantra không làm phân tích lại tăng dần và cũng không nhắm tới mục tiêu đó.

Lưu ý dành cho người dùng Việt Nam

Đối với các lập trình viên Việt Nam đang làm việc với trình biên dịch, công cụ phát triển ngôn ngữ, hoặc xây dựng các hệ thống xử lý ngôn ngữ tự nhiên, Yantra có thể là một lựa chọn đáng thử. Ưu điểm lớn nhất là không phụ thuộc ngoài thư viện chuẩn C++, giúp việc build đơn giản chỉ với CMake — không cần cài JVM hay các runtime phức tạp, vốn thường là rào cản khi làm việc trên môi trường CI/CD hoặc máy chủ có cấu hình hạn chế.

Tuy nhiên, cần lưu ý rằng dự án còn khá non trẻ (phiên bản 0.5.1, trước 1.0) và chỉ do một người duy nhất phát triển. Tác giả Renji Panicker cũng thẳng thắn chia sẻ: "Tôi thà biết nó hỏng ở đâu còn hơn để nó trông hoàn thiện hơn thực tế." Danh sách các hạn chế đã biết được công bố công khai trong kho mã nguồn.

Giấy phép và tài nguyên

Yantra được phát hành dưới giấy phép MIT, cho phép sử dụng rộng rãi cả trong dự án thương mại. Dự án có đầy đủ tài liệu hướng dẫn theo thứ tự từ Tutorial, Overview, Concepts đến User Manual và Developer Reference. Ngoài ra còn có dự án mẫu lingo và một extension language server do Raj Chaudhuri phát triển, hỗ trợ tô sáng cú pháp cho tệp Yantra trong VS Code, QtCreator và các IDE hỗ trợ giao thức Language Server Protocol.

Với định hướng thiết kế khác biệt và giấy phép mở, Yantra hứa hẹn sẽ là một bổ sung thú vị cho cộng đồng phát triển trình biên dịch, dù vẫn cần thêm thời gian để chứng minh độ ổn định trong các dự án thực tế.