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] Thông dịch máy ảo bytecode có vòng lặp và lời gọi hàm con

    Xây dựng trình thông dịch cho một máy ảo dựa trên ngăn xếp (stack-based VM), thực thi một chương trình bytecode gồm nnn dòng lệnh, đánh số địa chỉ từ 000 đến n−1n-1n−1. Tập lệnh gồm:

    • PUSH k: đẩy số nguyên kkk vào đỉnh ngăn xếp dữ liệu.
    • POP: bỏ giá trị ở đỉnh ngăn xếp.
    • ADD, SUB, MUL, DIV: pop hai giá trị đỉnh ngăn xếp (pop bbb trước, rồi pop aaa), tính a op ba\ \text{op}\ ba op b rồi đẩy kết quả trở lại (DIV là chia lấy phần nguyên làm tròn về 0; đề đảm bảo mẫu khác 0).
    • DUP: nhân đôi giá trị đỉnh ngăn xếp (đẩy thêm một bản sao).
    • SWAP: hoán đổi hai giá trị trên cùng của ngăn xếp.
    • JMP addr: nhảy (không điều kiện) tới dòng lệnh chỉ số addr.
    • JZ addr: pop giá trị đỉnh; nếu bằng 000 thì nhảy tới addr, ngược lại thực thi dòng kế tiếp.
    • CALL addr: đẩy địa chỉ dòng kế tiếp (địa chỉ trả về) vào một ngăn xếp lời gọi riêng biệt với ngăn xếp dữ liệu, rồi nhảy tới addr.
    • RET: pop địa chỉ trả về từ ngăn xếp lời gọi và nhảy tới đó.
    • PRINT: pop giá trị đỉnh ngăn xếp dữ liệu và in ra một dòng.
    • HALT: dừng máy ngay lập tức.

    Đề đảm bảo mọi chương trình test luôn dừng (bằng HALT hoặc chạy hết chương trình) trong không quá 10610^6106 lệnh được thực thi, và không có thao tác nào truy cập ngăn xếp khi đang rỗng.

    Ví dụ (đếm ngược, dùng DUP/JZ/JMP): chương trình 9 dòng PUSH 3 / DUP / JZ 8 / DUP / PRINT / PUSH 1 / SUB / JMP 1 / HALT in ra lần lượt 3, 2, 1.

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

      Dòng đầu chứa số nguyên nnn (1≤n≤20001 \le n \le 20001≤n≤2000). nnn dòng tiếp theo, mỗi dòng một lệnh bytecode theo đúng định dạng trên (các thành phần cách nhau bởi một khoảng trắng, addr là chỉ số dòng 0-based).

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

      In ra các giá trị được lệnh PRINT đưa ra, theo đúng thứ tự thực thi, mỗi giá trị trên một dòng riêng. Nếu không có PRINT nào được thực thi, không in gì cả.

    Ví dụ:

    Đầu vào:

    1
HALT

    Đầu ra:

    Đầu vào:

    9
PUSH 3
DUP
JZ 8
DUP
PRINT
PUSH 1
SUB
JMP 1
HALT

    Đầu ra:

    3
2
1

    Đang tải editor...