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] Bảng ký hiệu lồng khối cơ bản

    Trong một trình biên dịch, bảng ký hiệu (symbol table) thường được tổ chức thành một ngăn xếp các phạm vi (scope) lồng nhau: mỗi khi trình biên dịch bắt đầu duyệt qua một khối lệnh mới, nó đẩy (push) một phạm vi rỗng vào đỉnh ngăn xếp; khi ra khỏi khối, nó gỡ (pop) phạm vi đó đi. Khi cần tra cứu (lookup) một biến, trình biên dịch tìm từ phạm vi trong cùng (gần nhất, đỉnh ngăn xếp) ra ngoài dần, đúng theo quy tắc định phạm vi tĩnh (static/lexical scoping): nếu phạm vi hiện tại không có biến đó, tìm tiếp ở phạm vi bao ngoài nó, cứ thế đến phạm vi toàn cục.

    Cho một dãy gồm nnn lệnh mô phỏng quá trình biên dịch, mỗi lệnh thuộc một trong bốn dạng sau:

    • BEGIN: mở một khối lệnh mới — đẩy một phạm vi rỗng vào đỉnh ngăn xếp.
    • END: đóng khối lệnh hiện tại — gỡ phạm vi ở đỉnh ngăn xếp (dữ liệu đảm bảo không bao giờ END phạm vi toàn cục).
    • DECL x v: khai báo biến tên x với giá trị v (đều là chuỗi không chứa dấu cách) trong phạm vi hiện tại (đỉnh ngăn xếp). Nếu x đã có sẵn trong đúng phạm vi hiện tại, giá trị mới ghi đè giá trị cũ.
    • USE x: tra cứu biến x theo quy tắc lexical scoping ở trên. In ra giá trị của x ở phạm vi trong cùng nhất tìm thấy; nếu không tìm thấy ở bất kỳ phạm vi nào (kể cả toàn cục), in ra UNDECLARED.

    Ban đầu chỉ có phạm vi toàn cục (không cần lệnh BEGIN để tạo ra nó).

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

    8
DECL x 1
BEGIN
DECL x 2
USE x
END
USE x
DECL y 5
USE y

    kết quả in ra là:

    2
1
5

    vì USE x đầu tiên nằm trong khối con nên thấy x=2 (đã ghi đè cục bộ), USE x thứ hai đã ra khỏi khối con nên quay lại thấy x=1 của phạm vi toàn cục, và USE y thấy y=5 vừa khai báo.

    • Đị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 có một trong các dạng: BEGIN, END, DECL x v, USE x, trong đó x, v là các chuỗi không chứa khoảng trắng, x chỉ gồm chữ cái, chữ số, dấu gạch dưới và bắt đầu bằng chữ cái hoặc gạch dưới. Dữ liệu đảm bảo mọi END đều có một BEGIN mở tương ứng chưa đóng trước đó (không bao giờ END phạm vi toàn cục).

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

      Với mỗi lệnh USE x (theo đúng thứ tự xuất hiện trong input), in ra một dòng: giá trị của x tìm được (giữ nguyên chuỗi v đã khai báo) hoặc UNDECLARED nếu không tìm thấy.

    Ví dụ:

    Đầu vào:

    8
DECL x 1
BEGIN
DECL x 2
USE x
END
USE x
DECL y 5
USE y

    Đầu ra:

    2
1
5

    Đầu vào:

    1
USE x

    Đầu ra:

    UNDECLARED

    Đang tải editor...