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] Gọi hàm CALL/RET và phát hiện tràn ngăn xếp gọi

    Mở rộng máy ảo ở bài toán trước với cơ chế gọi hàm bằng một ngăn xếp gọi hàm (call stack) tường minh, có giới hạn độ sâu tối đa DDD. Máy ảo vẫn có thanh ghi ACC (khởi tạo 0) và IP (khởi tạo 1), chương trình có nnn lệnh đánh số 1..n1..n1..n, gồm:

    • SET x, ADD x, SUB x: như bài trước.
    • CALL L: nếu ngăn xếp gọi hàm hiện đang có đúng DDD phần tử, chương trình dừng do tràn ngăn xếp gọi hàm; ngược lại, đẩy địa chỉ lệnh kế tiếp (IP+1) vào ngăn xếp gọi hàm rồi nhảy tới lệnh LLL.
    • RET: nếu ngăn xếp gọi hàm rỗng, lệnh này coi như kết thúc chương trình (giống HALT); ngược lại lấy (pop) địa chỉ ở đỉnh ngăn xếp gọi hàm và nhảy IP tới đó.
    • HALT: dừng chương trình.

    Cũng như bài trước, nếu chương trình thực thi vượt quá 10610^6106 bước mà chưa dừng (theo HALT hoặc RET khi ngăn xếp gọi hàm rỗng), hoặc IP đi ra ngoài đoạn [1,n][1,n][1,n] mà chưa dừng, ta coi là không dừng.

    Ví dụ: D=2D=2D=2, chương trình 4 lệnh CALL 3, HALT, ADD 10, RET: gọi hàm tại địa chỉ 3, cộng 10 vào ACC, RET quay lại địa chỉ 2 và HALT; tổng cộng 4 bước, ACC cuối bằng 10.

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

      Dòng đầu gồm hai số nguyên nnn và DDD (1≤n≤10001 \le n \le 10001≤n≤1000, 0≤D≤10000 \le D \le 10000≤D≤1000). nnn dòng tiếp theo là các lệnh (∣x∣≤109|x| \le 10^9∣x∣≤109, 1≤L≤n1 \le L \le n1≤L≤n).

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

      Nếu chương trình dừng bình thường (qua HALT hoặc RET khi ngăn xếp gọi hàm rỗng) trong giới hạn 10610^6106 bước, in số bước thực thi và giá trị ACC cuối, cách nhau một dấu cách. Nếu xảy ra tràn ngăn xếp gọi hàm tại một lệnh CALL, in STACK OVERFLOW. Nếu vượt quá giới hạn bước mà chưa dừng và cũng chưa tràn ngăn xếp, in TIMEOUT.

    Ví dụ:

    Đầu vào:

    1 1
RET

    Đầu ra:

    1 0

    Đầu vào:

    4 2
CALL 3
HALT
ADD 10
RET

    Đầu ra:

    4 10

    Đang tải editor...