solution

Cho một đoạn mã ba địa chỉ (TAC) tuyến tính gồm $n$ câu lệnh, thực thi tuần tự (không có rẽ nhánh, không có vòng lặp). Mỗi câu lệnh có một trong ba dạng:

• x = c: gán hằng số nguyên $c$ cho biến $x$.
• x = INPUT: gán cho $x$ một giá trị đọc từ input thực thi — giá trị này KHÔNG thể biết trước tại thời điểm biên dịch, ta nói $x$ là không xác định.
• x = y op z với op $\in \{+, -, *, /\}$, trong đó $y, z$ mỗi cái là tên một biến đã từng xuất hiện ở vế trái trước đó, hoặc là một hằng số nguyên.

Đây chính là bài toán lan truyền hằng số (constant propagation) mà một trình biên dịch thực hiện: với câu lệnh x = y op z, nếu có ít nhất một trong hai toán hạng $y, z$ là biến không xác định (hoặc là biến chưa từng được gán lần nào — quy ước cũng coi là không xác định), thì kết quả $x$ cũng không xác định, bất kể toán hạng còn lại là gì. Ngược lại, nếu cả hai toán hạng đều có giá trị hằng biết trước, trình biên dịch tính luôn giá trị của $x$ tại thời điểm biên dịch (constant folding): phép chia / lấy phần nguyên làm tròn về 0 (giống ngôn ngữ C, ví dụ $-7/2 = -3$), đề bài đảm bảo không có phép chia cho 0.

Với mỗi biến khác nhau xuất hiện ở vế trái (theo đúng thứ tự lần đầu xuất hiện), hãy cho biết trạng thái cuối cùng của biến đó sau khi toàn bộ $n$ câu lệnh thực thi xong: là một hằng số cụ thể, hay vẫn không xác định.

Ví dụ: với 5 câu lệnh

5
a = 3
b = INPUT
c = a + 2
d = c * 2
e = b + 1

kết quả là:

a=3
b=?
c=5
d=10
e=?

($e$ không xác định vì phụ thuộc vào $b$ là INPUT, mặc dù $c, d$ vẫn tính được vì chỉ phụ thuộc $a$.)