Bài tập | NEU OJ

Cho $n$ câu lệnh gán ba địa chỉ liên tiếp (không có nhánh, không có vòng lặp), mỗi câu lệnh có dạng:

var = a
var = a OP b, với OP $\in \{+,-,*,\texttt{//}\}$ (// chia lấy phần nguyên kiểu Python, làm tròn về $-\infty$ )

trong đó a, b là số nguyên hằng hoặc tên biến đã xuất hiện ở vế trái của một câu lệnh trước đó (đảm bảo có giá trị xác định tại điểm dùng). Sau $n$ câu lệnh có một tập $k$ biến sống ra (live-out) — những biến bắt buộc phải giữ đúng giá trị sau khi chuỗi lệnh kết thúc (ví dụ vì được dùng ở phần chương trình phía sau, không cho trong đề).

Một câu lệnh var = ... được gọi là sống nếu tồn tại ít nhất một trong hai điều sau: (1) có ít nhất một lần var được đọc (làm toán hạng) ở một câu lệnh sau nó, trước khi var bị một câu lệnh khác ghi đè; hoặc (2) var thuộc tập live-out và không có câu lệnh nào sau nó ghi đè lại var. Các câu lệnh không thỏa gọi là mã chết (dead code) — có thể xoá an toàn mà không ảnh hưởng kết quả cuối cùng.

Cách xác định chính xác (tương đương thuật toán sống ngược chuẩn cho mã tuyến tính): duyệt từ câu lệnh cuối về câu lệnh đầu, duy trì tập live (khởi tạo bằng tập live-out). Tại câu lệnh var = ... đang xét: nếu var $\in$ live thì câu lệnh này sống, sau đó loại var khỏi live rồi thêm mọi biến xuất hiện ở vế phải của câu lệnh đó vào live; nếu var $\notin$ live thì câu lệnh chết và bỏ qua (không thêm gì vào live).

Định dạng đầu vào:
Dòng đầu: $n$ ( $0 \le n \le 1000$ ). $n$ dòng lệnh theo cú pháp trên. Dòng tiếp theo: $k$ ( $0 \le k \le 100$ ) — số biến live-out. $k$ dòng tiếp theo, mỗi dòng một tên biến (có thể trùng lặp giữa các dòng, trùng chỉ tính một lần; biến live-out có thể không xuất hiện ở vế trái câu lệnh nào, khi đó không ảnh hưởng gì).
Định dạng đầu ra:
In ra chỉ số (1-based, theo thứ tự xuất hiện trong đề) của các câu lệnh sống, mỗi chỉ số trên một dòng, theo thứ tự tăng dần. Nếu không có câu lệnh nào sống, in ra một dòng duy nhất NONE.

solution

Đề bài: [Trình biên dịch] Loại bỏ mã chết bằng phân tích sống