Tập 53: Parser subset

Có được token stream sạch sẽ, bước tiếp theo là Parser — dựng AST từ tokens. Sprint 82 là cuộc chiến với cấu trúc dữ liệu cây.

Trong JavaScript, AST được biểu diễn rất dễ dàng dưới dạng các nested object động. JavaScript cho phép bạn tạo ra một đối tượng bất kỳ và gán thêm thuộc tính tùy ý lúc runtime. Trong subset DUY, khi chưa có enum hay struct phức tạp ở bản self-host, việc biểu diễn cây cú pháp đòi hỏi chúng tôi phải dùng các mảng phẳng (flat arrays) và các con số ID để giả lập các node liên kết — một kỹ thuật tuy thô ráp nhưng cực kỳ hiệu quả về mặt bộ nhớ và tương thích với subset.

Chúng tôi viết parse_subset.duy và công cụ so sánh duy parse-compare. Parser viết bằng DUY phải xuất ra một bản dump AST dưới dạng JSON, rồi so sánh mã băm (digest) của nó với bản dump của JS parser.

Việc khớp AST khó hơn nhiều so với khớp token, vì chỉ cần lệch một nút ưu tiên toán tử (precedence), cấu trúc cây sẽ khác đi hoàn toàn. Tôi nhớ những đêm ngồi dò từng nút JSON rậm rạp giữa hai đầu ra. Hai file JSON dài hàng nghìn dòng, lệch nhau đúng một nút biểu thức else if bị parser của DUY hiểu lầm thành một block độc lập.

Cơn ác mộng lớn nhất là thuật toán Pratt parser. Do tính toán nhầm token lookahead trong parse_subset.duy, parser đã rơi vào vòng lặp vô hạn khi parse biểu thức toán tử lồng nhau. Bộ nhớ của máy tính bị cạn kiệt trong vài giây, terminal bị treo cứng. Tôi phải chèn hàng loạt lệnh debug in ra màn hình trạng thái token để tìm ra kẽ hở lookahead. Khi sửa thành công lỗi lookahead đó và thấy toàn bộ corpus vượt qua bài kiểm tra parse-compare với 0 mismatch, tôi biết rằng compiler trẻ đã có khả năng đọc và hiểu cấu trúc cú pháp của chính nó một cách chính xác.

---