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 qua đồ thị phụ thuộc biến

    Một số ngôn ngữ cho phép suy diễn kiểu (type inference) cho biến mà không cần khai báo kiểu tường minh: kiểu của biến được suy ra từ vế phải của lệnh gán duy nhất định nghĩa nó. Vế phải của các lệnh gán có thể tham chiếu đến các biến khác theo bất kỳ thứ tự nào trong chương trình (kể cả tham chiếu "xuôi" tới biến được định nghĩa ở dòng sau), vì vậy việc suy diễn kiểu phải được thực hiện như duyệt một đồ thị phụ thuộc (dependency graph), không đơn thuần theo thứ tự dòng lệnh.

    Chương trình gồm nnn lệnh gán, mỗi biến xuất hiện ở vế trái đúng một lần duy nhất trong toàn bộ chương trình. Mỗi lệnh có một trong hai dạng:

    • tên = X — gán trực tiếp, với X là một hằng số (phân loại như bài kiểm tra kiểu biểu thức số học) hoặc tên một biến khác.
    • tên = X op Y — với op ∈{+,−,∗,/}\in \{+,-,*,/\}∈{+,−,∗,/}, X và Y mỗi cái là hằng số hoặc tên biến; áp dụng đúng luật kiểm tra kiểu của bài kiểm tra kiểu biểu thức số học (widening int→float, string+string→string, còn lại là lỗi).

    Kiểu của một biến được suy diễn đệ quy theo kiểu của các biến/hằng số nó phụ thuộc vào. Một biến bị coi là lỗi kiểu (không suy diễn được kiểu cụ thể) nếu xảy ra bất kỳ điều nào sau: vế phải tham chiếu tới một biến không tồn tại (không được gán ở đâu trong chương trình); tồn tại chu trình phụ thuộc (ví dụ a = b và b = a mà không có hằng số neo giá trị); hoặc phép toán op được áp dụng lên các kiểu không hợp lệ theo luật ở trên (lỗi sẽ lan truyền: nếu X hoặc Y đã bị lỗi kiểu thì tên cũng bị lỗi kiểu).

    Ví dụ: với 2 lệnh c = a + b rồi a = 5, b = 2.5 (thứ tự tuỳ ý), suy ra a: int, b: float, c: float (nhờ widening).

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

      Dòng đầu là số nguyên nnn (1≤n≤5001 \le n \le 5001≤n≤500) — số lệnh gán. nnn dòng tiếp theo, mỗi dòng là một lệnh gán ở một trong hai dạng mô tả ở trên, các token cách nhau bởi khoảng trắng (tên = X gồm 3 token, tên = X op Y gồm 5 token). Tên biến không trùng với các từ khoá true, false, và không phải là chuỗi số.

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

      In ra đúng nnn dòng theo thứ tự xuất hiện của các lệnh gán trong input, mỗi dòng có định dạng tên: kiểu (ví dụ a: int) nếu suy diễn được kiểu cụ thể (int, float, bool, hoặc string), hoặc tên: Type Error nếu biến đó bị lỗi kiểu như mô tả ở trên.

    Ví dụ:

    Đầu vào:

    1
a = 5

    Đầu ra:

    a: int

    Đầu vào:

    3
a = 5
b = 2.5
c = a + b

    Đầu ra:

    a: int
b: float
c: float

    Đang tải editor...