solution

Biểu diễn cây cú pháp của một biểu thức số học bằng ký pháp tiền tố (prefix) ngoặc lồng nhau, trong đó mỗi nút là một trong bốn dạng token (dấu ngoặc ( ) là token riêng biệt, mọi token cách nhau đúng một khoảng trắng):

• hằng nguyên: chuỗi chữ số (có thể có dấu - đầu), không chứa . → kiểu int, giá trị là chính nó.
• hằng thực: chứa dấu chấm . → kiểu float, giá trị là chính nó.
• định danh: tra bảng ký hiệu để biết kiểu (int, float hoặc bool); giá trị là không xác định (unknown) — input đảm bảo mọi định danh dùng trong biểu thức có mặt trong bảng ký hiệu.
• biểu thức toán tử: ( OP L R ) với OP $\in \{+,-,*\}$, L, R là hai cây con (mỗi cây con cũng theo một trong bốn dạng trên).

Luật ngữ nghĩa SDT (thuộc tính tổng hợp) cho một nút ( OP L R ):

1. Kiểu (type): nếu type(L) hoặc type(R) là bool → cả biểu thức là lỗi kiểu (không dùng bool trong phép toán số học); lỗi lan truyền lên toàn cây (nếu một cây con là lỗi, nút cha cũng là lỗi). Ngược lại, nếu type(L) = type(R) = int thì type = int; nếu không (có ít nhất một float, không có bool) thì type = float.
2. Giá trị (value), chỉ tính khi không có lỗi kiểu: nếu value(L) và value(R) đều xác định (khác unknown) thì value = value(L) OP value(R) (số học thông thường, ép về kiểu kết quả — nếu type = int thì lấy phần nguyên của kết quả, dữ liệu vào đảm bảo phép tính giữa các số nguyên luôn cho kết quả nguyên đúng); nếu value(L) hoặc value(R) là unknown (do có định danh) thì value của nút cũng là unknown.

Ví dụ 1: bảng x:int, y:float, biểu thức ( + ( * x 2 ) y ): (* x 2) có type int nhưng value unknown (vì x là định danh); nút gốc có type float (vì y là float), value unknown (lan từ nhánh trái). Kết quả: float UNKNOWN.

Ví dụ 2: không có biến, biểu thức ( + ( * 2 3 ) 4.0 ): (* 2 3) = int 6; gốc = float, value = $6 + 4.0 = 10.0$. Kết quả: float 10.000000.

Ví dụ 3: bảng b:bool, biểu thức ( + b 1 ): b có type bool được dùng trực tiếp làm toán hạng → lỗi kiểu. Kết quả: ERROR.