solution

Khi sinh mã cho một khối lệnh, trình biên dịch cần cấp phát vị trí lưu trữ (offset trong khung ngăn xếp — stack frame) cho từng biến cục bộ. Một chiến lược đơn giản và phổ biến là bộ cấp phát kiểu ngăn xếp (stack allocator): duy trì một con trỏ khung hiện tại $p$ (ban đầu $p=0$); mỗi khi khai báo một biến kiểu $t$ có kích thước $\text{size}(t)$ byte, biến đó được gán offset bằng giá trị $p$ hiện tại, sau đó $p$ tăng thêm $\text{size}(t)$; khi một khối lệnh kết thúc, mọi biến cục bộ khai báo bên trong khối đó được giải phóng — con trỏ $p$ được khôi phục về đúng giá trị mà nó có ngay trước khi khối đó mở, để không gian này có thể được tái sử dụng bởi các khối anh em (sibling) tiếp theo.

Kích thước các kiểu dữ liệu: int = $4$ byte, char = $1$ byte, bool = $1$ byte, double = $8$ byte. Không cần căn chỉnh (alignment) — cấp phát liên tiếp theo đúng kích thước.

Cho dãy $n$ lệnh, mỗi lệnh thuộc một trong ba dạng:

• BEGIN: mở một khối lệnh mới — ghi nhớ giá trị $p$ hiện tại.
• END: đóng khối lệnh gần nhất đang mở — khôi phục $p$ về giá trị đã ghi nhớ khi khối đó mở (nếu không có khối nào đang mở thì bỏ qua).
• DECL x t: khai báo biến x kiểu t ($t \in \{\texttt{int}, \texttt{char}, \texttt{bool}, \texttt{double}\}$) trong khối hiện tại, theo đúng cơ chế cấp phát ở trên.

Với mỗi lệnh DECL, in ra offset được cấp cho biến đó. Sau khi xử lý xong toàn bộ $n$ lệnh, in thêm một dòng cuối cùng là kích thước khung ngăn xếp cần thiết — giá trị lớn nhất mà $p$ từng đạt được trong suốt quá trình (high-water mark), vì đó chính là dung lượng tối thiểu cần cấp phát sẵn cho toàn bộ hàm.

Ví dụ: với dãy lệnh

7
DECL a int
BEGIN
DECL b double
DECL c char
END
BEGIN
DECL d int

a được offset $0$ ($p: 0\to4$); vào khối con, b offset $4$ ($p:4\to12$), c offset $12$ ($p:12\to13$); khối đóng, $p$ khôi phục về $4$; khối mới mở, d offset $4$ ($p:4\to8$). Kích thước khung lớn nhất từng đạt là $13$. Kết quả in ra:

0
4
12
4
13