Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [Trình biên dịch] Phân giải tĩnh tên biến qua các khối lồng nhau

    Phân giải tên tĩnh (static name resolution) là bước trình biên dịch xác định, tại mỗi lần một biến được sử dụng trong mã nguồn, nó thực sự tham chiếu đến khai báo cụ thể nào — dựa hoàn toàn vào cấu trúc lồng khối của chương trình (lexical/static scoping), không phụ thuộc giá trị lúc chạy.

    Xét mô hình ngăn xếp phạm vi quen thuộc gồm bốn loại lệnh: BEGIN (đẩy một phạm vi rỗng mới), END (gỡ phạm vi ở đỉnh ngăn xếp, không bao giờ gỡ phạm vi toàn cục), DECL x (khai báo biến x trong phạm vi ở đỉnh ngăn xếp — nếu x đã có trong đúng phạm vi này, khai báo mới sẽ thay thế, "che" khai báo cũ trong chính phạm vi đó), và USE x (một lượt sử dụng biến x).

    Đánh số các dòng lệnh từ 111 đến nnn theo thứ tự trong input. Với mỗi lệnh USE x, hãy xác định số hiệu dòng lệnh của lệnh DECL x mà nó tham chiếu đến, theo quy tắc: tìm phạm vi gần nhất (từ đỉnh ngăn xếp ra ngoài) có chứa một khai báo của x; trong phạm vi đó, lấy khai báo x gần nhất về thời gian (dòng lệnh DECL x lớn nhất đã thực hiện trong phạm vi đó, tính đến thời điểm hiện tại) làm kết quả. Nếu không phạm vi nào (kể cả toàn cục) từng khai báo x, in ra −1-1−1.

    Ví dụ: với dãy lệnh

    9
DECL x
BEGIN
USE x
DECL x
USE x
BEGIN
USE x
END
USE x

    lệnh 333 (USE x) chưa có khai báo nào trong khối con nên tham chiếu đến lệnh 111 (toàn cục); lệnh 444 khai báo x mới trong khối con; lệnh 555 tham chiếu đến lệnh 444; lệnh 777 (trong khối cháu) vẫn tham chiếu đến lệnh 444 (khối con chưa đóng); lệnh 999 (sau khi khối cháu đã đóng ở lệnh 888, khối con vẫn còn mở) vẫn tham chiếu lệnh 444. Kết quả in ra:

    1
4
4
4
    • Định dạng đầu vào:

      Dòng đầu tiên chứa số nguyên nnn (1≤n≤2×1051 \le n \le 2\times10^51≤n≤2×105) — số lệnh. nnn dòng tiếp theo, mỗi dòng là một lệnh dạng BEGIN, END, DECL x, hoặc USE x (x là tên biến không chứa khoảng trắng). Dữ liệu đảm bảo mọi END đều khớp với một BEGIN đã mở trước đó.

    • Định dạng đầu ra:

      Với mỗi lệnh USE x (theo đúng thứ tự xuất hiện), in ra một dòng chứa số hiệu dòng lệnh của khai báo mà nó tham chiếu đến, hoặc −1-1−1 nếu không tìm thấy khai báo nào phù hợp. Nếu input không có lệnh USE nào, không in gì cả (có thể in một dòng trống).

    Ví dụ:

    Đầu vào:

    9
DECL x
BEGIN
USE x
DECL x
USE x
BEGIN
USE x
END
USE x

    Đầu ra:

    1
4
4
4

    Đầu vào:

    3
DECL x
USE x
USE y

    Đầu ra:

    1
-1

    Đang tải editor...