solution

Sau khi sinh mã trung gian, trình biên dịch thường thực hiện một bước tối ưu cục bộ gồm gấp hằng số (constant folding) và đơn giản hoá đại số (algebraic simplification) trên cây cú pháp trước khi phát sinh mã máy ảo cuối cùng, nhằm loại bỏ các phép tính thừa đã biết trước kết quả tại thời điểm biên dịch.

Cho một biểu thức hậu tố với toán hạng là hằng số nguyên (có thể âm) hoặc biến (một chuỗi chữ cái thường), và các toán tử hai ngôi + - * /, hãy dựng cây cú pháp rồi đơn giản hoá cây đó theo đúng thứ tự hậu thứ tự (xử lý xong hai cây con trước, rồi mới xét tới nút cha), áp dụng cho mỗi nút toán tử các quy tắc sau, theo đúng thứ tự ưu tiên liệt kê (dừng ở quy tắc đầu tiên khớp):

1. Nếu cả hai con (sau khi đã đơn giản hoá) đều là hằng số $a, b$: gấp thành một hằng số duy nhất bằng giá trị $a+b$, $a-b$, $a \times b$, hoặc $a \;/\; b$ (chia lấy phần nguyên kiểu Python, làm tròn xuống) tương ứng với toán tử của nút.
2. Toán tử +, con trái là hằng số $0$ $\Rightarrow$ kết quả là con phải.
3. Toán tử +, con phải là hằng số $0$ $\Rightarrow$ kết quả là con trái.
4. Toán tử -, con phải là hằng số $0$ $\Rightarrow$ kết quả là con trái.
5. Toán tử *, con trái hoặc con phải là hằng số $0$ $\Rightarrow$ kết quả là hằng số $0$ (bất kể toán hạng còn lại là gì, kể cả một cây con phức tạp).
6. Toán tử *, con trái là hằng số $1$ $\Rightarrow$ kết quả là con phải.
7. Toán tử *, con phải là hằng số $1$ $\Rightarrow$ kết quả là con trái.
8. Toán tử /, con phải là hằng số $1$ $\Rightarrow$ kết quả là con trái.
9. Nếu không quy tắc nào khớp: giữ nguyên nút toán tử với hai con đã đơn giản hoá.

Sau khi có cây đã đơn giản hoá hoàn toàn, sinh mã máy ảo ngăn xếp bằng cách duyệt hậu thứ tự cây kết quả: nút hằng số $v$ sinh lệnh PUSH v; nút biến name sinh lệnh LOAD name; nút toán tử (sau khi đã sinh mã của con trái rồi con phải) sinh lệnh tương ứng ADD, SUB, MUL, hoặc DIV.

Ví dụ: biểu thức hậu tố y 1 * đơn giản hoá còn lại đúng biến y (quy tắc 6), nên mã sinh ra chỉ có một dòng LOAD y.