solution

Khi trình biên dịch phát sinh mã cho các câu lệnh if/while, nó thường chưa biết trước địa chỉ đích cụ thể của các lệnh nhảy tại thời điểm phát sinh — nó chỉ biết tên nhãn (label) tượng trưng cho vị trí đó. Kỹ thuật backpatching giải quyết việc này bằng cách: phát sinh mã với nhãn tượng trưng trước, rồi sau đó duyệt lại toàn bộ để thay nhãn bằng địa chỉ số cụ thể.

Cho một chương trình bytecode gồm các dòng lệnh theo thứ tự, mỗi dòng là một trong hai dạng:

• LABEL name: đánh dấu vị trí hiện tại bằng tên nhãn name. Dòng này không sinh ra lệnh máy và không chiếm địa chỉ nào trong chương trình đích.
• Một lệnh bất kỳ khác, có thể là JMP name (nhảy không điều kiện tới nhãn), JZ name (nhảy tới nhãn nếu đỉnh ngăn xếp bằng 0), hoặc các lệnh khác không liên quan tới nhãn (ví dụ PUSH x, ADD, ...) — mỗi lệnh loại này chiếm đúng 1 đơn vị địa chỉ trong chương trình đích, đánh số bắt đầu từ $0$ theo đúng thứ tự xuất hiện (bỏ qua các dòng LABEL).

Mỗi tên nhãn được dùng trong JMP/JZ được đảm bảo có đúng một dòng LABEL định nghĩa nó ở đâu đó trong chương trình (có thể ở trước hoặc sau vị trí sử dụng — nhảy tiến hoặc nhảy lùi).

Hãy thực hiện backpatching: in ra chương trình sau khi loại bỏ toàn bộ dòng LABEL, và thay tên nhãn trong mỗi lệnh JMP/JZ bằng địa chỉ số (offset tuyệt đối, đánh số từ 0) mà nhãn đó trỏ tới.

Ví dụ: với chương trình LABEL start, PUSH 1, JZ end, PUSH 2, LABEL end, PUSH 3, các lệnh còn lại được đánh địa chỉ $0,1,2,3$; nhãn end trỏ tới địa chỉ $3$, nên JZ end trở thành JZ 3.