solution

Chương trình được biểu diễn bằng một dãy $m$ lệnh, mỗi lệnh thuộc một trong bốn dạng:

• BEGIN: mở một phạm vi (scope) mới, lồng vào phạm vi hiện tại.
• END: đóng phạm vi trong cùng hiện tại (loại bỏ khỏi ngăn xếp phạm vi).
• DECL type name: khai báo biến name kiểu type trong phạm vi hiện tại (đỉnh ngăn xếp phạm vi). Nếu name đã tồn tại trong chính phạm vi này (không xét scope cha), đây là khai báo trùng và bị bỏ qua (giữ nguyên khai báo đầu tiên).
• USE name: tham chiếu biến name. Việc phân giải (name resolution) tìm name bắt đầu từ phạm vi hiện tại, lần lượt ra các phạm vi cha (theo nguyên tắc nearest enclosing scope, tức shadowing: khai báo ở phạm vi trong cùng che khuất khai báo cùng tên ở phạm vi ngoài).

Luôn tồn tại sẵn một phạm vi ngoài cùng (global, độ sâu — depth — bằng 0, không cần BEGIN để mở). Mỗi BEGIN làm tăng độ sâu hiện tại thêm 1; END làm giảm 1. Input đảm bảo hợp lệ về cặp BEGIN/END (không END khi đang ở phạm vi global, số END không vượt số BEGIN đã mở tương ứng).

Với mỗi lệnh USE name, in kết quả phân giải: nếu tìm thấy khai báo gần nhất, in kiểu và độ sâu của phạm vi chứa khai báo đó; nếu không tìm thấy ở bất kỳ phạm vi nào (kể cả global), báo NOT_FOUND.

Ví dụ: DECL int x; BEGIN; DECL double x; USE x (tìm thấy x kiểu double ở depth 1); END; USE x (nay tìm thấy x kiểu int ở depth 0 — phạm vi global); USE y (không tìm thấy).