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 lời gọi hàm với ngăn xếp gọi hàm

    Xây dựng trình thông dịch cho một ngôn ngữ mini có hỗ trợ định nghĩa và gọi hàm — mô phỏng cách một trình biên dịch/thông dịch quản lý ngăn xếp gọi hàm (call stack) và phạm vi biến cục bộ (local scope) cho mỗi lần gọi.

    Chương trình gồm một số khối định nghĩa hàm, theo sau là đúng một khối MAIN:

    FUNC ten_ham p1 p2 ...
<câu lệnh>
...
RETURN v
ENDFUNC
...
MAIN
<câu lệnh>
...
ENDMAIN

    Trong đó p1 p2 ... là các tham số hình thức (biến cục bộ) của hàm, có thể không có tham số nào. Bên trong thân hàm và bên trong MAIN, các câu lệnh hợp lệ (mỗi dòng một câu lệnh, biến/tham số là định danh chữ cái thường, một biến chưa được gán mặc định có giá trị 000) gồm:

    • SET x v, ADD x v, SUB x v, MUL x v: gán/cộng/trừ/nhân vào biến xxx giá trị vvv (vvv là số nguyên hoặc tên một biến cùng phạm vi).
    • CALL x ten_ham a1 a2 ...: gọi hàm ten_ham với các đối số a1,a2,…a_1, a_2, \dotsa1​,a2​,… (mỗi đối số là số nguyên hoặc tên biến cùng phạm vi hiện tại), rồi gán giá trị trả về của lời gọi vào biến xxx. Số lượng đối số luôn khớp với số tham số hình thức của hàm được gọi.
    • PRINT x: chỉ xuất hiện trong MAIN, in ra giá trị hiện tại của biến xxx.

    Câu lệnh cuối cùng trong thân mỗi hàm luôn là RETURN v (vvv là số nguyên hoặc tên biến cục bộ), kết thúc hàm và trả về giá trị vvv cho lời gọi. Biến của mỗi hàm (kể cả tham số) là cục bộ — hoàn toàn tách biệt với biến của MAIN và của các lần gọi hàm khác. Đồ thị gọi hàm được đảm bảo không có chu trình (một hàm không bao giờ gọi trực tiếp hoặc gián tiếp tới chính nó), do đó không phát sinh đệ quy.

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

      Dòng đầu là số nguyên nnn (1≤n≤5001 \le n \le 5001≤n≤500) — tổng số dòng chương trình tiếp theo (bao gồm cả các dòng FUNC, ENDFUNC, MAIN, ENDMAIN). nnn dòng tiếp theo là nội dung chương trình như mô tả.

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

      In ra các giá trị được lệnh PRINT (trong MAIN) xuất ra theo đúng thứ tự thực thi, mỗi giá trị một dòng.

      Ví dụ:

      Input:

      16
FUNC square x
SET r x
MUL r x
RETURN r
ENDFUNC
FUNC sumsq a b
CALL sa square a
CALL sb square b
SET t sa
ADD t sb
RETURN t
ENDFUNC
MAIN
CALL result sumsq 3 4
PRINT result
ENDMAIN

      Output:

      25

      (vì 32+42=9+16=253^2+4^2=9+16=2532+42=9+16=25)

    Ví dụ:

    Đầu vào:

    4
MAIN
SET a 5
PRINT a
ENDMAIN

    Đầu ra:

    5

    Đầu vào:

    16
FUNC square x
SET r x
MUL r x
RETURN r
ENDFUNC
FUNC sumsq a b
CALL sa square a
CALL sb square b
SET t sa
ADD t sb
RETURN t
ENDFUNC
MAIN
CALL result sumsq 3 4
PRINT result
ENDMAIN

    Đầu ra:

    25

    Đang tải editor...