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] Nhãn Sethi-Ullman — số thanh ghi tối thiểu khi sinh mã

    Khi sinh mã máy đích cho một biểu thức số học sử dụng thanh ghi (register) thay vì ngăn xếp bộ nhớ, một câu hỏi quan trọng là: cần tối thiểu bao nhiêu thanh ghi để tính giá trị biểu thức mà không phải lưu tạm bất kỳ kết quả trung gian nào ra bộ nhớ (không spill)? Thuật toán Sethi-Ullman trả lời câu hỏi này bằng cách gán cho mỗi nút của cây cú pháp biểu thức một nhãn (label), tính từ lá lên gốc, theo quy tắc:

    • Nút lá (biến hoặc hằng số): nhãn =1= 1=1.
    • Nút trong ứng với một toán tử hai ngôi, có con trái nhãn LLL và con phải nhãn RRR:
      • Nếu L=RL = RL=R thì nhãn =L+1= L + 1=L+1.
      • Nếu L≠RL \ne RL=R thì nhãn =max⁡(L,R)= \max(L, R)=max(L,R).

    Nhãn của nút gốc chính là số thanh ghi tối thiểu cần thiết để tính biểu thức không cần lưu tạm ra bộ nhớ. Cho biểu thức dưới dạng cây cú pháp (biểu diễn bằng ký pháp tiền tố — Ba Lan), hãy tính nhãn Sethi-Ullman của nút gốc.

    Ví dụ: biểu thức trung tố (a+b)×c(a+b) \times c(a+b)×c viết ở dạng tiền tố là * + a b c. Nút + a b có nhãn max⁡(1,1)+1=2\max(1,1)+1=2max(1,1)+1=2 (vì hai con bằng nhãn); nút gốc * có con trái nhãn 222, con phải (lá c) nhãn 111, khác nhau nên nhãn gốc =max⁡(2,1)=2=\max(2,1)=2=max(2,1)=2.

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

      Một dòng duy nhất chứa biểu thức ở dạng tiền tố (ký pháp Ba Lan), các token cách nhau bởi đúng một khoảng trắng. Toán tử hai ngôi thuộc + - * /; toán hạng lá là biến (một hoặc nhiều chữ cái thường) hoặc hằng số nguyên. Đề bảo đảm biểu thức tiền tố đúng cú pháp và không rỗng (luôn có ít nhất một token).

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

      In ra đúng một số nguyên duy nhất — nhãn Sethi-Ullman của nút gốc (số thanh ghi tối thiểu cần thiết).

    Ví dụ:

    Đầu vào:

    a

    Đầu ra:

    1

    Đầu vào:

    + a b

    Đầu ra:

    2

    Đang tải editor...