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] Suy diễn kiểu cho biểu thức hậu tố (RPN) với ép kiểu ngầm định

    Cho bảng ký hiệu ánh xạ tên biến sang kiểu (int hoặc float) và một biểu thức hậu tố (Reverse Polish Notation — RPN) gồm các token cách nhau bởi khoảng trắng. Mỗi token là một trong:

    • hằng nguyên: chỉ gồm chữ số, có thể có dấu - đứng đầu, không chứa dấu chấm → kiểu int;
    • hằng thực: chứa dấu chấm . → kiểu float;
    • định danh: bắt đầu bằng chữ cái hoặc _ → tra bảng ký hiệu; nếu không có trong bảng, đây là lỗi "biến chưa khai báo";
    • toán tử hai ngôi: một trong + - * /.

    Quy tắc suy diễn kiểu tổng hợp (synthesized attribute) khi áp dụng một toán tử cho hai toán hạng có kiểu t1t_1t1​ (toán hạng bên trái, được đẩy vào ngăn xếp trước) và t2t_2t2​ (toán hạng bên phải, đẩy sau):

    1. Nếu toán tử là /: kết quả luôn có kiểu float (ngôn ngữ này không có phép chia nguyên). Với mỗi toán hạng trong số t1,t2t_1, t_2t1​,t2​ có kiểu int, tính là một lần ép kiểu ngầm định (int → float) — nếu cả hai đều int thì đếm 2 lần.
    2. Nếu toán tử là + - * và t1=t2=intt_1 = t_2 = \texttt{int}t1​=t2​=int: kết quả có kiểu int, không có ép kiểu nào.
    3. Nếu toán tử là + - * và ít nhất một trong t1,t2t_1, t_2t1​,t2​ là float: kết quả có kiểu float; với mỗi toán hạng có kiểu int trong hai toán hạng, tính là một lần ép kiểu ngầm định.

    Xử lý toàn bộ biểu thức theo đúng thứ tự token trái sang phải (ngăn xếp toán hạng luôn đủ, input RPN hợp lệ về cú pháp). Nếu gặp định danh chưa khai báo, dừng xử lý và báo lỗi ngay tại token đó (token đầu tiên theo thứ tự xuất hiện gây lỗi).

    Ví dụ 1: bảng x:int, y:float, biểu thức x y +: t1=int,t2=floatt_1=\texttt{int}, t_2=\texttt{float}t1​=int,t2​=float → kết quả float, 1 lần ép kiểu (cho x). Ví dụ 2: biểu thức 3 4 / (không cần bảng ký hiệu): cả hai hằng là int, toán tử / → kết quả float, 2 lần ép kiểu (mỗi hằng một lần).

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

      Dòng đầu tiên chứa số nguyên kkk (0≤k≤1000 \le k \le 1000≤k≤100) — số biến trong bảng ký hiệu. kkk dòng tiếp theo, mỗi dòng name type (type ∈\in∈ {int, float}). Dòng cuối cùng là biểu thức RPN — các token cách nhau đúng một khoảng trắng, luôn có ít nhất 1 token.

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

      In đúng một dòng:

      • Nếu không có lỗi: TYPE t C với t là kiểu cuối cùng của biểu thức (int hoặc float) và C là tổng số lần ép kiểu ngầm định đã đếm được.
      • Nếu có định danh chưa khai báo: ERROR UNDECLARED name (name là định danh chưa khai báo đầu tiên theo thứ tự token).

      Ví dụ với x y + (bảng x:int, y:float): TYPE float 1. Với 3 4 /: TYPE float 2.

    Ví dụ:

    Đầu vào:

    0
3 4 /

    Đầu ra:

    TYPE float 2

    Đầu vào:

    2
x int
y float
x y +

    Đầu ra:

    TYPE float 1

    Đang tải editor...