Pratt parsing: Kỹ thuật phân tích cú pháp mà ít trường dạy nhưng cực kỳ hữu ích

Trong thế giới phát triển trình biên dịch, có một kỹ thuật phân tích cú pháp (parser) khá nổi tiếng nhưng lại hiếm khi được giảng dạy trong các khóa học khoa học máy tính chính quy: Pratt parsing. Một lập trình viên mới đây đã ghi lại những quan sát của mình khi tự học kỹ thuật này để xây dựng một parser cho biểu thức ngôn ngữ C — và có thể tiến xa hơn thành một trình biên dịch hoàn chỉnh.

Bài viết bắt đầu từ một nhận xét thú vị: ngay cả "Dragon Book" — cuốn sách kinh điển về trình biên dịch — cũng không đề cập đến Pratt parsing. Hầu hết các khóa học lập trình chỉ dạy LR parsing hoặc recursive descent, tùy vào mức độ hàn lâm. Pratt parsing chủ yếu xuất hiện trong giới phát triển trình biên dịch (compiler dev) và lý thuyết ngôn ngữ lập trình (PLT), với tài liệu tham khảo phổ biến nhất là cuốn Crafting Interpreters.

Từ shunting yard đến Pratt parsing

Tác giả bắt đầu bằng việc giải thích thuật toán shunting yard — phương pháp chuyển biểu thức trung tố sang hậu tố bằng cách dùng một ngăn xếp toán tử (operator stack) tường minh. Mỗi toán tử có một binding power (độ ưu tiên kết hợp), ví dụ * có binding power cao hơn +.

Với shunting yard: nếu gặp toán tử có binding power cao hơn đỉnh ngăn xếp thì đẩy vào; nếu thấp hơn hoặc bằng thì lần lượt đẩy các toán tử ra ngoài cho đến khi thỏa mãn điều kiện.

Vấn đề của shunting yard là khó mở rộng. Thuật toán gốc không có khái niệm "biểu thức con" theo nghĩa đệ quy. Khi thêm dấu ngoặc đơn, bạn phải gắn logic đặc biệt vào token ). Các hành vi phức tạp hơn như toán tử một ngôi (unary), biểu thức kết hợp phải (right-associative), hay hàm với số tham số thay đổi sẽ khiến mã nguồn trở nên rối rắm.

Điểm chuyển hóa cốt lõi của Pratt parsing chính là: thay ngăn xếp toán tử tường minh bằng call stack của ngôn ngữ lập trình. Mỗi khi cần xử lý một biểu thức con, parser gọi đệ quy. Việc "tháo ngăn xếp" trong shunting yard tương đương với "return" khỏi lời gọi đệ quy trong Pratt parser.

Ưu điểm vượt trội so với recursive descent

Điều thú vị là Pratt parser không lồng nhau qua từng mức ưu tiên cho mọi biểu thức như recursive descent truyền thống, mà chỉ đệ quy khi thực sự bước vào biểu thức con.

• Ít tầng gọi hàm hơn: hiệu năng tốt hơn một chút
• Cấu trúc mã nguồn rõ ràng, dễ bảo trì hơn
• Phù hợp với ngôn ngữ có nhiều toán tử và mức ưu tiên phức tạp

Tác giả cũng chỉ ra hai điểm mạnh cốt lõi của Pratt parsing, dựa trên các khái niệm gốc trong bài báo của Vaughan Pratt:

• Nuds (null denotation): xử lý toán tử tiền tố (prefix) trong nửa đầu của hàm expr()
• Leds (left denotation): xử lý toán tử trung tố/hậu tố trong nửa sau

Về cơ bản, cấu trúc hàm expr() được chia làm hai phần:

if (prefix token) { xử lý toán tử tiền tố }
while (left_bindpower < binding_power(cur)) { xử lý toán tử trung tố/hậu tố }

Khả năng mở rộng linh hoạt

Điều tác giả ấn tượng nhất là khả năng gán mã xử lý tùy ý cho từng toán tử ngay khi gặp, giống hệt recursive descent, nhưng vẫn giữ được cấu trúc gọn gàng. Thêm toán tử một ngôi hay hậu tố chỉ cần sửa nhỏ trong phần xử lý tiền tố/hậu tố.

Theo tác giả, để mở rộng thêm nữa, có thể "gộp" hàm get_bindpower() với việc chọn hàm con (subroutine) tương ứng, lưu mỗi quy tắc như một struct chứa binding power, hàm xử lý tiền tố và hàm xử lý hậu tố. Phần lõi giữ nguyên đơn giản trong khi mỗi toán tử chạy độc lập trong hàm riêng.

Góc nhìn cho lập trình viên Việt Nam

Với những ai đang học hoặc làm việc ở mảng phát triển trình biên dịch, công cụ lập trình (IDE, linter), hoặc xử lý biểu thức trong các hệ thống cấu hình, Pratt parsing là một kỹ thuật đáng để nghiên cứu thêm. Đây cũng là ví dụ điển hình cho việc kiến thức chuyên sâu thường nằm ngoài giáo trình chuẩn — bạn phải chủ động đọc các bài báo gốc (như bài của Pratt) và tài liệu cộng đồng để tiếp cận.

Tác giả cũng nhắn nhủ rằng sẽ cập nhật thêm một ví dụ có cấu trúc gọn gàng hơn trong kho mã nguồn của mình, mở rộng ngữ pháp biểu thức với toán tử một ngôi +, - và hậu tố !. Bài viết là một chia sẻ chân thành: từ một người muốn ghi lại trải nghiệm học tập để không quên, đến một hướng dẫn nhỏ cho bất kỳ ai muốn tìm hiểu về parser.