Cho đoạn mã TAC tuyến tính gồm n dòng theo đúng định dạng như bài thông dịch TAC (mỗi dòng x = a hoặc x = a op b, op ∈{+,−,∗,/}, chia nguyên làm tròn về 0, không có chia cho 0). Hãy thực hiện tối ưu hoá gấp hằng số (constant folding) kết hợp lan truyền hằng số (constant propagation) theo đúng thuật toán một lượt (single forward pass) sau, xử lý tuần tự từng dòng và duy trì một bảng ánh xạ "biến đang là hằng số đã biết → giá trị":
x = c với c là hằng số: đánh dấu x là hằng số giá trị c; in nguyên dòng x = c.x = y với y là biến: nếu y hiện đang là hằng số đã biết giá trị v thì đánh dấu x là hằng số giá trị v và in x = v; ngược lại, đánh dấu x không còn là hằng số (xoá khỏi bảng nếu có) và in nguyên dòng x = y.x = y op z: với mỗi toán hạng là biến đang có trong bảng hằng số, thay nó bằng chính giá trị hằng số đó (toán hạng là hằng số có sẵn hoặc biến chưa biết thì giữ nguyên). Nếu sau khi thay, cả hai toán hạng đều là hằng số cụ thể, tính luôn kết quả (theo đúng quy tắc chia nêu trên), đánh dấu x là hằng số giá trị đó và in x = <gia_tri>. Nếu không, đánh dấu x không còn là hằng số (xoá khỏi bảng nếu có) và in dòng đã được thay thế các toán hạng đã biết: x = <toan_hang_1'> op <toan_hang_2'>.Sau khi in đủ n dòng đã tối ưu, in thêm một dòng cuối cho biết số dòng kết quả có dạng ten_bien = so_nguyen (tức số dòng đã được xác định là hằng số cụ thể).
Dòng 1: số nguyên n. n dòng tiếp theo: các lệnh TAC gốc, đúng định dạng mô tả ở trên.
In n dòng lệnh đã được tối ưu (theo đúng thứ tự), sau đó in dòng SO_DONG_HANG_SO = <so dong dang gan hang so trong ket qua>.
Ví dụ:
Đầu vào:
3
a = 5
b = a
c = b + 2
Đầu ra:
a = 5
b = 5
c = 7
SO_DONG_HANG_SO = 3
Đầu vào:
6
a = 3
b = 4
c = a + b
d = c * 2
e = x + 1
f = e - a
Đầu ra:
a = 3
b = 4
c = 7
d = 14
e = x + 1
f = e - 3
SO_DONG_HANG_SO = 4
Đang tải editor...