Trong các trình biên dịch, gấp hằng số (constant folding) là kỹ thuật tối ưu hóa thay các biểu thức chỉ chứa hằng số bằng giá trị đã tính sẵn ngay tại thời điểm biên dịch, thay vì tính lại lúc chạy chương trình.
Cho một đoạn mã ba địa chỉ (TAC) tuyến tính (không có lệnh rẽ nhánh, không có vòng lặp) gồm n dòng lệnh, mỗi dòng có một trong hai dạng:
x = c — gán giá trị c cho biến x;x = a op b — gán giá trị biểu thức cho biến x, với op ∈{+,−,∗}.Trong đó c, a, b mỗi cái là một số nguyên (hằng số) hoặc tên một biến đã được gán giá trị ở một dòng trước đó. Một biến có thể được gán lại nhiều lần; dòng sau ghi đè giá trị của dòng trước.
Vì mọi toán hạng cuối cùng đều quy về hằng số, toàn bộ chương trình có thể "gấp" hoàn toàn. Hãy mô phỏng việc thực thi tuần tự n dòng lệnh và cho biết giá trị hằng số cuối cùng của mỗi biến xuất hiện trong chương trình.
Ví dụ: với
3
x = 5
y = x + 3
z = y * 2
ta có x=5, y=5+3=8, z=8×2=16.
Dòng đầu tiên chứa số nguyên n (0≤n≤1000) — số dòng lệnh.
n dòng tiếp theo, mỗi dòng có dạng x = c hoặc x = a op b như mô tả (các token cách nhau đúng một dấu cách). Tên biến gồm chữ cái thường và chữ số, bắt đầu bằng chữ cái, độ dài không quá 10. Hằng số là số nguyên (có thể âm), trị tuyệt đối không quá 109.
In ra giá trị hằng số cuối cùng của từng biến xuất hiện trong chương trình, mỗi biến một dòng theo định dạng x = value, theo đúng thứ tự biến đó xuất hiện lần đầu ở vế trái của một lệnh gán. Nếu n=0 thì không in gì.
Ví dụ:
Đầu vào:
0
Đầu ra:
Đầu vào:
3
x = 5
y = x + 3
z = y * 2
Đầu ra:
x = 5
y = 8
z = 16
Đang tải editor...