solution

Khi sinh mã máy cho một biểu thức số học từ cây cú pháp AST, trình biên dịch cần xác định số thanh ghi tối thiểu cần dùng để tính giá trị biểu thức, với giả thiết có thể tự do chọn thứ tự tính nhánh trái/phải trước (miễn là tính xong một nhánh, kết quả được giữ trong một thanh ghi cho tới khi dùng), và không cho phép lưu tạm ra bộ nhớ (không spill). Đây chính là thuật toán gán nhãn Sethi–Ullman kinh điển.

Nhãn (label) của một nút được định nghĩa đệ quy như sau:

• Nếu nút là lá (biến hoặc hằng số): $label = 1$ (cần nạp giá trị vào $1$ thanh ghi).
• Nếu nút là toán tử nhị phân với con trái có nhãn $l$, con phải có nhãn $r$:
  • nếu $l \neq r$: $label = \max(l, r)$;
  • nếu $l = r$: $label = l + 1$.

Nhãn của nút gốc chính là số thanh ghi tối thiểu cần thiết để tính toàn bộ biểu thức.

Ví dụ: + a + b c — cây con + b c có nhãn $2$ (vì $1=1 \Rightarrow 1+1$); nút gốc có con trái nhãn $1$ (lá a), con phải nhãn $2$, hai nhãn khác nhau nên nhãn gốc $=\max(1,2)=2$.