Pratt parsing: hộp đen giúp đổi tư duy viết trình phân tích cú pháp

Có một nghịch lý trong cách cộng đồng lập trình viên dạy nhau về Pratt parsing. Đa số tài liệu dành gần như toàn bộ thời gian để giải thích thuật toán, trong khi phần thực sự tạo ra khác biệt lại không được nhắc tới. Tác giả bài viết trên blog cá nhân đã đặt vấn đề này và đưa ra một lời khuyên khá ngược đời: hãy coi Pratt như một hộp đen trước đã.

Thuật toán chỉ chiếm 9 dòng, tư duy mới là phần lớn

Trong bài viết đăng ngày 24/4/2026, tác giả chỉ ra rằng bản thân thuật toán Pratt gói gọn trong khoảng 9 dòng code nếu viết bằng ngôn ngữ bậc cao như Rhombus. Phần còn lại của mọi chương trình là các bảng tra nud (nuôi dưỡng biểu thức từ tiền tố) và led (mở rộng biểu thức từ hậu tố), cùng các hành động ngữ nghĩa gắn với từng loại token.

Chính cách tổ chức này tạo ra những lợi ích mà các kỹ thuật phân tích cú pháp truyền thống khó có được:

• Không còn vấn đề đệ quy trái như ở các bộ phân tích LL(k). Hành động ngữ nghĩa được gọi sau khi token tương ứng đã bị tiêu thụ khỏi luồng, nên đệ quy trái đơn giản là không xảy ra.
• Không cần thử phương án rồi quay lui (backtrack). Bộ phân tích chỉ so sánh các con số và lặp hoặc đệ quy, nên vấn đề đánh đổi giữa tốc độ và bộ nhớ (như PEG so với packrat) biến mất.
• Hành động ngữ nghĩa chỉ chạy đúng một lần, không cần khôi phục trạng thái khi khớp thất bại. Nhờ vậy có thể dùng tác dụng phụ (side-effect), chẳng hạn đánh dấu tên biến theo phạm vi từ vựng thông qua một đối tượng ngữ cảnh dùng chung.
• Hành động ngữ nghĩa luôn biết mình là kết quả khớp đúng, nên có thể nhìn xa tùy ý. Điều này cho phép lồng ghép bộ phân tích PEG hoặc nhiều tầng Pratt bên trong các nud và led.
• Đa số nhập nhằng ngữ pháp trở thành xung đột bảng (table collision), nên ít tốn công xử lý các trường hợp đơn giản hơn.
• Các ô trống trong bảng là điểm mở rộng tự nhiên của ngữ pháp, cho phép hiện thực macro, thậm chí phân tích một ngôn ngữ có thể tự định nghĩa thêm toán tử.

"Bên trái token này ta mong đợi thấy gì?"

Điểm chuyển biến trong tư duy được Douglas Crockford tóm gọn trong câu nói nổi tiếng tại GOTO 2013:

Pratt takes parsing which is a really complicated thing and reduces it to one simple question: What do we expect to see to the left of a token?

Tác giả lấy ví dụ quen thuộc: làm sao phân tích lời gọi hàm khi công cụ chỉ có nud và led, không có luật sinh (production rule)? Quan sát then chốt là dấu mở ngoặc tròn luôn chờ một thứ gì đó ở bên trái, nên nó phải là một led. Đăng ký một led cho dấu ngoặc tròn và phân tích lời gọi hàm từ đó — với người chỉ quen trường phái phân tích truyền thống thì đây không phải điều hiển nhiên.

Cũng theo tác giả, nếu muốn đổi một toán tử từ kết hợp trái sang kết hợp phải, chỉ cần truyền bp - 1 thay vì bp khi phân tích vế phải. Đây là mẹo nghề nghiệp ai cũng nên biết, nhưng lý do nó hoạt động thì "không quan trọng" — ít nhất là trong hôm nay.

Macro có thể đan xen giữa lexer và parser

Một điểm đáng chú ý là Pratt mở đường cho macro mạnh hơn nhiều so với cách hiểu thông thường. Macro của C chỉ là mẫu thay thế văn bản ở tầng lexer; macro của Lisp thao tác trên tầng AST. Macro kiểu Pratt hợp nhất hai thế giới vốn tách rời này: trong lúc mở rộng macro, nó có thể gọi xen kẽ API điều khiển lexer (đọc token) lẫn API điều khiển parser (phân tích và trả về biểu thức).

Theo tác giả, phần này thực ra dễ. Thử thách khó nhất của bất kỳ hệ macro nào nằm ở chỗ khác — vệ sinh macro (hygiene) — chứ không phải phân tích cú pháp.

Lexer bỗng trở nên quan trọng

Thông thường lexer là phần bị xem nhẹ nhất của trình biên dịch, được coi là "bài toán đã giải xong". Nhưng với Pratt thì khác: bản thân thuật toán chỉ là 9 dòng, nên lexer rất có thể đã lớn hơn parser. Hơn nữa, mỗi nud và led đều giống như một bộ phân tích con (subparser), và lexer là điểm chung xuyên qua ranh giới giữa các bộ phân tích con đó.

Kỹ thuật quan trọng nhất mà tác giả khuyên học là modal lexing — thêm tham số vào hàm đọc token để mỗi chế độ kích hoạt bộ luật khác nhau:

// lexer truyền thống
Token Read();

// lexer theo chế độ
// mỗi chế độ kích hoạt bộ luật riêng
Token Read(lex_mode_t mode);

Trong dự án của mình, tác giả thay enum bằng các hàm riêng như next_on_class_scope(), next_on_type_scope(), next_on_expr_scope(), vì thông tin điều phối đã biết hoàn toàn ở thời điểm biên dịch. Cơ chế này cho phép parser phản hồi lại lexer, nhờ đó xử lý được những ngôn ngữ có token xung đột giữa các ngôn ngữ con — ví dụ ngôn ngữ chú thích kiểu trong Rust hay trường hợp toán tử dịch phải của C++11 sinh ra token khác trong ngữ cảnh template.

Một lưu ý: lexer phải theo thiết kế kéo (pull) thay vì đọc hết token trước. Tác giả cũng khuyên không cho lexer làm IO hay đệm dữ liệu, để việc sao chép lexer trở nên rẻ và không có tác dụng phụ — điều kiện cần cho việc nhìn trước tùy ý.

Góc nhìn

Với lập trình viên Việt Nam đang tự viết ngôn ngữ nhỏ, DSL nội bộ hay công cụ phân tích mã nguồn, bài viết này đáng đọc vì nó đảo ngược thứ tự học thông thường. Thay vì cố hiểu sâu cơ chế trước, ta dùng Pratt như một hộp đen và tập trung trả lời câu hỏi "bên trái token này mong đợi gì" — cách tiếp cận này giúp tránh biến Pratt thành một phiên bản khác của precedence climbing.

Điểm đáng lưu ý cho các nhóm kỹ thuật là chi phí bảo trì. Khi ngữ pháp được biểu diễn bằng bảng nud/led thay vì luật sinh, việc thêm một cú pháp mới thường chỉ là điền vào một ô trống, và các ô trống đó còn có thể dùng để hiện thực macro. Đổi lại, nhóm cần thống nhất tư duy ngay từ đầu; nếu mỗi người tự "uốn" thuật toán theo cách riêng thì lợi thế lớn nhất của Pratt sẽ biến mất.